Print this page
6498 typo in libavl(3LIB) man page
Reviewed by: Marcel Telka <marcel@telka.sk>
Reviewed by: Yuri Pankov <yuri.pankov@nexenta.com>
| Split |
Close |
| Expand all |
| Collapse all |
--- old/usr/src/man/man3lib/libavl.3lib
+++ new/usr/src/man/man3lib/libavl.3lib
1 1 .\"
2 2 .\" This file and its contents are supplied under the terms of the
3 3 .\" Common Development and Distribution License ("CDDL"), version 1.0.
|
↓ open down ↓ |
3 lines elided |
↑ open up ↑ |
4 4 .\" You may only use this file in accordance with the terms of version
5 5 .\" 1.0 of the CDDL.
6 6 .\"
7 7 .\" A full copy of the text of the CDDL should have accompanied this
8 8 .\" source. A copy of the CDDL is also available via the Internet at
9 9 .\" http://www.illumos.org/license/CDDL.
10 10 .\"
11 11 .\"
12 12 .\" Copyright 2015 Joyent, Inc.
13 13 .\"
14 -.Dd May 07, 2015
14 +.Dd Dec 04, 2015
15 15 .Dt LIBAVL 3LIB
16 16 .Os
17 17 .Sh NAME
18 18 .Nm libavl
19 19 .Nd generic self-balancing binary search tree library
20 20 .Sh SYNOPSIS
21 21 .Lb libavl
22 22 .In sys/avl.h
23 23 .Sh DESCRIPTION
24 24 The
25 25 .Nm
26 26 library provides a generic implementation of AVL trees, a form of
27 27 self-balancing binary tree. The interfaces provided allow for an
28 28 efficient way of implementing an ordered set of data structures and, due
29 29 to its embeddable nature, allow for a single instance of a data
30 30 structure to belong to multiple AVL trees.
31 31 .Lp
32 32 Each AVL tree contains entries of a single type of data structure.
33 33 Rather than allocating memory for pointers for those data structures,
34 34 the storage for the tree is embedded into the data structures by
35 35 declaring a member of type
36 36 .Vt avl_node_t .
37 37 When an AVL tree is created, through the use of
38 38 .Fn avl_create ,
39 39 it encodes the size of the data structure, the offset of the data
40 40 structure, and a comparator function which is used to compare two
41 41 instances of a data structure. A data structure may be a member of
42 42 multiple AVL trees by creating AVL trees which use different
43 43 offsets (different members) into the data structure.
44 44 .Lp
45 45 AVL trees support both look up of an arbitrary item and ordered
46 46 iteration over the contents of the entire tree. In addition, from any
47 47 node, you can find the previous and next entries in the tree, if they
48 48 exist. In addition, AVL trees support arbitrary insertion and deletion.
49 49 .Ss Performance
50 50 AVL trees are often used in place of linked lists. Compared to the
51 51 standard, intrusive, doubly linked list, it has the following
52 52 performance characteristics:
53 53 .Bl -hang -width Ds
54 54 .It Sy Lookup One Node
55 55 .Bd -filled -compact
56 56 Lookup of a single node in a linked list is
57 57 .Sy O(n) ,
58 58 whereas lookup of a single node in an AVL tree is
59 59 .Sy O(log(n)) .
60 60 .Ed
61 61 .It Sy Insert One Node
62 62 .Bd -filled -compact
63 63 Inserting a single node into a linked list is
64 64 .Sy O(1) .
65 65 Inserting a single node into an AVL tree is
66 66 .Sy O(log(n)) .
67 67 .Pp
68 68 Note, insertions into an AVL tree always result in an ordered tree.
69 69 Insertions into a linked list do not guarantee order. If order is
70 70 required, then the time to do the insertion into a linked list will
71 71 depend on the time of the search algorithm being employed to find the
72 72 place to insert at.
73 73 .Ed
74 74 .It Sy Delete One Node
75 75 .Bd -filled -compact
76 76 Deleting a single node from a linked list is
|
↓ open down ↓ |
52 lines elided |
↑ open up ↑ |
77 77 .Sy O(1),
78 78 whereas deleting a single node from an AVL tree takes
79 79 .Sy O(log(n))
80 80 time.
81 81 .Ed
82 82 .It Sy Delete All Nodes
83 83 .Bd -filled -compact
84 84 Deleting all nodes from a linked list is
85 85 .Sy O(n) .
86 86 With an AVL tree, if using the
87 -.Xr avl_delete_nodes 3AVL
87 +.Xr avl_destroy_nodes 3AVL
88 88 function then deleting all nodes
89 89 is
90 90 .Sy O(n) .
91 91 However, if iterating over each entry in the tree and then removing it using
92 92 a while loop,
93 93 .Xr avl_first 3AVL
94 94 and
95 95 .Xr avl_remove 3AVL
96 96 then the time to remove all nodes is
97 97 .Sy O(n\ *\ log(n)).
98 98 .Ed
99 99 .It Sy Visit the Next or Previous Node
100 100 .Bd -filled -compact
101 101 Visiting the next or previous node in a linked list is
102 102 .Sy O(1) ,
103 103 whereas going from the next to the previous node in an AVL tree will
104 104 take between
105 105 .Sy O(1)
106 106 and
107 107 .Sy O(log(n)) .
108 108 .Ed
109 109 .El
110 110 .Pp
111 111 In general, AVL trees are a good alternative for linked lists when order
112 112 or lookup speed is important and a reasonable number of items will be
113 113 present.
114 114 .Sh INTERFACES
115 115 The shared object
116 116 .Sy libavl.so.1
117 117 provides the public interfaces defined below. See
118 118 .Xr Intro(3)
119 119 for additional information on shared object interfaces. Individual
120 120 functions are documented in their own manual pages.
121 121 .Bl -column -offset indent ".Sy avl_is_empty" ".Sy avl_destroy_nodes"
122 122 .It Sy avl_add Ta Sy avl_create
123 123 .It Sy avl_destroy Ta Sy avl_destroy_nodes
124 124 .It Sy avl_find Ta Sy avl_first
125 125 .It Sy avl_insert Ta Sy avl_insert_here
126 126 .It Sy avl_is_empty Ta Sy avl_last
127 127 .It Sy avl_nearest Ta Sy avl_numnodes
128 128 .It Sy avl_remove Ta Sy avl_swap
129 129 .El
130 130 .Pp
131 131 In addition, the library defines C pre-processor macros which are
132 132 defined below and documented in their own manual pages.
133 133 .\"
134 134 .\" Use the same column widths in both cases where we describe the list
135 135 .\" of interfaces, to allow the manual page to better line up when rendered.
136 136 .\"
137 137 .Bl -column -offset indent ".Sy avl_is_empty" ".Sy avl_destroy_nodes"
138 138 .It Sy AVL_NEXT Ta Sy AVL_PREV
139 139 .El
140 140 .Sh TYPES
141 141 The
142 142 .Nm
143 143 library defines the following types:
144 144 .Lp
145 145 .Sy avl_tree_t
146 146 .Lp
147 147 Type used for the root of the AVL tree. Consumers define one of these
148 148 for each of the different trees that they want to have.
149 149 .Lp
150 150 .Sy avl_node_t
151 151 .Lp
152 152 Type used as the data node for an AVL tree. One of these is embedded in
153 153 each data structure that is the member of an AVL tree.
154 154 .Lp
155 155 .Sy avl_index_t
156 156 .Lp
157 157 Type used to locate a position in a tree. This is used with
158 158 .Xr avl_find 3AVL
159 159 and
160 160 .Xr avl_insert 3AVL .
161 161 .Sh LOCKING
162 162 The
163 163 .Nm
164 164 library provides no locking. Callers that are using the same AVL tree
165 165 from multiple threads need to provide their own synchronization. If only
166 166 one thread is ever accessing or modifying the AVL tree, then there are
167 167 no synchronization concerns. If multiple AVL trees exist, then they may
168 168 all be used simultaneously; however, they are subject to the same rules
169 169 around simultaneous access from a single thread.
170 170 .Lp
171 171 All routines are both
172 172 .Sy Fork-safe
173 173 and
174 174 .Sy Async-Signal-Safe .
175 175 Callers may call functions in
176 176 .Nm
177 177 from a signal handler and
178 178 .Nm
179 179 calls are all safe in face of
180 180 .Xr fork 2 ;
181 181 however, if callers have their own locks, then they must make sure that
182 182 they are accounted for by the use of routines such as
183 183 .Xr pthread_atfork 3C .
184 184 .Sh EXAMPLES
185 185 The following code shows examples of exercising all of the functionality
186 186 that is present in
187 187 .Nm .
188 188 It can be compiled by using a C compiler and linking
189 189 against
190 190 .Nm .
191 191 For example, given a file named avl.c, with gcc, one would run:
192 192 .Bd -literal
193 193 $ gcc -Wall -o avl avl.c -lavl
194 194 .Ed
195 195 .Bd -literal
196 196 /*
197 197 * Example of using AVL Trees
198 198 */
199 199
200 200 #include <sys/avl.h>
201 201 #include <stddef.h>
202 202 #include <stdlib.h>
203 203 #include <stdio.h>
204 204
205 205 static avl_tree_t inttree;
206 206
207 207 /*
208 208 * The structure that we're storing in an AVL tree.
209 209 */
210 210 typedef struct intnode {
211 211 int in_val;
212 212 avl_node_t in_avl;
213 213 } intnode_t;
214 214
215 215 static int
216 216 intnode_comparator(const void *l, const void *r)
217 217 {
218 218 const intnode_t *li = l;
219 219 const intnode_t *ri = r;
220 220
221 221 if (li->in_val > ri->in_val)
222 222 return (1);
223 223 if (li->in_val < ri->in_val)
224 224 return (-1);
225 225 return (0);
226 226 }
227 227
228 228 /*
229 229 * Create an AVL Tree
230 230 */
231 231 static void
232 232 create_avl(void)
233 233 {
234 234 avl_create(&inttree, intnode_comparator, sizeof (intnode_t),
235 235 offsetof(intnode_t, in_avl));
236 236 }
237 237
238 238 /*
239 239 * Add entries to the tree with the avl_add function.
240 240 */
241 241 static void
242 242 fill_avl(void)
243 243 {
244 244 int i;
245 245 intnode_t *inp;
246 246
247 247 for (i = 0; i < 20; i++) {
248 248 inp = malloc(sizeof (intnode_t));
249 249 assert(inp != NULL);
250 250 inp->in_val = i;
251 251 avl_add(&inttree, inp);
252 252 }
253 253 }
254 254
255 255 /*
256 256 * Find entries in the AVL tree. Note, we create an intnode_t on the
257 257 * stack that we use to look this up.
258 258 */
259 259 static void
260 260 find_avl(void)
261 261 {
262 262 int i;
263 263 intnode_t lookup, *inp;
264 264
265 265 for (i = 10; i < 30; i++) {
266 266 lookup.in_val = i;
267 267 inp = avl_find(&inttree, &lookup, NULL);
268 268 if (inp == NULL) {
269 269 printf("Entry %d is not in the tree\\n", i);
270 270 } else {
271 271 printf("Entry %d is in the tree\\n",
272 272 inp->in_val);
273 273 }
274 274 }
275 275 }
276 276
277 277 /*
278 278 * Walk the tree forwards
279 279 */
280 280 static void
281 281 walk_forwards(void)
282 282 {
283 283 intnode_t *inp;
284 284 for (inp = avl_first(&inttree); inp != NULL;
285 285 inp = AVL_NEXT(&inttree, inp)) {
286 286 printf("Found entry %d\\n", inp->in_val);
287 287 }
288 288 }
289 289
290 290 /*
291 291 * Walk the tree backwards.
292 292 */
293 293 static void
294 294 walk_backwards(void)
295 295 {
296 296 intnode_t *inp;
297 297 for (inp = avl_last(&inttree); inp != NULL;
298 298 inp = AVL_PREV(&inttree, inp)) {
299 299 printf("Found entry %d\\n", inp->in_val);
300 300 }
301 301 }
302 302
303 303 /*
304 304 * Determine the number of nodes in the tree and if it is empty or
305 305 * not.
306 306 */
307 307 static void
308 308 inttree_inspect(void)
309 309 {
310 310 printf("The tree is %s, there are %ld nodes in it\\n",
311 311 avl_is_empty(&inttree) == B_TRUE ? "empty" : "not empty",
312 312 avl_numnodes(&inttree));
313 313 }
314 314
315 315 /*
316 316 * Use avl_remove to remove entries from the tree.
317 317 */
318 318 static void
319 319 remove_nodes(void)
320 320 {
321 321 int i;
322 322 intnode_t lookup, *inp;
323 323
324 324 for (i = 0; i < 20; i+= 4) {
325 325 lookup.in_val = i;
326 326 inp = avl_find(&inttree, &lookup, NULL);
327 327 if (inp != NULL)
328 328 avl_remove(&inttree, inp);
329 329 }
330 330 }
331 331
332 332 /*
333 333 * Find the nearest nodes in the tree.
334 334 */
335 335 static void
336 336 nearest_nodes(void)
337 337 {
338 338 intnode_t lookup, *inp;
339 339 avl_index_t where;
340 340
341 341 lookup.in_val = 12;
342 342 if (avl_find(&inttree, &lookup, &where) != NULL)
343 343 abort();
344 344 inp = avl_nearest(&inttree, where, AVL_BEFORE);
345 345 assert(inp != NULL);
346 346 printf("closest node before 12 is: %d\\n", inp->in_val);
347 347 inp = avl_nearest(&inttree, where, AVL_AFTER);
348 348 assert(inp != NULL);
349 349 printf("closest node after 12 is: %d\\n", inp->in_val);
350 350 }
351 351
352 352 static void
353 353 insert_avl(void)
354 354 {
355 355 intnode_t lookup, *inp;
356 356 avl_index_t where;
357 357
358 358 lookup.in_val = 12;
359 359 if (avl_find(&inttree, &lookup, &where) != NULL)
360 360 abort();
361 361 inp = malloc(sizeof (intnode_t));
362 362 assert(inp != NULL);
363 363 avl_insert(&inttree, inp, where);
364 364 }
365 365
366 366 static void
367 367 swap_avl(void)
368 368 {
369 369 avl_tree_t swap;
370 370
371 371 avl_create(&swap, intnode_comparator, sizeof (intnode_t),
372 372 offsetof(intnode_t, in_avl));
373 373 avl_swap(&inttree, &swap);
374 374 inttree_inspect();
375 375 avl_swap(&inttree, &swap);
376 376 inttree_inspect();
377 377 }
378 378
379 379 /*
380 380 * Remove all remaining nodes in the tree. We first use
381 381 * avl_destroy_nodes to empty the tree, then avl_destroy to finish.
382 382 */
383 383 static void
384 384 cleanup(void)
385 385 {
386 386 intnode_t *inp;
387 387 void *c = NULL;
388 388
389 389 while ((inp = avl_destroy_nodes(&inttree, &c)) != NULL) {
390 390 free(inp);
391 391 }
392 392 avl_destroy(&inttree);
393 393 }
394 394
395 395 int
396 396 main(void)
397 397 {
398 398 create_avl();
399 399 inttree_inspect();
400 400 fill_avl();
401 401 find_avl();
402 402 walk_forwards();
403 403 walk_backwards();
404 404 inttree_inspect();
405 405 remove_nodes();
406 406 inttree_inspect();
407 407 nearest_nodes();
408 408 insert_avl();
409 409 inttree_inspect();
410 410 swap_avl();
411 411 cleanup();
412 412 return (0);
413 413 }
414 414 .Ed
415 415 .Sh INTERFACE STABILITY
416 416 .Sy Committed
417 417 .Sh MT-Level
418 418 See
419 419 .Sx Locking.
420 420 .Sh SEE ALSO
421 421 .Xr Intro 3 ,
422 422 .Xr pthread_atfork 3C
423 423 .Lp
424 424 .Xr avl_add 3AVL ,
425 425 .Xr avl_create 3AVL ,
426 426 .Xr avl_destroy 3AVL ,
427 427 .Xr avl_destroy_nodes 3AVL ,
428 428 .Xr avl_find 3AVL ,
429 429 .Xr avl_first 3AVL ,
430 430 .Xr avl_insert 3AVL ,
431 431 .Xr avl_insert_here 3AVL ,
432 432 .Xr avl_is_empty 3AVL ,
433 433 .Xr avl_last 3AVL ,
434 434 .Xr avl_nearest 3AVL ,
435 435 .Xr avl_numnodes 3AVL ,
436 436 .Xr avl_remove 3AVL ,
437 437 .Xr avl_swap 3AVL ,
438 438 .Rs
439 439 .%A Adel'son-Vel'skiy, G. M.
440 440 .%A Landis, Ye. M.
441 441 .%T "An Algorithm for the Organization of Information"
442 442 .%Q Deklady Akademii Nauk
443 443 .%C USSR, Moscow
444 444 .%P 263-266
445 445 .%V Vol. 16
446 446 .%N No. 2
447 447 .%D 1962
448 448 .Re
|
↓ open down ↓ |
351 lines elided |
↑ open up ↑ |
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX