Heap data structure; all elements in the heap must be of the same size. A heap data structure is an ordered tree where the root node contains the smallest value. The smallest element in the whole heap is alway the top element. This heap is implemented by an array.
More...
Classes |
struct | HEAP |
Typedefs |
typedef int(* | HEAP_VISITOR )(int index, void *elm, size_t elmsize, void *context) |
Functions |
M_INLINE int | HEAP_init (HEAP *heap, size_t elmcount, size_t elmsize, HEAP_compare compare_func) |
M_INLINE void | HEAP_free (HEAP *heap) |
| free all memory used by the heap (object destructor). heap (in) the object.
|
M_INLINE size_t | HEAP_size (HEAP *heap) |
M_INLINE size_t | HEAP_maxsize (HEAP *heap) |
M_INLINE size_t | HEAP_elmsize (HEAP *heap) |
M_INLINE void * | HEAP_top (HEAP *heap) |
| returns pointer to the top element of the heap.
|
M_INLINE void * | HEAP_get_at (HEAP *heap, int index) |
int | HEAP_pop (HEAP *heap) |
| remove the top element from the heap
|
int | HEAP_push (HEAP *heap, void *element, size_t elmsize) |
| insert a new element into the heap
|
int | HEAP_check (HEAP *heap) |
| check consistency of heap object.
|
void | HEAP_foreach_sorted (HEAP *heap, HEAP_VISITOR eval, void *context) |
M_INLINE void | HEAP_foreach (HEAP *heap, HEAP_VISITOR eval, void *context) |
M_INLINE int | HEAP_findif (HEAP *heap, HEAP_VISITOR eval, void *context, int32_t *retval) |
Detailed Description
Heap data structure; all elements in the heap must be of the same size. A heap data structure is an ordered tree where the root node contains the smallest value. The smallest element in the whole heap is alway the top element. This heap is implemented by an array.
Typedef Documentation
typedef int(* HEAP_VISITOR)(int index, void *elm, size_t elmsize, void *context) |
Function Documentation
int HEAP_check |
( |
HEAP * |
heap | ) |
|
check consistency of heap object.
Definition at line 165 of file heap.c.
M_INLINE size_t HEAP_elmsize |
( |
HEAP * |
heap | ) |
|
M_INLINE int HEAP_findif |
( |
HEAP * |
heap, |
|
|
HEAP_VISITOR |
eval, |
|
|
void * |
context, |
|
|
int32_t * |
retval |
|
) |
| |
Definition at line 160 of file heap.h.
{
size_t i;
size_t sz = heap->elmcount;
size_t elmsz = heap->elmsize;
int32_t ret;
uint8_t *pos;
if (!retval) {
*retval = 0;
}
for(i = 0, pos = heap->buffer; i < sz; i++, pos += elmsz) {
if ( (ret = eval( i, pos, elmsz, context )) != 0) {
if (retval) {
*retval = ret;
}
return i;
}
}
return -1;
}
Definition at line 148 of file heap.h.
{
size_t i;
size_t sz = heap->elmcount;
size_t elmsz = heap->elmsize;
uint8_t *pos;
for(pos = heap->buffer, i = 0; i < sz; i++, pos += elmsz) {
eval( i, pos, elmsz, context );
}
}
M_INLINE void HEAP_free |
( |
HEAP * |
heap | ) |
|
free all memory used by the heap (object destructor). heap (in) the object.
Definition at line 68 of file heap.h.
M_INLINE void* HEAP_get_at |
( |
HEAP * |
heap, |
|
|
int |
index |
|
) |
| |
M_INLINE int HEAP_init |
( |
HEAP * |
heap, |
|
|
size_t |
elmcount, |
|
|
size_t |
elmsize, |
|
|
HEAP_compare |
compare_func |
|
) |
| |
M_INLINE size_t HEAP_maxsize |
( |
HEAP * |
heap | ) |
|
int HEAP_pop |
( |
HEAP * |
heap | ) |
|
remove the top element from the heap
- Parameters:
-
Definition at line 60 of file heap.c.
{
size_t pos, pos_offset;
size_t left_child, left_child_offset;
size_t right_child, right_child_offset;
size_t next_pos, next_pos_offset;
size_t last_element, last_element_offset;
size_t elmsize;
if (heap->elmcount == 0) {
return -1;
}
elmsize = heap->elmsize;
last_element = heap->elmcount;
last_element_offset = (last_element -1) * elmsize;
heap->elmcount--;
pos = 1;
while( pos <= heap->elmcount) {
left_child = (pos << 1);
if (left_child > heap->elmcount) {
break;
}
right_child = left_child + 1;
right_child_offset = (right_child - 1) * elmsize;
left_child_offset = (left_child - 1) * elmsize;
if (left_child != heap->elmcount &&
heap->compare_func( heap->buffer + right_child_offset,
heap->buffer + left_child_offset,
elmsize) < 0) {
next_pos = right_child;
} else {
next_pos = left_child;
}
next_pos_offset = (next_pos-1) * elmsize;
if (heap->compare_func(heap->buffer + last_element_offset,
heap->buffer + next_pos_offset,
elmsize) > 0) {
pos_offset = (pos - 1) * elmsize;
memcpy( heap->buffer + pos_offset, heap->buffer + next_pos_offset, elmsize);
} else {
break;
}
pos = next_pos;
}
pos_offset = (pos - 1) * elmsize;
if (pos_offset != last_element_offset) {
memcpy( heap->buffer + pos_offset, heap->buffer + last_element_offset, elmsize);
}
return 0;
}
int HEAP_push |
( |
HEAP * |
heap, |
|
|
void * |
element, |
|
|
size_t |
elmsize |
|
) |
| |
insert a new element into the heap
- Parameters:
-
heap | (in) the object |
element | (in) data of object to be inserted into heap |
elmsize | (in) size of data area for element pointer. |
Definition at line 7 of file heap.c.
{
size_t pos, pos_offset;
size_t parent, parent_offset;
if (elmsize != heap->elmsize) {
return -1;
}
if (heap->elmcount >= (heap->elmmaxcount - 1)) {
unsigned char *pbuffer;
size_t sz = heap->elmmaxcount * 2;
pbuffer = realloc( heap->buffer, (sz) * heap->elmsize );
if (!pbuffer) {
return -1;
}
heap->buffer = pbuffer;
heap->elmmaxcount = sz;
}
elmsize = heap->elmsize;
heap->elmcount ++;
pos = heap->elmcount;
while(pos > 1) {
parent = pos / 2;
pos_offset = (pos - 1) * elmsize;
parent_offset = (parent - 1) * elmsize;
if ( heap->compare_func( heap->buffer + parent_offset,
element,
elmsize ) > 0) {
memcpy( heap->buffer + pos_offset, heap->buffer + parent_offset, elmsize);
pos = parent;
} else {
break;
}
}
memcpy( heap->buffer + (pos - 1) * elmsize, element, elmsize);
return 0;
}
M_INLINE size_t HEAP_size |
( |
HEAP * |
heap | ) |
|
M_INLINE void* HEAP_top |
( |
HEAP * |
heap | ) |
|
returns pointer to the top element of the heap.
- Parameters:
-
- Returns:
- pointer to the top element of the heap or 0 if heap is empty.
Definition at line 99 of file heap.h.