Merge https://github.com/dgibson/ccan
[ccan] / ccan / heap / heap.h
1 /* Licensed under BSD-MIT - see LICENSE file for details */
2 #ifndef CCAN_HEAP_H
3 #define CCAN_HEAP_H
4
5 #include <stdbool.h>
6 #include <stdlib.h>
7
8 typedef bool (*heap_less_func_t)(const void *, const void *);
9
10 /**
11  * struct heap - a simple, generic heap structure
12  * @data: array of pointers to the heap's entries
13  * @less: function to compare heap entries
14  * @cap: capacity of the heap array in @data
15  * @len: number of valid elements in the heap array
16  *
17  * The @less function determines the nature of the heap. If @less is
18  * something akin to 'return a.foo < b.foo', then the heap will be
19  * a min heap. Conversely, a '>' predicate will result in a max heap.
20  *
21  * Elements in the @data array are allocated as needed, hence the need for
22  * @cap and @len.
23  */
24 struct heap {
25         void **data;
26         heap_less_func_t less;
27         size_t cap;
28         size_t len;
29 };
30
31 /**
32  * heap_init - allocate and initialise an empty heap
33  * @less: function to be used to compare heap entries
34  *
35  * Returns a pointer to an initialised heap struct on success, NULL if
36  * the heap could not be allocated.
37  *
38  * See also: HEAP_INIT()
39  */
40 struct heap *heap_init(heap_less_func_t less);
41
42 /**
43  * HEAP_INIT - initialiser for an empty heap
44  * @func: comparison function to be used in the heap
45  *
46  * Explicit initialiser for a heap.
47  *
48  * See also: heap_init()
49  */
50 #define HEAP_INIT(func) { NULL, func, 0, 0 }
51
52 /**
53  * heap_free - free a heap allocated via heap_init()
54  * @heap: the heap to be freed
55  *
56  * Note that this only frees the heap and its internal resources, not
57  * the entries pointed to by it.
58  *
59  * See also: heap_init()
60  */
61 void heap_free(struct heap *heap);
62
63 /**
64  * heap_ify - enforce the heap property based on a new comparison function
65  * @h: heap to be heapified
66  * @less: new comparison function
67  *
68  * Complexity: O(n)
69  */
70 void heap_ify(struct heap *h, heap_less_func_t less);
71
72 /**
73  * heap_push - push a new heap entry
74  * @h: heap to receive the new entry
75  * @data: pointer to the new entry
76  *
77  * Returns 0 on success, -1 on error.
78  *
79  * Complexity: O(log n)
80  *
81  * See also: heap_pop()
82  */
83 int heap_push(struct heap *h, void *data);
84
85 /**
86  * heap_pop - pops the root heap entry
87  * @h: heap to pop the head from
88  *
89  * Returns the root entry of the heap after extracting it, or NULL on error.
90  *
91  * Note: Calling heap_pop() on an empty heap is a bug--don't do it.
92  *
93  * Complexity: O(log n)
94  *
95  * See also: heap_push(), heap_peek()
96  */
97 void *heap_pop(struct heap *h);
98
99 /**
100  * heap_peek - inspect the root entry of a heap
101  * @h: heap whose root entry is to be inspected
102  *
103  * Returns the root entry in the heap, without extracting it from @h.
104  *
105  * Note: Calling heap_peek() on an empty heap is a bug--don't do it.
106  *
107  * See also: heap_pop()
108  */
109 static inline void *heap_peek(const struct heap *h)
110 {
111         return h->data[0];
112 }
113
114 #endif /* CCAN_HEAP_H */