PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
binaryheap.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  binaryheap
 

Macros

#define binaryheap_empty(h)   ((h)->bh_size == 0)
 

Typedefs

typedef int(* binaryheap_comparator )(Datum a, Datum b, void *arg)
 
typedef struct binaryheap binaryheap
 

Functions

binaryheapbinaryheap_allocate (int capacity, binaryheap_comparator compare, void *arg)
 
void binaryheap_reset (binaryheap *heap)
 
void binaryheap_free (binaryheap *heap)
 
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)
 

Macro Definition Documentation

#define binaryheap_empty (   h)    ((h)->bh_size == 0)

Typedef Documentation

typedef int(* binaryheap_comparator)(Datum a, Datum b, void *arg)

Definition at line 18 of file binaryheap.h.

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(), gather_merge_init(), 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(), gather_merge_setup(), 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:372
void * palloc(Size size)
Definition: mcxt.c:848
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:549
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(), gather_merge_init(), 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(), gather_merge_getnext(), and ReorderBufferIterTXNNext().

160 {
162  return heap->bh_nodes[0];
163 }
#define binaryheap_empty(h)
Definition: binaryheap.h:52
#define Assert(condition)
Definition: c.h:681
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:949
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(), gather_merge_getnext(), 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:681
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(), gather_merge_getnext(), 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:681
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(), and gather_merge_init().

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