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