PostgreSQL Source Code  git master
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-2023, 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;
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 */
void binaryheap_build(binaryheap *heap)
Definition: binaryheap.c:125
void binaryheap_add_unordered(binaryheap *heap, Datum d)
Definition: binaryheap.c:109
void binaryheap_reset(binaryheap *heap)
Definition: binaryheap.c:56
binaryheap * binaryheap_allocate(int capacity, binaryheap_comparator compare, void *arg)
Definition: binaryheap.c:32
Datum binaryheap_remove_first(binaryheap *heap)
Definition: binaryheap.c:173
struct binaryheap binaryheap
void binaryheap_free(binaryheap *heap)
Definition: binaryheap.c:68
void binaryheap_replace_first(binaryheap *heap, Datum d)
Definition: binaryheap.c:207
Datum binaryheap_first(binaryheap *heap)
Definition: binaryheap.c:158
void binaryheap_add(binaryheap *heap, Datum d)
Definition: binaryheap.c:141
int(* binaryheap_comparator)(Datum a, Datum b, void *arg)
Definition: binaryheap.h:18
#define FLEXIBLE_ARRAY_MEMBER
Definition: c.h:382
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
int b
Definition: isn.c:70
int a
Definition: isn.c:69
void * arg
uintptr_t Datum
Definition: postgres.h:64
bool bh_has_heap_property
Definition: binaryheap.h:34
int bh_space
Definition: binaryheap.h:33
int bh_size
Definition: binaryheap.h:32
Datum bh_nodes[FLEXIBLE_ARRAY_MEMBER]
Definition: binaryheap.h:37
binaryheap_comparator bh_compare
Definition: binaryheap.h:35
void * bh_arg
Definition: binaryheap.h:36