HEAP(@SYSCALL_EXT@)

NAME
heap_new, heap_free, heap_insert, heap_delete, heap_increased, heap_decreased, heap_element, heap_for_each - heap implementation of priority queues

SYNOPSIS
#include "heap.h"
heap_context
heap_new(heap_higher_priority_func higher_priority, heap_index_func index, int array_size_increment);
int
heap_free(heap_context ctx);
int
heap_insert(heap_context ctx, void *elt);
int
heap_delete(heap_context ctx, int i);
int
heap_increased(heap_context ctx, int i);
int
heap_decreased(heap_context ctx, int i);
void *
heap_element(heap_context ctx, int i);
int
heap_for_each(heap_context ctx, heap_for_each_func action, void *uap);

DESCRIPTION
These functions implement heap-based priority queues. The user defines a priority scheme, and provides a function for comparison of the priority of heap elements (see the description of the heap_higher_priority_func function pointer, below).

Each of the functions depends upon the heap_context type, which is a pointer to a struct heap_context (see heap.h for more information).

The heap.h header file also defines the following set of function function pointers:

    typedef int (*heap_higher_priority_func)(void *, void *);
    typedef void (*heap_index_func)(void *, int);
    typedef void (*heap_for_each_func)(void *, void *);

These are pointers to user-defined functions. The heap_higher_priority_func type is a pointer to a function which compares two different heap (queue) elements and returns an int which answers the question, "Does the first queue element have a higher priority than the second?" In other words, a function pointer of this type must return a number greater than zero if the element indicated by the first argument is of a higher priority than that indicated by the second element, and zero otherwise.

The other two function pointers are documented in the descriptions of heap_new() (heap_index_func) and heap_for_each() (heap_for_each_func), below.

The function heap_new() initializes a struct heap_context and returns a pointer to it. The higher_priority function pointer must be non-NULL. As explained above, this refers to a function supplied by the user which compares the priority of two different queue or heap elements; see above for more information. The second argument, index, is a pointer to a user-defined function whose arguments are a heap element and its index in the heap. Index is intended to provide the user a means of knowing the internal index of an element in the heap while maintaining the opacity of the implementation; since the user has to know the actual indexes of heap elements in order to use, e.g., heap_delete() or heap_element(), the user index function could store the index in the heap element, itself. If index is non-NULL, then it is called whenever the index of an element changes, allowing the user to stay up-to-date with index changes. The last argument, array_size_increment will be used, as its name suggests, by malloc(3) or realloc(3) to increment the array which implements the heap; if zero, a default value will be used.

The heap_free() function frees the given heap_context argument (ctx), which also frees the entire heap, if it is non-NULL. The argument ctx should be non-NULL.

The heap_insert() function is used to insert the new heap element elt into the appropriate place (priority-wise) in the heap indicated by ctx (a pointer to a heap_context). If non-NULL, the user-defined higher_priority function pointer associated with the indicated heap is used to determine that “appropriate place”; the highest-priority elements are at the front of the queue (top of the heap). (See the description of heap_new(), above, for more information.)

The function heap_delete() is used to delete the i-th element of the queue (heap), and fixing up the queue (heap) from that element onward via the priority as determined by the user function pointed to by higher_priority function pointer (see description of heap_new,() above).

heap_increased()

heap_decreased()

The heap_element() function returns the i-th element of the queue/heap indicated by ctx, if possible.

The heap_for_each() function provides a mechanism for the user to increment through the entire queue (heap) and perform some action upon each of the queue elements. This action is pointer to a user-defined function with two arguments, the first of which should be interpreted by the user's function as a heap element. The second value passed to the user function is just the uap argument to heap_for_each(); this allows the user to specify additional arguments, if necessary, to the function pointed to by action.

RETURN VALUES

heap_new()
    NULL if unable to malloc(3) a struct heap_context or if the higher_priority function pointer is NULL; otherwise, a valid heap_context.

heap_free()
    -1 if ctx is NULL (with errno set to EINVAL); otherwise, 0.

heap_insert()
    -1 if either ctx or elt is NULL, or if an attempt to malloc(3) or realloc(3) the heap array fails (with errno set to EINVAL or ENOMEM, respectively). Otherwise, 0.

heap_delete()
    -1 if ctx is NULL or i is out-of-range (with errno set to EINVAL); 0 otherwise.

heap_increased()
    As for heap_delete().

heap_decreased()
    As for heap_delete().

heap_element()
    NULL if ctx is NULL or i out-of-bounds (with errno set to EINVAL); otherwise, a pointer to the i-th queue element.

heap_for_each()
    -1 if either ctx or action is NULL (with errno set to EINVAL); 0 otherwise.

FILES

heap.h
    heap library header file

DIAGNOSTICS
Please refer to RETURN VALUES.

ERRORS
The variable errno is set by heap_free(), heap_insert(), heap_delete(), heap_increased(), and heap_decreased() under the conditions of invalid input (EINVAL) or lack of memory (ENOMEM); please refer to RETURN VALUES.

SEE ALSO
malloc(3), realloc(3).

Cormen, Leiserson, and Rivest, Introduction to Algorithms, MIT Press / McGraw Hill, 1990, ISBN 0-262-03141-8, chapter 7.

Sedgewick, Algorithms, 2nd ed'n, Addison-Wesley, 1988, ISBN 0-201-06673-4, chapter 11.

AUTHORS
The heap library was implemented by Bob Halley (halley@vix.com) of Vixie Enterprises, Inc., for the Internet Software consortium, and was adapted from the two books listed in the SEE ALSO section, above.