avl.h revision 185029
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 2008 Sun Microsystems, Inc. All rights reserved. 23 * Use is subject to license terms. 24 */ 25 26#ifndef _AVL_H 27#define _AVL_H 28 29#pragma ident "%Z%%M% %I% %E% SMI" 30 31/* 32 * This is a private header file. Applications should not directly include 33 * this file. 34 */ 35 36#ifdef __cplusplus 37extern "C" { 38#endif 39 40#include <sys/types.h> 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 */ 110typedef struct avl_tree avl_tree_t; 111 112/* 113 * The data nodes in the AVL tree must have a field of this type. 114 */ 115typedef 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 */ 121typedef 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 * Prototypes 133 * 134 * Where not otherwise mentioned, "void *" arguments are a pointer to the 135 * user data structure which must contain a field of type avl_node_t. 136 * 137 * Also assume the user data structures looks like: 138 * stuct my_type { 139 * ... 140 * avl_node_t my_link; 141 * ... 142 * }; 143 */ 144 145/* 146 * Initialize an AVL tree. Arguments are: 147 * 148 * tree - the tree to be initialized 149 * compar - function to compare two nodes, it must return exactly: -1, 0, or +1 150 * -1 for <, 0 for ==, and +1 for > 151 * size - the value of sizeof(struct my_type) 152 * offset - the value of OFFSETOF(struct my_type, my_link) 153 */ 154extern void avl_create(avl_tree_t *tree, 155 int (*compar) (const void *, const void *), size_t size, size_t offset); 156 157 158/* 159 * Find a node with a matching value in the tree. Returns the matching node 160 * found. If not found, it returns NULL and then if "where" is not NULL it sets 161 * "where" for use with avl_insert() or avl_nearest(). 162 * 163 * node - node that has the value being looked for 164 * where - position for use with avl_nearest() or avl_insert(), may be NULL 165 */ 166extern void *avl_find(avl_tree_t *tree, void *node, avl_index_t *where); 167 168/* 169 * Insert a node into the tree. 170 * 171 * node - the node to insert 172 * where - position as returned from avl_find() 173 */ 174extern void avl_insert(avl_tree_t *tree, void *node, avl_index_t where); 175 176/* 177 * Insert "new_data" in "tree" in the given "direction" either after 178 * or before the data "here". 179 * 180 * This might be usefull for avl clients caching recently accessed 181 * data to avoid doing avl_find() again for insertion. 182 * 183 * new_data - new data to insert 184 * here - existing node in "tree" 185 * direction - either AVL_AFTER or AVL_BEFORE the data "here". 186 */ 187extern void avl_insert_here(avl_tree_t *tree, void *new_data, void *here, 188 int direction); 189 190 191/* 192 * Return the first or last valued node in the tree. Will return NULL 193 * if the tree is empty. 194 * 195 */ 196extern void *avl_first(avl_tree_t *tree); 197extern void *avl_last(avl_tree_t *tree); 198 199 200/* 201 * Return the next or previous valued node in the tree. 202 * AVL_NEXT() will return NULL if at the last node. 203 * AVL_PREV() will return NULL if at the first node. 204 * 205 * node - the node from which the next or previous node is found 206 */ 207#define AVL_NEXT(tree, node) avl_walk(tree, node, AVL_AFTER) 208#define AVL_PREV(tree, node) avl_walk(tree, node, AVL_BEFORE) 209 210 211/* 212 * Find the node with the nearest value either greater or less than 213 * the value from a previous avl_find(). Returns the node or NULL if 214 * there isn't a matching one. 215 * 216 * where - position as returned from avl_find() 217 * direction - either AVL_BEFORE or AVL_AFTER 218 * 219 * EXAMPLE get the greatest node that is less than a given value: 220 * 221 * avl_tree_t *tree; 222 * struct my_data look_for_value = {....}; 223 * struct my_data *node; 224 * struct my_data *less; 225 * avl_index_t where; 226 * 227 * node = avl_find(tree, &look_for_value, &where); 228 * if (node != NULL) 229 * less = AVL_PREV(tree, node); 230 * else 231 * less = avl_nearest(tree, where, AVL_BEFORE); 232 */ 233extern void *avl_nearest(avl_tree_t *tree, avl_index_t where, int direction); 234 235 236/* 237 * Add a single node to the tree. 238 * The node must not be in the tree, and it must not 239 * compare equal to any other node already in the tree. 240 * 241 * node - the node to add 242 */ 243extern void avl_add(avl_tree_t *tree, void *node); 244 245 246/* 247 * Remove a single node from the tree. The node must be in the tree. 248 * 249 * node - the node to remove 250 */ 251extern void avl_remove(avl_tree_t *tree, void *node); 252 253/* 254 * Reinsert a node only if its order has changed relative to its nearest 255 * neighbors. To optimize performance avl_update_lt() checks only the previous 256 * node and avl_update_gt() checks only the next node. Use avl_update_lt() and 257 * avl_update_gt() only if you know the direction in which the order of the 258 * node may change. 259 */ 260extern boolean_t avl_update(avl_tree_t *, void *); 261extern boolean_t avl_update_lt(avl_tree_t *, void *); 262extern boolean_t avl_update_gt(avl_tree_t *, void *); 263 264/* 265 * Return the number of nodes in the tree 266 */ 267extern ulong_t avl_numnodes(avl_tree_t *tree); 268 269/* 270 * Return B_TRUE if there are zero nodes in the tree, B_FALSE otherwise. 271 */ 272extern boolean_t avl_is_empty(avl_tree_t *tree); 273 274/* 275 * Used to destroy any remaining nodes in a tree. The cookie argument should 276 * be initialized to NULL before the first call. Returns a node that has been 277 * removed from the tree and may be free()'d. Returns NULL when the tree is 278 * empty. 279 * 280 * Once you call avl_destroy_nodes(), you can only continuing calling it and 281 * finally avl_destroy(). No other AVL routines will be valid. 282 * 283 * cookie - a "void *" used to save state between calls to avl_destroy_nodes() 284 * 285 * EXAMPLE: 286 * avl_tree_t *tree; 287 * struct my_data *node; 288 * void *cookie; 289 * 290 * cookie = NULL; 291 * while ((node = avl_destroy_nodes(tree, &cookie)) != NULL) 292 * free(node); 293 * avl_destroy(tree); 294 */ 295extern void *avl_destroy_nodes(avl_tree_t *tree, void **cookie); 296 297 298/* 299 * Final destroy of an AVL tree. Arguments are: 300 * 301 * tree - the empty tree to destroy 302 */ 303extern void avl_destroy(avl_tree_t *tree); 304 305 306 307#ifdef __cplusplus 308} 309#endif 310 311#endif /* _AVL_H */ 312