HEAP(3)

NAME
heap - procedures for managing sorted heaps in libmagicutils.a

SYNOPSIS
#include magic.h
#include heap.h

typedef struct { int he_key, char *he_id; } HeapEntry;

bool HEAP_EMPTY(h)
Heap *h;

HeapInit(h, initsize, descending, stringids)
Heap *h;
int initsize;
bool descending, stringids;

HeapKill(h, func)
Heap *h;
int (*func)(h, index);

HeapFreeIdFunc(h, index)
Heap *h;
int index;

HeapEntry *HeapRemoveTop(h, entry);
Heap *h;
HeapEntry *entry;

HeapAdd(h, key, id)
Heap *h;
int key;
char *id;

DESCRIPTION
These procedures create, manipulate, and destroy heaps. A heap is essentially an array that automatically sorts itself when items are added to it. The items added to the heap consist of an integer key and a one-word datum which can either be the address of a NULL-terminated string (treated specially), or any other one-word data item. Heaps can be sorted in either ascending or descending order. The data storage for a heap automatically grows as more elements are added to the heap.

The HeapEntry structure identifies the integer key value (he_key) on which the element is sorted, and a one-word datum (he_id). Heaps are created by HeapInit, which initializes the data storage for h. Enough space is left initially for initsize elements, although the heap will grow automatically as more elements are added. If descending is TRUE, the largest element in the heap will be removed first; otherwise, the smallest element will be the first to be removed by HeapRemoveTop. Each heap entry has an associated datum or id; if stringids is TRUE, these are considered to be ASCII strings and handled specially by HeapAdd and HeapKill.

HeapKill deallocates the storage associated with a heap. If func is non-NULL, it is applied to each element in the heap. A common use of func is to free the storage associated with string ids in the heap, such as is necessary when the heap was created with stringids set to TRUE in the call to HeapInit above. A library function, HeapFreeIdFunc, is provided for this purpose.

HeapRemoveTop places the top element from h in the HeapEntry pointed to by entry and returns entry. However, if the heap was empty, HeapRemoveTop returns NULL. HeapRemoveTop always removes the smallest (if keys are ascending) or largest (if keys are descending) element from the heap.

HeapAdd is used to add a new entry to h. The new entry has an integer key of key, and a value of id. If the heap was created with stringids to be TRUE in HeapInit, then id is interpreted as a NULL-terminated ASCII string; sufficient additional memory to hold this string is allocated, the string is copied into this new memory, and a pointer to this new memory is stored with the heap entry. Otherwise, the value of id is just stored directly in the heap entry.

BUGS
The management of the he_id field should be consistent with the management of keys for hash tables, i.e, multi-word structures should be supported along with strings and single-word values.

SEE ALSO
magicutils(3)