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 #ifndef FB_AVL_H 27 #define FB_AVL_H 28 29 /* 30 * derived from Solaris' sys/avl.h and sys/avl_impl.h 31 */ 32 33 #ifdef __cplusplus 34 extern "C" { 35 #endif 36 37 #include <sys/types.h> 38 39 /* 40 * generic AVL tree implementation for FileBench use 41 * 42 * The interfaces provide an efficient way of implementing an ordered set of 43 * data 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 constant 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 * There are 5 pieces of information stored for each node in an AVL tree 66 * 67 * pointer to less than child 68 * pointer to greater than child 69 * a pointer to the parent of this node 70 * an indication [0/1] of which child I am of my parent 71 * a "balance" (-1, 0, +1) indicating which child tree is taller 72 * 73 * Since they only need 3 bits, the last two fields are packed into the 74 * bottom bits of the parent pointer on 64 bit machines to save on space. 75 */ 76 77 #ifndef _LP64 78 79 struct avl_node { 80 struct avl_node *avl_child[2]; /* left/right children */ 81 struct avl_node *avl_parent; /* this node's parent */ 82 unsigned short avl_child_index; /* my index in parent's avl_child[] */ 83 short avl_balance; /* balance value: -1, 0, +1 */ 84 }; 85 86 #define AVL_XPARENT(n) ((n)->avl_parent) 87 #define AVL_SETPARENT(n, p) ((n)->avl_parent = (p)) 88 89 #define AVL_XCHILD(n) ((n)->avl_child_index) 90 #define AVL_SETCHILD(n, c) ((n)->avl_child_index = (unsigned short)(c)) 91 92 #define AVL_XBALANCE(n) ((n)->avl_balance) 93 #define AVL_SETBALANCE(n, b) ((n)->avl_balance = (short)(b)) 94 95 #else /* _LP64 */ 96 97 /* 98 * for 64 bit machines, avl_pcb contains parent pointer, balance and child_index 99 * values packed in the following manner: 100 * 101 * |63 3| 2 |1 0 | 102 * |-------------------------------------|-----------------|-------------| 103 * | avl_parent hi order bits | avl_child_index | avl_balance | 104 * | | | + 1 | 105 * |-------------------------------------|-----------------|-------------| 106 * 107 */ 108 struct avl_node { 109 struct avl_node *avl_child[2]; /* left/right children nodes */ 110 uintptr_t avl_pcb; /* parent, child_index, balance */ 111 }; 112 113 /* 114 * macros to extract/set fields in avl_pcb 115 * 116 * pointer to the parent of the current node is the high order bits 117 */ 118 #define AVL_XPARENT(n) ((struct avl_node *)((n)->avl_pcb & ~7)) 119 #define AVL_SETPARENT(n, p) \ 120 ((n)->avl_pcb = (((n)->avl_pcb & 7) | (uintptr_t)(p))) 121 122 /* 123 * index of this node in its parent's avl_child[]: bit #2 124 */ 125 #define AVL_XCHILD(n) (((n)->avl_pcb >> 2) & 1) 126 #define AVL_SETCHILD(n, c) \ 127 ((n)->avl_pcb = (uintptr_t)(((n)->avl_pcb & ~4) | ((c) << 2))) 128 129 /* 130 * balance indication for a node, lowest 2 bits. A valid balance is 131 * -1, 0, or +1, and is encoded by adding 1 to the value to get the 132 * unsigned values of 0, 1, 2. 133 */ 134 #define AVL_XBALANCE(n) ((int)(((n)->avl_pcb & 3) - 1)) 135 #define AVL_SETBALANCE(n, b) \ 136 ((n)->avl_pcb = (uintptr_t)((((n)->avl_pcb & ~3) | ((b) + 1)))) 137 138 #endif /* _LP64 */ 139 140 141 142 /* 143 * switch between a node and data pointer for a given tree 144 * the value of "o" is tree->avl_offset 145 */ 146 #define AVL_NODE2DATA(n, o) ((void *)((uintptr_t)(n) - (o))) 147 #define AVL_DATA2NODE(d, o) ((struct avl_node *)((uintptr_t)(d) + (o))) 148 149 150 151 /* 152 * macros used to create/access an avl_index_t 153 */ 154 #define AVL_INDEX2NODE(x) ((avl_node_t *)((x) & ~1)) 155 #define AVL_INDEX2CHILD(x) ((x) & 1) 156 #define AVL_MKINDEX(n, c) ((avl_index_t)(n) | (c)) 157 158 159 /* 160 * The tree structure. The fields avl_root, avl_compar, and avl_offset come 161 * first since they are needed for avl_find(). We want them to fit into 162 * a single 64 byte cache line to make avl_find() as fast as possible. 163 */ 164 struct avl_tree { 165 struct avl_node *avl_root; /* root node in tree */ 166 int (*avl_compar)(const void *, const void *); 167 size_t avl_offset; /* offsetof(type, avl_link_t field) */ 168 unsigned long avl_numnodes; /* number of nodes in the tree */ 169 size_t avl_size; /* sizeof user type struct */ 170 }; 171 172 173 /* 174 * This will only by used via AVL_NEXT() or AVL_PREV() 175 */ 176 extern void *avl_walk(struct avl_tree *, void *, int); 177 178 179 /* 180 * The data structure nodes are anchored at an "avl_tree_t" (the equivalent 181 * of a list header) and the individual nodes will have a field of 182 * type "avl_node_t" (corresponding to list pointers). 183 * 184 * The type "avl_index_t" is used to indicate a position in the list for 185 * certain calls. 186 * 187 * The usage scenario is generally: 188 * 189 * 1. Create the list/tree with: avl_create() 190 * 191 * followed by any mixture of: 192 * 193 * 2a. Insert nodes with: avl_add(), or avl_find() and avl_insert() 194 * 195 * 2b. Visited elements with: 196 * avl_first() - returns the lowest valued node 197 * avl_last() - returns the highest valued node 198 * AVL_NEXT() - given a node go to next higher one 199 * AVL_PREV() - given a node go to previous lower one 200 * 201 * 2c. Find the node with the closest value either less than or greater 202 * than a given value with avl_nearest(). 203 * 204 * 2d. Remove individual nodes from the list/tree with avl_remove(). 205 * 206 * and finally when the list is being destroyed 207 * 208 * 3. Use avl_destroy_nodes() to quickly process/free up any remaining nodes. 209 * Note that once you use avl_destroy_nodes(), you can no longer 210 * use any routine except avl_destroy_nodes() and avl_destoy(). 211 * 212 * 4. Use avl_destroy() to destroy the AVL tree itself. 213 * 214 * Any locking for multiple thread access is up to the user to provide, just 215 * as is needed for any linked list implementation. 216 */ 217 218 219 /* 220 * Type used for the root of the AVL tree. 221 */ 222 typedef struct avl_tree avl_tree_t; 223 224 /* 225 * The data nodes in the AVL tree must have a field of this type. 226 */ 227 typedef struct avl_node avl_node_t; 228 229 /* 230 * An opaque type used to locate a position in the tree where a node 231 * would be inserted. 232 */ 233 typedef uintptr_t avl_index_t; 234 235 236 /* 237 * Direction constants used for avl_nearest(). 238 */ 239 #define AVL_BEFORE (0) 240 #define AVL_AFTER (1) 241 242 243 /* 244 * Prototypes 245 * 246 * Where not otherwise mentioned, "void *" arguments are a pointer to the 247 * user data structure which must contain a field of type avl_node_t. 248 * 249 * Also assume the user data structures looks like: 250 * stuct my_type { 251 * ... 252 * avl_node_t my_link; 253 * ... 254 * }; 255 */ 256 257 /* 258 * Initialize an AVL tree. Arguments are: 259 * 260 * tree - the tree to be initialized 261 * compar - function to compare two nodes, it must return exactly: -1, 0, or +1 262 * -1 for <, 0 for ==, and +1 for > 263 * size - the value of sizeof(struct my_type) 264 * offset - the value of OFFSETOF(struct my_type, my_link) 265 */ 266 extern void avl_create(avl_tree_t *tree, 267 int (*compar) (const void *, const void *), size_t size, size_t offset); 268 269 270 /* 271 * Find a node with a matching value in the tree. Returns the matching node 272 * found. If not found, it returns NULL and then if "where" is not NULL it sets 273 * "where" for use with avl_insert() or avl_nearest(). 274 * 275 * node - node that has the value being looked for 276 * where - position for use with avl_nearest() or avl_insert(), may be NULL 277 */ 278 extern void *avl_find(avl_tree_t *tree, void *node, avl_index_t *where); 279 280 /* 281 * Insert a node into the tree. 282 * 283 * node - the node to insert 284 * where - position as returned from avl_find() 285 */ 286 extern void avl_insert(avl_tree_t *tree, void *node, avl_index_t where); 287 288 /* 289 * Insert "new_data" in "tree" in the given "direction" either after 290 * or before the data "here". 291 * 292 * This might be usefull for avl clients caching recently accessed 293 * data to avoid doing avl_find() again for insertion. 294 * 295 * new_data - new data to insert 296 * here - existing node in "tree" 297 * direction - either AVL_AFTER or AVL_BEFORE the data "here". 298 */ 299 extern void avl_insert_here(avl_tree_t *tree, void *new_data, void *here, 300 int direction); 301 302 303 /* 304 * Return the first or last valued node in the tree. Will return NULL 305 * if the tree is empty. 306 * 307 */ 308 extern void *avl_first(avl_tree_t *tree); 309 extern void *avl_last(avl_tree_t *tree); 310 311 312 /* 313 * Return the next or previous valued node in the tree. 314 * AVL_NEXT() will return NULL if at the last node. 315 * AVL_PREV() will return NULL if at the first node. 316 * 317 * node - the node from which the next or previous node is found 318 */ 319 #define AVL_NEXT(tree, node) avl_walk(tree, node, AVL_AFTER) 320 #define AVL_PREV(tree, node) avl_walk(tree, node, AVL_BEFORE) 321 322 323 /* 324 * Find the node with the nearest value either greater or less than 325 * the value from a previous avl_find(). Returns the node or NULL if 326 * there isn't a matching one. 327 * 328 * where - position as returned from avl_find() 329 * direction - either AVL_BEFORE or AVL_AFTER 330 * 331 * EXAMPLE get the greatest node that is less than a given value: 332 * 333 * avl_tree_t *tree; 334 * struct my_data look_for_value = {....}; 335 * struct my_data *node; 336 * struct my_data *less; 337 * avl_index_t where; 338 * 339 * node = avl_find(tree, &look_for_value, &where); 340 * if (node != NULL) 341 * less = AVL_PREV(tree, node); 342 * else 343 * less = avl_nearest(tree, where, AVL_BEFORE); 344 */ 345 extern void *avl_nearest(avl_tree_t *tree, avl_index_t where, int direction); 346 347 348 /* 349 * Add a single node to the tree. 350 * The node must not be in the tree, and it must not 351 * compare equal to any other node already in the tree. 352 * 353 * node - the node to add 354 */ 355 extern void avl_add(avl_tree_t *tree, void *node); 356 357 358 /* 359 * Remove a single node from the tree. The node must be in the tree. 360 * 361 * node - the node to remove 362 */ 363 extern void avl_remove(avl_tree_t *tree, void *node); 364 365 /* 366 * Reinsert a node only if its order has changed relative to its nearest 367 * neighbors. To optimize performance avl_update_lt() checks only the previous 368 * node and avl_update_gt() checks only the next node. Use avl_update_lt() and 369 * avl_update_gt() only if you know the direction in which the order of the 370 * node may change. 371 */ 372 extern boolean_t avl_update(avl_tree_t *, void *); 373 extern boolean_t avl_update_lt(avl_tree_t *, void *); 374 extern boolean_t avl_update_gt(avl_tree_t *, void *); 375 376 /* 377 * Return the number of nodes in the tree 378 */ 379 extern unsigned long avl_numnodes(avl_tree_t *tree); 380 381 /* 382 * Return B_TRUE if there are zero nodes in the tree, B_FALSE otherwise. 383 */ 384 extern boolean_t avl_is_empty(avl_tree_t *tree); 385 386 /* 387 * Used to destroy any remaining nodes in a tree. The cookie argument should 388 * be initialized to NULL before the first call. Returns a node that has been 389 * removed from the tree and may be free()'d. Returns NULL when the tree is 390 * empty. 391 * 392 * Once you call avl_destroy_nodes(), you can only continuing calling it and 393 * finally avl_destroy(). No other AVL routines will be valid. 394 * 395 * cookie - a "void *" used to save state between calls to avl_destroy_nodes() 396 * 397 * EXAMPLE: 398 * avl_tree_t *tree; 399 * struct my_data *node; 400 * void *cookie; 401 * 402 * cookie = NULL; 403 * while ((node = avl_destroy_nodes(tree, &cookie)) != NULL) 404 * free(node); 405 * avl_destroy(tree); 406 */ 407 extern void *avl_destroy_nodes(avl_tree_t *tree, void **cookie); 408 409 410 /* 411 * Final destroy of an AVL tree. Arguments are: 412 * 413 * tree - the empty tree to destroy 414 */ 415 extern void avl_destroy(avl_tree_t *tree); 416 417 418 419 #ifdef __cplusplus 420 } 421 #endif 422 423 #endif /* FB_AVL_H */