ARI: Add ability to raise arbitrary User Events
[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 /*** MODULEINFO
27         <support_level>core</support_level>
28  ***/
29
30 #include "asterisk.h"
31
32 ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
33
34 #include "asterisk/heap.h"
35 #include "asterisk/utils.h"
36 #include "asterisk/cli.h"
37
38 struct ast_heap {
39         ast_rwlock_t lock;
40         ast_heap_cmp_fn cmp_fn;
41         ssize_t index_offset;
42         size_t cur_len;
43         size_t avail_len;
44         void **heap;
45 };
46
47 static inline int left_node(int i)
48 {
49         return 2 * i;
50 }
51
52 static inline int right_node(int i)
53 {
54         return 2 * i + 1;
55 }
56
57 static inline int parent_node(int i)
58 {
59         return i / 2;
60 }
61
62 static inline void *heap_get(struct ast_heap *h, int i)
63 {
64         return h->heap[i - 1];
65 }
66
67 static inline ssize_t get_index(struct ast_heap *h, void *elm)
68 {
69         ssize_t *index;
70
71         if (h->index_offset < 0) {
72                 return -1;
73         }
74
75         index = elm + h->index_offset;
76
77         return *index;
78 }
79
80 static inline void heap_set(struct ast_heap *h, int i, void *elm)
81 {
82         h->heap[i - 1] = elm;
83
84         if (h->index_offset >= 0) {
85                 ssize_t *index = elm + h->index_offset;
86                 *index = i;
87         }
88 }
89
90 int ast_heap_verify(struct ast_heap *h)
91 {
92         unsigned int i;
93
94         for (i = 1; i <= (h->cur_len / 2); i++) {
95                 int l = left_node(i);
96                 int r = right_node(i);
97
98                 if (l <= h->cur_len) {
99                         if (h->cmp_fn(heap_get(h, i), heap_get(h, l)) < 0) {
100                                 return -1;
101                         }
102                 }
103
104                 if (r <= h->cur_len) {
105                         if (h->cmp_fn(heap_get(h, i), heap_get(h, r)) < 0) {
106                                 return -1;
107                         }
108                 }
109         }
110
111         return 0;
112 }
113
114 #ifdef MALLOC_DEBUG
115 struct ast_heap *_ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn,
116                 ssize_t index_offset, const char *file, int lineno, const char *func)
117 #else
118 struct ast_heap *ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn,
119                 ssize_t index_offset)
120 #endif
121 {
122         struct ast_heap *h;
123
124         if (!cmp_fn) {
125                 ast_log(LOG_ERROR, "A comparison function must be provided\n");
126                 return NULL;
127         }
128
129         if (!init_height) {
130                 init_height = 8;
131         }
132
133         if (!(h =
134 #ifdef MALLOC_DEBUG
135                         __ast_calloc(1, sizeof(*h), file, lineno, func)
136 #else
137                         ast_calloc(1, sizeof(*h))
138 #endif
139                 )) {
140                 return NULL;
141         }
142
143         h->cmp_fn = cmp_fn;
144         h->index_offset = index_offset;
145         h->avail_len = (1 << init_height) - 1;
146
147         if (!(h->heap =
148 #ifdef MALLOC_DEBUG
149                         __ast_calloc(1, h->avail_len * sizeof(void *), file, lineno, func)
150 #else
151                         ast_calloc(1, h->avail_len * sizeof(void *))
152 #endif
153                 )) {
154                 ast_free(h);
155                 return NULL;
156         }
157
158         ast_rwlock_init(&h->lock);
159
160         return h;
161 }
162
163 struct ast_heap *ast_heap_destroy(struct ast_heap *h)
164 {
165         ast_free(h->heap);
166         h->heap = NULL;
167
168         ast_rwlock_destroy(&h->lock);
169
170         ast_free(h);
171
172         return NULL;
173 }
174
175 /*!
176  * \brief Add a row of additional storage for the heap.
177  */
178 static int grow_heap(struct ast_heap *h
179 #ifdef MALLOC_DEBUG
180 , const char *file, int lineno, const char *func
181 #endif
182 )
183 {
184         void **new_heap;
185         size_t new_len = h->avail_len * 2 + 1;
186
187 #ifdef MALLOC_DEBUG
188         new_heap = __ast_realloc(h->heap, new_len * sizeof(void *), file, lineno, func);
189 #else
190         new_heap = ast_realloc(h->heap, new_len * sizeof(void *));
191 #endif
192         if (!new_heap) {
193                 return -1;
194         }
195         h->heap = new_heap;
196         h->avail_len = new_len;
197
198         return 0;
199 }
200
201 static inline void heap_swap(struct ast_heap *h, int i, int j)
202 {
203         void *tmp;
204
205         tmp = heap_get(h, i);
206         heap_set(h, i, heap_get(h, j));
207         heap_set(h, j, tmp);
208 }
209
210 static inline void max_heapify(struct ast_heap *h, int i)
211 {
212         for (;;) {
213                 int l = left_node(i);
214                 int r = right_node(i);
215                 int max;
216
217                 if (l <= h->cur_len && h->cmp_fn(heap_get(h, l), heap_get(h, i)) > 0) {
218                         max = l;
219                 } else {
220                         max = i;
221                 }
222
223                 if (r <= h->cur_len && h->cmp_fn(heap_get(h, r), heap_get(h, max)) > 0) {
224                         max = r;
225                 }
226
227                 if (max == i) {
228                         break;
229                 }
230
231                 heap_swap(h, i, max);
232
233                 i = max;
234         }
235 }
236
237 static int bubble_up(struct ast_heap *h, int i)
238 {
239         while (i > 1 && h->cmp_fn(heap_get(h, parent_node(i)), heap_get(h, i)) < 0) {
240                 heap_swap(h, i, parent_node(i));
241                 i = parent_node(i);
242         }
243
244         return i;
245 }
246
247 #ifdef MALLOC_DEBUG
248 int _ast_heap_push(struct ast_heap *h, void *elm, const char *file, int lineno, const char *func)
249 #else
250 int ast_heap_push(struct ast_heap *h, void *elm)
251 #endif
252 {
253         if (h->cur_len == h->avail_len && grow_heap(h
254 #ifdef MALLOC_DEBUG
255                 , file, lineno, func
256 #endif
257                 )) {
258                 return -1;
259         }
260
261         heap_set(h, ++(h->cur_len), elm);
262
263         bubble_up(h, h->cur_len);
264
265         return 0;
266 }
267
268 static void *_ast_heap_remove(struct ast_heap *h, unsigned int index)
269 {
270         void *ret;
271
272         if (!index || index > h->cur_len) {
273                 return NULL;
274         }
275
276         ret = heap_get(h, index);
277         heap_set(h, index, heap_get(h, (h->cur_len)--));
278         index = bubble_up(h, index);
279         max_heapify(h, index);
280
281         return ret;
282 }
283
284 void *ast_heap_remove(struct ast_heap *h, void *elm)
285 {
286         ssize_t i = get_index(h, elm);
287
288         if (i == -1) {
289                 return NULL;
290         }
291
292         return _ast_heap_remove(h, i);
293 }
294
295 void *ast_heap_pop(struct ast_heap *h)
296 {
297         return _ast_heap_remove(h, 1);
298 }
299
300 void *ast_heap_peek(struct ast_heap *h, unsigned int index)
301 {
302         if (!h->cur_len || !index || index > h->cur_len) {
303                 return NULL;
304         }
305
306         return heap_get(h, index);
307 }
308
309 size_t ast_heap_size(struct ast_heap *h)
310 {
311         return h->cur_len;
312 }
313
314 int __ast_heap_wrlock(struct ast_heap *h, const char *file, const char *func, int line)
315 {
316         return __ast_rwlock_wrlock(file, line, func, &h->lock, "&h->lock");
317 }
318
319 int __ast_heap_rdlock(struct ast_heap *h, const char *file, const char *func, int line)
320 {
321         return __ast_rwlock_rdlock(file, line, func, &h->lock, "&h->lock");
322 }
323
324 int __ast_heap_unlock(struct ast_heap *h, const char *file, const char *func, int line)
325 {
326         return __ast_rwlock_unlock(file, line, func, &h->lock, "&h->lock");
327 }