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