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: 261497 $")
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 struct ast_heap *ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn,
00111 ssize_t index_offset)
00112 {
00113 struct ast_heap *h;
00114
00115 if (!cmp_fn) {
00116 ast_log(LOG_ERROR, "A comparison function must be provided\n");
00117 return NULL;
00118 }
00119
00120 if (!init_height) {
00121 init_height = 8;
00122 }
00123
00124 if (!(h = ast_calloc(1, sizeof(*h)))) {
00125 return NULL;
00126 }
00127
00128 h->cmp_fn = cmp_fn;
00129 h->index_offset = index_offset;
00130 h->avail_len = (1 << init_height) - 1;
00131
00132 if (!(h->heap = ast_calloc(1, h->avail_len * sizeof(void *)))) {
00133 ast_free(h);
00134 return NULL;
00135 }
00136
00137 ast_rwlock_init(&h->lock);
00138
00139 return h;
00140 }
00141
00142 struct ast_heap *ast_heap_destroy(struct ast_heap *h)
00143 {
00144 ast_free(h->heap);
00145 h->heap = NULL;
00146
00147 ast_rwlock_destroy(&h->lock);
00148
00149 ast_free(h);
00150
00151 return NULL;
00152 }
00153
00154
00155
00156
00157 static int grow_heap(struct ast_heap *h)
00158 {
00159 h->avail_len = h->avail_len * 2 + 1;
00160
00161 if (!(h->heap = ast_realloc(h->heap, h->avail_len * sizeof(void *)))) {
00162 h->cur_len = h->avail_len = 0;
00163 return -1;
00164 }
00165
00166 return 0;
00167 }
00168
00169 static inline void heap_swap(struct ast_heap *h, int i, int j)
00170 {
00171 void *tmp;
00172
00173 tmp = heap_get(h, i);
00174 heap_set(h, i, heap_get(h, j));
00175 heap_set(h, j, tmp);
00176 }
00177
00178 static inline void max_heapify(struct ast_heap *h, int i)
00179 {
00180 for (;;) {
00181 int l = left_node(i);
00182 int r = right_node(i);
00183 int max;
00184
00185 if (l <= h->cur_len && h->cmp_fn(heap_get(h, l), heap_get(h, i)) > 0) {
00186 max = l;
00187 } else {
00188 max = i;
00189 }
00190
00191 if (r <= h->cur_len && h->cmp_fn(heap_get(h, r), heap_get(h, max)) > 0) {
00192 max = r;
00193 }
00194
00195 if (max == i) {
00196 break;
00197 }
00198
00199 heap_swap(h, i, max);
00200
00201 i = max;
00202 }
00203 }
00204
00205 static int bubble_up(struct ast_heap *h, int i)
00206 {
00207 while (i > 1 && h->cmp_fn(heap_get(h, parent_node(i)), heap_get(h, i)) < 0) {
00208 heap_swap(h, i, parent_node(i));
00209 i = parent_node(i);
00210 }
00211
00212 return i;
00213 }
00214
00215 int ast_heap_push(struct ast_heap *h, void *elm)
00216 {
00217 if (h->cur_len == h->avail_len && grow_heap(h)) {
00218 return -1;
00219 }
00220
00221 heap_set(h, ++(h->cur_len), elm);
00222
00223 bubble_up(h, h->cur_len);
00224
00225 return 0;
00226 }
00227
00228 static void *_ast_heap_remove(struct ast_heap *h, unsigned int index)
00229 {
00230 void *ret;
00231
00232 if (!index || index > h->cur_len) {
00233 return NULL;
00234 }
00235
00236 ret = heap_get(h, index);
00237 heap_set(h, index, heap_get(h, (h->cur_len)--));
00238 index = bubble_up(h, index);
00239 max_heapify(h, index);
00240
00241 return ret;
00242 }
00243
00244 void *ast_heap_remove(struct ast_heap *h, void *elm)
00245 {
00246 ssize_t i = get_index(h, elm);
00247
00248 if (i == -1) {
00249 return NULL;
00250 }
00251
00252 return _ast_heap_remove(h, i);
00253 }
00254
00255 void *ast_heap_pop(struct ast_heap *h)
00256 {
00257 return _ast_heap_remove(h, 1);
00258 }
00259
00260 void *ast_heap_peek(struct ast_heap *h, unsigned int index)
00261 {
00262 if (!h->cur_len || !index || index > h->cur_len) {
00263 return NULL;
00264 }
00265
00266 return heap_get(h, index);
00267 }
00268
00269 size_t ast_heap_size(struct ast_heap *h)
00270 {
00271 return h->cur_len;
00272 }
00273
00274 #ifndef DEBUG_THREADS
00275
00276 int ast_heap_wrlock(struct ast_heap *h)
00277 {
00278 return ast_rwlock_wrlock(&h->lock);
00279 }
00280
00281 int ast_heap_rdlock(struct ast_heap *h)
00282 {
00283 return ast_rwlock_rdlock(&h->lock);
00284 }
00285
00286 int ast_heap_unlock(struct ast_heap *h)
00287 {
00288 return ast_rwlock_unlock(&h->lock);
00289 }
00290
00291 #else
00292
00293 int __ast_heap_wrlock(struct ast_heap *h, const char *file, const char *func, int line)
00294 {
00295 return _ast_rwlock_wrlock(&h->lock, "&h->lock", file, line, func);
00296 }
00297
00298 int __ast_heap_rdlock(struct ast_heap *h, const char *file, const char *func, int line)
00299 {
00300 return _ast_rwlock_rdlock(&h->lock, "&h->lock", file, line, func);
00301 }
00302
00303 int __ast_heap_unlock(struct ast_heap *h, const char *file, const char *func, int line)
00304 {
00305 return _ast_rwlock_unlock(&h->lock, "&h->lock", file, line, func);
00306 }
00307
00308 #endif