Asterisk - The Open Source Telephony Project  GIT-master-44aef04
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 
36 struct ast_heap {
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;
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 
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  */
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 }
void * ast_heap_remove(struct ast_heap *h, void *elm)
Remove a specific element from a heap.
Definition: heap.c:251
static ssize_t get_index(struct ast_heap *h, void *elm)
Definition: heap.c:65
static void max_heapify(struct ast_heap *h, int i)
Definition: heap.c:185
ast_heap_cmp_fn cmp_fn
Definition: heap.c:38
int __ast_heap_unlock(struct ast_heap *h, const char *file, const char *func, int line)
Unlock a heap.
Definition: heap.c:291
void * __ast_calloc(size_t nmemb, size_t size, const char *file, int lineno, const char *func) attribute_malloc
Definition: astmm.c:1635
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:235
#define ast_rwlock_destroy(rwlock)
Definition: lock.h:231
static int tmp()
Definition: bt_open.c:389
static void * heap_get(struct ast_heap *h, int i)
Definition: heap.c:60
int __ast_rwlock_rdlock(const char *filename, int lineno, const char *func, ast_rwlock_t *t, const char *name)
Definition: lock.c:819
int __ast_heap_rdlock(struct ast_heap *h, const char *file, const char *func, int line)
Read-Lock a heap.
Definition: heap.c:286
Definition: heap.c:36
ast_rwlock_t lock
Definition: heap.c:37
size_t avail_len
Definition: heap.c:41
#define NULL
Definition: resample.c:96
int __ast_rwlock_unlock(const char *filename, int lineno, const char *func, ast_rwlock_t *t, const char *name)
Definition: lock.c:748
Utility functions.
void ** heap
Definition: heap.c:42
Max Heap data structure.
#define ast_log
Definition: astobj2.c:42
int(* ast_heap_cmp_fn)(void *elm1, void *elm2)
Function type for comparing nodes in a heap.
Definition: heap.h:55
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
size_t ast_heap_size(struct ast_heap *h)
Get the current size of a heap.
Definition: heap.c:276
#define LOG_ERROR
Definition: logger.h:285
void * ast_heap_peek(struct ast_heap *h, unsigned int index)
Peek at an element on a heap.
Definition: heap.c:267
#define ast_rwlock_init(rwlock)
wrapper for rwlock with tracking enabled
Definition: lock.h:222
size_t cur_len
Definition: heap.c:40
static int parent_node(int i)
Definition: heap.c:55
int ast_heap_verify(struct ast_heap *h)
Verify that a heap has been properly constructed.
Definition: heap.c:88
void * __ast_realloc(void *ptr, size_t size, const char *file, int lineno, const char *func)
Definition: astmm.c:1672
#define ast_free(a)
Definition: astmm.h:182
void * ast_heap_pop(struct ast_heap *h)
Pop the max element off of the heap.
Definition: heap.c:262
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)
Create a max heap.
Definition: heap.c:112
int __ast_rwlock_wrlock(const char *filename, int lineno, const char *func, ast_rwlock_t *t, const char *name)
Definition: lock.c:917
static int right_node(int i)
Definition: heap.c:50
static void heap_swap(struct ast_heap *h, int i, int j)
Definition: heap.c:176
static int bubble_up(struct ast_heap *h, int i)
Definition: heap.c:212
Structure for rwlock and tracking information.
Definition: lock.h:156
Standard Command Line Interface.
int _ast_heap_push(struct ast_heap *h, void *elm, const char *file, int lineno, const char *func)
Push an element on to a heap.
Definition: heap.c:222
ssize_t index_offset
Definition: heap.c:39
static int left_node(int i)
Definition: heap.c:45
static void heap_set(struct ast_heap *h, int i, void *elm)
Definition: heap.c:78
int __ast_heap_wrlock(struct ast_heap *h, const char *file, const char *func, int line)
Write-Lock a heap.
Definition: heap.c:281
void * __ast_malloc(size_t size, const char *file, int lineno, const char *func) attribute_malloc
Definition: astmm.c:1660
#define max(a, b)
Definition: f2c.h:198