Age Owner Branch data TLA 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 *
703 msawada@postgresql.o 37 :CBC 4662 : binaryheap_allocate(int capacity, binaryheap_comparator compare, void *arg)
38 : : {
39 : : int sz;
40 : : binaryheap *heap;
41 : :
42 : 4662 : sz = offsetof(binaryheap, bh_nodes) + sizeof(bh_node_type) * capacity;
43 : 4662 : heap = (binaryheap *) palloc(sz);
44 : 4662 : heap->bh_space = capacity;
4854 rhaas@postgresql.org 45 : 4662 : heap->bh_compare = compare;
46 : 4662 : heap->bh_arg = arg;
47 : :
4580 tgl@sss.pgh.pa.us 48 : 4662 : heap->bh_size = 0;
49 : 4662 : heap->bh_has_heap_property = true;
50 : :
4854 rhaas@postgresql.org 51 : 4662 : return heap;
52 : : }
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
4580 tgl@sss.pgh.pa.us 61 : 230 : binaryheap_reset(binaryheap *heap)
62 : : {
63 : 230 : heap->bh_size = 0;
64 : 230 : heap->bh_has_heap_property = true;
65 : 230 : }
66 : :
67 : : /*
68 : : * binaryheap_free
69 : : *
70 : : * Releases memory used by the given binaryheap.
71 : : */
72 : : void
4854 rhaas@postgresql.org 73 : 4121 : binaryheap_free(binaryheap *heap)
74 : : {
75 : 4121 : pfree(heap);
76 : 4121 : }
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 : 23192974 : left_offset(int i)
89 : : {
90 : 23192974 : return 2 * i + 1;
91 : : }
92 : :
93 : : static inline int
94 : 23192974 : right_offset(int i)
95 : : {
96 : 23192974 : return 2 * i + 2;
97 : : }
98 : :
99 : : static inline int
100 : 5275919 : parent_offset(int i)
101 : : {
102 : 5275919 : 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
909 nathan@postgresql.or 114 : 38611 : binaryheap_add_unordered(binaryheap *heap, bh_node_type d)
115 : : {
4854 rhaas@postgresql.org 116 [ - + ]: 38611 : if (heap->bh_size >= heap->bh_space)
117 : : {
118 : : #ifdef FRONTEND
703 msawada@postgresql.o 119 :UBC 0 : pg_fatal("out of binary heap slots");
120 : : #else
121 [ # # ]: 0 : elog(ERROR, "out of binary heap slots");
122 : : #endif
123 : : }
4854 rhaas@postgresql.org 124 :CBC 38611 : heap->bh_has_heap_property = false;
703 msawada@postgresql.o 125 : 38611 : heap->bh_nodes[heap->bh_size] = d;
4854 rhaas@postgresql.org 126 : 38611 : heap->bh_size++;
127 : 38611 : }
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 : 4401 : binaryheap_build(binaryheap *heap)
137 : : {
138 : : int i;
139 : :
140 [ + + ]: 25036 : for (i = parent_offset(heap->bh_size - 1); i >= 0; i--)
141 : 20635 : sift_down(heap, i);
142 : 4401 : heap->bh_has_heap_property = true;
143 : 4401 : }
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
909 nathan@postgresql.or 152 : 2236300 : binaryheap_add(binaryheap *heap, bh_node_type d)
153 : : {
4854 rhaas@postgresql.org 154 [ - + ]: 2236300 : if (heap->bh_size >= heap->bh_space)
155 : : {
156 : : #ifdef FRONTEND
703 msawada@postgresql.o 157 :UBC 0 : pg_fatal("out of binary heap slots");
158 : : #else
159 [ # # ]: 0 : elog(ERROR, "out of binary heap slots");
160 : : #endif
161 : : }
703 msawada@postgresql.o 162 :CBC 2236300 : heap->bh_nodes[heap->bh_size] = d;
4854 rhaas@postgresql.org 163 : 2236300 : heap->bh_size++;
164 : 2236300 : sift_up(heap, heap->bh_size - 1);
165 : 2236300 : }
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 : 1096599 : binaryheap_first(binaryheap *heap)
176 : : {
177 [ + - - + ]: 1096599 : Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
178 : 1096599 : 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 : 2270272 : binaryheap_remove_first(binaryheap *heap)
191 : : {
192 : : bh_node_type result;
193 : :
194 [ + - + + ]: 2270272 : Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
195 : :
196 : : /* extract the root node, which will be the result */
1552 tgl@sss.pgh.pa.us 197 : 2270272 : result = heap->bh_nodes[0];
198 : :
199 : : /* easy if heap contains one element */
4854 rhaas@postgresql.org 200 [ + + ]: 2270272 : if (heap->bh_size == 1)
201 : : {
202 : 6479 : heap->bh_size--;
1552 tgl@sss.pgh.pa.us 203 : 6479 : 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 : : */
703 msawada@postgresql.o 210 : 2263793 : heap->bh_nodes[0] = heap->bh_nodes[--heap->bh_size];
4854 rhaas@postgresql.org 211 : 2263793 : sift_down(heap, 0);
212 : :
1552 tgl@sss.pgh.pa.us 213 : 2263793 : return result;
214 : : }
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
909 nathan@postgresql.or 223 : 618 : binaryheap_remove_node(binaryheap *heap, int n)
224 : : {
225 : : int cmp;
226 : :
227 [ + - + + ]: 618 : Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
228 [ + - + + ]: 618 : Assert(n >= 0 && n < heap->bh_size);
229 : :
230 : : /* compare last node to the one that is being removed */
231 : 618 : cmp = heap->bh_compare(heap->bh_nodes[--heap->bh_size],
232 : : heap->bh_nodes[n],
233 : : heap->bh_arg);
234 : :
235 : : /* remove the last node, placing it in the vacated entry */
703 msawada@postgresql.o 236 : 618 : heap->bh_nodes[n] = heap->bh_nodes[heap->bh_size];
237 : :
238 : : /* sift as needed to preserve the heap property */
909 nathan@postgresql.or 239 [ + + ]: 618 : if (cmp > 0)
909 nathan@postgresql.or 240 :GBC 118 : sift_up(heap, n);
909 nathan@postgresql.or 241 [ + + ]:CBC 500 : else if (cmp < 0)
242 : 482 : sift_down(heap, n);
243 : 618 : }
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 : 882198 : binaryheap_replace_first(binaryheap *heap, bh_node_type d)
254 : : {
4854 rhaas@postgresql.org 255 [ + - - + ]: 882198 : Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
256 : :
703 msawada@postgresql.o 257 : 882198 : heap->bh_nodes[0] = d;
258 : :
4854 rhaas@postgresql.org 259 [ + + ]: 882198 : if (heap->bh_size > 1)
260 : 455844 : sift_down(heap, 0);
261 : 882198 : }
262 : :
263 : : /*
264 : : * Sift a node up to the highest position it can hold according to the
265 : : * comparator.
266 : : */
267 : : static void
268 : 2236418 : sift_up(binaryheap *heap, int node_off)
269 : : {
909 nathan@postgresql.or 270 : 2236418 : 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 : : */
4854 rhaas@postgresql.org 277 [ + + ]: 5456047 : while (node_off != 0)
278 : : {
279 : : int cmp;
280 : : int parent_off;
281 : : 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 : 5271518 : parent_off = parent_offset(node_off);
1552 tgl@sss.pgh.pa.us 288 : 5271518 : parent_val = heap->bh_nodes[parent_off];
289 : 5271518 : cmp = heap->bh_compare(node_val,
290 : : parent_val,
291 : : heap->bh_arg);
4854 rhaas@postgresql.org 292 [ + + ]: 5271518 : if (cmp <= 0)
293 : 2051889 : break;
294 : :
295 : : /*
296 : : * Otherwise, swap the parent value with the hole, and go on to check
297 : : * the node's new parent.
298 : : */
703 msawada@postgresql.o 299 : 3219629 : heap->bh_nodes[node_off] = parent_val;
4854 rhaas@postgresql.org 300 : 3219629 : node_off = parent_off;
301 : : }
302 : : /* Re-fill the hole */
703 msawada@postgresql.o 303 : 2236418 : heap->bh_nodes[node_off] = node_val;
4854 rhaas@postgresql.org 304 : 2236418 : }
305 : :
306 : : /*
307 : : * Sift a node down from its current position to satisfy the heap
308 : : * property.
309 : : */
310 : : static void
311 : 2740754 : sift_down(binaryheap *heap, int node_off)
312 : : {
909 nathan@postgresql.or 313 : 2740754 : 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 : : while (true)
4854 rhaas@postgresql.org 321 : 20452220 : {
322 : 23192974 : int left_off = left_offset(node_off);
323 : 23192974 : int right_off = right_offset(node_off);
501 nathan@postgresql.or 324 : 23192974 : int swap_off = left_off;
325 : :
326 : : /* Is the right child larger than the left child? */
4854 rhaas@postgresql.org 327 [ + + + + ]: 44268071 : if (right_off < heap->bh_size &&
501 nathan@postgresql.or 328 : 21075097 : heap->bh_compare(heap->bh_nodes[left_off],
329 : : heap->bh_nodes[right_off],
330 : : heap->bh_arg) < 0)
331 : 10444567 : 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 [ + + + + ]: 44732724 : if (left_off >= heap->bh_size ||
338 : 21539750 : heap->bh_compare(node_val,
339 : : heap->bh_nodes[swap_off],
340 : : heap->bh_arg) >= 0)
341 : : 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 : : */
703 msawada@postgresql.o 347 : 20452220 : heap->bh_nodes[node_off] = heap->bh_nodes[swap_off];
4854 rhaas@postgresql.org 348 : 20452220 : node_off = swap_off;
349 : : }
350 : : /* Re-fill the hole */
703 msawada@postgresql.o 351 : 2740754 : heap->bh_nodes[node_off] = node_val;
4854 rhaas@postgresql.org 352 : 2740754 : }
|
