PostgreSQL Source Code  git master
binaryheap.c File Reference
#include "postgres.h"
#include <math.h>
#include "lib/binaryheap.h"
Include dependency graph for binaryheap.c:

Go to the source code of this file.

Functions

static void sift_down (binaryheap *heap, int node_off)
 
static void sift_up (binaryheap *heap, int node_off)
 
binaryheapbinaryheap_allocate (int capacity, binaryheap_comparator compare, void *arg)
 
void binaryheap_reset (binaryheap *heap)
 
void binaryheap_free (binaryheap *heap)
 
static int left_offset (int i)
 
static int right_offset (int i)
 
static int parent_offset (int i)
 
void binaryheap_add_unordered (binaryheap *heap, Datum d)
 
void binaryheap_build (binaryheap *heap)
 
void binaryheap_add (binaryheap *heap, Datum d)
 
Datum binaryheap_first (binaryheap *heap)
 
Datum binaryheap_remove_first (binaryheap *heap)
 
void binaryheap_replace_first (binaryheap *heap, Datum d)
 

Function Documentation

◆ binaryheap_add()

void binaryheap_add ( binaryheap heap,
Datum  d 
)

Definition at line 141 of file binaryheap.c.

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 }
static void sift_up(binaryheap *heap, int node_off)
Definition: binaryheap.c:222
#define ERROR
Definition: elog.h:33
#define elog(elevel,...)
Definition: elog.h:218
int bh_space
Definition: binaryheap.h:33
int bh_size
Definition: binaryheap.h:32
Datum bh_nodes[FLEXIBLE_ARRAY_MEMBER]
Definition: binaryheap.h:37

References binaryheap::bh_nodes, binaryheap::bh_size, binaryheap::bh_space, elog, ERROR, and sift_up().

Referenced by pgarch_readyXlog().

◆ binaryheap_add_unordered()

void binaryheap_add_unordered ( binaryheap heap,
Datum  d 
)

Definition at line 109 of file binaryheap.c.

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 }
bool bh_has_heap_property
Definition: binaryheap.h:34

References binaryheap::bh_has_heap_property, binaryheap::bh_nodes, binaryheap::bh_size, binaryheap::bh_space, elog, and ERROR.

Referenced by BufferSync(), ExecMergeAppend(), gather_merge_init(), pgarch_readyXlog(), and ReorderBufferIterTXNInit().

◆ binaryheap_allocate()

binaryheap* binaryheap_allocate ( int  capacity,
binaryheap_comparator  compare,
void *  arg 
)

Definition at line 32 of file binaryheap.c.

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 }
#define offsetof(type, field)
Definition: c.h:727
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
void * palloc(Size size)
Definition: mcxt.c:1068
void * arg
uintptr_t Datum
Definition: postgres.h:411
binaryheap_comparator bh_compare
Definition: binaryheap.h:35
void * bh_arg
Definition: binaryheap.h:36

References arg, binaryheap::bh_arg, binaryheap::bh_compare, binaryheap::bh_has_heap_property, binaryheap::bh_size, binaryheap::bh_space, compare(), offsetof, and palloc().

Referenced by BufferSync(), ExecInitMergeAppend(), gather_merge_setup(), PgArchiverMain(), and ReorderBufferIterTXNInit().

◆ binaryheap_build()

void binaryheap_build ( binaryheap heap)

Definition at line 125 of file binaryheap.c.

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 }
static void sift_down(binaryheap *heap, int node_off)
Definition: binaryheap.c:265
static int parent_offset(int i)
Definition: binaryheap.c:95
int i
Definition: isn.c:73

References binaryheap::bh_has_heap_property, binaryheap::bh_size, i, parent_offset(), and sift_down().

Referenced by BufferSync(), ExecMergeAppend(), gather_merge_init(), pgarch_readyXlog(), and ReorderBufferIterTXNInit().

◆ binaryheap_first()

