heap_new, heap_free, heap_insert, heap_delete, heap_increased,
heap_decreased, heap_element, heap_for_each -- heap implementation of
priority queues
#include <isc/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);
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.
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.
heap.h heap library header file
Please refer to RETURN VALUES.
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.
malloc(3), realloc(3).
Cormen, Leiserson, and Rivest, Introduction to Algorithms, chapter 7, MIT
Press / McGraw Hill, 1990, ISBN 0-262-03141-8.
Sedgewick, Algorithms, 2nd ed'n, chapter 11, Addison-Wesley, 1988, ISBN
0-201-06673-4.
The heap library was implemented by Bob Halley ([email protected]) of Vixie
Enterprises, Inc., for the Internet Software consortium, and was adapted
from the two books listed in the SEE ALSO section, above.
4th Berkeley Distribution January 1, 1997 4th Berkeley Distribution
[ Back ] |
