app_dial: Allow macro/gosub pre-bridge execution to occur on priorities
[asterisk/asterisk.git] / main / heap.c
index 30fb4e4..c04f7a0 100644 (file)
  * \author Russell Bryant <russell@digium.com>
  */
 
+/*** MODULEINFO
+       <support_level>core</support_level>
+ ***/
+
 #include "asterisk.h"
 
 ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
@@ -92,13 +96,13 @@ int ast_heap_verify(struct ast_heap *h)
                int r = right_node(i);
 
                if (l <= h->cur_len) {
-                       if (h->cmp_fn(heap_get(h, i), heap_get(h, l)) <= 0) {
+                       if (h->cmp_fn(heap_get(h, i), heap_get(h, l)) < 0) {
                                return -1;
                        }
                }
 
                if (r <= h->cur_len) {
-                       if (h->cmp_fn(heap_get(h, i), heap_get(h, r)) <= 0) {
+                       if (h->cmp_fn(heap_get(h, i), heap_get(h, r)) < 0) {
                                return -1;
                        }
                }
@@ -177,18 +181,19 @@ static int grow_heap(struct ast_heap *h
 #endif
 )
 {
-       h->avail_len = h->avail_len * 2 + 1;
+       void **new_heap;
+       size_t new_len = h->avail_len * 2 + 1;
 
-       if (!(h->heap =
 #ifdef MALLOC_DEBUG
-                       __ast_realloc(h->heap, h->avail_len * sizeof(void *), file, lineno, func)
+       new_heap = __ast_realloc(h->heap, new_len * sizeof(void *), file, lineno, func);
 #else
-                       ast_realloc(h->heap, h->avail_len * sizeof(void *))
+       new_heap = ast_realloc(h->heap, new_len * sizeof(void *));
 #endif
-               )) {
-               h->cur_len = h->avail_len = 0;
+       if (!new_heap) {
                return -1;
        }
+       h->heap = new_heap;
+       h->avail_len = new_len;
 
        return 0;
 }
@@ -229,14 +234,22 @@ static inline void max_heapify(struct ast_heap *h, int i)
        }
 }
 
+static int bubble_up(struct ast_heap *h, int i)
+{
+       while (i > 1 && h->cmp_fn(heap_get(h, parent_node(i)), heap_get(h, i)) < 0) {
+               heap_swap(h, i, parent_node(i));
+               i = parent_node(i);
+       }
+
+       return i;
+}
+
 #ifdef MALLOC_DEBUG
 int _ast_heap_push(struct ast_heap *h, void *elm, const char *file, int lineno, const char *func)
 #else
 int ast_heap_push(struct ast_heap *h, void *elm)
 #endif
 {
-       int i;
-
        if (h->cur_len == h->avail_len && grow_heap(h
 #ifdef MALLOC_DEBUG
                , file, lineno, func
@@ -247,11 +260,7 @@ int ast_heap_push(struct ast_heap *h, void *elm)
 
        heap_set(h, ++(h->cur_len), elm);
 
-       for (i = h->cur_len;
-                       i > 1 && h->cmp_fn(heap_get(h, parent_node(i)), heap_get(h, i)) < 0;
-                       i = parent_node(i)) {
-               heap_swap(h, i, parent_node(i));
-       }
+       bubble_up(h, h->cur_len);
 
        return 0;
 }
@@ -266,7 +275,7 @@ static void *_ast_heap_remove(struct ast_heap *h, unsigned int index)
 
        ret = heap_get(h, index);
        heap_set(h, index, heap_get(h, (h->cur_len)--));
-
+       index = bubble_up(h, index);
        max_heapify(h, index);
 
        return ret;
@@ -304,15 +313,15 @@ size_t ast_heap_size(struct ast_heap *h)
 
 int __ast_heap_wrlock(struct ast_heap *h, const char *file, const char *func, int line)
 {
-       return __ast_rwlock_wrlock(&h->lock, "&h->lock", file, line, func);
+       return __ast_rwlock_wrlock(file, line, func, &h->lock, "&h->lock");
 }
 
 int __ast_heap_rdlock(struct ast_heap *h, const char *file, const char *func, int line)
 {
-       return __ast_rwlock_rdlock(&h->lock, "&h->lock", file, line, func);
+       return __ast_rwlock_rdlock(file, line, func, &h->lock, "&h->lock");
 }
 
 int __ast_heap_unlock(struct ast_heap *h, const char *file, const char *func, int line)
 {
-       return __ast_rwlock_unlock(&h->lock, "&h->lock", file, line, func);
+       return __ast_rwlock_unlock(file, line, func, &h->lock, "&h->lock");
 }