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