PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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)
 
static void swap_nodes (binaryheap *heap, int a, int b)
 
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

void binaryheap_add ( binaryheap heap,
Datum  d 
)

Definition at line 142 of file binaryheap.c.

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

143 {
144  if (heap->bh_size >= heap->bh_space)
145  elog(ERROR, "out of binary heap slots");
146  heap->bh_nodes[heap->bh_size] = d;
147  heap->bh_size++;
148  sift_up(heap, heap->bh_size - 1);
149 }
int bh_space
Definition: binaryheap.h:33
#define ERROR
Definition: elog.h:43
int bh_size
Definition: binaryheap.h:32
static void sift_up(binaryheap *heap, int node_off)
Definition: binaryheap.c:232
Datum bh_nodes[FLEXIBLE_ARRAY_MEMBER]
Definition: binaryheap.h:37
#define elog
Definition: elog.h:219
void binaryheap_add_unordered ( binaryheap heap,
Datum  d 
)

Definition at line 110 of file binaryheap.c.

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

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

111 {
112  if (heap->bh_size >= heap->bh_space)
113  elog(ERROR, "out of binary heap slots");
114  heap->bh_has_heap_property = false;
115  heap->bh_nodes[heap->bh_size] = d;
116  heap->bh_size++;
117 }
int bh_space
Definition: binaryheap.h:33
#define ERROR
Definition: elog.h:43
int bh_size
Definition: binaryheap.h:32
Datum bh_nodes[FLEXIBLE_ARRAY_MEMBER]
Definition: binaryheap.h:37
bool bh_has_heap_property
Definition: binaryheap.h:34
#define elog
Definition: elog.h:219
binaryheap* binaryheap_allocate ( int  capacity,
binaryheap_comparator  compare,
void *  arg 
)

Definition at line 33 of file binaryheap.c.

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

34 {
35  int sz;
36  binaryheap *heap;
37 
38  sz = offsetof(binaryheap, bh_nodes) +sizeof(Datum) * capacity;
39  heap = (binaryheap *) palloc(sz);
40  heap->bh_space = capacity;
41  heap->bh_compare = compare;
42  heap->bh_arg = arg;
43 
44  heap->bh_size = 0;
45  heap->bh_has_heap_property = true;
46 
47  return heap;
48 }
int bh_space
Definition: binaryheap.h:33
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
binaryheap_comparator bh_compare
Definition: binaryheap.h:35
int bh_size
Definition: binaryheap.h:32
uintptr_t Datum
Definition: postgres.h:374
void * palloc(Size size)
Definition: mcxt.c:891
void * arg
bool bh_has_heap_property
Definition: binaryheap.h:34
void * bh_arg
Definition: binaryheap.h:36
#define offsetof(type, field)
Definition: c.h:551
void binaryheap_build ( binaryheap heap)

Definition at line 126 of file binaryheap.c.

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

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

127 {
128  int i;
129 
130  for (i = parent_offset(heap->bh_size - 1); i >= 0; i--)
131  sift_down(heap, i);
132  heap->bh_has_heap_property = true;
133 }
static int parent_offset(int i)
Definition: binaryheap.c:96
static void sift_down(binaryheap *heap, int node_off)
Definition: binaryheap.c:264
int bh_size
Definition: binaryheap.h:32
int i
bool bh_has_heap_property
Definition: binaryheap.h:34
Datum binaryheap_first ( binaryheap heap)

Definition at line 159 of file binaryheap.c.

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

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

160 {
162  return heap->bh_nodes[0];
163 }
#define binaryheap_empty(h)
Definition: binaryheap.h:52
#define Assert(condition)
Definition: c.h:671
Datum bh_nodes[FLEXIBLE_ARRAY_MEMBER]
Definition: binaryheap.h:37
bool bh_has_heap_property
Definition: binaryheap.h:34
void binaryheap_free ( binaryheap heap)

Definition at line 69 of file binaryheap.c.

References pfree().

Referenced by BufferSync(), and ReorderBufferIterTXNFinish().

70 {
71  pfree(heap);
72 }
void pfree(void *pointer)
Definition: mcxt.c:992
Datum binaryheap_remove_first ( binaryheap heap)

Definition at line 174 of file binaryheap.c.

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

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

175 {
177 
178  if (heap->bh_size == 1)
179  {
180  heap->bh_size--;
181  return heap->bh_nodes[0];
182  }
183 
184  /*
185  * Swap the root and last nodes, decrease the size of the heap (i.e.
186  * remove the former root node) and sift the new root node down to its
187  * correct position.
188  */
189  swap_nodes(heap, 0, heap->bh_size - 1);
190  heap->bh_size--;
191  sift_down(heap, 0);
192 
193  return heap->bh_nodes[heap->bh_size];
194 }
static void swap_nodes(binaryheap *heap, int a, int b)
Definition: binaryheap.c:218
#define binaryheap_empty(h)
Definition: binaryheap.h:52
static void sift_down(binaryheap *heap, int node_off)
Definition: binaryheap.c:264
int bh_size
Definition: binaryheap.h:32
#define Assert(condition)
Definition: c.h:671
Datum bh_nodes[FLEXIBLE_ARRAY_MEMBER]
Definition: binaryheap.h:37
bool bh_has_heap_property
Definition: binaryheap.h:34
void binaryheap_replace_first ( binaryheap heap,
Datum  d 
)

Definition at line 204 of file binaryheap.c.

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

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

