1/*
2 * binaryheap.h
3 *
4 * A simple binary heap implementation
5 *
6 * Portions Copyright (c) 2012-2019, 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 */
18typedef 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 */
30typedef struct binaryheap
31{
32 int bh_size;
33 int bh_space;
34 bool bh_has_heap_property; /* debugging cross-check */
35 binaryheap_comparator bh_compare;
36 void *bh_arg;
37 Datum bh_nodes[FLEXIBLE_ARRAY_MEMBER];
38} binaryheap;
39
40extern binaryheap *binaryheap_allocate(int capacity,
41 binaryheap_comparator compare,
42 void *arg);
43extern void binaryheap_reset(binaryheap *heap);
44extern void binaryheap_free(binaryheap *heap);
45extern void binaryheap_add_unordered(binaryheap *heap, Datum d);
46extern void binaryheap_build(binaryheap *heap);
47extern void binaryheap_add(binaryheap *heap, Datum d);
48extern Datum binaryheap_first(binaryheap *heap);
49extern Datum binaryheap_remove_first(binaryheap *heap);
50extern void binaryheap_replace_first(binaryheap *heap, Datum d);
51
52#define binaryheap_empty(h) ((h)->bh_size == 0)
53
54#endif /* BINARYHEAP_H */
55