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 26*0f6d88adSAlex Reece /* 27*0f6d88adSAlex Reece * Copyright (c) 2014 by Delphix. All rights reserved. 28*0f6d88adSAlex Reece */ 29*0f6d88adSAlex Reece 307c478bd9Sstevel@tonic-gate #ifndef _AVL_H 317c478bd9Sstevel@tonic-gate #define _AVL_H 327c478bd9Sstevel@tonic-gate 337c478bd9Sstevel@tonic-gate /* 347c478bd9Sstevel@tonic-gate * This is a private header file. Applications should not directly include 357c478bd9Sstevel@tonic-gate * this file. 367c478bd9Sstevel@tonic-gate */ 377c478bd9Sstevel@tonic-gate 387c478bd9Sstevel@tonic-gate #ifdef __cplusplus 397c478bd9Sstevel@tonic-gate extern "C" { 407c478bd9Sstevel@tonic-gate #endif 417c478bd9Sstevel@tonic-gate 42b5fca8f8Stomee #include <sys/types.h> 437c478bd9Sstevel@tonic-gate #include <sys/avl_impl.h> 447c478bd9Sstevel@tonic-gate 457c478bd9Sstevel@tonic-gate /* 466907ca4bSJosef 'Jeff' Sipek * This is a generic implementation of AVL trees for use in the Solaris kernel. 477c478bd9Sstevel@tonic-gate * The interfaces provide an efficient way of implementing an ordered set of 487c478bd9Sstevel@tonic-gate * data structures. 497c478bd9Sstevel@tonic-gate * 507c478bd9Sstevel@tonic-gate * AVL trees provide an alternative to using an ordered linked list. Using AVL 517c478bd9Sstevel@tonic-gate * trees will usually be faster, however they requires more storage. An ordered 527c478bd9Sstevel@tonic-gate * linked list in general requires 2 pointers in each data structure. The 537c478bd9Sstevel@tonic-gate * AVL tree implementation uses 3 pointers. The following chart gives the 547c478bd9Sstevel@tonic-gate * approximate performance of operations with the different approaches: 557c478bd9Sstevel@tonic-gate * 567c478bd9Sstevel@tonic-gate * Operation Link List AVL tree 577c478bd9Sstevel@tonic-gate * --------- -------- -------- 587c478bd9Sstevel@tonic-gate * lookup O(n) O(log(n)) 597c478bd9Sstevel@tonic-gate * 607c478bd9Sstevel@tonic-gate * insert 1 node constant constant 617c478bd9Sstevel@tonic-gate * 627c478bd9Sstevel@tonic-gate * delete 1 node constant between constant and O(log(n)) 637c478bd9Sstevel@tonic-gate * 647c478bd9Sstevel@tonic-gate * delete all nodes O(n) O(n) 657c478bd9Sstevel@tonic-gate * 667c478bd9Sstevel@tonic-gate * visit the next 677c478bd9Sstevel@tonic-gate * or prev node constant between constant and O(log(n)) 687c478bd9Sstevel@tonic-gate * 697c478bd9Sstevel@tonic-gate * 707c478bd9Sstevel@tonic-gate * The data structure nodes are anchored at an "avl_tree_t" (the equivalent 717c478bd9Sstevel@tonic-gate * of a list header) and the individual nodes will have a field of 727c478bd9Sstevel@tonic-gate * type "avl_node_t" (corresponding to list pointers). 737c478bd9Sstevel@tonic-gate * 747c478bd9Sstevel@tonic-gate * The type "avl_index_t" is used to indicate a position in the list for 757c478bd9Sstevel@tonic-gate * certain calls. 767c478bd9Sstevel@tonic-gate * 777c478bd9Sstevel@tonic-gate * The usage scenario is generally: 787c478bd9Sstevel@tonic-gate * 797c478bd9Sstevel@tonic-gate * 1. Create the list/tree with: avl_create() 807c478bd9Sstevel@tonic-gate * 817c478bd9Sstevel@tonic-gate * followed by any mixture of: 827c478bd9Sstevel@tonic-gate * 83fa9e4066Sahrens * 2a. Insert nodes with: avl_add(), or avl_find() and avl_insert() 847c478bd9Sstevel@tonic-gate * 857c478bd9Sstevel@tonic-gate * 2b. Visited elements with: 867c478bd9Sstevel@tonic-gate * avl_first() - returns the lowest valued node 877c478bd9Sstevel@tonic-gate * avl_last() - returns the highest valued node 887c478bd9Sstevel@tonic-gate * AVL_NEXT() - given a node go to next higher one 897c478bd9Sstevel@tonic-gate * AVL_PREV() - given a node go to previous lower one 907c478bd9Sstevel@tonic-gate * 917c478bd9Sstevel@tonic-gate * 2c. Find the node with the closest value either less than or greater 927c478bd9Sstevel@tonic-gate * than a given value with avl_nearest(). 937c478bd9Sstevel@tonic-gate * 94fa9e4066Sahrens * 2d. Remove individual nodes from the list/tree with avl_remove(). 957c478bd9Sstevel@tonic-gate * 967c478bd9Sstevel@tonic-gate * and finally when the list is being destroyed 977c478bd9Sstevel@tonic-gate * 987c478bd9Sstevel@tonic-gate * 3. Use avl_destroy_nodes() to quickly process/free up any remaining nodes. 997c478bd9Sstevel@tonic-gate * Note that once you use avl_destroy_nodes(), you can no longer 1007c478bd9Sstevel@tonic-gate * use any routine except avl_destroy_nodes() and avl_destoy(). 1017c478bd9Sstevel@tonic-gate * 1027c478bd9Sstevel@tonic-gate * 4. Use avl_destroy() to destroy the AVL tree itself. 1037c478bd9Sstevel@tonic-gate * 1047c478bd9Sstevel@tonic-gate * Any locking for multiple thread access is up to the user to provide, just 1057c478bd9Sstevel@tonic-gate * as is needed for any linked list implementation. 1067c478bd9Sstevel@tonic-gate */ 1077c478bd9Sstevel@tonic-gate 1087c478bd9Sstevel@tonic-gate 1097c478bd9Sstevel@tonic-gate /* 1107c478bd9Sstevel@tonic-gate * Type used for the root of the AVL tree. 1117c478bd9Sstevel@tonic-gate */ 1127c478bd9Sstevel@tonic-gate typedef struct avl_tree avl_tree_t; 1137c478bd9Sstevel@tonic-gate 1147c478bd9Sstevel@tonic-gate /* 1157c478bd9Sstevel@tonic-gate * The data nodes in the AVL tree must have a field of this type. 1167c478bd9Sstevel@tonic-gate */ 1177c478bd9Sstevel@tonic-gate typedef struct avl_node avl_node_t; 1187c478bd9Sstevel@tonic-gate 1197c478bd9Sstevel@tonic-gate /* 1207c478bd9Sstevel@tonic-gate * An opaque type used to locate a position in the tree where a node 1217c478bd9Sstevel@tonic-gate * would be inserted. 1227c478bd9Sstevel@tonic-gate */ 1237c478bd9Sstevel@tonic-gate typedef uintptr_t avl_index_t; 1247c478bd9Sstevel@tonic-gate 1257c478bd9Sstevel@tonic-gate 1267c478bd9Sstevel@tonic-gate /* 1277c478bd9Sstevel@tonic-gate * Direction constants used for avl_nearest(). 1287c478bd9Sstevel@tonic-gate */ 1297c478bd9Sstevel@tonic-gate #define AVL_BEFORE (0) 1307c478bd9Sstevel@tonic-gate #define AVL_AFTER (1) 1317c478bd9Sstevel@tonic-gate 1327c478bd9Sstevel@tonic-gate 1337c478bd9Sstevel@tonic-gate /* 1347c478bd9Sstevel@tonic-gate * Prototypes 1357c478bd9Sstevel@tonic-gate * 1367c478bd9Sstevel@tonic-gate * Where not otherwise mentioned, "void *" arguments are a pointer to the 1377c478bd9Sstevel@tonic-gate * user data structure which must contain a field of type avl_node_t. 1387c478bd9Sstevel@tonic-gate * 1397c478bd9Sstevel@tonic-gate * Also assume the user data structures looks like: 1407c478bd9Sstevel@tonic-gate * stuct my_type { 1417c478bd9Sstevel@tonic-gate * ... 1427c478bd9Sstevel@tonic-gate * avl_node_t my_link; 1437c478bd9Sstevel@tonic-gate * ... 1447c478bd9Sstevel@tonic-gate * }; 1457c478bd9Sstevel@tonic-gate */ 1467c478bd9Sstevel@tonic-gate 1477c478bd9Sstevel@tonic-gate /* 1487c478bd9Sstevel@tonic-gate * Initialize an AVL tree. Arguments are: 1497c478bd9Sstevel@tonic-gate * 1507c478bd9Sstevel@tonic-gate * tree - the tree to be initialized 1517c478bd9Sstevel@tonic-gate * compar - function to compare two nodes, it must return exactly: -1, 0, or +1 1527c478bd9Sstevel@tonic-gate * -1 for <, 0 for ==, and +1 for > 1537c478bd9Sstevel@tonic-gate * size - the value of sizeof(struct my_type) 1547c478bd9Sstevel@tonic-gate * offset - the value of OFFSETOF(struct my_type, my_link) 1557c478bd9Sstevel@tonic-gate */ 1567c478bd9Sstevel@tonic-gate extern void avl_create(avl_tree_t *tree, 1577c478bd9Sstevel@tonic-gate int (*compar) (const void *, const void *), size_t size, size_t offset); 1587c478bd9Sstevel@tonic-gate 1597c478bd9Sstevel@tonic-gate 1607c478bd9Sstevel@tonic-gate /* 1617c478bd9Sstevel@tonic-gate * Find a node with a matching value in the tree. Returns the matching node 1627c478bd9Sstevel@tonic-gate * found. If not found, it returns NULL and then if "where" is not NULL it sets 1637c478bd9Sstevel@tonic-gate * "where" for use with avl_insert() or avl_nearest(). 1647c478bd9Sstevel@tonic-gate * 1657c478bd9Sstevel@tonic-gate * node - node that has the value being looked for 1667c478bd9Sstevel@tonic-gate * where - position for use with avl_nearest() or avl_insert(), may be NULL 1677c478bd9Sstevel@tonic-gate */ 168b24ab676SJeff Bonwick extern void *avl_find(avl_tree_t *tree, const void *node, avl_index_t *where); 1697c478bd9Sstevel@tonic-gate 1707c478bd9Sstevel@tonic-gate /* 1717c478bd9Sstevel@tonic-gate * Insert a node into the tree. 1727c478bd9Sstevel@tonic-gate * 1737c478bd9Sstevel@tonic-gate * node - the node to insert 1747c478bd9Sstevel@tonic-gate * where - position as returned from avl_find() 1757c478bd9Sstevel@tonic-gate */ 1767c478bd9Sstevel@tonic-gate extern void avl_insert(avl_tree_t *tree, void *node, avl_index_t where); 1777c478bd9Sstevel@tonic-gate 1787c478bd9Sstevel@tonic-gate /* 1797c478bd9Sstevel@tonic-gate * Insert "new_data" in "tree" in the given "direction" either after 1807c478bd9Sstevel@tonic-gate * or before the data "here". 1817c478bd9Sstevel@tonic-gate * 1826907ca4bSJosef 'Jeff' Sipek * This might be useful for avl clients caching recently accessed 1837c478bd9Sstevel@tonic-gate * data to avoid doing avl_find() again for insertion. 1847c478bd9Sstevel@tonic-gate * 1857c478bd9Sstevel@tonic-gate * new_data - new data to insert 186b5fca8f8Stomee * here - existing node in "tree" 1877c478bd9Sstevel@tonic-gate * direction - either AVL_AFTER or AVL_BEFORE the data "here". 1887c478bd9Sstevel@tonic-gate */ 1897c478bd9Sstevel@tonic-gate extern void avl_insert_here(avl_tree_t *tree, void *new_data, void *here, 1907c478bd9Sstevel@tonic-gate int direction); 1917c478bd9Sstevel@tonic-gate 1927c478bd9Sstevel@tonic-gate 1937c478bd9Sstevel@tonic-gate /* 1947c478bd9Sstevel@tonic-gate * Return the first or last valued node in the tree. Will return NULL 1957c478bd9Sstevel@tonic-gate * if the tree is empty. 1967c478bd9Sstevel@tonic-gate * 1977c478bd9Sstevel@tonic-gate */ 1987c478bd9Sstevel@tonic-gate extern void *avl_first(avl_tree_t *tree); 1997c478bd9Sstevel@tonic-gate extern void *avl_last(avl_tree_t *tree); 2007c478bd9Sstevel@tonic-gate 2017c478bd9Sstevel@tonic-gate 2027c478bd9Sstevel@tonic-gate /* 2037c478bd9Sstevel@tonic-gate * Return the next or previous valued node in the tree. 2047c478bd9Sstevel@tonic-gate * AVL_NEXT() will return NULL if at the last node. 2057c478bd9Sstevel@tonic-gate * AVL_PREV() will return NULL if at the first node. 2067c478bd9Sstevel@tonic-gate * 2077c478bd9Sstevel@tonic-gate * node - the node from which the next or previous node is found 2087c478bd9Sstevel@tonic-gate */ 2097c478bd9Sstevel@tonic-gate #define AVL_NEXT(tree, node) avl_walk(tree, node, AVL_AFTER) 2107c478bd9Sstevel@tonic-gate #define AVL_PREV(tree, node) avl_walk(tree, node, AVL_BEFORE) 2117c478bd9Sstevel@tonic-gate 2127c478bd9Sstevel@tonic-gate 2137c478bd9Sstevel@tonic-gate /* 2147c478bd9Sstevel@tonic-gate * Find the node with the nearest value either greater or less than 2157c478bd9Sstevel@tonic-gate * the value from a previous avl_find(). Returns the node or NULL if 2167c478bd9Sstevel@tonic-gate * there isn't a matching one. 2177c478bd9Sstevel@tonic-gate * 2187c478bd9Sstevel@tonic-gate * where - position as returned from avl_find() 2197c478bd9Sstevel@tonic-gate * direction - either AVL_BEFORE or AVL_AFTER 2207c478bd9Sstevel@tonic-gate * 2217c478bd9Sstevel@tonic-gate * EXAMPLE get the greatest node that is less than a given value: 2227c478bd9Sstevel@tonic-gate * 2237c478bd9Sstevel@tonic-gate * avl_tree_t *tree; 2247c478bd9Sstevel@tonic-gate * struct my_data look_for_value = {....}; 2257c478bd9Sstevel@tonic-gate * struct my_data *node; 2267c478bd9Sstevel@tonic-gate * struct my_data *less; 2277c478bd9Sstevel@tonic-gate * avl_index_t where; 2287c478bd9Sstevel@tonic-gate * 2297c478bd9Sstevel@tonic-gate * node = avl_find(tree, &look_for_value, &where); 2307c478bd9Sstevel@tonic-gate * if (node != NULL) 2317c478bd9Sstevel@tonic-gate * less = AVL_PREV(tree, node); 2327c478bd9Sstevel@tonic-gate * else 2337c478bd9Sstevel@tonic-gate * less = avl_nearest(tree, where, AVL_BEFORE); 2347c478bd9Sstevel@tonic-gate */ 2357c478bd9Sstevel@tonic-gate extern void *avl_nearest(avl_tree_t *tree, avl_index_t where, int direction); 2367c478bd9Sstevel@tonic-gate 2377c478bd9Sstevel@tonic-gate 2387c478bd9Sstevel@tonic-gate /* 239fa9e4066Sahrens * Add a single node to the tree. 240fa9e4066Sahrens * The node must not be in the tree, and it must not 241fa9e4066Sahrens * compare equal to any other node already in the tree. 242fa9e4066Sahrens * 243fa9e4066Sahrens * node - the node to add 244fa9e4066Sahrens */ 245fa9e4066Sahrens extern void avl_add(avl_tree_t *tree, void *node); 246fa9e4066Sahrens 247fa9e4066Sahrens 248fa9e4066Sahrens /* 249fa9e4066Sahrens * Remove a single node from the tree. The node must be in the tree. 2507c478bd9Sstevel@tonic-gate * 2517c478bd9Sstevel@tonic-gate * node - the node to remove 2527c478bd9Sstevel@tonic-gate */ 2537c478bd9Sstevel@tonic-gate extern void avl_remove(avl_tree_t *tree, void *node); 2547c478bd9Sstevel@tonic-gate 255b5fca8f8Stomee /* 256b5fca8f8Stomee * Reinsert a node only if its order has changed relative to its nearest 257b5fca8f8Stomee * neighbors. To optimize performance avl_update_lt() checks only the previous 258b5fca8f8Stomee * node and avl_update_gt() checks only the next node. Use avl_update_lt() and 259b5fca8f8Stomee * avl_update_gt() only if you know the direction in which the order of the 260b5fca8f8Stomee * node may change. 261b5fca8f8Stomee */ 262b5fca8f8Stomee extern boolean_t avl_update(avl_tree_t *, void *); 263b5fca8f8Stomee extern boolean_t avl_update_lt(avl_tree_t *, void *); 264b5fca8f8Stomee extern boolean_t avl_update_gt(avl_tree_t *, void *); 2657c478bd9Sstevel@tonic-gate 266*0f6d88adSAlex Reece /* 267*0f6d88adSAlex Reece * Swaps the contents of the two trees. 268*0f6d88adSAlex Reece */ 269*0f6d88adSAlex Reece extern void avl_swap(avl_tree_t *tree1, avl_tree_t *tree2); 270*0f6d88adSAlex Reece 2717c478bd9Sstevel@tonic-gate /* 2727c478bd9Sstevel@tonic-gate * Return the number of nodes in the tree 2737c478bd9Sstevel@tonic-gate */ 2747c478bd9Sstevel@tonic-gate extern ulong_t avl_numnodes(avl_tree_t *tree); 2757c478bd9Sstevel@tonic-gate 276b5fca8f8Stomee /* 277b5fca8f8Stomee * Return B_TRUE if there are zero nodes in the tree, B_FALSE otherwise. 278b5fca8f8Stomee */ 279b5fca8f8Stomee extern boolean_t avl_is_empty(avl_tree_t *tree); 2807c478bd9Sstevel@tonic-gate 2817c478bd9Sstevel@tonic-gate /* 2827c478bd9Sstevel@tonic-gate * Used to destroy any remaining nodes in a tree. The cookie argument should 2837c478bd9Sstevel@tonic-gate * be initialized to NULL before the first call. Returns a node that has been 2847c478bd9Sstevel@tonic-gate * removed from the tree and may be free()'d. Returns NULL when the tree is 2857c478bd9Sstevel@tonic-gate * empty. 2867c478bd9Sstevel@tonic-gate * 2877c478bd9Sstevel@tonic-gate * Once you call avl_destroy_nodes(), you can only continuing calling it and 2887c478bd9Sstevel@tonic-gate * finally avl_destroy(). No other AVL routines will be valid. 2897c478bd9Sstevel@tonic-gate * 2907c478bd9Sstevel@tonic-gate * cookie - a "void *" used to save state between calls to avl_destroy_nodes() 2917c478bd9Sstevel@tonic-gate * 2927c478bd9Sstevel@tonic-gate * EXAMPLE: 2937c478bd9Sstevel@tonic-gate * avl_tree_t *tree; 2947c478bd9Sstevel@tonic-gate * struct my_data *node; 2957c478bd9Sstevel@tonic-gate * void *cookie; 2967c478bd9Sstevel@tonic-gate * 2977c478bd9Sstevel@tonic-gate * cookie = NULL; 2987c478bd9Sstevel@tonic-gate * while ((node = avl_destroy_nodes(tree, &cookie)) != NULL) 2997c478bd9Sstevel@tonic-gate * free(node); 3007c478bd9Sstevel@tonic-gate * avl_destroy(tree); 3017c478bd9Sstevel@tonic-gate */ 3027c478bd9Sstevel@tonic-gate extern void *avl_destroy_nodes(avl_tree_t *tree, void **cookie); 3037c478bd9Sstevel@tonic-gate 3047c478bd9Sstevel@tonic-gate 3057c478bd9Sstevel@tonic-gate /* 3067c478bd9Sstevel@tonic-gate * Final destroy of an AVL tree. Arguments are: 3077c478bd9Sstevel@tonic-gate * 3087c478bd9Sstevel@tonic-gate * tree - the empty tree to destroy 3097c478bd9Sstevel@tonic-gate */ 3107c478bd9Sstevel@tonic-gate extern void avl_destroy(avl_tree_t *tree); 3117c478bd9Sstevel@tonic-gate 3127c478bd9Sstevel@tonic-gate 3137c478bd9Sstevel@tonic-gate 3147c478bd9Sstevel@tonic-gate #ifdef __cplusplus 3157c478bd9Sstevel@tonic-gate } 3167c478bd9Sstevel@tonic-gate #endif 3177c478bd9Sstevel@tonic-gate 3187c478bd9Sstevel@tonic-gate #endif /* _AVL_H */ 319