205 {
207 
208  heap->bh_nodes[0] = d;
209 
210  if (heap->bh_size > 1)
211  sift_down(heap, 0);
212 }
#define binaryheap_empty(h)
Definition: binaryheap.h:52
static void sift_down(binaryheap *heap, int node_off)
Definition: binaryheap.c:264
int bh_size
Definition: binaryheap.h:32
#define Assert(condition)
Definition: c.h:671
Datum bh_nodes[FLEXIBLE_ARRAY_MEMBER]
Definition: binaryheap.h:37
bool bh_has_heap_property
Definition: binaryheap.h:34
void binaryheap_reset ( binaryheap heap)

Definition at line 57 of file binaryheap.c.

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

Referenced by ExecReScanMergeAppend().

58 {
59  heap->bh_size = 0;
60  heap->bh_has_heap_property = true;
61 }
int bh_size
Definition: binaryheap.h:32
bool bh_has_heap_property
Definition: binaryheap.h:34
static int left_offset ( int  i)
inlinestatic

Definition at line 84 of file binaryheap.c.

Referenced by sift_down().

85 {
86  return 2 * i + 1;
87 }
int i
static int parent_offset ( int  i)
inlinestatic

Definition at line 96 of file binaryheap.c.

Referenced by binaryheap_build(), and sift_up().

97 {
98  return (i - 1) / 2;
99 }
int i
static int right_offset ( int  i)
inlinestatic

Definition at line 90 of file binaryheap.c.

Referenced by sift_down().

91 {
92  return 2 * i + 2;
93 }
int i
static void sift_down ( binaryheap heap,
int  node_off 
)
static

Definition at line 264 of file binaryheap.c.

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

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

265 {
266  while (true)
267  {
268  int left_off = left_offset(node_off);
269  int right_off = right_offset(node_off);
270  int swap_off = 0;
271 
272  /* Is the left child larger than the parent? */
273  if (left_off < heap->bh_size &&
274  heap->bh_compare(heap->bh_nodes[node_off],
275  heap->bh_nodes[left_off],
276  heap->bh_arg) < 0)
277  swap_off = left_off;
278 
279  /* Is the right child larger than the parent? */
280  if (right_off < heap->bh_size &&
281  heap->bh_compare(heap->bh_nodes[node_off],
282  heap->bh_nodes[right_off],
283  heap->bh_arg) < 0)
284  {
285  /* swap with the larger child */
286  if (!swap_off ||
287  heap->bh_compare(heap->bh_nodes[left_off],
288  heap->bh_nodes[right_off],
289  heap->bh_arg) < 0)
290  swap_off = right_off;
291  }
292 
293  /*
294  * If we didn't find anything to swap, the heap condition is
295  * satisfied, and we're done.
296  */
297  if (!swap_off)
298  break;
299 
300  /*
301  * Otherwise, swap the node with the child that violates the heap
302  * property; then go on to check its children.
303  */
304  swap_nodes(heap, swap_off, node_off);
305  node_off = swap_off;
306  }
307 }
static void swap_nodes(binaryheap *heap, int a, int b)
Definition: binaryheap.c:218
binaryheap_comparator bh_compare
Definition: binaryheap.h:35
static int right_offset(int i)
Definition: binaryheap.c:90
Datum bh_nodes[FLEXIBLE_ARRAY_MEMBER]
Definition: binaryheap.h:37
void * bh_arg
Definition: binaryheap.h:36
static int left_offset(int i)
Definition: binaryheap.c:84
static void sift_up ( binaryheap heap,
int  node_off 
)
static

Definition at line 232 of file binaryheap.c.

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

Referenced by binaryheap_add().

233 {
234  while (node_off != 0)
235  {
236  int cmp;
237  int parent_off;
238 
239  /*
240  * If this node is smaller than its parent, the heap condition is
241  * satisfied, and we're done.
242  */
243  parent_off = parent_offset(node_off);
244  cmp = heap->bh_compare(heap->bh_nodes[node_off],
245  heap->bh_nodes[parent_off],
246  heap->bh_arg);
247  if (cmp <= 0)
248  break;
249 
250  /*
251  * Otherwise, swap the node and its parent and go on to check the
252  * node's new parent.
253  */
254  swap_nodes(heap, node_off, parent_off);
255  node_off = parent_off;
256  }
257 }
static void swap_nodes(binaryheap *heap, int a, int b)
Definition: binaryheap.c:218
static int parent_offset(int i)
Definition: binaryheap.c:96
binaryheap_comparator bh_compare
Definition: binaryheap.h:35
Datum bh_nodes[FLEXIBLE_ARRAY_MEMBER]
Definition: binaryheap.h:37
void * bh_arg
Definition: binaryheap.h:36
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742
static void swap_nodes ( binaryheap heap,
int  a,
int  b 
)
inlinestatic

Definition at line 218 of file binaryheap.c.

References binaryheap::bh_nodes, and swap.

Referenced by binaryheap_remove_first(), sift_down(), and sift_up().

219 {
220  Datum swap;
221 
222  swap = heap->bh_nodes[a];
223  heap->bh_nodes[a] = heap->bh_nodes[b];
224  heap->bh_nodes[b] = swap;
225 }
#define swap(a, b)
Definition: qsort.c:94
uintptr_t Datum
Definition: postgres.h:374
Datum bh_nodes[FLEXIBLE_ARRAY_MEMBER]
Definition: binaryheap.h:37