00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030 #include "asterisk.h"
00031
00032 ASTERISK_FILE_VERSION(__FILE__, "$Revision: 398757 $")
00033
00034 #include "asterisk/heap.h"
00035 #include "asterisk/utils.h"
00036 #include "asterisk/cli.h"
00037
00038 struct ast_heap {
00039 ast_rwlock_t lock;
00040 ast_heap_cmp_fn cmp_fn;
00041 ssize_t index_offset;
00042 size_t cur_len;
00043 size_t avail_len;
00044 void **heap;
00045 };
00046
00047 static inline int left_node(int i)
00048 {
00049 return 2 * i;
00050 }
00051
00052 static inline int right_node(int i)
00053 {
00054 return 2 * i + 1;
00055 }
00056
00057 static inline int parent_node(int i)
00058 {
00059 return i / 2;
00060 }
00061
00062 static inline void *heap_get(struct ast_heap *h, int i)
00063 {
00064 return h->heap[i - 1];
00065 }
00066
00067 static inline ssize_t get_index(struct ast_heap *h, void *elm)
00068 {
00069 ssize_t *index;
00070
00071 if (h->index_offset < 0) {
00072 return -1;
00073 }
00074
00075 index = elm + h->index_offset;
00076
00077 return *index;
00078 }
00079
00080 static inline void heap_set(struct ast_heap *h, int i, void *elm)
00081 {
00082 h->heap[i - 1] = elm;
00083
00084 if (h->index_offset >= 0) {
00085 ssize_t *index = elm + h->index_offset;
00086 *index = i;
00087 }
00088 }
00089
00090 int ast_heap_verify(struct ast_heap *h)
00091 {
00092 unsigned int i;
00093
00094 for (i = 1; i <= (h->cur_len / 2); i++) {
00095 int l = left_node(i);
00096 int r = right_node(i);
00097
00098 if (l <= h->cur_len) {
00099 if (h->cmp_fn(heap_get(h, i), heap_get(h, l)) < 0) {
00100 return -1;
00101 }
00102 }
00103
00104 if (r <= h->cur_len) {
00105 if (h->cmp_fn(heap_get(h, i), heap_get(h, r)) < 0) {
00106 return -1;
00107 }
00108 }
00109 }
00110
00111 return 0;
00112 }
00113
00114 #ifdef MALLOC_DEBUG
00115 struct ast_heap *_ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn,
00116 ssize_t index_offset, const char *file, int lineno, const char *func)
00117 #else
00118 struct ast_heap *ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn,
00119 ssize_t index_offset)
00120 #endif
00121 {
00122 struct ast_heap *h;
00123
00124 if (!cmp_fn) {
00125 ast_log(LOG_ERROR, "A comparison function must be provided\n");
00126 return NULL;
00127 }
00128
00129 if (!init_height) {
00130 init_height = 8;
00131 }
00132
00133 if (!(h =
00134 #ifdef MALLOC_DEBUG
00135 __ast_calloc(1, sizeof(*h), file, lineno, func)
00136 #else
00137 ast_calloc(1, sizeof(*h))
00138 #endif
00139 )) {
00140 return NULL;
00141 }
00142
00143 h->cmp_fn = cmp_fn;
00144 h->index_offset = index_offset;
00145 h->avail_len = (1 << init_height) - 1;
00146
00147 if (!(h->heap =
00148 #ifdef MALLOC_DEBUG
00149 __ast_calloc(1, h->avail_len * sizeof(void *), file, lineno, func)
00150 #else
00151 ast_calloc(1, h->avail_len * sizeof(void *))
00152 #endif
00153 )) {
00154 ast_free(h);
00155 return NULL;
00156 }
00157
00158 ast_rwlock_init(&h->lock);
00159
00160 return h;
00161 }
00162
00163 struct ast_heap *ast_heap_destroy(struct ast_heap *h)
00164 {
00165 ast_free(h->heap);
00166 h->heap = NULL;
00167
00168 ast_rwlock_destroy(&h->lock);
00169
00170 ast_free(h);
00171
00172 return NULL;
00173 }
00174
00175
00176
00177
00178 static int grow_heap(struct ast_heap *h
00179 #ifdef MALLOC_DEBUG
00180 , const char *file, int lineno, const char *func
00181 #endif
00182 )
00183 {
00184 void **new_heap;
00185 size_t new_len = h->avail_len * 2 + 1;
00186
00187 #ifdef MALLOC_DEBUG
00188 new_heap = __ast_realloc(h->heap, new_len * sizeof(void *), file, lineno, func);
00189 #else
00190 new_heap = ast_realloc(h->heap, new_len * sizeof(void *));
00191 #endif
00192 if (!new_heap) {
00193 return -1;
00194 }
00195 h->heap = new_heap;
00196 h->avail_len = new_len;
00197
00198 return 0;
00199 }
00200
00201 static inline void heap_swap(struct ast_heap *h, int i, int j)
00202 {
00203 void *tmp;
00204
00205 tmp = heap_get(h, i);
00206 heap_set(h, i, heap_get(h, j));
00207 heap_set(h, j, tmp);
00208 }
00209
00210 static inline void max_heapify(struct ast_heap *h, int i)
00211 {
00212 for (;;) {
00213 int l = left_node(i);
00214 int r = right_node(i);
00215 int max;
00216
00217 if (l <= h->cur_len && h->cmp_fn(heap_get(h, l), heap_get(h, i)) > 0) {
00218 max = l;
00219 } else {
00220 max = i;
00221 }
00222
00223 if (r <= h->cur_len && h->cmp_fn(heap_get(h, r), heap_get(h, max)) > 0) {
00224 max = r;
00225 }
00226
00227 if (max == i) {
00228 break;
00229 }
00230
00231 heap_swap(h, i, max);
00232
00233 i = max;
00234 }
00235 }
00236
00237 static int bubble_up(struct ast_heap *h, int i)
00238 {
00239 while (i > 1 && h->cmp_fn(heap_get(h, parent_node(i)), heap_get(h, i)) < 0) {
00240 heap_swap(h, i, parent_node(i));
00241 i = parent_node(i);
00242 }
00243
00244 return i;
00245 }
00246
00247 #ifdef MALLOC_DEBUG
00248 int _ast_heap_push(struct ast_heap *h, void *elm, const char *file, int lineno, const char *func)
00249 #else
00250 int ast_heap_push(struct ast_heap *h, void *elm)
00251 #endif
00252 {
00253 if (h->cur_len == h->avail_len && grow_heap(h
00254 #ifdef MALLOC_DEBUG
00255 , file, lineno, func
00256 #endif
00257 )) {
00258 return -1;
00259 }
00260
00261 heap_set(h, ++(h->cur_len), elm);
00262
00263 bubble_up(h, h->cur_len);
00264
00265 return 0;
00266 }
00267
00268 static void *_ast_heap_remove(struct ast_heap *h, unsigned int index)
00269 {
00270 void *ret;
00271
00272 if (!index || index > h->cur_len) {
00273 return NULL;
00274 }
00275
00276 ret = heap_get(h, index);
00277 heap_set(h, index, heap_get(h, (h->cur_len)--));
00278 index = bubble_up(h, index);
00279 max_heapify(h, index);
00280
00281 return ret;
00282 }
00283
00284 void *ast_heap_remove(struct ast_heap *h, void *elm)
00285 {
00286 ssize_t i = get_index(h, elm);
00287
00288 if (i == -1) {
00289 return NULL;
00290 }
00291
00292 return _ast_heap_remove(h, i);
00293 }
00294
00295 void *ast_heap_pop(struct ast_heap *h)
00296 {
00297 return _ast_heap_remove(h, 1);
00298 }
00299
00300 void *ast_heap_peek(struct ast_heap *h, unsigned int index)
00301 {
00302 if (!h->cur_len || !index || index > h->cur_len) {
00303 return NULL;
00304 }
00305
00306 return heap_get(h, index);
00307 }
00308
00309 size_t ast_heap_size(struct ast_heap *h)
00310 {
00311 return h->cur_len;
00312 }
00313
00314 int __ast_heap_wrlock(struct ast_heap *h, const char *file, const char *func, int line)
00315 {
00316 return __ast_rwlock_wrlock(file, line, func, &h->lock, "&h->lock");
00317 }
00318
00319 int __ast_heap_rdlock(struct ast_heap *h, const char *file, const char *func, int line)
00320 {
00321 return __ast_rwlock_rdlock(file, line, func, &h->lock, "&h->lock");
00322 }
00323
00324 int __ast_heap_unlock(struct ast_heap *h, const char *file, const char *func, int line)
00325 {
00326 return __ast_rwlock_unlock(file, line, func, &h->lock, "&h->lock");
00327 }