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, 0 insertions, 378 deletions
diff --git a/contrib/bind9/lib/bind/isc/heap.mdoc b/contrib/bind9/lib/bind/isc/heap.mdoc deleted file mode 100644 index 332a6ec5d079..000000000000 --- a/contrib/bind9/lib/bind/isc/heap.mdoc +++ /dev/null @@ -1,378 +0,0 @@ -.\" $Id: heap.mdoc,v 1.3 2004/03/09 06:30:08 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 |