#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) |
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. | |
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 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) |
Definition in file heap.c.
static void* _ast_heap_remove | ( | struct ast_heap * | h, | |
unsigned int | index | |||
) | [static] |
Definition at line 224 of file heap.c.
References ast_heap::cur_len, heap_get(), heap_set(), and max_heapify().
Referenced by ast_heap_pop(), and ast_heap_remove().
00225 { 00226 void *ret; 00227 00228 if (!index || index > h->cur_len) { 00229 return NULL; 00230 } 00231 00232 ret = heap_get(h, index); 00233 heap_set(h, index, heap_get(h, (h->cur_len)--)); 00234 00235 max_heapify(h, index); 00236 00237 return ret; 00238 }
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 110 of file heap.c.
References ast_calloc, ast_free, ast_log(), ast_rwlock_init(), and LOG_ERROR.
Referenced by ast_timing_init().
00112 { 00113 struct ast_heap *h; 00114 00115 if (!cmp_fn) { 00116 ast_log(LOG_ERROR, "A comparison function must be provided\n"); 00117 return NULL; 00118 } 00119 00120 if (!init_height) { 00121 init_height = 8; 00122 } 00123 00124 if (!(h = ast_calloc(1, sizeof(*h)))) { 00125 return NULL; 00126 } 00127 00128 h->cmp_fn = cmp_fn; 00129 h->index_offset = index_offset; 00130 h->avail_len = (1 << init_height) - 1; 00131 00132 if (!(h->heap = ast_calloc(1, h->avail_len * sizeof(void *)))) { 00133 ast_free(h); 00134 return NULL; 00135 } 00136 00137 ast_rwlock_init(&h->lock); 00138 00139 return h; 00140 }
Destroy a max heap.
h | the heap to destroy |
Definition at line 142 of file heap.c.
References ast_free, ast_rwlock_destroy(), ast_heap::heap, and ast_heap::lock.
00143 { 00144 ast_free(h->heap); 00145 h->heap = NULL; 00146 00147 ast_rwlock_destroy(&h->lock); 00148 00149 ast_free(h); 00150 00151 return NULL; 00152 }
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 256 of file heap.c.
References ast_heap::cur_len, and heap_get().
Referenced by ast_timer_open().
00257 { 00258 if (!h->cur_len || !index || index > h->cur_len) { 00259 return NULL; 00260 } 00261 00262 return heap_get(h, index); 00263 }
void* ast_heap_pop | ( | struct ast_heap * | h | ) |
Pop the max element off of the heap.
h | the heap |
Definition at line 251 of file heap.c.
References _ast_heap_remove().
00252 { 00253 return _ast_heap_remove(h, 1); 00254 }
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 205 of file heap.c.
References ast_heap::avail_len, ast_heap::cmp_fn, ast_heap::cur_len, grow_heap(), heap_get(), heap_set(), heap_swap(), and parent_node().
Referenced by _ast_register_timing_interface().
00206 { 00207 int i; 00208 00209 if (h->cur_len == h->avail_len && grow_heap(h)) { 00210 return -1; 00211 } 00212 00213 heap_set(h, ++(h->cur_len), elm); 00214 00215 for (i = h->cur_len; 00216 i > 1 && h->cmp_fn(heap_get(h, parent_node(i)), heap_get(h, i)) < 0; 00217 i = parent_node(i)) { 00218 heap_swap(h, i, parent_node(i)); 00219 } 00220 00221 return 0; 00222 }
int ast_heap_rdlock | ( | struct ast_heap * | h | ) |
Read-Lock a heap.
h | the heap |
Definition at line 277 of file heap.c.
References ast_rwlock_rdlock(), and ast_heap::lock.
Referenced by ast_timer_open().
00278 { 00279 return ast_rwlock_rdlock(&h->lock); 00280 }
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 240 of file heap.c.
References _ast_heap_remove(), and get_index().
Referenced by ast_unregister_timing_interface().
00241 { 00242 ssize_t i = get_index(h, elm); 00243 00244 if (i == -1) { 00245 return NULL; 00246 } 00247 00248 return _ast_heap_remove(h, i); 00249 }
size_t ast_heap_size | ( | struct ast_heap * | h | ) |
Get the current size of a heap.
h | the heap |
Definition at line 265 of file heap.c.
References ast_heap::cur_len.
00266 { 00267 return h->cur_len; 00268 }
int ast_heap_unlock | ( | struct ast_heap * | h | ) |
Unlock a heap.
h | the heap |
Definition at line 282 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().
00283 { 00284 return ast_rwlock_unlock(&h->lock); 00285 }
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 }
int ast_heap_wrlock | ( | struct ast_heap * | h | ) |
Write-Lock a heap.
h | the heap |
Definition at line 272 of file heap.c.
References ast_rwlock_wrlock(), and ast_heap::lock.
Referenced by _ast_register_timing_interface(), and ast_unregister_timing_interface().
00273 { 00274 return ast_rwlock_wrlock(&h->lock); 00275 }
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 _while_exec(), ast_heap_remove(), and while_continue_exec().
00064 { 00065 ssize_t *index; 00066 00067 if (h->index_offset < 0) { 00068 return -1; 00069 } 00070 00071 index = elm + h->index_offset; 00072 00073 return *index; 00074 }
static int grow_heap | ( | struct ast_heap * | h | ) | [static] |
Add a row of additional storage for the heap.
Definition at line 157 of file heap.c.
References ast_realloc, ast_heap::avail_len, ast_heap::cur_len, and ast_heap::heap.
Referenced by ast_heap_push().
00158 { 00159 h->avail_len = h->avail_len * 2 + 1; 00160 00161 if (!(h->heap = ast_realloc(h->heap, h->avail_len * sizeof(void *)))) { 00162 h->cur_len = h->avail_len = 0; 00163 return -1; 00164 } 00165 00166 return 0; 00167 }
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_push(), ast_heap_verify(), heap_swap(), and max_heapify().
00059 { 00060 return h->heap[i - 1]; 00061 }
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().
00077 { 00078 h->heap[i - 1] = elm; 00079 00080 if (h->index_offset >= 0) { 00081 ssize_t *index = elm + h->index_offset; 00082 *index = i; 00083 } 00084 }
static void heap_swap | ( | struct ast_heap * | h, | |
int | i, | |||
int | j | |||
) | [inline, static] |
Definition at line 169 of file heap.c.
References heap_get(), and heap_set().
Referenced by ast_heap_push(), and max_heapify().
00170 { 00171 void *tmp; 00172 00173 tmp = heap_get(h, i); 00174 heap_set(h, i, heap_get(h, j)); 00175 heap_set(h, j, tmp); 00176 }
static int left_node | ( | int | i | ) | [inline, static] |
static void max_heapify | ( | struct ast_heap * | h, | |
int | i | |||
) | [inline, static] |
Definition at line 178 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().
00179 { 00180 for (;;) { 00181 int l = left_node(i); 00182 int r = right_node(i); 00183 int max; 00184 00185 if (l <= h->cur_len && h->cmp_fn(heap_get(h, l), heap_get(h, i)) > 0) { 00186 max = l; 00187 } else { 00188 max = i; 00189 } 00190 00191 if (r <= h->cur_len && h->cmp_fn(heap_get(h, r), heap_get(h, max)) > 0) { 00192 max = r; 00193 } 00194 00195 if (max == i) { 00196 break; 00197 } 00198 00199 heap_swap(h, i, max); 00200 00201 i = max; 00202 } 00203 }
static int parent_node | ( | int | i | ) | [inline, static] |
static int right_node | ( | int | i | ) | [inline, static] |