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:782
#define offsetof(type, field)
Definition: c.h:593

Definition at line 51 of file pairingheap.h.

Referenced by xmin_cmp().

◆ pairingheap_container

#define pairingheap_container (   type,
  membername,
  ptr 
)
Value:
AssertVariableIsOfTypeMacro(((type *) NULL)->membername, pairingheap_node), \
((type *) ((char *) (ptr) - offsetof(type, membername))))
#define AssertVariableIsOfTypeMacro(varname, typename)
Definition: c.h:782
#define offsetof(type, field)
Definition: c.h:593

Definition at line 43 of file pairingheap.h.

Referenced by GetOldestSnapshot(), and SnapshotResetXmin().

◆ pairingheap_is_empty

◆ pairingheap_is_singular

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

◆ pairingheap_reset

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

Definition at line 93 of file pairingheap.h.

Referenced by AtEOXact_Snapshot().

Typedef Documentation

◆ 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.

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(), reorderqueue_push(), and SetTransactionSnapshot().

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 }
struct pairingheap_node * first_child
Definition: pairingheap.h:32
pairingheap_node * ph_root
Definition: pairingheap.h:75
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

◆ pairingheap_allocate()

pairingheap* pairingheap_allocate ( pairingheap_comparator  compare,
void *  arg 
)

Definition at line 42 of file pairingheap.c.

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

Referenced by ExecInitIndexScan(), and gistrescan().

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 }
pairingheap_node * ph_root
Definition: pairingheap.h:75
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
void * ph_arg
Definition: pairingheap.h:74
pairingheap_comparator ph_compare
Definition: pairingheap.h:73
void * palloc(Size size)
Definition: mcxt.c:848
void * arg

◆ pairingheap_first()

pairingheap_node* pairingheap_first ( pairingheap heap)

Definition at line 130 of file pairingheap.c.

References Assert, pairingheap_is_empty, and pairingheap::ph_root.

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

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

◆ pairingheap_free()

void pairingheap_free ( pairingheap heap)

Definition at line 63 of file pairingheap.c.

References pfree().

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

◆ pairingheap_remove()

void pairingheap_remove ( pairingheap heap,
pairingheap_node node 
)

Definition at line 170 of file pairingheap.c.

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(), and UnregisterSnapshotFromOwner().

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 }
struct pairingheap_node * first_child
Definition: pairingheap.h:32
pairingheap_node * ph_root
Definition: pairingheap.h:75
struct pairingheap_node * next_sibling
Definition: pairingheap.h:33
#define Assert(condition)
Definition: c.h:670
static pairingheap_node * merge_children(pairingheap *heap, pairingheap_node *children)
Definition: pairingheap.c:234
pairingheap_node * pairingheap_remove_first(pairingheap *heap)
Definition: pairingheap.c:145
struct pairingheap_node * prev_or_parent
Definition: pairingheap.h:34

◆ pairingheap_remove_first()

pairingheap_node* pairingheap_remove_first ( pairingheap heap)

Definition at line 145 of file pairingheap.c.

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(), and reorderqueue_pop().

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 }
struct pairingheap_node * first_child
Definition: pairingheap.h:32
#define pairingheap_is_empty(h)
Definition: pairingheap.h:96
pairingheap_node * ph_root
Definition: pairingheap.h:75
struct pairingheap_node * next_sibling
Definition: pairingheap.h:33
#define Assert(condition)
Definition: c.h:670
static pairingheap_node * merge_children(pairingheap *heap, pairingheap_node *children)
Definition: pairingheap.c:234
struct pairingheap_node * prev_or_parent
Definition: pairingheap.h:34