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
34extern "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 */
114typedef struct avl_tree avl_tree_t;
115
116/*
117 * The data nodes in the AVL tree must have a field of this type.
118 */
119typedef 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 */
125typedef 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 */
158extern 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 */
170extern 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 */
178extern 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 */
191extern 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 */
200extern void *avl_first(avl_tree_t *tree);
201extern 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 */
237extern 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 */
247extern 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 */
255extern 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 */
264extern boolean_t avl_update(avl_tree_t *, void *);
265extern boolean_t avl_update_lt(avl_tree_t *, void *);
266extern boolean_t avl_update_gt(avl_tree_t *, void *);
267
268/*
269 * Swaps the contents of the two trees.
270 */
271extern void avl_swap(avl_tree_t *tree1, avl_tree_t *tree2);
272
273/*
274 * Return the number of nodes in the tree
275 */
276extern 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 */
281extern 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 */
304extern 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 */
312extern void avl_destroy(avl_tree_t *tree);
313
314
315
316#ifdef	__cplusplus
317}
318#endif
319
320#endif	/* _AVL_H */
321