PostgreSQL Source Code git master
Data Structures | Macros | Typedefs | Functions
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)
 
#define  binaryheap_size(h)   ((h)->bh_size)
 
#define  binaryheap_get_node(h, n)   ((h)->bh_nodes[n])
 

Typedefs

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

Functions

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

Macro Definition Documentation

◆ binaryheap_empty

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

Definition at line 65 of file binaryheap.h.

◆ binaryheap_get_node

#define binaryheap_get_node (   h,
  n 
)    ((h)->bh_nodes[n])

Definition at line 67 of file binaryheap.h.

◆ binaryheap_size

#define binaryheap_size (   h )    ((h)->bh_size)

Definition at line 66 of file binaryheap.h.

Typedef Documentation

◆ bh_node_type

typedef Datum bh_node_type

Definition at line 23 of file binaryheap.h.

◆ binaryheap

typedef struct binaryheap binaryheap

◆ binaryheap_comparator

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

Definition at line 30 of file binaryheap.h.

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:226
#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(), test_basic(), test_duplicates(), test_remove_node(), test_replace_first(), test_reset(), 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(), test_build(), 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:1365
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(), test_basic(), test_build(), test_duplicates(), test_remove_node(), test_replace_first(), test_reset(), 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
i
int i
Definition: isn.c:77

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(), test_build(), 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
Assert(PointerIsAligned(start, uint64))

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

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

◆ 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:1594

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(), test_basic(), test_duplicates(), 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(), and test_remove_node().

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

◆ 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(), pgarch_readyXlog(), and test_reset().

AltStyle によって変換されたページ (->オリジナル) /