#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. | |
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. | |
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. | |
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. | |
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) |
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.
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 318 of file heap.c.
References __ast_rwlock_rdlock(), and ast_heap::lock.
00319 { 00320 return __ast_rwlock_rdlock(file, line, func, &h->lock, "&h->lock"); 00321 }
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 323 of file heap.c.
References __ast_rwlock_unlock(), and ast_heap::lock.
00324 { 00325 return __ast_rwlock_unlock(file, line, func, &h->lock, "&h->lock"); 00326 }
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 313 of file heap.c.
References __ast_rwlock_wrlock(), and ast_heap::lock.
00314 { 00315 return __ast_rwlock_wrlock(file, line, func, &h->lock, "&h->lock"); 00316 }
static void* _ast_heap_remove | ( | struct ast_heap * | h, | |
unsigned int | index | |||
) | [static] |
Definition at line 267 of file heap.c.
References bubble_up(), ast_heap::cur_len, heap_get(), heap_set(), and max_heapify().
Referenced by ast_heap_pop(), and ast_heap_remove().
00268 { 00269 void *ret; 00270 00271 if (!index || index > h->cur_len) { 00272 return NULL; 00273 } 00274 00275 ret = heap_get(h, index); 00276 heap_set(h, index, heap_get(h, (h->cur_len)--)); 00277 index = bubble_up(h, index); 00278 max_heapify(h, index); 00279 00280 return ret; 00281 }
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 118 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().
00121 { 00122 struct ast_heap *h; 00123 00124 if (!cmp_fn) { 00125 ast_log(LOG_ERROR, "A comparison function must be provided\n"); 00126 return NULL; 00127 } 00128 00129 if (!init_height) { 00130 init_height = 8; 00131 } 00132 00133 if (!(h = 00134 #ifdef MALLOC_DEBUG 00135 __ast_calloc(1, sizeof(*h), file, lineno, func) 00136 #else 00137 ast_calloc(1, sizeof(*h)) 00138 #endif 00139 )) { 00140 return NULL; 00141 } 00142 00143 h->cmp_fn = cmp_fn; 00144 h->index_offset = index_offset; 00145 h->avail_len = (1 << init_height) - 1; 00146 00147 if (!(h->heap = 00148 #ifdef MALLOC_DEBUG 00149 __ast_calloc(1, h->avail_len * sizeof(void *), file, lineno, func) 00150 #else 00151 ast_calloc(1, h->avail_len * sizeof(void *)) 00152 #endif 00153 )) { 00154 ast_free(h); 00155 return NULL; 00156 } 00157 00158 ast_rwlock_init(&h->lock); 00159 00160 return h; 00161 }
Destroy a max heap.
h | the heap to destroy |
Definition at line 163 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().
00164 { 00165 ast_free(h->heap); 00166 h->heap = NULL; 00167 00168 ast_rwlock_destroy(&h->lock); 00169 00170 ast_free(h); 00171 00172 return NULL; 00173 }
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 299 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().
00300 { 00301 if (!h->cur_len || !index || index > h->cur_len) { 00302 return NULL; 00303 } 00304 00305 return heap_get(h, index); 00306 }
void* ast_heap_pop | ( | struct ast_heap * | h | ) |
Pop the max element off of the heap.
h | the heap |
Definition at line 294 of file heap.c.
References _ast_heap_remove().
Referenced by ast_sched_runq(), load_resource_list(), and sched_context_destroy().
00295 { 00296 return _ast_heap_remove(h, 1); 00297 }
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 249 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().
00251 { 00252 if (h->cur_len == h->avail_len && grow_heap(h 00253 #ifdef MALLOC_DEBUG 00254 , file, lineno, func 00255 #endif 00256 )) { 00257 return -1; 00258 } 00259 00260 heap_set(h, ++(h->cur_len), elm); 00261 00262 bubble_up(h, h->cur_len); 00263 00264 return 0; 00265 }
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 283 of file heap.c.
References _ast_heap_remove(), and get_index().
Referenced by ast_sched_del(), and ast_unregister_timing_interface().
00284 { 00285 ssize_t i = get_index(h, elm); 00286 00287 if (i == -1) { 00288 return NULL; 00289 } 00290 00291 return _ast_heap_remove(h, i); 00292 }
size_t ast_heap_size | ( | struct ast_heap * | h | ) |
Get the current size of a heap.
h | the heap |
Definition at line 308 of file heap.c.
References ast_heap::cur_len.
Referenced by ast_sched_dump(), and ast_sched_report().
00309 { 00310 return h->cur_len; 00311 }
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 90 of file heap.c.
References ast_heap::cmp_fn, ast_heap::cur_len, heap_get(), left_node(), and right_node().
00091 { 00092 unsigned int i; 00093 00094 for (i = 1; i <= (h->cur_len / 2); i++) { 00095 int l = left_node(i); 00096 int r = right_node(i); 00097 00098 if (l <= h->cur_len) { 00099 if (h->cmp_fn(heap_get(h, i), heap_get(h, l)) < 0) { 00100 return -1; 00101 } 00102 } 00103 00104 if (r <= h->cur_len) { 00105 if (h->cmp_fn(heap_get(h, i), heap_get(h, r)) < 0) { 00106 return -1; 00107 } 00108 } 00109 } 00110 00111 return 0; 00112 }
static int bubble_up | ( | struct ast_heap * | h, | |
int | i | |||
) | [static] |
Definition at line 236 of file heap.c.
References ast_heap::cmp_fn, heap_get(), heap_swap(), and parent_node().
Referenced by _ast_heap_remove(), and ast_heap_push().
00237 { 00238 while (i > 1 && h->cmp_fn(heap_get(h, parent_node(i)), heap_get(h, i)) < 0) { 00239 heap_swap(h, i, parent_node(i)); 00240 i = parent_node(i); 00241 } 00242 00243 return i; 00244 }
static ssize_t get_index | ( | struct ast_heap * | h, | |
void * | elm | |||
) | [inline, static] |
Definition at line 67 of file heap.c.
References ast_heap::index_offset.
00068 { 00069 ssize_t *index; 00070 00071 if (h->index_offset < 0) { 00072 return -1; 00073 } 00074 00075 index = elm + h->index_offset; 00076 00077 return *index; 00078 }
static int grow_heap | ( | struct ast_heap * | h | ) | [static] |
Add a row of additional storage for the heap.
Definition at line 178 of file heap.c.
References __ast_realloc(), and ast_realloc.
Referenced by ast_heap_push().
00183 { 00184 h->avail_len = h->avail_len * 2 + 1; 00185 00186 if (!(h->heap = 00187 #ifdef MALLOC_DEBUG 00188 __ast_realloc(h->heap, h->avail_len * sizeof(void *), file, lineno, func) 00189 #else 00190 ast_realloc(h->heap, h->avail_len * sizeof(void *)) 00191 #endif 00192 )) { 00193 h->cur_len = h->avail_len = 0; 00194 return -1; 00195 } 00196 00197 return 0; 00198 }
static void* heap_get | ( | struct ast_heap * | h, | |
int | i | |||
) | [inline, static] |
Definition at line 62 of file heap.c.
References ast_heap::heap.
Referenced by _ast_heap_remove(), ast_heap_peek(), ast_heap_verify(), bubble_up(), heap_swap(), and max_heapify().
00063 { 00064 return h->heap[i - 1]; 00065 }
static void heap_set | ( | struct ast_heap * | h, | |
int | i, | |||
void * | elm | |||
) | [inline, static] |
Definition at line 80 of file heap.c.
References ast_heap::heap, and ast_heap::index_offset.
Referenced by _ast_heap_remove(), ast_heap_push(), and heap_swap().
00081 { 00082 h->heap[i - 1] = elm; 00083 00084 if (h->index_offset >= 0) { 00085 ssize_t *index = elm + h->index_offset; 00086 *index = i; 00087 } 00088 }
static void heap_swap | ( | struct ast_heap * | h, | |
int | i, | |||
int | j | |||
) | [inline, static] |
Definition at line 200 of file heap.c.
References heap_get(), and heap_set().
Referenced by bubble_up(), and max_heapify().
00201 { 00202 void *tmp; 00203 00204 tmp = heap_get(h, i); 00205 heap_set(h, i, heap_get(h, j)); 00206 heap_set(h, j, tmp); 00207 }
static int left_node | ( | int | i | ) | [inline, static] |
static void max_heapify | ( | struct ast_heap * | h, | |
int | i | |||
) | [inline, static] |
Definition at line 209 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().
00210 { 00211 for (;;) { 00212 int l = left_node(i); 00213 int r = right_node(i); 00214 int max; 00215 00216 if (l <= h->cur_len && h->cmp_fn(heap_get(h, l), heap_get(h, i)) > 0) { 00217 max = l; 00218 } else { 00219 max = i; 00220 } 00221 00222 if (r <= h->cur_len && h->cmp_fn(heap_get(h, r), heap_get(h, max)) > 0) { 00223 max = r; 00224 } 00225 00226 if (max == i) { 00227 break; 00228 } 00229 00230 heap_swap(h, i, max); 00231 00232 i = max; 00233 } 00234 }
static int parent_node | ( | int | i | ) | [inline, static] |
static int right_node | ( | int | i | ) | [inline, static] |