diff options
Diffstat (limited to 'src/include/lib/pairingheap.h')
-rw-r--r-- | src/include/lib/pairingheap.h | 102 |
1 files changed, 102 insertions, 0 deletions
diff --git a/src/include/lib/pairingheap.h b/src/include/lib/pairingheap.h new file mode 100644 index 0000000..73d1a30 --- /dev/null +++ b/src/include/lib/pairingheap.h @@ -0,0 +1,102 @@ +/* + * pairingheap.h + * + * A Pairing Heap implementation + * + * Portions Copyright (c) 2012-2021, PostgreSQL Global Development Group + * + * src/include/lib/pairingheap.h + */ + +#ifndef PAIRINGHEAP_H +#define PAIRINGHEAP_H + +#include "lib/stringinfo.h" + +/* Enable if you need the pairingheap_dump() debug function */ +/* #define PAIRINGHEAP_DEBUG */ + +/* + * This represents an element stored in the heap. Embed this in a larger + * struct containing the actual data you're storing. + * + * A node can have multiple children, which form a double-linked list. + * first_child points to the node's first child, and the subsequent children + * can be found by following the next_sibling pointers. The last child has + * next_sibling == NULL. The prev_or_parent pointer points to the node's + * previous sibling, or if the node is its parent's first child, to the + * parent. + */ +typedef struct pairingheap_node +{ + struct pairingheap_node *first_child; + struct pairingheap_node *next_sibling; + struct pairingheap_node *prev_or_parent; +} pairingheap_node; + +/* + * Return the containing struct of 'type' where 'membername' is the + * pairingheap_node pointed at by 'ptr'. + * + * This is used to convert a pairingheap_node * back to its containing struct. + */ +#define pairingheap_container(type, membername, ptr) \ + (AssertVariableIsOfTypeMacro(ptr, pairingheap_node *), \ + AssertVariableIsOfTypeMacro(((type *) NULL)->membername, pairingheap_node), \ + ((type *) ((char *) (ptr) - offsetof(type, membername)))) + +/* + * Like pairingheap_container, but used when the pointer is 'const ptr' + */ +#define pairingheap_const_container(type, membername, ptr) \ + (AssertVariableIsOfTypeMacro(ptr, const pairingheap_node *), \ + AssertVariableIsOfTypeMacro(((type *) NULL)->membername, pairingheap_node), \ + ((const type *) ((const char *) (ptr) - offsetof(type, membername)))) + +/* + * For a max-heap, the comparator must return <0 iff a < b, 0 iff a == b, + * and >0 iff a > b. For a min-heap, the conditions are reversed. + */ +typedef int (*pairingheap_comparator) (const pairingheap_node *a, + const pairingheap_node *b, + void *arg); + +/* + * A pairing heap. + * + * You can use pairingheap_allocate() to create a new palloc'd heap, or embed + * this in a larger struct, set ph_compare and ph_arg directly and initialize + * ph_root to NULL. + */ +typedef struct pairingheap +{ + pairingheap_comparator ph_compare; /* comparison function */ + void *ph_arg; /* opaque argument to ph_compare */ + pairingheap_node *ph_root; /* current root of the heap */ +} pairingheap; + +extern pairingheap *pairingheap_allocate(pairingheap_comparator compare, + void *arg); +extern void pairingheap_free(pairingheap *heap); +extern void pairingheap_add(pairingheap *heap, pairingheap_node *node); +extern pairingheap_node *pairingheap_first(pairingheap *heap); +extern pairingheap_node *pairingheap_remove_first(pairingheap *heap); +extern void pairingheap_remove(pairingheap *heap, pairingheap_node *node); + +#ifdef PAIRINGHEAP_DEBUG +extern char *pairingheap_dump(pairingheap *heap, + void (*dumpfunc) (pairingheap_node *node, StringInfo buf, void *opaque), + void *opaque); +#endif + +/* Resets the heap to be empty. */ +#define pairingheap_reset(h) ((h)->ph_root = NULL) + +/* Is the heap empty? */ +#define pairingheap_is_empty(h) ((h)->ph_root == NULL) + +/* Is there exactly one node in the heap? */ +#define pairingheap_is_singular(h) \ + ((h)->ph_root && (h)->ph_root->first_child == NULL) + +#endif /* PAIRINGHEAP_H */ |