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-2025, 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 *
4012 heikki.linnakangas@i 42 :CBC 4558 : pairingheap_allocate(pairingheap_comparator compare, void *arg)
43 : : {
44 : : pairingheap *heap;
45 : :
6 michael@paquier.xyz 46 :GNC 4558 : heap = palloc_object(pairingheap);
41 akorotkov@postgresql 47 : 4558 : pairingheap_initialize(heap, compare, arg);
48 : :
49 : 4558 : return heap;
50 : : }
51 : :
52 : : /*
53 : : * pairingheap_initialize
54 : : *
55 : : * Same as pairingheap_allocate(), but initializes the pairing heap in-place
56 : : * rather than allocating a new chunk of memory. Useful to store the pairing
57 : : * heap in a shared memory.
58 : : */
59 : : void
60 : 6696 : pairingheap_initialize(pairingheap *heap, pairingheap_comparator compare,
61 : : void *arg)
62 : : {
4012 heikki.linnakangas@i 63 :CBC 6696 : heap->ph_compare = compare;
64 : 6696 : heap->ph_arg = arg;
65 : :
66 : 6696 : heap->ph_root = NULL;
4012 heikki.linnakangas@i 67 :GIC 6696 : }
68 : :
69 : : /*
70 : : * pairingheap_free
71 : : *
72 : : * Releases memory used by the given pairingheap.
73 : : *
74 : : * Note: The nodes in the heap are not freed!
75 : : */
76 : : void
4012 heikki.linnakangas@i 77 :UBC 0 : pairingheap_free(pairingheap *heap)
78 : : {
79 : 0 : pfree(heap);
80 : 0 : }
81 : :
82 : : /*
83 : : * A helper function to merge two subheaps into one.
84 : : *
85 : : * The subheap with smaller value is put as a child of the other one (assuming
86 : : * a max-heap).
87 : : *
88 : : * The next_sibling and prev_or_parent pointers of the input nodes are
89 : : * ignored. On return, the returned node's next_sibling and prev_or_parent
90 : : * pointers are garbage.
91 : : */
92 : : static pairingheap_node *
4012 heikki.linnakangas@i 93 :CBC 12058841 : merge(pairingheap *heap, pairingheap_node *a, pairingheap_node *b)
94 : : {
95 [ + + ]: 12058841 : if (a == NULL)
96 : 2431337 : return b;
97 [ - + ]: 9627504 : if (b == NULL)
4012 heikki.linnakangas@i 98 :UBC 0 : return a;
99 : :
100 : : /* swap 'a' and 'b' so that 'a' is the one with larger value */
4012 heikki.linnakangas@i 101 [ + + ]:CBC 9627504 : if (heap->ph_compare(a, b, heap->ph_arg) < 0)
102 : : {
103 : : pairingheap_node *tmp;
104 : :
105 : 1053247 : tmp = a;
106 : 1053247 : a = b;
107 : 1053247 : b = tmp;
108 : : }
109 : :
110 : : /* and put 'b' as a child of 'a' */
111 [ + + ]: 9627504 : if (a->first_child)
112 : 3933010 : a->first_child->prev_or_parent = b;
113 : 9627504 : b->prev_or_parent = a;
114 : 9627504 : b->next_sibling = a->first_child;
115 : 9627504 : a->first_child = b;
116 : :
117 : 9627504 : return a;
118 : : }
119 : :
120 : : /*
121 : : * pairingheap_add
122 : : *
123 : : * Adds the given node to the heap in O(1) time.
124 : : */
125 : : void
126 : 9945161 : pairingheap_add(pairingheap *heap, pairingheap_node *node)
127 : : {
128 : 9945161 : node->first_child = NULL;
129 : :
130 : : /* Link the new node as a new tree */
131 : 9945161 : heap->ph_root = merge(heap, heap->ph_root, node);
3955 132 : 9945161 : heap->ph_root->prev_or_parent = NULL;
133 : 9945161 : heap->ph_root->next_sibling = NULL;
4012 134 : 9945161 : }
135 : :
136 : : /*
137 : : * pairingheap_first
138 : : *
139 : : * Returns a pointer to the first (root, topmost) node in the heap without
140 : : * modifying the heap. The caller must ensure that this routine is not used on
141 : : * an empty heap. Always O(1).
142 : : */
143 : : pairingheap_node *
144 : 1608789 : pairingheap_first(pairingheap *heap)
145 : : {
146 [ - + ]: 1608789 : Assert(!pairingheap_is_empty(heap));
147 : :
148 : 1608789 : return heap->ph_root;
149 : : }
150 : :
151 : : /*
152 : : * pairingheap_remove_first
153 : : *
154 : : * Removes the first (root, topmost) node in the heap and returns a pointer to
155 : : * it after rebalancing the heap. The caller must ensure that this routine is
156 : : * not used on an empty heap. O(log n) amortized.
157 : : */
158 : : pairingheap_node *
159 : 3103533 : pairingheap_remove_first(pairingheap *heap)
160 : : {
161 : : pairingheap_node *result;
162 : : pairingheap_node *children;
163 : :
164 [ - + ]: 3103533 : Assert(!pairingheap_is_empty(heap));
165 : :
166 : : /* Remove the root, and form a new heap of its children. */
167 : 3103533 : result = heap->ph_root;
168 : 3103533 : children = result->first_child;
169 : :
170 : 3103533 : heap->ph_root = merge_children(heap, children);
3955 171 [ + + ]: 3103533 : if (heap->ph_root)
172 : : {
173 : 672334 : heap->ph_root->prev_or_parent = NULL;
174 : 672334 : heap->ph_root->next_sibling = NULL;
175 : : }
176 : :
4012 177 : 3103533 : return result;
178 : : }
179 : :
180 : : /*
181 : : * Remove 'node' from the heap. O(log n) amortized.
182 : : */
183 : : void
184 : 9659946 : pairingheap_remove(pairingheap *heap, pairingheap_node *node)
185 : : {
186 : : pairingheap_node *children;
187 : : pairingheap_node *replacement;
188 : : pairingheap_node *next_sibling;
189 : : pairingheap_node **prev_ptr;
190 : :
191 : : /*
192 : : * If the removed node happens to be the root node, do it with
193 : : * pairingheap_remove_first().
194 : : */
195 [ + + ]: 9659946 : if (node == heap->ph_root)
196 : : {
197 : 2834789 : (void) pairingheap_remove_first(heap);
198 : 2834789 : return;
199 : : }
200 : :
201 : : /*
202 : : * Before we modify anything, remember the removed node's first_child and
203 : : * next_sibling pointers.
204 : : */
205 : 6825157 : children = node->first_child;
206 : 6825157 : next_sibling = node->next_sibling;
207 : :
208 : : /*
209 : : * Also find the pointer to the removed node in its previous sibling, or
210 : : * if this is the first child of its parent, in its parent.
211 : : */
212 [ + + ]: 6825157 : if (node->prev_or_parent->first_child == node)
213 : 6814011 : prev_ptr = &node->prev_or_parent->first_child;
214 : : else
215 : 11146 : prev_ptr = &node->prev_or_parent->next_sibling;
216 [ - + ]: 6825157 : Assert(*prev_ptr == node);
217 : :
218 : : /*
219 : : * If this node has children, make a new subheap of the children and link
220 : : * the subheap in place of the removed node. Otherwise just unlink this
221 : : * node.
222 : : */
223 [ + + ]: 6825157 : if (children)
224 : : {
225 : 1090 : replacement = merge_children(heap, children);
226 : :
227 : 1090 : replacement->prev_or_parent = node->prev_or_parent;
228 : 1090 : replacement->next_sibling = node->next_sibling;
229 : 1090 : *prev_ptr = replacement;
230 [ + + ]: 1090 : if (next_sibling)
231 : 1033 : next_sibling->prev_or_parent = replacement;
232 : : }
233 : : else
234 : : {
235 : 6824067 : *prev_ptr = next_sibling;
236 [ + + ]: 6824067 : if (next_sibling)
237 : 1802299 : next_sibling->prev_or_parent = node->prev_or_parent;
238 : : }
239 : : }
240 : :
241 : : /*
242 : : * Merge a list of subheaps into a single heap.
243 : : *
244 : : * This implements the basic two-pass merging strategy, first forming pairs
245 : : * from left to right, and then merging the pairs.
246 : : */
247 : : static pairingheap_node *
248 : 3104623 : merge_children(pairingheap *heap, pairingheap_node *children)
249 : : {
250 : : pairingheap_node *curr,
251 : : *next;
252 : : pairingheap_node *pairs;
253 : : pairingheap_node *newroot;
254 : :
255 [ + + + + ]: 3104623 : if (children == NULL || children->next_sibling == NULL)
256 : 2850926 : return children;
257 : :
258 : : /* Walk the subheaps from left to right, merging in pairs */
259 : 253697 : next = children;
260 : 253697 : pairs = NULL;
261 : : for (;;)
262 : : {
263 : 1376594 : curr = next;
264 : :
265 [ + + ]: 1376594 : if (curr == NULL)
266 : 132114 : break;
267 : :
268 [ + + ]: 1244480 : if (curr->next_sibling == NULL)
269 : : {
270 : : /* last odd node at the end of list */
271 : 121583 : curr->next_sibling = pairs;
272 : 121583 : pairs = curr;
273 : 121583 : break;
274 : : }
275 : :
276 : 1122897 : next = curr->next_sibling->next_sibling;
277 : :
278 : : /* merge this and the next subheap, and add to 'pairs' list. */
279 : :
280 : 1122897 : curr = merge(heap, curr, curr->next_sibling);
281 : 1122897 : curr->next_sibling = pairs;
282 : 1122897 : pairs = curr;
283 : : }
284 : :
285 : : /*
286 : : * Merge all the pairs together to form a single heap.
287 : : */
288 : 253697 : newroot = pairs;
289 : 253697 : next = pairs->next_sibling;
290 [ + + ]: 1244480 : while (next)
291 : : {
292 : 990783 : curr = next;
293 : 990783 : next = curr->next_sibling;
294 : :
295 : 990783 : newroot = merge(heap, newroot, curr);
296 : : }
297 : :
298 : 253697 : return newroot;
299 : : }
300 : :
301 : : /*
302 : : * A debug function to dump the contents of the heap as a string.
303 : : *
304 : : * The 'dumpfunc' callback appends a string representation of a single node
305 : : * to the StringInfo. 'opaque' can be used to pass more information to the
306 : : * callback.
307 : : */
308 : : #ifdef PAIRINGHEAP_DEBUG
309 : : static void
310 : : pairingheap_dump_recurse(StringInfo buf,
311 : : pairingheap_node *node,
312 : : void (*dumpfunc) (pairingheap_node *node, StringInfo buf, void *opaque),
313 : : void *opaque,
314 : : int depth,
315 : : pairingheap_node *prev_or_parent)
316 : : {
317 : : while (node)
318 : : {
319 : : Assert(node->prev_or_parent == prev_or_parent);
320 : :
321 : : appendStringInfoSpaces(buf, depth * 4);
322 : : dumpfunc(node, buf, opaque);
323 : : appendStringInfoChar(buf, '\n');
324 : : if (node->first_child)
325 : : pairingheap_dump_recurse(buf, node->first_child, dumpfunc, opaque, depth + 1, node);
326 : : prev_or_parent = node;
327 : : node = node->next_sibling;
328 : : }
329 : : }
330 : :
331 : : char *
332 : : pairingheap_dump(pairingheap *heap,
333 : : void (*dumpfunc) (pairingheap_node *node, StringInfo buf, void *opaque),
334 : : void *opaque)
335 : : {
336 : : StringInfoData buf;
337 : :
338 : : if (!heap->ph_root)
339 : : return pstrdup("(empty)");
340 : :
341 : : initStringInfo(&buf);
342 : :
343 : : pairingheap_dump_recurse(&buf, heap->ph_root, dumpfunc, opaque, 0, NULL);
344 : :
345 : : return buf.data;
346 : : }
347 : : #endif
|
