17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate * CDDL HEADER START
37c478bd9Sstevel@tonic-gate *
47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the
55ad82045Snd * Common Development and Distribution License (the "License").
65ad82045Snd * You may not use this file except in compliance with the License.
77c478bd9Sstevel@tonic-gate *
87c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
97c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
107c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions
117c478bd9Sstevel@tonic-gate * and limitations under the License.
127c478bd9Sstevel@tonic-gate *
137c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
147c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
157c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
167c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
177c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
187c478bd9Sstevel@tonic-gate *
197c478bd9Sstevel@tonic-gate * CDDL HEADER END
207c478bd9Sstevel@tonic-gate */
217c478bd9Sstevel@tonic-gate /*
22903a11ebSrh * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
237c478bd9Sstevel@tonic-gate * Use is subject to license terms.
247c478bd9Sstevel@tonic-gate */
257c478bd9Sstevel@tonic-gate
267c478bd9Sstevel@tonic-gate #include "libuutil_common.h"
277c478bd9Sstevel@tonic-gate
287c478bd9Sstevel@tonic-gate #include <stdlib.h>
297c478bd9Sstevel@tonic-gate #include <string.h>
307c478bd9Sstevel@tonic-gate #include <unistd.h>
317c478bd9Sstevel@tonic-gate #include <sys/avl.h>
327c478bd9Sstevel@tonic-gate
337c478bd9Sstevel@tonic-gate static uu_avl_pool_t uu_null_apool = { &uu_null_apool, &uu_null_apool };
347c478bd9Sstevel@tonic-gate static pthread_mutex_t uu_apool_list_lock = PTHREAD_MUTEX_INITIALIZER;
357c478bd9Sstevel@tonic-gate
367c478bd9Sstevel@tonic-gate /*
377c478bd9Sstevel@tonic-gate * The index mark change on every insert and delete, to catch stale
387c478bd9Sstevel@tonic-gate * references.
397c478bd9Sstevel@tonic-gate *
407c478bd9Sstevel@tonic-gate * We leave the low bit alone, since the avl code uses it.
417c478bd9Sstevel@tonic-gate */
427c478bd9Sstevel@tonic-gate #define INDEX_MAX (sizeof (uintptr_t) - 2)
437c478bd9Sstevel@tonic-gate #define INDEX_NEXT(m) (((m) == INDEX_MAX)? 2 : ((m) + 2) & INDEX_MAX)
447c478bd9Sstevel@tonic-gate
457c478bd9Sstevel@tonic-gate #define INDEX_DECODE(i) ((i) & ~INDEX_MAX)
467c478bd9Sstevel@tonic-gate #define INDEX_ENCODE(p, n) (((n) & ~INDEX_MAX) | (p)->ua_index)
477c478bd9Sstevel@tonic-gate #define INDEX_VALID(p, i) (((i) & INDEX_MAX) == (p)->ua_index)
487c478bd9Sstevel@tonic-gate #define INDEX_CHECK(i) (((i) & INDEX_MAX) != 0)
497c478bd9Sstevel@tonic-gate
507c478bd9Sstevel@tonic-gate /*
517c478bd9Sstevel@tonic-gate * When an element is inactive (not in a tree), we keep a marked pointer to
527c478bd9Sstevel@tonic-gate * its containing pool in its first word, and a NULL pointer in its second.
537c478bd9Sstevel@tonic-gate *
547c478bd9Sstevel@tonic-gate * On insert, we use these to verify that it comes from the correct pool.
557c478bd9Sstevel@tonic-gate */
567c478bd9Sstevel@tonic-gate #define NODE_ARRAY(p, n) ((uintptr_t *)((uintptr_t)(n) + \
577c478bd9Sstevel@tonic-gate (pp)->uap_nodeoffset))
587c478bd9Sstevel@tonic-gate
597c478bd9Sstevel@tonic-gate #define POOL_TO_MARKER(pp) (((uintptr_t)(pp) | 1))
607c478bd9Sstevel@tonic-gate
617c478bd9Sstevel@tonic-gate #define DEAD_MARKER 0xc4
627c478bd9Sstevel@tonic-gate
637c478bd9Sstevel@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)647c478bd9Sstevel@tonic-gate uu_avl_pool_create(const char *name, size_t objsize, size_t nodeoffset,
657c478bd9Sstevel@tonic-gate uu_compare_fn_t *compare_func, uint32_t flags)
667c478bd9Sstevel@tonic-gate {
677c478bd9Sstevel@tonic-gate uu_avl_pool_t *pp, *next, *prev;
687c478bd9Sstevel@tonic-gate
697c478bd9Sstevel@tonic-gate if (name == NULL ||
707c478bd9Sstevel@tonic-gate uu_check_name(name, UU_NAME_DOMAIN) == -1 ||
717c478bd9Sstevel@tonic-gate nodeoffset + sizeof (uu_avl_node_t) > objsize ||
727c478bd9Sstevel@tonic-gate compare_func == NULL) {
737c478bd9Sstevel@tonic-gate uu_set_error(UU_ERROR_INVALID_ARGUMENT);
747c478bd9Sstevel@tonic-gate return (NULL);
757c478bd9Sstevel@tonic-gate }
767c478bd9Sstevel@tonic-gate
777c478bd9Sstevel@tonic-gate if (flags & ~UU_AVL_POOL_DEBUG) {
787c478bd9Sstevel@tonic-gate uu_set_error(UU_ERROR_UNKNOWN_FLAG);
797c478bd9Sstevel@tonic-gate return (NULL);
807c478bd9Sstevel@tonic-gate }
817c478bd9Sstevel@tonic-gate
827c478bd9Sstevel@tonic-gate pp = uu_zalloc(sizeof (uu_avl_pool_t));
837c478bd9Sstevel@tonic-gate if (pp == NULL) {
847c478bd9Sstevel@tonic-gate uu_set_error(UU_ERROR_NO_MEMORY);
857c478bd9Sstevel@tonic-gate return (NULL);
867c478bd9Sstevel@tonic-gate }
877c478bd9Sstevel@tonic-gate
887c478bd9Sstevel@tonic-gate (void) strlcpy(pp->uap_name, name, sizeof (pp->uap_name));
897c478bd9Sstevel@tonic-gate pp->uap_nodeoffset = nodeoffset;
907c478bd9Sstevel@tonic-gate pp->uap_objsize = objsize;
917c478bd9Sstevel@tonic-gate pp->uap_cmp = compare_func;
927c478bd9Sstevel@tonic-gate if (flags & UU_AVL_POOL_DEBUG)
937c478bd9Sstevel@tonic-gate pp->uap_debug = 1;
947c478bd9Sstevel@tonic-gate pp->uap_last_index = 0;
957c478bd9Sstevel@tonic-gate
967c478bd9Sstevel@tonic-gate (void) pthread_mutex_init(&pp->uap_lock, NULL);
977c478bd9Sstevel@tonic-gate
988918dff3Sjwadams pp->uap_null_avl.ua_next_enc = UU_PTR_ENCODE(&pp->uap_null_avl);
998918dff3Sjwadams pp->uap_null_avl.ua_prev_enc = UU_PTR_ENCODE(&pp->uap_null_avl);
1007c478bd9Sstevel@tonic-gate
1017c478bd9Sstevel@tonic-gate (void) pthread_mutex_lock(&uu_apool_list_lock);
1027c478bd9Sstevel@tonic-gate pp->uap_next = next = &uu_null_apool;
1037c478bd9Sstevel@tonic-gate pp->uap_prev = prev = next->uap_prev;
1047c478bd9Sstevel@tonic-gate next->uap_prev = pp;
1057c478bd9Sstevel@tonic-gate prev->uap_next = pp;
1067c478bd9Sstevel@tonic-gate (void) pthread_mutex_unlock(&uu_apool_list_lock);
1077c478bd9Sstevel@tonic-gate
1087c478bd9Sstevel@tonic-gate return (pp);
1097c478bd9Sstevel@tonic-gate }
1107c478bd9Sstevel@tonic-gate
1117c478bd9Sstevel@tonic-gate void
uu_avl_pool_destroy(uu_avl_pool_t * pp)1127c478bd9Sstevel@tonic-gate uu_avl_pool_destroy(uu_avl_pool_t *pp)
1137c478bd9Sstevel@tonic-gate {
1147c478bd9Sstevel@tonic-gate if (pp->uap_debug) {
1158918dff3Sjwadams if (pp->uap_null_avl.ua_next_enc !=
1168918dff3Sjwadams UU_PTR_ENCODE(&pp->uap_null_avl) ||
1178918dff3Sjwadams pp->uap_null_avl.ua_prev_enc !=
1188918dff3Sjwadams UU_PTR_ENCODE(&pp->uap_null_avl)) {
1197c478bd9Sstevel@tonic-gate uu_panic("uu_avl_pool_destroy: Pool \"%.*s\" (%p) has "
1207c478bd9Sstevel@tonic-gate "outstanding avls, or is corrupt.\n",
121903a11ebSrh (int)sizeof (pp->uap_name), pp->uap_name,
122903a11ebSrh (void *)pp);
1237c478bd9Sstevel@tonic-gate }
1247c478bd9Sstevel@tonic-gate }
1257c478bd9Sstevel@tonic-gate (void) pthread_mutex_lock(&uu_apool_list_lock);
1267c478bd9Sstevel@tonic-gate pp->uap_next->uap_prev = pp->uap_prev;
1277c478bd9Sstevel@tonic-gate pp->uap_prev->uap_next = pp->uap_next;
1287c478bd9Sstevel@tonic-gate (void) pthread_mutex_unlock(&uu_apool_list_lock);
129*c33daa8aSAlan Somers (void) pthread_mutex_destroy(&pp->uap_lock);
1307c478bd9Sstevel@tonic-gate pp->uap_prev = NULL;
1317c478bd9Sstevel@tonic-gate pp->uap_next = NULL;
1327c478bd9Sstevel@tonic-gate uu_free(pp);
1337c478bd9Sstevel@tonic-gate }
1347c478bd9Sstevel@tonic-gate
1357c478bd9Sstevel@tonic-gate void
uu_avl_node_init(void * base,uu_avl_node_t * np,uu_avl_pool_t * pp)1367c478bd9Sstevel@tonic-gate uu_avl_node_init(void *base, uu_avl_node_t *np, uu_avl_pool_t *pp)
1377c478bd9Sstevel@tonic-gate {
1387c478bd9Sstevel@tonic-gate uintptr_t *na = (uintptr_t *)np;
1397c478bd9Sstevel@tonic-gate
1407c478bd9Sstevel@tonic-gate if (pp->uap_debug) {
1417c478bd9Sstevel@tonic-gate uintptr_t offset = (uintptr_t)np - (uintptr_t)base;
1427c478bd9Sstevel@tonic-gate if (offset + sizeof (*np) > pp->uap_objsize) {
1437c478bd9Sstevel@tonic-gate uu_panic("uu_avl_node_init(%p, %p, %p (\"%s\")): "
1447c478bd9Sstevel@tonic-gate "offset %ld doesn't fit in object (size %ld)\n",
145903a11ebSrh base, (void *)np, (void *)pp, pp->uap_name,
146903a11ebSrh (long)offset, (long)pp->uap_objsize);
1477c478bd9Sstevel@tonic-gate }
1487c478bd9Sstevel@tonic-gate if (offset != pp->uap_nodeoffset) {
1497c478bd9Sstevel@tonic-gate uu_panic("uu_avl_node_init(%p, %p, %p (\"%s\")): "
1507c478bd9Sstevel@tonic-gate "offset %ld doesn't match pool's offset (%ld)\n",
151903a11ebSrh base, (void *)np, (void *)pp, pp->uap_name,
152903a11ebSrh (long)offset, (long)pp->uap_objsize);
1537c478bd9Sstevel@tonic-gate }
1547c478bd9Sstevel@tonic-gate }
1557c478bd9Sstevel@tonic-gate
1567c478bd9Sstevel@tonic-gate na[0] = POOL_TO_MARKER(pp);
1575ad82045Snd na[1] = 0;
1587c478bd9Sstevel@tonic-gate }
1597c478bd9Sstevel@tonic-gate
1607c478bd9Sstevel@tonic-gate void
uu_avl_node_fini(void * base,uu_avl_node_t * np,uu_avl_pool_t * pp)1617c478bd9Sstevel@tonic-gate uu_avl_node_fini(void *base, uu_avl_node_t *np, uu_avl_pool_t *pp)
1627c478bd9Sstevel@tonic-gate {
1637c478bd9Sstevel@tonic-gate uintptr_t *na = (uintptr_t *)np;
1647c478bd9Sstevel@tonic-gate
1657c478bd9Sstevel@tonic-gate if (pp->uap_debug) {
1667c478bd9Sstevel@tonic-gate if (na[0] == DEAD_MARKER && na[1] == DEAD_MARKER) {
1677c478bd9Sstevel@tonic-gate uu_panic("uu_avl_node_fini(%p, %p, %p (\"%s\")): "
1687c478bd9Sstevel@tonic-gate "node already finied\n",
169903a11ebSrh base, (void *)np, (void *)pp, pp->uap_name);
1707c478bd9Sstevel@tonic-gate }
1715ad82045Snd if (na[0] != POOL_TO_MARKER(pp) || na[1] != 0) {
1727c478bd9Sstevel@tonic-gate uu_panic("uu_avl_node_fini(%p, %p, %p (\"%s\")): "
1737c478bd9Sstevel@tonic-gate "node corrupt, in tree, or in different pool\n",
174903a11ebSrh base, (void *)np, (void *)pp, pp->uap_name);
1757c478bd9Sstevel@tonic-gate }
1767c478bd9Sstevel@tonic-gate }
1777c478bd9Sstevel@tonic-gate
1787c478bd9Sstevel@tonic-gate na[0] = DEAD_MARKER;
1797c478bd9Sstevel@tonic-gate na[1] = DEAD_MARKER;
1807c478bd9Sstevel@tonic-gate na[2] = DEAD_MARKER;
1817c478bd9Sstevel@tonic-gate }
1827c478bd9Sstevel@tonic-gate
1837c478bd9Sstevel@tonic-gate struct uu_avl_node_compare_info {
1847c478bd9Sstevel@tonic-gate uu_compare_fn_t *ac_compare;
1857c478bd9Sstevel@tonic-gate void *ac_private;
1867c478bd9Sstevel@tonic-gate void *ac_right;
1877c478bd9Sstevel@tonic-gate void *ac_found;
1887c478bd9Sstevel@tonic-gate };
1897c478bd9Sstevel@tonic-gate
1907c478bd9Sstevel@tonic-gate static int
uu_avl_node_compare(const void * l,const void * r)1917c478bd9Sstevel@tonic-gate uu_avl_node_compare(const void *l, const void *r)
1927c478bd9Sstevel@tonic-gate {
1937c478bd9Sstevel@tonic-gate struct uu_avl_node_compare_info *info =
1947c478bd9Sstevel@tonic-gate (struct uu_avl_node_compare_info *)l;
1957c478bd9Sstevel@tonic-gate
1967c478bd9Sstevel@tonic-gate int res = info->ac_compare(r, info->ac_right, info->ac_private);
1977c478bd9Sstevel@tonic-gate
1987c478bd9Sstevel@tonic-gate if (res == 0) {
1997c478bd9Sstevel@tonic-gate if (info->ac_found == NULL)
2007c478bd9Sstevel@tonic-gate info->ac_found = (void *)r;
2017c478bd9Sstevel@tonic-gate return (-1);
2027c478bd9Sstevel@tonic-gate }
2037c478bd9Sstevel@tonic-gate if (res < 0)
2047c478bd9Sstevel@tonic-gate return (1);
2057c478bd9Sstevel@tonic-gate return (-1);
2067c478bd9Sstevel@tonic-gate }
2077c478bd9Sstevel@tonic-gate
2087c478bd9Sstevel@tonic-gate uu_avl_t *
uu_avl_create(uu_avl_pool_t * pp,void * parent,uint32_t flags)2097c478bd9Sstevel@tonic-gate uu_avl_create(uu_avl_pool_t *pp, void *parent, uint32_t flags)
2107c478bd9Sstevel@tonic-gate {
2117c478bd9Sstevel@tonic-gate uu_avl_t *ap, *next, *prev;
2127c478bd9Sstevel@tonic-gate
2138918dff3Sjwadams if (flags & ~UU_AVL_DEBUG) {
2147c478bd9Sstevel@tonic-gate uu_set_error(UU_ERROR_UNKNOWN_FLAG);
2157c478bd9Sstevel@tonic-gate return (NULL);
2167c478bd9Sstevel@tonic-gate }
2177c478bd9Sstevel@tonic-gate
2187c478bd9Sstevel@tonic-gate ap = uu_zalloc(sizeof (*ap));
2197c478bd9Sstevel@tonic-gate if (ap == NULL) {
2207c478bd9Sstevel@tonic-gate uu_set_error(UU_ERROR_NO_MEMORY);
2217c478bd9Sstevel@tonic-gate return (NULL);
2227c478bd9Sstevel@tonic-gate }
2237c478bd9Sstevel@tonic-gate
2247c478bd9Sstevel@tonic-gate ap->ua_pool = pp;
2258918dff3Sjwadams ap->ua_parent_enc = UU_PTR_ENCODE(parent);
2267c478bd9Sstevel@tonic-gate ap->ua_debug = pp->uap_debug || (flags & UU_AVL_DEBUG);
2277c478bd9Sstevel@tonic-gate ap->ua_index = (pp->uap_last_index = INDEX_NEXT(pp->uap_last_index));
2287c478bd9Sstevel@tonic-gate
2297c478bd9Sstevel@tonic-gate avl_create(&ap->ua_tree, &uu_avl_node_compare, pp->uap_objsize,
2307c478bd9Sstevel@tonic-gate pp->uap_nodeoffset);
2317c478bd9Sstevel@tonic-gate
2327c478bd9Sstevel@tonic-gate ap->ua_null_walk.uaw_next = &ap->ua_null_walk;
2337c478bd9Sstevel@tonic-gate ap->ua_null_walk.uaw_prev = &ap->ua_null_walk;
2347c478bd9Sstevel@tonic-gate
2357c478bd9Sstevel@tonic-gate (void) pthread_mutex_lock(&pp->uap_lock);
2368918dff3Sjwadams next = &pp->uap_null_avl;
2378918dff3Sjwadams prev = UU_PTR_DECODE(next->ua_prev_enc);
2388918dff3Sjwadams ap->ua_next_enc = UU_PTR_ENCODE(next);
2398918dff3Sjwadams ap->ua_prev_enc = UU_PTR_ENCODE(prev);
2408918dff3Sjwadams next->ua_prev_enc = UU_PTR_ENCODE(ap);
2418918dff3Sjwadams prev->ua_next_enc = UU_PTR_ENCODE(ap);
2427c478bd9Sstevel@tonic-gate (void) pthread_mutex_unlock(&pp->uap_lock);
2437c478bd9Sstevel@tonic-gate
2447c478bd9Sstevel@tonic-gate return (ap);
2457c478bd9Sstevel@tonic-gate }
2467c478bd9Sstevel@tonic-gate
2477c478bd9Sstevel@tonic-gate void
uu_avl_destroy(uu_avl_t * ap)2487c478bd9Sstevel@tonic-gate uu_avl_destroy(uu_avl_t *ap)
2497c478bd9Sstevel@tonic-gate {
2507c478bd9Sstevel@tonic-gate uu_avl_pool_t *pp = ap->ua_pool;
2517c478bd9Sstevel@tonic-gate
2527c478bd9Sstevel@tonic-gate if (ap->ua_debug) {
2537c478bd9Sstevel@tonic-gate if (avl_numnodes(&ap->ua_tree) != 0) {
254903a11ebSrh uu_panic("uu_avl_destroy(%p): tree not empty\n",
255903a11ebSrh (void *)ap);
2567c478bd9Sstevel@tonic-gate }
2577c478bd9Sstevel@tonic-gate if (ap->ua_null_walk.uaw_next != &ap->ua_null_walk ||
2587c478bd9Sstevel@tonic-gate ap->ua_null_walk.uaw_prev != &ap->ua_null_walk) {
2597c478bd9Sstevel@tonic-gate uu_panic("uu_avl_destroy(%p): outstanding walkers\n",
260903a11ebSrh (void *)ap);
2617c478bd9Sstevel@tonic-gate }
2627c478bd9Sstevel@tonic-gate }
2637c478bd9Sstevel@tonic-gate (void) pthread_mutex_lock(&pp->uap_lock);
2648918dff3Sjwadams UU_AVL_PTR(ap->ua_next_enc)->ua_prev_enc = ap->ua_prev_enc;
2658918dff3Sjwadams UU_AVL_PTR(ap->ua_prev_enc)->ua_next_enc = ap->ua_next_enc;
2667c478bd9Sstevel@tonic-gate (void) pthread_mutex_unlock(&pp->uap_lock);
2678918dff3Sjwadams ap->ua_prev_enc = UU_PTR_ENCODE(NULL);
2688918dff3Sjwadams ap->ua_next_enc = UU_PTR_ENCODE(NULL);
2697c478bd9Sstevel@tonic-gate
2707c478bd9Sstevel@tonic-gate ap->ua_pool = NULL;
2717c478bd9Sstevel@tonic-gate avl_destroy(&ap->ua_tree);
2727c478bd9Sstevel@tonic-gate
2737c478bd9Sstevel@tonic-gate uu_free(ap);
2747c478bd9Sstevel@tonic-gate }
2757c478bd9Sstevel@tonic-gate
2767c478bd9Sstevel@tonic-gate size_t
uu_avl_numnodes(uu_avl_t * ap)2777c478bd9Sstevel@tonic-gate uu_avl_numnodes(uu_avl_t *ap)
2787c478bd9Sstevel@tonic-gate {
2797c478bd9Sstevel@tonic-gate return (avl_numnodes(&ap->ua_tree));
2807c478bd9Sstevel@tonic-gate }
2817c478bd9Sstevel@tonic-gate
2827c478bd9Sstevel@tonic-gate void *
uu_avl_first(uu_avl_t * ap)2837c478bd9Sstevel@tonic-gate uu_avl_first(uu_avl_t *ap)
2847c478bd9Sstevel@tonic-gate {
2857c478bd9Sstevel@tonic-gate return (avl_first(&ap->ua_tree));
2867c478bd9Sstevel@tonic-gate }
2877c478bd9Sstevel@tonic-gate
2887c478bd9Sstevel@tonic-gate void *
uu_avl_last(uu_avl_t * ap)2897c478bd9Sstevel@tonic-gate uu_avl_last(uu_avl_t *ap)
2907c478bd9Sstevel@tonic-gate {
2917c478bd9Sstevel@tonic-gate return (avl_last(&ap->ua_tree));
2927c478bd9Sstevel@tonic-gate }
2937c478bd9Sstevel@tonic-gate
2947c478bd9Sstevel@tonic-gate void *
uu_avl_next(uu_avl_t * ap,void * node)2957c478bd9Sstevel@tonic-gate uu_avl_next(uu_avl_t *ap, void *node)
2967c478bd9Sstevel@tonic-gate {
2977c478bd9Sstevel@tonic-gate return (AVL_NEXT(&ap->ua_tree, node));
2987c478bd9Sstevel@tonic-gate }
2997c478bd9Sstevel@tonic-gate
3007c478bd9Sstevel@tonic-gate void *
uu_avl_prev(uu_avl_t * ap,void * node)3017c478bd9Sstevel@tonic-gate uu_avl_prev(uu_avl_t *ap, void *node)
3027c478bd9Sstevel@tonic-gate {
3037c478bd9Sstevel@tonic-gate return (AVL_PREV(&ap->ua_tree, node));
3047c478bd9Sstevel@tonic-gate }
3057c478bd9Sstevel@tonic-gate
3067c478bd9Sstevel@tonic-gate static void
_avl_walk_init(uu_avl_walk_t * wp,uu_avl_t * ap,uint32_t flags)3077c478bd9Sstevel@tonic-gate _avl_walk_init(uu_avl_walk_t *wp, uu_avl_t *ap, uint32_t flags)
3087c478bd9Sstevel@tonic-gate {
3097c478bd9Sstevel@tonic-gate uu_avl_walk_t *next, *prev;
3107c478bd9Sstevel@tonic-gate
3117c478bd9Sstevel@tonic-gate int robust = (flags & UU_WALK_ROBUST);
3127c478bd9Sstevel@tonic-gate int direction = (flags & UU_WALK_REVERSE)? -1 : 1;
3137c478bd9Sstevel@tonic-gate
3147c478bd9Sstevel@tonic-gate (void) memset(wp, 0, sizeof (*wp));
3157c478bd9Sstevel@tonic-gate wp->uaw_avl = ap;
3167c478bd9Sstevel@tonic-gate wp->uaw_robust = robust;
3177c478bd9Sstevel@tonic-gate wp->uaw_dir = direction;
3187c478bd9Sstevel@tonic-gate
3197c478bd9Sstevel@tonic-gate if (direction > 0)
3207c478bd9Sstevel@tonic-gate wp->uaw_next_result = avl_first(&ap->ua_tree);
3217c478bd9Sstevel@tonic-gate else
3227c478bd9Sstevel@tonic-gate wp->uaw_next_result = avl_last(&ap->ua_tree);
3237c478bd9Sstevel@tonic-gate
3247c478bd9Sstevel@tonic-gate if (ap->ua_debug || robust) {
3257c478bd9Sstevel@tonic-gate wp->uaw_next = next = &ap->ua_null_walk;
3267c478bd9Sstevel@tonic-gate wp->uaw_prev = prev = next->uaw_prev;
3277c478bd9Sstevel@tonic-gate next->uaw_prev = wp;
3287c478bd9Sstevel@tonic-gate prev->uaw_next = wp;
3297c478bd9Sstevel@tonic-gate }
3307c478bd9Sstevel@tonic-gate }
3317c478bd9Sstevel@tonic-gate
3327c478bd9Sstevel@tonic-gate static void *
_avl_walk_advance(uu_avl_walk_t * wp,uu_avl_t * ap)3337c478bd9Sstevel@tonic-gate _avl_walk_advance(uu_avl_walk_t *wp, uu_avl_t *ap)
3347c478bd9Sstevel@tonic-gate {
3357c478bd9Sstevel@tonic-gate void *np = wp->uaw_next_result;
3367c478bd9Sstevel@tonic-gate
3377c478bd9Sstevel@tonic-gate avl_tree_t *t = &ap->ua_tree;
3387c478bd9Sstevel@tonic-gate
3397c478bd9Sstevel@tonic-gate if (np == NULL)
3407c478bd9Sstevel@tonic-gate return (NULL);
3417c478bd9Sstevel@tonic-gate
3427c478bd9Sstevel@tonic-gate wp->uaw_next_result = (wp->uaw_dir > 0)? AVL_NEXT(t, np) :
3437c478bd9Sstevel@tonic-gate AVL_PREV(t, np);
3447c478bd9Sstevel@tonic-gate
3457c478bd9Sstevel@tonic-gate return (np);
3467c478bd9Sstevel@tonic-gate }
3477c478bd9Sstevel@tonic-gate
3487c478bd9Sstevel@tonic-gate static void
_avl_walk_fini(uu_avl_walk_t * wp)3497c478bd9Sstevel@tonic-gate _avl_walk_fini(uu_avl_walk_t *wp)
3507c478bd9Sstevel@tonic-gate {
3517c478bd9Sstevel@tonic-gate if (wp->uaw_next != NULL) {
3527c478bd9Sstevel@tonic-gate wp->uaw_next->uaw_prev = wp->uaw_prev;
3537c478bd9Sstevel@tonic-gate wp->uaw_prev->uaw_next = wp->uaw_next;
3547c478bd9Sstevel@tonic-gate wp->uaw_next = NULL;
3557c478bd9Sstevel@tonic-gate wp->uaw_prev = NULL;
3567c478bd9Sstevel@tonic-gate }
3577c478bd9Sstevel@tonic-gate wp->uaw_avl = NULL;
3587c478bd9Sstevel@tonic-gate wp->uaw_next_result = NULL;
3597c478bd9Sstevel@tonic-gate }
3607c478bd9Sstevel@tonic-gate
3617c478bd9Sstevel@tonic-gate uu_avl_walk_t *
uu_avl_walk_start(uu_avl_t * ap,uint32_t flags)3627c478bd9Sstevel@tonic-gate uu_avl_walk_start(uu_avl_t *ap, uint32_t flags)
3637c478bd9Sstevel@tonic-gate {
3647c478bd9Sstevel@tonic-gate uu_avl_walk_t *wp;
3657c478bd9Sstevel@tonic-gate
3667c478bd9Sstevel@tonic-gate if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) {
3677c478bd9Sstevel@tonic-gate uu_set_error(UU_ERROR_UNKNOWN_FLAG);
3687c478bd9Sstevel@tonic-gate return (NULL);
3697c478bd9Sstevel@tonic-gate }
3707c478bd9Sstevel@tonic-gate
3717c478bd9Sstevel@tonic-gate wp = uu_zalloc(sizeof (*wp));
3727c478bd9Sstevel@tonic-gate if (wp == NULL) {
3737c478bd9Sstevel@tonic-gate uu_set_error(UU_ERROR_NO_MEMORY);
3747c478bd9Sstevel@tonic-gate return (NULL);
3757c478bd9Sstevel@tonic-gate }
3767c478bd9Sstevel@tonic-gate
3777c478bd9Sstevel@tonic-gate _avl_walk_init(wp, ap, flags);
3787c478bd9Sstevel@tonic-gate return (wp);
3797c478bd9Sstevel@tonic-gate }
3807c478bd9Sstevel@tonic-gate
3817c478bd9Sstevel@tonic-gate void *
uu_avl_walk_next(uu_avl_walk_t * wp)3827c478bd9Sstevel@tonic-gate uu_avl_walk_next(uu_avl_walk_t *wp)
3837c478bd9Sstevel@tonic-gate {
3847c478bd9Sstevel@tonic-gate return (_avl_walk_advance(wp, wp->uaw_avl));
3857c478bd9Sstevel@tonic-gate }
3867c478bd9Sstevel@tonic-gate
3877c478bd9Sstevel@tonic-gate void
uu_avl_walk_end(uu_avl_walk_t * wp)3887c478bd9Sstevel@tonic-gate uu_avl_walk_end(uu_avl_walk_t *wp)
3897c478bd9Sstevel@tonic-gate {
3907c478bd9Sstevel@tonic-gate _avl_walk_fini(wp);
3917c478bd9Sstevel@tonic-gate uu_free(wp);
3927c478bd9Sstevel@tonic-gate }
3937c478bd9Sstevel@tonic-gate
3947c478bd9Sstevel@tonic-gate int
uu_avl_walk(uu_avl_t * ap,uu_walk_fn_t * func,void * private,uint32_t flags)3957c478bd9Sstevel@tonic-gate uu_avl_walk(uu_avl_t *ap, uu_walk_fn_t *func, void *private, uint32_t flags)
3967c478bd9Sstevel@tonic-gate {
3977c478bd9Sstevel@tonic-gate void *e;
3987c478bd9Sstevel@tonic-gate uu_avl_walk_t my_walk;
3997c478bd9Sstevel@tonic-gate
4007c478bd9Sstevel@tonic-gate int status = UU_WALK_NEXT;
4017c478bd9Sstevel@tonic-gate
4027c478bd9Sstevel@tonic-gate if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) {
4037c478bd9Sstevel@tonic-gate uu_set_error(UU_ERROR_UNKNOWN_FLAG);
4047c478bd9Sstevel@tonic-gate return (-1);
4057c478bd9Sstevel@tonic-gate }
4067c478bd9Sstevel@tonic-gate
4077c478bd9Sstevel@tonic-gate _avl_walk_init(&my_walk, ap, flags);
4087c478bd9Sstevel@tonic-gate while (status == UU_WALK_NEXT &&
4097c478bd9Sstevel@tonic-gate (e = _avl_walk_advance(&my_walk, ap)) != NULL)
4107c478bd9Sstevel@tonic-gate status = (*func)(e, private);
4117c478bd9Sstevel@tonic-gate _avl_walk_fini(&my_walk);
4127c478bd9Sstevel@tonic-gate
4137c478bd9Sstevel@tonic-gate if (status >= 0)
4147c478bd9Sstevel@tonic-gate return (0);
4157c478bd9Sstevel@tonic-gate uu_set_error(UU_ERROR_CALLBACK_FAILED);
4167c478bd9Sstevel@tonic-gate return (-1);
4177c478bd9Sstevel@tonic-gate }
4187c478bd9Sstevel@tonic-gate
4197c478bd9Sstevel@tonic-gate void
uu_avl_remove(uu_avl_t * ap,void * elem)4207c478bd9Sstevel@tonic-gate uu_avl_remove(uu_avl_t *ap, void *elem)
4217c478bd9Sstevel@tonic-gate {
4227c478bd9Sstevel@tonic-gate uu_avl_walk_t *wp;
4237c478bd9Sstevel@tonic-gate uu_avl_pool_t *pp = ap->ua_pool;
4247c478bd9Sstevel@tonic-gate uintptr_t *na = NODE_ARRAY(pp, elem);
4257c478bd9Sstevel@tonic-gate
4267c478bd9Sstevel@tonic-gate if (ap->ua_debug) {
4277c478bd9Sstevel@tonic-gate /*
4287c478bd9Sstevel@tonic-gate * invalidate outstanding uu_avl_index_ts.
4297c478bd9Sstevel@tonic-gate */
4307c478bd9Sstevel@tonic-gate ap->ua_index = INDEX_NEXT(ap->ua_index);
4317c478bd9Sstevel@tonic-gate }
4327c478bd9Sstevel@tonic-gate
4337c478bd9Sstevel@tonic-gate /*
4347c478bd9Sstevel@tonic-gate * Robust walkers most be advanced, if we are removing the node
4357c478bd9Sstevel@tonic-gate * they are currently using. In debug mode, non-robust walkers
4367c478bd9Sstevel@tonic-gate * are also on the walker list.
4377c478bd9Sstevel@tonic-gate */
4387c478bd9Sstevel@tonic-gate for (wp = ap->ua_null_walk.uaw_next; wp != &ap->ua_null_walk;
4397c478bd9Sstevel@tonic-gate wp = wp->uaw_next) {
4407c478bd9Sstevel@tonic-gate if (wp->uaw_robust) {
4417c478bd9Sstevel@tonic-gate if (elem == wp->uaw_next_result)
4427c478bd9Sstevel@tonic-gate (void) _avl_walk_advance(wp, ap);
4437c478bd9Sstevel@tonic-gate } else if (wp->uaw_next_result != NULL) {
4447c478bd9Sstevel@tonic-gate uu_panic("uu_avl_remove(%p, %p): active non-robust "
445903a11ebSrh "walker\n", (void *)ap, elem);
4467c478bd9Sstevel@tonic-gate }
4477c478bd9Sstevel@tonic-gate }
4487c478bd9Sstevel@tonic-gate
4497c478bd9Sstevel@tonic-gate avl_remove(&ap->ua_tree, elem);
4507c478bd9Sstevel@tonic-gate
4517c478bd9Sstevel@tonic-gate na[0] = POOL_TO_MARKER(pp);
4525ad82045Snd na[1] = 0;
4537c478bd9Sstevel@tonic-gate }
4547c478bd9Sstevel@tonic-gate
4557c478bd9Sstevel@tonic-gate void *
uu_avl_teardown(uu_avl_t * ap,void ** cookie)4567c478bd9Sstevel@tonic-gate uu_avl_teardown(uu_avl_t *ap, void **cookie)
4577c478bd9Sstevel@tonic-gate {
4588918dff3Sjwadams void *elem = avl_destroy_nodes(&ap->ua_tree, cookie);
4598918dff3Sjwadams
4608918dff3Sjwadams if (elem != NULL) {
4618918dff3Sjwadams uu_avl_pool_t *pp = ap->ua_pool;
4628918dff3Sjwadams uintptr_t *na = NODE_ARRAY(pp, elem);
4638918dff3Sjwadams
4648918dff3Sjwadams na[0] = POOL_TO_MARKER(pp);
4655ad82045Snd na[1] = 0;
4668918dff3Sjwadams }
4678918dff3Sjwadams return (elem);
4687c478bd9Sstevel@tonic-gate }
4697c478bd9Sstevel@tonic-gate
4707c478bd9Sstevel@tonic-gate void *
uu_avl_find(uu_avl_t * ap,void * elem,void * private,uu_avl_index_t * out)4717c478bd9Sstevel@tonic-gate uu_avl_find(uu_avl_t *ap, void *elem, void *private, uu_avl_index_t *out)
4727c478bd9Sstevel@tonic-gate {
4737c478bd9Sstevel@tonic-gate struct uu_avl_node_compare_info info;
4747c478bd9Sstevel@tonic-gate void *result;
4757c478bd9Sstevel@tonic-gate
4767c478bd9Sstevel@tonic-gate info.ac_compare = ap->ua_pool->uap_cmp;
4777c478bd9Sstevel@tonic-gate info.ac_private = private;
4787c478bd9Sstevel@tonic-gate info.ac_right = elem;
4797c478bd9Sstevel@tonic-gate info.ac_found = NULL;
4807c478bd9Sstevel@tonic-gate
4817c478bd9Sstevel@tonic-gate result = avl_find(&ap->ua_tree, &info, out);
4827c478bd9Sstevel@tonic-gate if (out != NULL)
4837c478bd9Sstevel@tonic-gate *out = INDEX_ENCODE(ap, *out);
4847c478bd9Sstevel@tonic-gate
4857c478bd9Sstevel@tonic-gate if (ap->ua_debug && result != NULL)
4867c478bd9Sstevel@tonic-gate uu_panic("uu_avl_find: internal error: avl_find succeeded\n");
4877c478bd9Sstevel@tonic-gate
4887c478bd9Sstevel@tonic-gate return (info.ac_found);
4897c478bd9Sstevel@tonic-gate }
4907c478bd9Sstevel@tonic-gate
4917c478bd9Sstevel@tonic-gate void
uu_avl_insert(uu_avl_t * ap,void * elem,uu_avl_index_t idx)4927c478bd9Sstevel@tonic-gate uu_avl_insert(uu_avl_t *ap, void *elem, uu_avl_index_t idx)
4937c478bd9Sstevel@tonic-gate {
4947c478bd9Sstevel@tonic-gate if (ap->ua_debug) {
4957c478bd9Sstevel@tonic-gate uu_avl_pool_t *pp = ap->ua_pool;
4967c478bd9Sstevel@tonic-gate uintptr_t *na = NODE_ARRAY(pp, elem);
4977c478bd9Sstevel@tonic-gate
4985ad82045Snd if (na[1] != 0)
4997c478bd9Sstevel@tonic-gate uu_panic("uu_avl_insert(%p, %p, %p): node already "
5007c478bd9Sstevel@tonic-gate "in tree, or corrupt\n",
501903a11ebSrh (void *)ap, elem, (void *)idx);
5025ad82045Snd if (na[0] == 0)
5037c478bd9Sstevel@tonic-gate uu_panic("uu_avl_insert(%p, %p, %p): node not "
5047c478bd9Sstevel@tonic-gate "initialized\n",
505903a11ebSrh (void *)ap, elem, (void *)idx);
5067c478bd9Sstevel@tonic-gate if (na[0] != POOL_TO_MARKER(pp))
5077c478bd9Sstevel@tonic-gate uu_panic("uu_avl_insert(%p, %p, %p): node from "
5087c478bd9Sstevel@tonic-gate "other pool, or corrupt\n",
509903a11ebSrh (void *)ap, elem, (void *)idx);
5107c478bd9Sstevel@tonic-gate
5117c478bd9Sstevel@tonic-gate if (!INDEX_VALID(ap, idx))
5127c478bd9Sstevel@tonic-gate uu_panic("uu_avl_insert(%p, %p, %p): %s\n",
513903a11ebSrh (void *)ap, elem, (void *)idx,
5147c478bd9Sstevel@tonic-gate INDEX_CHECK(idx)? "outdated index" :
5157c478bd9Sstevel@tonic-gate "invalid index");
5167c478bd9Sstevel@tonic-gate
5177c478bd9Sstevel@tonic-gate /*
5187c478bd9Sstevel@tonic-gate * invalidate outstanding uu_avl_index_ts.
5197c478bd9Sstevel@tonic-gate */
5207c478bd9Sstevel@tonic-gate ap->ua_index = INDEX_NEXT(ap->ua_index);
5217c478bd9Sstevel@tonic-gate }
5227c478bd9Sstevel@tonic-gate avl_insert(&ap->ua_tree, elem, INDEX_DECODE(idx));
5237c478bd9Sstevel@tonic-gate }
5247c478bd9Sstevel@tonic-gate
5257c478bd9Sstevel@tonic-gate void *
uu_avl_nearest_next(uu_avl_t * ap,uu_avl_index_t idx)5267c478bd9Sstevel@tonic-gate uu_avl_nearest_next(uu_avl_t *ap, uu_avl_index_t idx)
5277c478bd9Sstevel@tonic-gate {
5287c478bd9Sstevel@tonic-gate if (ap->ua_debug && !INDEX_VALID(ap, idx))
5297c478bd9Sstevel@tonic-gate uu_panic("uu_avl_nearest_next(%p, %p): %s\n",
530903a11ebSrh (void *)ap, (void *)idx, INDEX_CHECK(idx)?
531903a11ebSrh "outdated index" : "invalid index");
5327c478bd9Sstevel@tonic-gate return (avl_nearest(&ap->ua_tree, INDEX_DECODE(idx), AVL_AFTER));
5337c478bd9Sstevel@tonic-gate }
5347c478bd9Sstevel@tonic-gate
5357c478bd9Sstevel@tonic-gate void *
uu_avl_nearest_prev(uu_avl_t * ap,uu_avl_index_t idx)5367c478bd9Sstevel@tonic-gate uu_avl_nearest_prev(uu_avl_t *ap, uu_avl_index_t idx)
5377c478bd9Sstevel@tonic-gate {
5387c478bd9Sstevel@tonic-gate if (ap->ua_debug && !INDEX_VALID(ap, idx))
5397c478bd9Sstevel@tonic-gate uu_panic("uu_avl_nearest_prev(%p, %p): %s\n",
540903a11ebSrh (void *)ap, (void *)idx, INDEX_CHECK(idx)?
541903a11ebSrh "outdated index" : "invalid index");
5427c478bd9Sstevel@tonic-gate return (avl_nearest(&ap->ua_tree, INDEX_DECODE(idx), AVL_BEFORE));
5437c478bd9Sstevel@tonic-gate }
5447c478bd9Sstevel@tonic-gate
5457c478bd9Sstevel@tonic-gate /*
5467c478bd9Sstevel@tonic-gate * called from uu_lockup() and uu_release(), as part of our fork1()-safety.
5477c478bd9Sstevel@tonic-gate */
5487c478bd9Sstevel@tonic-gate void
uu_avl_lockup(void)5497c478bd9Sstevel@tonic-gate uu_avl_lockup(void)
5507c478bd9Sstevel@tonic-gate {
5517c478bd9Sstevel@tonic-gate uu_avl_pool_t *pp;
5527c478bd9Sstevel@tonic-gate
5537c478bd9Sstevel@tonic-gate (void) pthread_mutex_lock(&uu_apool_list_lock);
5547c478bd9Sstevel@tonic-gate for (pp = uu_null_apool.uap_next; pp != &uu_null_apool;
5557c478bd9Sstevel@tonic-gate pp = pp->uap_next)
5567c478bd9Sstevel@tonic-gate (void) pthread_mutex_lock(&pp->uap_lock);
5577c478bd9Sstevel@tonic-gate }
5587c478bd9Sstevel@tonic-gate
5597c478bd9Sstevel@tonic-gate void
uu_avl_release(void)5607c478bd9Sstevel@tonic-gate uu_avl_release(void)
5617c478bd9Sstevel@tonic-gate {
5627c478bd9Sstevel@tonic-gate uu_avl_pool_t *pp;
5637c478bd9Sstevel@tonic-gate
5647c478bd9Sstevel@tonic-gate for (pp = uu_null_apool.uap_next; pp != &uu_null_apool;
5657c478bd9Sstevel@tonic-gate pp = pp->uap_next)
5667c478bd9Sstevel@tonic-gate (void) pthread_mutex_unlock(&pp->uap_lock);
5677c478bd9Sstevel@tonic-gate (void) pthread_mutex_unlock(&uu_apool_list_lock);
5687c478bd9Sstevel@tonic-gate }
569