Thu Apr 28 2011 16:56:47

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: 261498 $")
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  * \brief Add a row of additional storage for the heap.
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 #ifndef DEBUG_THREADS
00310 
00311 int ast_heap_wrlock(struct ast_heap *h)
00312 {
00313    return ast_rwlock_wrlock(&h->lock);
00314 }
00315 
00316 int ast_heap_rdlock(struct ast_heap *h)
00317 {
00318    return ast_rwlock_rdlock(&h->lock);
00319 }
00320 
00321 int ast_heap_unlock(struct ast_heap *h)
00322 {
00323    return ast_rwlock_unlock(&h->lock);
00324 }
00325 
00326 #else /* DEBUG_THREADS */
00327 
00328 int __ast_heap_wrlock(struct ast_heap *h, const char *file, const char *func, int line)
00329 {
00330    return _ast_rwlock_wrlock(&h->lock, "&h->lock", file, line, func);
00331 }
00332 
00333 int __ast_heap_rdlock(struct ast_heap *h, const char *file, const char *func, int line)
00334 {
00335    return _ast_rwlock_rdlock(&h->lock, "&h->lock", file, line, func);
00336 }
00337 
00338 int __ast_heap_unlock(struct ast_heap *h, const char *file, const char *func, int line)
00339 {
00340    return _ast_rwlock_unlock(&h->lock, "&h->lock", file, line, func);
00341 }
00342 
00343 #endif /* DEBUG_THREADS */