Simple data structures / objects in plain C Snapshot
Classes | Typedefs | Functions
HEAP

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)

Definition at line 141 of file heap.h.


Function Documentation

int HEAP_check ( HEAP heap)

check consistency of heap object.

Definition at line 165 of file heap.c.

{

        if (heap->elmcount > heap->elmmaxcount) {
                return 0;
        }
        if (!check_recursive(heap, 1)) {
                return 0;
        }
        return 1;
}
M_INLINE size_t HEAP_elmsize ( HEAP heap)

Definition at line 89 of file heap.h.

{
        return heap->elmsize;
}
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;
}
M_INLINE void HEAP_foreach ( HEAP heap,
HEAP_VISITOR  eval,
void *  context 
)

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 ); 
        }
}
void HEAP_foreach_sorted ( HEAP heap,
HEAP_VISITOR  eval,
void *  context 
)

Definition at line 205 of file heap.c.

{
        visit_sorted( heap, 1, eval, 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.

{
        if (heap->buffer) {
                free(heap->buffer);
                heap->buffer = 0;
                heap->elmcount = 0;
                heap->elmmaxcount = 0;
                heap->elmsize = 0;
        }
}
M_INLINE void* HEAP_get_at ( HEAP heap,
int  index 
)

Definition at line 108 of file heap.h.

{
        if (heap->elmcount == 0) {
                return 0;
        }
        if (index > (int) heap->elmcount || index < 0) {
                return 0;
        }

        return heap->buffer + index * heap->elmsize;
}
M_INLINE int HEAP_init ( HEAP heap,
size_t  elmcount,
size_t  elmsize,
HEAP_compare  compare_func 
)

Definition at line 46 of file heap.h.

{
        
        heap->elmsize = elmsize;
        heap->elmcount = 0;
        heap->elmmaxcount = elmcount;
        heap->compare_func = compare_func;

        heap->buffer = (unsigned char *) malloc( elmcount * elmsize );
        if (!heap->buffer) {
                return -1;
        }

        return 0;
}
M_INLINE size_t HEAP_maxsize ( HEAP heap)

Definition at line 84 of file heap.h.

{
        return heap->elmmaxcount;
}
int HEAP_pop ( HEAP heap)

remove the top element from the heap

Parameters:
heap(in) the object

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)

Definition at line 79 of file heap.h.

{
        return heap->elmcount;
}
M_INLINE void* HEAP_top ( HEAP heap)

returns pointer to the top element of the heap.

Parameters:
heap(in) the object
Returns:
pointer to the top element of the heap or 0 if heap is empty.

Definition at line 99 of file heap.h.

{
        if (heap->elmcount == 0) {
                return 0;
        }
        return heap->buffer;
}