1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* 23 * Copyright 2005 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 */ 26 27 #ifndef _AVL_H 28 #define _AVL_H 29 30 #pragma ident "%Z%%M% %I% %E% SMI" 31 32 /* 33 * This is a private header file. Applications should not directly include 34 * this file. 35 */ 36 37 #ifdef __cplusplus 38 extern "C" { 39 #endif 40 41 #include <sys/avl_impl.h> 42 43 /* 44 * This is a generic implemenatation of AVL trees for use in the Solaris kernel. 45 * The interfaces provide an efficient way of implementing an ordered set of 46 * data structures. 47 * 48 * AVL trees provide an alternative to using an ordered linked list. Using AVL 49 * trees will usually be faster, however they requires more storage. An ordered 50 * linked list in general requires 2 pointers in each data structure. The 51 * AVL tree implementation uses 3 pointers. The following chart gives the 52 * approximate performance of operations with the different approaches: 53 * 54 * Operation Link List AVL tree 55 * --------- -------- -------- 56 * lookup O(n) O(log(n)) 57 * 58 * insert 1 node constant constant 59 * 60 * delete 1 node constant between constant and O(log(n)) 61 * 62 * delete all nodes O(n) O(n) 63 * 64 * visit the next 65 * or prev node constant between constant and O(log(n)) 66 * 67 * 68 * The data structure nodes are anchored at an "avl_tree_t" (the equivalent 69 * of a list header) and the individual nodes will have a field of 70 * type "avl_node_t" (corresponding to list pointers). 71 * 72 * The type "avl_index_t" is used to indicate a position in the list for 73 * certain calls. 74 * 75 * The usage scenario is generally: 76 * 77 * 1. Create the list/tree with: avl_create() 78 * 79 * followed by any mixture of: 80 * 81 * 2a. Insert nodes with: avl_add(), or avl_find() and avl_insert() 82 * 83 * 2b. Visited elements with: 84 * avl_first() - returns the lowest valued node 85 * avl_last() - returns the highest valued node 86 * AVL_NEXT() - given a node go to next higher one 87 * AVL_PREV() - given a node go to previous lower one 88 * 89 * 2c. Find the node with the closest value either less than or greater 90 * than a given value with avl_nearest(). 91 * 92 * 2d. Remove individual nodes from the list/tree with avl_remove(). 93 * 94 * and finally when the list is being destroyed 95 * 96 * 3. Use avl_destroy_nodes() to quickly process/free up any remaining nodes. 97 * Note that once you use avl_destroy_nodes(), you can no longer 98 * use any routine except avl_destroy_nodes() and avl_destoy(). 99 * 100 * 4. Use avl_destroy() to destroy the AVL tree itself. 101 * 102 * Any locking for multiple thread access is up to the user to provide, just 103 * as is needed for any linked list implementation. 104 */ 105 106 107 /* 108 * Type used for the root of the AVL tree. 109 */ 110 typedef struct avl_tree avl_tree_t; 111 112 /* 113 * The data nodes in the AVL tree must have a field of this type. 114 */ 115 typedef struct avl_node avl_node_t; 116 117 /* 118 * An opaque type used to locate a position in the tree where a node 119 * would be inserted. 120 */ 121 typedef uintptr_t avl_index_t; 122 123 124 /* 125 * Direction constants used for avl_nearest(). 126 */ 127 #define AVL_BEFORE (0) 128 #define AVL_AFTER (1) 129 130 131 132 /* 133 * Prototypes 134 * 135 * Where not otherwise mentioned, "void *" arguments are a pointer to the 136 * user data structure which must contain a field of type avl_node_t. 137 * 138 * Also assume the user data structures looks like: 139 * stuct my_type { 140 * ... 141 * avl_node_t my_link; 142 * ... 143 * }; 144 */ 145 146 /* 147 * Initialize an AVL tree. Arguments are: 148 * 149 * tree - the tree to be initialized 150 * compar - function to compare two nodes, it must return exactly: -1, 0, or +1 151 * -1 for <, 0 for ==, and +1 for > 152 * size - the value of sizeof(struct my_type) 153 * offset - the value of OFFSETOF(struct my_type, my_link) 154 */ 155 extern void avl_create(avl_tree_t *tree, 156 int (*compar) (const void *, const void *), size_t size, size_t offset); 157 158 159 /* 160 * Find a node with a matching value in the tree. Returns the matching node 161 * found. If not found, it returns NULL and then if "where" is not NULL it sets 162 * "where" for use with avl_insert() or avl_nearest(). 163 * 164 * node - node that has the value being looked for 165 * where - position for use with avl_nearest() or avl_insert(), may be NULL 166 */ 167 extern void *avl_find(avl_tree_t *tree, void *node, avl_index_t *where); 168 169 /* 170 * Insert a node into the tree. 171 * 172 * node - the node to insert 173 * where - position as returned from avl_find() 174 */ 175 extern void avl_insert(avl_tree_t *tree, void *node, avl_index_t where); 176 177 /* 178 * Insert "new_data" in "tree" in the given "direction" either after 179 * or before the data "here". 180 * 181 * This might be usefull for avl clients caching recently accessed 182 * data to avoid doing avl_find() again for insertion. 183 * 184 * new_data - new data to insert 185 * here - existing node in "tree" 186 * direction - either AVL_AFTER or AVL_BEFORE the data "here". 187 */ 188 extern void avl_insert_here(avl_tree_t *tree, void *new_data, void *here, 189 int direction); 190 191 192 /* 193 * Return the first or last valued node in the tree. Will return NULL 194 * if the tree is empty. 195 * 196 */ 197 extern void *avl_first(avl_tree_t *tree); 198 extern void *avl_last(avl_tree_t *tree); 199 200 201 /* 202 * Return the next or previous valued node in the tree. 203 * AVL_NEXT() will return NULL if at the last node. 204 * AVL_PREV() will return NULL if at the first node. 205 * 206 * node - the node from which the next or previous node is found 207 */ 208 #define AVL_NEXT(tree, node) avl_walk(tree, node, AVL_AFTER) 209 #define AVL_PREV(tree, node) avl_walk(tree, node, AVL_BEFORE) 210 211 212 /* 213 * Find the node with the nearest value either greater or less than 214 * the value from a previous avl_find(). Returns the node or NULL if 215 * there isn't a matching one. 216 * 217 * where - position as returned from avl_find() 218 * direction - either AVL_BEFORE or AVL_AFTER 219 * 220 * EXAMPLE get the greatest node that is less than a given value: 221 * 222 * avl_tree_t *tree; 223 * struct my_data look_for_value = {....}; 224 * struct my_data *node; 225 * struct my_data *less; 226 * avl_index_t where; 227 * 228 * node = avl_find(tree, &look_for_value, &where); 229 * if (node != NULL) 230 * less = AVL_PREV(tree, node); 231 * else 232 * less = avl_nearest(tree, where, AVL_BEFORE); 233 */ 234 extern void *avl_nearest(avl_tree_t *tree, avl_index_t where, int direction); 235 236 237 /* 238 * Add a single node to the tree. 239 * The node must not be in the tree, and it must not 240 * compare equal to any other node already in the tree. 241 * 242 * node - the node to add 243 */ 244 extern void avl_add(avl_tree_t *tree, void *node); 245 246 247 /* 248 * Remove a single node from the tree. The node must be in the tree. 249 * 250 * node - the node to remove 251 */ 252 extern void avl_remove(avl_tree_t *tree, void *node); 253 254 255 /* 256 * Return the number of nodes in the tree 257 */ 258 extern ulong_t avl_numnodes(avl_tree_t *tree); 259 260 261 /* 262 * Used to destroy any remaining nodes in a tree. The cookie argument should 263 * be initialized to NULL before the first call. Returns a node that has been 264 * removed from the tree and may be free()'d. Returns NULL when the tree is 265 * empty. 266 * 267 * Once you call avl_destroy_nodes(), you can only continuing calling it and 268 * finally avl_destroy(). No other AVL routines will be valid. 269 * 270 * cookie - a "void *" used to save state between calls to avl_destroy_nodes() 271 * 272 * EXAMPLE: 273 * avl_tree_t *tree; 274 * struct my_data *node; 275 * void *cookie; 276 * 277 * cookie = NULL; 278 * while ((node = avl_destroy_nodes(tree, &cookie)) != NULL) 279 * free(node); 280 * avl_destroy(tree); 281 */ 282 extern void *avl_destroy_nodes(avl_tree_t *tree, void **cookie); 283 284 285 /* 286 * Final destroy of an AVL tree. Arguments are: 287 * 288 * tree - the empty tree to destroy 289 */ 290 extern void avl_destroy(avl_tree_t *tree); 291 292 293 294 #ifdef __cplusplus 295 } 296 #endif 297 298 #endif /* _AVL_H */ 299