Heap template implemented with dynamic array. More...

#include <sofia-sip/su_types.h>

Include dependency graph for heap.h:

Defines
#define	SOFIA_SIP_HEAP_H
	Defined when <sofia-sip/heap.h> has been included.
#define	HEAP_MIN_SIZE
	Minimum size of heap.
#define	HEAP_TYPE struct { void *private; }
	Declare heap structure type.
#define	HEAP_DECLARE(scope, heaptype, prefix, type)
	Prototypes for heap.
#define	HEAP_BODIES(scope, heaptype, prefix, type, less, set, alloc, null)
	Heap implementation.

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>.

Author:: Pekka Pessi <Pekka.Pessi@nokia-email.address.hidden>.

Since:: New in 1.12.7.

Define Documentation

#define HEAP_BODIES	(	scope,
		heaptype,
		prefix,
		type,
		less,
		set,
		alloc,
		null
	)

Heap implementation.

The macro HEAP_BODIES() expands to the bodies of heap functions:

prefix ## resize(argument, heap, size)
prefix ## free(argument, in_heap)
prefix ## is_full(heap)
prefix ## size(heap)
prefix ## used(heap)
prefix ## sort(heap)
prefix ## add(heap, entry)
prefix ## remove(heap, index)
prefix ## get(heap, index)

Parameters:

	scope	scope of functions
	prefix	function prefix for heap
	heaptype	type of heap
	type	type of heaped elements
	less	function or macro comparing two entries
	set	function or macro assigning entry to array
	alloc	function allocating or freeing memory
	null	empty element (returned when index is invalid)

Functions have scope scope, e.g., static inline. The heap structure has type type. The function names start with prefix, the field names start with pr. The entry type is entrytype.

The function (or macro) less compares two entries in heap. It gets two arguments and it returns true if its left argument is less than its right argument.

The function (or macro) set stores an entry in heap array. It gets three arguments, first is heap array, second index to the array and third the element to store at the given index.

The function (or macro) halloc re-allocates the heap array. It receives three arguments, first is the first argument given to resize(), second the pointer to existing heap and third is the number of bytes in the heap.

#define HEAP_DECLARE	(	scope,
		heaptype,
		prefix,
		type
	)

Value:

scope int prefix##resize(void *, heaptype *, size_t); \
scope int prefix##free(void *, heaptype *); \
scope int prefix##is_full(heaptype const); \
scope size_t prefix##size(heaptype const); \
scope size_t prefix##used(heaptype const); \
scope void prefix##sort(heaptype); \
scope int prefix##add(heaptype, type); \
scope type prefix##remove(heaptype, size_t); \
scope type prefix##get(heaptype, size_t)

Prototypes for heap.

The macro HEAP_PROTOS() expands to the prototypes of heap functions:

prefix ## resize(argument, in_out_heap, size)
prefix ## free(argument, in_heap)
prefix ## is_full(heap)
prefix ## size(heap)
prefix ## used(heap)
prefix ## add(heap, entry)
prefix ## remove(heap, index)
prefix ## get(heap, index)

Parameters:

	scope	scope of functions
	heaptype	type of heap
	prefix	function prefix
	type	type of entries

The declared functions will have scope scope (for example, static or static inline). The declared function names will have prefix prefix. The heap structure has type heaptype. The heap element type is entrytype.

#define HEAP_TYPE struct { void *private; }

Declare heap structure type.

The macro HEAP_TYPE contains declaration of the heap structure.

#define SOFIA_SIP_HEAP_H

Defined when <sofia-sip/heap.h> has been included.

sofia-sip/heap.h File Reference

Defines

Detailed Description

Define Documentation