Merge "stasis: No need to keep a stasis type ref in a stasis msg or cache object."
[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 struct ast_heap *_ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn,
113         ssize_t index_offset, const char *file, int lineno, const char *func)
114 {
115         struct ast_heap *h;
116
117         if (!cmp_fn) {
118                 ast_log(LOG_ERROR, "A comparison function must be provided\n");
119                 return NULL;
120         }
121
122         if (!init_height) {
123                 init_height = 8;
124         }
125
126         h = __ast_calloc(1, sizeof(*h), file, lineno, func);
127         if (!h) {
128                 return NULL;
129         }
130
131         h->cmp_fn = cmp_fn;
132         h->index_offset = index_offset;
133         h->avail_len = (1 << init_height) - 1;
134
135         h->heap = __ast_malloc(h->avail_len * sizeof(void *), file, lineno, func);
136         if (!h->heap) {
137                 ast_free(h);
138                 return NULL;
139         }
140
141         ast_rwlock_init(&h->lock);
142
143         return h;
144 }
145
146 struct ast_heap *ast_heap_destroy(struct ast_heap *h)
147 {
148         ast_free(h->heap);
149         h->heap = NULL;
150
151         ast_rwlock_destroy(&h->lock);
152
153         ast_free(h);
154
155         return NULL;
156 }
157
158 /*!
159  * \brief Add a row of additional storage for the heap.
160  */
161 static int grow_heap(struct ast_heap *h, const char *file, int lineno, const char *func)
162 {
163         void **new_heap;
164         size_t new_len = h->avail_len * 2 + 1;
165
166         new_heap = __ast_realloc(h->heap, new_len * sizeof(void *), file, lineno, func);
167         if (!new_heap) {
168                 return -1;
169         }
170         h->heap = new_heap;
171         h->avail_len = new_len;
172
173         return 0;
174 }
175
176 static inline void heap_swap(struct ast_heap *h, int i, int j)
177 {
178         void *tmp;
179
180         tmp = heap_get(h, i);
181         heap_set(h, i, heap_get(h, j));
182         heap_set(h, j, tmp);
183 }
184
185 static inline void max_heapify(struct ast_heap *h, int i)
186 {
187         for (;;) {
188                 int l = left_node(i);
189                 int r = right_node(i);
190                 int max;
191
192                 if (l <= h->cur_len && h->cmp_fn(heap_get(h, l), heap_get(h, i)) > 0) {
193                         max = l;
194                 } else {
195                         max = i;
196                 }
197
198                 if (r <= h->cur_len && h->cmp_fn(heap_get(h, r), heap_get(h, max)) > 0) {
199                         max = r;
200                 }
201
202                 if (max == i) {
203                         break;
204                 }
205
206                 heap_swap(h, i, max);
207
208                 i = max;
209         }
210 }
211
212 static int bubble_up(struct ast_heap *h, int i)
213 {
214         while (i > 1 && h->cmp_fn(heap_get(h, parent_node(i)), heap_get(h, i)) < 0) {
215                 heap_swap(h, i, parent_node(i));
216                 i = parent_node(i);
217         }
218
219         return i;
220 }
221
222 int _ast_heap_push(struct ast_heap *h, void *elm, const char *file, int lineno, const char *func)
223 {
224         if (h->cur_len == h->avail_len && grow_heap(h, file, lineno, func)) {
225                 return -1;
226         }
227
228         heap_set(h, ++(h->cur_len), elm);
229
230         bubble_up(h, h->cur_len);
231
232         return 0;
233 }
234
235 static void *_ast_heap_remove(struct ast_heap *h, unsigned int index)
236 {
237         void *ret;
238
239         if (!index || index > h->cur_len) {
240                 return NULL;
241         }
242
243         ret = heap_get(h, index);
244         heap_set(h, index, heap_get(h, (h->cur_len)--));
245         index = bubble_up(h, index);
246         max_heapify(h, index);
247
248         return ret;
249 }
250
251 void *ast_heap_remove(struct ast_heap *h, void *elm)
252 {
253         ssize_t i = get_index(h, elm);
254
255         if (i == -1) {
256                 return NULL;
257         }
258
259         return _ast_heap_remove(h, i);
260 }
261
262 void *ast_heap_pop(struct ast_heap *h)
263 {
264         return _ast_heap_remove(h, 1);
265 }
266
267 void *ast_heap_peek(struct ast_heap *h, unsigned int index)
268 {
269         if (!h->cur_len || !index || index > h->cur_len) {
270                 return NULL;
271         }
272
273         return heap_get(h, index);
274 }
275
276 size_t ast_heap_size(struct ast_heap *h)
277 {
278         return h->cur_len;
279 }
280
281 int __ast_heap_wrlock(struct ast_heap *h, const char *file, const char *func, int line)
282 {
283         return __ast_rwlock_wrlock(file, line, func, &h->lock, "&h->lock");
284 }
285
286 int __ast_heap_rdlock(struct ast_heap *h, const char *file, const char *func, int line)
287 {
288         return __ast_rwlock_rdlock(file, line, func, &h->lock, "&h->lock");
289 }
290
291 int __ast_heap_unlock(struct ast_heap *h, const char *file, const char *func, int line)
292 {
293         return __ast_rwlock_unlock(file, line, func, &h->lock, "&h->lock");
294 }