Age Owner Branch data TLA Line data Source code
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-2024, 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 : :
29 : : static pairingheap_node *merge(pairingheap *heap, pairingheap_node *a,
30 : : pairingheap_node *b);
31 : : static pairingheap_node *merge_children(pairingheap *heap,
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 : : */
41 : : pairingheap *
3401 heikki.linnakangas@i 42 :CBC 3792 : pairingheap_allocate(pairingheap_comparator compare, void *arg)
43 : : {
44 : : pairingheap *heap;
45 : :
46 : 3792 : heap = (pairingheap *) palloc(sizeof(pairingheap));
47 : 3792 : heap->ph_compare = compare;
48 : 3792 : heap->ph_arg = arg;
49 : :
50 : 3792 : heap->ph_root = NULL;
51 : :
3 akorotkov@postgresql 52 : 3792 : 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
3401 heikki.linnakangas@i 63 :UBC 0 : pairingheap_free(pairingheap *heap)
64 : : {
65 : 0 : pfree(heap);
66 : 0 : }
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 *
3401 heikki.linnakangas@i 79 :CBC 11209729 : merge(pairingheap *heap, pairingheap_node *a, pairingheap_node *b)
80 : : {
81 [ + + ]: 11209729 : if (a == NULL)
82 : 2552336 : return b;
83 [ - + ]: 8657393 : if (b == NULL)
3401 heikki.linnakangas@i 84 :UBC 0 : return a;
85 : :
86 : : /* swap 'a' and 'b' so that 'a' is the one with larger value */
3401 heikki.linnakangas@i 87 [ + + ]:CBC 8657393 : if (heap->ph_compare(a, b, heap->ph_arg) < 0)
88 : : {
89 : : pairingheap_node *tmp;
90 : :
91 : 1041950 : tmp = a;
92 : 1041950 : a = b;
93 : 1041950 : b = tmp;
94 : : }
95 : :
96 : : /* and put 'b' as a child of 'a' */
97 [ + + ]: 8657393 : if (a->first_child)
98 : 3465151 : a->first_child->prev_or_parent = b;
99 : 8657393 : b->prev_or_parent = a;
100 : 8657393 : b->next_sibling = a->first_child;
101 : 8657393 : a->first_child = b;
102 : :
103 : 8657393 : return a;
104 : : }
105 : :
106 : : /*
107 : : * pairingheap_add
108 : : *
109 : : * Adds the given node to the heap in O(1) time.
110 : : */
111 : : void
112 : 9103465 : pairingheap_add(pairingheap *heap, pairingheap_node *node)
113 : : {
114 : 9103465 : node->first_child = NULL;
115 : :
116 : : /* Link the new node as a new tree */
117 : 9103465 : heap->ph_root = merge(heap, heap->ph_root, node);
3344 118 : 9103465 : heap->ph_root->prev_or_parent = NULL;
119 : 9103465 : heap->ph_root->next_sibling = NULL;
3401 120 : 9103465 : }
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 : : */
129 : : pairingheap_node *
130 : 1596691 : pairingheap_first(pairingheap *heap)
131 : : {
132 [ - + ]: 1596691 : Assert(!pairingheap_is_empty(heap));
133 : :
134 : 1596691 : 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 : : */
144 : : pairingheap_node *
145 : 3109447 : pairingheap_remove_first(pairingheap *heap)
146 : : {
147 : : pairingheap_node *result;
148 : : pairingheap_node *children;
149 : :
150 [ - + ]: 3109447 : Assert(!pairingheap_is_empty(heap));
151 : :
152 : : /* Remove the root, and form a new heap of its children. */
153 : 3109447 : result = heap->ph_root;
154 : 3109447 : children = result->first_child;
155 : :
156 : 3109447 : heap->ph_root = merge_children(heap, children);
3344 157 [ + + ]: 3109447 : if (heap->ph_root)
158 : : {
159 : 557251 : heap->ph_root->prev_or_parent = NULL;
160 : 557251 : heap->ph_root->next_sibling = NULL;
161 : : }
162 : :
3401 163 : 3109447 : return result;
164 : : }
165 : :
166 : : /*
167 : : * Remove 'node' from the heap. O(log n) amortized.
168 : : */
169 : : void
170 : 8819290 : pairingheap_remove(pairingheap *heap, pairingheap_node *node)
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 [ + + ]: 8819290 : if (node == heap->ph_root)
182 : : {
183 : 2841086 : (void) pairingheap_remove_first(heap);
184 : 2841086 : return;
185 : : }
186 : :
187 : : /*
188 : : * Before we modify anything, remember the removed node's first_child and
189 : : * next_sibling pointers.
190 : : */
191 : 5978204 : children = node->first_child;
192 : 5978204 : 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 [ + + ]: 5978204 : if (node->prev_or_parent->first_child == node)
199 : 5967019 : prev_ptr = &node->prev_or_parent->first_child;
200 : : else
201 : 11185 : prev_ptr = &node->prev_or_parent->next_sibling;
202 [ - + ]: 5978204 : 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 [ + + ]: 5978204 : if (children)
210 : : {
211 : 330 : replacement = merge_children(heap, children);
212 : :
213 : 330 : replacement->prev_or_parent = node->prev_or_parent;
214 : 330 : replacement->next_sibling = node->next_sibling;
215 : 330 : *prev_ptr = replacement;
216 [ + + ]: 330 : if (next_sibling)
217 : 293 : next_sibling->prev_or_parent = replacement;
218 : : }
219 : : else
220 : : {
221 : 5977874 : *prev_ptr = next_sibling;
222 [ + + ]: 5977874 : if (next_sibling)
223 : 1343287 : 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 *
234 : 3109777 : merge_children(pairingheap *heap, pairingheap_node *children)
235 : : {
236 : : pairingheap_node *curr,
237 : : *next;
238 : : pairingheap_node *pairs;
239 : : pairingheap_node *newroot;
240 : :
241 [ + + + + ]: 3109777 : if (children == NULL || children->next_sibling == NULL)
242 : 2856528 : return children;
243 : :
244 : : /* Walk the subheaps from left to right, merging in pairs */
245 : 253249 : next = children;
246 : 253249 : pairs = NULL;
247 : : for (;;)
248 : : {
249 : 1372214 : curr = next;
250 : :
251 [ + + ]: 1372214 : if (curr == NULL)
252 : 131666 : break;
253 : :
254 [ + + ]: 1240548 : if (curr->next_sibling == NULL)
255 : : {
256 : : /* last odd node at the end of list */
257 : 121583 : curr->next_sibling = pairs;
258 : 121583 : pairs = curr;
259 : 121583 : break;
260 : : }
261 : :
262 : 1118965 : next = curr->next_sibling->next_sibling;
263 : :
264 : : /* merge this and the next subheap, and add to 'pairs' list. */
265 : :
266 : 1118965 : curr = merge(heap, curr, curr->next_sibling);
267 : 1118965 : curr->next_sibling = pairs;
268 : 1118965 : pairs = curr;
269 : : }
270 : :
271 : : /*
272 : : * Merge all the pairs together to form a single heap.
273 : : */
274 : 253249 : newroot = pairs;
275 : 253249 : next = pairs->next_sibling;
276 [ + + ]: 1240548 : while (next)
277 : : {
278 : 987299 : curr = next;
279 : 987299 : next = curr->next_sibling;
280 : :
281 : 987299 : newroot = merge(heap, newroot, curr);
282 : : }
283 : :
284 : 253249 : 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 : : {
322 : : StringInfoData buf;
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
|
