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