xref: /illumos-gate/usr/src/uts/common/sys/avl.h (revision c4ab0d3f)
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  * AVL comparator helpers
105  */
106 #define	AVL_ISIGN(a)	(((a) > 0) - ((a) < 0))
107 #define	AVL_CMP(a, b)	(((a) > (b)) - ((a) < (b)))
108 #define	AVL_PCMP(a, b)	\
109 	(((uintptr_t)(a) > (uintptr_t)(b)) - ((uintptr_t)(a) < (uintptr_t)(b)))
110 
111 /*
112  * Type used for the root of the AVL tree.
113  */
114 typedef struct avl_tree avl_tree_t;
115 
116 /*
117  * The data nodes in the AVL tree must have a field of this type.
118  */
119 typedef struct avl_node avl_node_t;
120 
121 /*
122  * An opaque type used to locate a position in the tree where a node
123  * would be inserted.
124  */
125 typedef uintptr_t avl_index_t;
126 
127 
128 /*
129  * Direction constants used for avl_nearest().
130  */
131 #define	AVL_BEFORE	(0)
132 #define	AVL_AFTER	(1)
133 
134 
135 /*
136  * Prototypes
137  *
138  * Where not otherwise mentioned, "void *" arguments are a pointer to the
139  * user data structure which must contain a field of type avl_node_t.
140  *
141  * Also assume the user data structures looks like:
142  *	stuct my_type {
143  *		...
144  *		avl_node_t	my_link;
145  *		...
146  *	};
147  */
148 
149 /*
150  * Initialize an AVL tree. Arguments are:
151  *
152  * tree   - the tree to be initialized
153  * compar - function to compare two nodes, it must return exactly: -1, 0, or +1
154  *          -1 for <, 0 for ==, and +1 for >
155  * size   - the value of sizeof(struct my_type)
156  * offset - the value of OFFSETOF(struct my_type, my_link)
157  */
158 extern void avl_create(avl_tree_t *tree,
159 	int (*compar) (const void *, const void *), size_t size, size_t offset);
160 
161 
162 /*
163  * Find a node with a matching value in the tree. Returns the matching node
164  * found. If not found, it returns NULL and then if "where" is not NULL it sets
165  * "where" for use with avl_insert() or avl_nearest().
166  *
167  * node   - node that has the value being looked for
168  * where  - position for use with avl_nearest() or avl_insert(), may be NULL
169  */
170 extern void *avl_find(avl_tree_t *tree, const void *node, avl_index_t *where);
171 
172 /*
173  * Insert a node into the tree.
174  *
175  * node   - the node to insert
176  * where  - position as returned from avl_find()
177  */
178 extern void avl_insert(avl_tree_t *tree, void *node, avl_index_t where);
179 
180 /*
181  * Insert "new_data" in "tree" in the given "direction" either after
182  * or before the data "here".
183  *
184  * This might be useful for avl clients caching recently accessed
185  * data to avoid doing avl_find() again for insertion.
186  *
187  * new_data	- new data to insert
188  * here		- existing node in "tree"
189  * direction	- either AVL_AFTER or AVL_BEFORE the data "here".
190  */
191 extern void avl_insert_here(avl_tree_t *tree, void *new_data, void *here,
192     int direction);
193 
194 
195 /*
196  * Return the first or last valued node in the tree. Will return NULL
197  * if the tree is empty.
198  *
199  */
200 extern void *avl_first(avl_tree_t *tree);
201 extern void *avl_last(avl_tree_t *tree);
202 
203 
204 /*
205  * Return the next or previous valued node in the tree.
206  * AVL_NEXT() will return NULL if at the last node.
207  * AVL_PREV() will return NULL if at the first node.
208  *
209  * node   - the node from which the next or previous node is found
210  */
211 #define	AVL_NEXT(tree, node)	avl_walk(tree, node, AVL_AFTER)
212 #define	AVL_PREV(tree, node)	avl_walk(tree, node, AVL_BEFORE)
213 
214 
215 /*
216  * Find the node with the nearest value either greater or less than
217  * the value from a previous avl_find(). Returns the node or NULL if
218  * there isn't a matching one.
219  *
220  * where     - position as returned from avl_find()
221  * direction - either AVL_BEFORE or AVL_AFTER
222  *
223  * EXAMPLE get the greatest node that is less than a given value:
224  *
225  *	avl_tree_t *tree;
226  *	struct my_data look_for_value = {....};
227  *	struct my_data *node;
228  *	struct my_data *less;
229  *	avl_index_t where;
230  *
231  *	node = avl_find(tree, &look_for_value, &where);
232  *	if (node != NULL)
233  *		less = AVL_PREV(tree, node);
234  *	else
235  *		less = avl_nearest(tree, where, AVL_BEFORE);
236  */
237 extern void *avl_nearest(avl_tree_t *tree, avl_index_t where, int direction);
238 
239 
240 /*
241  * Add a single node to the tree.
242  * The node must not be in the tree, and it must not
243  * compare equal to any other node already in the tree.
244  *
245  * node   - the node to add
246  */
247 extern void avl_add(avl_tree_t *tree, void *node);
248 
249 
250 /*
251  * Remove a single node from the tree.  The node must be in the tree.
252  *
253  * node   - the node to remove
254  */
255 extern void avl_remove(avl_tree_t *tree, void *node);
256 
257 /*
258  * Reinsert a node only if its order has changed relative to its nearest
259  * neighbors. To optimize performance avl_update_lt() checks only the previous
260  * node and avl_update_gt() checks only the next node. Use avl_update_lt() and
261  * avl_update_gt() only if you know the direction in which the order of the
262  * node may change.
263  */
264 extern boolean_t avl_update(avl_tree_t *, void *);
265 extern boolean_t avl_update_lt(avl_tree_t *, void *);
266 extern boolean_t avl_update_gt(avl_tree_t *, void *);
267 
268 /*
269  * Swaps the contents of the two trees.
270  */
271 extern void avl_swap(avl_tree_t *tree1, avl_tree_t *tree2);
272 
273 /*
274  * Return the number of nodes in the tree
275  */
276 extern ulong_t avl_numnodes(avl_tree_t *tree);
277 
278 /*
279  * Return B_TRUE if there are zero nodes in the tree, B_FALSE otherwise.
280  */
281 extern boolean_t avl_is_empty(avl_tree_t *tree);
282 
283 /*
284  * Used to destroy any remaining nodes in a tree. The cookie argument should
285  * be initialized to NULL before the first call. Returns a node that has been
286  * removed from the tree and may be free()'d. Returns NULL when the tree is
287  * empty.
288  *
289  * Once you call avl_destroy_nodes(), you can only continuing calling it and
290  * finally avl_destroy(). No other AVL routines will be valid.
291  *
292  * cookie - a "void *" used to save state between calls to avl_destroy_nodes()
293  *
294  * EXAMPLE:
295  *	avl_tree_t *tree;
296  *	struct my_data *node;
297  *	void *cookie;
298  *
299  *	cookie = NULL;
300  *	while ((node = avl_destroy_nodes(tree, &cookie)) != NULL)
301  *		free(node);
302  *	avl_destroy(tree);
303  */
304 extern void *avl_destroy_nodes(avl_tree_t *tree, void **cookie);
305 
306 
307 /*
308  * Final destroy of an AVL tree. Arguments are:
309  *
310  * tree   - the empty tree to destroy
311  */
312 extern void avl_destroy(avl_tree_t *tree);
313 
314 
315 
316 #ifdef	__cplusplus
317 }
318 #endif
319 
320 #endif	/* _AVL_H */
321