.\" $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 DESCRIPTIONThese functions implement heap\-based priority queues.  The user defines apriority scheme, and provides a function for comparison of the priorityof heap elements(see the description of the.Ft heap_higher_priority_funcfunction pointer, below)..PpEach of the functions depends upon the.Ft heap_contexttype, which is a pointer to a.Ft struct heap_context .Pq see Pa heap.h No for more information ..PpThe.Pa heap.hheader file also defines the following set of functionfunction pointers:.Bd -literal -offset indenttypedef int (*heap_higher_priority_func)(void *, void *);typedef void (*heap_index_func)(void *, int);typedef void (*heap_for_each_func)(void *, void *);.Ed.PpThese are pointers to user-defined functions.The .Ft heap_higher_priority_functype is a pointer to a function which compares twodifferent heap (queue) elements and returns an.Ft intwhich 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 zeroif the element indicated by the first argument is of a higher priority than that indicated by the second element, and zero otherwise.  .PpThe other two function pointers are documented in the descriptionsof .Fn heap_new.Pq Va heap_index_funcand.Fn heap_for_each.Pq Va heap_for_each_func ,below..PpThe function.Fn heap_newinitializes a .Ft struct heap_contextand returns a pointer to it.  The.Fa higher_priorityfunction 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 differentqueue or heap elements; see above for more information. The second argument, .Fa index ,is a pointer to a user-defined function whose arguments area heap element and its index in the heap..Fa Index is intended to provide the user a means of knowing the internal indexof 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_deleteor.Fn heap_element ,the user .Fa indexfunction could store the index in the heap element, itself.  If .Fa indexis .No non\- Ns Dv NULL ,then it is called .Em whenever the index of an element changes, allowing the user to stay up\-to\-datewith index changes.The last argument, .Fa array_size_incrementwill be used, as its name suggests, by.Xr malloc 3or.Xr realloc 3to increment the array which implements the heap; if zero, a default value will be used..PpThe.Fn heap_freefunction frees the given.Ft heap_contextargument .Pq Fa ctx ,which also frees the entire.Nm heap ,if it is.No non\- Ns Dv NULL .The argument.Fa ctxshould be.No non\- Ns Dv NULL ..PpThe .Fn heap_insertfunction is used to insert the new heap element.Fa eltinto the appropriate place (priority\-wise) in the.Ft heapindicated by .Fa ctx(a pointer to a.Ft heap_context ) .If .No non\- Ns Dv NULL ,the user-defined.Ft higher_priorityfunction pointer associated with the indicated .Nm heapis used to determine that.Dq appropriate place ;the highest\-priority elements are at the front of the queue (top ofthe heap).(See the description of .Fn heap_new , above, for more information.).PpThe function.Fn heap_deleteis used to delete the .Fa i\- Ns thelement of the queue (heap), and fixing up the queue (heap) from thatelement onward via the priority as determined by the user functionpointed to by.Ft higher_priority function pointer(see description of.Fn heap_new ,above)..Pp.Fn heap_increased.Pp.Fn heap_decreased.PpThe .Fn heap_elementfunction returns the.Fa i\- Ns thelement of the queue/heap indicated by.Fa ctx ,if possible..PpThe.Fn heap_for_eachfunction provides a mechanism for the user to increment through the entirequeue (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 ofwhich should be interpreted by the user's function as a heap element.  The second value passed to the user function is just the.Fa uapargument to .Fn heap_for_each ;this allows the user to specify additional arguments, if necessary, tothe 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 NULLif unable to .Xr malloc 3a .Ft struct heap_contextor if the.Fa higher_priorityfunction pointer is .Dv NULL ;otherwise, a valid.Ft heap_context .Ns ..It Fn heap_free-1 if .Fa ctxis .Dv NULL (with .Va errnoset to.Dv EINVAL ) ;otherwise, 0..It Fn heap_insert-1 if either.Fa ctxor .Fa eltis .Dv NULL ,or if an attempt to .Xr malloc 3or .Xr realloc 3the heap array fails (with.Va errnoset to .Dv EINVALor .Dv ENOMEM ,respectively).Otherwise, 0..It Fn heap_delete-1 if .Fa ctxis .Dv NULLor .Fa i is out\-of\-range (with.Va errnoset to.Dv EINVAL ) ;0 otherwise..It Fn heap_increasedAs for.Fn heap_delete ..It Fn heap_decreasedAs for.Fn heap_delete ..It Fn heap_elementNULL if .Fa ctx is .Dv NULLor.Fa iout\-of-bounds (with.Va errnoset to.Dv EINVAL ) ;otherwise, a pointer to the.Fa i\- Ns thqueue element..It Fn heap_for_each-1 if either.Fa ctxor .Fa actionis .Dv NULL(with .Va errnoset 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 DIAGNOSTICSPlease refer to.Sx RETURN VALUES ..\" The next request is for sections 2 and 3 error.\" and signal handling only..Sh ERRORSThe variable.Va errnois 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 EINVALor 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 AUTHORSThe.Nm heaplibrary was implemented by Bob Halley (halley@vix.com) of Vixie Enterprises, Inc., for the Internet Software consortium, and was adapted fromthe two books listed in the .Sx SEE ALSOsection, above..\" .Sh BUGS