This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

## Defines | |

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

#define | SOFIA_SIP_HEAP_H |

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

Definition in file heap.h.

Generated by Doxygen 1.6.0 Back to index