22 * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
24 */
25
26 #ifndef _AVL_H
27 #define _AVL_H
28
29 /*
30 * This is a private header file. Applications should not directly include
31 * this file.
32 */
33
34 #ifdef __cplusplus
35 extern "C" {
36 #endif
37
38 #include <sys/types.h>
39 #include <sys/avl_impl.h>
40
41 /*
42 * This is a generic implemenatation of AVL trees for use in the Solaris kernel.
43 * The interfaces provide an efficient way of implementing an ordered set of
44 * data structures.
45 *
46 * AVL trees provide an alternative to using an ordered linked list. Using AVL
47 * trees will usually be faster, however they requires more storage. An ordered
48 * linked list in general requires 2 pointers in each data structure. The
49 * AVL tree implementation uses 3 pointers. The following chart gives the
50 * approximate performance of operations with the different approaches:
51 *
52 * Operation Link List AVL tree
53 * --------- -------- --------
54 * lookup O(n) O(log(n))
55 *
56 * insert 1 node constant constant
57 *
58 * delete 1 node constant between constant and O(log(n))
59 *
60 * delete all nodes O(n) O(n)
61 *
62 * visit the next
158 * found. If not found, it returns NULL and then if "where" is not NULL it sets
159 * "where" for use with avl_insert() or avl_nearest().
160 *
161 * node - node that has the value being looked for
162 * where - position for use with avl_nearest() or avl_insert(), may be NULL
163 */
164 extern void *avl_find(avl_tree_t *tree, const void *node, avl_index_t *where);
165
166 /*
167 * Insert a node into the tree.
168 *
169 * node - the node to insert
170 * where - position as returned from avl_find()
171 */
172 extern void avl_insert(avl_tree_t *tree, void *node, avl_index_t where);
173
174 /*
175 * Insert "new_data" in "tree" in the given "direction" either after
176 * or before the data "here".
177 *
178 * This might be usefull for avl clients caching recently accessed
179 * data to avoid doing avl_find() again for insertion.
180 *
181 * new_data - new data to insert
182 * here - existing node in "tree"
183 * direction - either AVL_AFTER or AVL_BEFORE the data "here".
184 */
185 extern void avl_insert_here(avl_tree_t *tree, void *new_data, void *here,
186 int direction);
187
188
189 /*
190 * Return the first or last valued node in the tree. Will return NULL
191 * if the tree is empty.
192 *
193 */
194 extern void *avl_first(avl_tree_t *tree);
195 extern void *avl_last(avl_tree_t *tree);
196
197
198 /*
|
22 * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
24 */
25
26 #ifndef _AVL_H
27 #define _AVL_H
28
29 /*
30 * This is a private header file. Applications should not directly include
31 * this file.
32 */
33
34 #ifdef __cplusplus
35 extern "C" {
36 #endif
37
38 #include <sys/types.h>
39 #include <sys/avl_impl.h>
40
41 /*
42 * This is a generic implementation of AVL trees for use in the Solaris kernel.
43 * The interfaces provide an efficient way of implementing an ordered set of
44 * data structures.
45 *
46 * AVL trees provide an alternative to using an ordered linked list. Using AVL
47 * trees will usually be faster, however they requires more storage. An ordered
48 * linked list in general requires 2 pointers in each data structure. The
49 * AVL tree implementation uses 3 pointers. The following chart gives the
50 * approximate performance of operations with the different approaches:
51 *
52 * Operation Link List AVL tree
53 * --------- -------- --------
54 * lookup O(n) O(log(n))
55 *
56 * insert 1 node constant constant
57 *
58 * delete 1 node constant between constant and O(log(n))
59 *
60 * delete all nodes O(n) O(n)
61 *
62 * visit the next
158 * found. If not found, it returns NULL and then if "where" is not NULL it sets
159 * "where" for use with avl_insert() or avl_nearest().
160 *
161 * node - node that has the value being looked for
162 * where - position for use with avl_nearest() or avl_insert(), may be NULL
163 */
164 extern void *avl_find(avl_tree_t *tree, const void *node, avl_index_t *where);
165
166 /*
167 * Insert a node into the tree.
168 *
169 * node - the node to insert
170 * where - position as returned from avl_find()
171 */
172 extern void avl_insert(avl_tree_t *tree, void *node, avl_index_t where);
173
174 /*
175 * Insert "new_data" in "tree" in the given "direction" either after
176 * or before the data "here".
177 *
178 * This might be useful for avl clients caching recently accessed
179 * data to avoid doing avl_find() again for insertion.
180 *
181 * new_data - new data to insert
182 * here - existing node in "tree"
183 * direction - either AVL_AFTER or AVL_BEFORE the data "here".
184 */
185 extern void avl_insert_here(avl_tree_t *tree, void *new_data, void *here,
186 int direction);
187
188
189 /*
190 * Return the first or last valued node in the tree. Will return NULL
191 * if the tree is empty.
192 *
193 */
194 extern void *avl_first(avl_tree_t *tree);
195 extern void *avl_last(avl_tree_t *tree);
196
197
198 /*
|