45 static inline int left_node(
int i)
50 static inline int right_node(
int i)
55 static inline int parent_node(
int i)
60 static inline void *heap_get(
struct ast_heap *h,
int i)
62 return h->heap[i - 1];
65 static inline ssize_t get_index(
struct ast_heap *h,
void *elm)
69 if (h->index_offset < 0) {
73 index = elm + h->index_offset;
78 static inline void heap_set(
struct ast_heap *h,
int i,
void *elm)
82 if (h->index_offset >= 0) {
83 ssize_t *index = elm + h->index_offset;
92 for (i = 1; i <= (h->cur_len / 2); i++) {
94 int r = right_node(i);
96 if (l <= h->cur_len) {
97 if (h->cmp_fn(heap_get(h, i), heap_get(h, l)) < 0) {
102 if (r <= h->cur_len) {
103 if (h->cmp_fn(heap_get(h, i), heap_get(h, r)) < 0) {
113 ssize_t index_offset,
const char *file,
int lineno,
const char *func)
118 ast_log(LOG_ERROR,
"A comparison function must be provided\n");
126 h = __ast_calloc(1,
sizeof(*h), file, lineno, func);
132 h->index_offset = index_offset;
133 h->avail_len = (1 << init_height) - 1;
135 h->heap = __ast_malloc(h->avail_len *
sizeof(
void *), file, lineno, func);
151 ast_rwlock_destroy(&h->lock);
164 size_t new_len = h->avail_len * 2 + 1;
166 new_heap = __ast_realloc(h->heap, new_len *
sizeof(
void *), file, lineno, func);
171 h->avail_len = new_len;
176 static inline void heap_swap(
struct ast_heap *h,
int i,
int j)
180 tmp = heap_get(h, i);
181 heap_set(h, i, heap_get(h, j));
185 static inline void max_heapify(
struct ast_heap *h,
int i)
188 int l = left_node(i);
189 int r = right_node(i);
192 if (l <= h->cur_len && h->cmp_fn(heap_get(h, l), heap_get(h, i)) > 0) {
198 if (r <= h->cur_len && h->cmp_fn(heap_get(h, r), heap_get(h, max)) > 0) {
206 heap_swap(h, i, max);
212 static int bubble_up(
struct ast_heap *h,
int i)
214 while (i > 1 && h->cmp_fn(heap_get(h, parent_node(i)), heap_get(h, i)) < 0) {
215 heap_swap(h, i, parent_node(i));
222 int _ast_heap_push(
struct ast_heap *h,
void *elm,
const char *file,
int lineno,
const char *func)
224 if (h->cur_len == h->avail_len &&
grow_heap(h, file, lineno, func)) {
228 heap_set(h, ++(h->cur_len), elm);
230 bubble_up(h, h->cur_len);
235 static void *_ast_heap_remove(
struct ast_heap *h,
unsigned int index)
239 if (!index || index > h->cur_len) {
243 ret = heap_get(h, index);
244 heap_set(h, index, heap_get(h, (h->cur_len)--));
245 index = bubble_up(h, index);
246 max_heapify(h, index);
253 ssize_t i = get_index(h, elm);
259 return _ast_heap_remove(h, i);
264 return _ast_heap_remove(h, 1);
269 if (!h->cur_len || !index || index > h->cur_len) {
273 return heap_get(h, index);
283 return __ast_rwlock_wrlock(file, line, func, &h->lock,
"&h->lock");
288 return __ast_rwlock_rdlock(file, line, func, &h->lock,
"&h->lock");
293 return __ast_rwlock_unlock(file, line, func, &h->lock,
"&h->lock");
void * ast_heap_remove(struct ast_heap *h, void *elm)
Remove a specific element from a heap.
int __ast_heap_unlock(struct ast_heap *h, const char *file, const char *func, int line)
Unlock a heap.
Asterisk main include file. File version handling, generic pbx functions.
#define ast_rwlock_init(rwlock)
wrapper for rwlock with tracking enabled
int __ast_heap_rdlock(struct ast_heap *h, const char *file, const char *func, int line)
Read-Lock a heap.
int(* ast_heap_cmp_fn)(void *elm1, void *elm2)
Function type for comparing nodes in a heap.
struct ast_heap * ast_heap_destroy(struct ast_heap *h)
Destroy a max heap.
static int grow_heap(struct ast_heap *h, const char *file, int lineno, const char *func)
Add a row of additional storage for the heap.
size_t ast_heap_size(struct ast_heap *h)
Get the current size of a heap.
void * ast_heap_peek(struct ast_heap *h, unsigned int index)
Peek at an element on a heap.
int ast_heap_verify(struct ast_heap *h)
Verify that a heap has been properly constructed.
void * ast_heap_pop(struct ast_heap *h)
Pop the max element off of the heap.
Structure for rwlock and tracking information.
Standard Command Line Interface.
int __ast_heap_wrlock(struct ast_heap *h, const char *file, const char *func, int line)
Write-Lock a heap.