/* * CDDL HEADER START * * The contents of this file are subject to the terms of the * Common Development and Distribution License (the "License"). * You may not use this file except in compliance with the License. * * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE * or http://www.opensolaris.org/os/licensing. * See the License for the specific language governing permissions * and limitations under the License. * * When distributing Covered Code, include this CDDL HEADER in each * file and include the License file at usr/src/OPENSOLARIS.LICENSE. * If applicable, add the following below this CDDL HEADER, with the * fields enclosed by brackets "[]" replaced with your own identifying * information: Portions Copyright [yyyy] [name of copyright owner] * * CDDL HEADER END */ /* * Copyright 2009 Sun Microsystems, Inc. All rights reserved. * Use is subject to license terms. */ /* * Portions copyright 2013 Igor Pashev */ /* * Copyright (c) 2014 by Delphix. All rights reserved. */ /* Just a wrapper, but intended to be the only public interface */ #ifndef _LIBSUNAVL_H #define _LIBSUNAVL_H #include #include /* To avoid conflicts with sys/avl.h */ #ifndef _AVL_DATA_DEFINED # define _AVL_DATA_DEFINED # include #endif /* * Prototypes * * Where not otherwise mentioned, "void *" arguments are a pointer to the * user data structure which must contain a field of type avl_node_t. * * Also assume the user data structures looks like: * stuct my_type { * ... * avl_node_t my_link; * ... * }; */ #ifdef __cplusplus extern "C" { #endif /* * Initialize an AVL tree. Arguments are: * * tree - the tree to be initialized * compar - function to compare two nodes, it must return exactly: -1, 0, or +1 * -1 for <, 0 for ==, and +1 for > * size - the value of sizeof(struct my_type) * offset - the value of OFFSETOF(struct my_type, my_link) */ extern void avl_create(avl_tree_t *tree, int (*compar) (const void *, const void *), size_t size, size_t offset); /* * Find a node with a matching value in the tree. Returns the matching node * found. If not found, it returns NULL and then if "where" is not NULL it sets * "where" for use with avl_insert() or avl_nearest(). * * node - node that has the value being looked for * where - position for use with avl_nearest() or avl_insert(), may be NULL */ extern void *avl_find(avl_tree_t *tree, const void *node, avl_index_t *where); /* * Insert a node into the tree. * * node - the node to insert * where - position as returned from avl_find() */ extern void avl_insert(avl_tree_t *tree, void *node, avl_index_t where); /* * Insert "new_data" in "tree" in the given "direction" either after * or before the data "here". * * This might be useful for avl clients caching recently accessed * data to avoid doing avl_find() again for insertion. * * new_data - new data to insert * here - existing node in "tree" * direction - either AVL_AFTER or AVL_BEFORE the data "here". */ extern void avl_insert_here(avl_tree_t *tree, void *new_data, void *here, int direction); /* * Return the first or last valued node in the tree. Will return NULL * if the tree is empty. * */ extern void *avl_first(avl_tree_t *tree); extern void *avl_last(avl_tree_t *tree); /* * Return the next or previous valued node in the tree. * AVL_NEXT() will return NULL if at the last node. * AVL_PREV() will return NULL if at the first node. * * node - the node from which the next or previous node is found */ /* * Direction constants used for avl_nearest(). */ #define AVL_BEFORE (0) #define AVL_AFTER (1) #define AVL_NEXT(tree, node) avl_walk(tree, node, AVL_AFTER) #define AVL_PREV(tree, node) avl_walk(tree, node, AVL_BEFORE) extern void *avl_walk(struct avl_tree *, void *, int); /* * Find the node with the nearest value either greater or less than * the value from a previous avl_find(). Returns the node or NULL if * there isn't a matching one. * * where - position as returned from avl_find() * direction - either AVL_BEFORE or AVL_AFTER * * EXAMPLE get the greatest node that is less than a given value: * * avl_tree_t *tree; * struct my_data look_for_value = {....}; * struct my_data *node; * struct my_data *less; * avl_index_t where; * * node = avl_find(tree, &look_for_value, &where); * if (node != NULL) * less = AVL_PREV(tree, node); * else * less = avl_nearest(tree, where, AVL_BEFORE); */ extern void *avl_nearest(avl_tree_t *tree, avl_index_t where, int direction); /* * Add a single node to the tree. * The node must not be in the tree, and it must not * compare equal to any other node already in the tree. * * node - the node to add */ extern void avl_add(avl_tree_t *tree, void *node); /* * Remove a single node from the tree. The node must be in the tree. * * node - the node to remove */ extern void avl_remove(avl_tree_t *tree, void *node); /* * Reinsert a node only if its order has changed relative to its nearest * neighbors. To optimize performance avl_update_lt() checks only the previous * node and avl_update_gt() checks only the next node. Use avl_update_lt() and * avl_update_gt() only if you know the direction in which the order of the * node may change. */ extern int avl_update(avl_tree_t *, void *); extern int avl_update_lt(avl_tree_t *, void *); extern int avl_update_gt(avl_tree_t *, void *); /* * Swaps the contents of the two trees. */ extern void avl_swap(avl_tree_t *tree1, avl_tree_t *tree2); /* * Return the number of nodes in the tree */ extern size_t avl_numnodes(avl_tree_t *tree); /* * Return 1 if there are zero nodes in the tree, 0 otherwise. */ extern int avl_is_empty(avl_tree_t *tree); /* * Used to destroy any remaining nodes in a tree. The cookie argument should * be initialized to NULL before the first call. Returns a node that has been * removed from the tree and may be free()'d. Returns NULL when the tree is * empty. * * Once you call avl_destroy_nodes(), you can only continuing calling it and * finally avl_destroy(). No other AVL routines will be valid. * * cookie - a "void *" used to save state between calls to avl_destroy_nodes() * * EXAMPLE: * avl_tree_t *tree; * struct my_data *node; * void *cookie; * * cookie = NULL; * while ((node = avl_destroy_nodes(tree, &cookie)) != NULL) * free(node); * avl_destroy(tree); */ extern void *avl_destroy_nodes(avl_tree_t *tree, void **cookie); /* * Final destroy of an AVL tree. Arguments are: * * tree - the empty tree to destroy */ extern void avl_destroy(avl_tree_t *tree); #ifdef __cplusplus } #endif #endif