PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
pairingheap.h
Go to the documentation of this file.
1 /*
2  * pairingheap.h
3  *
4  * A Pairing Heap implementation
5  *
6  * Portions Copyright (c) 2012-2017, 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 {
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 
79  void *arg);
80 extern void pairingheap_free(pairingheap *heap);
81 extern void pairingheap_add(pairingheap *heap, pairingheap_node *node);
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 */
void pairingheap_add(pairingheap *heap, pairingheap_node *node)
Definition: pairingheap.c:112
struct pairingheap_node * first_child
Definition: pairingheap.h:32
pairingheap_node * ph_root
Definition: pairingheap.h:75
pairingheap_node * pairingheap_remove_first(pairingheap *heap)
Definition: pairingheap.c:145
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
void * ph_arg
Definition: pairingheap.h:74
static char * buf
Definition: pg_test_fsync.c:65
void pairingheap_remove(pairingheap *heap, pairingheap_node *node)
Definition: pairingheap.c:170
struct pairingheap_node * next_sibling
Definition: pairingheap.h:33
pairingheap_comparator ph_compare
Definition: pairingheap.h:73
int(* pairingheap_comparator)(const pairingheap_node *a, const pairingheap_node *b, void *arg)
Definition: pairingheap.h:60
struct pairingheap pairingheap
pairingheap_node * pairingheap_first(pairingheap *heap)
Definition: pairingheap.c:130
pairingheap * pairingheap_allocate(pairingheap_comparator compare, void *arg)
Definition: pairingheap.c:42
struct pairingheap_node pairingheap_node
void * arg
void pairingheap_free(pairingheap *heap)
Definition: pairingheap.c:63
struct pairingheap_node * prev_or_parent
Definition: pairingheap.h:34