27c478bdstevel@tonic-gate * CDDL HEADER START
37c478bdstevel@tonic-gate *
47c478bdstevel@tonic-gate * The contents of this file are subject to the terms of the
5b5fca8ftomee * Common Development and Distribution License (the "License").
6b5fca8ftomee * You may not use this file except in compliance with the License.
77c478bdstevel@tonic-gate *
87c478bdstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
97c478bdstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
107c478bdstevel@tonic-gate * See the License for the specific language governing permissions
117c478bdstevel@tonic-gate * and limitations under the License.
127c478bdstevel@tonic-gate *
137c478bdstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
147c478bdstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
157c478bdstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
167c478bdstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
177c478bdstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
187c478bdstevel@tonic-gate *
197c478bdstevel@tonic-gate * CDDL HEADER END
207c478bdstevel@tonic-gate */
22b24ab67Jeff Bonwick * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
237c478bdstevel@tonic-gate * Use is subject to license terms.
247c478bdstevel@tonic-gate */
260f6d88aAlex Reece/*
270f6d88aAlex Reece * Copyright (c) 2014 by Delphix. All rights reserved.
280f6d88aAlex Reece */
290f6d88aAlex Reece
307c478bdstevel@tonic-gate#ifndef	_AVL_H
317c478bdstevel@tonic-gate#define	_AVL_H
337c478bdstevel@tonic-gate#ifdef	__cplusplus
347c478bdstevel@tonic-gateextern "C" {
37b5fca8ftomee#include <sys/types.h>
387c478bdstevel@tonic-gate#include <sys/avl_impl.h>
41fa9922cRobert Mustacchi * This is a generic implementation of AVL trees for use in the illumos. The
42fa9922cRobert Mustacchi * interfaces provide an efficient way of implementing an ordered set of data
43fa9922cRobert Mustacchi * structures.
447c478bdstevel@tonic-gate *
457c478bdstevel@tonic-gate * AVL trees provide an alternative to using an ordered linked list. Using AVL
467c478bdstevel@tonic-gate * trees will usually be faster, however they requires more storage. An ordered
477c478bdstevel@tonic-gate * linked list in general requires 2 pointers in each data structure. The
487c478bdstevel@tonic-gate * AVL tree implementation uses 3 pointers. The following chart gives the
497c478bdstevel@tonic-gate * approximate performance of operations with the different approaches:
507c478bdstevel@tonic-gate *
517c478bdstevel@tonic-gate *	Operation	 Link List	AVL tree
527c478bdstevel@tonic-gate *	---------	 --------	--------
537c478bdstevel@tonic-gate *	lookup		   O(n)		O(log(n))
547c478bdstevel@tonic-gate *
55fa9922cRobert Mustacchi *	insert 1 node	 constant	O(log(n))
567c478bdstevel@tonic-gate *
577c478bdstevel@tonic-gate *	delete 1 node	 constant	between constant and O(log(n))
587c478bdstevel@tonic-gate *
597c478bdstevel@tonic-gate *	delete all nodes   O(n)		O(n)
607c478bdstevel@tonic-gate *
617c478bdstevel@tonic-gate *	visit the next
627c478bdstevel@tonic-gate *	or prev node	 constant	between constant and O(log(n))
637c478bdstevel@tonic-gate *
647c478bdstevel@tonic-gate *
657c478bdstevel@tonic-gate * The data structure nodes are anchored at an "avl_tree_t" (the equivalent
667c478bdstevel@tonic-gate * of a list header) and the individual nodes will have a field of
677c478bdstevel@tonic-gate * type "avl_node_t" (corresponding to list pointers).
687c478bdstevel@tonic-gate *
697c478bdstevel@tonic-gate * The type "avl_index_t" is used to indicate a position in the list for
707c478bdstevel@tonic-gate * certain calls.
717c478bdstevel@tonic-gate *
727c478bdstevel@tonic-gate * The usage scenario is generally:
737c478bdstevel@tonic-gate *
747c478bdstevel@tonic-gate * 1. Create the list/tree with: avl_create()
757c478bdstevel@tonic-gate *
767c478bdstevel@tonic-gate * followed by any mixture of:
777c478bdstevel@tonic-gate *
78fa9e406ahrens * 2a. Insert nodes with: avl_add(), or avl_find() and avl_insert()
797c478bdstevel@tonic-gate *
807c478bdstevel@tonic-gate * 2b. Visited elements with:
817c478bdstevel@tonic-gate *	 avl_first() - returns the lowest valued node
827c478bdstevel@tonic-gate *	 avl_last() - returns the highest valued node
837c478bdstevel@tonic-gate *	 AVL_NEXT() - given a node go to next higher one
847c478bdstevel@tonic-gate *	 AVL_PREV() - given a node go to previous lower one
857c478bdstevel@tonic-gate *
867c478bdstevel@tonic-gate * 2c.  Find the node with the closest value either less than or greater
877c478bdstevel@tonic-gate *	than a given value with avl_nearest().
887c478bdstevel@tonic-gate *
89fa9e406ahrens * 2d. Remove individual nodes from the list/tree with avl_remove().
907c478bdstevel@tonic-gate *
917c478bdstevel@tonic-gate * and finally when the list is being destroyed
927c478bdstevel@tonic-gate *
937c478bdstevel@tonic-gate * 3. Use avl_destroy_nodes() to quickly process/free up any remaining nodes.
947c478bdstevel@tonic-gate *    Note that once you use avl_destroy_nodes(), you can no longer
957c478bdstevel@tonic-gate *    use any routine except avl_destroy_nodes() and avl_destoy().
967c478bdstevel@tonic-gate *
977c478bdstevel@tonic-gate * 4. Use avl_destroy() to destroy the AVL tree itself.
987c478bdstevel@tonic-gate *
997c478bdstevel@tonic-gate * Any locking for multiple thread access is up to the user to provide, just
1007c478bdstevel@tonic-gate * as is needed for any linked list implementation.
1017c478bdstevel@tonic-gate */
103c4ab0d3Gvozden Neskovic/*
104c4ab0d3Gvozden Neskovic * AVL comparator helpers
105c4ab0d3Gvozden Neskovic */
106c4ab0d3Gvozden Neskovic#define	AVL_ISIGN(a)	(((a) > 0) - ((a) < 0))
107c4ab0d3Gvozden Neskovic#define	AVL_CMP(a, b)	(((a) > (b)) - ((a) < (b)))
108c4ab0d3Gvozden Neskovic#define	AVL_PCMP(a, b)	\
109c4ab0d3Gvozden Neskovic	(((uintptr_t)(a) > (uintptr_t)(b)) - ((uintptr_t)(a) < (uintptr_t)(b)))
1127c478bdstevel@tonic-gate * Type used for the root of the AVL tree.
1137c478bdstevel@tonic-gate */
1147c478bdstevel@tonic-gatetypedef struct avl_tree avl_tree_t;
1177c478bdstevel@tonic-gate * The data nodes in the AVL tree must have a field of this type.
1187c478bdstevel@tonic-gate */
1197c478bdstevel@tonic-gatetypedef struct avl_node avl_node_t;
1227c478bdstevel@tonic-gate * An opaque type used to locate a position in the tree where a node
1237c478bdstevel@tonic-gate * would be inserted.
1247c478bdstevel@tonic-gate */
1257c478bdstevel@tonic-gatetypedef uintptr_t avl_index_t;
1297c478bdstevel@tonic-gate * Direction constants used for avl_nearest().
1307c478bdstevel@tonic-gate */
1317c478bdstevel@tonic-gate#define	AVL_BEFORE	(0)
1327c478bdstevel@tonic-gate#define	AVL_AFTER	(1)
1367c478bdstevel@tonic-gate * Prototypes
1377c478bdstevel@tonic-gate *
1387c478bdstevel@tonic-gate * Where not otherwise mentioned, "void *" arguments are a pointer to the
1397c478bdstevel@tonic-gate * user data structure which must contain a field of type avl_node_t.
1407c478bdstevel@tonic-gate *
1417c478bdstevel@tonic-gate * Also assume the user data structures looks like:
1427c478bdstevel@tonic-gate *	stuct my_type {
1437c478bdstevel@tonic-gate *		...
1447c478bdstevel@tonic-gate *		avl_node_t	my_link;
1457c478bdstevel@tonic-gate *		...
1467c478bdstevel@tonic-gate *	};
1477c478bdstevel@tonic-gate */
1507c478bdstevel@tonic-gate * Initialize an AVL tree. Arguments are:
1517c478bdstevel@tonic-gate *
1527c478bdstevel@tonic-gate * tree   - the tree to be initialized
1537c478bdstevel@tonic-gate * compar - function to compare two nodes, it must return exactly: -1, 0, or +1
1547c478bdstevel@tonic-gate *          -1 for <, 0 for ==, and +1 for >
1557c478bdstevel@tonic-gate * size   - the value of sizeof(struct my_type)
1567c478bdstevel@tonic-gate * offset - the value of OFFSETOF(struct my_type, my_link)
1577c478bdstevel@tonic-gate */
1587c478bdstevel@tonic-gateextern void avl_create(avl_tree_t *tree,
1597c478bdstevel@tonic-gate	int (*compar) (const void *, const void *), size_t size, size_t offset);
1637c478bdstevel@tonic-gate * Find a node with a matching value in the tree. Returns the matching node
1647c478bdstevel@tonic-gate * found. If not found, it returns NULL and then if "where" is not NULL it sets
1657c478bdstevel@tonic-gate * "where" for use with avl_insert() or avl_nearest().
1667c478bdstevel@tonic-gate *
1677c478bdstevel@tonic-gate * node   - node that has the value being looked for
1687c478bdstevel@tonic-gate * where  - position for use with avl_nearest() or avl_insert(), may be NULL
1697c478bdstevel@tonic-gate */
170b24ab67Jeff Bonwickextern void *avl_find(avl_tree_t *tree, const void *node, avl_index_t *where);
1737c478bdstevel@tonic-gate * Insert a node into the tree.
1747c478bdstevel@tonic-gate *
1757c478bdstevel@tonic-gate * node   - the node to insert
1767c478bdstevel@tonic-gate * where  - position as returned from avl_find()
1777c478bdstevel@tonic-gate */
1787c478bdstevel@tonic-gateextern void avl_insert(avl_tree_t *tree, void *node, avl_index_t where);
1817c478bdstevel@tonic-gate * Insert "new_data" in "tree" in the given "direction" either after
1827c478bdstevel@tonic-gate * or before the data "here".
1837c478bdstevel@tonic-gate *
1846907ca4Josef 'Jeff' Sipek * This might be useful for avl clients caching recently accessed
1857c478bdstevel@tonic-gate * data to avoid doing avl_find() again for insertion.
1867c478bdstevel@tonic-gate *
1877c478bdstevel@tonic-gate * new_data	- new data to insert
188b5fca8ftomee * here		- existing node in "tree"
1897c478bdstevel@tonic-gate * direction	- either AVL_AFTER or AVL_BEFORE the data "here".
1907c478bdstevel@tonic-gate */
1917c478bdstevel@tonic-gateextern void avl_insert_here(avl_tree_t *tree, void *new_data, void *here,
1927c478bdstevel@tonic-gate    int direction);
1967c478bdstevel@tonic-gate * Return the first or last valued node in the tree. Will return NULL
1977c478bdstevel@tonic-gate * if the tree is empty.
1987c478bdstevel@tonic-gate *
1997c478bdstevel@tonic-gate */
2007c478bdstevel@tonic-gateextern void *avl_first(avl_tree_t *tree);
2017c478bdstevel@tonic-gateextern void *avl_last(avl_tree_t *tree);
2057c478bdstevel@tonic-gate * Return the next or previous valued node in the tree.
2067c478bdstevel@tonic-gate * AVL_NEXT() will return NULL if at the last node.
2077c478bdstevel@tonic-gate * AVL_PREV() will return NULL if at the first node.
2087c478bdstevel@tonic-gate *
2097c478bdstevel@tonic-gate * node   - the node from which the next or previous node is found
2107c478bdstevel@tonic-gate */
2117c478bdstevel@tonic-gate#define	AVL_NEXT(tree, node)	avl_walk(tree, node, AVL_AFTER)
2127c478bdstevel@tonic-gate#define	AVL_PREV(tree, node)	avl_walk(tree, node, AVL_BEFORE)
2167c478bdstevel@tonic-gate * Find the node with the nearest value either greater or less than
2177c478bdstevel@tonic-gate * the value from a previous avl_find(). Returns the node or NULL if
2187c478bdstevel@tonic-gate * there isn't a matching one.
2197c478bdstevel@tonic-gate *
2207c478bdstevel@tonic-gate * where     - position as returned from avl_find()
2217c478bdstevel@tonic-gate * direction - either AVL_BEFORE or AVL_AFTER
2227c478bdstevel@tonic-gate *
2237c478bdstevel@tonic-gate * EXAMPLE get the greatest node that is less than a given value:
2247c478bdstevel@tonic-gate *
2257c478bdstevel@tonic-gate *	avl_tree_t *tree;
2267c478bdstevel@tonic-gate *	struct my_data look_for_value = {....};
2277c478bdstevel@tonic-gate *	struct my_data *node;
2287c478bdstevel@tonic-gate *	struct my_data *less;
2297c478bdstevel@tonic-gate *	avl_index_t where;
2307c478bdstevel@tonic-gate *
2317c478bdstevel@tonic-gate *	node = avl_find(tree, &look_for_value, &where);
2327c478bdstevel@tonic-gate *	if (node != NULL)
2337c478bdstevel@tonic-gate *		less = AVL_PREV(tree, node);
2347c478bdstevel@tonic-gate *	else
2357c478bdstevel@tonic-gate *		less = avl_nearest(tree, where, AVL_BEFORE);
2367c478bdstevel@tonic-gate */
2377c478bdstevel@tonic-gateextern void *avl_nearest(avl_tree_t *tree, avl_index_t where, int direction);
241fa9e406ahrens * Add a single node to the tree.
242fa9e406ahrens * The node must not be in the tree, and it must not
243fa9e406ahrens * compare equal to any other node already in the tree.
244fa9e406ahrens *
245fa9e406ahrens * node   - the node to add
246fa9e406ahrens */
247fa9e406ahrensextern void avl_add(avl_tree_t *tree, void *node);
251fa9e406ahrens * Remove a single node from the tree.  The node must be in the tree.
2527c478bdstevel@tonic-gate *
2537c478bdstevel@tonic-gate * node   - the node to remove
2547c478bdstevel@tonic-gate */
2557c478bdstevel@tonic-gateextern void avl_remove(avl_tree_t *tree, void *node);
258b5fca8ftomee * Reinsert a node only if its order has changed relative to its nearest
259b5fca8ftomee * neighbors. To optimize performance avl_update_lt() checks only the previous
260b5fca8ftomee * node and avl_update_gt() checks only the next node. Use avl_update_lt() and
261b5fca8ftomee * avl_update_gt() only if you know the direction in which the order of the
262b5fca8ftomee * node may change.
263b5fca8ftomee */
264b5fca8ftomeeextern boolean_t avl_update(avl_tree_t *, void *);
265b5fca8ftomeeextern boolean_t avl_update_lt(avl_tree_t *, void *);
266b5fca8ftomeeextern boolean_t avl_update_gt(avl_tree_t *, void *);
2690f6d88aAlex Reece * Swaps the contents of the two trees.
2700f6d88aAlex Reece */
2710f6d88aAlex Reeceextern void avl_swap(avl_tree_t *tree1, avl_tree_t *tree2);
2720f6d88aAlex Reece
2730f6d88aAlex Reece/*
2747c478bdstevel@tonic-gate * Return the number of nodes in the tree
2757c478bdstevel@tonic-gate */
2767c478bdstevel@tonic-gateextern ulong_t avl_numnodes(avl_tree_t *tree);
279b5fca8ftomee * Return B_TRUE if there are zero nodes in the tree, B_FALSE otherwise.
280b5fca8ftomee */
281b5fca8ftomeeextern boolean_t avl_is_empty(avl_tree_t *tree);
2847c478bdstevel@tonic-gate * Used to destroy any remaining nodes in a tree. The cookie argument should
2857c478bdstevel@tonic-gate * be initialized to NULL before the first call. Returns a node that has been
2867c478bdstevel@tonic-gate * removed from the tree and may be free()'d. Returns NULL when the tree is
2877c478bdstevel@tonic-gate * empty.
2887c478bdstevel@tonic-gate *
2897c478bdstevel@tonic-gate * Once you call avl_destroy_nodes(), you can only continuing calling it and
2907c478bdstevel@tonic-gate * finally avl_destroy(). No other AVL routines will be valid.
2917c478bdstevel@tonic-gate *
2927c478bdstevel@tonic-gate * cookie - a "void *" used to save state between calls to avl_destroy_nodes()
2937c478bdstevel@tonic-gate *
2947c478bdstevel@tonic-gate * EXAMPLE:
2957c478bdstevel@tonic-gate *	avl_tree_t *tree;
2967c478bdstevel@tonic-gate *	struct my_data *node;
2977c478bdstevel@tonic-gate *	void *cookie;
2987c478bdstevel@tonic-gate *
2997c478bdstevel@tonic-gate *	cookie = NULL;
3007c478bdstevel@tonic-gate *	while ((node = avl_destroy_nodes(tree, &cookie)) != NULL)
3017c478bdstevel@tonic-gate *		free(node);
3027c478bdstevel@tonic-gate *	avl_destroy(tree);
3037c478bdstevel@tonic-gate */
3047c478bdstevel@tonic-gateextern void *avl_destroy_nodes(avl_tree_t *tree, void **cookie);
3087c478bdstevel@tonic-gate * Final destroy of an AVL tree. Arguments are:
3097c478bdstevel@tonic-gate *
3107c478bdstevel@tonic-gate * tree   - the empty tree to destroy
3117c478bdstevel@tonic-gate */
3127c478bdstevel@tonic-gateextern void avl_destroy(avl_tree_t *tree);
3167c478bdstevel@tonic-gate#ifdef	__cplusplus
3207c478bdstevel@tonic-gate#endif	/* _AVL_H */