PostgreSQL Source Code  git master
pairingheap.c File Reference
#include "postgres.h"
#include "lib/pairingheap.h"
Include dependency graph for pairingheap.c:

Go to the source code of this file.

Functions

static pairingheap_nodemerge (pairingheap *heap, pairingheap_node *a, pairingheap_node *b)
 
static pairingheap_nodemerge_children (pairingheap *heap, pairingheap_node *children)
 
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)
 

Function Documentation

◆ merge()

static pairingheap_node * merge ( pairingheap heap,
pairingheap_node a,
pairingheap_node b 
)
static

Definition at line 79 of file pairingheap.c.

80 {
81  if (a == NULL)
82  return b;
83  if (b == NULL)
84  return a;
85 
86  /* swap 'a' and 'b' so that 'a' is the one with larger value */
87  if (heap->ph_compare(a, b, heap->ph_arg) < 0)
88  {
89  pairingheap_node *tmp;
90 
91  tmp = a;
92  a = b;
93  b = tmp;
94  }
95 
96  /* and put 'b' as a child of 'a' */
97  if (a->first_child)
98  a->first_child->prev_or_parent = b;
99  b->prev_or_parent = a;
100  b->next_sibling = a->first_child;
101  a->first_child = b;
102 
103  return a;
104 }
int b
Definition: isn.c:69
int a
Definition: isn.c:68
pairingheap_comparator ph_compare
Definition: pairingheap.h:73
void * ph_arg
Definition: pairingheap.h:74

References a, b, pairingheap::ph_arg, and pairingheap::ph_compare.

Referenced by _bt_load(), merge_children(), and pairingheap_add().

◆ merge_children()

static pairingheap_node * merge_children ( pairingheap heap,
pairingheap_node children 
)
static

Definition at line 234 of file pairingheap.c.

235 {
236  pairingheap_node *curr,
237  *next;
238  pairingheap_node *pairs;
239  pairingheap_node *newroot;
240 
241  if (children == NULL || children->next_sibling == NULL)
242  return children;
243 
244  /* Walk the subheaps from left to right, merging in pairs */
245  next = children;
246  pairs = NULL;
247  for (;;)
248  {
249  curr = next;
250 
251  if (curr == NULL)
252  break;
253 
254  if (curr->next_sibling == NULL)
255  {
256  /* last odd node at the end of list */
257  curr->next_sibling = pairs;
258  pairs = curr;
259  break;
260  }
261 
262  next = curr->next_sibling->next_sibling;
263 
264  /* merge this and the next subheap, and add to 'pairs' list. */
265 
266  curr = merge(heap, curr, curr->next_sibling);
267  curr->next_sibling = pairs;
268  pairs = curr;
269  }
270 
271  /*
272  * Merge all the pairs together to form a single heap.
273  */
274  newroot = pairs;
275  next = pairs->next_sibling;
276  while (next)
277  {
278  curr = next;
279  next = curr->next_sibling;
280 
281  newroot = merge(heap, newroot, curr);
282  }
283 
284  return newroot;
285 }
static int32 next
Definition: blutils.c:219
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

References merge(), next, and pairingheap_node::next_sibling.

Referenced by pairingheap_remove(), and pairingheap_remove_first().

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

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:812
#define pairingheap_is_empty(h)
Definition: pairingheap.h:96

References Assert, pairingheap_is_empty, and pairingheap::ph_root.

Referenced by GetOldestSnapshot(), 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().