Flatten bind9 vendor work area

1 files changed, 378 insertions, 0 deletions

diff --git a/lib/bind/isc/heap.mdoc b/lib/bind/isc/heap.mdoc
new file mode 100644
index 0000000..332a6ec
--- /dev/null
+++ b/lib/bind/isc/heap.mdoc
@@ -0,0 +1,378 @@
+.\" $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