contrib/bind/lib/bind/isc/heap.mdoc

   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
  52 These functions implement heap\-based priority queues.  The user defines a
  53 priority scheme, and provides a function for comparison of the priority
  54 of heap elements
  55 (see the description of the
  56 .Ft heap_higher_priority_func
  57 function pointer, below).
  58 .Pp
  59 Each of the functions depends upon the
  60 .Ft heap_context
  61 type, which is a pointer to a
  62 .Ft struct heap_context
  63 .Pq see Pa heap.h No for more information .
  64 .Pp
  65 The
  66 .Pa heap.h
  67 header file also defines the following set of function
  68 function pointers:
  69 .Bd -literal -offset indent
  70 typedef int (*heap_higher_priority_func)(void *, void *);
  71 typedef void (*heap_index_func)(void *, int);
  72 typedef void (*heap_for_each_func)(void *, void *);
  73 .Ed
  74 .Pp
  75 These are pointers to user-defined functions.
  76 The
  77 .Ft heap_higher_priority_func
  78 type is a pointer to a function which compares two
  79 different heap (queue) elements and returns an
  80 .Ft int
  81 which answers the question, "Does the first queue element
  82 have a higher priority than the second?"  In other words,
  83 a function pointer of this type
  84 .Em must
  85 return a number greater than zero
  86 if the element indicated by the first argument is of a higher priority than
  87 that indicated by the second element, and zero otherwise.
  88 .Pp
  89 The other two function pointers are documented in the descriptions
  90 of
  91 .Fn heap_new
  92 .Pq Va heap_index_func
  93 and
  94 .Fn heap_for_each
  95 .Pq Va heap_for_each_func ,
  96 below.
  97 .Pp
  98 The function
  99 .Fn heap_new
 100 initializes a
 101 .Ft struct heap_context
 102 and returns a pointer to it.  The
 103 .Fa higher_priority
 104 function pointer
 105 .Em must
 106 be
 107 .No non\- Ns Dv NULL .
 108 As explained above, this refers to a
 109 function supplied by the user which compares the priority of two different
 110 queue or heap elements; see above for more information.
 111 The second argument,
 112 .Fa index ,
 113 is a pointer to a user-defined function whose arguments are
 114 a heap element and its index in the heap.
 115 .Fa Index
 116 is intended to provide the user a means of knowing the internal index
 117 of an element in the heap while maintaining the opacity of the implementation;
 118 since the user has to know the actual indexes of heap elements in order to use,
 119 e.g.,
 120 .Fn heap_delete
 121 or
 122 .Fn heap_element ,
 123 the user
 124 .Fa index
 125 function could store the index in the heap element, itself.  If
 126 .Fa index
 127 is
 128 .No non\- Ns Dv NULL ,
 129 then it is called
 130 .Em whenever
 131 the index of an element changes, allowing the user to stay up\-to\-date
 132 with index changes.
 133 The last argument,
 134 .Fa array_size_increment
 135 will be used, as its name suggests, by
 136 .Xr malloc 3
 137 or
 138 .Xr realloc 3
 139 to increment the array which implements the heap; if zero, a default value
 140 will be used.
 141 .Pp
 142 The
 143 .Fn heap_free
 144 function frees the given
 145 .Ft heap_context
 146 argument
 147 .Pq Fa ctx ,
 148 which also frees the entire
 149 .Nm heap ,
 150 if it is
 151 .No non\- Ns Dv NULL .
 152 The argument
 153 .Fa ctx
 154 should be
 155 .No non\- Ns Dv NULL .
 156 .Pp
 157 The
 158 .Fn heap_insert
 159 function is used to insert the new heap element
 160 .Fa elt
 161 into the appropriate place (priority\-wise) in the
 162 .Ft heap
 163 indicated by
 164 .Fa ctx
 165 (a pointer to a
 166 .Ft heap_context ) .
 167 If
 168 .No non\- Ns Dv NULL ,
 169 the user-defined
 170 .Ft higher_priority
 171 function pointer associated with the indicated
 172 .Nm heap
 173 is used to determine that
 174 .Dq appropriate place ;
 175 the highest\-priority elements are at the front of the queue (top of
 176 the heap).
 177 (See the description of
 178 .Fn heap_new ,
 179 above, for more information.)
 180 .Pp
 181 The function
 182 .Fn heap_delete
 183 is used to delete the
 184 .Fa i\- Ns th
 185 element of the queue (heap), and fixing up the queue (heap) from that
 186 element onward via the priority as determined by the user function
 187 pointed to by
 188 .Ft higher_priority
 189 function pointer
 190 (see description of
 191 .Fn heap_new ,
 192 above).
 193 .Pp
 194 .Fn heap_increased
 195 .Pp
 196 .Fn heap_decreased
 197 .Pp
 198 The
 199 .Fn heap_element
 200 function returns the
 201 .Fa i\- Ns th
 202 element of the queue/heap indicated by
 203 .Fa ctx ,
 204 if possible.
 205 .Pp
 206 The
 207 .Fn heap_for_each
 208 function provides a mechanism for the user to increment through the entire
 209 queue (heap) and perform some
 210 .Fa action
 211 upon each of the queue elements.  This
 212 .Fa action
 213 is pointer to a user\-defined function with two arguments, the first of
 214 which should be interpreted by the user's function as a heap element.  The
 215 second value passed to the user function is just the
 216 .Fa uap
 217 argument to
 218 .Fn heap_for_each ;
 219 this allows the user to specify additional arguments, if necessary, to
 220 the 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
 229 if unable to
 230 .Xr malloc 3
 231 a
 232 .Ft struct heap_context
 233 or if the
 234 .Fa higher_priority
 235 function pointer is
 236 .Dv NULL ;
 237 otherwise, a valid
 238 .Ft heap_context
 239 .Ns .
 240 .It Fn heap_free
 241 -1 if
 242 .Fa ctx
 243 is
 244 .Dv NULL
 245 (with
 246 .Va errno
 247 set to
 248 .Dv EINVAL ) ;
 249 otherwise, 0.
 250 .It Fn heap_insert
 251 -1
 252 if either
 253 .Fa ctx
 254 or
 255 .Fa elt
 256 is
 257 .Dv NULL ,
 258 or if an attempt to
 259 .Xr malloc 3
 260 or
 261 .Xr realloc 3
 262 the heap array fails (with
 263 .Va errno
 264 set to
 265 .Dv EINVAL
 266 or
 267 .Dv ENOMEM ,
 268 respectively).
 269 Otherwise, 0.
 270 .It Fn heap_delete
 271 -1 if
 272 .Fa ctx
 273 is
 274 .Dv NULL
 275 or
 276 .Fa i
 277 is out\-of\-range (with
 278 .Va errno
 279 set to
 280 .Dv EINVAL ) ;
 281 0 otherwise.
 282 .It Fn heap_increased
 283 As for
 284 .Fn heap_delete .
 285 .It Fn heap_decreased
 286 As for
 287 .Fn heap_delete .
 288 .It Fn heap_element
 289 NULL if
 290 .Fa ctx
 291 is
 292 .Dv NULL
 293 or
 294 .Fa i
 295 out\-of-bounds (with
 296 .Va errno
 297 set to
 298 .Dv EINVAL ) ;
 299 otherwise, a pointer to the
 300 .Fa i\- Ns th
 301 queue element.
 302 .It Fn heap_for_each
 303 -1 if either
 304 .Fa ctx
 305 or
 306 .Fa action
 307 is
 308 .Dv NULL
 309 (with
 310 .Va errno
 311 set to
 312 .Dv EINVAL ) ;
 313 0 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
 327 Please 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
 332 The variable
 333 .Va errno
 334 is set by
 335 .Fn heap_free ,
 336 .Fn heap_insert ,
 337 .Fn heap_delete ,
 338 .Fn heap_increased ,
 339 and
 340 .Fn heap_decreased
 341 under the conditions of invalid input
 342 .Pq Dv EINVAL
 343 or lack of memory
 344 .Pq Dv ENOMEM ;
 345 please 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
 371 The
 372 .Nm heap
 373 library was implemented by Bob Halley (halley@vix.com) of Vixie Enterprises,
 374 Inc., for the Internet Software consortium, and was adapted from
 375 the two books listed in the
 376 .Sx SEE ALSO
 377 section, above.
 378 .\" .Sh BUGS