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