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