1/*
2 * pairingheap.h
3 *
4 * A Pairing Heap implementation
5 *
6 * Portions Copyright (c) 2012-2019, 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 */
30typedef 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 */
60typedef 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 */
71typedef 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
78extern pairingheap *pairingheap_allocate(pairingheap_comparator compare,
79 void *arg);
80extern void pairingheap_free(pairingheap *heap);
81extern void pairingheap_add(pairingheap *heap, pairingheap_node *node);
82extern pairingheap_node *pairingheap_first(pairingheap *heap);
83extern pairingheap_node *pairingheap_remove_first(pairingheap *heap);
84extern void pairingheap_remove(pairingheap *heap, pairingheap_node *node);
85
86#ifdef PAIRINGHEAP_DEBUG
87extern 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