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