1 /* 2 * binaryheap.h 3 * 4 * A simple binary heap implementation 5 * 6 * Portions Copyright (c) 2012-2018, 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 */ 35 binaryheap_comparator bh_compare; 36 void *bh_arg; 37 Datum bh_nodes[FLEXIBLE_ARRAY_MEMBER]; 38 } binaryheap; 39 40 extern binaryheap *binaryheap_allocate(int capacity, 41 binaryheap_comparator compare, 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); 49 extern Datum binaryheap_remove_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 */ 55