4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
22 * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
28 #include "libuutil_common.h"
35 static uu_avl_pool_t uu_null_apool = { &uu_null_apool, &uu_null_apool };
36 static pthread_mutex_t uu_apool_list_lock = PTHREAD_MUTEX_INITIALIZER;
39 * The index mark change on every insert and delete, to catch stale
42 * We leave the low bit alone, since the avl code uses it.
44 #define INDEX_MAX (sizeof (uintptr_t) - 2)
45 #define INDEX_NEXT(m) (((m) == INDEX_MAX)? 2 : ((m) + 2) & INDEX_MAX)
47 #define INDEX_DECODE(i) ((i) & ~INDEX_MAX)
48 #define INDEX_ENCODE(p, n) (((n) & ~INDEX_MAX) | (p)->ua_index)
49 #define INDEX_VALID(p, i) (((i) & INDEX_MAX) == (p)->ua_index)
50 #define INDEX_CHECK(i) (((i) & INDEX_MAX) != 0)
53 * When an element is inactive (not in a tree), we keep a marked pointer to
54 * its containing pool in its first word, and a NULL pointer in its second.
56 * On insert, we use these to verify that it comes from the correct pool.
58 #define NODE_ARRAY(p, n) ((uintptr_t *)((uintptr_t)(n) + \
59 (pp)->uap_nodeoffset))
61 #define POOL_TO_MARKER(pp) (((uintptr_t)(pp) | 1))
63 #define DEAD_MARKER 0xc4
66 uu_avl_pool_create(const char *name, size_t objsize, size_t nodeoffset,
67 uu_compare_fn_t *compare_func, uint32_t flags)
69 uu_avl_pool_t *pp, *next, *prev;
72 uu_check_name(name, UU_NAME_DOMAIN) == -1 ||
73 nodeoffset + sizeof (uu_avl_node_t) > objsize ||
74 compare_func == NULL) {
75 uu_set_error(UU_ERROR_INVALID_ARGUMENT);
79 if (flags & ~UU_AVL_POOL_DEBUG) {
80 uu_set_error(UU_ERROR_UNKNOWN_FLAG);
84 pp = uu_zalloc(sizeof (uu_avl_pool_t));
86 uu_set_error(UU_ERROR_NO_MEMORY);
90 (void) strlcpy(pp->uap_name, name, sizeof (pp->uap_name));
91 pp->uap_nodeoffset = nodeoffset;
92 pp->uap_objsize = objsize;
93 pp->uap_cmp = compare_func;
94 if (flags & UU_AVL_POOL_DEBUG)
96 pp->uap_last_index = 0;
98 (void) pthread_mutex_init(&pp->uap_lock, NULL);
100 pp->uap_null_avl.ua_next_enc = UU_PTR_ENCODE(&pp->uap_null_avl);
101 pp->uap_null_avl.ua_prev_enc = UU_PTR_ENCODE(&pp->uap_null_avl);
103 (void) pthread_mutex_lock(&uu_apool_list_lock);
104 pp->uap_next = next = &uu_null_apool;
105 pp->uap_prev = prev = next->uap_prev;
108 (void) pthread_mutex_unlock(&uu_apool_list_lock);
114 uu_avl_pool_destroy(uu_avl_pool_t *pp)
117 if (pp->uap_null_avl.ua_next_enc !=
118 UU_PTR_ENCODE(&pp->uap_null_avl) ||
119 pp->uap_null_avl.ua_prev_enc !=
120 UU_PTR_ENCODE(&pp->uap_null_avl)) {
121 uu_panic("uu_avl_pool_destroy: Pool \"%.*s\" (%p) has "
122 "outstanding avls, or is corrupt.\n",
123 sizeof (pp->uap_name), pp->uap_name, pp);
126 (void) pthread_mutex_lock(&uu_apool_list_lock);
127 pp->uap_next->uap_prev = pp->uap_prev;
128 pp->uap_prev->uap_next = pp->uap_next;
129 (void) pthread_mutex_unlock(&uu_apool_list_lock);
136 uu_avl_node_init(void *base, uu_avl_node_t *np, uu_avl_pool_t *pp)
138 uintptr_t *na = (uintptr_t *)np;
141 uintptr_t offset = (uintptr_t)np - (uintptr_t)base;
142 if (offset + sizeof (*np) > pp->uap_objsize) {
143 uu_panic("uu_avl_node_init(%p, %p, %p (\"%s\")): "
144 "offset %ld doesn't fit in object (size %ld)\n",
145 base, np, pp, pp->uap_name, offset,
148 if (offset != pp->uap_nodeoffset) {
149 uu_panic("uu_avl_node_init(%p, %p, %p (\"%s\")): "
150 "offset %ld doesn't match pool's offset (%ld)\n",
151 base, np, pp, pp->uap_name, offset,
156 na[0] = POOL_TO_MARKER(pp);
161 uu_avl_node_fini(void *base, uu_avl_node_t *np, uu_avl_pool_t *pp)
163 uintptr_t *na = (uintptr_t *)np;
166 if (na[0] == DEAD_MARKER && na[1] == DEAD_MARKER) {
167 uu_panic("uu_avl_node_fini(%p, %p, %p (\"%s\")): "
168 "node already finied\n",
169 base, np, pp, pp->uap_name);
171 if (na[0] != POOL_TO_MARKER(pp) || na[1] != 0) {
172 uu_panic("uu_avl_node_fini(%p, %p, %p (\"%s\")): "
173 "node corrupt, in tree, or in different pool\n",
174 base, np, pp, pp->uap_name);
183 struct uu_avl_node_compare_info {
184 uu_compare_fn_t *ac_compare;
191 uu_avl_node_compare(const void *l, const void *r)
193 struct uu_avl_node_compare_info *info =
194 (struct uu_avl_node_compare_info *)l;
196 int res = info->ac_compare(r, info->ac_right, info->ac_private);
199 if (info->ac_found == NULL)
200 info->ac_found = (void *)r;
209 uu_avl_create(uu_avl_pool_t *pp, void *parent, uint32_t flags)
211 uu_avl_t *ap, *next, *prev;
213 if (flags & ~UU_AVL_DEBUG) {
214 uu_set_error(UU_ERROR_UNKNOWN_FLAG);
218 ap = uu_zalloc(sizeof (*ap));
220 uu_set_error(UU_ERROR_NO_MEMORY);
225 ap->ua_parent_enc = UU_PTR_ENCODE(parent);
226 ap->ua_debug = pp->uap_debug || (flags & UU_AVL_DEBUG);
227 ap->ua_index = (pp->uap_last_index = INDEX_NEXT(pp->uap_last_index));
229 avl_create(&ap->ua_tree, &uu_avl_node_compare, pp->uap_objsize,
232 ap->ua_null_walk.uaw_next = &ap->ua_null_walk;
233 ap->ua_null_walk.uaw_prev = &ap->ua_null_walk;
235 (void) pthread_mutex_lock(&pp->uap_lock);
236 next = &pp->uap_null_avl;
237 prev = UU_PTR_DECODE(next->ua_prev_enc);
238 ap->ua_next_enc = UU_PTR_ENCODE(next);
239 ap->ua_prev_enc = UU_PTR_ENCODE(prev);
240 next->ua_prev_enc = UU_PTR_ENCODE(ap);
241 prev->ua_next_enc = UU_PTR_ENCODE(ap);
242 (void) pthread_mutex_unlock(&pp->uap_lock);
248 uu_avl_destroy(uu_avl_t *ap)
250 uu_avl_pool_t *pp = ap->ua_pool;
253 if (avl_numnodes(&ap->ua_tree) != 0) {
254 uu_panic("uu_avl_destroy(%p): tree not empty\n", ap);
256 if (ap->ua_null_walk.uaw_next != &ap->ua_null_walk ||
257 ap->ua_null_walk.uaw_prev != &ap->ua_null_walk) {
258 uu_panic("uu_avl_destroy(%p): outstanding walkers\n",
262 (void) pthread_mutex_lock(&pp->uap_lock);
263 UU_AVL_PTR(ap->ua_next_enc)->ua_prev_enc = ap->ua_prev_enc;
264 UU_AVL_PTR(ap->ua_prev_enc)->ua_next_enc = ap->ua_next_enc;
265 (void) pthread_mutex_unlock(&pp->uap_lock);
266 ap->ua_prev_enc = UU_PTR_ENCODE(NULL);
267 ap->ua_next_enc = UU_PTR_ENCODE(NULL);
270 avl_destroy(&ap->ua_tree);
276 uu_avl_numnodes(uu_avl_t *ap)
278 return (avl_numnodes(&ap->ua_tree));
282 uu_avl_first(uu_avl_t *ap)
284 return (avl_first(&ap->ua_tree));
288 uu_avl_last(uu_avl_t *ap)
290 return (avl_last(&ap->ua_tree));
294 uu_avl_next(uu_avl_t *ap, void *node)
296 return (AVL_NEXT(&ap->ua_tree, node));
300 uu_avl_prev(uu_avl_t *ap, void *node)
302 return (AVL_PREV(&ap->ua_tree, node));
306 _avl_walk_init(uu_avl_walk_t *wp, uu_avl_t *ap, uint32_t flags)
308 uu_avl_walk_t *next, *prev;
310 int robust = (flags & UU_WALK_ROBUST);
311 int direction = (flags & UU_WALK_REVERSE)? -1 : 1;
313 (void) memset(wp, 0, sizeof (*wp));
315 wp->uaw_robust = robust;
316 wp->uaw_dir = direction;
319 wp->uaw_next_result = avl_first(&ap->ua_tree);
321 wp->uaw_next_result = avl_last(&ap->ua_tree);
323 if (ap->ua_debug || robust) {
324 wp->uaw_next = next = &ap->ua_null_walk;
325 wp->uaw_prev = prev = next->uaw_prev;
332 _avl_walk_advance(uu_avl_walk_t *wp, uu_avl_t *ap)
334 void *np = wp->uaw_next_result;
336 avl_tree_t *t = &ap->ua_tree;
341 wp->uaw_next_result = (wp->uaw_dir > 0)? AVL_NEXT(t, np) :
348 _avl_walk_fini(uu_avl_walk_t *wp)
350 if (wp->uaw_next != NULL) {
351 wp->uaw_next->uaw_prev = wp->uaw_prev;
352 wp->uaw_prev->uaw_next = wp->uaw_next;
357 wp->uaw_next_result = NULL;
361 uu_avl_walk_start(uu_avl_t *ap, uint32_t flags)
365 if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) {
366 uu_set_error(UU_ERROR_UNKNOWN_FLAG);
370 wp = uu_zalloc(sizeof (*wp));
372 uu_set_error(UU_ERROR_NO_MEMORY);
376 _avl_walk_init(wp, ap, flags);
381 uu_avl_walk_next(uu_avl_walk_t *wp)
383 return (_avl_walk_advance(wp, wp->uaw_avl));
387 uu_avl_walk_end(uu_avl_walk_t *wp)
394 uu_avl_walk(uu_avl_t *ap, uu_walk_fn_t *func, void *private, uint32_t flags)
397 uu_avl_walk_t my_walk;
399 int status = UU_WALK_NEXT;
401 if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) {
402 uu_set_error(UU_ERROR_UNKNOWN_FLAG);
406 _avl_walk_init(&my_walk, ap, flags);
407 while (status == UU_WALK_NEXT &&
408 (e = _avl_walk_advance(&my_walk, ap)) != NULL)
409 status = (*func)(e, private);
410 _avl_walk_fini(&my_walk);
414 uu_set_error(UU_ERROR_CALLBACK_FAILED);
419 uu_avl_remove(uu_avl_t *ap, void *elem)
422 uu_avl_pool_t *pp = ap->ua_pool;
423 uintptr_t *na = NODE_ARRAY(pp, elem);
427 * invalidate outstanding uu_avl_index_ts.
429 ap->ua_index = INDEX_NEXT(ap->ua_index);
433 * Robust walkers most be advanced, if we are removing the node
434 * they are currently using. In debug mode, non-robust walkers
435 * are also on the walker list.
437 for (wp = ap->ua_null_walk.uaw_next; wp != &ap->ua_null_walk;
439 if (wp->uaw_robust) {
440 if (elem == wp->uaw_next_result)
441 (void) _avl_walk_advance(wp, ap);
442 } else if (wp->uaw_next_result != NULL) {
443 uu_panic("uu_avl_remove(%p, %p): active non-robust "
444 "walker\n", ap, elem);
448 avl_remove(&ap->ua_tree, elem);
450 na[0] = POOL_TO_MARKER(pp);
455 uu_avl_teardown(uu_avl_t *ap, void **cookie)
457 void *elem = avl_destroy_nodes(&ap->ua_tree, cookie);
460 uu_avl_pool_t *pp = ap->ua_pool;
461 uintptr_t *na = NODE_ARRAY(pp, elem);
463 na[0] = POOL_TO_MARKER(pp);
470 uu_avl_find(uu_avl_t *ap, void *elem, void *private, uu_avl_index_t *out)
472 struct uu_avl_node_compare_info info;
475 info.ac_compare = ap->ua_pool->uap_cmp;
476 info.ac_private = private;
477 info.ac_right = elem;
478 info.ac_found = NULL;
480 result = avl_find(&ap->ua_tree, &info, out);
482 *out = INDEX_ENCODE(ap, *out);
484 if (ap->ua_debug && result != NULL)
485 uu_panic("uu_avl_find: internal error: avl_find succeeded\n");
487 return (info.ac_found);
491 uu_avl_insert(uu_avl_t *ap, void *elem, uu_avl_index_t idx)
494 uu_avl_pool_t *pp = ap->ua_pool;
495 uintptr_t *na = NODE_ARRAY(pp, elem);
498 uu_panic("uu_avl_insert(%p, %p, %p): node already "
499 "in tree, or corrupt\n",
502 uu_panic("uu_avl_insert(%p, %p, %p): node not "
505 if (na[0] != POOL_TO_MARKER(pp))
506 uu_panic("uu_avl_insert(%p, %p, %p): node from "
507 "other pool, or corrupt\n",
510 if (!INDEX_VALID(ap, idx))
511 uu_panic("uu_avl_insert(%p, %p, %p): %s\n",
513 INDEX_CHECK(idx)? "outdated index" :
517 * invalidate outstanding uu_avl_index_ts.
519 ap->ua_index = INDEX_NEXT(ap->ua_index);
521 avl_insert(&ap->ua_tree, elem, INDEX_DECODE(idx));
525 uu_avl_nearest_next(uu_avl_t *ap, uu_avl_index_t idx)
527 if (ap->ua_debug && !INDEX_VALID(ap, idx))
528 uu_panic("uu_avl_nearest_next(%p, %p): %s\n",
529 ap, idx, INDEX_CHECK(idx)? "outdated index" :
531 return (avl_nearest(&ap->ua_tree, INDEX_DECODE(idx), AVL_AFTER));
535 uu_avl_nearest_prev(uu_avl_t *ap, uu_avl_index_t idx)
537 if (ap->ua_debug && !INDEX_VALID(ap, idx))
538 uu_panic("uu_avl_nearest_prev(%p, %p): %s\n",
539 ap, idx, INDEX_CHECK(idx)? "outdated index" :
541 return (avl_nearest(&ap->ua_tree, INDEX_DECODE(idx), AVL_BEFORE));
545 * called from uu_lockup() and uu_release(), as part of our fork1()-safety.
552 (void) pthread_mutex_lock(&uu_apool_list_lock);
553 for (pp = uu_null_apool.uap_next; pp != &uu_null_apool;
555 (void) pthread_mutex_lock(&pp->uap_lock);
563 for (pp = uu_null_apool.uap_next; pp != &uu_null_apool;
565 (void) pthread_mutex_unlock(&pp->uap_lock);
566 (void) pthread_mutex_unlock(&uu_apool_list_lock);