Mon Aug 31 12:30:08 2015

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 /*** MODULEINFO
00027    <support_level>core</support_level>
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  * \brief Add a row of additional storage for the heap.
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 }

Generated on 31 Aug 2015 for Asterisk - The Open Source Telephony Project by  doxygen 1.6.1