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
|
/* Licensed under BSD-MIT - see LICENSE file for details */
#include <ccan/heap/heap.h>
/*
* Allocating memory in chunks greater than needed does not yield measurable
* speedups of the test program when linking against glibc 2.15.
*
* When the data array has to be shrunk though, limiting calls to realloc
* does help a little bit (~7% speedup), hence the following parameter.
*/
#define HEAP_MEM_HYSTERESIS 4096
static inline void swap(struct heap *h, size_t i, size_t j)
{
void *foo = h->data[i];
h->data[i] = h->data[j];
h->data[j] = foo;
}
static void __up(struct heap *h, size_t j)
{
size_t i; /* parent */
while (j) {
i = (j - 1) / 2;
if (h->less(h->data[j], h->data[i])) {
swap(h, i, j);
j = i;
} else {
break;
}
}
}
int heap_push(struct heap *h, void *data)
{
if (h->len == h->cap) {
void *m = realloc(h->data, (h->cap + 1) * sizeof(void *));
if (m == NULL)
return -1;
h->data = m;
h->cap++;
}
h->data[h->len++] = data;
__up(h, h->len - 1);
return 0;
}
static void __down(struct heap *h, size_t i)
{
size_t l, r, j; /* left, right, min child */
while (1) {
l = 2 * i + 1;
if (l >= h->len)
break;
r = l + 1;
if (r >= h->len)
j = l;
else
j = h->less(h->data[l], h->data[r]) ? l : r;
if (h->less(h->data[j], h->data[i])) {
swap(h, i, j);
i = j;
} else {
break;
}
}
}
void *heap_pop(struct heap *h)
{
void *ret = h->data[0];
void *m;
swap(h, 0, --h->len);
if (h->len) {
__down(h, 0);
if (h->len == h->cap - HEAP_MEM_HYSTERESIS) {
m = realloc(h->data, h->len * sizeof(void *));
if (m == NULL)
return NULL;
h->data = m;
h->cap = h->len;
}
}
return ret;
}
struct heap *heap_init(heap_less_func_t less)
{
struct heap *heap = calloc(1, sizeof(*heap));
if (heap == NULL)
return NULL;
heap->less = less;
return heap;
}
void heap_ify(struct heap *h, heap_less_func_t less)
{
int i;
if (less)
h->less = less;
for (i = h->len / 2 - 1; i >= 0; i--)
__down(h, i);
}
void heap_free(struct heap *heap)
{
free(heap->data);
free(heap);
}
|
