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, bh_node_type d)
 
void binaryheap_build (binaryheap *heap)
 
void binaryheap_add (binaryheap *heap, bh_node_type d)
 
bh_node_type binaryheap_first (binaryheap *heap)
 
bh_node_type binaryheap_remove_first (binaryheap *heap)
 
void binaryheap_remove_node (binaryheap *heap, int n)
 
void binaryheap_replace_first (binaryheap *heap, bh_node_type d)
 

Function Documentation

◆ binaryheap_add()

void binaryheap_add ( binaryheap heap,
bh_node_type  d 
)

Definition at line 154 of file binaryheap.c.

155 {
156  if (heap->bh_size >= heap->bh_space)
157  {
158 #ifdef FRONTEND
159  pg_fatal("out of binary heap slots");
160 #else
161  elog(ERROR, "out of binary heap slots");
162 #endif
163  }
164  heap->bh_nodes[heap->bh_size] = d;
165  heap->bh_size++;
166  sift_up(heap, heap->bh_size - 1);
167 }
static void sift_up(binaryheap *heap, int node_off)
Definition: binaryheap.c:270
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
#define pg_fatal(...)
int bh_space
Definition: binaryheap.h:45
int bh_size
Definition: binaryheap.h:44
bh_node_type bh_nodes[FLEXIBLE_ARRAY_MEMBER]
Definition: binaryheap.h:49

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

Referenced by move_to_ready_heap(), pgarch_readyXlog(), reduce_dependencies(), and TopoSort().

◆ binaryheap_add_unordered()

void binaryheap_add_unordered ( binaryheap heap,
bh_node_type  d 
)

Definition at line 116 of file binaryheap.c.

117 {
118  if (heap->bh_size >= heap->bh_space)
119  {
120 #ifdef FRONTEND
121  pg_fatal("out of binary heap slots");
122 #else
123  elog(ERROR, "out of binary heap slots");
124 #endif
125  }
126  heap->bh_has_heap_property = false;
127  heap->bh_nodes[heap->bh_size] = d;
128  heap->bh_size++;
129 }
bool bh_has_heap_property
Definition: binaryheap.h:46

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

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

◆ binaryheap_allocate()

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

Definition at line 39 of file binaryheap.c.

40 {
41  int sz;
42  binaryheap *heap;
43 
44  sz = offsetof(binaryheap, bh_nodes) + sizeof(bh_node_type) * capacity;
45  heap = (binaryheap *) palloc(sz);
46  heap->bh_space = capacity;
47  heap->bh_compare = compare;
48  heap->bh_arg = arg;
49 
50  heap->bh_size = 0;
51  heap->bh_has_heap_property = true;
52 
53  return heap;
54 }
Datum bh_node_type
Definition: binaryheap.h:23
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
void * palloc(Size size)
Definition: mcxt.c:1317
void * arg
binaryheap_comparator bh_compare
Definition: binaryheap.h:47
void * bh_arg
Definition: binaryheap.h:48

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

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

◆ binaryheap_build()

void binaryheap_build ( binaryheap heap)

Definition at line 138 of file binaryheap.c.

139 {
140  int i;
141 
142  for (i = parent_offset(heap->bh_size - 1); i >= 0; i--)
143  sift_down(heap, i);
144  heap->bh_has_heap_property = true;
145 }
static void sift_down(binaryheap *heap, int node_off)
Definition: binaryheap.c:313
static int parent_offset(int i)
Definition: binaryheap.c:102
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(), ReorderBufferIterTXNInit(), and TopoSort().

◆ binaryheap_first()

bh_node_type binaryheap_first ( binaryheap heap)

Definition at line 177 of file binaryheap.c.

178 {
180  return heap->bh_nodes[0];
181 }
#define binaryheap_empty(h)
Definition: binaryheap.h:65
#define Assert(condition)
Definition: c.h:861

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 75 of file binaryheap.c.

76 {
77  pfree(heap);
78 }
void pfree(void *pointer)
Definition: mcxt.c:1521

References pfree().

Referenced by BufferSync(), ReorderBufferIterTXNFinish(), restore_toc_entries_parallel(), and TopoSort().

◆ binaryheap_remove_first()

bh_node_type binaryheap_remove_first ( binaryheap heap)

Definition at line 192 of file binaryheap.c.

193 {
194  bh_node_type result;
195 
197 
198  /* extract the root node, which will be the result */
199  result = heap->bh_nodes[0];
200 
201  /* easy if heap contains one element */
202  if (heap->bh_size == 1)
203  {
204  heap->bh_size--;
205  return result;
206  }
207 
208  /*
209  * Remove the last node, placing it in the vacated root entry, and sift
210  * the new root node down to its correct position.
211  */
212  heap->bh_nodes[0] = heap->bh_nodes[--heap->bh_size];
213  sift_down(heap, 0);
214 
215  return result;
216 }

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(), ReorderBufferIterTXNNext(), and TopoSort().

◆ binaryheap_remove_node()

void binaryheap_remove_node ( binaryheap heap,
int  n 
)

Definition at line 225 of file binaryheap.c.

