PostgreSQL Source Code git master
pairingheap.h File Reference
#include "lib/stringinfo.h"
Include dependency graph for pairingheap.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  pairingheap_node
 
struct  pairingheap
 

Macros

#define pairingheap_container(type, membername, ptr)
 
#define pairingheap_const_container(type, membername, ptr)
 
#define pairingheap_reset(h)   ((h)->ph_root = NULL)
 
#define pairingheap_is_empty(h)   ((h)->ph_root == NULL)
 
#define pairingheap_is_singular(h)    ((h)->ph_root && (h)->ph_root->first_child == NULL)
 

Typedefs

typedef struct pairingheap_node pairingheap_node
 
typedef int(* pairingheap_comparator) (const pairingheap_node *a, const pairingheap_node *b, void *arg)
 
typedef struct pairingheap pairingheap
 

Functions

pairingheappairingheap_allocate (pairingheap_comparator compare, void *arg)
 
void pairingheap_free (pairingheap *heap)
 
void pairingheap_add (pairingheap *heap, pairingheap_node *node)
 
pairingheap_nodepairingheap_first (pairingheap *heap)
 
pairingheap_nodepairingheap_remove_first (pairingheap *heap)
 
void pairingheap_remove (pairingheap *heap, pairingheap_node *node)
 

Macro Definition Documentation

◆ pairingheap_const_container

#define pairingheap_const_container (   type,
  membername,
  ptr 
)
Value:
AssertVariableIsOfTypeMacro(((type *) NULL)->membername, pairingheap_node), \
((const type *) ((const char *) (ptr) - offsetof(type, membername))))
#define AssertVariableIsOfTypeMacro(varname, typename)
Definition: c.h:941
const char * type

Definition at line 51 of file pairingheap.h.

◆ pairingheap_container

#define pairingheap_container (   type,
  membername,
  ptr 
)
Value:
AssertVariableIsOfTypeMacro(((type *) NULL)->membername, pairingheap_node), \
((type *) ((char *) (ptr) - offsetof(type, membername))))

Definition at line 43 of file pairingheap.h.

◆ pairingheap_is_empty

#define pairingheap_is_empty (   h)    ((h)->ph_root == NULL)

Definition at line 96 of file pairingheap.h.

◆ pairingheap_is_singular

#define pairingheap_is_singular (   h)     ((h)->ph_root && (h)->ph_root->first_child == NULL)

Definition at line 99 of file pairingheap.h.

◆ pairingheap_reset

#define pairingheap_reset (   h)    ((h)->ph_root = NULL)

Definition at line 93 of file pairingheap.h.

Typedef Documentation

◆ pairingheap

typedef struct pairingheap pairingheap

◆ pairingheap_comparator

typedef int(* pairingheap_comparator) (const pairingheap_node *a, const pairingheap_node *b, void *arg)

Definition at line 60 of file pairingheap.h.

◆ pairingheap_node

Function Documentation

◆ pairingheap_add()

void pairingheap_add ( pairingheap heap,
pairingheap_node node 
)

Definition at line 112 of file pairingheap.c.

113{
114 node->first_child = NULL;
115
116 /* Link the new node as a new tree */
117 heap->ph_root = merge(heap, heap->ph_root, node);
118 heap->ph_root->prev_or_parent = NULL;
119 heap->ph_root->next_sibling = NULL;
120}
static pairingheap_node * merge(pairingheap *heap, pairingheap_node *a, pairingheap_node *b)
Definition: pairingheap.c:79
struct pairingheap_node * next_sibling
Definition: pairingheap.h:33
struct pairingheap_node * prev_or_parent
Definition: pairingheap.h:34
struct pairingheap_node * first_child
Definition: pairingheap.h:32
pairingheap_node * ph_root
Definition: pairingheap.h:75

References pairingheap_node::first_child, merge(), pairingheap_node::next_sibling, pairingheap::ph_root, and pairingheap_node::prev_or_parent.

Referenced by ExportSnapshot(), GetNonHistoricCatalogSnapshot(), GetTransactionSnapshot(), gistScanPage(), RegisterSnapshotOnOwner(), ReorderBufferChangeMemoryUpdate(), reorderqueue_push(), SetTransactionSnapshot(), and spgAddSearchItemToQueue().

◆ pairingheap_allocate()

pairingheap * pairingheap_allocate ( pairingheap_comparator  compare,
void *  arg 
)

Definition at line 42 of file pairingheap.c.

