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-2025, PostgreSQL Global Development Group
7 *
8 * src/include/lib/binaryheap.h
9 */
10
11#ifndef BINARYHEAP_H
12#define BINARYHEAP_H
13
14/*
15 * We provide a Datum-based API for backend code and a void *-based API for
16 * frontend code (since the Datum definitions are not available to frontend
17 * code). You should typically avoid using bh_node_type directly and instead
18 * use Datum or void * as appropriate.
19 */
20#ifdef FRONTEND
21typedef void *bh_node_type;
22#else
24#endif
25
26/*
27 * For a max-heap, the comparator must return <0 iff a < b, 0 iff a == b,
28 * and >0 iff a > b. For a min-heap, the conditions are reversed.
29 */
31
32/*
33 * binaryheap
34 *
35 * bh_size how many nodes are currently in "nodes"
36 * bh_space how many nodes can be stored in "nodes"
37 * bh_has_heap_property no unordered operations since last heap build
38 * bh_compare comparison function to define the heap property
39 * bh_arg user data for comparison function
40 * bh_nodes variable-length array of "space" nodes
41 */
42typedef struct binaryheap
43{
46 bool bh_has_heap_property; /* debugging cross-check */
48 void *bh_arg;
51
52extern binaryheap *binaryheap_allocate(int capacity,
54 void *arg);
55extern void binaryheap_reset(binaryheap *heap);
56extern void binaryheap_free(binaryheap *heap);
58extern void binaryheap_build(binaryheap *heap);
59extern void binaryheap_add(binaryheap *heap, bh_node_type d);
62extern void binaryheap_remove_node(binaryheap *heap, int n);
64
65#define binaryheap_empty(h) ((h)->bh_size == 0)
66#define binaryheap_size(h) ((h)->bh_size)
67#define binaryheap_get_node(h, n) ((h)->bh_nodes[n])
68
69#endif /* BINARYHEAP_H */
void binaryheap_remove_node(binaryheap *heap, int n)
Definition: binaryheap.c:225
void binaryheap_build(binaryheap *heap)
Definition: binaryheap.c:138
void binaryheap_replace_first(binaryheap *heap, bh_node_type d)
Definition: binaryheap.c:255
void binaryheap_reset(binaryheap *heap)
Definition: binaryheap.c:63
bh_node_type binaryheap_first(binaryheap *heap)
Definition: binaryheap.c:177
void binaryheap_add(binaryheap *heap, bh_node_type d)
Definition: binaryheap.c:154
bh_node_type binaryheap_remove_first(binaryheap *heap)
Definition: binaryheap.c:192
int(* binaryheap_comparator)(bh_node_type a, bh_node_type b, void *arg)
Definition: binaryheap.h:30
struct binaryheap binaryheap
void binaryheap_free(binaryheap *heap)
Definition: binaryheap.c:75
Datum bh_node_type
Definition: binaryheap.h:23
void binaryheap_add_unordered(binaryheap *heap, bh_node_type d)
Definition: binaryheap.c:116
binaryheap * binaryheap_allocate(int capacity, binaryheap_comparator compare, void *arg)
Definition: binaryheap.c:39
#define FLEXIBLE_ARRAY_MEMBER
Definition: c.h:420
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
int b
Definition: isn.c:69
int a
Definition: isn.c:68
void * arg
uintptr_t Datum
Definition: postgres.h:69
bool bh_has_heap_property
Definition: binaryheap.h:46
int bh_space
Definition: binaryheap.h:45
int bh_size
Definition: binaryheap.h:44
binaryheap_comparator bh_compare
Definition: binaryheap.h:47
bh_node_type bh_nodes[FLEXIBLE_ARRAY_MEMBER]
Definition: binaryheap.h:49
void * bh_arg
Definition: binaryheap.h:48