Wed Jan 8 2020 09:49:48

Asterisk developer's documentation


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 ASTERISK_FILE_VERSION(__FILE__, "$Revision: 398757 $")
33 
34 #include "asterisk/heap.h"
35 #include "asterisk/utils.h"
36 #include "asterisk/cli.h"
37 
38 struct ast_heap {
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;
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 
164 {
165  ast_free(h->heap);
166  h->heap = NULL;
167 
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 }
static int grow_heap(struct ast_heap *h)
Add a row of additional storage for the heap.
Definition: heap.c:178
static ssize_t get_index(struct ast_heap *h, void *elm)
Definition: heap.c:67
static void max_heapify(struct ast_heap *h, int i)
Definition: heap.c:210
ast_heap_cmp_fn cmp_fn
Definition: heap.c:40
Asterisk main include file. File version handling, generic pbx functions.
static void * _ast_heap_remove(struct ast_heap *h, unsigned int index)
Definition: heap.c:268
#define ast_rwlock_destroy(rwlock)
Definition: lock.h:199
static void * heap_get(struct ast_heap *h, int i)
Definition: heap.c:62
int __ast_heap_wrlock(struct ast_heap *h, const char *file, const char *func, int line)
Write-Lock a heap.
Definition: heap.c:314
int ast_heap_push(struct ast_heap *h, void *elm)
Push an element on to a heap.
Definition: heap.c:250
int __ast_rwlock_rdlock(const char *filename, int lineno, const char *func, ast_rwlock_t *t, const char *name)
Definition: lock.c:832
Definition: heap.c:38
ast_rwlock_t lock
Definition: heap.c:39
struct ast_heap * ast_heap_destroy(struct ast_heap *h)
Destroy a max heap.
Definition: heap.c:163
void * __ast_calloc(size_t nmemb, size_t size, const char *file, int lineno, const char *func)
size_t avail_len
Definition: heap.c:43
int __ast_rwlock_unlock(const char *filename, int lineno, const char *func, ast_rwlock_t *t, const char *name)
Definition: lock.c:746
void * ast_heap_pop(struct ast_heap *h)
Pop the max element off of the heap.
Definition: heap.c:295
Utility functions.
void ** heap
Definition: heap.c:44
int __ast_heap_unlock(struct ast_heap *h, const char *file, const char *func, int line)
Unlock a heap.
Definition: heap.c:324
int __ast_heap_rdlock(struct ast_heap *h, const char *file, const char *func, int line)
Read-Lock a heap.
Definition: heap.c:319
#define LOG_ERROR
Definition: logger.h:155
int(* ast_heap_cmp_fn)(void *elm1, void *elm2)
Function type for comparing nodes in a heap.
Definition: heap.h:55
#define ast_rwlock_init(rwlock)
wrapper for rwlock with tracking enabled
Definition: lock.h:190
size_t cur_len
Definition: heap.c:42
static int parent_node(int i)
Definition: heap.c:57
void ast_log(int level, const char *file, int line, const char *function, const char *fmt,...)
Used for sending a log message This is the standard logger function. Probably the only way you will i...
Definition: logger.c:1207
void * __ast_realloc(void *ptr, size_t size, const char *file, int lineno, const char *func)
#define ast_free(a)
Definition: astmm.h:97
int __ast_rwlock_wrlock(const char *filename, int lineno, const char *func, ast_rwlock_t *t, const char *name)
Definition: lock.c:959
static int right_node(int i)
Definition: heap.c:52
static void heap_swap(struct ast_heap *h, int i, int j)
Definition: heap.c:201
static int bubble_up(struct ast_heap *h, int i)
Definition: heap.c:237
void * ast_heap_remove(struct ast_heap *h, void *elm)
Remove a specific element from a heap.
Definition: heap.c:284
Structure for rwlock and tracking information.
Definition: lock.h:133
Standard Command Line Interface.
#define ast_calloc(a, b)
Definition: astmm.h:82
size_t ast_heap_size(struct ast_heap *h)
Get the current size of a heap.
Definition: heap.c:309
struct ast_heap * ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn, ssize_t index_offset)
Create a max heap.
Definition: heap.c:118
#define ast_realloc(a, b)
Definition: astmm.h:103
void * ast_heap_peek(struct ast_heap *h, unsigned int index)
Peek at an element on a heap.
Definition: heap.c:300
ssize_t index_offset
Definition: heap.c:41
int ast_heap_verify(struct ast_heap *h)
Verify that a heap has been properly constructed.
Definition: heap.c:90
static int left_node(int i)
Definition: heap.c:47
static void heap_set(struct ast_heap *h, int i, void *elm)
Definition: heap.c:80
#define ASTERISK_FILE_VERSION(file, version)
Register/unregister a source code file with the core.
Definition: asterisk.h:180