226 {
227  int cmp;
228 
230  Assert(n >= 0 && n < heap->bh_size);
231 
232  /* compare last node to the one that is being removed */
233  cmp = heap->bh_compare(heap->bh_nodes[--heap->bh_size],
234  heap->bh_nodes[n],
235  heap->bh_arg);
236 
237  /* remove the last node, placing it in the vacated entry */
238  heap->bh_nodes[n] = heap->bh_nodes[heap->bh_size];
239 
240  /* sift as needed to preserve the heap property */
241  if (cmp > 0)
242  sift_up(heap, n);
243  else if (cmp < 0)
244  sift_down(heap, n);
245 }
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:743

References Assert, binaryheap::bh_arg, binaryheap::bh_compare, binaryheap::bh_has_heap_property, binaryheap::bh_nodes, binaryheap::bh_size, binaryheap_empty, cmp(), sift_down(), and sift_up().

Referenced by pop_next_work_item().

◆ binaryheap_replace_first()

void binaryheap_replace_first ( binaryheap heap,
bh_node_type  d 
)

Definition at line 255 of file binaryheap.c.

256 {
258 
259  heap->bh_nodes[0] = d;
260 
261  if (heap->bh_size > 1)
262  sift_down(heap, 0);
263 }

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 63 of file binaryheap.c.

64 {
65  heap->bh_size = 0;
66  heap->bh_has_heap_property = true;
67 }

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 90 of file binaryheap.c.

91 {
92  return 2 * i + 1;
93 }

References i.

Referenced by sift_down().

◆ parent_offset()

static int parent_offset ( int  i)
inlinestatic

Definition at line 102 of file binaryheap.c.

103 {
104  return (i - 1) / 2;
105 }

References i.

Referenced by binaryheap_build(), and sift_up().

◆ right_offset()

static int right_offset ( int  i)
inlinestatic

Definition at line 96 of file binaryheap.c.

97 {
98  return 2 * i + 2;
99 }

References i.

Referenced by sift_down().

◆ sift_down()

static void sift_down ( binaryheap heap,
int  node_off 
)
static

Definition at line 313 of file binaryheap.c.

314 {
315  bh_node_type node_val = heap->bh_nodes[node_off];
316 
317  /*
318  * Within the loop, the node_off'th array entry is a "hole" that
319  * notionally holds node_val, but we don't actually store node_val there
320  * till the end, saving some unnecessary data copying steps.
321  */
322  while (true)
323  {
324  int left_off = left_offset(node_off);
325  int right_off = right_offset(node_off);
326  int swap_off = 0;
327 
328  /* Is the left child larger than the parent? */
329  if (left_off < heap->bh_size &&
330  heap->bh_compare(node_val,
331  heap->bh_nodes[left_off],
332  heap->bh_arg) < 0)
333  swap_off = left_off;
334 
335  /* Is the right child larger than the parent? */
336  if (right_off < heap->bh_size &&
337  heap->bh_compare(node_val,
338  heap->bh_nodes[right_off],
339  heap->bh_arg) < 0)
340  {
341  /* swap with the larger child */
342  if (!swap_off ||
343  heap->bh_compare(heap->bh_nodes[left_off],
344  heap->bh_nodes[right_off],
345  heap->bh_arg) < 0)
346  swap_off = right_off;
347  }
348 
349  /*
350  * If we didn't find anything to swap, the heap condition is
351  * satisfied, and we're done.
352  */
353  if (!swap_off)
354  break;
355 
356  /*
357  * Otherwise, swap the hole with the child that violates the heap
358  * property; then go on to check its children.
359  */
360  heap->bh_nodes[node_off] = heap->bh_nodes[swap_off];
361  node_off = swap_off;
362  }
363  /* Re-fill the hole */
364  heap->bh_nodes[node_off] = node_val;
365 }
static int right_offset(int i)
Definition: binaryheap.c:96
static int left_offset(int i)
Definition: binaryheap.c:90

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

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

◆ sift_up()

static void sift_up ( binaryheap heap,
int  node_off 
)
static

Definition at line 270 of file binaryheap.c.

271 {
272  bh_node_type node_val = heap->bh_nodes[node_off];
273 
274  /*
275  * Within the loop, the node_off'th array entry is a "hole" that
276  * notionally holds node_val, but we don't actually store node_val there
277  * till the end, saving some unnecessary data copying steps.
278  */
279  while (node_off != 0)
280  {
281  int cmp;
282  int parent_off;
283  bh_node_type parent_val;
284 
285  /*
286  * If this node is smaller than its parent, the heap condition is
287  * satisfied, and we're done.
288  */
289  parent_off = parent_offset(node_off);
290  parent_val = heap->bh_nodes[parent_off];
291  cmp = heap->bh_compare(node_val,
292  parent_val,
293  heap->bh_arg);
294  if (cmp <= 0)
295  break;
296 
297  /*
298  * Otherwise, swap the parent value with the hole, and go on to check
299  * the node's new parent.
300  */
301  heap->bh_nodes[node_off] = parent_val;
302  node_off = parent_off;
303  }
304  /* Re-fill the hole */
305  heap->bh_nodes[node_off] = node_val;
306 }

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

Referenced by binaryheap_add(), and binaryheap_remove_node().