1168404Spjd/* 2168404Spjd * CDDL HEADER START 3168404Spjd * 4168404Spjd * The contents of this file are subject to the terms of the 5168404Spjd * Common Development and Distribution License (the "License"). 6168404Spjd * You may not use this file except in compliance with the License. 7168404Spjd * 8168404Spjd * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9168404Spjd * or http://www.opensolaris.org/os/licensing. 10168404Spjd * See the License for the specific language governing permissions 11168404Spjd * and limitations under the License. 12168404Spjd * 13168404Spjd * When distributing Covered Code, include this CDDL HEADER in each 14168404Spjd * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15168404Spjd * If applicable, add the following below this CDDL HEADER, with the 16168404Spjd * fields enclosed by brackets "[]" replaced with your own identifying 17168404Spjd * information: Portions Copyright [yyyy] [name of copyright owner] 18168404Spjd * 19168404Spjd * CDDL HEADER END 20168404Spjd */ 21168404Spjd/* 22185029Spjd * Copyright 2008 Sun Microsystems, Inc. All rights reserved. 23168404Spjd * Use is subject to license terms. 24168404Spjd */ 25168404Spjd 26168404Spjd#pragma ident "%Z%%M% %I% %E% SMI" 27168404Spjd 28168404Spjd#include "libuutil_common.h" 29168404Spjd 30168404Spjd#include <stdlib.h> 31168404Spjd#include <string.h> 32168404Spjd#include <unistd.h> 33168404Spjd#include <sys/avl.h> 34168404Spjd 35168404Spjdstatic uu_avl_pool_t uu_null_apool = { &uu_null_apool, &uu_null_apool }; 36168404Spjdstatic pthread_mutex_t uu_apool_list_lock = PTHREAD_MUTEX_INITIALIZER; 37168404Spjd 38168404Spjd/* 39168404Spjd * The index mark change on every insert and delete, to catch stale 40168404Spjd * references. 41168404Spjd * 42168404Spjd * We leave the low bit alone, since the avl code uses it. 43168404Spjd */ 44168404Spjd#define INDEX_MAX (sizeof (uintptr_t) - 2) 45168404Spjd#define INDEX_NEXT(m) (((m) == INDEX_MAX)? 2 : ((m) + 2) & INDEX_MAX) 46168404Spjd 47168404Spjd#define INDEX_DECODE(i) ((i) & ~INDEX_MAX) 48168404Spjd#define INDEX_ENCODE(p, n) (((n) & ~INDEX_MAX) | (p)->ua_index) 49168404Spjd#define INDEX_VALID(p, i) (((i) & INDEX_MAX) == (p)->ua_index) 50168404Spjd#define INDEX_CHECK(i) (((i) & INDEX_MAX) != 0) 51168404Spjd 52168404Spjd/* 53168404Spjd * When an element is inactive (not in a tree), we keep a marked pointer to 54168404Spjd * its containing pool in its first word, and a NULL pointer in its second. 55168404Spjd * 56168404Spjd * On insert, we use these to verify that it comes from the correct pool. 57168404Spjd */ 58168404Spjd#define NODE_ARRAY(p, n) ((uintptr_t *)((uintptr_t)(n) + \ 59168404Spjd (pp)->uap_nodeoffset)) 60168404Spjd 61168404Spjd#define POOL_TO_MARKER(pp) (((uintptr_t)(pp) | 1)) 62168404Spjd 63168404Spjd#define DEAD_MARKER 0xc4 64168404Spjd 65168404Spjduu_avl_pool_t * 66168404Spjduu_avl_pool_create(const char *name, size_t objsize, size_t nodeoffset, 67168404Spjd uu_compare_fn_t *compare_func, uint32_t flags) 68168404Spjd{ 69168404Spjd uu_avl_pool_t *pp, *next, *prev; 70168404Spjd 71168404Spjd if (name == NULL || 72168404Spjd uu_check_name(name, UU_NAME_DOMAIN) == -1 || 73168404Spjd nodeoffset + sizeof (uu_avl_node_t) > objsize || 74168404Spjd compare_func == NULL) { 75168404Spjd uu_set_error(UU_ERROR_INVALID_ARGUMENT); 76168404Spjd return (NULL); 77168404Spjd } 78168404Spjd 79168404Spjd if (flags & ~UU_AVL_POOL_DEBUG) { 80168404Spjd uu_set_error(UU_ERROR_UNKNOWN_FLAG); 81168404Spjd return (NULL); 82168404Spjd } 83168404Spjd 84168404Spjd pp = uu_zalloc(sizeof (uu_avl_pool_t)); 85168404Spjd if (pp == NULL) { 86168404Spjd uu_set_error(UU_ERROR_NO_MEMORY); 87168404Spjd return (NULL); 88168404Spjd } 89168404Spjd 90168404Spjd (void) strlcpy(pp->uap_name, name, sizeof (pp->uap_name)); 91168404Spjd pp->uap_nodeoffset = nodeoffset; 92168404Spjd pp->uap_objsize = objsize; 93168404Spjd pp->uap_cmp = compare_func; 94168404Spjd if (flags & UU_AVL_POOL_DEBUG) 95168404Spjd pp->uap_debug = 1; 96168404Spjd pp->uap_last_index = 0; 97168404Spjd 98168404Spjd (void) pthread_mutex_init(&pp->uap_lock, NULL); 99168404Spjd 100168404Spjd pp->uap_null_avl.ua_next_enc = UU_PTR_ENCODE(&pp->uap_null_avl); 101168404Spjd pp->uap_null_avl.ua_prev_enc = UU_PTR_ENCODE(&pp->uap_null_avl); 102168404Spjd 103168404Spjd (void) pthread_mutex_lock(&uu_apool_list_lock); 104168404Spjd pp->uap_next = next = &uu_null_apool; 105168404Spjd pp->uap_prev = prev = next->uap_prev; 106168404Spjd next->uap_prev = pp; 107168404Spjd prev->uap_next = pp; 108168404Spjd (void) pthread_mutex_unlock(&uu_apool_list_lock); 109168404Spjd 110168404Spjd return (pp); 111168404Spjd} 112168404Spjd 113168404Spjdvoid 114168404Spjduu_avl_pool_destroy(uu_avl_pool_t *pp) 115168404Spjd{ 116168404Spjd if (pp->uap_debug) { 117168404Spjd if (pp->uap_null_avl.ua_next_enc != 118168404Spjd UU_PTR_ENCODE(&pp->uap_null_avl) || 119168404Spjd pp->uap_null_avl.ua_prev_enc != 120168404Spjd UU_PTR_ENCODE(&pp->uap_null_avl)) { 121168404Spjd uu_panic("uu_avl_pool_destroy: Pool \"%.*s\" (%p) has " 122168404Spjd "outstanding avls, or is corrupt.\n", 123185029Spjd (int)sizeof (pp->uap_name), pp->uap_name, 124185029Spjd (void *)pp); 125168404Spjd } 126168404Spjd } 127168404Spjd (void) pthread_mutex_lock(&uu_apool_list_lock); 128168404Spjd pp->uap_next->uap_prev = pp->uap_prev; 129168404Spjd pp->uap_prev->uap_next = pp->uap_next; 130168404Spjd (void) pthread_mutex_unlock(&uu_apool_list_lock); 131262912Sasomers (void) pthread_mutex_destroy(&pp->uap_lock); 132168404Spjd pp->uap_prev = NULL; 133168404Spjd pp->uap_next = NULL; 134168404Spjd uu_free(pp); 135168404Spjd} 136168404Spjd 137168404Spjdvoid 138168404Spjduu_avl_node_init(void *base, uu_avl_node_t *np, uu_avl_pool_t *pp) 139168404Spjd{ 140168404Spjd uintptr_t *na = (uintptr_t *)np; 141168404Spjd 142168404Spjd if (pp->uap_debug) { 143168404Spjd uintptr_t offset = (uintptr_t)np - (uintptr_t)base; 144168404Spjd if (offset + sizeof (*np) > pp->uap_objsize) { 145168404Spjd uu_panic("uu_avl_node_init(%p, %p, %p (\"%s\")): " 146168404Spjd "offset %ld doesn't fit in object (size %ld)\n", 147185029Spjd base, (void *)np, (void *)pp, pp->uap_name, 148185029Spjd (long)offset, (long)pp->uap_objsize); 149168404Spjd } 150168404Spjd if (offset != pp->uap_nodeoffset) { 151168404Spjd uu_panic("uu_avl_node_init(%p, %p, %p (\"%s\")): " 152168404Spjd "offset %ld doesn't match pool's offset (%ld)\n", 153185029Spjd base, (void *)np, (void *)pp, pp->uap_name, 154185029Spjd (long)offset, (long)pp->uap_objsize); 155168404Spjd } 156168404Spjd } 157168404Spjd 158168404Spjd na[0] = POOL_TO_MARKER(pp); 159168404Spjd na[1] = 0; 160168404Spjd} 161168404Spjd 162168404Spjdvoid 163168404Spjduu_avl_node_fini(void *base, uu_avl_node_t *np, uu_avl_pool_t *pp) 164168404Spjd{ 165168404Spjd uintptr_t *na = (uintptr_t *)np; 166168404Spjd 167168404Spjd if (pp->uap_debug) { 168168404Spjd if (na[0] == DEAD_MARKER && na[1] == DEAD_MARKER) { 169168404Spjd uu_panic("uu_avl_node_fini(%p, %p, %p (\"%s\")): " 170168404Spjd "node already finied\n", 171185029Spjd base, (void *)np, (void *)pp, pp->uap_name); 172168404Spjd } 173168404Spjd if (na[0] != POOL_TO_MARKER(pp) || na[1] != 0) { 174168404Spjd uu_panic("uu_avl_node_fini(%p, %p, %p (\"%s\")): " 175168404Spjd "node corrupt, in tree, or in different pool\n", 176185029Spjd base, (void *)np, (void *)pp, pp->uap_name); 177168404Spjd } 178168404Spjd } 179168404Spjd 180168404Spjd na[0] = DEAD_MARKER; 181168404Spjd na[1] = DEAD_MARKER; 182168404Spjd na[2] = DEAD_MARKER; 183168404Spjd} 184168404Spjd 185168404Spjdstruct uu_avl_node_compare_info { 186168404Spjd uu_compare_fn_t *ac_compare; 187168404Spjd void *ac_private; 188168404Spjd void *ac_right; 189168404Spjd void *ac_found; 190168404Spjd}; 191168404Spjd 192168404Spjdstatic int 193168404Spjduu_avl_node_compare(const void *l, const void *r) 194168404Spjd{ 195168404Spjd struct uu_avl_node_compare_info *info = 196168404Spjd (struct uu_avl_node_compare_info *)l; 197168404Spjd 198168404Spjd int res = info->ac_compare(r, info->ac_right, info->ac_private); 199168404Spjd 200168404Spjd if (res == 0) { 201168404Spjd if (info->ac_found == NULL) 202168404Spjd info->ac_found = (void *)r; 203168404Spjd return (-1); 204168404Spjd } 205168404Spjd if (res < 0) 206168404Spjd return (1); 207168404Spjd return (-1); 208168404Spjd} 209168404Spjd 210168404Spjduu_avl_t * 211168404Spjduu_avl_create(uu_avl_pool_t *pp, void *parent, uint32_t flags) 212168404Spjd{ 213168404Spjd uu_avl_t *ap, *next, *prev; 214168404Spjd 215168404Spjd if (flags & ~UU_AVL_DEBUG) { 216168404Spjd uu_set_error(UU_ERROR_UNKNOWN_FLAG); 217168404Spjd return (NULL); 218168404Spjd } 219168404Spjd 220168404Spjd ap = uu_zalloc(sizeof (*ap)); 221168404Spjd if (ap == NULL) { 222168404Spjd uu_set_error(UU_ERROR_NO_MEMORY); 223168404Spjd return (NULL); 224168404Spjd } 225168404Spjd 226168404Spjd ap->ua_pool = pp; 227168404Spjd ap->ua_parent_enc = UU_PTR_ENCODE(parent); 228168404Spjd ap->ua_debug = pp->uap_debug || (flags & UU_AVL_DEBUG); 229168404Spjd ap->ua_index = (pp->uap_last_index = INDEX_NEXT(pp->uap_last_index)); 230168404Spjd 231168404Spjd avl_create(&ap->ua_tree, &uu_avl_node_compare, pp->uap_objsize, 232168404Spjd pp->uap_nodeoffset); 233168404Spjd 234168404Spjd ap->ua_null_walk.uaw_next = &ap->ua_null_walk; 235168404Spjd ap->ua_null_walk.uaw_prev = &ap->ua_null_walk; 236168404Spjd 237168404Spjd (void) pthread_mutex_lock(&pp->uap_lock); 238168404Spjd next = &pp->uap_null_avl; 239168404Spjd prev = UU_PTR_DECODE(next->ua_prev_enc); 240168404Spjd ap->ua_next_enc = UU_PTR_ENCODE(next); 241168404Spjd ap->ua_prev_enc = UU_PTR_ENCODE(prev); 242168404Spjd next->ua_prev_enc = UU_PTR_ENCODE(ap); 243168404Spjd prev->ua_next_enc = UU_PTR_ENCODE(ap); 244168404Spjd (void) pthread_mutex_unlock(&pp->uap_lock); 245168404Spjd 246168404Spjd return (ap); 247168404Spjd} 248168404Spjd 249168404Spjdvoid 250168404Spjduu_avl_destroy(uu_avl_t *ap) 251168404Spjd{ 252168404Spjd uu_avl_pool_t *pp = ap->ua_pool; 253168404Spjd 254168404Spjd if (ap->ua_debug) { 255168404Spjd if (avl_numnodes(&ap->ua_tree) != 0) { 256185029Spjd uu_panic("uu_avl_destroy(%p): tree not empty\n", 257185029Spjd (void *)ap); 258168404Spjd } 259168404Spjd if (ap->ua_null_walk.uaw_next != &ap->ua_null_walk || 260168404Spjd ap->ua_null_walk.uaw_prev != &ap->ua_null_walk) { 261168404Spjd uu_panic("uu_avl_destroy(%p): outstanding walkers\n", 262185029Spjd (void *)ap); 263168404Spjd } 264168404Spjd } 265168404Spjd (void) pthread_mutex_lock(&pp->uap_lock); 266168404Spjd UU_AVL_PTR(ap->ua_next_enc)->ua_prev_enc = ap->ua_prev_enc; 267168404Spjd UU_AVL_PTR(ap->ua_prev_enc)->ua_next_enc = ap->ua_next_enc; 268168404Spjd (void) pthread_mutex_unlock(&pp->uap_lock); 269168404Spjd ap->ua_prev_enc = UU_PTR_ENCODE(NULL); 270168404Spjd ap->ua_next_enc = UU_PTR_ENCODE(NULL); 271168404Spjd 272168404Spjd ap->ua_pool = NULL; 273168404Spjd avl_destroy(&ap->ua_tree); 274168404Spjd 275168404Spjd uu_free(ap); 276168404Spjd} 277168404Spjd 278168404Spjdsize_t 279168404Spjduu_avl_numnodes(uu_avl_t *ap) 280168404Spjd{ 281168404Spjd return (avl_numnodes(&ap->ua_tree)); 282168404Spjd} 283168404Spjd 284168404Spjdvoid * 285168404Spjduu_avl_first(uu_avl_t *ap) 286168404Spjd{ 287168404Spjd return (avl_first(&ap->ua_tree)); 288168404Spjd} 289168404Spjd 290168404Spjdvoid * 291168404Spjduu_avl_last(uu_avl_t *ap) 292168404Spjd{ 293168404Spjd return (avl_last(&ap->ua_tree)); 294168404Spjd} 295168404Spjd 296168404Spjdvoid * 297168404Spjduu_avl_next(uu_avl_t *ap, void *node) 298168404Spjd{ 299168404Spjd return (AVL_NEXT(&ap->ua_tree, node)); 300168404Spjd} 301168404Spjd 302168404Spjdvoid * 303168404Spjduu_avl_prev(uu_avl_t *ap, void *node) 304168404Spjd{ 305168404Spjd return (AVL_PREV(&ap->ua_tree, node)); 306168404Spjd} 307168404Spjd 308168404Spjdstatic void 309168404Spjd_avl_walk_init(uu_avl_walk_t *wp, uu_avl_t *ap, uint32_t flags) 310168404Spjd{ 311168404Spjd uu_avl_walk_t *next, *prev; 312168404Spjd 313168404Spjd int robust = (flags & UU_WALK_ROBUST); 314168404Spjd int direction = (flags & UU_WALK_REVERSE)? -1 : 1; 315168404Spjd 316168404Spjd (void) memset(wp, 0, sizeof (*wp)); 317168404Spjd wp->uaw_avl = ap; 318168404Spjd wp->uaw_robust = robust; 319168404Spjd wp->uaw_dir = direction; 320168404Spjd 321168404Spjd if (direction > 0) 322168404Spjd wp->uaw_next_result = avl_first(&ap->ua_tree); 323168404Spjd else 324168404Spjd wp->uaw_next_result = avl_last(&ap->ua_tree); 325168404Spjd 326168404Spjd if (ap->ua_debug || robust) { 327168404Spjd wp->uaw_next = next = &ap->ua_null_walk; 328168404Spjd wp->uaw_prev = prev = next->uaw_prev; 329168404Spjd next->uaw_prev = wp; 330168404Spjd prev->uaw_next = wp; 331168404Spjd } 332168404Spjd} 333168404Spjd 334168404Spjdstatic void * 335168404Spjd_avl_walk_advance(uu_avl_walk_t *wp, uu_avl_t *ap) 336168404Spjd{ 337168404Spjd void *np = wp->uaw_next_result; 338168404Spjd 339168404Spjd avl_tree_t *t = &ap->ua_tree; 340168404Spjd 341168404Spjd if (np == NULL) 342168404Spjd return (NULL); 343168404Spjd 344168404Spjd wp->uaw_next_result = (wp->uaw_dir > 0)? AVL_NEXT(t, np) : 345168404Spjd AVL_PREV(t, np); 346168404Spjd 347168404Spjd return (np); 348168404Spjd} 349168404Spjd 350168404Spjdstatic void 351168404Spjd_avl_walk_fini(uu_avl_walk_t *wp) 352168404Spjd{ 353168404Spjd if (wp->uaw_next != NULL) { 354168404Spjd wp->uaw_next->uaw_prev = wp->uaw_prev; 355168404Spjd wp->uaw_prev->uaw_next = wp->uaw_next; 356168404Spjd wp->uaw_next = NULL; 357168404Spjd wp->uaw_prev = NULL; 358168404Spjd } 359168404Spjd wp->uaw_avl = NULL; 360168404Spjd wp->uaw_next_result = NULL; 361168404Spjd} 362168404Spjd 363168404Spjduu_avl_walk_t * 364168404Spjduu_avl_walk_start(uu_avl_t *ap, uint32_t flags) 365168404Spjd{ 366168404Spjd uu_avl_walk_t *wp; 367168404Spjd 368168404Spjd if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) { 369168404Spjd uu_set_error(UU_ERROR_UNKNOWN_FLAG); 370168404Spjd return (NULL); 371168404Spjd } 372168404Spjd 373168404Spjd wp = uu_zalloc(sizeof (*wp)); 374168404Spjd if (wp == NULL) { 375168404Spjd uu_set_error(UU_ERROR_NO_MEMORY); 376168404Spjd return (NULL); 377168404Spjd } 378168404Spjd 379168404Spjd _avl_walk_init(wp, ap, flags); 380168404Spjd return (wp); 381168404Spjd} 382168404Spjd 383168404Spjdvoid * 384168404Spjduu_avl_walk_next(uu_avl_walk_t *wp) 385168404Spjd{ 386168404Spjd return (_avl_walk_advance(wp, wp->uaw_avl)); 387168404Spjd} 388168404Spjd 389168404Spjdvoid 390168404Spjduu_avl_walk_end(uu_avl_walk_t *wp) 391168404Spjd{ 392168404Spjd _avl_walk_fini(wp); 393168404Spjd uu_free(wp); 394168404Spjd} 395168404Spjd 396168404Spjdint 397168404Spjduu_avl_walk(uu_avl_t *ap, uu_walk_fn_t *func, void *private, uint32_t flags) 398168404Spjd{ 399168404Spjd void *e; 400168404Spjd uu_avl_walk_t my_walk; 401168404Spjd 402168404Spjd int status = UU_WALK_NEXT; 403168404Spjd 404168404Spjd if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) { 405168404Spjd uu_set_error(UU_ERROR_UNKNOWN_FLAG); 406168404Spjd return (-1); 407168404Spjd } 408168404Spjd 409168404Spjd _avl_walk_init(&my_walk, ap, flags); 410168404Spjd while (status == UU_WALK_NEXT && 411168404Spjd (e = _avl_walk_advance(&my_walk, ap)) != NULL) 412168404Spjd status = (*func)(e, private); 413168404Spjd _avl_walk_fini(&my_walk); 414168404Spjd 415168404Spjd if (status >= 0) 416168404Spjd return (0); 417168404Spjd uu_set_error(UU_ERROR_CALLBACK_FAILED); 418168404Spjd return (-1); 419168404Spjd} 420168404Spjd 421168404Spjdvoid 422168404Spjduu_avl_remove(uu_avl_t *ap, void *elem) 423168404Spjd{ 424168404Spjd uu_avl_walk_t *wp; 425168404Spjd uu_avl_pool_t *pp = ap->ua_pool; 426168404Spjd uintptr_t *na = NODE_ARRAY(pp, elem); 427168404Spjd 428168404Spjd if (ap->ua_debug) { 429168404Spjd /* 430168404Spjd * invalidate outstanding uu_avl_index_ts. 431168404Spjd */ 432168404Spjd ap->ua_index = INDEX_NEXT(ap->ua_index); 433168404Spjd } 434168404Spjd 435168404Spjd /* 436168404Spjd * Robust walkers most be advanced, if we are removing the node 437168404Spjd * they are currently using. In debug mode, non-robust walkers 438168404Spjd * are also on the walker list. 439168404Spjd */ 440168404Spjd for (wp = ap->ua_null_walk.uaw_next; wp != &ap->ua_null_walk; 441168404Spjd wp = wp->uaw_next) { 442168404Spjd if (wp->uaw_robust) { 443168404Spjd if (elem == wp->uaw_next_result) 444168404Spjd (void) _avl_walk_advance(wp, ap); 445168404Spjd } else if (wp->uaw_next_result != NULL) { 446168404Spjd uu_panic("uu_avl_remove(%p, %p): active non-robust " 447185029Spjd "walker\n", (void *)ap, elem); 448168404Spjd } 449168404Spjd } 450168404Spjd 451168404Spjd avl_remove(&ap->ua_tree, elem); 452168404Spjd 453168404Spjd na[0] = POOL_TO_MARKER(pp); 454168404Spjd na[1] = 0; 455168404Spjd} 456168404Spjd 457168404Spjdvoid * 458168404Spjduu_avl_teardown(uu_avl_t *ap, void **cookie) 459168404Spjd{ 460168404Spjd void *elem = avl_destroy_nodes(&ap->ua_tree, cookie); 461168404Spjd 462168404Spjd if (elem != NULL) { 463168404Spjd uu_avl_pool_t *pp = ap->ua_pool; 464168404Spjd uintptr_t *na = NODE_ARRAY(pp, elem); 465168404Spjd 466168404Spjd na[0] = POOL_TO_MARKER(pp); 467168404Spjd na[1] = 0; 468168404Spjd } 469168404Spjd return (elem); 470168404Spjd} 471168404Spjd 472168404Spjdvoid * 473168404Spjduu_avl_find(uu_avl_t *ap, void *elem, void *private, uu_avl_index_t *out) 474168404Spjd{ 475168404Spjd struct uu_avl_node_compare_info info; 476168404Spjd void *result; 477168404Spjd 478168404Spjd info.ac_compare = ap->ua_pool->uap_cmp; 479168404Spjd info.ac_private = private; 480168404Spjd info.ac_right = elem; 481168404Spjd info.ac_found = NULL; 482168404Spjd 483168404Spjd result = avl_find(&ap->ua_tree, &info, out); 484168404Spjd if (out != NULL) 485168404Spjd *out = INDEX_ENCODE(ap, *out); 486168404Spjd 487168404Spjd if (ap->ua_debug && result != NULL) 488168404Spjd uu_panic("uu_avl_find: internal error: avl_find succeeded\n"); 489168404Spjd 490168404Spjd return (info.ac_found); 491168404Spjd} 492168404Spjd 493168404Spjdvoid 494168404Spjduu_avl_insert(uu_avl_t *ap, void *elem, uu_avl_index_t idx) 495168404Spjd{ 496168404Spjd if (ap->ua_debug) { 497168404Spjd uu_avl_pool_t *pp = ap->ua_pool; 498168404Spjd uintptr_t *na = NODE_ARRAY(pp, elem); 499168404Spjd 500168404Spjd if (na[1] != 0) 501168404Spjd uu_panic("uu_avl_insert(%p, %p, %p): node already " 502168404Spjd "in tree, or corrupt\n", 503185029Spjd (void *)ap, elem, (void *)idx); 504168404Spjd if (na[0] == 0) 505168404Spjd uu_panic("uu_avl_insert(%p, %p, %p): node not " 506168404Spjd "initialized\n", 507185029Spjd (void *)ap, elem, (void *)idx); 508168404Spjd if (na[0] != POOL_TO_MARKER(pp)) 509168404Spjd uu_panic("uu_avl_insert(%p, %p, %p): node from " 510168404Spjd "other pool, or corrupt\n", 511185029Spjd (void *)ap, elem, (void *)idx); 512168404Spjd 513168404Spjd if (!INDEX_VALID(ap, idx)) 514168404Spjd uu_panic("uu_avl_insert(%p, %p, %p): %s\n", 515185029Spjd (void *)ap, elem, (void *)idx, 516168404Spjd INDEX_CHECK(idx)? "outdated index" : 517168404Spjd "invalid index"); 518168404Spjd 519168404Spjd /* 520168404Spjd * invalidate outstanding uu_avl_index_ts. 521168404Spjd */ 522168404Spjd ap->ua_index = INDEX_NEXT(ap->ua_index); 523168404Spjd } 524168404Spjd avl_insert(&ap->ua_tree, elem, INDEX_DECODE(idx)); 525168404Spjd} 526168404Spjd 527168404Spjdvoid * 528168404Spjduu_avl_nearest_next(uu_avl_t *ap, uu_avl_index_t idx) 529168404Spjd{ 530168404Spjd if (ap->ua_debug && !INDEX_VALID(ap, idx)) 531168404Spjd uu_panic("uu_avl_nearest_next(%p, %p): %s\n", 532185029Spjd (void *)ap, (void *)idx, INDEX_CHECK(idx)? 533185029Spjd "outdated index" : "invalid index"); 534168404Spjd return (avl_nearest(&ap->ua_tree, INDEX_DECODE(idx), AVL_AFTER)); 535168404Spjd} 536168404Spjd 537168404Spjdvoid * 538168404Spjduu_avl_nearest_prev(uu_avl_t *ap, uu_avl_index_t idx) 539168404Spjd{ 540168404Spjd if (ap->ua_debug && !INDEX_VALID(ap, idx)) 541168404Spjd uu_panic("uu_avl_nearest_prev(%p, %p): %s\n", 542185029Spjd (void *)ap, (void *)idx, INDEX_CHECK(idx)? 543185029Spjd "outdated index" : "invalid index"); 544168404Spjd return (avl_nearest(&ap->ua_tree, INDEX_DECODE(idx), AVL_BEFORE)); 545168404Spjd} 546168404Spjd 547168404Spjd/* 548168404Spjd * called from uu_lockup() and uu_release(), as part of our fork1()-safety. 549168404Spjd */ 550168404Spjdvoid 551168404Spjduu_avl_lockup(void) 552168404Spjd{ 553168404Spjd uu_avl_pool_t *pp; 554168404Spjd 555168404Spjd (void) pthread_mutex_lock(&uu_apool_list_lock); 556168404Spjd for (pp = uu_null_apool.uap_next; pp != &uu_null_apool; 557168404Spjd pp = pp->uap_next) 558168404Spjd (void) pthread_mutex_lock(&pp->uap_lock); 559168404Spjd} 560168404Spjd 561168404Spjdvoid 562168404Spjduu_avl_release(void) 563168404Spjd{ 564168404Spjd uu_avl_pool_t *pp; 565168404Spjd 566168404Spjd for (pp = uu_null_apool.uap_next; pp != &uu_null_apool; 567168404Spjd pp = pp->uap_next) 568168404Spjd (void) pthread_mutex_unlock(&pp->uap_lock); 569168404Spjd (void) pthread_mutex_unlock(&uu_apool_list_lock); 570168404Spjd} 571