Asterisk - The Open Source Telephony Project GIT-master-85241bd
heap.c
Go to the documentation of this file.
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
36struct ast_heap {
39 ssize_t index_offset;
40 size_t cur_len;
41 size_t avail_len;
42 void **heap;
43};
44
45static inline int left_node(int i)
46{
47 return 2 * i;
48}
49
50static inline int right_node(int i)
51{
52 return 2 * i + 1;
53}
54
55static inline int parent_node(int i)
56{
57 return i / 2;
58}
59
60static inline void *heap_get(struct ast_heap *h, int i)
61{
62 return h->heap[i - 1];
63}
64
65static 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
78static 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
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
112struct 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;
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
142
143 return h;
144}
145
147{
148 ast_free(h->heap);
149 h->heap = NULL;
150
152
153 ast_free(h);
154
155 return NULL;
156}
157
158/*!
159 * \brief Add a row of additional storage for the heap.
160 */
161static 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
176static 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
185static 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
212static 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
222int _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
235static 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
251void *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
262void *ast_heap_pop(struct ast_heap *h)
263{
264 return _ast_heap_remove(h, 1);
265}
266
267void *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
276size_t ast_heap_size(struct ast_heap *h)
277{
278 return h->cur_len;
279}
280
281int __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
286int __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
291int __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}
Asterisk main include file. File version handling, generic pbx functions.
void * __ast_malloc(size_t size, const char *file, int lineno, const char *func) attribute_malloc
Definition: astmm.c:1628
#define ast_free(a)
Definition: astmm.h:180
void * __ast_realloc(void *ptr, size_t size, const char *file, int lineno, const char *func)
Definition: astmm.c:1640
void * __ast_calloc(size_t nmemb, size_t size, const char *file, int lineno, const char *func) attribute_malloc
Definition: astmm.c:1603
#define ast_log
Definition: astobj2.c:42
static int tmp()
Definition: bt_open.c:389
Standard Command Line Interface.
#define max(a, b)
Definition: f2c.h:198
static void heap_set(struct ast_heap *h, int i, void *elm)
Definition: heap.c:78
int ast_heap_verify(struct ast_heap *h)
Verify that a heap has been properly constructed.
Definition: heap.c:88
struct ast_heap * _ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn, ssize_t index_offset, const char *file, int lineno, const char *func)
Definition: heap.c:112
static void max_heapify(struct ast_heap *h, int i)
Definition: heap.c:185
static int bubble_up(struct ast_heap *h, int i)
Definition: heap.c:212
static void heap_swap(struct ast_heap *h, int i, int j)
Definition: heap.c:176
struct ast_heap * ast_heap_destroy(struct ast_heap *h)
Destroy a max heap.
Definition: heap.c:146
static int grow_heap(struct ast_heap *h, const char *file, int lineno, const char *func)
Add a row of additional storage for the heap.
Definition: heap.c:161
static ssize_t get_index(struct ast_heap *h, void *elm)
Definition: heap.c:65
void * ast_heap_pop(struct ast_heap *h)
Pop the max element off of the heap.
Definition: heap.c:262
static int left_node(int i)
Definition: heap.c:45
void * ast_heap_remove(struct ast_heap *h, void *elm)
Remove a specific element from a heap.
Definition: heap.c:251
int __ast_heap_rdlock(struct ast_heap *h, const char *file, const char *func, int line)
Read-Lock a heap.
Definition: heap.c:286
static void * heap_get(struct ast_heap *h, int i)
Definition: heap.c:60
static void * _ast_heap_remove(struct ast_heap *h, unsigned int index)
Definition: heap.c:235
int __ast_heap_unlock(struct ast_heap *h, const char *file, const char *func, int line)
Unlock a heap.
Definition: heap.c:291
size_t ast_heap_size(struct ast_heap *h)
Get the current size of a heap.
Definition: heap.c:276
static int right_node(int i)
Definition: heap.c:50
int __ast_heap_wrlock(struct ast_heap *h, const char *file, const char *func, int line)
Write-Lock a heap.
Definition: heap.c:281
static int parent_node(int i)
Definition: heap.c:55
int _ast_heap_push(struct ast_heap *h, void *elm, const char *file, int lineno, const char *func)
Definition: heap.c:222
void * ast_heap_peek(struct ast_heap *h, unsigned int index)
Peek at an element on a heap.
Definition: heap.c:267
Max Heap data structure.
int(* ast_heap_cmp_fn)(void *elm1, void *elm2)
Function type for comparing nodes in a heap.
Definition: heap.h:55
#define LOG_ERROR
int __ast_rwlock_wrlock(const char *filename, int lineno, const char *func, ast_rwlock_t *t, const char *name)
Definition: lock.c:952
int __ast_rwlock_unlock(const char *filename, int lineno, const char *func, ast_rwlock_t *t, const char *name)
Definition: lock.c:777
#define ast_rwlock_init(rwlock)
wrapper for rwlock with tracking enabled
Definition: lock.h:224
#define ast_rwlock_destroy(rwlock)
Definition: lock.h:233
int __ast_rwlock_rdlock(const char *filename, int lineno, const char *func, ast_rwlock_t *t, const char *name)
Definition: lock.c:848
#define NULL
Definition: resample.c:96
Definition: heap.c:36
ssize_t index_offset
Definition: heap.c:39
void ** heap
Definition: heap.c:42
size_t cur_len
Definition: heap.c:40
size_t avail_len
Definition: heap.c:41
ast_rwlock_t lock
Definition: heap.c:37
ast_heap_cmp_fn cmp_fn
Definition: heap.c:38
Structure for rwlock and tracking information.
Definition: lock.h:157
Utility functions.