Max Heap data structure. More...
#include "asterisk.h"
#include "asterisk/heap.h"
#include "asterisk/utils.h"
#include "asterisk/cli.h"
Go to the source code of this file.
Data Structures | |
struct | ast_heap |
Functions | |
static void * | _ast_heap_remove (struct ast_heap *h, unsigned int index) |
struct ast_heap * | ast_heap_create (unsigned int init_height, ast_heap_cmp_fn cmp_fn, ssize_t index_offset) |
Create a max heap. | |
struct ast_heap * | ast_heap_destroy (struct ast_heap *h) |
Destroy a max heap. | |
void * | ast_heap_peek (struct ast_heap *h, unsigned int index) |
Peek at an element on a heap. | |
void * | ast_heap_pop (struct ast_heap *h) |
Pop the max element off of the heap. | |
int | ast_heap_push (struct ast_heap *h, void *elm) |
Push an element on to a heap. | |
int | ast_heap_rdlock (struct ast_heap *h) |
Read-Lock a heap. | |
void * | ast_heap_remove (struct ast_heap *h, void *elm) |
Remove a specific element from a heap. | |
size_t | ast_heap_size (struct ast_heap *h) |
Get the current size of a heap. | |
int | ast_heap_unlock (struct ast_heap *h) |
Unlock a heap. | |
int | ast_heap_verify (struct ast_heap *h) |
Verify that a heap has been properly constructed. | |
int | ast_heap_wrlock (struct ast_heap *h) |
Write-Lock a heap. | |
static int | bubble_up (struct ast_heap *h, int i) |
static ssize_t | get_index (struct ast_heap *h, void *elm) |
static int | grow_heap (struct ast_heap *h) |
Add a row of additional storage for the heap. | |
static void * | heap_get (struct ast_heap *h, int i) |
static void | heap_set (struct ast_heap *h, int i, void *elm) |
static void | heap_swap (struct ast_heap *h, int i, int j) |
static int | left_node (int i) |
static void | max_heapify (struct ast_heap *h, int i) |
static int | parent_node (int i) |
static int | right_node (int i) |
Max Heap data structure.
Definition in file heap.c.
static void* _ast_heap_remove | ( | struct ast_heap * | h, |
unsigned int | index | ||
) | [static] |
Definition at line 263 of file heap.c.
References bubble_up(), ast_heap::cur_len, heap_get(), heap_set(), and max_heapify().
Referenced by ast_heap_pop(), and ast_heap_remove().
struct ast_heap* ast_heap_create | ( | unsigned int | init_height, |
ast_heap_cmp_fn | cmp_fn, | ||
ssize_t | index_offset | ||
) | [read] |
Create a max heap.
init_height | The initial height of the heap to allocate space for. To start out, there will be room for (2 ^ init_height) - 1 entries. However, the heap will grow as needed. |
cmp_fn | The function that should be used to compare elements in the heap. |
index_offset | This parameter is optional, but must be provided to be able to use ast_heap_remove(). This is the number of bytes into the element where an ssize_t has been made available for the heap's internal use. The heap will use this field to keep track of the element's current position in the heap. The offsetof() macro is useful for providing a proper value for this argument. If ast_heap_remove() will not be used, then a negative value can be provided to indicate that no field for an offset has been allocated. |
Example Usage:
struct myobj { int foo; int bar; char stuff[8]; char things[8]; ssize_t __heap_index; }; ... static int myobj_cmp(void *obj1, void *obj2); ... struct ast_heap *h; h = ast_heap_create(8, myobj_cmp, offsetof(struct myobj, __heap_index));
Definition at line 114 of file heap.c.
References __ast_calloc(), ast_calloc, ast_free, ast_log(), ast_rwlock_init(), ast_heap::avail_len, ast_heap::cmp_fn, ast_heap::heap, ast_heap::index_offset, ast_heap::lock, and LOG_ERROR.
Referenced by ast_timing_init(), load_resource_list(), and sched_context_create().
{ struct ast_heap *h; if (!cmp_fn) { ast_log(LOG_ERROR, "A comparison function must be provided\n"); return NULL; } if (!init_height) { init_height = 8; } if (!(h = #ifdef MALLOC_DEBUG __ast_calloc(1, sizeof(*h), file, lineno, func) #else ast_calloc(1, sizeof(*h)) #endif )) { return NULL; } h->cmp_fn = cmp_fn; h->index_offset = index_offset; h->avail_len = (1 << init_height) - 1; 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_rwlock_init(&h->lock); return h; }
Destroy a max heap.
h | the heap to destroy |
Definition at line 159 of file heap.c.
References ast_free, ast_rwlock_destroy(), ast_heap::heap, and ast_heap::lock.
Referenced by load_resource_list(), and sched_context_destroy().
void* ast_heap_peek | ( | struct ast_heap * | h, |
unsigned int | index | ||
) |
Peek at an element on a heap.
h | the heap |
index | index of the element to return. The first element is at index 1, and the last element is at the index == the size of the heap. |
Example code for a traversal:
struct ast_heap *h; ... size_t size, i; void *cur_obj; ast_heap_rdlock(h); size = ast_heap_size(h); for (i = 1; i <= size && (cur_obj = ast_heap_peek(h, i)); i++) { ... Do stuff with cur_obj ... } ast_heap_unlock(h);
Definition at line 295 of file heap.c.
References ast_heap::cur_len, and heap_get().
Referenced by ast_sched_dump(), ast_sched_report(), ast_sched_runq(), ast_sched_wait(), and ast_timer_open().
void* ast_heap_pop | ( | struct ast_heap * | h | ) |
Pop the max element off of the heap.
h | the heap |
Definition at line 290 of file heap.c.
References _ast_heap_remove().
Referenced by ast_sched_runq(), load_resource_list(), and sched_context_destroy().
{ return _ast_heap_remove(h, 1); }
int ast_heap_push | ( | struct ast_heap * | h, |
void * | elm | ||
) |
Push an element on to a heap.
h | the heap being added to |
elm | the element being put on the heap |
0 | success |
non-zero | failure |
Definition at line 245 of file heap.c.
References ast_heap::avail_len, bubble_up(), ast_heap::cur_len, grow_heap(), and heap_set().
Referenced by _ast_register_timing_interface(), load_resource(), and schedule().
int ast_heap_rdlock | ( | struct ast_heap * | h | ) |
Read-Lock a heap.
h | the heap |
A lock is provided for convenience. It can be assumed that none of the ast_heap API calls are thread safe. This lock does not have to be used if another one is already available to protect the heap.
Definition at line 316 of file heap.c.
References ast_rwlock_rdlock(), and ast_heap::lock.
Referenced by ast_timer_open().
{ return ast_rwlock_rdlock(&h->lock); }
void* ast_heap_remove | ( | struct ast_heap * | h, |
void * | elm | ||
) |
Remove a specific element from a heap.
h | the heap to remove from |
elm | the element to remove |
Definition at line 279 of file heap.c.
References _ast_heap_remove(), and get_index().
Referenced by ast_sched_del(), and ast_unregister_timing_interface().
{ ssize_t i = get_index(h, elm); if (i == -1) { return NULL; } return _ast_heap_remove(h, i); }
size_t ast_heap_size | ( | struct ast_heap * | h | ) |
Get the current size of a heap.
h | the heap |
Definition at line 304 of file heap.c.
References ast_heap::cur_len.
Referenced by ast_sched_dump(), and ast_sched_report().
{ return h->cur_len; }
int ast_heap_unlock | ( | struct ast_heap * | h | ) |
Unlock a heap.
h | the heap |
Definition at line 321 of file heap.c.
References ast_rwlock_unlock(), and ast_heap::lock.
Referenced by _ast_register_timing_interface(), ast_timer_open(), and ast_unregister_timing_interface().
{ return ast_rwlock_unlock(&h->lock); }
int ast_heap_verify | ( | struct ast_heap * | h | ) |
Verify that a heap has been properly constructed.
h | a heap |
0 | success |
non-zero | failure |
Definition at line 86 of file heap.c.
References ast_heap::cmp_fn, ast_heap::cur_len, heap_get(), left_node(), and right_node().
{ unsigned int i; for (i = 1; i <= (h->cur_len / 2); i++) { int l = left_node(i); int r = right_node(i); if (l <= h->cur_len) { 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) { return -1; } } } return 0; }
int ast_heap_wrlock | ( | struct ast_heap * | h | ) |
Write-Lock a heap.
h | the heap |
A lock is provided for convenience. It can be assumed that none of the ast_heap API calls are thread safe. This lock does not have to be used if another one is already available to protect the heap.
Definition at line 311 of file heap.c.
References ast_rwlock_wrlock(), and ast_heap::lock.
Referenced by _ast_register_timing_interface(), and ast_unregister_timing_interface().
{ return ast_rwlock_wrlock(&h->lock); }
static int bubble_up | ( | struct ast_heap * | h, |
int | i | ||
) | [static] |
Definition at line 232 of file heap.c.
References ast_heap::cmp_fn, heap_get(), heap_swap(), and parent_node().
Referenced by _ast_heap_remove(), and ast_heap_push().
{ 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; }
static ssize_t get_index | ( | struct ast_heap * | h, |
void * | elm | ||
) | [inline, static] |
Definition at line 63 of file heap.c.
References ast_heap::index_offset.
Referenced by ast_heap_remove().
{ ssize_t *index; if (h->index_offset < 0) { return -1; } index = elm + h->index_offset; return *index; }
static int grow_heap | ( | struct ast_heap * | h | ) | [static] |
Add a row of additional storage for the heap.
Definition at line 174 of file heap.c.
References __ast_realloc(), and ast_realloc.
Referenced by ast_heap_push().
static void* heap_get | ( | struct ast_heap * | h, |
int | i | ||
) | [inline, static] |
Definition at line 58 of file heap.c.
References ast_heap::heap.
Referenced by _ast_heap_remove(), ast_heap_peek(), ast_heap_verify(), bubble_up(), heap_swap(), and max_heapify().
{ return h->heap[i - 1]; }
static void heap_set | ( | struct ast_heap * | h, |
int | i, | ||
void * | elm | ||
) | [inline, static] |
Definition at line 76 of file heap.c.
References ast_heap::heap, and ast_heap::index_offset.
Referenced by _ast_heap_remove(), ast_heap_push(), and heap_swap().
{ h->heap[i - 1] = elm; if (h->index_offset >= 0) { ssize_t *index = elm + h->index_offset; *index = i; } }
static void heap_swap | ( | struct ast_heap * | h, |
int | i, | ||
int | j | ||
) | [inline, static] |
Definition at line 196 of file heap.c.
References heap_get(), and heap_set().
Referenced by bubble_up(), and max_heapify().
static int left_node | ( | int | i | ) | [inline, static] |
Definition at line 43 of file heap.c.
Referenced by ast_heap_verify(), and max_heapify().
{
return 2 * i;
}
static void max_heapify | ( | struct ast_heap * | h, |
int | i | ||
) | [inline, static] |
Definition at line 205 of file heap.c.
References ast_heap::cmp_fn, ast_heap::cur_len, heap_get(), heap_swap(), left_node(), and right_node().
Referenced by _ast_heap_remove().
{ for (;;) { int l = left_node(i); int r = right_node(i); int max; if (l <= h->cur_len && h->cmp_fn(heap_get(h, l), heap_get(h, i)) > 0) { max = l; } else { max = i; } if (r <= h->cur_len && h->cmp_fn(heap_get(h, r), heap_get(h, max)) > 0) { max = r; } if (max == i) { break; } heap_swap(h, i, max); i = max; } }
static int parent_node | ( | int | i | ) | [inline, static] |
static int right_node | ( | int | i | ) | [inline, static] |
Definition at line 48 of file heap.c.
Referenced by ast_heap_verify(), and max_heapify().
{
return 2 * i + 1;
}