| blob | 332a6ec5d079fdfd85df9b8360f8aeaab0c69321 |
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