103 for (i = 0; i < level; i++)
106 heap_dump(top->
l, level + 1);
107 heap_dump(top->
r, level + 1);
121subheap_insert(
heapnode_t * root,
void *data, int32 val)
137 if (root->
val > val) {
138 tmpdata = root->
data;
147 if (root->nl > root->
nr) {
148 root->
r = subheap_insert(root->
r, data, val);
152 root->
l = subheap_insert(root->
l, data, val);
163 heap->top = subheap_insert(heap->top, data, val);
185 root->
r = subheap_pop(r);
190 if ((!r) || (l->
val < r->
val)) {
193 root->
l = subheap_pop(l);
199 root->
r = subheap_pop(r);
211 if (heap->top == NULL)
213 *data = heap->top->
data;
214 *val = heap->top->
val;
215 heap->top = subheap_pop(heap->top);
223 if (heap->top == NULL)
225 *data = heap->top->
data;
226 *val = heap->top->
val;
235 else if (top->
data == data) {
236 assert(top == heap->top);
237 heap->top = subheap_pop(heap->top);
241 if (top->
l->
data == data) {
242 top->
l = subheap_pop(top->
l);
246 else if (heap_remove_one(heap, top->
l, data) == 0) {
252 if (top->
r->
data == data) {
253 top->
r = subheap_pop(top->
r);
257 else if (heap_remove_one(heap, top->
r, data) == 0) {
268 return heap_remove_one(heap, heap->top, data);
275 if (heap->top == NULL)
277 return heap->top->nl + heap->top->
nr + 1;
287 while (
heap_pop(heap, &data, &val) > 0)
Sphinx's memory allocation/deallocation routines.
SPHINXBASE_EXPORT void ckd_free(void *ptr)
Test and free a 1-D array.
#define ckd_calloc(n, sz)
Macros to simplify the use of above functions.
Implementation of logging routines.
SPHINXBASE_EXPORT size_t heap_size(heap_t *heap)
Return the number of items in the heap.
SPHINXBASE_EXPORT int heap_pop(heap_t *heap, void **data, int32 *val)
Like heap_top but also pop the top item off the heap.
SPHINXBASE_EXPORT heap_t * heap_new(void)
Allocate a new heap and return handle to it.
SPHINXBASE_EXPORT int heap_insert(heap_t *heap, void *data, int32 val)
Insert a new item into the given heap.
SPHINXBASE_EXPORT int heap_remove(heap_t *heap, void *data)
Remove an item from the heap.
SPHINXBASE_EXPORT int heap_destroy(heap_t *heap)
Destroy the given heap; free the heap nodes.
SPHINXBASE_EXPORT int heap_top(heap_t *heap, void **data, int32 *val)
Return the topmost item in the heap.
Internal heap data structure.
int32 val
Associated with above application data; according to which heap is sorted (in ascending order)
void * data
Application data at this node.
struct heapnode_s * r
Root of right descendant heap.
int32 nr
left/right descendants of this node (for balancing heap)
struct heapnode_s * l
Root of left descendant heap.