1.\" Id: heap.mdoc,v 1.3 2004/03/09 06:30:08 marka Exp 2.\" 3.\" Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC") 4.\" Copyright (c) 1997,1999 by Internet Software Consortium. 5.\" 6.\" Permission to use, copy, modify, and distribute this software for any 7.\" purpose with or without fee is hereby granted, provided that the above 8.\" copyright notice and this permission notice appear in all copies. 9.\" 10.\" THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES 11.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR 13.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT 16.\" OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17.\" 18.Dd January 1, 1997 19.\"Os OPERATING_SYSTEM [version/release] 20.Os BSD 4 21.Dt HEAP @SYSCALL_EXT@ 22.Sh NAME 23.Nm heap_new , 24.Nm heap_free , 25.Nm heap_insert , 26.Nm heap_delete , 27.Nm heap_increased , 28.Nm heap_decreased , 29.Nm heap_element , 30.Nm heap_for_each 31.Nd heap implementation of priority queues 32.Sh SYNOPSIS 33.Fd #include \&"heap.h\&" 34.Ft heap_context 35.Fn heap_new "heap_higher_priority_func higher_priority" \ 36"heap_index_func index" "int array_size_increment" 37.Ft int 38.Fn heap_free "heap_context ctx" 39.Ft int 40.Fn heap_insert "heap_context ctx" "void *elt" 41.Ft int 42.Fn heap_delete "heap_context ctx" "int i" 43.Ft int 44.Fn heap_increased "heap_context ctx" "int i" 45.Ft int 46.Fn heap_decreased "heap_context ctx" "int i" 47.Ft void * 48.Fn heap_element "heap_context ctx" "int i" 49.Ft int 50.Fn heap_for_each "heap_context ctx" "heap_for_each_func action" "void *uap" 51.Sh DESCRIPTION 52These functions implement heap\-based priority queues. The user defines a 53priority scheme, and provides a function for comparison of the priority 54of heap elements 55(see the description of the 56.Ft heap_higher_priority_func 57function pointer, below). 58.Pp 59Each of the functions depends upon the 60.Ft heap_context 61type, which is a pointer to a 62.Ft struct heap_context 63.Pq see Pa heap.h No for more information . 64.Pp 65The 66.Pa heap.h 67header file also defines the following set of function 68function pointers: 69.Bd -literal -offset indent 70typedef int (*heap_higher_priority_func)(void *, void *); 71typedef void (*heap_index_func)(void *, int); 72typedef void (*heap_for_each_func)(void *, void *); 73.Ed 74.Pp 75These are pointers to user-defined functions. 76The 77.Ft heap_higher_priority_func 78type is a pointer to a function which compares two 79different heap (queue) elements and returns an 80.Ft int 81which answers the question, "Does the first queue element 82have a higher priority than the second?" In other words, 83a function pointer of this type 84.Em must 85return a number greater than zero 86if the element indicated by the first argument is of a higher priority than 87that indicated by the second element, and zero otherwise. 88.Pp 89The other two function pointers are documented in the descriptions 90of 91.Fn heap_new 92.Pq Va heap_index_func 93and 94.Fn heap_for_each 95.Pq Va heap_for_each_func , 96below. 97.Pp 98The function 99.Fn heap_new 100initializes a 101.Ft struct heap_context 102and returns a pointer to it. The 103.Fa higher_priority 104function pointer 105.Em must 106be 107.No non\- Ns Dv NULL . 108As explained above, this refers to a 109function supplied by the user which compares the priority of two different 110queue or heap elements; see above for more information. 111The second argument, 112.Fa index , 113is a pointer to a user-defined function whose arguments are 114a heap element and its index in the heap. 115.Fa Index 116is intended to provide the user a means of knowing the internal index 117of an element in the heap while maintaining the opacity of the implementation; 118since the user has to know the actual indexes of heap elements in order to use, 119e.g., 120.Fn heap_delete 121or 122.Fn heap_element , 123the user 124.Fa index 125function could store the index in the heap element, itself. If 126.Fa index 127is 128.No non\- Ns Dv NULL , 129then it is called 130.Em whenever 131the index of an element changes, allowing the user to stay up\-to\-date 132with index changes. 133The last argument, 134.Fa array_size_increment 135will be used, as its name suggests, by 136.Xr malloc 3 137or 138.Xr realloc 3 139to increment the array which implements the heap; if zero, a default value 140will be used. 141.Pp 142The 143.Fn heap_free 144function frees the given 145.Ft heap_context 146argument 147.Pq Fa ctx , 148which also frees the entire 149.Nm heap , 150if it is 151.No non\- Ns Dv NULL . 152The argument 153.Fa ctx 154should be 155.No non\- Ns Dv NULL . 156.Pp 157The 158.Fn heap_insert 159function is used to insert the new heap element 160.Fa elt 161into the appropriate place (priority\-wise) in the 162.Ft heap 163indicated by 164.Fa ctx 165(a pointer to a 166.Ft heap_context ) . 167If 168.No non\- Ns Dv NULL , 169the user-defined 170.Ft higher_priority 171function pointer associated with the indicated 172.Nm heap 173is used to determine that 174.Dq appropriate place ; 175the highest\-priority elements are at the front of the queue (top of 176the heap). 177(See the description of 178.Fn heap_new , 179above, for more information.) 180.Pp 181The function 182.Fn heap_delete 183is used to delete the 184.Fa i\- Ns th 185element of the queue (heap), and fixing up the queue (heap) from that 186element onward via the priority as determined by the user function 187pointed to by 188.Ft higher_priority 189function pointer 190(see description of 191.Fn heap_new , 192above). 193.Pp 194.Fn heap_increased 195.Pp 196.Fn heap_decreased 197.Pp 198The 199.Fn heap_element 200function returns the 201.Fa i\- Ns th 202element of the queue/heap indicated by 203.Fa ctx , 204if possible. 205.Pp 206The 207.Fn heap_for_each 208function provides a mechanism for the user to increment through the entire 209queue (heap) and perform some 210.Fa action 211upon each of the queue elements. This 212.Fa action 213is pointer to a user\-defined function with two arguments, the first of 214which should be interpreted by the user's function as a heap element. The 215second value passed to the user function is just the 216.Fa uap 217argument to 218.Fn heap_for_each ; 219this allows the user to specify additional arguments, if necessary, to 220the function pointed to by 221.Fa action . 222.\" The following requests should be uncommented and 223.\" used where appropriate. This next request is 224.\" for sections 2 and 3 function return values only. 225.Sh RETURN VALUES 226.Bl -tag -width "heap_decreased()" 227.It Fn heap_new 228.Dv NULL 229if unable to 230.Xr malloc 3 231a 232.Ft struct heap_context 233or if the 234.Fa higher_priority 235function pointer is 236.Dv NULL ; 237otherwise, a valid 238.Ft heap_context 239.Ns . 240.It Fn heap_free 241-1 if 242.Fa ctx 243is 244.Dv NULL 245(with 246.Va errno 247set to 248.Dv EINVAL ) ; 249otherwise, 0. 250.It Fn heap_insert 251-1 252if either 253.Fa ctx 254or 255.Fa elt 256is 257.Dv NULL , 258or if an attempt to 259.Xr malloc 3 260or 261.Xr realloc 3 262the heap array fails (with 263.Va errno 264set to 265.Dv EINVAL 266or 267.Dv ENOMEM , 268respectively). 269Otherwise, 0. 270.It Fn heap_delete 271-1 if 272.Fa ctx 273is 274.Dv NULL 275or 276.Fa i 277is out\-of\-range (with 278.Va errno 279set to 280.Dv EINVAL ) ; 2810 otherwise. 282.It Fn heap_increased 283As for 284.Fn heap_delete . 285.It Fn heap_decreased 286As for 287.Fn heap_delete . 288.It Fn heap_element 289NULL if 290.Fa ctx 291is 292.Dv NULL 293or 294.Fa i 295out\-of-bounds (with 296.Va errno 297set to 298.Dv EINVAL ) ; 299otherwise, a pointer to the 300.Fa i\- Ns th 301queue element. 302.It Fn heap_for_each 303-1 if either 304.Fa ctx 305or 306.Fa action 307is 308.Dv NULL 309(with 310.Va errno 311set to 312.Dv EINVAL ) ; 3130 otherwise. 314.El 315.\" This next request is for sections 1, 6, 7 & 8 only 316.\" .Sh ENVIRONMENT 317.Sh FILES 318.Bl -tag -width "heap.h000" 319.It Pa heap.h 320 heap library header file 321.El 322.\" .Sh EXAMPLES 323.\" This next request is for sections 1, 6, 7 & 8 only 324.\" (command return values (to shell) and 325.\" fprintf/stderr type diagnostics) 326.Sh DIAGNOSTICS 327Please refer to 328.Sx RETURN VALUES . 329.\" The next request is for sections 2 and 3 error 330.\" and signal handling only. 331.Sh ERRORS 332The variable 333.Va errno 334is set by 335.Fn heap_free , 336.Fn heap_insert , 337.Fn heap_delete , 338.Fn heap_increased , 339and 340.Fn heap_decreased 341under the conditions of invalid input 342.Pq Dv EINVAL 343or lack of memory 344.Pq Dv ENOMEM ; 345please refer to 346.Sx RETURN VALUES . 347.Sh SEE ALSO 348.Xr malloc 3 , 349.Xr realloc 3 . 350.Rs 351.%A Cormen 352.%A Leiserson 353.%A Rivest 354.%B Introduction to Algorithms 355.%Q "MIT Press / McGraw Hill" 356.%D 1990 357.%O ISBN 0\-262\-03141\-8 358.%P chapter 7 359.Re 360.Rs 361.%A Sedgewick 362.%B Algorithms, 2nd ed'n 363.%Q Addison\-Wesley 364.%D 1988 365.%O ISBN 0\-201\-06673\-4 366.%P chapter 11 367.Re 368.\" .Sh STANDARDS 369.\" .Sh HISTORY 370.Sh AUTHORS 371The 372.Nm heap 373library was implemented by Bob Halley (halley@vix.com) of Vixie Enterprises, 374Inc., for the Internet Software consortium, and was adapted from 375the two books listed in the 376.Sx SEE ALSO 377section, above. 378.\" .Sh BUGS 379