1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
/*
* pairingheap.h
*
* A Pairing Heap implementation
*
* Portions Copyright (c) 2012-2020, 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 */
|
