src/include/lib/pairingheap.h

   1 /*
   2  * pairingheap.h
   3  *
   4  * A Pairing Heap implementation
   5  *
   6  * Portions Copyright (c) 2012-2021, 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 */