1 /* 2 * pairingheap.h 3 * 4 * A Pairing Heap implementation 5 * 6 * Portions Copyright (c) 2012-2016, PostgreSQL Global Development Group 7 * 8 * src/include/lib/pairingheap.h 9 */ 10 11 #ifndef PAIRINGHEAP_H 12 #define PAIRINGHEAP_H 13 14 #include "lib/stringinfo.h" 15 16 /* Enable if you need the pairingheap_dump() debug function */ 17 /* #define PAIRINGHEAP_DEBUG */ 18 19 /* 20 * This represents an element stored in the heap. Embed this in a larger 21 * struct containing the actual data you're storing. 22 * 23 * A node can have multiple children, which form a double-linked list. 24 * first_child points to the node's first child, and the subsequent children 25 * can be found by following the next_sibling pointers. The last child has 26 * next_sibling == NULL. The prev_or_parent pointer points to the node's 27 * previous sibling, or if the node is its parent's first child, to the 28 * parent. 29 */ 30 typedef struct pairingheap_node 31 { 32 struct pairingheap_node *first_child; 33 struct pairingheap_node *next_sibling; 34 struct pairingheap_node *prev_or_parent; 35 } pairingheap_node; 36 37 /* 38 * Return the containing struct of 'type' where 'membername' is the 39 * pairingheap_node pointed at by 'ptr'. 40 * 41 * This is used to convert a pairingheap_node * back to its containing struct. 42 */ 43 #define pairingheap_container(type, membername, ptr) \ 44 (AssertVariableIsOfTypeMacro(ptr, pairingheap_node *), \ 45 AssertVariableIsOfTypeMacro(((type *) NULL)->membername, pairingheap_node), \ 46 ((type *) ((char *) (ptr) - offsetof(type, membername)))) 47 48 /* 49 * Like pairingheap_container, but used when the pointer is 'const ptr' 50 */ 51 #define pairingheap_const_container(type, membername, ptr) \ 52 (AssertVariableIsOfTypeMacro(ptr, const pairingheap_node *), \ 53 AssertVariableIsOfTypeMacro(((type *) NULL)->membername, pairingheap_node), \ 54 ((const type *) ((const char *) (ptr) - offsetof(type, membername)))) 55 56 /* 57 * For a max-heap, the comparator must return <0 iff a < b, 0 iff a == b, 58 * and >0 iff a > b. For a min-heap, the conditions are reversed. 59 */ 60 typedef int (*pairingheap_comparator) (const pairingheap_node *a, 61 const pairingheap_node *b, 62 void *arg); 63 64 /* 65 * A pairing heap. 66 * 67 * You can use pairingheap_allocate() to create a new palloc'd heap, or embed 68 * this in a larger struct, set ph_compare and ph_arg directly and initialize 69 * ph_root to NULL. 70 */ 71 typedef struct pairingheap 72 { 73 pairingheap_comparator ph_compare; /* comparison function */ 74 void *ph_arg; /* opaque argument to ph_compare */ 75 pairingheap_node *ph_root; /* current root of the heap */ 76 } pairingheap; 77 78 extern pairingheap *pairingheap_allocate(pairingheap_comparator compare, 79 void *arg); 80 extern void pairingheap_free(pairingheap *heap); 81 extern void pairingheap_add(pairingheap *heap, pairingheap_node *node); 82 extern pairingheap_node *pairingheap_first(pairingheap *heap); 83 extern pairingheap_node *pairingheap_remove_first(pairingheap *heap); 84 extern void pairingheap_remove(pairingheap *heap, pairingheap_node *node); 85 86 #ifdef PAIRINGHEAP_DEBUG 87 extern char *pairingheap_dump(pairingheap *heap, 88 void (*dumpfunc) (pairingheap_node *node, StringInfo buf, void *opaque), 89 void *opaque); 90 #endif 91 92 /* Resets the heap to be empty. */ 93 #define pairingheap_reset(h) ((h)->ph_root = NULL) 94 95 /* Is the heap empty? */ 96 #define pairingheap_is_empty(h) ((h)->ph_root == NULL) 97 98 /* Is there exactly one node in the heap? */ 99 #define pairingheap_is_singular(h) \ 100 ((h)->ph_root && (h)->ph_root->first_child == NULL) 101 102 #endif /* PAIRINGHEAP_H */ 103