Wed Aug 18 22:33:52 2010

Asterisk developer's documentation


heap.c

Go to the documentation of this file.
00001 /*
00002  * Asterisk -- An open source telephony toolkit.
00003  *
00004  * Copyright (C) 2009, Digium, Inc.
00005  *
00006  * Russell Bryant <russell@digium.com>
00007  *
00008  * See http://www.asterisk.org for more information about
00009  * the Asterisk project. Please do not directly contact
00010  * any of the maintainers of this project for assistance;
00011  * the project provides a web site, mailing lists and IRC
00012  * channels for your use.
00013  *
00014  * This program is free software, distributed under the terms of
00015  * the GNU General Public License Version 2. See the LICENSE file
00016  * at the top of the source tree.
00017  */
00018 
00019 /*! \file
00020  *
00021  * \brief Max Heap data structure
00022  *
00023  * \author Russell Bryant <russell@digium.com>
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  * \brief Add a row of additional storage for the heap.
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 /* DEBUG_THREADS */
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 /* DEBUG_THREADS */

Generated on Wed Aug 18 22:33:52 2010 for Asterisk - the Open Source PBX by  doxygen 1.4.7