Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * binaryheap.c
4 : * A simple binary heap implementation
5 : *
6 : * Portions Copyright (c) 2012-2024, PostgreSQL Global Development Group
7 : *
8 : * IDENTIFICATION
9 : * src/common/binaryheap.c
10 : *
11 : *-------------------------------------------------------------------------
12 : */
13 :
14 : #ifdef FRONTEND
15 : #include "postgres_fe.h"
16 : #else
17 : #include "postgres.h"
18 : #endif
19 :
20 : #include <math.h>
21 :
22 : #ifdef FRONTEND
23 : #include "common/logging.h"
24 : #endif
25 : #include "lib/binaryheap.h"
26 :
27 : static void sift_down(binaryheap *heap, int node_off);
28 : static void sift_up(binaryheap *heap, int node_off);
29 :
30 : /*
31 : * binaryheap_allocate
32 : *
33 : * Returns a pointer to a newly-allocated heap that has the capacity to
34 : * store the given number of nodes, with the heap property defined by
35 : * the given comparator function, which will be invoked with the additional
36 : * argument specified by 'arg'.
37 : */
38 : binaryheap *
39 6638 : binaryheap_allocate(int capacity, binaryheap_comparator compare, void *arg)
40 : {
41 : int sz;
42 : binaryheap *heap;
43 :
44 6638 : sz = offsetof(binaryheap, bh_nodes) + sizeof(bh_node_type) * capacity;
45 6638 : heap = (binaryheap *) palloc(sz);
46 6638 : heap->bh_space = capacity;
47 6638 : heap->bh_compare = compare;
48 6638 : heap->bh_arg = arg;
49 :
50 6638 : heap->bh_size = 0;
51 6638 : heap->bh_has_heap_property = true;
52 :
53 6638 : return heap;
54 : }
55 :
56 : /*
57 : * binaryheap_reset
58 : *
59 : * Resets the heap to an empty state, losing its data content but not the
60 : * parameters passed at allocation.
61 : */
62 : void
63 336 : binaryheap_reset(binaryheap *heap)
64 : {
65 336 : heap->bh_size = 0;
66 336 : heap->bh_has_heap_property = true;
67 336 : }
68 :
69 : /*
70 : * binaryheap_free
71 : *
72 : * Releases memory used by the given binaryheap.
73 : */
74 : void
75 5796 : binaryheap_free(binaryheap *heap)
76 : {
77 5796 : pfree(heap);
78 5796 : }
79 :
80 : /*
81 : * These utility functions return the offset of the left child, right
82 : * child, and parent of the node at the given index, respectively.
83 : *
84 : * The heap is represented as an array of nodes, with the root node
85 : * stored at index 0. The left child of node i is at index 2*i+1, and
86 : * the right child at 2*i+2. The parent of node i is at index (i-1)/2.
87 : */
88 :
89 : static inline int
90 21952618 : left_offset(int i)
91 : {
92 21952618 : return 2 * i + 1;
93 : }
94 :
95 : static inline int
96 21952618 : right_offset(int i)
97 : {
98 21952618 : return 2 * i + 2;
99 : }
100 :
101 : static inline int
102 5705992 : parent_offset(int i)
103 : {
104 5705992 : return (i - 1) / 2;
105 : }
106 :
107 : /*
108 : * binaryheap_add_unordered
109 : *
110 : * Adds the given datum to the end of the heap's list of nodes in O(1) without
111 : * preserving the heap property. This is a convenience to add elements quickly
112 : * to a new heap. To obtain a valid heap, one must call binaryheap_build()
113 : * afterwards.
114 : */
115 : void
116 54344 : binaryheap_add_unordered(binaryheap *heap, bh_node_type d)
117 : {
118 54344 : if (heap->bh_size >= heap->bh_space)
119 : {
120 : #ifdef FRONTEND
121 0 : pg_fatal("out of binary heap slots");
122 : #else
123 0 : elog(ERROR, "out of binary heap slots");
124 : #endif
125 : }
126 54344 : heap->bh_has_heap_property = false;
127 54344 : heap->bh_nodes[heap->bh_size] = d;
128 54344 : heap->bh_size++;
129 54344 : }
130 :
131 : /*
132 : * binaryheap_build
133 : *
134 : * Assembles a valid heap in O(n) from the nodes added by
135 : * binaryheap_add_unordered(). Not needed otherwise.
136 : */
137 : void
138 6246 : binaryheap_build(binaryheap *heap)
139 : {
140 : int i;
141 :
142 35424 : for (i = parent_offset(heap->bh_size - 1); i >= 0; i--)
143 29178 : sift_down(heap, i);
144 6246 : heap->bh_has_heap_property = true;
145 6246 : }
146 :
147 : /*
148 : * binaryheap_add
149 : *
150 : * Adds the given datum to the heap in O(log n) time, while preserving
151 : * the heap property.
152 : */
153 : void
154 2121370 : binaryheap_add(binaryheap *heap, bh_node_type d)
155 : {
156 2121370 : if (heap->bh_size >= heap->bh_space)
157 : {
158 : #ifdef FRONTEND
159 0 : pg_fatal("out of binary heap slots");
160 : #else
161 0 : elog(ERROR, "out of binary heap slots");
162 : #endif
163 : }
164 2121370 : heap->bh_nodes[heap->bh_size] = d;
165 2121370 : heap->bh_size++;
166 2121370 : sift_up(heap, heap->bh_size - 1);
167 2121370 : }
168 :
169 : /*
170 : * binaryheap_first
171 : *
172 : * Returns a pointer to the first (root, topmost) node in the heap
173 : * without modifying the heap. The caller must ensure that this
174 : * routine is not used on an empty heap. Always O(1).
175 : */
176 : bh_node_type
177 1962606 : binaryheap_first(binaryheap *heap)
178 : {
179 : Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
180 1962606 : return heap->bh_nodes[0];
181 : }
182 :
183 : /*
184 : * binaryheap_remove_first
185 : *
186 : * Removes the first (root, topmost) node in the heap and returns a
187 : * pointer to it after rebalancing the heap. The caller must ensure
188 : * that this routine is not used on an empty heap. O(log n) worst
189 : * case.
190 : */
191 : bh_node_type
192 2175412 : binaryheap_remove_first(binaryheap *heap)
193 : {
194 : bh_node_type result;
195 :
196 : Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
197 :
198 : /* extract the root node, which will be the result */
199 2175412 : result = heap->bh_nodes[0];
200 :
201 : /* easy if heap contains one element */
202 2175412 : if (heap->bh_size == 1)
203 : {
204 8402 : heap->bh_size--;
205 8402 : return result;
206 : }
207 :
208 : /*
209 : * Remove the last node, placing it in the vacated root entry, and sift
210 : * the new root node down to its correct position.
211 : */
212 2167010 : heap->bh_nodes[0] = heap->bh_nodes[--heap->bh_size];
213 2167010 : sift_down(heap, 0);
214 :
215 2167010 : return result;
216 : }
217 :
218 : /*
219 : * binaryheap_remove_node
220 : *
221 : * Removes the nth (zero based) node from the heap. The caller must ensure
222 : * that there are at least (n + 1) nodes in the heap. O(log n) worst case.
223 : */
224 : void
225 92 : binaryheap_remove_node(binaryheap *heap, int n)
226 : {
227 : int cmp;
228 :
229 : Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
230 : Assert(n >= 0 && n < heap->bh_size);
231 :
232 : /* compare last node to the one that is being removed */
233 92 : cmp = heap->bh_compare(heap->bh_nodes[--heap->bh_size],
234 : heap->bh_nodes[n],
235 : heap->bh_arg);
236 :
237 : /* remove the last node, placing it in the vacated entry */
238 92 : heap->bh_nodes[n] = heap->bh_nodes[heap->bh_size];
239 :
240 : /* sift as needed to preserve the heap property */
241 92 : if (cmp > 0)
242 0 : sift_up(heap, n);
243 92 : else if (cmp < 0)
244 62 : sift_down(heap, n);
245 92 : }
246 :
247 : /*
248 : * binaryheap_replace_first
249 : *
250 : * Replace the topmost element of a non-empty heap, preserving the heap
251 : * property. O(1) in the best case, or O(log n) if it must fall back to
252 : * sifting the new node down.
253 : */
254 : void
255 1538546 : binaryheap_replace_first(binaryheap *heap, bh_node_type d)
256 : {
257 : Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
258 :
259 1538546 : heap->bh_nodes[0] = d;
260 :
261 1538546 : if (heap->bh_size > 1)
262 585962 : sift_down(heap, 0);
263 1538546 : }
264 :
265 : /*
266 : * Sift a node up to the highest position it can hold according to the
267 : * comparator.
268 : */
269 : static void
270 2121370 : sift_up(binaryheap *heap, int node_off)
271 : {
272 2121370 : bh_node_type node_val = heap->bh_nodes[node_off];
273 :
274 : /*
275 : * Within the loop, the node_off'th array entry is a "hole" that
276 : * notionally holds node_val, but we don't actually store node_val there
277 : * till the end, saving some unnecessary data copying steps.
278 : */
279 5910128 : while (node_off != 0)
280 : {
281 : int cmp;
282 : int parent_off;
283 : bh_node_type parent_val;
284 :
285 : /*
286 : * If this node is smaller than its parent, the heap condition is
287 : * satisfied, and we're done.
288 : */
289 5699746 : parent_off = parent_offset(node_off);
290 5699746 : parent_val = heap->bh_nodes[parent_off];
291 5699746 : cmp = heap->bh_compare(node_val,
292 : parent_val,
293 : heap->bh_arg);
294 5699746 : if (cmp <= 0)
295 1910988 : break;
296 :
297 : /*
298 : * Otherwise, swap the parent value with the hole, and go on to check
299 : * the node's new parent.
300 : */
301 3788758 : heap->bh_nodes[node_off] = parent_val;
302 3788758 : node_off = parent_off;
303 : }
304 : /* Re-fill the hole */
305 2121370 : heap->bh_nodes[node_off] = node_val;
306 2121370 : }
307 :
308 : /*
309 : * Sift a node down from its current position to satisfy the heap
310 : * property.
311 : */
312 : static void
313 2782212 : sift_down(binaryheap *heap, int node_off)
314 : {
315 2782212 : bh_node_type node_val = heap->bh_nodes[node_off];
316 :
317 : /*
318 : * Within the loop, the node_off'th array entry is a "hole" that
319 : * notionally holds node_val, but we don't actually store node_val there
320 : * till the end, saving some unnecessary data copying steps.
321 : */
322 : while (true)
323 19170406 : {
324 21952618 : int left_off = left_offset(node_off);
325 21952618 : int right_off = right_offset(node_off);
326 21952618 : int swap_off = 0;
327 :
328 : /* Is the left child larger than the parent? */
329 42220346 : if (left_off < heap->bh_size &&
330 20267728 : heap->bh_compare(node_val,
331 : heap->bh_nodes[left_off],
332 : heap->bh_arg) < 0)
333 18656038 : swap_off = left_off;
334 :
335 : /* Is the right child larger than the parent? */
336 41544270 : if (right_off < heap->bh_size &&
337 19591652 : heap->bh_compare(node_val,
338 : heap->bh_nodes[right_off],
339 : heap->bh_arg) < 0)
340 : {
341 : /* swap with the larger child */
342 36872812 : if (!swap_off ||
343 18179222 : heap->bh_compare(heap->bh_nodes[left_off],
344 : heap->bh_nodes[right_off],
345 : heap->bh_arg) < 0)
346 9286734 : swap_off = right_off;
347 : }
348 :
349 : /*
350 : * If we didn't find anything to swap, the heap condition is
351 : * satisfied, and we're done.
352 : */
353 21952618 : if (!swap_off)
354 2782212 : break;
355 :
356 : /*
357 : * Otherwise, swap the hole with the child that violates the heap
358 : * property; then go on to check its children.
359 : */
360 19170406 : heap->bh_nodes[node_off] = heap->bh_nodes[swap_off];
361 19170406 : node_off = swap_off;
362 : }
363 : /* Re-fill the hole */
364 2782212 : heap->bh_nodes[node_off] = node_val;
365 2782212 : }
|
