PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
pairingheap.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * pairingheap.c
4  * A Pairing Heap implementation
5  *
6  * A pairing heap is a data structure that's useful for implementing
7  * priority queues. It is simple to implement, and provides amortized O(1)
8  * insert and find-min operations, and amortized O(log n) delete-min.
9  *
10  * The pairing heap was first described in this paper:
11  *
12  * Michael L. Fredman, Robert Sedgewick, Daniel D. Sleator, and Robert E.
13  * Tarjan. 1986.
14  * The pairing heap: a new form of self-adjusting heap.
15  * Algorithmica 1, 1 (January 1986), pages 111-129. DOI: 10.1007/BF01840439
16  *
17  * Portions Copyright (c) 2012-2017, PostgreSQL Global Development Group
18  *
19  * IDENTIFICATION
20  * src/backend/lib/pairingheap.c
21  *
22  *-------------------------------------------------------------------------
23  */
24 
25 #include "postgres.h"
26 
27 #include "lib/pairingheap.h"
28 
30  pairingheap_node *b);
32  pairingheap_node *children);
33 
34 /*
35  * pairingheap_allocate
36  *
37  * Returns a pointer to a newly-allocated heap, with the heap property defined
38  * by the given comparator function, which will be invoked with the additional
39  * argument specified by 'arg'.
40  */
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 }
54 
55 /*
56  * pairingheap_free
57  *
58  * Releases memory used by the given pairingheap.
59  *
60  * Note: The nodes in the heap are not freed!
61  */
62 void
64 {
65  pfree(heap);
66 }
67 
68 /*
69  * A helper function to merge two subheaps into one.
70  *
71  * The subheap with smaller value is put as a child of the other one (assuming
72  * a max-heap).
73  *
74  * The next_sibling and prev_or_parent pointers of the input nodes are
75  * ignored. On return, the returned node's next_sibling and prev_or_parent
76  * pointers are garbage.
77  */
78 static pairingheap_node *
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)
99  b->prev_or_parent = a;
100  b->next_sibling = a->first_child;
101  a->first_child = b;
102 
103  return a;
104 }
105 
106 /*
107  * pairingheap_add
108  *
109  * Adds the given node to the heap in O(1) time.
110  */
111 void
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 }
121 
122 /*
123  * pairingheap_first
124  *
125  * Returns a pointer to the first (root, topmost) node in the heap without
126  * modifying the heap. The caller must ensure that this routine is not used on
127  * an empty heap. Always O(1).
128  */
131 {
133 
134  return heap->ph_root;
135 }
136 
137 /*
138  * pairingheap_remove_first
139  *
140  * Removes the first (root, topmost) node in the heap and returns a pointer to
141  * it after rebalancing the heap. The caller must ensure that this routine is
142  * not used on an empty heap. O(log n) amortized.
143  */
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 }
165 
166 /*
167  * Remove 'node' from the heap. O(log n) amortized.
168  */
169 void
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 }
226 
227 /*
228  * Merge a list of subheaps into a single heap.
229  *
230  * This implements the basic two-pass merging strategy, first forming pairs
231  * from left to right, and then merging the pairs.
232  */
233 static pairingheap_node *
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 }
286 
287 /*
288  * A debug function to dump the contents of the heap as a string.
289  *
290  * The 'dumpfunc' callback appends a string representation of a single node
291  * to the StringInfo. 'opaque' can be used to pass more information to the
292  * callback.
293  */
294 #ifdef PAIRINGHEAP_DEBUG
295 static void
296 pairingheap_dump_recurse(StringInfo buf,
297  pairingheap_node *node,
298  void (*dumpfunc) (pairingheap_node *node, StringInfo buf, void *opaque),
299  void *opaque,
300  int depth,
301  pairingheap_node *prev_or_parent)
302 {
303  while (node)
304  {
305  Assert(node->prev_or_parent == prev_or_parent);
306 
307  appendStringInfoSpaces(buf, depth * 4);
308  dumpfunc(node, buf, opaque);
309  appendStringInfoChar(buf, '\n');
310  if (node->first_child)
311  pairingheap_dump_recurse(buf, node->first_child, dumpfunc, opaque, depth + 1, node);
312  prev_or_parent = node;
313  node = node->next_sibling;
314  }
315 }
316 
317 char *
318 pairingheap_dump(pairingheap *heap,
319  void (*dumpfunc) (pairingheap_node *node, StringInfo buf, void *opaque),
320  void *opaque)
321 {
323 
324  if (!heap->ph_root)
325  return pstrdup("(empty)");
326 
327  initStringInfo(&buf);
328 
329  pairingheap_dump_recurse(&buf, heap->ph_root, dumpfunc, opaque, 0, NULL);
330 
331  return buf.data;
332 }
333 #endif
pairingheap_node * pairingheap_first(pairingheap *heap)
Definition: pairingheap.c:130
static int32 next
Definition: blutils.c:210
struct pairingheap_node * first_child
Definition: pairingheap.h:32
char * pstrdup(const char *in)
Definition: mcxt.c:1076
#define pairingheap_is_empty(h)
Definition: pairingheap.h:96
pairingheap * pairingheap_allocate(pairingheap_comparator compare, void *arg)
Definition: pairingheap.c:42
pairingheap_node * ph_root
Definition: pairingheap.h:75
static pairingheap_node * merge(pairingheap *heap, pairingheap_node *a, pairingheap_node *b)
Definition: pairingheap.c:79
void pfree(void *pointer)
Definition: mcxt.c:949
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
void * ph_arg
Definition: pairingheap.h:74
static char * buf
Definition: pg_test_fsync.c:67
struct pairingheap_node * next_sibling
Definition: pairingheap.h:33
pairingheap_comparator ph_compare
Definition: pairingheap.h:73
int(* pairingheap_comparator)(const pairingheap_node *a, const pairingheap_node *b, void *arg)
Definition: pairingheap.h:60
void appendStringInfoChar(StringInfo str, char ch)
Definition: stringinfo.c:169
void initStringInfo(StringInfo str)
Definition: stringinfo.c:46
void appendStringInfoSpaces(StringInfo str, int count)
Definition: stringinfo.c:187
void pairingheap_free(pairingheap *heap)
Definition: pairingheap.c:63
#define Assert(condition)
Definition: c.h:681
static pairingheap_node * merge_children(pairingheap *heap, pairingheap_node *children)
Definition: pairingheap.c:234
void * palloc(Size size)
Definition: mcxt.c:848
pairingheap_node * pairingheap_remove_first(pairingheap *heap)
Definition: pairingheap.c:145
void * arg
void pairingheap_remove(pairingheap *heap, pairingheap_node *node)
Definition: pairingheap.c:170
void pairingheap_add(pairingheap *heap, pairingheap_node *node)
Definition: pairingheap.c:112
struct pairingheap_node * prev_or_parent
Definition: pairingheap.h:34