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