10Sstevel@tonic-gate /*
20Sstevel@tonic-gate * CDDL HEADER START
30Sstevel@tonic-gate *
40Sstevel@tonic-gate * The contents of this file are subject to the terms of the
52856Snd150628 * Common Development and Distribution License (the "License").
62856Snd150628 * You may not use this file except in compliance with the License.
70Sstevel@tonic-gate *
80Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
90Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
100Sstevel@tonic-gate * See the License for the specific language governing permissions
110Sstevel@tonic-gate * and limitations under the License.
120Sstevel@tonic-gate *
130Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
140Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
150Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
160Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
170Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
180Sstevel@tonic-gate *
190Sstevel@tonic-gate * CDDL HEADER END
200Sstevel@tonic-gate */
210Sstevel@tonic-gate /*
22*7240Srh87107 * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
230Sstevel@tonic-gate * Use is subject to license terms.
240Sstevel@tonic-gate */
250Sstevel@tonic-gate
260Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI"
270Sstevel@tonic-gate
280Sstevel@tonic-gate #include "libuutil_common.h"
290Sstevel@tonic-gate
300Sstevel@tonic-gate #include <stdlib.h>
310Sstevel@tonic-gate #include <string.h>
320Sstevel@tonic-gate #include <unistd.h>
330Sstevel@tonic-gate #include <sys/avl.h>
340Sstevel@tonic-gate
350Sstevel@tonic-gate static uu_avl_pool_t uu_null_apool = { &uu_null_apool, &uu_null_apool };
360Sstevel@tonic-gate static pthread_mutex_t uu_apool_list_lock = PTHREAD_MUTEX_INITIALIZER;
370Sstevel@tonic-gate
380Sstevel@tonic-gate /*
390Sstevel@tonic-gate * The index mark change on every insert and delete, to catch stale
400Sstevel@tonic-gate * references.
410Sstevel@tonic-gate *
420Sstevel@tonic-gate * We leave the low bit alone, since the avl code uses it.
430Sstevel@tonic-gate */
440Sstevel@tonic-gate #define INDEX_MAX (sizeof (uintptr_t) - 2)
450Sstevel@tonic-gate #define INDEX_NEXT(m) (((m) == INDEX_MAX)? 2 : ((m) + 2) & INDEX_MAX)
460Sstevel@tonic-gate
470Sstevel@tonic-gate #define INDEX_DECODE(i) ((i) & ~INDEX_MAX)
480Sstevel@tonic-gate #define INDEX_ENCODE(p, n) (((n) & ~INDEX_MAX) | (p)->ua_index)
490Sstevel@tonic-gate #define INDEX_VALID(p, i) (((i) & INDEX_MAX) == (p)->ua_index)
500Sstevel@tonic-gate #define INDEX_CHECK(i) (((i) & INDEX_MAX) != 0)
510Sstevel@tonic-gate
520Sstevel@tonic-gate /*
530Sstevel@tonic-gate * When an element is inactive (not in a tree), we keep a marked pointer to
540Sstevel@tonic-gate * its containing pool in its first word, and a NULL pointer in its second.
550Sstevel@tonic-gate *
560Sstevel@tonic-gate * On insert, we use these to verify that it comes from the correct pool.
570Sstevel@tonic-gate */
580Sstevel@tonic-gate #define NODE_ARRAY(p, n) ((uintptr_t *)((uintptr_t)(n) + \
590Sstevel@tonic-gate (pp)->uap_nodeoffset))
600Sstevel@tonic-gate
610Sstevel@tonic-gate #define POOL_TO_MARKER(pp) (((uintptr_t)(pp) | 1))
620Sstevel@tonic-gate
630Sstevel@tonic-gate #define DEAD_MARKER 0xc4
640Sstevel@tonic-gate
650Sstevel@tonic-gate uu_avl_pool_t *
uu_avl_pool_create(const char * name,size_t objsize,size_t nodeoffset,uu_compare_fn_t * compare_func,uint32_t flags)660Sstevel@tonic-gate uu_avl_pool_create(const char *name, size_t objsize, size_t nodeoffset,
670Sstevel@tonic-gate uu_compare_fn_t *compare_func, uint32_t flags)
680Sstevel@tonic-gate {
690Sstevel@tonic-gate uu_avl_pool_t *pp, *next, *prev;
700Sstevel@tonic-gate
710Sstevel@tonic-gate if (name == NULL ||
720Sstevel@tonic-gate uu_check_name(name, UU_NAME_DOMAIN) == -1 ||
730Sstevel@tonic-gate nodeoffset + sizeof (uu_avl_node_t) > objsize ||
740Sstevel@tonic-gate compare_func == NULL) {
750Sstevel@tonic-gate uu_set_error(UU_ERROR_INVALID_ARGUMENT);
760Sstevel@tonic-gate return (NULL);
770Sstevel@tonic-gate }
780Sstevel@tonic-gate
790Sstevel@tonic-gate if (flags & ~UU_AVL_POOL_DEBUG) {
800Sstevel@tonic-gate uu_set_error(UU_ERROR_UNKNOWN_FLAG);
810Sstevel@tonic-gate return (NULL);
820Sstevel@tonic-gate }
830Sstevel@tonic-gate
840Sstevel@tonic-gate pp = uu_zalloc(sizeof (uu_avl_pool_t));
850Sstevel@tonic-gate if (pp == NULL) {
860Sstevel@tonic-gate uu_set_error(UU_ERROR_NO_MEMORY);
870Sstevel@tonic-gate return (NULL);
880Sstevel@tonic-gate }
890Sstevel@tonic-gate
900Sstevel@tonic-gate (void) strlcpy(pp->uap_name, name, sizeof (pp->uap_name));
910Sstevel@tonic-gate pp->uap_nodeoffset = nodeoffset;
920Sstevel@tonic-gate pp->uap_objsize = objsize;
930Sstevel@tonic-gate pp->uap_cmp = compare_func;
940Sstevel@tonic-gate if (flags & UU_AVL_POOL_DEBUG)
950Sstevel@tonic-gate pp->uap_debug = 1;
960Sstevel@tonic-gate pp->uap_last_index = 0;
970Sstevel@tonic-gate
980Sstevel@tonic-gate (void) pthread_mutex_init(&pp->uap_lock, NULL);
990Sstevel@tonic-gate
100407Sjwadams pp->uap_null_avl.ua_next_enc = UU_PTR_ENCODE(&pp->uap_null_avl);
101407Sjwadams pp->uap_null_avl.ua_prev_enc = UU_PTR_ENCODE(&pp->uap_null_avl);
1020Sstevel@tonic-gate
1030Sstevel@tonic-gate (void) pthread_mutex_lock(&uu_apool_list_lock);
1040Sstevel@tonic-gate pp->uap_next = next = &uu_null_apool;
1050Sstevel@tonic-gate pp->uap_prev = prev = next->uap_prev;
1060Sstevel@tonic-gate next->uap_prev = pp;
1070Sstevel@tonic-gate prev->uap_next = pp;
1080Sstevel@tonic-gate (void) pthread_mutex_unlock(&uu_apool_list_lock);
1090Sstevel@tonic-gate
1100Sstevel@tonic-gate return (pp);
1110Sstevel@tonic-gate }
1120Sstevel@tonic-gate
1130Sstevel@tonic-gate void
uu_avl_pool_destroy(uu_avl_pool_t * pp)1140Sstevel@tonic-gate uu_avl_pool_destroy(uu_avl_pool_t *pp)
1150Sstevel@tonic-gate {
1160Sstevel@tonic-gate if (pp->uap_debug) {
117407Sjwadams if (pp->uap_null_avl.ua_next_enc !=
118407Sjwadams UU_PTR_ENCODE(&pp->uap_null_avl) ||
119407Sjwadams pp->uap_null_avl.ua_prev_enc !=
120407Sjwadams UU_PTR_ENCODE(&pp->uap_null_avl)) {
1210Sstevel@tonic-gate uu_panic("uu_avl_pool_destroy: Pool \"%.*s\" (%p) has "
1220Sstevel@tonic-gate "outstanding avls, or is corrupt.\n",
123*7240Srh87107 (int)sizeof (pp->uap_name), pp->uap_name,
124*7240Srh87107 (void *)pp);
1250Sstevel@tonic-gate }
1260Sstevel@tonic-gate }
1270Sstevel@tonic-gate (void) pthread_mutex_lock(&uu_apool_list_lock);
1280Sstevel@tonic-gate pp->uap_next->uap_prev = pp->uap_prev;
1290Sstevel@tonic-gate pp->uap_prev->uap_next = pp->uap_next;
1300Sstevel@tonic-gate (void) pthread_mutex_unlock(&uu_apool_list_lock);
1310Sstevel@tonic-gate pp->uap_prev = NULL;
1320Sstevel@tonic-gate pp->uap_next = NULL;
1330Sstevel@tonic-gate uu_free(pp);
1340Sstevel@tonic-gate }
1350Sstevel@tonic-gate
1360Sstevel@tonic-gate void
uu_avl_node_init(void * base,uu_avl_node_t * np,uu_avl_pool_t * pp)1370Sstevel@tonic-gate uu_avl_node_init(void *base, uu_avl_node_t *np, uu_avl_pool_t *pp)
1380Sstevel@tonic-gate {
1390Sstevel@tonic-gate uintptr_t *na = (uintptr_t *)np;
1400Sstevel@tonic-gate
1410Sstevel@tonic-gate if (pp->uap_debug) {
1420Sstevel@tonic-gate uintptr_t offset = (uintptr_t)np - (uintptr_t)base;
1430Sstevel@tonic-gate if (offset + sizeof (*np) > pp->uap_objsize) {
1440Sstevel@tonic-gate uu_panic("uu_avl_node_init(%p, %p, %p (\"%s\")): "
1450Sstevel@tonic-gate "offset %ld doesn't fit in object (size %ld)\n",
146*7240Srh87107 base, (void *)np, (void *)pp, pp->uap_name,
147*7240Srh87107 (long)offset, (long)pp->uap_objsize);
1480Sstevel@tonic-gate }
1490Sstevel@tonic-gate if (offset != pp->uap_nodeoffset) {
1500Sstevel@tonic-gate uu_panic("uu_avl_node_init(%p, %p, %p (\"%s\")): "
1510Sstevel@tonic-gate "offset %ld doesn't match pool's offset (%ld)\n",
152*7240Srh87107 base, (void *)np, (void *)pp, pp->uap_name,
153*7240Srh87107 (long)offset, (long)pp->uap_objsize);
1540Sstevel@tonic-gate }
1550Sstevel@tonic-gate }
1560Sstevel@tonic-gate
1570Sstevel@tonic-gate na[0] = POOL_TO_MARKER(pp);
1582856Snd150628 na[1] = 0;
1590Sstevel@tonic-gate }
1600Sstevel@tonic-gate
1610Sstevel@tonic-gate void
uu_avl_node_fini(void * base,uu_avl_node_t * np,uu_avl_pool_t * pp)1620Sstevel@tonic-gate uu_avl_node_fini(void *base, uu_avl_node_t *np, uu_avl_pool_t *pp)
1630Sstevel@tonic-gate {
1640Sstevel@tonic-gate uintptr_t *na = (uintptr_t *)np;
1650Sstevel@tonic-gate
1660Sstevel@tonic-gate if (pp->uap_debug) {
1670Sstevel@tonic-gate if (na[0] == DEAD_MARKER && na[1] == DEAD_MARKER) {
1680Sstevel@tonic-gate uu_panic("uu_avl_node_fini(%p, %p, %p (\"%s\")): "
1690Sstevel@tonic-gate "node already finied\n",
170*7240Srh87107 base, (void *)np, (void *)pp, pp->uap_name);
1710Sstevel@tonic-gate }
1722856Snd150628 if (na[0] != POOL_TO_MARKER(pp) || na[1] != 0) {
1730Sstevel@tonic-gate uu_panic("uu_avl_node_fini(%p, %p, %p (\"%s\")): "
1740Sstevel@tonic-gate "node corrupt, in tree, or in different pool\n",
175*7240Srh87107 base, (void *)np, (void *)pp, pp->uap_name);
1760Sstevel@tonic-gate }
1770Sstevel@tonic-gate }
1780Sstevel@tonic-gate
1790Sstevel@tonic-gate na[0] = DEAD_MARKER;
1800Sstevel@tonic-gate na[1] = DEAD_MARKER;
1810Sstevel@tonic-gate na[2] = DEAD_MARKER;
1820Sstevel@tonic-gate }
1830Sstevel@tonic-gate
1840Sstevel@tonic-gate struct uu_avl_node_compare_info {
1850Sstevel@tonic-gate uu_compare_fn_t *ac_compare;
1860Sstevel@tonic-gate void *ac_private;
1870Sstevel@tonic-gate void *ac_right;
1880Sstevel@tonic-gate void *ac_found;
1890Sstevel@tonic-gate };
1900Sstevel@tonic-gate
1910Sstevel@tonic-gate static int
uu_avl_node_compare(const void * l,const void * r)1920Sstevel@tonic-gate uu_avl_node_compare(const void *l, const void *r)
1930Sstevel@tonic-gate {
1940Sstevel@tonic-gate struct uu_avl_node_compare_info *info =
1950Sstevel@tonic-gate (struct uu_avl_node_compare_info *)l;
1960Sstevel@tonic-gate
1970Sstevel@tonic-gate int res = info->ac_compare(r, info->ac_right, info->ac_private);
1980Sstevel@tonic-gate
1990Sstevel@tonic-gate if (res == 0) {
2000Sstevel@tonic-gate if (info->ac_found == NULL)
2010Sstevel@tonic-gate info->ac_found = (void *)r;
2020Sstevel@tonic-gate return (-1);
2030Sstevel@tonic-gate }
2040Sstevel@tonic-gate if (res < 0)
2050Sstevel@tonic-gate return (1);
2060Sstevel@tonic-gate return (-1);
2070Sstevel@tonic-gate }
2080Sstevel@tonic-gate
2090Sstevel@tonic-gate uu_avl_t *
uu_avl_create(uu_avl_pool_t * pp,void * parent,uint32_t flags)2100Sstevel@tonic-gate uu_avl_create(uu_avl_pool_t *pp, void *parent, uint32_t flags)
2110Sstevel@tonic-gate {
2120Sstevel@tonic-gate uu_avl_t *ap, *next, *prev;
2130Sstevel@tonic-gate
214407Sjwadams if (flags & ~UU_AVL_DEBUG) {
2150Sstevel@tonic-gate uu_set_error(UU_ERROR_UNKNOWN_FLAG);
2160Sstevel@tonic-gate return (NULL);
2170Sstevel@tonic-gate }
2180Sstevel@tonic-gate
2190Sstevel@tonic-gate ap = uu_zalloc(sizeof (*ap));
2200Sstevel@tonic-gate if (ap == NULL) {
2210Sstevel@tonic-gate uu_set_error(UU_ERROR_NO_MEMORY);
2220Sstevel@tonic-gate return (NULL);
2230Sstevel@tonic-gate }
2240Sstevel@tonic-gate
2250Sstevel@tonic-gate ap->ua_pool = pp;
226407Sjwadams ap->ua_parent_enc = UU_PTR_ENCODE(parent);
2270Sstevel@tonic-gate ap->ua_debug = pp->uap_debug || (flags & UU_AVL_DEBUG);
2280Sstevel@tonic-gate ap->ua_index = (pp->uap_last_index = INDEX_NEXT(pp->uap_last_index));
2290Sstevel@tonic-gate
2300Sstevel@tonic-gate avl_create(&ap->ua_tree, &uu_avl_node_compare, pp->uap_objsize,
2310Sstevel@tonic-gate pp->uap_nodeoffset);
2320Sstevel@tonic-gate
2330Sstevel@tonic-gate ap->ua_null_walk.uaw_next = &ap->ua_null_walk;
2340Sstevel@tonic-gate ap->ua_null_walk.uaw_prev = &ap->ua_null_walk;
2350Sstevel@tonic-gate
2360Sstevel@tonic-gate (void) pthread_mutex_lock(&pp->uap_lock);
237407Sjwadams next = &pp->uap_null_avl;
238407Sjwadams prev = UU_PTR_DECODE(next->ua_prev_enc);
239407Sjwadams ap->ua_next_enc = UU_PTR_ENCODE(next);
240407Sjwadams ap->ua_prev_enc = UU_PTR_ENCODE(prev);
241407Sjwadams next->ua_prev_enc = UU_PTR_ENCODE(ap);
242407Sjwadams prev->ua_next_enc = UU_PTR_ENCODE(ap);
2430Sstevel@tonic-gate (void) pthread_mutex_unlock(&pp->uap_lock);
2440Sstevel@tonic-gate
2450Sstevel@tonic-gate return (ap);
2460Sstevel@tonic-gate }
2470Sstevel@tonic-gate
2480Sstevel@tonic-gate void
uu_avl_destroy(uu_avl_t * ap)2490Sstevel@tonic-gate uu_avl_destroy(uu_avl_t *ap)
2500Sstevel@tonic-gate {
2510Sstevel@tonic-gate uu_avl_pool_t *pp = ap->ua_pool;
2520Sstevel@tonic-gate
2530Sstevel@tonic-gate if (ap->ua_debug) {
2540Sstevel@tonic-gate if (avl_numnodes(&ap->ua_tree) != 0) {
255*7240Srh87107 uu_panic("uu_avl_destroy(%p): tree not empty\n",
256*7240Srh87107 (void *)ap);
2570Sstevel@tonic-gate }
2580Sstevel@tonic-gate if (ap->ua_null_walk.uaw_next != &ap->ua_null_walk ||
2590Sstevel@tonic-gate ap->ua_null_walk.uaw_prev != &ap->ua_null_walk) {
2600Sstevel@tonic-gate uu_panic("uu_avl_destroy(%p): outstanding walkers\n",
261*7240Srh87107 (void *)ap);
2620Sstevel@tonic-gate }
2630Sstevel@tonic-gate }
2640Sstevel@tonic-gate (void) pthread_mutex_lock(&pp->uap_lock);
265407Sjwadams UU_AVL_PTR(ap->ua_next_enc)->ua_prev_enc = ap->ua_prev_enc;
266407Sjwadams UU_AVL_PTR(ap->ua_prev_enc)->ua_next_enc = ap->ua_next_enc;
2670Sstevel@tonic-gate (void) pthread_mutex_unlock(&pp->uap_lock);
268407Sjwadams ap->ua_prev_enc = UU_PTR_ENCODE(NULL);
269407Sjwadams ap->ua_next_enc = UU_PTR_ENCODE(NULL);
2700Sstevel@tonic-gate
2710Sstevel@tonic-gate ap->ua_pool = NULL;
2720Sstevel@tonic-gate avl_destroy(&ap->ua_tree);
2730Sstevel@tonic-gate
2740Sstevel@tonic-gate uu_free(ap);
2750Sstevel@tonic-gate }
2760Sstevel@tonic-gate
2770Sstevel@tonic-gate size_t
uu_avl_numnodes(uu_avl_t * ap)2780Sstevel@tonic-gate uu_avl_numnodes(uu_avl_t *ap)
2790Sstevel@tonic-gate {
2800Sstevel@tonic-gate return (avl_numnodes(&ap->ua_tree));
2810Sstevel@tonic-gate }
2820Sstevel@tonic-gate
2830Sstevel@tonic-gate void *
uu_avl_first(uu_avl_t * ap)2840Sstevel@tonic-gate uu_avl_first(uu_avl_t *ap)
2850Sstevel@tonic-gate {
2860Sstevel@tonic-gate return (avl_first(&ap->ua_tree));
2870Sstevel@tonic-gate }
2880Sstevel@tonic-gate
2890Sstevel@tonic-gate void *
uu_avl_last(uu_avl_t * ap)2900Sstevel@tonic-gate uu_avl_last(uu_avl_t *ap)
2910Sstevel@tonic-gate {
2920Sstevel@tonic-gate return (avl_last(&ap->ua_tree));
2930Sstevel@tonic-gate }
2940Sstevel@tonic-gate
2950Sstevel@tonic-gate void *
uu_avl_next(uu_avl_t * ap,void * node)2960Sstevel@tonic-gate uu_avl_next(uu_avl_t *ap, void *node)
2970Sstevel@tonic-gate {
2980Sstevel@tonic-gate return (AVL_NEXT(&ap->ua_tree, node));
2990Sstevel@tonic-gate }
3000Sstevel@tonic-gate
3010Sstevel@tonic-gate void *
uu_avl_prev(uu_avl_t * ap,void * node)3020Sstevel@tonic-gate uu_avl_prev(uu_avl_t *ap, void *node)
3030Sstevel@tonic-gate {
3040Sstevel@tonic-gate return (AVL_PREV(&ap->ua_tree, node));
3050Sstevel@tonic-gate }
3060Sstevel@tonic-gate
3070Sstevel@tonic-gate static void
_avl_walk_init(uu_avl_walk_t * wp,uu_avl_t * ap,uint32_t flags)3080Sstevel@tonic-gate _avl_walk_init(uu_avl_walk_t *wp, uu_avl_t *ap, uint32_t flags)
3090Sstevel@tonic-gate {
3100Sstevel@tonic-gate uu_avl_walk_t *next, *prev;
3110Sstevel@tonic-gate
3120Sstevel@tonic-gate int robust = (flags & UU_WALK_ROBUST);
3130Sstevel@tonic-gate int direction = (flags & UU_WALK_REVERSE)? -1 : 1;
3140Sstevel@tonic-gate
3150Sstevel@tonic-gate (void) memset(wp, 0, sizeof (*wp));
3160Sstevel@tonic-gate wp->uaw_avl = ap;
3170Sstevel@tonic-gate wp->uaw_robust = robust;
3180Sstevel@tonic-gate wp->uaw_dir = direction;
3190Sstevel@tonic-gate
3200Sstevel@tonic-gate if (direction > 0)
3210Sstevel@tonic-gate wp->uaw_next_result = avl_first(&ap->ua_tree);
3220Sstevel@tonic-gate else
3230Sstevel@tonic-gate wp->uaw_next_result = avl_last(&ap->ua_tree);
3240Sstevel@tonic-gate
3250Sstevel@tonic-gate if (ap->ua_debug || robust) {
3260Sstevel@tonic-gate wp->uaw_next = next = &ap->ua_null_walk;
3270Sstevel@tonic-gate wp->uaw_prev = prev = next->uaw_prev;
3280Sstevel@tonic-gate next->uaw_prev = wp;
3290Sstevel@tonic-gate prev->uaw_next = wp;
3300Sstevel@tonic-gate }
3310Sstevel@tonic-gate }
3320Sstevel@tonic-gate
3330Sstevel@tonic-gate static void *
_avl_walk_advance(uu_avl_walk_t * wp,uu_avl_t * ap)3340Sstevel@tonic-gate _avl_walk_advance(uu_avl_walk_t *wp, uu_avl_t *ap)
3350Sstevel@tonic-gate {
3360Sstevel@tonic-gate void *np = wp->uaw_next_result;
3370Sstevel@tonic-gate
3380Sstevel@tonic-gate avl_tree_t *t = &ap->ua_tree;
3390Sstevel@tonic-gate
3400Sstevel@tonic-gate if (np == NULL)
3410Sstevel@tonic-gate return (NULL);
3420Sstevel@tonic-gate
3430Sstevel@tonic-gate wp->uaw_next_result = (wp->uaw_dir > 0)? AVL_NEXT(t, np) :
3440Sstevel@tonic-gate AVL_PREV(t, np);
3450Sstevel@tonic-gate
3460Sstevel@tonic-gate return (np);
3470Sstevel@tonic-gate }
3480Sstevel@tonic-gate
3490Sstevel@tonic-gate static void
_avl_walk_fini(uu_avl_walk_t * wp)3500Sstevel@tonic-gate _avl_walk_fini(uu_avl_walk_t *wp)
3510Sstevel@tonic-gate {
3520Sstevel@tonic-gate if (wp->uaw_next != NULL) {
3530Sstevel@tonic-gate wp->uaw_next->uaw_prev = wp->uaw_prev;
3540Sstevel@tonic-gate wp->uaw_prev->uaw_next = wp->uaw_next;
3550Sstevel@tonic-gate wp->uaw_next = NULL;
3560Sstevel@tonic-gate wp->uaw_prev = NULL;
3570Sstevel@tonic-gate }
3580Sstevel@tonic-gate wp->uaw_avl = NULL;
3590Sstevel@tonic-gate wp->uaw_next_result = NULL;
3600Sstevel@tonic-gate }
3610Sstevel@tonic-gate
3620Sstevel@tonic-gate uu_avl_walk_t *
uu_avl_walk_start(uu_avl_t * ap,uint32_t flags)3630Sstevel@tonic-gate uu_avl_walk_start(uu_avl_t *ap, uint32_t flags)
3640Sstevel@tonic-gate {
3650Sstevel@tonic-gate uu_avl_walk_t *wp;
3660Sstevel@tonic-gate
3670Sstevel@tonic-gate if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) {
3680Sstevel@tonic-gate uu_set_error(UU_ERROR_UNKNOWN_FLAG);
3690Sstevel@tonic-gate return (NULL);
3700Sstevel@tonic-gate }
3710Sstevel@tonic-gate
3720Sstevel@tonic-gate wp = uu_zalloc(sizeof (*wp));
3730Sstevel@tonic-gate if (wp == NULL) {
3740Sstevel@tonic-gate uu_set_error(UU_ERROR_NO_MEMORY);
3750Sstevel@tonic-gate return (NULL);
3760Sstevel@tonic-gate }
3770Sstevel@tonic-gate
3780Sstevel@tonic-gate _avl_walk_init(wp, ap, flags);
3790Sstevel@tonic-gate return (wp);
3800Sstevel@tonic-gate }
3810Sstevel@tonic-gate
3820Sstevel@tonic-gate void *
uu_avl_walk_next(uu_avl_walk_t * wp)3830Sstevel@tonic-gate uu_avl_walk_next(uu_avl_walk_t *wp)
3840Sstevel@tonic-gate {
3850Sstevel@tonic-gate return (_avl_walk_advance(wp, wp->uaw_avl));
3860Sstevel@tonic-gate }
3870Sstevel@tonic-gate
3880Sstevel@tonic-gate void
uu_avl_walk_end(uu_avl_walk_t * wp)3890Sstevel@tonic-gate uu_avl_walk_end(uu_avl_walk_t *wp)
3900Sstevel@tonic-gate {
3910Sstevel@tonic-gate _avl_walk_fini(wp);
3920Sstevel@tonic-gate uu_free(wp);
3930Sstevel@tonic-gate }
3940Sstevel@tonic-gate
3950Sstevel@tonic-gate int
uu_avl_walk(uu_avl_t * ap,uu_walk_fn_t * func,void * private,uint32_t flags)3960Sstevel@tonic-gate uu_avl_walk(uu_avl_t *ap, uu_walk_fn_t *func, void *private, uint32_t flags)
3970Sstevel@tonic-gate {
3980Sstevel@tonic-gate void *e;
3990Sstevel@tonic-gate uu_avl_walk_t my_walk;
4000Sstevel@tonic-gate
4010Sstevel@tonic-gate int status = UU_WALK_NEXT;
4020Sstevel@tonic-gate
4030Sstevel@tonic-gate if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) {
4040Sstevel@tonic-gate uu_set_error(UU_ERROR_UNKNOWN_FLAG);
4050Sstevel@tonic-gate return (-1);
4060Sstevel@tonic-gate }
4070Sstevel@tonic-gate
4080Sstevel@tonic-gate _avl_walk_init(&my_walk, ap, flags);
4090Sstevel@tonic-gate while (status == UU_WALK_NEXT &&
4100Sstevel@tonic-gate (e = _avl_walk_advance(&my_walk, ap)) != NULL)
4110Sstevel@tonic-gate status = (*func)(e, private);
4120Sstevel@tonic-gate _avl_walk_fini(&my_walk);
4130Sstevel@tonic-gate
4140Sstevel@tonic-gate if (status >= 0)
4150Sstevel@tonic-gate return (0);
4160Sstevel@tonic-gate uu_set_error(UU_ERROR_CALLBACK_FAILED);
4170Sstevel@tonic-gate return (-1);
4180Sstevel@tonic-gate }
4190Sstevel@tonic-gate
4200Sstevel@tonic-gate void
uu_avl_remove(uu_avl_t * ap,void * elem)4210Sstevel@tonic-gate uu_avl_remove(uu_avl_t *ap, void *elem)
4220Sstevel@tonic-gate {
4230Sstevel@tonic-gate uu_avl_walk_t *wp;
4240Sstevel@tonic-gate uu_avl_pool_t *pp = ap->ua_pool;
4250Sstevel@tonic-gate uintptr_t *na = NODE_ARRAY(pp, elem);
4260Sstevel@tonic-gate
4270Sstevel@tonic-gate if (ap->ua_debug) {
4280Sstevel@tonic-gate /*
4290Sstevel@tonic-gate * invalidate outstanding uu_avl_index_ts.
4300Sstevel@tonic-gate */
4310Sstevel@tonic-gate ap->ua_index = INDEX_NEXT(ap->ua_index);
4320Sstevel@tonic-gate }
4330Sstevel@tonic-gate
4340Sstevel@tonic-gate /*
4350Sstevel@tonic-gate * Robust walkers most be advanced, if we are removing the node
4360Sstevel@tonic-gate * they are currently using. In debug mode, non-robust walkers
4370Sstevel@tonic-gate * are also on the walker list.
4380Sstevel@tonic-gate */
4390Sstevel@tonic-gate for (wp = ap->ua_null_walk.uaw_next; wp != &ap->ua_null_walk;
4400Sstevel@tonic-gate wp = wp->uaw_next) {
4410Sstevel@tonic-gate if (wp->uaw_robust) {
4420Sstevel@tonic-gate if (elem == wp->uaw_next_result)
4430Sstevel@tonic-gate (void) _avl_walk_advance(wp, ap);
4440Sstevel@tonic-gate } else if (wp->uaw_next_result != NULL) {
4450Sstevel@tonic-gate uu_panic("uu_avl_remove(%p, %p): active non-robust "
446*7240Srh87107 "walker\n", (void *)ap, elem);
4470Sstevel@tonic-gate }
4480Sstevel@tonic-gate }
4490Sstevel@tonic-gate
4500Sstevel@tonic-gate avl_remove(&ap->ua_tree, elem);
4510Sstevel@tonic-gate
4520Sstevel@tonic-gate na[0] = POOL_TO_MARKER(pp);
4532856Snd150628 na[1] = 0;
4540Sstevel@tonic-gate }
4550Sstevel@tonic-gate
4560Sstevel@tonic-gate void *
uu_avl_teardown(uu_avl_t * ap,void ** cookie)4570Sstevel@tonic-gate uu_avl_teardown(uu_avl_t *ap, void **cookie)
4580Sstevel@tonic-gate {
459407Sjwadams void *elem = avl_destroy_nodes(&ap->ua_tree, cookie);
460407Sjwadams
461407Sjwadams if (elem != NULL) {
462407Sjwadams uu_avl_pool_t *pp = ap->ua_pool;
463407Sjwadams uintptr_t *na = NODE_ARRAY(pp, elem);
464407Sjwadams
465407Sjwadams na[0] = POOL_TO_MARKER(pp);
4662856Snd150628 na[1] = 0;
467407Sjwadams }
468407Sjwadams return (elem);
4690Sstevel@tonic-gate }
4700Sstevel@tonic-gate
4710Sstevel@tonic-gate void *
uu_avl_find(uu_avl_t * ap,void * elem,void * private,uu_avl_index_t * out)4720Sstevel@tonic-gate uu_avl_find(uu_avl_t *ap, void *elem, void *private, uu_avl_index_t *out)
4730Sstevel@tonic-gate {
4740Sstevel@tonic-gate struct uu_avl_node_compare_info info;
4750Sstevel@tonic-gate void *result;
4760Sstevel@tonic-gate
4770Sstevel@tonic-gate info.ac_compare = ap->ua_pool->uap_cmp;
4780Sstevel@tonic-gate info.ac_private = private;
4790Sstevel@tonic-gate info.ac_right = elem;
4800Sstevel@tonic-gate info.ac_found = NULL;
4810Sstevel@tonic-gate
4820Sstevel@tonic-gate result = avl_find(&ap->ua_tree, &info, out);
4830Sstevel@tonic-gate if (out != NULL)
4840Sstevel@tonic-gate *out = INDEX_ENCODE(ap, *out);
4850Sstevel@tonic-gate
4860Sstevel@tonic-gate if (ap->ua_debug && result != NULL)
4870Sstevel@tonic-gate uu_panic("uu_avl_find: internal error: avl_find succeeded\n");
4880Sstevel@tonic-gate
4890Sstevel@tonic-gate return (info.ac_found);
4900Sstevel@tonic-gate }
4910Sstevel@tonic-gate
4920Sstevel@tonic-gate void
uu_avl_insert(uu_avl_t * ap,void * elem,uu_avl_index_t idx)4930Sstevel@tonic-gate uu_avl_insert(uu_avl_t *ap, void *elem, uu_avl_index_t idx)
4940Sstevel@tonic-gate {
4950Sstevel@tonic-gate if (ap->ua_debug) {
4960Sstevel@tonic-gate uu_avl_pool_t *pp = ap->ua_pool;
4970Sstevel@tonic-gate uintptr_t *na = NODE_ARRAY(pp, elem);
4980Sstevel@tonic-gate
4992856Snd150628 if (na[1] != 0)
5000Sstevel@tonic-gate uu_panic("uu_avl_insert(%p, %p, %p): node already "
5010Sstevel@tonic-gate "in tree, or corrupt\n",
502*7240Srh87107 (void *)ap, elem, (void *)idx);
5032856Snd150628 if (na[0] == 0)
5040Sstevel@tonic-gate uu_panic("uu_avl_insert(%p, %p, %p): node not "
5050Sstevel@tonic-gate "initialized\n",
506*7240Srh87107 (void *)ap, elem, (void *)idx);
5070Sstevel@tonic-gate if (na[0] != POOL_TO_MARKER(pp))
5080Sstevel@tonic-gate uu_panic("uu_avl_insert(%p, %p, %p): node from "
5090Sstevel@tonic-gate "other pool, or corrupt\n",
510*7240Srh87107 (void *)ap, elem, (void *)idx);
5110Sstevel@tonic-gate
5120Sstevel@tonic-gate if (!INDEX_VALID(ap, idx))
5130Sstevel@tonic-gate uu_panic("uu_avl_insert(%p, %p, %p): %s\n",
514*7240Srh87107 (void *)ap, elem, (void *)idx,
5150Sstevel@tonic-gate INDEX_CHECK(idx)? "outdated index" :
5160Sstevel@tonic-gate "invalid index");
5170Sstevel@tonic-gate
5180Sstevel@tonic-gate /*
5190Sstevel@tonic-gate * invalidate outstanding uu_avl_index_ts.
5200Sstevel@tonic-gate */
5210Sstevel@tonic-gate ap->ua_index = INDEX_NEXT(ap->ua_index);
5220Sstevel@tonic-gate }
5230Sstevel@tonic-gate avl_insert(&ap->ua_tree, elem, INDEX_DECODE(idx));
5240Sstevel@tonic-gate }
5250Sstevel@tonic-gate
5260Sstevel@tonic-gate void *
uu_avl_nearest_next(uu_avl_t * ap,uu_avl_index_t idx)5270Sstevel@tonic-gate uu_avl_nearest_next(uu_avl_t *ap, uu_avl_index_t idx)
5280Sstevel@tonic-gate {
5290Sstevel@tonic-gate if (ap->ua_debug && !INDEX_VALID(ap, idx))
5300Sstevel@tonic-gate uu_panic("uu_avl_nearest_next(%p, %p): %s\n",
531*7240Srh87107 (void *)ap, (void *)idx, INDEX_CHECK(idx)?
532*7240Srh87107 "outdated index" : "invalid index");
5330Sstevel@tonic-gate return (avl_nearest(&ap->ua_tree, INDEX_DECODE(idx), AVL_AFTER));
5340Sstevel@tonic-gate }
5350Sstevel@tonic-gate
5360Sstevel@tonic-gate void *
uu_avl_nearest_prev(uu_avl_t * ap,uu_avl_index_t idx)5370Sstevel@tonic-gate uu_avl_nearest_prev(uu_avl_t *ap, uu_avl_index_t idx)
5380Sstevel@tonic-gate {
5390Sstevel@tonic-gate if (ap->ua_debug && !INDEX_VALID(ap, idx))
5400Sstevel@tonic-gate uu_panic("uu_avl_nearest_prev(%p, %p): %s\n",
541*7240Srh87107 (void *)ap, (void *)idx, INDEX_CHECK(idx)?
542*7240Srh87107 "outdated index" : "invalid index");
5430Sstevel@tonic-gate return (avl_nearest(&ap->ua_tree, INDEX_DECODE(idx), AVL_BEFORE));
5440Sstevel@tonic-gate }
5450Sstevel@tonic-gate
5460Sstevel@tonic-gate /*
5470Sstevel@tonic-gate * called from uu_lockup() and uu_release(), as part of our fork1()-safety.
5480Sstevel@tonic-gate */
5490Sstevel@tonic-gate void
uu_avl_lockup(void)5500Sstevel@tonic-gate uu_avl_lockup(void)
5510Sstevel@tonic-gate {
5520Sstevel@tonic-gate uu_avl_pool_t *pp;
5530Sstevel@tonic-gate
5540Sstevel@tonic-gate (void) pthread_mutex_lock(&uu_apool_list_lock);
5550Sstevel@tonic-gate for (pp = uu_null_apool.uap_next; pp != &uu_null_apool;
5560Sstevel@tonic-gate pp = pp->uap_next)
5570Sstevel@tonic-gate (void) pthread_mutex_lock(&pp->uap_lock);
5580Sstevel@tonic-gate }
5590Sstevel@tonic-gate
5600Sstevel@tonic-gate void
uu_avl_release(void)5610Sstevel@tonic-gate uu_avl_release(void)
5620Sstevel@tonic-gate {
5630Sstevel@tonic-gate uu_avl_pool_t *pp;
5640Sstevel@tonic-gate
5650Sstevel@tonic-gate for (pp = uu_null_apool.uap_next; pp != &uu_null_apool;
5660Sstevel@tonic-gate pp = pp->uap_next)
5670Sstevel@tonic-gate (void) pthread_mutex_unlock(&pp->uap_lock);
5680Sstevel@tonic-gate (void) pthread_mutex_unlock(&uu_apool_list_lock);
5690Sstevel@tonic-gate }
570