PostgreSQL Source Code  git master
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

◆ binaryheap_empty

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

Definition at line 52 of file binaryheap.h.

Typedef Documentation

◆ binaryheap

typedef struct binaryheap binaryheap

◆ binaryheap_comparator

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

Definition at line 18 of file binaryheap.h.

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:39
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 }
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
void * palloc(Size size)
Definition: mcxt.c:1226
void * arg
uintptr_t Datum
Definition: postgres.h:64
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(), 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:1456

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().