|
Crater Container Library 0.2.0
|
|
| |
|
Crater Container Library 0.2.0
|
|
|
| |
char data[] field (element data, stored polymorphically as a flexible length array).Intrusive data structures on the other hand have all the metadata stored in a struct which is the same for any type of element data, and then specialization to different types is handled by creating structs containing this metadata struct. EG, for a pairing heap, any struct containing a metadata struct of the correct type can be used as a pairing heap.
This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
Definition in file pheap.h.
Go to the source code of this file.
Data Structures | |
| struct | cr8r_pheap_node |
| struct | cr8r_pheap_ft |
| function table for pairing heaps note that since this is an intrusive data structure, base.size is actually the OFFSET of the cr8r_pheap_node struct within the outer struct, and cmp, alloc, and free deal with outer struct pointers. More... | |
Functions | |
| cr8r_pheap_node * | cr8r_pheap_new (void *key, cr8r_pheap_ft *, cr8r_pheap_node *first_child, cr8r_pheap_node *sibling, cr8r_pheap_node *parent) |
| Allocate a new pairing heap node using ft->alloc and initialize it. More... | |
| void * | cr8r_pheap_top (cr8r_pheap_node *, cr8r_pheap_ft *) |
| Return a pointer to the minimal data element of a pairing heap, or NULL if the heap is empty. More... | |
| cr8r_pheap_node * | cr8r_pheap_root (cr8r_pheap_node *) |
| Return a pointer to the root node given a pointer to any node in a heap. | |
| cr8r_pheap_node * | cr8r_pheap_meld (cr8r_pheap_node *a, cr8r_pheap_node *b, cr8r_pheap_ft *) |
| Combine two pairing heaps, invalidating them The nodes of the existing heaps are reused and re-linked so no new allocations are done, but the original heaps are mutated. More... | |
| cr8r_pheap_node * | cr8r_pheap_push (cr8r_pheap_node *, void *key, cr8r_pheap_ft *) |
| Insert an item into a pairing heap Allocates and initializes a new node for the new item. More... | |
| cr8r_pheap_node * | cr8r_pheap_pop (cr8r_pheap_node **r, cr8r_pheap_ft *) |
| Remove the root (minimal) element from a pairing heap. More... | |
| cr8r_pheap_node * | cr8r_pheap_decreased_key (cr8r_pheap_node *n, cr8r_pheap_ft *) |
| Restore the (min) heap invariant after decreasing the key of a node. More... | |
| void | cr8r_pheap_delete (cr8r_pheap_node *, cr8r_pheap_ft *) |
| Delete all nodes in a pairing heap. More... | |
| cr8r_pheap_node* cr8r_pheap_new | ( | void * | key, |
| cr8r_pheap_ft * | , | ||
| cr8r_pheap_node * | first_child, | ||
| cr8r_pheap_node * | sibling, | ||
| cr8r_pheap_node * | parent | ||
| ) |
Allocate a new pairing heap node using ft->alloc and initialize it.
Returns a pointer to a pheap node that lives within an outer struct (the pairing heap is said to be "intrusive" in the outer struct).
Note that this function is not really needed in the normal use case for this data structure. Typically, the pairing heap will be a secondary data structure stored in place within a hash table, avl tree, or so on. In that case, the other data structure will handle the allocations. If the pairing heap is the primary data structure, consider using a regualar binary heap instead.
| [in] | key | Pointer to an initializer for the outer struct. ft->base.size bytes are copied from here to the newly allocated node. WARNING: ft->base.size is the offset of the cr8r_pheap_node struct within the outer struct, so if the node struct is not the last member of the outer struct (including if there is padding due to alignment), or if there is padding in the struct and some other code cares about its value, this function does not work and the allocation must be done manually. |
| [in] | first_child,sibling,parent | Initializers for the intrusive struct's fields |
| void* cr8r_pheap_top | ( | cr8r_pheap_node * | , |
| cr8r_pheap_ft * | |||
| ) |
Return a pointer to the minimal data element of a pairing heap, or NULL if the heap is empty.
The pointer returned is to the outer struct.
| cr8r_pheap_node* cr8r_pheap_meld | ( | cr8r_pheap_node * | a, |
| cr8r_pheap_node * | b, | ||
| cr8r_pheap_ft * | |||
| ) |
Combine two pairing heaps, invalidating them The nodes of the existing heaps are reused and re-linked so no new allocations are done, but the original heaps are mutated.
| [in,out] | a,b | pointers to root nodes of two existing heaps. |
| cr8r_pheap_node* cr8r_pheap_push | ( | cr8r_pheap_node * | , |
| void * | key, | ||
| cr8r_pheap_ft * | |||
| ) |
Insert an item into a pairing heap Allocates and initializes a new node for the new item.
| [in] | key | Pointer to an initializer for the outer struct. ft->base.size bytes are copied from here to the newly allocated node. The same warning from cr8r_pheap_new applies. |
| cr8r_pheap_node* cr8r_pheap_pop | ( | cr8r_pheap_node ** | r, |
| cr8r_pheap_ft * | |||
| ) |
Remove the root (minimal) element from a pairing heap.
The input pointer is modified to indicate the new root. Does nothing if called on an empty heap.
| [in,out] | r | pointer to pointer to root node |
| cr8r_pheap_node* cr8r_pheap_decreased_key | ( | cr8r_pheap_node * | n, |
| cr8r_pheap_ft * | |||
| ) |
Restore the (min) heap invariant after decreasing the key of a node.
| [in] | n | the node whose key was decreased and may now be less than its parent |
| void cr8r_pheap_delete | ( | cr8r_pheap_node * | , |
| cr8r_pheap_ft * | |||
| ) |
Delete all nodes in a pairing heap.
The same note as for cr8r_pheap_new applies here: typically, the allocation should be handled by a primary data structure and the pairing heap should just be a secondary data structure.