5e8a2baeff038a82b59f7dd4ccacbefc212bd88c
[asterisk/asterisk.git] / main / heap.c
1 /*
2  * Asterisk -- An open source telephony toolkit.
3  *
4  * Copyright (C) 2009, Digium, Inc.
5  *
6  * Russell Bryant <russell@digium.com>
7  *
8  * See http://www.asterisk.org for more information about
9  * the Asterisk project. Please do not directly contact
10  * any of the maintainers of this project for assistance;
11  * the project provides a web site, mailing lists and IRC
12  * channels for your use.
13  *
14  * This program is free software, distributed under the terms of
15  * the GNU General Public License Version 2. See the LICENSE file
16  * at the top of the source tree.
17  */
18
19 /*! \file
20  *
21  * \brief Max Heap data structure
22  *
23  * \author Russell Bryant <russell@digium.com>
24  */
25
26 #include "asterisk.h"
27
28 ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
29
30 #include "asterisk/heap.h"
31 #include "asterisk/utils.h"
32 #include "asterisk/cli.h"
33
34 struct ast_heap {
35         ast_rwlock_t lock;
36         ast_heap_cmp_fn cmp_fn;
37         ssize_t index_offset;
38         size_t cur_len;
39         size_t avail_len;
40         void **heap;
41 };
42
43 static inline int left_node(int i)
44 {
45         return 2 * i;
46 }
47
48 static inline int right_node(int i)
49 {
50         return 2 * i + 1;
51 }
52
53 static inline int parent_node(int i)
54 {
55         return i / 2;
56 }
57
58 static inline void *heap_get(struct ast_heap *h, int i)
59 {
60         return h->heap[i - 1];
61 }
62
63 static inline ssize_t get_index(struct ast_heap *h, void *elm)
64 {
65         ssize_t *index;
66
67         if (h->index_offset < 0) {
68                 return -1;
69         }
70
71         index = elm + h->index_offset;
72
73         return *index;
74 }
75
76 static inline void heap_set(struct ast_heap *h, int i, void *elm)
77 {
78         h->heap[i - 1] = elm;
79
80         if (h->index_offset >= 0) {
81                 ssize_t *index = elm + h->index_offset;
82                 *index = i;
83         }
84 }
85
86 int ast_heap_verify(struct ast_heap *h)
87 {
88         unsigned int i;
89
90         for (i = 1; i <= (h->cur_len / 2); i++) {
91                 int l = left_node(i);
92                 int r = right_node(i);
93
94                 if (l <= h->cur_len) {
95                         if (h->cmp_fn(heap_get(h, i), heap_get(h, l)) <= 0) {
96                                 return -1;
97                         }
98                 }
99
100                 if (r <= h->cur_len) {
101                         if (h->cmp_fn(heap_get(h, i), heap_get(h, r)) <= 0) {
102                                 return -1;
103                         }
104                 }
105         }
106
107         return 0;
108 }
109
110 struct ast_heap *ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn,
111                 ssize_t index_offset)
112 {
113         struct ast_heap *h;
114
115         if (!cmp_fn) {
116                 ast_log(LOG_ERROR, "A comparison function must be provided\n");
117                 return NULL;
118         }
119
120         if (!init_height) {
121                 init_height = 8;
122         }
123
124         if (!(h = ast_calloc(1, sizeof(*h)))) {
125                 return NULL;
126         }
127
128         h->cmp_fn = cmp_fn;
129         h->index_offset = index_offset;
130         h->avail_len = (1 << init_height) - 1;
131
132         if (!(h->heap = ast_calloc(1, h->avail_len * sizeof(void *)))) {
133                 ast_free(h);
134                 return NULL;
135         }
136
137         ast_rwlock_init(&h->lock);
138
139         return h;
140 }
141
142 struct ast_heap *ast_heap_destroy(struct ast_heap *h)
143 {
144         ast_free(h->heap);
145         h->heap = NULL;
146
147         ast_rwlock_destroy(&h->lock);
148
149         ast_free(h);
150
151         return NULL;
152 }
153
154 /*!
155  * \brief Add a row of additional storage for the heap.
156  */
157 static int grow_heap(struct ast_heap *h)
158 {
159         h->avail_len = h->avail_len * 2 + 1;
160
161         if (!(h->heap = ast_realloc(h->heap, h->avail_len * sizeof(void *)))) {
162                 h->cur_len = h->avail_len = 0;
163                 return -1;
164         }
165
166         return 0;
167 }
168
169 static inline void heap_swap(struct ast_heap *h, int i, int j)
170 {
171         void *tmp;
172
173         tmp = heap_get(h, i);
174         heap_set(h, i, heap_get(h, j));
175         heap_set(h, j, tmp);
176 }
177
178 static inline void max_heapify(struct ast_heap *h, int i)
179 {
180         for (;;) {
181                 int l = left_node(i);
182                 int r = right_node(i);
183                 int max;
184
185                 if (l <= h->cur_len && h->cmp_fn(heap_get(h, l), heap_get(h, i)) > 0) {
186                         max = l;
187                 } else {
188                         max = i;
189                 }
190
191                 if (r <= h->cur_len && h->cmp_fn(heap_get(h, r), heap_get(h, max)) > 0) {
192                         max = r;
193                 }
194
195                 if (max == i) {
196                         break;
197                 }
198
199                 heap_swap(h, i, max);
200
201                 i = max;
202         }
203 }
204
205 int ast_heap_push(struct ast_heap *h, void *elm)
206 {
207         int i;
208
209         if (h->cur_len == h->avail_len && grow_heap(h)) {
210                 return -1;
211         }
212
213         heap_set(h, ++(h->cur_len), elm);
214
215         for (i = h->cur_len;
216                         i > 1 && h->cmp_fn(heap_get(h, parent_node(i)), heap_get(h, i)) < 0;
217                         i = parent_node(i)) {
218                 heap_swap(h, i, parent_node(i));
219         }
220
221         return 0;
222 }
223
224 static void *_ast_heap_remove(struct ast_heap *h, unsigned int index)
225 {
226         void *ret;
227
228         if (!index || index > h->cur_len) {
229                 return NULL;
230         }
231
232         ret = heap_get(h, index);
233         heap_set(h, index, heap_get(h, (h->cur_len)--));
234
235         max_heapify(h, index);
236
237         return ret;
238 }
239
240 void *ast_heap_remove(struct ast_heap *h, void *elm)
241 {
242         ssize_t i = get_index(h, elm);
243
244         if (i == -1) {
245                 return NULL;
246         }
247
248         return _ast_heap_remove(h, i);
249 }
250
251 void *ast_heap_pop(struct ast_heap *h)
252 {
253         return _ast_heap_remove(h, 1);
254 }
255
256 void *ast_heap_peek(struct ast_heap *h, unsigned int index)
257 {
258         if (!h->cur_len || !index || index > h->cur_len) {
259                 return NULL;
260         }
261
262         return heap_get(h, index);
263 }
264
265 size_t ast_heap_size(struct ast_heap *h)
266 {
267         return h->cur_len;
268 }
269
270 int ast_heap_wrlock(struct ast_heap *h)
271 {
272         return ast_rwlock_wrlock(&h->lock);
273 }
274
275 int ast_heap_rdlock(struct ast_heap *h)
276 {
277         return ast_rwlock_rdlock(&h->lock);
278 }
279
280 int ast_heap_unlock(struct ast_heap *h)
281 {
282         return ast_rwlock_unlock(&h->lock);
283 }
284