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