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;
}

Classes

Typedefs

Functions

Detailed Description

Typedef Documentation

Function Documentation