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