diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-04 12:15:05 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-04 12:15:05 +0000 |
commit | 46651ce6fe013220ed397add242004d764fc0153 (patch) | |
tree | 6e5299f990f88e60174a1d3ae6e48eedd2688b2b /src/include/lib/binaryheap.h | |
parent | Initial commit. (diff) | |
download | postgresql-14-46651ce6fe013220ed397add242004d764fc0153.tar.xz postgresql-14-46651ce6fe013220ed397add242004d764fc0153.zip |
Adding upstream version 14.5.upstream/14.5upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/include/lib/binaryheap.h')
-rw-r--r-- | src/include/lib/binaryheap.h | 54 |
1 files changed, 54 insertions, 0 deletions
diff --git a/src/include/lib/binaryheap.h b/src/include/lib/binaryheap.h new file mode 100644 index 0000000..5831351 --- /dev/null +++ b/src/include/lib/binaryheap.h @@ -0,0 +1,54 @@ +/* + * binaryheap.h + * + * A simple binary heap implementation + * + * Portions Copyright (c) 2012-2021, PostgreSQL Global Development Group + * + * src/include/lib/binaryheap.h + */ + +#ifndef BINARYHEAP_H +#define BINARYHEAP_H + +/* + * For a max-heap, the comparator must return <0 iff a < b, 0 iff a == b, + * and >0 iff a > b. For a min-heap, the conditions are reversed. + */ +typedef int (*binaryheap_comparator) (Datum a, Datum b, void *arg); + +/* + * binaryheap + * + * bh_size how many nodes are currently in "nodes" + * bh_space how many nodes can be stored in "nodes" + * bh_has_heap_property no unordered operations since last heap build + * bh_compare comparison function to define the heap property + * bh_arg user data for comparison function + * bh_nodes variable-length array of "space" nodes + */ +typedef struct binaryheap +{ + int bh_size; + int bh_space; + bool bh_has_heap_property; /* debugging cross-check */ + binaryheap_comparator bh_compare; + void *bh_arg; + Datum bh_nodes[FLEXIBLE_ARRAY_MEMBER]; +} binaryheap; + +extern binaryheap *binaryheap_allocate(int capacity, + binaryheap_comparator compare, + void *arg); +extern void binaryheap_reset(binaryheap *heap); +extern void binaryheap_free(binaryheap *heap); +extern void binaryheap_add_unordered(binaryheap *heap, Datum d); +extern void binaryheap_build(binaryheap *heap); +extern void binaryheap_add(binaryheap *heap, Datum d); +extern Datum binaryheap_first(binaryheap *heap); +extern Datum binaryheap_remove_first(binaryheap *heap); +extern void binaryheap_replace_first(binaryheap *heap, Datum d); + +#define binaryheap_empty(h) ((h)->bh_size == 0) + +#endif /* BINARYHEAP_H */ |