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