diff options
Diffstat (limited to 'contrib/bind9/lib/bind/isc/heap.mdoc')
| -rw-r--r-- | contrib/bind9/lib/bind/isc/heap.mdoc | 378 |
1 files changed, 378 insertions, 0 deletions
diff --git a/contrib/bind9/lib/bind/isc/heap.mdoc b/contrib/bind9/lib/bind/isc/heap.mdoc new file mode 100644 index 0000000..95c9444 --- /dev/null +++ b/contrib/bind9/lib/bind/isc/heap.mdoc @@ -0,0 +1,378 @@ +.\" $Id: heap.mdoc,v 1.1.2.1.10.1 2004/03/09 08:33:43 marka Exp $ +.\" +.\" Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC") +.\" Copyright (c) 1997,1999 by Internet Software Consortium. +.\" +.\" Permission to use, copy, modify, and distribute this software for any +.\" purpose with or without fee is hereby granted, provided that the above +.\" copyright notice and this permission notice appear in all copies. +.\" +.\" THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES +.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF +.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR +.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN +.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT +.\" OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. +.\" +.Dd January 1, 1997 +.\"Os OPERATING_SYSTEM [version/release] +.Os BSD 4 +.Dt HEAP @SYSCALL_EXT@ +.Sh NAME +.Nm heap_new , +.Nm heap_free , +.Nm heap_insert , +.Nm heap_delete , +.Nm heap_increased , +.Nm heap_decreased , +.Nm heap_element , +.Nm heap_for_each +.Nd heap implementation of priority queues +.Sh SYNOPSIS +.Fd #include \&"heap.h\&" +.Ft heap_context +.Fn heap_new "heap_higher_priority_func higher_priority" \ +"heap_index_func index" "int array_size_increment" +.Ft int +.Fn heap_free "heap_context ctx" +.Ft int +.Fn heap_insert "heap_context ctx" "void *elt" +.Ft int +.Fn heap_delete "heap_context ctx" "int i" +.Ft int +.Fn heap_increased "heap_context ctx" "int i" +.Ft int +.Fn heap_decreased "heap_context ctx" "int i" +.Ft void * +.Fn heap_element "heap_context ctx" "int i" +.Ft int +.Fn heap_for_each "heap_context ctx" "heap_for_each_func action" "void *uap" +.Sh 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 +.Ft heap_higher_priority_func +function pointer, below). +.Pp +Each of the functions depends upon the +.Ft heap_context +type, which is a pointer to a +.Ft struct heap_context +.Pq see Pa heap.h No for more information . +.Pp +The +.Pa heap.h +header file also defines the following set of function +function pointers: +.Bd -literal -offset indent +typedef int (*heap_higher_priority_func)(void *, void *); +typedef void (*heap_index_func)(void *, int); +typedef void (*heap_for_each_func)(void *, void *); +.Ed +.Pp +These are pointers to user-defined functions. +The +.Ft heap_higher_priority_func +type is a pointer to a function which compares two +different heap (queue) elements and returns an +.Ft 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 +.Em 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. +.Pp +The other two function pointers are documented in the descriptions +of +.Fn heap_new +.Pq Va heap_index_func +and +.Fn heap_for_each +.Pq Va heap_for_each_func , +below. +.Pp +The function +.Fn heap_new +initializes a +.Ft struct heap_context +and returns a pointer to it. The +.Fa higher_priority +function pointer +.Em must +be +.No non\- Ns Dv 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, +.Fa index , +is a pointer to a user-defined function whose arguments are +a heap element and its index in the heap. +.Fa 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., +.Fn heap_delete +or +.Fn heap_element , +the user +.Fa index +function could store the index in the heap element, itself. If +.Fa index +is +.No non\- Ns Dv NULL , +then it is called +.Em whenever +the index of an element changes, allowing the user to stay up\-to\-date +with index changes. +The last argument, +.Fa array_size_increment +will be used, as its name suggests, by +.Xr malloc 3 +or +.Xr realloc 3 +to increment the array which implements the heap; if zero, a default value +will be used. +.Pp +The +.Fn heap_free +function frees the given +.Ft heap_context +argument +.Pq Fa ctx , +which also frees the entire +.Nm heap , +if it is +.No non\- Ns Dv NULL . +The argument +.Fa ctx +should be +.No non\- Ns Dv NULL . +.Pp +The +.Fn heap_insert +function is used to insert the new heap element +.Fa elt +into the appropriate place (priority\-wise) in the +.Ft heap +indicated by +.Fa ctx +(a pointer to a +.Ft heap_context ) . +If +.No non\- Ns Dv NULL , +the user-defined +.Ft higher_priority +function pointer associated with the indicated +.Nm heap +is used to determine that +.Dq appropriate place ; +the highest\-priority elements are at the front of the queue (top of +the heap). +(See the description of +.Fn heap_new , +above, for more information.) +.Pp +The function +.Fn heap_delete +is used to delete the +.Fa i\- Ns 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 +.Ft higher_priority +function pointer +(see description of +.Fn heap_new , +above). +.Pp +.Fn heap_increased +.Pp +.Fn heap_decreased +.Pp +The +.Fn heap_element +function returns the +.Fa i\- Ns th +element of the queue/heap indicated by +.Fa ctx , +if possible. +.Pp +The +.Fn heap_for_each +function provides a mechanism for the user to increment through the entire +queue (heap) and perform some +.Fa action +upon each of the queue elements. This +.Fa 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 +.Fa uap +argument to +.Fn heap_for_each ; +this allows the user to specify additional arguments, if necessary, to +the function pointed to by +.Fa action . +.\" The following requests should be uncommented and +.\" used where appropriate. This next request is +.\" for sections 2 and 3 function return values only. +.Sh RETURN VALUES +.Bl -tag -width "heap_decreased()" +.It Fn heap_new +.Dv NULL +if unable to +.Xr malloc 3 +a +.Ft struct heap_context +or if the +.Fa higher_priority +function pointer is +.Dv NULL ; +otherwise, a valid +.Ft heap_context +.Ns . +.It Fn heap_free +-1 if +.Fa ctx +is +.Dv NULL +(with +.Va errno +set to +.Dv EINVAL ) ; +otherwise, 0. +.It Fn heap_insert +-1 +if either +.Fa ctx +or +.Fa elt +is +.Dv NULL , +or if an attempt to +.Xr malloc 3 +or +.Xr realloc 3 +the heap array fails (with +.Va errno +set to +.Dv EINVAL +or +.Dv ENOMEM , +respectively). +Otherwise, 0. +.It Fn heap_delete +-1 if +.Fa ctx +is +.Dv NULL +or +.Fa i +is out\-of\-range (with +.Va errno +set to +.Dv EINVAL ) ; +0 otherwise. +.It Fn heap_increased +As for +.Fn heap_delete . +.It Fn heap_decreased +As for +.Fn heap_delete . +.It Fn heap_element +NULL if +.Fa ctx +is +.Dv NULL +or +.Fa i +out\-of-bounds (with +.Va errno +set to +.Dv EINVAL ) ; +otherwise, a pointer to the +.Fa i\- Ns th +queue element. +.It Fn heap_for_each +-1 if either +.Fa ctx +or +.Fa action +is +.Dv NULL +(with +.Va errno +set to +.Dv EINVAL ) ; +0 otherwise. +.El +.\" This next request is for sections 1, 6, 7 & 8 only +.\" .Sh ENVIRONMENT +.Sh FILES +.Bl -tag -width "heap.h000" +.It Pa heap.h + heap library header file +.El +.\" .Sh EXAMPLES +.\" This next request is for sections 1, 6, 7 & 8 only +.\" (command return values (to shell) and +.\" fprintf/stderr type diagnostics) +.Sh DIAGNOSTICS +Please refer to +.Sx RETURN VALUES . +.\" The next request is for sections 2 and 3 error +.\" and signal handling only. +.Sh ERRORS +The variable +.Va errno +is set by +.Fn heap_free , +.Fn heap_insert , +.Fn heap_delete , +.Fn heap_increased , +and +.Fn heap_decreased +under the conditions of invalid input +.Pq Dv EINVAL +or lack of memory +.Pq Dv ENOMEM ; +please refer to +.Sx RETURN VALUES . +.Sh SEE ALSO +.Xr malloc 3 , +.Xr realloc 3 . +.Rs +.%A Cormen +.%A Leiserson +.%A Rivest +.%B Introduction to Algorithms +.%Q "MIT Press / McGraw Hill" +.%D 1990 +.%O ISBN 0\-262\-03141\-8 +.%P chapter 7 +.Re +.Rs +.%A Sedgewick +.%B Algorithms, 2nd ed'n +.%Q Addison\-Wesley +.%D 1988 +.%O ISBN 0\-201\-06673\-4 +.%P chapter 11 +.Re +.\" .Sh STANDARDS +.\" .Sh HISTORY +.Sh AUTHORS +The +.Nm 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 +.Sx SEE ALSO +section, above. +.\" .Sh BUGS |
