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. When in doubt,
92 * check heap->len. See heap_peek()'s documentation for an example.
93 *
94 * Complexity: O(log n)
95 *
96 * See also: heap_push(), heap_peek()
97 */
98 void *heap_pop(struct heap *h);
99
100 /**
101 * heap_peek - inspect the root entry of a heap
102 * @h: heap whose root entry is to be inspected
103 *
104 * Returns the root entry in the heap, without extracting it from @h.
105 *
106 * Note: Calling heap_peek() on an empty heap is a bug; check the heap's
107 * number of items and act accordingly, as in the example below.
108 *
109 * See also: heap_pop()
110 *
111 * Example:
112 * static inline void *heap_peek_safe(const struct heap *h)
113 * {
114 * return h->len ? heap_peek(h) : NULL;
115 * }
116 */
heap_peek(const struct heap * h)117 static inline void *heap_peek(const struct heap *h)
118 {
119 return h->data[0];
120 }
121
122 #endif /* CCAN_HEAP_H */
123