43{
44 pairingheap *heap;
45
46 heap = (pairingheap *) palloc(sizeof(pairingheap));
47 heap->ph_compare = compare;
48 heap->ph_arg = arg;
49
50 heap->ph_root = NULL;
51
52 return heap;
53}
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
void * palloc(Size size)
Definition: mcxt.c:1317
void * arg
pairingheap_comparator ph_compare
Definition: pairingheap.h:73
void * ph_arg
Definition: pairingheap.h:74

References arg, compare(), palloc(), pairingheap::ph_arg, pairingheap::ph_compare, and pairingheap::ph_root.

Referenced by ExecInitIndexScan(), gistrescan(), ReorderBufferAllocate(), and resetSpGistScanOpaque().

◆ pairingheap_first()

pairingheap_node * pairingheap_first ( pairingheap heap)

Definition at line 130 of file pairingheap.c.

131{
133
134 return heap->ph_root;
135}
#define Assert(condition)
Definition: c.h:815
#define pairingheap_is_empty(h)
Definition: pairingheap.h:96

References Assert, pairingheap_is_empty, and pairingheap::ph_root.

Referenced by IndexNextWithReorder(), ReorderBufferLargestTXN(), and SnapshotResetXmin().

◆ pairingheap_free()

void pairingheap_free ( pairingheap heap)

Definition at line 63 of file pairingheap.c.

64{
65 pfree(heap);
66}
void pfree(void *pointer)
Definition: mcxt.c:1521

References pfree().

◆ pairingheap_remove()

void pairingheap_remove ( pairingheap heap,
pairingheap_node node 
)

Definition at line 170 of file pairingheap.c.

171{
172 pairingheap_node *children;
173 pairingheap_node *replacement;
174 pairingheap_node *next_sibling;
175 pairingheap_node **prev_ptr;
176
177 /*
178 * If the removed node happens to be the root node, do it with
179 * pairingheap_remove_first().
180 */
181 if (node == heap->ph_root)
182 {
183 (void) pairingheap_remove_first(heap);
184 return;
185 }
186
187 /*
188 * Before we modify anything, remember the removed node's first_child and
189 * next_sibling pointers.
190 */
191 children = node->first_child;
192 next_sibling = node->next_sibling;
193
194 /*
195 * Also find the pointer to the removed node in its previous sibling, or
196 * if this is the first child of its parent, in its parent.
197 */
198 if (node->prev_or_parent->first_child == node)
199 prev_ptr = &node->prev_or_parent->first_child;
200 else
201 prev_ptr = &node->prev_or_parent->next_sibling;
202 Assert(*prev_ptr == node);
203
204 /*
205 * If this node has children, make a new subheap of the children and link
206 * the subheap in place of the removed node. Otherwise just unlink this
207 * node.
208 */
209 if (children)
210 {
211 replacement = merge_children(heap, children);
212
213 replacement->prev_or_parent = node->prev_or_parent;
214 replacement->next_sibling = node->next_sibling;
215 *prev_ptr = replacement;
216 if (next_sibling)
217 next_sibling->prev_or_parent = replacement;
218 }
219 else
220 {
221 *prev_ptr = next_sibling;
222 if (next_sibling)
223 next_sibling->prev_or_parent = node->prev_or_parent;
224 }
225}
pairingheap_node * pairingheap_remove_first(pairingheap *heap)
Definition: pairingheap.c:145
static pairingheap_node * merge_children(pairingheap *heap, pairingheap_node *children)
Definition: pairingheap.c:234

References Assert, pairingheap_node::first_child, merge_children(), pairingheap_node::next_sibling, pairingheap_remove_first(), pairingheap::ph_root, and pairingheap_node::prev_or_parent.

Referenced by AtEOXact_Snapshot(), InvalidateCatalogSnapshot(), ReorderBufferChangeMemoryUpdate(), and UnregisterSnapshotNoOwner().

◆ pairingheap_remove_first()

pairingheap_node * pairingheap_remove_first ( pairingheap heap)

Definition at line 145 of file pairingheap.c.

146{
147 pairingheap_node *result;
148 pairingheap_node *children;
149
151
152 /* Remove the root, and form a new heap of its children. */
153 result = heap->ph_root;
154 children = result->first_child;
155
156 heap->ph_root = merge_children(heap, children);
157 if (heap->ph_root)
158 {
159 heap->ph_root->prev_or_parent = NULL;
160 heap->ph_root->next_sibling = NULL;
161 }
162
163 return result;
164}

References Assert, pairingheap_node::first_child, merge_children(), pairingheap_node::next_sibling, pairingheap_is_empty, pairingheap::ph_root, and pairingheap_node::prev_or_parent.

Referenced by getNextGISTSearchItem(), pairingheap_remove(), reorderqueue_pop(), and spgGetNextQueueItem().