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