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