app_dial: Allow macro/gosub pre-bridge execution to occur on priorities
[asterisk/asterisk.git] / main / heap.c
index 5e8a2ba..c04f7a0 100644 (file)
  * \author Russell Bryant <russell@digium.com>
  */
 
  * \author Russell Bryant <russell@digium.com>
  */
 
+/*** MODULEINFO
+       <support_level>core</support_level>
+ ***/
+
 #include "asterisk.h"
 
 ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
 #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) {
                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) {
                                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;
                        }
                }
                                return -1;
                        }
                }
@@ -107,8 +111,13 @@ int ast_heap_verify(struct ast_heap *h)
        return 0;
 }
 
        return 0;
 }
 
+#ifdef MALLOC_DEBUG
+struct ast_heap *_ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn,
+               ssize_t index_offset, const char *file, int lineno, const char *func)
+#else
 struct ast_heap *ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn,
                ssize_t index_offset)
 struct ast_heap *ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_fn,
                ssize_t index_offset)
+#endif
 {
        struct ast_heap *h;
 
 {
        struct ast_heap *h;
 
@@ -121,7 +130,13 @@ struct ast_heap *ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_f
                init_height = 8;
        }
 
                init_height = 8;
        }
 
-       if (!(h = ast_calloc(1, sizeof(*h)))) {
+       if (!(h =
+#ifdef MALLOC_DEBUG
+                       __ast_calloc(1, sizeof(*h), file, lineno, func)
+#else
+                       ast_calloc(1, sizeof(*h))
+#endif
+               )) {
                return NULL;
        }
 
                return NULL;
        }
 
@@ -129,7 +144,13 @@ struct ast_heap *ast_heap_create(unsigned int init_height, ast_heap_cmp_fn cmp_f
        h->index_offset = index_offset;
        h->avail_len = (1 << init_height) - 1;
 
        h->index_offset = index_offset;
        h->avail_len = (1 << init_height) - 1;
 
-       if (!(h->heap = ast_calloc(1, h->avail_len * sizeof(void *)))) {
+       if (!(h->heap =
+#ifdef MALLOC_DEBUG
+                       __ast_calloc(1, h->avail_len * sizeof(void *), file, lineno, func)
+#else
+                       ast_calloc(1, h->avail_len * sizeof(void *))
+#endif
+               )) {
                ast_free(h);
                return NULL;
        }
                ast_free(h);
                return NULL;
        }
@@ -154,14 +175,25 @@ struct ast_heap *ast_heap_destroy(struct ast_heap *h)
 /*!
  * \brief Add a row of additional storage for the heap.
  */
 /*!
  * \brief Add a row of additional storage for the heap.
  */
-static int grow_heap(struct ast_heap *h)
+static int grow_heap(struct ast_heap *h
+#ifdef MALLOC_DEBUG
+, const char *file, int lineno, const char *func
+#endif
+)
 {
 {
-       h->avail_len = h->avail_len * 2 + 1;
-
-       if (!(h->heap = ast_realloc(h->heap, h->avail_len * sizeof(void *)))) {
-               h->cur_len = h->avail_len = 0;
+       void **new_heap;
+       size_t new_len = h->avail_len * 2 + 1;
+
+#ifdef MALLOC_DEBUG
+       new_heap = __ast_realloc(h->heap, new_len * sizeof(void *), file, lineno, func);
+#else
+       new_heap = ast_realloc(h->heap, new_len * sizeof(void *));
+#endif
+       if (!new_heap) {
                return -1;
        }
                return -1;
        }
+       h->heap = new_heap;
+       h->avail_len = new_len;
 
        return 0;
 }
 
        return 0;
 }
@@ -202,21 +234,33 @@ static inline void max_heapify(struct ast_heap *h, int i)
        }
 }
 
        }
 }
 
-int ast_heap_push(struct ast_heap *h, void *elm)
+static int bubble_up(struct ast_heap *h, int i)
 {
 {
-       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;
+}
 
 
-       if (h->cur_len == h->avail_len && grow_heap(h)) {
+#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
+{
+       if (h->cur_len == h->avail_len && grow_heap(h
+#ifdef MALLOC_DEBUG
+               , file, lineno, func
+#endif
+               )) {
                return -1;
        }
 
        heap_set(h, ++(h->cur_len), elm);
 
                return -1;
        }
 
        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;
 }
 
        return 0;
 }
@@ -231,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)--));
 
        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;
        max_heapify(h, index);
 
        return ret;
@@ -267,18 +311,17 @@ size_t ast_heap_size(struct ast_heap *h)
        return h->cur_len;
 }
 
        return h->cur_len;
 }
 
-int ast_heap_wrlock(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);
+       return __ast_rwlock_wrlock(file, line, func, &h->lock, "&h->lock");
 }
 
 }
 
-int ast_heap_rdlock(struct ast_heap *h)
+int __ast_heap_rdlock(struct ast_heap *h, const char *file, const char *func, int line)
 {
 {
-       return ast_rwlock_rdlock(&h->lock);
+       return __ast_rwlock_rdlock(file, line, func, &h->lock, "&h->lock");
 }
 
 }
 
-int ast_heap_unlock(struct ast_heap *h)
+int __ast_heap_unlock(struct ast_heap *h, const char *file, const char *func, int line)
 {
 {
-       return ast_rwlock_unlock(&h->lock);
+       return __ast_rwlock_unlock(file, line, func, &h->lock, "&h->lock");
 }
 }
-