Logo Search packages:      
Sourcecode: sofia-sip version File versions  Download package

heap.h File Reference
Include dependency graph for heap.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.


#define HEAP_BODIES(scope, heaptype, prefix, type, less, set, alloc, null)
#define HEAP_DECLARE(scope, heaptype, prefix, type)
#define HEAP_MIN_SIZE   31
#define HEAP_TYPE   struct { void *private; }


SOFIA_BEGIN_DECLS SOFIAPUBFUN void su_smoothsort (void *base, size_t r0, size_t N, int(*less)(void *base, size_t a, size_t b), void(*swap)(void *base, size_t a, size_t b))

Detailed Description

Heap template implemented with dynamic array.

This file contain template macros implementing heap in C. The heap keeps its element in a known order and it can be used to implement, for example, a prioritye queue or an ordered queue.

The ordering within the heap is defined as follows:

  • indexing starts from 1
  • for each element with index [i] in the heap there are two descendant elements with indices [2*i] and [2*i+1],
  • the heap guarantees that the descendant elements are never smaller than their parent element. Therefore it follows that there is no element smaller than element at index [1] in the rest of the heap.

Adding and removing elements to the heap is an O(logN) operation.

The heap array is resizeable, and it usually contain pointers to the actual entries. The template macros define two functions used to add and remove entries to the heap. The add() function takes the element to be added as its argument, the remove() function the index of the element to be removed. The template defines also a predicate used to check if the heap is full, and a function used to resize the heap.

The heap user must define four primitives:

  • less than comparison
  • array setter
  • heap array allocator
  • empty element

Please note that in order to remove an entry in the heap, the application must know its index in the heap array.

The heap struct is declared with macro HEAP_DECLARE(). The prototypes for heap functions are instantiated with macro HEAP_PROTOS(). The implementation is instantiated with macro HEAP_BODIES().

Example code can be found from <su/torture_heap.c> and <sresolv/sres_cache.c>.

Pekka Pessi <Pekka.Pessi@nokia.com>. .

Definition in file heap.h.

Generated by  Doxygen 1.6.0   Back to index