PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
binaryheap.h
Go to the documentation of this file.
1 /*
2  * binaryheap.h
3  *
4  * A simple binary heap implementation
5  *
6  * Portions Copyright (c) 2012-2017, PostgreSQL Global Development Group
7  *
8  * src/include/lib/binaryheap.h
9  */
10 
11 #ifndef BINARYHEAP_H
12 #define BINARYHEAP_H
13 
14 /*
15  * For a max-heap, the comparator must return <0 iff a < b, 0 iff a == b,
16  * and >0 iff a > b. For a min-heap, the conditions are reversed.
17  */
18 typedef int (*binaryheap_comparator) (Datum a, Datum b, void *arg);
19 
20 /*
21  * binaryheap
22  *
23  * bh_size how many nodes are currently in "nodes"
24  * bh_space how many nodes can be stored in "nodes"
25  * bh_has_heap_property no unordered operations since last heap build
26  * bh_compare comparison function to define the heap property
27  * bh_arg user data for comparison function
28  * bh_nodes variable-length array of "space" nodes
29  */
30 typedef struct binaryheap
31 {
32  int bh_size;
33  int bh_space;
34  bool bh_has_heap_property; /* debugging cross-check */
36  void *bh_arg;
37  Datum bh_nodes[FLEXIBLE_ARRAY_MEMBER];
38 } binaryheap;
39 
40 extern binaryheap *binaryheap_allocate(int capacity,
42  void *arg);
43 extern void binaryheap_reset(binaryheap *heap);
44 extern void binaryheap_free(binaryheap *heap);
45 extern void binaryheap_add_unordered(binaryheap *heap, Datum d);
46 extern void binaryheap_build(binaryheap *heap);
47 extern void binaryheap_add(binaryheap *heap, Datum d);
48 extern Datum binaryheap_first(binaryheap *heap);
50 extern void binaryheap_replace_first(binaryheap *heap, Datum d);
51 
52 #define binaryheap_empty(h) ((h)->bh_size == 0)
53 
54 #endif /* BINARYHEAP_H */
int bh_space
Definition: binaryheap.h:33
void binaryheap_replace_first(binaryheap *heap, Datum d)
Definition: binaryheap.c:204
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
struct binaryheap binaryheap
void binaryheap_reset(binaryheap *heap)
Definition: binaryheap.c:57
binaryheap_comparator bh_compare
Definition: binaryheap.h:35
int bh_size
Definition: binaryheap.h:32
int(* binaryheap_comparator)(Datum a, Datum b, void *arg)
Definition: binaryheap.h:18
uintptr_t Datum
Definition: postgres.h:372
Datum binaryheap_remove_first(binaryheap *heap)
Definition: binaryheap.c:174
void binaryheap_add(binaryheap *heap, Datum d)
Definition: binaryheap.c:142
binaryheap * binaryheap_allocate(int capacity, binaryheap_comparator compare, void *arg)
Definition: binaryheap.c:33
Datum binaryheap_first(binaryheap *heap)
Definition: binaryheap.c:159
void binaryheap_free(binaryheap *heap)
Definition: binaryheap.c:69
Datum bh_nodes[FLEXIBLE_ARRAY_MEMBER]
Definition: binaryheap.h:37
void * arg
bool bh_has_heap_property
Definition: binaryheap.h:34
void binaryheap_add_unordered(binaryheap *heap, Datum d)
Definition: binaryheap.c:110
void binaryheap_build(binaryheap *heap)
Definition: binaryheap.c:126
void * bh_arg
Definition: binaryheap.h:36