Loading...
Searching...
No Matches
heap.h File Reference

Heap template implemented with dynamic array. More...

`#include <sofia-sip/su_types.h>`
Include dependency graph for heap.h:

Go to the source code of this file.

## Macros

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

## Functions

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))
| Sort array using smoothsort.

## 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.nosp@m..Pes.nosp@m.si@no.nosp@m.kia..nosp@m.com.

Since
  New in 1.12.7.

## Macro Definition Documentation

## HEAP_BODIES

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

## HEAP_DECLARE

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

## HEAP_TYPE

#define HEAP_TYPE struct { void *private; }

Declare heap structure type.

The macro HEAP_TYPE contains declaration of the heap structure.

## Function Documentation

## su_smoothsort()

void su_smoothsort | ( | void * | base,
|  | size_t | r,
|  | size_t | N,
|  | int(* | less )(void *m, size_t a, size_t b),
|  | void(* | swap )(void *m, size_t a, size_t b) )

Sort array using smoothsort.

Sort N elements from array base starting with index r with smoothsort.

Parameters

  base | pointer to array
  r | lowest index to sort
  N | number of elements to sort
  less | comparison function returning nonzero if m[a] < m[b]
  swap | swapper function exchanging elements m[a] and m[b]

Sofia-SIP 1.12.11devel - Copyright (C) 2006 Nokia Corporation. All rights reserved. Licensed under the terms of the GNU Lesser General Public License.