Asterisk - The Open Source Telephony Project
21.4.1
|
Max Heap data structure. More...
Go to the source code of this file.
Macros | |
#define | ast_heap_create(init_height, cmp_fn, index_offset) _ast_heap_create(init_height, cmp_fn, index_offset, __FILE__, __LINE__, __PRETTY_FUNCTION__) |
Create a max heap. More... | |
#define | ast_heap_push(h, elm) _ast_heap_push(h, elm, __FILE__, __LINE__, __PRETTY_FUNCTION__) |
Push an element on to a heap. More... | |
#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. More... | |
Functions | |
int | __ast_heap_rdlock (struct ast_heap *h, const char *file, const char *func, int line) |
Read-Lock a heap. More... | |
int | __ast_heap_unlock (struct ast_heap *h, const char *file, const char *func, int line) |
Unlock a heap. More... | |
int | __ast_heap_wrlock (struct ast_heap *h, const char *file, const char *func, int line) |
Write-Lock a heap. More... | |
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) |
int | _ast_heap_push (struct ast_heap *h, void *elm, const char *file, int lineno, const char *func) |
struct ast_heap * | ast_heap_destroy (struct ast_heap *h) |
Destroy a max heap. More... | |
void * | ast_heap_peek (struct ast_heap *h, unsigned int index) |
Peek at an element on a heap. More... | |
void * | ast_heap_pop (struct ast_heap *h) |
Pop the max element off of the heap. More... | |
void * | ast_heap_remove (struct ast_heap *h, void *elm) |
Remove a specific element from a heap. More... | |
size_t | ast_heap_size (struct ast_heap *h) |
Get the current size of a heap. More... | |
int | ast_heap_verify (struct ast_heap *h) |
Verify that a heap has been properly constructed. More... | |
Max Heap data structure.
Definition in file heap.h.
#define ast_heap_create | ( | init_height, | |
cmp_fn, | |||
index_offset | |||
) | _ast_heap_create(init_height, cmp_fn, index_offset, __FILE__, __LINE__, __PRETTY_FUNCTION__) |
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:
Definition at line 100 of file heap.h.
Referenced by ast_bridge_features_init(), ast_sched_context_create(), and ast_timing_init().
#define ast_heap_push | ( | h, | |
elm | |||
) | _ast_heap_push(h, elm, __FILE__, __LINE__, __PRETTY_FUNCTION__) |
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 125 of file heap.h.
Referenced by ast_bridge_interval_hook(), and schedule().
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 |
file,func,line | 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. |
int __ast_heap_unlock | ( | struct ast_heap * | h, |
const char * | file, | ||
const char * | func, | ||
int | line | ||
) |
int __ast_heap_wrlock | ( | struct ast_heap * | h, |
const char * | file, | ||
const char * | func, | ||
int | line | ||
) |
Write-Lock a heap.
h | the heap |
file,func,line | 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. |
Destroy a max heap.
h | the heap to destroy |
NULL | for convenience |
Definition at line 146 of file heap.c.
Referenced by ast_bridge_features_cleanup(), and ast_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:
Definition at line 267 of file heap.c.
Referenced by ast_bridge_features_merge(), ast_sched_clean_by_callback(), 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 262 of file heap.c.
Referenced by ast_bridge_features_cleanup(), ast_sched_context_destroy(), and ast_sched_runq().
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 |
NULL | if it failed |
Definition at line 251 of file heap.c.
Referenced by ast_sched_clean_by_callback(), ast_sched_del_nonrunning(), and ast_unregister_timing_interface().
size_t ast_heap_size | ( | struct ast_heap * | h | ) |
Get the current size of a heap.
h | the heap |
Definition at line 276 of file heap.c.
Referenced by ast_sched_dump(), ast_sched_report(), and schedule().
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 88 of file heap.c.