PostgreSQL Source Code  git master
binaryheap.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * binaryheap.c
4  * A simple binary heap implementation
5  *
6  * Portions Copyright (c) 2012-2022, 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 *
33 {
34  int sz;
35  binaryheap *heap;
36 
37  sz = offsetof(binaryheap, bh_nodes) + sizeof(Datum) * capacity;
38  heap = (binaryheap *) palloc(sz);
39  heap->bh_space = capacity;
40  heap->bh_compare = compare;
41  heap->bh_arg = arg;
42 
43  heap->bh_size = 0;
44  heap->bh_has_heap_property = true;
45 
46  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
57 {
58  heap->bh_size = 0;
59  heap->bh_has_heap_property = true;
60 }
61 
62 /*
63  * binaryheap_free
64  *
65  * Releases memory used by the given binaryheap.
66  */
67 void
69 {
70  pfree(heap);
71 }
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
84 {
85  return 2 * i + 1;
86 }
87 
88 static inline int
90 {
91  return 2 * i + 2;
92 }
93 
94 static inline int
96 {
97  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
110 {
111  if (heap->bh_size >= heap->bh_space)
112  elog(ERROR, "out of binary heap slots");
113  heap->bh_has_heap_property = false;
114  heap->bh_nodes[heap->bh_size] = d;
115  heap->bh_size++;
116 }
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
126 {
127  int i;
128 
129  for (i = parent_offset(heap->bh_size - 1); i >= 0; i--)
130  sift_down(heap, i);
131  heap->bh_has_heap_property = true;
132 }
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
142 {
143  if (heap->bh_size >= heap->bh_space)
144  elog(ERROR, "out of binary heap slots");
145  heap->bh_nodes[heap->bh_size] = d;
146  heap->bh_size++;
147  sift_up(heap, heap->bh_size - 1);
148 }
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
159 {
161  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
174 {
175  Datum result;
176 
178 
179  /* extract the root node, which will be the result */
180  result = heap->bh_nodes[0];
181 
182  /* easy if heap contains one element */
183  if (heap->bh_size == 1)
184  {
185  heap->bh_size--;
186  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  heap->bh_nodes[0] = heap->bh_nodes[--heap->bh_size];
194  sift_down(heap, 0);
195 
196  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
208 {
210 
211  heap->bh_nodes[0] = d;
212 
213  if (heap->bh_size > 1)
214  sift_down(heap, 0);
215 }
216 
217 /*
218  * Sift a node up to the highest position it can hold according to the
219  * comparator.
220  */
221 static void
222 sift_up(binaryheap *heap, int node_off)
223 {
224  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  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  parent_off = parent_offset(node_off);
242  parent_val = heap->bh_nodes[parent_off];
243  cmp = heap->bh_compare(node_val,
244  parent_val,
245  heap->bh_arg);
246  if (cmp <= 0)
247  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  heap->bh_nodes[node_off] = parent_val;
254  node_off = parent_off;
255  }
256  /* Re-fill the hole */
257  heap->bh_nodes[node_off] = node_val;
258 }
259 
260 /*
261  * Sift a node down from its current position to satisfy the heap
262  * property.
263  */
264 static void
265 sift_down(binaryheap *heap, int node_off)
266 {
267  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  {
276  int left_off = left_offset(node_off);
277  int right_off = right_offset(node_off);
278  int swap_off = 0;
279 
280  /* Is the left child larger than the parent? */
281  if (left_off < heap->bh_size &&
282  heap->bh_compare(node_val,
283  heap->bh_nodes[left_off],
284  heap->bh_arg) < 0)
285  swap_off = left_off;
286 
287  /* Is the right child larger than the parent? */
288  if (right_off < heap->bh_size &&
289  heap->bh_compare(node_val,
290  heap->bh_nodes[right_off],
291  heap->bh_arg) < 0)
292  {
293  /* swap with the larger child */
294  if (!swap_off ||
295  heap->bh_compare(heap->bh_nodes[left_off],
296  heap->bh_nodes[right_off],
297  heap->bh_arg) < 0)
298  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  if (!swap_off)
306  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  heap->bh_nodes[node_off] = heap->bh_nodes[swap_off];
313  node_off = swap_off;
314  }
315  /* Re-fill the hole */
316  heap->bh_nodes[node_off] = node_val;
317 }
void binaryheap_build(binaryheap *heap)
Definition: binaryheap.c:125
void binaryheap_add_unordered(binaryheap *heap, Datum d)
Definition: binaryheap.c:109
void binaryheap_reset(binaryheap *heap)
Definition: binaryheap.c:56
static void sift_down(binaryheap *heap, int node_off)
Definition: binaryheap.c:265
static int parent_offset(int i)
Definition: binaryheap.c:95
binaryheap * binaryheap_allocate(int capacity, binaryheap_comparator compare, void *arg)
Definition: binaryheap.c:32
Datum binaryheap_remove_first(binaryheap *heap)
Definition: binaryheap.c:173
static void sift_up(binaryheap *heap, int node_off)
Definition: binaryheap.c:222
static int right_offset(int i)
Definition: binaryheap.c:89
static int left_offset(int i)
Definition: binaryheap.c:83
void binaryheap_free(binaryheap *heap)
Definition: binaryheap.c:68
void binaryheap_replace_first(binaryheap *heap, Datum d)
Definition: binaryheap.c:207
Datum binaryheap_first(binaryheap *heap)
Definition: binaryheap.c:158
void binaryheap_add(binaryheap *heap, Datum d)
Definition: binaryheap.c:141
#define binaryheap_empty(h)
Definition: binaryheap.h:52
int(* binaryheap_comparator)(Datum a, Datum b, void *arg)
Definition: binaryheap.h:18
#define offsetof(type, field)
Definition: c.h:727
#define ERROR
Definition: elog.h:33
#define elog(elevel,...)
Definition: elog.h:218
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
int i
Definition: isn.c:73
Assert(fmt[strlen(fmt) - 1] !='\n')
void pfree(void *pointer)
Definition: mcxt.c:1175
void * palloc(Size size)
Definition: mcxt.c:1068
void * arg
uintptr_t Datum
Definition: postgres.h:411
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:747
bool bh_has_heap_property
Definition: binaryheap.h:34
int bh_space
Definition: binaryheap.h:33
int bh_size
Definition: binaryheap.h:32
Datum bh_nodes[FLEXIBLE_ARRAY_MEMBER]
Definition: binaryheap.h:37
binaryheap_comparator bh_compare
Definition: binaryheap.h:35
void * bh_arg
Definition: binaryheap.h:36