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 57c478bd9Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only 67c478bd9Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance 77c478bd9Sstevel@tonic-gate * with the License. 87c478bd9Sstevel@tonic-gate * 97c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 107c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing. 117c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions 127c478bd9Sstevel@tonic-gate * and limitations under the License. 137c478bd9Sstevel@tonic-gate * 147c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each 157c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 167c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the 177c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying 187c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner] 197c478bd9Sstevel@tonic-gate * 207c478bd9Sstevel@tonic-gate * CDDL HEADER END 217c478bd9Sstevel@tonic-gate */ 227c478bd9Sstevel@tonic-gate /* 23*fa9e4066Sahrens * Copyright 2005 Sun Microsystems, Inc. All rights reserved. 247c478bd9Sstevel@tonic-gate * Use is subject to license terms. 257c478bd9Sstevel@tonic-gate */ 267c478bd9Sstevel@tonic-gate 277c478bd9Sstevel@tonic-gate #ifndef _AVL_H 287c478bd9Sstevel@tonic-gate #define _AVL_H 297c478bd9Sstevel@tonic-gate 307c478bd9Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI" 317c478bd9Sstevel@tonic-gate 327c478bd9Sstevel@tonic-gate /* 337c478bd9Sstevel@tonic-gate * This is a private header file. Applications should not directly include 347c478bd9Sstevel@tonic-gate * this file. 357c478bd9Sstevel@tonic-gate */ 367c478bd9Sstevel@tonic-gate 377c478bd9Sstevel@tonic-gate #ifdef __cplusplus 387c478bd9Sstevel@tonic-gate extern "C" { 397c478bd9Sstevel@tonic-gate #endif 407c478bd9Sstevel@tonic-gate 417c478bd9Sstevel@tonic-gate #include <sys/avl_impl.h> 427c478bd9Sstevel@tonic-gate 437c478bd9Sstevel@tonic-gate /* 447c478bd9Sstevel@tonic-gate * This is a generic implemenatation of AVL trees for use in the Solaris kernel. 457c478bd9Sstevel@tonic-gate * The interfaces provide an efficient way of implementing an ordered set of 467c478bd9Sstevel@tonic-gate * data structures. 477c478bd9Sstevel@tonic-gate * 487c478bd9Sstevel@tonic-gate * AVL trees provide an alternative to using an ordered linked list. Using AVL 497c478bd9Sstevel@tonic-gate * trees will usually be faster, however they requires more storage. An ordered 507c478bd9Sstevel@tonic-gate * linked list in general requires 2 pointers in each data structure. The 517c478bd9Sstevel@tonic-gate * AVL tree implementation uses 3 pointers. The following chart gives the 527c478bd9Sstevel@tonic-gate * approximate performance of operations with the different approaches: 537c478bd9Sstevel@tonic-gate * 547c478bd9Sstevel@tonic-gate * Operation Link List AVL tree 557c478bd9Sstevel@tonic-gate * --------- -------- -------- 567c478bd9Sstevel@tonic-gate * lookup O(n) O(log(n)) 577c478bd9Sstevel@tonic-gate * 587c478bd9Sstevel@tonic-gate * insert 1 node constant constant 597c478bd9Sstevel@tonic-gate * 607c478bd9Sstevel@tonic-gate * delete 1 node constant between constant and O(log(n)) 617c478bd9Sstevel@tonic-gate * 627c478bd9Sstevel@tonic-gate * delete all nodes O(n) O(n) 637c478bd9Sstevel@tonic-gate * 647c478bd9Sstevel@tonic-gate * visit the next 657c478bd9Sstevel@tonic-gate * or prev node constant between constant and O(log(n)) 667c478bd9Sstevel@tonic-gate * 677c478bd9Sstevel@tonic-gate * 687c478bd9Sstevel@tonic-gate * The data structure nodes are anchored at an "avl_tree_t" (the equivalent 697c478bd9Sstevel@tonic-gate * of a list header) and the individual nodes will have a field of 707c478bd9Sstevel@tonic-gate * type "avl_node_t" (corresponding to list pointers). 717c478bd9Sstevel@tonic-gate * 727c478bd9Sstevel@tonic-gate * The type "avl_index_t" is used to indicate a position in the list for 737c478bd9Sstevel@tonic-gate * certain calls. 747c478bd9Sstevel@tonic-gate * 757c478bd9Sstevel@tonic-gate * The usage scenario is generally: 767c478bd9Sstevel@tonic-gate * 777c478bd9Sstevel@tonic-gate * 1. Create the list/tree with: avl_create() 787c478bd9Sstevel@tonic-gate * 797c478bd9Sstevel@tonic-gate * followed by any mixture of: 807c478bd9Sstevel@tonic-gate * 81*fa9e4066Sahrens * 2a. Insert nodes with: avl_add(), or avl_find() and avl_insert() 827c478bd9Sstevel@tonic-gate * 837c478bd9Sstevel@tonic-gate * 2b. Visited elements with: 847c478bd9Sstevel@tonic-gate * avl_first() - returns the lowest valued node 857c478bd9Sstevel@tonic-gate * avl_last() - returns the highest valued node 867c478bd9Sstevel@tonic-gate * AVL_NEXT() - given a node go to next higher one 877c478bd9Sstevel@tonic-gate * AVL_PREV() - given a node go to previous lower one 887c478bd9Sstevel@tonic-gate * 897c478bd9Sstevel@tonic-gate * 2c. Find the node with the closest value either less than or greater 907c478bd9Sstevel@tonic-gate * than a given value with avl_nearest(). 917c478bd9Sstevel@tonic-gate * 92*fa9e4066Sahrens * 2d. Remove individual nodes from the list/tree with avl_remove(). 937c478bd9Sstevel@tonic-gate * 947c478bd9Sstevel@tonic-gate * and finally when the list is being destroyed 957c478bd9Sstevel@tonic-gate * 967c478bd9Sstevel@tonic-gate * 3. Use avl_destroy_nodes() to quickly process/free up any remaining nodes. 977c478bd9Sstevel@tonic-gate * Note that once you use avl_destroy_nodes(), you can no longer 987c478bd9Sstevel@tonic-gate * use any routine except avl_destroy_nodes() and avl_destoy(). 997c478bd9Sstevel@tonic-gate * 1007c478bd9Sstevel@tonic-gate * 4. Use avl_destroy() to destroy the AVL tree itself. 1017c478bd9Sstevel@tonic-gate * 1027c478bd9Sstevel@tonic-gate * Any locking for multiple thread access is up to the user to provide, just 1037c478bd9Sstevel@tonic-gate * as is needed for any linked list implementation. 1047c478bd9Sstevel@tonic-gate */ 1057c478bd9Sstevel@tonic-gate 1067c478bd9Sstevel@tonic-gate 1077c478bd9Sstevel@tonic-gate /* 1087c478bd9Sstevel@tonic-gate * Type used for the root of the AVL tree. 1097c478bd9Sstevel@tonic-gate */ 1107c478bd9Sstevel@tonic-gate typedef struct avl_tree avl_tree_t; 1117c478bd9Sstevel@tonic-gate 1127c478bd9Sstevel@tonic-gate /* 1137c478bd9Sstevel@tonic-gate * The data nodes in the AVL tree must have a field of this type. 1147c478bd9Sstevel@tonic-gate */ 1157c478bd9Sstevel@tonic-gate typedef struct avl_node avl_node_t; 1167c478bd9Sstevel@tonic-gate 1177c478bd9Sstevel@tonic-gate /* 1187c478bd9Sstevel@tonic-gate * An opaque type used to locate a position in the tree where a node 1197c478bd9Sstevel@tonic-gate * would be inserted. 1207c478bd9Sstevel@tonic-gate */ 1217c478bd9Sstevel@tonic-gate typedef uintptr_t avl_index_t; 1227c478bd9Sstevel@tonic-gate 1237c478bd9Sstevel@tonic-gate 1247c478bd9Sstevel@tonic-gate /* 1257c478bd9Sstevel@tonic-gate * Direction constants used for avl_nearest(). 1267c478bd9Sstevel@tonic-gate */ 1277c478bd9Sstevel@tonic-gate #define AVL_BEFORE (0) 1287c478bd9Sstevel@tonic-gate #define AVL_AFTER (1) 1297c478bd9Sstevel@tonic-gate 1307c478bd9Sstevel@tonic-gate 1317c478bd9Sstevel@tonic-gate 1327c478bd9Sstevel@tonic-gate /* 1337c478bd9Sstevel@tonic-gate * Prototypes 1347c478bd9Sstevel@tonic-gate * 1357c478bd9Sstevel@tonic-gate * Where not otherwise mentioned, "void *" arguments are a pointer to the 1367c478bd9Sstevel@tonic-gate * user data structure which must contain a field of type avl_node_t. 1377c478bd9Sstevel@tonic-gate * 1387c478bd9Sstevel@tonic-gate * Also assume the user data structures looks like: 1397c478bd9Sstevel@tonic-gate * stuct my_type { 1407c478bd9Sstevel@tonic-gate * ... 1417c478bd9Sstevel@tonic-gate * avl_node_t my_link; 1427c478bd9Sstevel@tonic-gate * ... 1437c478bd9Sstevel@tonic-gate * }; 1447c478bd9Sstevel@tonic-gate */ 1457c478bd9Sstevel@tonic-gate 1467c478bd9Sstevel@tonic-gate /* 1477c478bd9Sstevel@tonic-gate * Initialize an AVL tree. Arguments are: 1487c478bd9Sstevel@tonic-gate * 1497c478bd9Sstevel@tonic-gate * tree - the tree to be initialized 1507c478bd9Sstevel@tonic-gate * compar - function to compare two nodes, it must return exactly: -1, 0, or +1 1517c478bd9Sstevel@tonic-gate * -1 for <, 0 for ==, and +1 for > 1527c478bd9Sstevel@tonic-gate * size - the value of sizeof(struct my_type) 1537c478bd9Sstevel@tonic-gate * offset - the value of OFFSETOF(struct my_type, my_link) 1547c478bd9Sstevel@tonic-gate */ 1557c478bd9Sstevel@tonic-gate extern void avl_create(avl_tree_t *tree, 1567c478bd9Sstevel@tonic-gate int (*compar) (const void *, const void *), size_t size, size_t offset); 1577c478bd9Sstevel@tonic-gate 1587c478bd9Sstevel@tonic-gate 1597c478bd9Sstevel@tonic-gate /* 1607c478bd9Sstevel@tonic-gate * Find a node with a matching value in the tree. Returns the matching node 1617c478bd9Sstevel@tonic-gate * found. If not found, it returns NULL and then if "where" is not NULL it sets 1627c478bd9Sstevel@tonic-gate * "where" for use with avl_insert() or avl_nearest(). 1637c478bd9Sstevel@tonic-gate * 1647c478bd9Sstevel@tonic-gate * node - node that has the value being looked for 1657c478bd9Sstevel@tonic-gate * where - position for use with avl_nearest() or avl_insert(), may be NULL 1667c478bd9Sstevel@tonic-gate */ 1677c478bd9Sstevel@tonic-gate extern void *avl_find(avl_tree_t *tree, void *node, avl_index_t *where); 1687c478bd9Sstevel@tonic-gate 1697c478bd9Sstevel@tonic-gate /* 1707c478bd9Sstevel@tonic-gate * Insert a node into the tree. 1717c478bd9Sstevel@tonic-gate * 1727c478bd9Sstevel@tonic-gate * node - the node to insert 1737c478bd9Sstevel@tonic-gate * where - position as returned from avl_find() 1747c478bd9Sstevel@tonic-gate */ 1757c478bd9Sstevel@tonic-gate extern void avl_insert(avl_tree_t *tree, void *node, avl_index_t where); 1767c478bd9Sstevel@tonic-gate 1777c478bd9Sstevel@tonic-gate /* 1787c478bd9Sstevel@tonic-gate * Insert "new_data" in "tree" in the given "direction" either after 1797c478bd9Sstevel@tonic-gate * or before the data "here". 1807c478bd9Sstevel@tonic-gate * 1817c478bd9Sstevel@tonic-gate * This might be usefull for avl clients caching recently accessed 1827c478bd9Sstevel@tonic-gate * data to avoid doing avl_find() again for insertion. 1837c478bd9Sstevel@tonic-gate * 1847c478bd9Sstevel@tonic-gate * new_data - new data to insert 1857c478bd9Sstevel@tonic-gate * here - existing node in "tree" 1867c478bd9Sstevel@tonic-gate * direction - either AVL_AFTER or AVL_BEFORE the data "here". 1877c478bd9Sstevel@tonic-gate */ 1887c478bd9Sstevel@tonic-gate extern void avl_insert_here(avl_tree_t *tree, void *new_data, void *here, 1897c478bd9Sstevel@tonic-gate int direction); 1907c478bd9Sstevel@tonic-gate 1917c478bd9Sstevel@tonic-gate 1927c478bd9Sstevel@tonic-gate /* 1937c478bd9Sstevel@tonic-gate * Return the first or last valued node in the tree. Will return NULL 1947c478bd9Sstevel@tonic-gate * if the tree is empty. 1957c478bd9Sstevel@tonic-gate * 1967c478bd9Sstevel@tonic-gate */ 1977c478bd9Sstevel@tonic-gate extern void *avl_first(avl_tree_t *tree); 1987c478bd9Sstevel@tonic-gate extern void *avl_last(avl_tree_t *tree); 1997c478bd9Sstevel@tonic-gate 2007c478bd9Sstevel@tonic-gate 2017c478bd9Sstevel@tonic-gate /* 2027c478bd9Sstevel@tonic-gate * Return the next or previous valued node in the tree. 2037c478bd9Sstevel@tonic-gate * AVL_NEXT() will return NULL if at the last node. 2047c478bd9Sstevel@tonic-gate * AVL_PREV() will return NULL if at the first node. 2057c478bd9Sstevel@tonic-gate * 2067c478bd9Sstevel@tonic-gate * node - the node from which the next or previous node is found 2077c478bd9Sstevel@tonic-gate */ 2087c478bd9Sstevel@tonic-gate #define AVL_NEXT(tree, node) avl_walk(tree, node, AVL_AFTER) 2097c478bd9Sstevel@tonic-gate #define AVL_PREV(tree, node) avl_walk(tree, node, AVL_BEFORE) 2107c478bd9Sstevel@tonic-gate 2117c478bd9Sstevel@tonic-gate 2127c478bd9Sstevel@tonic-gate /* 2137c478bd9Sstevel@tonic-gate * Find the node with the nearest value either greater or less than 2147c478bd9Sstevel@tonic-gate * the value from a previous avl_find(). Returns the node or NULL if 2157c478bd9Sstevel@tonic-gate * there isn't a matching one. 2167c478bd9Sstevel@tonic-gate * 2177c478bd9Sstevel@tonic-gate * where - position as returned from avl_find() 2187c478bd9Sstevel@tonic-gate * direction - either AVL_BEFORE or AVL_AFTER 2197c478bd9Sstevel@tonic-gate * 2207c478bd9Sstevel@tonic-gate * EXAMPLE get the greatest node that is less than a given value: 2217c478bd9Sstevel@tonic-gate * 2227c478bd9Sstevel@tonic-gate * avl_tree_t *tree; 2237c478bd9Sstevel@tonic-gate * struct my_data look_for_value = {....}; 2247c478bd9Sstevel@tonic-gate * struct my_data *node; 2257c478bd9Sstevel@tonic-gate * struct my_data *less; 2267c478bd9Sstevel@tonic-gate * avl_index_t where; 2277c478bd9Sstevel@tonic-gate * 2287c478bd9Sstevel@tonic-gate * node = avl_find(tree, &look_for_value, &where); 2297c478bd9Sstevel@tonic-gate * if (node != NULL) 2307c478bd9Sstevel@tonic-gate * less = AVL_PREV(tree, node); 2317c478bd9Sstevel@tonic-gate * else 2327c478bd9Sstevel@tonic-gate * less = avl_nearest(tree, where, AVL_BEFORE); 2337c478bd9Sstevel@tonic-gate */ 2347c478bd9Sstevel@tonic-gate extern void *avl_nearest(avl_tree_t *tree, avl_index_t where, int direction); 2357c478bd9Sstevel@tonic-gate 2367c478bd9Sstevel@tonic-gate 2377c478bd9Sstevel@tonic-gate /* 238*fa9e4066Sahrens * Add a single node to the tree. 239*fa9e4066Sahrens * The node must not be in the tree, and it must not 240*fa9e4066Sahrens * compare equal to any other node already in the tree. 241*fa9e4066Sahrens * 242*fa9e4066Sahrens * node - the node to add 243*fa9e4066Sahrens */ 244*fa9e4066Sahrens extern void avl_add(avl_tree_t *tree, void *node); 245*fa9e4066Sahrens 246*fa9e4066Sahrens 247*fa9e4066Sahrens /* 248*fa9e4066Sahrens * Remove a single node from the tree. The node must be in the tree. 2497c478bd9Sstevel@tonic-gate * 2507c478bd9Sstevel@tonic-gate * node - the node to remove 2517c478bd9Sstevel@tonic-gate */ 2527c478bd9Sstevel@tonic-gate extern void avl_remove(avl_tree_t *tree, void *node); 2537c478bd9Sstevel@tonic-gate 2547c478bd9Sstevel@tonic-gate 2557c478bd9Sstevel@tonic-gate /* 2567c478bd9Sstevel@tonic-gate * Return the number of nodes in the tree 2577c478bd9Sstevel@tonic-gate */ 2587c478bd9Sstevel@tonic-gate extern ulong_t avl_numnodes(avl_tree_t *tree); 2597c478bd9Sstevel@tonic-gate 2607c478bd9Sstevel@tonic-gate 2617c478bd9Sstevel@tonic-gate /* 2627c478bd9Sstevel@tonic-gate * Used to destroy any remaining nodes in a tree. The cookie argument should 2637c478bd9Sstevel@tonic-gate * be initialized to NULL before the first call. Returns a node that has been 2647c478bd9Sstevel@tonic-gate * removed from the tree and may be free()'d. Returns NULL when the tree is 2657c478bd9Sstevel@tonic-gate * empty. 2667c478bd9Sstevel@tonic-gate * 2677c478bd9Sstevel@tonic-gate * Once you call avl_destroy_nodes(), you can only continuing calling it and 2687c478bd9Sstevel@tonic-gate * finally avl_destroy(). No other AVL routines will be valid. 2697c478bd9Sstevel@tonic-gate * 2707c478bd9Sstevel@tonic-gate * cookie - a "void *" used to save state between calls to avl_destroy_nodes() 2717c478bd9Sstevel@tonic-gate * 2727c478bd9Sstevel@tonic-gate * EXAMPLE: 2737c478bd9Sstevel@tonic-gate * avl_tree_t *tree; 2747c478bd9Sstevel@tonic-gate * struct my_data *node; 2757c478bd9Sstevel@tonic-gate * void *cookie; 2767c478bd9Sstevel@tonic-gate * 2777c478bd9Sstevel@tonic-gate * cookie = NULL; 2787c478bd9Sstevel@tonic-gate * while ((node = avl_destroy_nodes(tree, &cookie)) != NULL) 2797c478bd9Sstevel@tonic-gate * free(node); 2807c478bd9Sstevel@tonic-gate * avl_destroy(tree); 2817c478bd9Sstevel@tonic-gate */ 2827c478bd9Sstevel@tonic-gate extern void *avl_destroy_nodes(avl_tree_t *tree, void **cookie); 2837c478bd9Sstevel@tonic-gate 2847c478bd9Sstevel@tonic-gate 2857c478bd9Sstevel@tonic-gate /* 2867c478bd9Sstevel@tonic-gate * Final destroy of an AVL tree. Arguments are: 2877c478bd9Sstevel@tonic-gate * 2887c478bd9Sstevel@tonic-gate * tree - the empty tree to destroy 2897c478bd9Sstevel@tonic-gate */ 2907c478bd9Sstevel@tonic-gate extern void avl_destroy(avl_tree_t *tree); 2917c478bd9Sstevel@tonic-gate 2927c478bd9Sstevel@tonic-gate 2937c478bd9Sstevel@tonic-gate 2947c478bd9Sstevel@tonic-gate #ifdef __cplusplus 2957c478bd9Sstevel@tonic-gate } 2967c478bd9Sstevel@tonic-gate #endif 2977c478bd9Sstevel@tonic-gate 2987c478bd9Sstevel@tonic-gate #endif /* _AVL_H */ 299