Datum binaryheap_first ( binaryheap heap)

Definition at line 158 of file binaryheap.c.

159 {
161  return heap->bh_nodes[0];
162 }
#define binaryheap_empty(h)
Definition: binaryheap.h:52
Assert(fmt[strlen(fmt) - 1] !='\n')

References Assert(), binaryheap::bh_has_heap_property, binaryheap::bh_nodes, and binaryheap_empty.

Referenced by BufferSync(), ExecMergeAppend(), gather_merge_getnext(), pgarch_readyXlog(), and ReorderBufferIterTXNNext().

◆ binaryheap_free()

void binaryheap_free ( binaryheap heap)

Definition at line 68 of file binaryheap.c.

69 {
70  pfree(heap);
71 }
void pfree(void *pointer)
Definition: mcxt.c:1175

References pfree().

Referenced by BufferSync(), and ReorderBufferIterTXNFinish().

◆ binaryheap_remove_first()

Datum binaryheap_remove_first ( binaryheap heap)

Definition at line 173 of file binaryheap.c.

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 }

References Assert(), binaryheap::bh_has_heap_property, binaryheap::bh_nodes, binaryheap::bh_size, binaryheap_empty, and sift_down().

Referenced by BufferSync(), ExecMergeAppend(), gather_merge_getnext(), pgarch_readyXlog(), and ReorderBufferIterTXNNext().

◆ binaryheap_replace_first()

void binaryheap_replace_first ( binaryheap heap,
Datum  d 
)

Definition at line 207 of file binaryheap.c.

208 {
210 
211  heap->bh_nodes[0] = d;
212 
213  if (heap->bh_size > 1)
214  sift_down(heap, 0);
215 }

References Assert(), binaryheap::bh_has_heap_property, binaryheap::bh_nodes, binaryheap::bh_size, binaryheap_empty, and sift_down().

Referenced by BufferSync(), ExecMergeAppend(), gather_merge_getnext(), and ReorderBufferIterTXNNext().

◆ binaryheap_reset()

void binaryheap_reset ( binaryheap heap)

Definition at line 56 of file binaryheap.c.

57 {
58  heap->bh_size = 0;
59  heap->bh_has_heap_property = true;
60 }

References binaryheap::bh_has_heap_property, and binaryheap::bh_size.

Referenced by ExecReScanMergeAppend(), gather_merge_init(), and pgarch_readyXlog().

◆ left_offset()

static int left_offset ( int  i)
inlinestatic

Definition at line 83 of file binaryheap.c.

84 {
85  return 2 * i + 1;
86 }

References i.

Referenced by sift_down().

◆ parent_offset()

static int parent_offset ( int  i)
inlinestatic

Definition at line 95 of file binaryheap.c.

96 {
97  return (i - 1) / 2;
98 }

References i.

Referenced by binaryheap_build(), and sift_up().

◆ right_offset()

static int right_offset ( int  i)
inlinestatic

Definition at line 89 of file binaryheap.c.

90 {
91  return 2 * i + 2;
92 }

References i.

Referenced by sift_down().

◆ sift_down()

static void sift_down ( binaryheap heap,
int  node_off 
)
static

Definition at line 265 of file binaryheap.c.

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 }
static int right_offset(int i)
Definition: binaryheap.c:89
static int left_offset(int i)
Definition: binaryheap.c:83

References binaryheap::bh_arg, binaryheap::bh_compare, binaryheap::bh_nodes, left_offset(), and right_offset().

Referenced by binaryheap_build(), binaryheap_remove_first(), and binaryheap_replace_first().

◆ sift_up()

static void sift_up ( binaryheap heap,
int  node_off 
)
static

Definition at line 222 of file binaryheap.c.

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 }
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:747

References binaryheap::bh_arg, binaryheap::bh_compare, binaryheap::bh_nodes, cmp(), and parent_offset().

Referenced by binaryheap_add().