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 2008 Sun Microsystems, Inc. All rights reserved. 23eda14cbcSMatt Macy * Use is subject to license terms. 24eda14cbcSMatt Macy */ 25eda14cbcSMatt Macy 26eda14cbcSMatt Macy 27eda14cbcSMatt Macy 28eda14cbcSMatt Macy #include "libuutil_common.h" 29eda14cbcSMatt Macy 30eda14cbcSMatt Macy #include <stdlib.h> 31eda14cbcSMatt Macy #include <string.h> 32eda14cbcSMatt Macy #include <unistd.h> 33eda14cbcSMatt Macy #include <sys/avl.h> 34eda14cbcSMatt Macy 35eda14cbcSMatt Macy static uu_avl_pool_t uu_null_apool = { &uu_null_apool, &uu_null_apool }; 36eda14cbcSMatt Macy static pthread_mutex_t uu_apool_list_lock = PTHREAD_MUTEX_INITIALIZER; 37eda14cbcSMatt Macy 38eda14cbcSMatt Macy /* 39eda14cbcSMatt Macy * The index mark change on every insert and delete, to catch stale 40eda14cbcSMatt Macy * references. 41eda14cbcSMatt Macy * 42eda14cbcSMatt Macy * We leave the low bit alone, since the avl code uses it. 43eda14cbcSMatt Macy */ 44eda14cbcSMatt Macy #define INDEX_MAX (sizeof (uintptr_t) - 2) 45eda14cbcSMatt Macy #define INDEX_NEXT(m) (((m) == INDEX_MAX)? 2 : ((m) + 2) & INDEX_MAX) 46eda14cbcSMatt Macy 47eda14cbcSMatt Macy #define INDEX_DECODE(i) ((i) & ~INDEX_MAX) 48eda14cbcSMatt Macy #define INDEX_ENCODE(p, n) (((n) & ~INDEX_MAX) | (p)->ua_index) 49eda14cbcSMatt Macy #define INDEX_VALID(p, i) (((i) & INDEX_MAX) == (p)->ua_index) 50eda14cbcSMatt Macy #define INDEX_CHECK(i) (((i) & INDEX_MAX) != 0) 51eda14cbcSMatt Macy 52eda14cbcSMatt Macy /* 53eda14cbcSMatt Macy * When an element is inactive (not in a tree), we keep a marked pointer to 54eda14cbcSMatt Macy * its containing pool in its first word, and a NULL pointer in its second. 55eda14cbcSMatt Macy * 56eda14cbcSMatt Macy * On insert, we use these to verify that it comes from the correct pool. 57eda14cbcSMatt Macy */ 58eda14cbcSMatt Macy #define NODE_ARRAY(p, n) ((uintptr_t *)((uintptr_t)(n) + \ 59eda14cbcSMatt Macy (pp)->uap_nodeoffset)) 60eda14cbcSMatt Macy 61eda14cbcSMatt Macy #define POOL_TO_MARKER(pp) (((uintptr_t)(pp) | 1)) 62eda14cbcSMatt Macy 63eda14cbcSMatt Macy #define DEAD_MARKER 0xc4 64eda14cbcSMatt Macy 65eda14cbcSMatt Macy uu_avl_pool_t * 66eda14cbcSMatt Macy uu_avl_pool_create(const char *name, size_t objsize, size_t nodeoffset, 67eda14cbcSMatt Macy uu_compare_fn_t *compare_func, uint32_t flags) 68eda14cbcSMatt Macy { 69eda14cbcSMatt Macy uu_avl_pool_t *pp, *next, *prev; 70eda14cbcSMatt Macy 71eda14cbcSMatt Macy if (name == NULL || 72eda14cbcSMatt Macy uu_check_name(name, UU_NAME_DOMAIN) == -1 || 73eda14cbcSMatt Macy nodeoffset + sizeof (uu_avl_node_t) > objsize || 74eda14cbcSMatt Macy compare_func == NULL) { 75eda14cbcSMatt Macy uu_set_error(UU_ERROR_INVALID_ARGUMENT); 76eda14cbcSMatt Macy return (NULL); 77eda14cbcSMatt Macy } 78eda14cbcSMatt Macy 79eda14cbcSMatt Macy if (flags & ~UU_AVL_POOL_DEBUG) { 80eda14cbcSMatt Macy uu_set_error(UU_ERROR_UNKNOWN_FLAG); 81eda14cbcSMatt Macy return (NULL); 82eda14cbcSMatt Macy } 83eda14cbcSMatt Macy 84eda14cbcSMatt Macy pp = uu_zalloc(sizeof (uu_avl_pool_t)); 85eda14cbcSMatt Macy if (pp == NULL) { 86eda14cbcSMatt Macy uu_set_error(UU_ERROR_NO_MEMORY); 87eda14cbcSMatt Macy return (NULL); 88eda14cbcSMatt Macy } 89eda14cbcSMatt Macy 90eda14cbcSMatt Macy (void) strlcpy(pp->uap_name, name, sizeof (pp->uap_name)); 91eda14cbcSMatt Macy pp->uap_nodeoffset = nodeoffset; 92eda14cbcSMatt Macy pp->uap_objsize = objsize; 93eda14cbcSMatt Macy pp->uap_cmp = compare_func; 94eda14cbcSMatt Macy if (flags & UU_AVL_POOL_DEBUG) 95eda14cbcSMatt Macy pp->uap_debug = 1; 96eda14cbcSMatt Macy pp->uap_last_index = 0; 97eda14cbcSMatt Macy 98eda14cbcSMatt Macy (void) pthread_mutex_init(&pp->uap_lock, NULL); 99eda14cbcSMatt Macy 100eda14cbcSMatt Macy pp->uap_null_avl.ua_next_enc = UU_PTR_ENCODE(&pp->uap_null_avl); 101eda14cbcSMatt Macy pp->uap_null_avl.ua_prev_enc = UU_PTR_ENCODE(&pp->uap_null_avl); 102eda14cbcSMatt Macy 103eda14cbcSMatt Macy (void) pthread_mutex_lock(&uu_apool_list_lock); 104eda14cbcSMatt Macy pp->uap_next = next = &uu_null_apool; 105eda14cbcSMatt Macy pp->uap_prev = prev = next->uap_prev; 106eda14cbcSMatt Macy next->uap_prev = pp; 107eda14cbcSMatt Macy prev->uap_next = pp; 108eda14cbcSMatt Macy (void) pthread_mutex_unlock(&uu_apool_list_lock); 109eda14cbcSMatt Macy 110eda14cbcSMatt Macy return (pp); 111eda14cbcSMatt Macy } 112eda14cbcSMatt Macy 113eda14cbcSMatt Macy void 114eda14cbcSMatt Macy uu_avl_pool_destroy(uu_avl_pool_t *pp) 115eda14cbcSMatt Macy { 116eda14cbcSMatt Macy if (pp->uap_debug) { 117eda14cbcSMatt Macy if (pp->uap_null_avl.ua_next_enc != 118eda14cbcSMatt Macy UU_PTR_ENCODE(&pp->uap_null_avl) || 119eda14cbcSMatt Macy pp->uap_null_avl.ua_prev_enc != 120eda14cbcSMatt Macy UU_PTR_ENCODE(&pp->uap_null_avl)) { 121eda14cbcSMatt Macy uu_panic("uu_avl_pool_destroy: Pool \"%.*s\" (%p) has " 122eda14cbcSMatt Macy "outstanding avls, or is corrupt.\n", 123eda14cbcSMatt Macy (int)sizeof (pp->uap_name), pp->uap_name, 124eda14cbcSMatt Macy (void *)pp); 125eda14cbcSMatt Macy } 126eda14cbcSMatt Macy } 127eda14cbcSMatt Macy (void) pthread_mutex_lock(&uu_apool_list_lock); 128eda14cbcSMatt Macy pp->uap_next->uap_prev = pp->uap_prev; 129eda14cbcSMatt Macy pp->uap_prev->uap_next = pp->uap_next; 130eda14cbcSMatt Macy (void) pthread_mutex_unlock(&uu_apool_list_lock); 131184c1b94SMartin Matuska (void) pthread_mutex_destroy(&pp->uap_lock); 132eda14cbcSMatt Macy pp->uap_prev = NULL; 133eda14cbcSMatt Macy pp->uap_next = NULL; 134eda14cbcSMatt Macy uu_free(pp); 135eda14cbcSMatt Macy } 136eda14cbcSMatt Macy 137eda14cbcSMatt Macy void 138eda14cbcSMatt Macy uu_avl_node_init(void *base, uu_avl_node_t *np, uu_avl_pool_t *pp) 139eda14cbcSMatt Macy { 140eda14cbcSMatt Macy uintptr_t *na = (uintptr_t *)np; 141eda14cbcSMatt Macy 142eda14cbcSMatt Macy if (pp->uap_debug) { 143eda14cbcSMatt Macy uintptr_t offset = (uintptr_t)np - (uintptr_t)base; 144eda14cbcSMatt Macy if (offset + sizeof (*np) > pp->uap_objsize) { 145eda14cbcSMatt Macy uu_panic("uu_avl_node_init(%p, %p, %p (\"%s\")): " 146eda14cbcSMatt Macy "offset %ld doesn't fit in object (size %ld)\n", 147eda14cbcSMatt Macy base, (void *)np, (void *)pp, pp->uap_name, 148eda14cbcSMatt Macy (long)offset, (long)pp->uap_objsize); 149eda14cbcSMatt Macy } 150eda14cbcSMatt Macy if (offset != pp->uap_nodeoffset) { 151eda14cbcSMatt Macy uu_panic("uu_avl_node_init(%p, %p, %p (\"%s\")): " 152eda14cbcSMatt Macy "offset %ld doesn't match pool's offset (%ld)\n", 153eda14cbcSMatt Macy base, (void *)np, (void *)pp, pp->uap_name, 154eda14cbcSMatt Macy (long)offset, (long)pp->uap_objsize); 155eda14cbcSMatt Macy } 156eda14cbcSMatt Macy } 157eda14cbcSMatt Macy 158eda14cbcSMatt Macy na[0] = POOL_TO_MARKER(pp); 159eda14cbcSMatt Macy na[1] = 0; 160eda14cbcSMatt Macy } 161eda14cbcSMatt Macy 162eda14cbcSMatt Macy void 163eda14cbcSMatt Macy uu_avl_node_fini(void *base, uu_avl_node_t *np, uu_avl_pool_t *pp) 164eda14cbcSMatt Macy { 165eda14cbcSMatt Macy uintptr_t *na = (uintptr_t *)np; 166eda14cbcSMatt Macy 167eda14cbcSMatt Macy if (pp->uap_debug) { 168eda14cbcSMatt Macy if (na[0] == DEAD_MARKER && na[1] == DEAD_MARKER) { 169eda14cbcSMatt Macy uu_panic("uu_avl_node_fini(%p, %p, %p (\"%s\")): " 170eda14cbcSMatt Macy "node already finied\n", 171eda14cbcSMatt Macy base, (void *)np, (void *)pp, pp->uap_name); 172eda14cbcSMatt Macy } 173eda14cbcSMatt Macy if (na[0] != POOL_TO_MARKER(pp) || na[1] != 0) { 174eda14cbcSMatt Macy uu_panic("uu_avl_node_fini(%p, %p, %p (\"%s\")): " 175eda14cbcSMatt Macy "node corrupt, in tree, or in different pool\n", 176eda14cbcSMatt Macy base, (void *)np, (void *)pp, pp->uap_name); 177eda14cbcSMatt Macy } 178eda14cbcSMatt Macy } 179eda14cbcSMatt Macy 180eda14cbcSMatt Macy na[0] = DEAD_MARKER; 181eda14cbcSMatt Macy na[1] = DEAD_MARKER; 182eda14cbcSMatt Macy na[2] = DEAD_MARKER; 183eda14cbcSMatt Macy } 184eda14cbcSMatt Macy 185eda14cbcSMatt Macy struct uu_avl_node_compare_info { 186eda14cbcSMatt Macy uu_compare_fn_t *ac_compare; 187eda14cbcSMatt Macy void *ac_private; 188eda14cbcSMatt Macy void *ac_right; 189eda14cbcSMatt Macy void *ac_found; 190eda14cbcSMatt Macy }; 191eda14cbcSMatt Macy 192eda14cbcSMatt Macy static int 193eda14cbcSMatt Macy uu_avl_node_compare(const void *l, const void *r) 194eda14cbcSMatt Macy { 195eda14cbcSMatt Macy struct uu_avl_node_compare_info *info = 196eda14cbcSMatt Macy (struct uu_avl_node_compare_info *)l; 197eda14cbcSMatt Macy 198eda14cbcSMatt Macy int res = info->ac_compare(r, info->ac_right, info->ac_private); 199eda14cbcSMatt Macy 200eda14cbcSMatt Macy if (res == 0) { 201eda14cbcSMatt Macy if (info->ac_found == NULL) 202eda14cbcSMatt Macy info->ac_found = (void *)r; 203eda14cbcSMatt Macy return (-1); 204eda14cbcSMatt Macy } 205eda14cbcSMatt Macy if (res < 0) 206eda14cbcSMatt Macy return (1); 207eda14cbcSMatt Macy return (-1); 208eda14cbcSMatt Macy } 209eda14cbcSMatt Macy 210eda14cbcSMatt Macy uu_avl_t * 211eda14cbcSMatt Macy uu_avl_create(uu_avl_pool_t *pp, void *parent, uint32_t flags) 212eda14cbcSMatt Macy { 213eda14cbcSMatt Macy uu_avl_t *ap, *next, *prev; 214eda14cbcSMatt Macy 215eda14cbcSMatt Macy if (flags & ~UU_AVL_DEBUG) { 216eda14cbcSMatt Macy uu_set_error(UU_ERROR_UNKNOWN_FLAG); 217eda14cbcSMatt Macy return (NULL); 218eda14cbcSMatt Macy } 219eda14cbcSMatt Macy 220eda14cbcSMatt Macy ap = uu_zalloc(sizeof (*ap)); 221eda14cbcSMatt Macy if (ap == NULL) { 222eda14cbcSMatt Macy uu_set_error(UU_ERROR_NO_MEMORY); 223eda14cbcSMatt Macy return (NULL); 224eda14cbcSMatt Macy } 225eda14cbcSMatt Macy 226eda14cbcSMatt Macy ap->ua_pool = pp; 227eda14cbcSMatt Macy ap->ua_parent_enc = UU_PTR_ENCODE(parent); 228eda14cbcSMatt Macy ap->ua_debug = pp->uap_debug || (flags & UU_AVL_DEBUG); 229eda14cbcSMatt Macy ap->ua_index = (pp->uap_last_index = INDEX_NEXT(pp->uap_last_index)); 230eda14cbcSMatt Macy 231eda14cbcSMatt Macy avl_create(&ap->ua_tree, &uu_avl_node_compare, pp->uap_objsize, 232eda14cbcSMatt Macy pp->uap_nodeoffset); 233eda14cbcSMatt Macy 234eda14cbcSMatt Macy ap->ua_null_walk.uaw_next = &ap->ua_null_walk; 235eda14cbcSMatt Macy ap->ua_null_walk.uaw_prev = &ap->ua_null_walk; 236eda14cbcSMatt Macy 237eda14cbcSMatt Macy (void) pthread_mutex_lock(&pp->uap_lock); 238eda14cbcSMatt Macy next = &pp->uap_null_avl; 239eda14cbcSMatt Macy prev = UU_PTR_DECODE(next->ua_prev_enc); 240eda14cbcSMatt Macy ap->ua_next_enc = UU_PTR_ENCODE(next); 241eda14cbcSMatt Macy ap->ua_prev_enc = UU_PTR_ENCODE(prev); 242eda14cbcSMatt Macy next->ua_prev_enc = UU_PTR_ENCODE(ap); 243eda14cbcSMatt Macy prev->ua_next_enc = UU_PTR_ENCODE(ap); 244eda14cbcSMatt Macy (void) pthread_mutex_unlock(&pp->uap_lock); 245eda14cbcSMatt Macy 246eda14cbcSMatt Macy return (ap); 247eda14cbcSMatt Macy } 248eda14cbcSMatt Macy 249eda14cbcSMatt Macy void 250eda14cbcSMatt Macy uu_avl_destroy(uu_avl_t *ap) 251eda14cbcSMatt Macy { 252eda14cbcSMatt Macy uu_avl_pool_t *pp = ap->ua_pool; 253eda14cbcSMatt Macy 254eda14cbcSMatt Macy if (ap->ua_debug) { 255eda14cbcSMatt Macy if (avl_numnodes(&ap->ua_tree) != 0) { 256eda14cbcSMatt Macy uu_panic("uu_avl_destroy(%p): tree not empty\n", 257eda14cbcSMatt Macy (void *)ap); 258eda14cbcSMatt Macy } 259eda14cbcSMatt Macy if (ap->ua_null_walk.uaw_next != &ap->ua_null_walk || 260eda14cbcSMatt Macy ap->ua_null_walk.uaw_prev != &ap->ua_null_walk) { 261eda14cbcSMatt Macy uu_panic("uu_avl_destroy(%p): outstanding walkers\n", 262eda14cbcSMatt Macy (void *)ap); 263eda14cbcSMatt Macy } 264eda14cbcSMatt Macy } 265eda14cbcSMatt Macy (void) pthread_mutex_lock(&pp->uap_lock); 266eda14cbcSMatt Macy UU_AVL_PTR(ap->ua_next_enc)->ua_prev_enc = ap->ua_prev_enc; 267eda14cbcSMatt Macy UU_AVL_PTR(ap->ua_prev_enc)->ua_next_enc = ap->ua_next_enc; 268eda14cbcSMatt Macy (void) pthread_mutex_unlock(&pp->uap_lock); 269eda14cbcSMatt Macy ap->ua_prev_enc = UU_PTR_ENCODE(NULL); 270eda14cbcSMatt Macy ap->ua_next_enc = UU_PTR_ENCODE(NULL); 271eda14cbcSMatt Macy 272eda14cbcSMatt Macy ap->ua_pool = NULL; 273eda14cbcSMatt Macy avl_destroy(&ap->ua_tree); 274eda14cbcSMatt Macy 275eda14cbcSMatt Macy uu_free(ap); 276eda14cbcSMatt Macy } 277eda14cbcSMatt Macy 278eda14cbcSMatt Macy size_t 279eda14cbcSMatt Macy uu_avl_numnodes(uu_avl_t *ap) 280eda14cbcSMatt Macy { 281eda14cbcSMatt Macy return (avl_numnodes(&ap->ua_tree)); 282eda14cbcSMatt Macy } 283eda14cbcSMatt Macy 284eda14cbcSMatt Macy void * 285eda14cbcSMatt Macy uu_avl_first(uu_avl_t *ap) 286eda14cbcSMatt Macy { 287eda14cbcSMatt Macy return (avl_first(&ap->ua_tree)); 288eda14cbcSMatt Macy } 289eda14cbcSMatt Macy 290eda14cbcSMatt Macy void * 291eda14cbcSMatt Macy uu_avl_last(uu_avl_t *ap) 292eda14cbcSMatt Macy { 293eda14cbcSMatt Macy return (avl_last(&ap->ua_tree)); 294eda14cbcSMatt Macy } 295eda14cbcSMatt Macy 296eda14cbcSMatt Macy void * 297eda14cbcSMatt Macy uu_avl_next(uu_avl_t *ap, void *node) 298eda14cbcSMatt Macy { 299eda14cbcSMatt Macy return (AVL_NEXT(&ap->ua_tree, node)); 300eda14cbcSMatt Macy } 301eda14cbcSMatt Macy 302eda14cbcSMatt Macy void * 303eda14cbcSMatt Macy uu_avl_prev(uu_avl_t *ap, void *node) 304eda14cbcSMatt Macy { 305eda14cbcSMatt Macy return (AVL_PREV(&ap->ua_tree, node)); 306eda14cbcSMatt Macy } 307eda14cbcSMatt Macy 308eda14cbcSMatt Macy static void 309eda14cbcSMatt Macy _avl_walk_init(uu_avl_walk_t *wp, uu_avl_t *ap, uint32_t flags) 310eda14cbcSMatt Macy { 311eda14cbcSMatt Macy uu_avl_walk_t *next, *prev; 312eda14cbcSMatt Macy 313eda14cbcSMatt Macy int robust = (flags & UU_WALK_ROBUST); 314eda14cbcSMatt Macy int direction = (flags & UU_WALK_REVERSE)? -1 : 1; 315eda14cbcSMatt Macy 316eda14cbcSMatt Macy (void) memset(wp, 0, sizeof (*wp)); 317eda14cbcSMatt Macy wp->uaw_avl = ap; 318eda14cbcSMatt Macy wp->uaw_robust = robust; 319eda14cbcSMatt Macy wp->uaw_dir = direction; 320eda14cbcSMatt Macy 321eda14cbcSMatt Macy if (direction > 0) 322eda14cbcSMatt Macy wp->uaw_next_result = avl_first(&ap->ua_tree); 323eda14cbcSMatt Macy else 324eda14cbcSMatt Macy wp->uaw_next_result = avl_last(&ap->ua_tree); 325eda14cbcSMatt Macy 326eda14cbcSMatt Macy if (ap->ua_debug || robust) { 327eda14cbcSMatt Macy wp->uaw_next = next = &ap->ua_null_walk; 328eda14cbcSMatt Macy wp->uaw_prev = prev = next->uaw_prev; 329eda14cbcSMatt Macy next->uaw_prev = wp; 330eda14cbcSMatt Macy prev->uaw_next = wp; 331eda14cbcSMatt Macy } 332eda14cbcSMatt Macy } 333eda14cbcSMatt Macy 334eda14cbcSMatt Macy static void * 335eda14cbcSMatt Macy _avl_walk_advance(uu_avl_walk_t *wp, uu_avl_t *ap) 336eda14cbcSMatt Macy { 337eda14cbcSMatt Macy void *np = wp->uaw_next_result; 338eda14cbcSMatt Macy 339eda14cbcSMatt Macy avl_tree_t *t = &ap->ua_tree; 340eda14cbcSMatt Macy 341eda14cbcSMatt Macy if (np == NULL) 342eda14cbcSMatt Macy return (NULL); 343eda14cbcSMatt Macy 344eda14cbcSMatt Macy wp->uaw_next_result = (wp->uaw_dir > 0)? AVL_NEXT(t, np) : 345eda14cbcSMatt Macy AVL_PREV(t, np); 346eda14cbcSMatt Macy 347eda14cbcSMatt Macy return (np); 348eda14cbcSMatt Macy } 349eda14cbcSMatt Macy 350eda14cbcSMatt Macy static void 351eda14cbcSMatt Macy _avl_walk_fini(uu_avl_walk_t *wp) 352eda14cbcSMatt Macy { 353eda14cbcSMatt Macy if (wp->uaw_next != NULL) { 354eda14cbcSMatt Macy wp->uaw_next->uaw_prev = wp->uaw_prev; 355eda14cbcSMatt Macy wp->uaw_prev->uaw_next = wp->uaw_next; 356eda14cbcSMatt Macy wp->uaw_next = NULL; 357eda14cbcSMatt Macy wp->uaw_prev = NULL; 358eda14cbcSMatt Macy } 359eda14cbcSMatt Macy wp->uaw_avl = NULL; 360eda14cbcSMatt Macy wp->uaw_next_result = NULL; 361eda14cbcSMatt Macy } 362eda14cbcSMatt Macy 363eda14cbcSMatt Macy uu_avl_walk_t * 364eda14cbcSMatt Macy uu_avl_walk_start(uu_avl_t *ap, uint32_t flags) 365eda14cbcSMatt Macy { 366eda14cbcSMatt Macy uu_avl_walk_t *wp; 367eda14cbcSMatt Macy 368eda14cbcSMatt Macy if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) { 369eda14cbcSMatt Macy uu_set_error(UU_ERROR_UNKNOWN_FLAG); 370eda14cbcSMatt Macy return (NULL); 371eda14cbcSMatt Macy } 372eda14cbcSMatt Macy 373eda14cbcSMatt Macy wp = uu_zalloc(sizeof (*wp)); 374eda14cbcSMatt Macy if (wp == NULL) { 375eda14cbcSMatt Macy uu_set_error(UU_ERROR_NO_MEMORY); 376eda14cbcSMatt Macy return (NULL); 377eda14cbcSMatt Macy } 378eda14cbcSMatt Macy 379eda14cbcSMatt Macy _avl_walk_init(wp, ap, flags); 380eda14cbcSMatt Macy return (wp); 381eda14cbcSMatt Macy } 382eda14cbcSMatt Macy 383eda14cbcSMatt Macy void * 384eda14cbcSMatt Macy uu_avl_walk_next(uu_avl_walk_t *wp) 385eda14cbcSMatt Macy { 386eda14cbcSMatt Macy return (_avl_walk_advance(wp, wp->uaw_avl)); 387eda14cbcSMatt Macy } 388eda14cbcSMatt Macy 389eda14cbcSMatt Macy void 390eda14cbcSMatt Macy uu_avl_walk_end(uu_avl_walk_t *wp) 391eda14cbcSMatt Macy { 392eda14cbcSMatt Macy _avl_walk_fini(wp); 393eda14cbcSMatt Macy uu_free(wp); 394eda14cbcSMatt Macy } 395eda14cbcSMatt Macy 396eda14cbcSMatt Macy int 397eda14cbcSMatt Macy uu_avl_walk(uu_avl_t *ap, uu_walk_fn_t *func, void *private, uint32_t flags) 398eda14cbcSMatt Macy { 399eda14cbcSMatt Macy void *e; 400eda14cbcSMatt Macy uu_avl_walk_t my_walk; 401eda14cbcSMatt Macy 402eda14cbcSMatt Macy int status = UU_WALK_NEXT; 403eda14cbcSMatt Macy 404eda14cbcSMatt Macy if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) { 405eda14cbcSMatt Macy uu_set_error(UU_ERROR_UNKNOWN_FLAG); 406eda14cbcSMatt Macy return (-1); 407eda14cbcSMatt Macy } 408eda14cbcSMatt Macy 409eda14cbcSMatt Macy _avl_walk_init(&my_walk, ap, flags); 410eda14cbcSMatt Macy while (status == UU_WALK_NEXT && 411eda14cbcSMatt Macy (e = _avl_walk_advance(&my_walk, ap)) != NULL) 412eda14cbcSMatt Macy status = (*func)(e, private); 413eda14cbcSMatt Macy _avl_walk_fini(&my_walk); 414eda14cbcSMatt Macy 415eda14cbcSMatt Macy if (status >= 0) 416eda14cbcSMatt Macy return (0); 417eda14cbcSMatt Macy uu_set_error(UU_ERROR_CALLBACK_FAILED); 418eda14cbcSMatt Macy return (-1); 419eda14cbcSMatt Macy } 420eda14cbcSMatt Macy 421eda14cbcSMatt Macy void 422eda14cbcSMatt Macy uu_avl_remove(uu_avl_t *ap, void *elem) 423eda14cbcSMatt Macy { 424eda14cbcSMatt Macy uu_avl_walk_t *wp; 425eda14cbcSMatt Macy uu_avl_pool_t *pp = ap->ua_pool; 426eda14cbcSMatt Macy uintptr_t *na = NODE_ARRAY(pp, elem); 427eda14cbcSMatt Macy 428eda14cbcSMatt Macy if (ap->ua_debug) { 429eda14cbcSMatt Macy /* 430eda14cbcSMatt Macy * invalidate outstanding uu_avl_index_ts. 431eda14cbcSMatt Macy */ 432eda14cbcSMatt Macy ap->ua_index = INDEX_NEXT(ap->ua_index); 433eda14cbcSMatt Macy } 434eda14cbcSMatt Macy 435eda14cbcSMatt Macy /* 436eda14cbcSMatt Macy * Robust walkers most be advanced, if we are removing the node 437eda14cbcSMatt Macy * they are currently using. In debug mode, non-robust walkers 438eda14cbcSMatt Macy * are also on the walker list. 439eda14cbcSMatt Macy */ 440eda14cbcSMatt Macy for (wp = ap->ua_null_walk.uaw_next; wp != &ap->ua_null_walk; 441eda14cbcSMatt Macy wp = wp->uaw_next) { 442eda14cbcSMatt Macy if (wp->uaw_robust) { 443eda14cbcSMatt Macy if (elem == wp->uaw_next_result) 444eda14cbcSMatt Macy (void) _avl_walk_advance(wp, ap); 445eda14cbcSMatt Macy } else if (wp->uaw_next_result != NULL) { 446eda14cbcSMatt Macy uu_panic("uu_avl_remove(%p, %p): active non-robust " 447eda14cbcSMatt Macy "walker\n", (void *)ap, elem); 448eda14cbcSMatt Macy } 449eda14cbcSMatt Macy } 450eda14cbcSMatt Macy 451eda14cbcSMatt Macy avl_remove(&ap->ua_tree, elem); 452eda14cbcSMatt Macy 453eda14cbcSMatt Macy na[0] = POOL_TO_MARKER(pp); 454eda14cbcSMatt Macy na[1] = 0; 455eda14cbcSMatt Macy } 456eda14cbcSMatt Macy 457eda14cbcSMatt Macy void * 458eda14cbcSMatt Macy uu_avl_teardown(uu_avl_t *ap, void **cookie) 459eda14cbcSMatt Macy { 460eda14cbcSMatt Macy void *elem = avl_destroy_nodes(&ap->ua_tree, cookie); 461eda14cbcSMatt Macy 462eda14cbcSMatt Macy if (elem != NULL) { 463eda14cbcSMatt Macy uu_avl_pool_t *pp = ap->ua_pool; 464eda14cbcSMatt Macy uintptr_t *na = NODE_ARRAY(pp, elem); 465eda14cbcSMatt Macy 466eda14cbcSMatt Macy na[0] = POOL_TO_MARKER(pp); 467eda14cbcSMatt Macy na[1] = 0; 468eda14cbcSMatt Macy } 469eda14cbcSMatt Macy return (elem); 470eda14cbcSMatt Macy } 471eda14cbcSMatt Macy 472eda14cbcSMatt Macy void * 473eda14cbcSMatt Macy uu_avl_find(uu_avl_t *ap, void *elem, void *private, uu_avl_index_t *out) 474eda14cbcSMatt Macy { 475eda14cbcSMatt Macy struct uu_avl_node_compare_info info; 476eda14cbcSMatt Macy void *result; 477eda14cbcSMatt Macy 478eda14cbcSMatt Macy info.ac_compare = ap->ua_pool->uap_cmp; 479eda14cbcSMatt Macy info.ac_private = private; 480eda14cbcSMatt Macy info.ac_right = elem; 481eda14cbcSMatt Macy info.ac_found = NULL; 482eda14cbcSMatt Macy 483eda14cbcSMatt Macy result = avl_find(&ap->ua_tree, &info, out); 484eda14cbcSMatt Macy if (out != NULL) 485eda14cbcSMatt Macy *out = INDEX_ENCODE(ap, *out); 486eda14cbcSMatt Macy 487eda14cbcSMatt Macy if (ap->ua_debug && result != NULL) 488eda14cbcSMatt Macy uu_panic("uu_avl_find: internal error: avl_find succeeded\n"); 489eda14cbcSMatt Macy 490eda14cbcSMatt Macy return (info.ac_found); 491eda14cbcSMatt Macy } 492eda14cbcSMatt Macy 493eda14cbcSMatt Macy void 494eda14cbcSMatt Macy uu_avl_insert(uu_avl_t *ap, void *elem, uu_avl_index_t idx) 495eda14cbcSMatt Macy { 496eda14cbcSMatt Macy if (ap->ua_debug) { 497eda14cbcSMatt Macy uu_avl_pool_t *pp = ap->ua_pool; 498eda14cbcSMatt Macy uintptr_t *na = NODE_ARRAY(pp, elem); 499eda14cbcSMatt Macy 500eda14cbcSMatt Macy if (na[1] != 0) 501eda14cbcSMatt Macy uu_panic("uu_avl_insert(%p, %p, %p): node already " 502eda14cbcSMatt Macy "in tree, or corrupt\n", 503eda14cbcSMatt Macy (void *)ap, elem, (void *)idx); 504eda14cbcSMatt Macy if (na[0] == 0) 505eda14cbcSMatt Macy uu_panic("uu_avl_insert(%p, %p, %p): node not " 506eda14cbcSMatt Macy "initialized\n", 507eda14cbcSMatt Macy (void *)ap, elem, (void *)idx); 508eda14cbcSMatt Macy if (na[0] != POOL_TO_MARKER(pp)) 509eda14cbcSMatt Macy uu_panic("uu_avl_insert(%p, %p, %p): node from " 510eda14cbcSMatt Macy "other pool, or corrupt\n", 511eda14cbcSMatt Macy (void *)ap, elem, (void *)idx); 512eda14cbcSMatt Macy 513eda14cbcSMatt Macy if (!INDEX_VALID(ap, idx)) 514eda14cbcSMatt Macy uu_panic("uu_avl_insert(%p, %p, %p): %s\n", 515eda14cbcSMatt Macy (void *)ap, elem, (void *)idx, 516eda14cbcSMatt Macy INDEX_CHECK(idx)? "outdated index" : 517eda14cbcSMatt Macy "invalid index"); 518eda14cbcSMatt Macy 519eda14cbcSMatt Macy /* 520eda14cbcSMatt Macy * invalidate outstanding uu_avl_index_ts. 521eda14cbcSMatt Macy */ 522eda14cbcSMatt Macy ap->ua_index = INDEX_NEXT(ap->ua_index); 523eda14cbcSMatt Macy } 524eda14cbcSMatt Macy avl_insert(&ap->ua_tree, elem, INDEX_DECODE(idx)); 525eda14cbcSMatt Macy } 526eda14cbcSMatt Macy 527eda14cbcSMatt Macy void * 528eda14cbcSMatt Macy uu_avl_nearest_next(uu_avl_t *ap, uu_avl_index_t idx) 529eda14cbcSMatt Macy { 530eda14cbcSMatt Macy if (ap->ua_debug && !INDEX_VALID(ap, idx)) 531eda14cbcSMatt Macy uu_panic("uu_avl_nearest_next(%p, %p): %s\n", 532eda14cbcSMatt Macy (void *)ap, (void *)idx, INDEX_CHECK(idx)? 533eda14cbcSMatt Macy "outdated index" : "invalid index"); 534eda14cbcSMatt Macy return (avl_nearest(&ap->ua_tree, INDEX_DECODE(idx), AVL_AFTER)); 535eda14cbcSMatt Macy } 536eda14cbcSMatt Macy 537eda14cbcSMatt Macy void * 538eda14cbcSMatt Macy uu_avl_nearest_prev(uu_avl_t *ap, uu_avl_index_t idx) 539eda14cbcSMatt Macy { 540eda14cbcSMatt Macy if (ap->ua_debug && !INDEX_VALID(ap, idx)) 541eda14cbcSMatt Macy uu_panic("uu_avl_nearest_prev(%p, %p): %s\n", 542eda14cbcSMatt Macy (void *)ap, (void *)idx, INDEX_CHECK(idx)? 543eda14cbcSMatt Macy "outdated index" : "invalid index"); 544eda14cbcSMatt Macy return (avl_nearest(&ap->ua_tree, INDEX_DECODE(idx), AVL_BEFORE)); 545eda14cbcSMatt Macy } 546eda14cbcSMatt Macy 547eda14cbcSMatt Macy /* 548eda14cbcSMatt Macy * called from uu_lockup() and uu_release(), as part of our fork1()-safety. 549eda14cbcSMatt Macy */ 550eda14cbcSMatt Macy void 551eda14cbcSMatt Macy uu_avl_lockup(void) 552eda14cbcSMatt Macy { 553eda14cbcSMatt Macy uu_avl_pool_t *pp; 554eda14cbcSMatt Macy 555eda14cbcSMatt Macy (void) pthread_mutex_lock(&uu_apool_list_lock); 556eda14cbcSMatt Macy for (pp = uu_null_apool.uap_next; pp != &uu_null_apool; 557eda14cbcSMatt Macy pp = pp->uap_next) 558eda14cbcSMatt Macy (void) pthread_mutex_lock(&pp->uap_lock); 559eda14cbcSMatt Macy } 560eda14cbcSMatt Macy 561eda14cbcSMatt Macy void 562eda14cbcSMatt Macy uu_avl_release(void) 563eda14cbcSMatt Macy { 564eda14cbcSMatt Macy uu_avl_pool_t *pp; 565eda14cbcSMatt Macy 566eda14cbcSMatt Macy for (pp = uu_null_apool.uap_next; pp != &uu_null_apool; 567eda14cbcSMatt Macy pp = pp->uap_next) 568eda14cbcSMatt Macy (void) pthread_mutex_unlock(&pp->uap_lock); 569eda14cbcSMatt Macy (void) pthread_mutex_unlock(&uu_apool_list_lock); 570eda14cbcSMatt Macy } 571