Go to the source code of this file.
Defines | |
#define | ast_heap_rdlock(h) __ast_heap_rdlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__) |
#define | ast_heap_unlock(h) __ast_heap_unlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__) |
#define | ast_heap_wrlock(h) __ast_heap_wrlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__) |
Typedefs | |
typedef int(*) | ast_heap_cmp_fn (void *elm1, void *elm2) |
Function type for comparing nodes in a heap. | |
Functions | |
int | __ast_heap_rdlock (struct ast_heap *h, const char *file, const char *func, int line) |
Read-Lock a heap. | |
int | __ast_heap_unlock (struct ast_heap *h, const char *file, const char *func, int line) |
Unlock a heap. | |
int | __ast_heap_wrlock (struct ast_heap *h, const char *file, const char *func, int line) |
Write-Lock a heap. | |
ast_heap * | ast_heap_create (unsigned int init_height, ast_heap_cmp_fn cmp_fn, ssize_t index_offset) |
Create a max heap. | |
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. | |
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_verify (struct ast_heap *h) |
Verify that a heap has been properly constructed. |
Definition in file heap.h.
#define ast_heap_rdlock | ( | h | ) | __ast_heap_rdlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__) |
#define ast_heap_unlock | ( | h | ) | __ast_heap_unlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__) |
Definition at line 252 of file heap.h.
Referenced by _ast_register_timing_interface(), ast_timer_open(), and ast_unregister_timing_interface().
#define ast_heap_wrlock | ( | h | ) | __ast_heap_wrlock(h, __FILE__, __PRETTY_FUNCTION__, __LINE__) |
Definition at line 250 of file heap.h.
Referenced by _ast_register_timing_interface(), and ast_unregister_timing_interface().
typedef int(*) ast_heap_cmp_fn(void *elm1, void *elm2) |
Function type for comparing nodes in a heap.
elm1 | the first element | |
elm2 | the second element |
negative | if elm1 < elm2 | |
0 | if elm1 == elm2 | |
positive | if elm1 > elm2 |
int __ast_heap_rdlock | ( | struct ast_heap * | h, | |
const char * | file, | |||
const char * | func, | |||
int | line | |||
) |
Read-Lock a heap.
h | the heap |
Definition at line 314 of file heap.c.
References __ast_rwlock_rdlock(), and ast_heap::lock.
00315 { 00316 return __ast_rwlock_rdlock(&h->lock, "&h->lock", file, line, func); 00317 }
int __ast_heap_unlock | ( | struct ast_heap * | h, | |
const char * | file, | |||
const char * | func, | |||
int | line | |||
) |
Unlock a heap.
h | the heap |
Definition at line 319 of file heap.c.
References __ast_rwlock_unlock(), and ast_heap::lock.
00320 { 00321 return __ast_rwlock_unlock(&h->lock, "&h->lock", file, line, func); 00322 }
int __ast_heap_wrlock | ( | struct ast_heap * | h, | |
const char * | file, | |||
const char * | func, | |||
int | line | |||
) |
Write-Lock a heap.
h | the heap |
Definition at line 309 of file heap.c.
References __ast_rwlock_wrlock(), and ast_heap::lock.
00310 { 00311 return __ast_rwlock_wrlock(&h->lock, "&h->lock", file, line, func); 00312 }
struct ast_heap* ast_heap_create | ( | unsigned int | init_height, | |
ast_heap_cmp_fn | cmp_fn, | |||
ssize_t | index_offset | |||
) |
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. |
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, and LOG_ERROR.
Referenced by ast_timing_init(), load_resource_list(), and sched_context_create().
00117 { 00118 struct ast_heap *h; 00119 00120 if (!cmp_fn) { 00121 ast_log(LOG_ERROR, "A comparison function must be provided\n"); 00122 return NULL; 00123 } 00124 00125 if (!init_height) { 00126 init_height = 8; 00127 } 00128 00129 if (!(h = 00130 #ifdef MALLOC_DEBUG 00131 __ast_calloc(1, sizeof(*h), file, lineno, func) 00132 #else 00133 ast_calloc(1, sizeof(*h)) 00134 #endif 00135 )) { 00136 return NULL; 00137 } 00138 00139 h->cmp_fn = cmp_fn; 00140 h->index_offset = index_offset; 00141 h->avail_len = (1 << init_height) - 1; 00142 00143 if (!(h->heap = 00144 #ifdef MALLOC_DEBUG 00145 __ast_calloc(1, h->avail_len * sizeof(void *), file, lineno, func) 00146 #else 00147 ast_calloc(1, h->avail_len * sizeof(void *)) 00148 #endif 00149 )) { 00150 ast_free(h); 00151 return NULL; 00152 } 00153 00154 ast_rwlock_init(&h->lock); 00155 00156 return h; 00157 }
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().
00160 { 00161 ast_free(h->heap); 00162 h->heap = NULL; 00163 00164 ast_rwlock_destroy(&h->lock); 00165 00166 ast_free(h); 00167 00168 return NULL; 00169 }
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. |
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().
00296 { 00297 if (!h->cur_len || !index || index > h->cur_len) { 00298 return NULL; 00299 } 00300 00301 return heap_get(h, index); 00302 }
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().
00291 { 00292 return _ast_heap_remove(h, 1); 00293 }
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().
00247 { 00248 if (h->cur_len == h->avail_len && grow_heap(h 00249 #ifdef MALLOC_DEBUG 00250 , file, lineno, func 00251 #endif 00252 )) { 00253 return -1; 00254 } 00255 00256 heap_set(h, ++(h->cur_len), elm); 00257 00258 bubble_up(h, h->cur_len); 00259 00260 return 0; 00261 }
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().
00280 { 00281 ssize_t i = get_index(h, elm); 00282 00283 if (i == -1) { 00284 return NULL; 00285 } 00286 00287 return _ast_heap_remove(h, i); 00288 }
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().
00305 { 00306 return h->cur_len; 00307 }
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().
00087 { 00088 unsigned int i; 00089 00090 for (i = 1; i <= (h->cur_len / 2); i++) { 00091 int l = left_node(i); 00092 int r = right_node(i); 00093 00094 if (l <= h->cur_len) { 00095 if (h->cmp_fn(heap_get(h, i), heap_get(h, l)) < 0) { 00096 return -1; 00097 } 00098 } 00099 00100 if (r <= h->cur_len) { 00101 if (h->cmp_fn(heap_get(h, i), heap_get(h, r)) < 0) { 00102 return -1; 00103 } 00104 } 00105 } 00106 00107 return 0; 00108 }