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