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