Asterisk - The Open Source Telephony Project
21.4.1
|
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 | |
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) |
static void * | _ast_heap_remove (struct ast_heap *h, unsigned int index) |
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... | |
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, const char *file, int lineno, const char *func) |
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.
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.