Print this page
4745 fix AVL code misspellings
| Split |
Close |
| Expand all |
| Collapse all |
--- old/usr/src/uts/common/sys/avl.h
+++ new/usr/src/uts/common/sys/avl.h
1 1 /*
2 2 * CDDL HEADER START
3 3 *
4 4 * The contents of this file are subject to the terms of the
5 5 * Common Development and Distribution License (the "License").
6 6 * You may not use this file except in compliance with the License.
7 7 *
8 8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 9 * or http://www.opensolaris.org/os/licensing.
10 10 * See the License for the specific language governing permissions
11 11 * and limitations under the License.
12 12 *
13 13 * When distributing Covered Code, include this CDDL HEADER in each
14 14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 15 * If applicable, add the following below this CDDL HEADER, with the
16 16 * fields enclosed by brackets "[]" replaced with your own identifying
17 17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 18 *
19 19 * CDDL HEADER END
20 20 */
21 21 /*
22 22 * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
23 23 * Use is subject to license terms.
24 24 */
25 25
26 26 #ifndef _AVL_H
27 27 #define _AVL_H
28 28
29 29 /*
30 30 * This is a private header file. Applications should not directly include
31 31 * this file.
|
↓ open down ↓ |
31 lines elided |
↑ open up ↑ |
32 32 */
33 33
34 34 #ifdef __cplusplus
35 35 extern "C" {
36 36 #endif
37 37
38 38 #include <sys/types.h>
39 39 #include <sys/avl_impl.h>
40 40
41 41 /*
42 - * This is a generic implemenatation of AVL trees for use in the Solaris kernel.
42 + * This is a generic implementation of AVL trees for use in the Solaris kernel.
43 43 * The interfaces provide an efficient way of implementing an ordered set of
44 44 * data structures.
45 45 *
46 46 * AVL trees provide an alternative to using an ordered linked list. Using AVL
47 47 * trees will usually be faster, however they requires more storage. An ordered
48 48 * linked list in general requires 2 pointers in each data structure. The
49 49 * AVL tree implementation uses 3 pointers. The following chart gives the
50 50 * approximate performance of operations with the different approaches:
51 51 *
52 52 * Operation Link List AVL tree
53 53 * --------- -------- --------
54 54 * lookup O(n) O(log(n))
55 55 *
56 56 * insert 1 node constant constant
57 57 *
58 58 * delete 1 node constant between constant and O(log(n))
59 59 *
60 60 * delete all nodes O(n) O(n)
61 61 *
62 62 * visit the next
63 63 * or prev node constant between constant and O(log(n))
64 64 *
65 65 *
66 66 * The data structure nodes are anchored at an "avl_tree_t" (the equivalent
67 67 * of a list header) and the individual nodes will have a field of
68 68 * type "avl_node_t" (corresponding to list pointers).
69 69 *
70 70 * The type "avl_index_t" is used to indicate a position in the list for
71 71 * certain calls.
72 72 *
73 73 * The usage scenario is generally:
74 74 *
75 75 * 1. Create the list/tree with: avl_create()
76 76 *
77 77 * followed by any mixture of:
78 78 *
79 79 * 2a. Insert nodes with: avl_add(), or avl_find() and avl_insert()
80 80 *
81 81 * 2b. Visited elements with:
82 82 * avl_first() - returns the lowest valued node
83 83 * avl_last() - returns the highest valued node
84 84 * AVL_NEXT() - given a node go to next higher one
85 85 * AVL_PREV() - given a node go to previous lower one
86 86 *
87 87 * 2c. Find the node with the closest value either less than or greater
88 88 * than a given value with avl_nearest().
89 89 *
90 90 * 2d. Remove individual nodes from the list/tree with avl_remove().
91 91 *
92 92 * and finally when the list is being destroyed
93 93 *
94 94 * 3. Use avl_destroy_nodes() to quickly process/free up any remaining nodes.
95 95 * Note that once you use avl_destroy_nodes(), you can no longer
96 96 * use any routine except avl_destroy_nodes() and avl_destoy().
97 97 *
98 98 * 4. Use avl_destroy() to destroy the AVL tree itself.
99 99 *
100 100 * Any locking for multiple thread access is up to the user to provide, just
101 101 * as is needed for any linked list implementation.
102 102 */
103 103
104 104
105 105 /*
106 106 * Type used for the root of the AVL tree.
107 107 */
108 108 typedef struct avl_tree avl_tree_t;
109 109
110 110 /*
111 111 * The data nodes in the AVL tree must have a field of this type.
112 112 */
113 113 typedef struct avl_node avl_node_t;
114 114
115 115 /*
116 116 * An opaque type used to locate a position in the tree where a node
117 117 * would be inserted.
118 118 */
119 119 typedef uintptr_t avl_index_t;
120 120
121 121
122 122 /*
123 123 * Direction constants used for avl_nearest().
124 124 */
125 125 #define AVL_BEFORE (0)
126 126 #define AVL_AFTER (1)
127 127
128 128
129 129 /*
130 130 * Prototypes
131 131 *
132 132 * Where not otherwise mentioned, "void *" arguments are a pointer to the
133 133 * user data structure which must contain a field of type avl_node_t.
134 134 *
135 135 * Also assume the user data structures looks like:
136 136 * stuct my_type {
137 137 * ...
138 138 * avl_node_t my_link;
139 139 * ...
140 140 * };
141 141 */
142 142
143 143 /*
144 144 * Initialize an AVL tree. Arguments are:
145 145 *
146 146 * tree - the tree to be initialized
147 147 * compar - function to compare two nodes, it must return exactly: -1, 0, or +1
148 148 * -1 for <, 0 for ==, and +1 for >
149 149 * size - the value of sizeof(struct my_type)
150 150 * offset - the value of OFFSETOF(struct my_type, my_link)
151 151 */
152 152 extern void avl_create(avl_tree_t *tree,
153 153 int (*compar) (const void *, const void *), size_t size, size_t offset);
154 154
155 155
156 156 /*
157 157 * Find a node with a matching value in the tree. Returns the matching node
158 158 * found. If not found, it returns NULL and then if "where" is not NULL it sets
159 159 * "where" for use with avl_insert() or avl_nearest().
160 160 *
161 161 * node - node that has the value being looked for
162 162 * where - position for use with avl_nearest() or avl_insert(), may be NULL
163 163 */
164 164 extern void *avl_find(avl_tree_t *tree, const void *node, avl_index_t *where);
165 165
166 166 /*
167 167 * Insert a node into the tree.
|
↓ open down ↓ |
115 lines elided |
↑ open up ↑ |
168 168 *
169 169 * node - the node to insert
170 170 * where - position as returned from avl_find()
171 171 */
172 172 extern void avl_insert(avl_tree_t *tree, void *node, avl_index_t where);
173 173
174 174 /*
175 175 * Insert "new_data" in "tree" in the given "direction" either after
176 176 * or before the data "here".
177 177 *
178 - * This might be usefull for avl clients caching recently accessed
178 + * This might be useful for avl clients caching recently accessed
179 179 * data to avoid doing avl_find() again for insertion.
180 180 *
181 181 * new_data - new data to insert
182 182 * here - existing node in "tree"
183 183 * direction - either AVL_AFTER or AVL_BEFORE the data "here".
184 184 */
185 185 extern void avl_insert_here(avl_tree_t *tree, void *new_data, void *here,
186 186 int direction);
187 187
188 188
189 189 /*
190 190 * Return the first or last valued node in the tree. Will return NULL
191 191 * if the tree is empty.
192 192 *
193 193 */
194 194 extern void *avl_first(avl_tree_t *tree);
195 195 extern void *avl_last(avl_tree_t *tree);
196 196
197 197
198 198 /*
199 199 * Return the next or previous valued node in the tree.
200 200 * AVL_NEXT() will return NULL if at the last node.
201 201 * AVL_PREV() will return NULL if at the first node.
202 202 *
203 203 * node - the node from which the next or previous node is found
204 204 */
205 205 #define AVL_NEXT(tree, node) avl_walk(tree, node, AVL_AFTER)
206 206 #define AVL_PREV(tree, node) avl_walk(tree, node, AVL_BEFORE)
207 207
208 208
209 209 /*
210 210 * Find the node with the nearest value either greater or less than
211 211 * the value from a previous avl_find(). Returns the node or NULL if
212 212 * there isn't a matching one.
213 213 *
214 214 * where - position as returned from avl_find()
215 215 * direction - either AVL_BEFORE or AVL_AFTER
216 216 *
217 217 * EXAMPLE get the greatest node that is less than a given value:
218 218 *
219 219 * avl_tree_t *tree;
220 220 * struct my_data look_for_value = {....};
221 221 * struct my_data *node;
222 222 * struct my_data *less;
223 223 * avl_index_t where;
224 224 *
225 225 * node = avl_find(tree, &look_for_value, &where);
226 226 * if (node != NULL)
227 227 * less = AVL_PREV(tree, node);
228 228 * else
229 229 * less = avl_nearest(tree, where, AVL_BEFORE);
230 230 */
231 231 extern void *avl_nearest(avl_tree_t *tree, avl_index_t where, int direction);
232 232
233 233
234 234 /*
235 235 * Add a single node to the tree.
236 236 * The node must not be in the tree, and it must not
237 237 * compare equal to any other node already in the tree.
238 238 *
239 239 * node - the node to add
240 240 */
241 241 extern void avl_add(avl_tree_t *tree, void *node);
242 242
243 243
244 244 /*
245 245 * Remove a single node from the tree. The node must be in the tree.
246 246 *
247 247 * node - the node to remove
248 248 */
249 249 extern void avl_remove(avl_tree_t *tree, void *node);
250 250
251 251 /*
252 252 * Reinsert a node only if its order has changed relative to its nearest
253 253 * neighbors. To optimize performance avl_update_lt() checks only the previous
254 254 * node and avl_update_gt() checks only the next node. Use avl_update_lt() and
255 255 * avl_update_gt() only if you know the direction in which the order of the
256 256 * node may change.
257 257 */
258 258 extern boolean_t avl_update(avl_tree_t *, void *);
259 259 extern boolean_t avl_update_lt(avl_tree_t *, void *);
260 260 extern boolean_t avl_update_gt(avl_tree_t *, void *);
261 261
262 262 /*
263 263 * Return the number of nodes in the tree
264 264 */
265 265 extern ulong_t avl_numnodes(avl_tree_t *tree);
266 266
267 267 /*
268 268 * Return B_TRUE if there are zero nodes in the tree, B_FALSE otherwise.
269 269 */
270 270 extern boolean_t avl_is_empty(avl_tree_t *tree);
271 271
272 272 /*
273 273 * Used to destroy any remaining nodes in a tree. The cookie argument should
274 274 * be initialized to NULL before the first call. Returns a node that has been
275 275 * removed from the tree and may be free()'d. Returns NULL when the tree is
276 276 * empty.
277 277 *
278 278 * Once you call avl_destroy_nodes(), you can only continuing calling it and
279 279 * finally avl_destroy(). No other AVL routines will be valid.
280 280 *
281 281 * cookie - a "void *" used to save state between calls to avl_destroy_nodes()
282 282 *
283 283 * EXAMPLE:
284 284 * avl_tree_t *tree;
285 285 * struct my_data *node;
286 286 * void *cookie;
287 287 *
288 288 * cookie = NULL;
289 289 * while ((node = avl_destroy_nodes(tree, &cookie)) != NULL)
290 290 * free(node);
291 291 * avl_destroy(tree);
292 292 */
293 293 extern void *avl_destroy_nodes(avl_tree_t *tree, void **cookie);
294 294
295 295
296 296 /*
297 297 * Final destroy of an AVL tree. Arguments are:
298 298 *
299 299 * tree - the empty tree to destroy
300 300 */
301 301 extern void avl_destroy(avl_tree_t *tree);
302 302
303 303
304 304
305 305 #ifdef __cplusplus
306 306 }
307 307 #endif
308 308
309 309 #endif /* _AVL_H */
|
↓ open down ↓ |
121 lines elided |
↑ open up ↑ |
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX