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