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