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
9271171e0SMartin 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 *
uu_avl_pool_create(const char * name,size_t objsize,size_t nodeoffset,uu_compare_fn_t * compare_func,uint32_t flags)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
100*dbd5678dSMartin Matuska pp->uap_null_avl.ua_next = &pp->uap_null_avl;
101*dbd5678dSMartin Matuska pp->uap_null_avl.ua_prev = &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
uu_avl_pool_destroy(uu_avl_pool_t * pp)114eda14cbcSMatt Macy uu_avl_pool_destroy(uu_avl_pool_t *pp)
115eda14cbcSMatt Macy {
116eda14cbcSMatt Macy if (pp->uap_debug) {
117*dbd5678dSMartin Matuska if (pp->uap_null_avl.ua_next != &pp->uap_null_avl ||
118*dbd5678dSMartin Matuska pp->uap_null_avl.ua_prev != &pp->uap_null_avl) {
119eda14cbcSMatt Macy uu_panic("uu_avl_pool_destroy: Pool \"%.*s\" (%p) has "
120eda14cbcSMatt Macy "outstanding avls, or is corrupt.\n",
121eda14cbcSMatt Macy (int)sizeof (pp->uap_name), pp->uap_name,
122eda14cbcSMatt Macy (void *)pp);
123eda14cbcSMatt Macy }
124eda14cbcSMatt Macy }
125eda14cbcSMatt Macy (void) pthread_mutex_lock(&uu_apool_list_lock);
126eda14cbcSMatt Macy pp->uap_next->uap_prev = pp->uap_prev;
127eda14cbcSMatt Macy pp->uap_prev->uap_next = pp->uap_next;
128eda14cbcSMatt Macy (void) pthread_mutex_unlock(&uu_apool_list_lock);
129184c1b94SMartin Matuska (void) pthread_mutex_destroy(&pp->uap_lock);
130eda14cbcSMatt Macy pp->uap_prev = NULL;
131eda14cbcSMatt Macy pp->uap_next = NULL;
132eda14cbcSMatt Macy uu_free(pp);
133eda14cbcSMatt Macy }
134eda14cbcSMatt Macy
135eda14cbcSMatt Macy void
uu_avl_node_init(void * base,uu_avl_node_t * np,uu_avl_pool_t * pp)136eda14cbcSMatt Macy uu_avl_node_init(void *base, uu_avl_node_t *np, uu_avl_pool_t *pp)
137eda14cbcSMatt Macy {
138eda14cbcSMatt Macy uintptr_t *na = (uintptr_t *)np;
139eda14cbcSMatt Macy
140eda14cbcSMatt Macy if (pp->uap_debug) {
141eda14cbcSMatt Macy uintptr_t offset = (uintptr_t)np - (uintptr_t)base;
142eda14cbcSMatt Macy if (offset + sizeof (*np) > pp->uap_objsize) {
143eda14cbcSMatt Macy uu_panic("uu_avl_node_init(%p, %p, %p (\"%s\")): "
144eda14cbcSMatt Macy "offset %ld doesn't fit in object (size %ld)\n",
145eda14cbcSMatt Macy base, (void *)np, (void *)pp, pp->uap_name,
146eda14cbcSMatt Macy (long)offset, (long)pp->uap_objsize);
147eda14cbcSMatt Macy }
148eda14cbcSMatt Macy if (offset != pp->uap_nodeoffset) {
149eda14cbcSMatt Macy uu_panic("uu_avl_node_init(%p, %p, %p (\"%s\")): "
150eda14cbcSMatt Macy "offset %ld doesn't match pool's offset (%ld)\n",
151eda14cbcSMatt Macy base, (void *)np, (void *)pp, pp->uap_name,
152eda14cbcSMatt Macy (long)offset, (long)pp->uap_objsize);
153eda14cbcSMatt Macy }
154eda14cbcSMatt Macy }
155eda14cbcSMatt Macy
156eda14cbcSMatt Macy na[0] = POOL_TO_MARKER(pp);
157eda14cbcSMatt Macy na[1] = 0;
158eda14cbcSMatt Macy }
159eda14cbcSMatt Macy
160eda14cbcSMatt Macy void
uu_avl_node_fini(void * base,uu_avl_node_t * np,uu_avl_pool_t * pp)161eda14cbcSMatt Macy uu_avl_node_fini(void *base, uu_avl_node_t *np, uu_avl_pool_t *pp)
162eda14cbcSMatt Macy {
163eda14cbcSMatt Macy uintptr_t *na = (uintptr_t *)np;
164eda14cbcSMatt Macy
165eda14cbcSMatt Macy if (pp->uap_debug) {
166eda14cbcSMatt Macy if (na[0] == DEAD_MARKER && na[1] == DEAD_MARKER) {
167eda14cbcSMatt Macy uu_panic("uu_avl_node_fini(%p, %p, %p (\"%s\")): "
168eda14cbcSMatt Macy "node already finied\n",
169eda14cbcSMatt Macy base, (void *)np, (void *)pp, pp->uap_name);
170eda14cbcSMatt Macy }
171eda14cbcSMatt Macy if (na[0] != POOL_TO_MARKER(pp) || na[1] != 0) {
172eda14cbcSMatt Macy uu_panic("uu_avl_node_fini(%p, %p, %p (\"%s\")): "
173eda14cbcSMatt Macy "node corrupt, in tree, or in different pool\n",
174eda14cbcSMatt Macy base, (void *)np, (void *)pp, pp->uap_name);
175eda14cbcSMatt Macy }
176eda14cbcSMatt Macy }
177eda14cbcSMatt Macy
178eda14cbcSMatt Macy na[0] = DEAD_MARKER;
179eda14cbcSMatt Macy na[1] = DEAD_MARKER;
180eda14cbcSMatt Macy na[2] = DEAD_MARKER;
181eda14cbcSMatt Macy }
182eda14cbcSMatt Macy
183eda14cbcSMatt Macy struct uu_avl_node_compare_info {
184eda14cbcSMatt Macy uu_compare_fn_t *ac_compare;
185eda14cbcSMatt Macy void *ac_private;
186eda14cbcSMatt Macy void *ac_right;
187eda14cbcSMatt Macy void *ac_found;
188eda14cbcSMatt Macy };
189eda14cbcSMatt Macy
190eda14cbcSMatt Macy static int
uu_avl_node_compare(const void * l,const void * r)191eda14cbcSMatt Macy uu_avl_node_compare(const void *l, const void *r)
192eda14cbcSMatt Macy {
193eda14cbcSMatt Macy struct uu_avl_node_compare_info *info =
194eda14cbcSMatt Macy (struct uu_avl_node_compare_info *)l;
195eda14cbcSMatt Macy
196eda14cbcSMatt Macy int res = info->ac_compare(r, info->ac_right, info->ac_private);
197eda14cbcSMatt Macy
198eda14cbcSMatt Macy if (res == 0) {
199eda14cbcSMatt Macy if (info->ac_found == NULL)
200eda14cbcSMatt Macy info->ac_found = (void *)r;
201eda14cbcSMatt Macy return (-1);
202eda14cbcSMatt Macy }
203eda14cbcSMatt Macy if (res < 0)
204eda14cbcSMatt Macy return (1);
205eda14cbcSMatt Macy return (-1);
206eda14cbcSMatt Macy }
207eda14cbcSMatt Macy
208eda14cbcSMatt Macy uu_avl_t *
uu_avl_create(uu_avl_pool_t * pp,void * parent,uint32_t flags)209eda14cbcSMatt Macy uu_avl_create(uu_avl_pool_t *pp, void *parent, uint32_t flags)
210eda14cbcSMatt Macy {
211eda14cbcSMatt Macy uu_avl_t *ap, *next, *prev;
212eda14cbcSMatt Macy
213eda14cbcSMatt Macy if (flags & ~UU_AVL_DEBUG) {
214eda14cbcSMatt Macy uu_set_error(UU_ERROR_UNKNOWN_FLAG);
215eda14cbcSMatt Macy return (NULL);
216eda14cbcSMatt Macy }
217eda14cbcSMatt Macy
218eda14cbcSMatt Macy ap = uu_zalloc(sizeof (*ap));
219eda14cbcSMatt Macy if (ap == NULL) {
220eda14cbcSMatt Macy uu_set_error(UU_ERROR_NO_MEMORY);
221eda14cbcSMatt Macy return (NULL);
222eda14cbcSMatt Macy }
223eda14cbcSMatt Macy
224eda14cbcSMatt Macy ap->ua_pool = pp;
225*dbd5678dSMartin Matuska ap->ua_parent = parent;
226eda14cbcSMatt Macy ap->ua_debug = pp->uap_debug || (flags & UU_AVL_DEBUG);
227eda14cbcSMatt Macy ap->ua_index = (pp->uap_last_index = INDEX_NEXT(pp->uap_last_index));
228eda14cbcSMatt Macy
229eda14cbcSMatt Macy avl_create(&ap->ua_tree, &uu_avl_node_compare, pp->uap_objsize,
230eda14cbcSMatt Macy pp->uap_nodeoffset);
231eda14cbcSMatt Macy
232eda14cbcSMatt Macy ap->ua_null_walk.uaw_next = &ap->ua_null_walk;
233eda14cbcSMatt Macy ap->ua_null_walk.uaw_prev = &ap->ua_null_walk;
234eda14cbcSMatt Macy
235eda14cbcSMatt Macy (void) pthread_mutex_lock(&pp->uap_lock);
236eda14cbcSMatt Macy next = &pp->uap_null_avl;
237*dbd5678dSMartin Matuska prev = next->ua_prev;
238*dbd5678dSMartin Matuska ap->ua_next = next;
239*dbd5678dSMartin Matuska ap->ua_prev = prev;
240*dbd5678dSMartin Matuska next->ua_prev = ap;
241*dbd5678dSMartin Matuska prev->ua_next = ap;
242eda14cbcSMatt Macy (void) pthread_mutex_unlock(&pp->uap_lock);
243eda14cbcSMatt Macy
244eda14cbcSMatt Macy return (ap);
245eda14cbcSMatt Macy }
246eda14cbcSMatt Macy
247eda14cbcSMatt Macy void
uu_avl_destroy(uu_avl_t * ap)248eda14cbcSMatt Macy uu_avl_destroy(uu_avl_t *ap)
249eda14cbcSMatt Macy {
250eda14cbcSMatt Macy uu_avl_pool_t *pp = ap->ua_pool;
251eda14cbcSMatt Macy
252eda14cbcSMatt Macy if (ap->ua_debug) {
253eda14cbcSMatt Macy if (avl_numnodes(&ap->ua_tree) != 0) {
254eda14cbcSMatt Macy uu_panic("uu_avl_destroy(%p): tree not empty\n",
255eda14cbcSMatt Macy (void *)ap);
256eda14cbcSMatt Macy }
257eda14cbcSMatt Macy if (ap->ua_null_walk.uaw_next != &ap->ua_null_walk ||
258eda14cbcSMatt Macy ap->ua_null_walk.uaw_prev != &ap->ua_null_walk) {
259eda14cbcSMatt Macy uu_panic("uu_avl_destroy(%p): outstanding walkers\n",
260eda14cbcSMatt Macy (void *)ap);
261eda14cbcSMatt Macy }
262eda14cbcSMatt Macy }
263eda14cbcSMatt Macy (void) pthread_mutex_lock(&pp->uap_lock);
264*dbd5678dSMartin Matuska ap->ua_next->ua_prev = ap->ua_prev;
265*dbd5678dSMartin Matuska ap->ua_prev->ua_next = ap->ua_next;
266eda14cbcSMatt Macy (void) pthread_mutex_unlock(&pp->uap_lock);
267*dbd5678dSMartin Matuska ap->ua_prev = NULL;
268*dbd5678dSMartin Matuska ap->ua_next = NULL;
269eda14cbcSMatt Macy
270eda14cbcSMatt Macy ap->ua_pool = NULL;
271eda14cbcSMatt Macy avl_destroy(&ap->ua_tree);
272eda14cbcSMatt Macy
273eda14cbcSMatt Macy uu_free(ap);
274eda14cbcSMatt Macy }
275eda14cbcSMatt Macy
276eda14cbcSMatt Macy size_t
uu_avl_numnodes(uu_avl_t * ap)277eda14cbcSMatt Macy uu_avl_numnodes(uu_avl_t *ap)
278eda14cbcSMatt Macy {
279eda14cbcSMatt Macy return (avl_numnodes(&ap->ua_tree));
280eda14cbcSMatt Macy }
281eda14cbcSMatt Macy
282eda14cbcSMatt Macy void *
uu_avl_first(uu_avl_t * ap)283eda14cbcSMatt Macy uu_avl_first(uu_avl_t *ap)
284eda14cbcSMatt Macy {
285eda14cbcSMatt Macy return (avl_first(&ap->ua_tree));
286eda14cbcSMatt Macy }
287eda14cbcSMatt Macy
288eda14cbcSMatt Macy void *
uu_avl_last(uu_avl_t * ap)289eda14cbcSMatt Macy uu_avl_last(uu_avl_t *ap)
290eda14cbcSMatt Macy {
291eda14cbcSMatt Macy return (avl_last(&ap->ua_tree));
292eda14cbcSMatt Macy }
293eda14cbcSMatt Macy
294eda14cbcSMatt Macy void *
uu_avl_next(uu_avl_t * ap,void * node)295eda14cbcSMatt Macy uu_avl_next(uu_avl_t *ap, void *node)
296eda14cbcSMatt Macy {
297eda14cbcSMatt Macy return (AVL_NEXT(&ap->ua_tree, node));
298eda14cbcSMatt Macy }
299eda14cbcSMatt Macy
300eda14cbcSMatt Macy void *
uu_avl_prev(uu_avl_t * ap,void * node)301eda14cbcSMatt Macy uu_avl_prev(uu_avl_t *ap, void *node)
302eda14cbcSMatt Macy {
303eda14cbcSMatt Macy return (AVL_PREV(&ap->ua_tree, node));
304eda14cbcSMatt Macy }
305eda14cbcSMatt Macy
306eda14cbcSMatt Macy static void
_avl_walk_init(uu_avl_walk_t * wp,uu_avl_t * ap,uint32_t flags)307eda14cbcSMatt Macy _avl_walk_init(uu_avl_walk_t *wp, uu_avl_t *ap, uint32_t flags)
308eda14cbcSMatt Macy {
309eda14cbcSMatt Macy uu_avl_walk_t *next, *prev;
310eda14cbcSMatt Macy
311eda14cbcSMatt Macy int robust = (flags & UU_WALK_ROBUST);
312eda14cbcSMatt Macy int direction = (flags & UU_WALK_REVERSE)? -1 : 1;
313eda14cbcSMatt Macy
314eda14cbcSMatt Macy (void) memset(wp, 0, sizeof (*wp));
315eda14cbcSMatt Macy wp->uaw_avl = ap;
316eda14cbcSMatt Macy wp->uaw_robust = robust;
317eda14cbcSMatt Macy wp->uaw_dir = direction;
318eda14cbcSMatt Macy
319eda14cbcSMatt Macy if (direction > 0)
320eda14cbcSMatt Macy wp->uaw_next_result = avl_first(&ap->ua_tree);
321eda14cbcSMatt Macy else
322eda14cbcSMatt Macy wp->uaw_next_result = avl_last(&ap->ua_tree);
323eda14cbcSMatt Macy
324eda14cbcSMatt Macy if (ap->ua_debug || robust) {
325eda14cbcSMatt Macy wp->uaw_next = next = &ap->ua_null_walk;
326eda14cbcSMatt Macy wp->uaw_prev = prev = next->uaw_prev;
327eda14cbcSMatt Macy next->uaw_prev = wp;
328eda14cbcSMatt Macy prev->uaw_next = wp;
329eda14cbcSMatt Macy }
330eda14cbcSMatt Macy }
331eda14cbcSMatt Macy
332eda14cbcSMatt Macy static void *
_avl_walk_advance(uu_avl_walk_t * wp,uu_avl_t * ap)333eda14cbcSMatt Macy _avl_walk_advance(uu_avl_walk_t *wp, uu_avl_t *ap)
334eda14cbcSMatt Macy {
335eda14cbcSMatt Macy void *np = wp->uaw_next_result;
336eda14cbcSMatt Macy
337eda14cbcSMatt Macy avl_tree_t *t = &ap->ua_tree;
338eda14cbcSMatt Macy
339eda14cbcSMatt Macy if (np == NULL)
340eda14cbcSMatt Macy return (NULL);
341eda14cbcSMatt Macy
342eda14cbcSMatt Macy wp->uaw_next_result = (wp->uaw_dir > 0)? AVL_NEXT(t, np) :
343eda14cbcSMatt Macy AVL_PREV(t, np);
344eda14cbcSMatt Macy
345eda14cbcSMatt Macy return (np);
346eda14cbcSMatt Macy }
347eda14cbcSMatt Macy
348eda14cbcSMatt Macy static void
_avl_walk_fini(uu_avl_walk_t * wp)349eda14cbcSMatt Macy _avl_walk_fini(uu_avl_walk_t *wp)
350eda14cbcSMatt Macy {
351eda14cbcSMatt Macy if (wp->uaw_next != NULL) {
352eda14cbcSMatt Macy wp->uaw_next->uaw_prev = wp->uaw_prev;
353eda14cbcSMatt Macy wp->uaw_prev->uaw_next = wp->uaw_next;
354eda14cbcSMatt Macy wp->uaw_next = NULL;
355eda14cbcSMatt Macy wp->uaw_prev = NULL;
356eda14cbcSMatt Macy }
357eda14cbcSMatt Macy wp->uaw_avl = NULL;
358eda14cbcSMatt Macy wp->uaw_next_result = NULL;
359eda14cbcSMatt Macy }
360eda14cbcSMatt Macy
361eda14cbcSMatt Macy uu_avl_walk_t *
uu_avl_walk_start(uu_avl_t * ap,uint32_t flags)362eda14cbcSMatt Macy uu_avl_walk_start(uu_avl_t *ap, uint32_t flags)
363eda14cbcSMatt Macy {
364eda14cbcSMatt Macy uu_avl_walk_t *wp;
365eda14cbcSMatt Macy
366eda14cbcSMatt Macy if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) {
367eda14cbcSMatt Macy uu_set_error(UU_ERROR_UNKNOWN_FLAG);
368eda14cbcSMatt Macy return (NULL);
369eda14cbcSMatt Macy }
370eda14cbcSMatt Macy
371eda14cbcSMatt Macy wp = uu_zalloc(sizeof (*wp));
372eda14cbcSMatt Macy if (wp == NULL) {
373eda14cbcSMatt Macy uu_set_error(UU_ERROR_NO_MEMORY);
374eda14cbcSMatt Macy return (NULL);
375eda14cbcSMatt Macy }
376eda14cbcSMatt Macy
377eda14cbcSMatt Macy _avl_walk_init(wp, ap, flags);
378eda14cbcSMatt Macy return (wp);
379eda14cbcSMatt Macy }
380eda14cbcSMatt Macy
381eda14cbcSMatt Macy void *
uu_avl_walk_next(uu_avl_walk_t * wp)382eda14cbcSMatt Macy uu_avl_walk_next(uu_avl_walk_t *wp)
383eda14cbcSMatt Macy {
384eda14cbcSMatt Macy return (_avl_walk_advance(wp, wp->uaw_avl));
385eda14cbcSMatt Macy }
386eda14cbcSMatt Macy
387eda14cbcSMatt Macy void
uu_avl_walk_end(uu_avl_walk_t * wp)388eda14cbcSMatt Macy uu_avl_walk_end(uu_avl_walk_t *wp)
389eda14cbcSMatt Macy {
390eda14cbcSMatt Macy _avl_walk_fini(wp);
391eda14cbcSMatt Macy uu_free(wp);
392eda14cbcSMatt Macy }
393eda14cbcSMatt Macy
394eda14cbcSMatt Macy int
uu_avl_walk(uu_avl_t * ap,uu_walk_fn_t * func,void * private,uint32_t flags)395eda14cbcSMatt Macy uu_avl_walk(uu_avl_t *ap, uu_walk_fn_t *func, void *private, uint32_t flags)
396eda14cbcSMatt Macy {
397eda14cbcSMatt Macy void *e;
398eda14cbcSMatt Macy uu_avl_walk_t my_walk;
399eda14cbcSMatt Macy
400eda14cbcSMatt Macy int status = UU_WALK_NEXT;
401eda14cbcSMatt Macy
402eda14cbcSMatt Macy if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) {
403eda14cbcSMatt Macy uu_set_error(UU_ERROR_UNKNOWN_FLAG);
404eda14cbcSMatt Macy return (-1);
405eda14cbcSMatt Macy }
406eda14cbcSMatt Macy
407eda14cbcSMatt Macy _avl_walk_init(&my_walk, ap, flags);
408eda14cbcSMatt Macy while (status == UU_WALK_NEXT &&
409eda14cbcSMatt Macy (e = _avl_walk_advance(&my_walk, ap)) != NULL)
410eda14cbcSMatt Macy status = (*func)(e, private);
411eda14cbcSMatt Macy _avl_walk_fini(&my_walk);
412eda14cbcSMatt Macy
413eda14cbcSMatt Macy if (status >= 0)
414eda14cbcSMatt Macy return (0);
415eda14cbcSMatt Macy uu_set_error(UU_ERROR_CALLBACK_FAILED);
416eda14cbcSMatt Macy return (-1);
417eda14cbcSMatt Macy }
418eda14cbcSMatt Macy
419eda14cbcSMatt Macy void
uu_avl_remove(uu_avl_t * ap,void * elem)420eda14cbcSMatt Macy uu_avl_remove(uu_avl_t *ap, void *elem)
421eda14cbcSMatt Macy {
422eda14cbcSMatt Macy uu_avl_walk_t *wp;
423eda14cbcSMatt Macy uu_avl_pool_t *pp = ap->ua_pool;
424eda14cbcSMatt Macy uintptr_t *na = NODE_ARRAY(pp, elem);
425eda14cbcSMatt Macy
426eda14cbcSMatt Macy if (ap->ua_debug) {
427eda14cbcSMatt Macy /*
428eda14cbcSMatt Macy * invalidate outstanding uu_avl_index_ts.
429eda14cbcSMatt Macy */
430eda14cbcSMatt Macy ap->ua_index = INDEX_NEXT(ap->ua_index);
431eda14cbcSMatt Macy }
432eda14cbcSMatt Macy
433eda14cbcSMatt Macy /*
434eda14cbcSMatt Macy * Robust walkers most be advanced, if we are removing the node
435eda14cbcSMatt Macy * they are currently using. In debug mode, non-robust walkers
436eda14cbcSMatt Macy * are also on the walker list.
437eda14cbcSMatt Macy */
438eda14cbcSMatt Macy for (wp = ap->ua_null_walk.uaw_next; wp != &ap->ua_null_walk;
439eda14cbcSMatt Macy wp = wp->uaw_next) {
440eda14cbcSMatt Macy if (wp->uaw_robust) {
441eda14cbcSMatt Macy if (elem == wp->uaw_next_result)
442eda14cbcSMatt Macy (void) _avl_walk_advance(wp, ap);
443eda14cbcSMatt Macy } else if (wp->uaw_next_result != NULL) {
444eda14cbcSMatt Macy uu_panic("uu_avl_remove(%p, %p): active non-robust "
445eda14cbcSMatt Macy "walker\n", (void *)ap, elem);
446eda14cbcSMatt Macy }
447eda14cbcSMatt Macy }
448eda14cbcSMatt Macy
449eda14cbcSMatt Macy avl_remove(&ap->ua_tree, elem);
450eda14cbcSMatt Macy
451eda14cbcSMatt Macy na[0] = POOL_TO_MARKER(pp);
452eda14cbcSMatt Macy na[1] = 0;
453eda14cbcSMatt Macy }
454eda14cbcSMatt Macy
455eda14cbcSMatt Macy void *
uu_avl_teardown(uu_avl_t * ap,void ** cookie)456eda14cbcSMatt Macy uu_avl_teardown(uu_avl_t *ap, void **cookie)
457eda14cbcSMatt Macy {
458eda14cbcSMatt Macy void *elem = avl_destroy_nodes(&ap->ua_tree, cookie);
459eda14cbcSMatt Macy
460eda14cbcSMatt Macy if (elem != NULL) {
461eda14cbcSMatt Macy uu_avl_pool_t *pp = ap->ua_pool;
462eda14cbcSMatt Macy uintptr_t *na = NODE_ARRAY(pp, elem);
463eda14cbcSMatt Macy
464eda14cbcSMatt Macy na[0] = POOL_TO_MARKER(pp);
465eda14cbcSMatt Macy na[1] = 0;
466eda14cbcSMatt Macy }
467eda14cbcSMatt Macy return (elem);
468eda14cbcSMatt Macy }
469eda14cbcSMatt Macy
470eda14cbcSMatt Macy void *
uu_avl_find(uu_avl_t * ap,void * elem,void * private,uu_avl_index_t * out)471eda14cbcSMatt Macy uu_avl_find(uu_avl_t *ap, void *elem, void *private, uu_avl_index_t *out)
472eda14cbcSMatt Macy {
473eda14cbcSMatt Macy struct uu_avl_node_compare_info info;
474eda14cbcSMatt Macy void *result;
475eda14cbcSMatt Macy
476eda14cbcSMatt Macy info.ac_compare = ap->ua_pool->uap_cmp;
477eda14cbcSMatt Macy info.ac_private = private;
478eda14cbcSMatt Macy info.ac_right = elem;
479eda14cbcSMatt Macy info.ac_found = NULL;
480eda14cbcSMatt Macy
481eda14cbcSMatt Macy result = avl_find(&ap->ua_tree, &info, out);
482eda14cbcSMatt Macy if (out != NULL)
483eda14cbcSMatt Macy *out = INDEX_ENCODE(ap, *out);
484eda14cbcSMatt Macy
485eda14cbcSMatt Macy if (ap->ua_debug && result != NULL)
486eda14cbcSMatt Macy uu_panic("uu_avl_find: internal error: avl_find succeeded\n");
487eda14cbcSMatt Macy
488eda14cbcSMatt Macy return (info.ac_found);
489eda14cbcSMatt Macy }
490eda14cbcSMatt Macy
491eda14cbcSMatt Macy void
uu_avl_insert(uu_avl_t * ap,void * elem,uu_avl_index_t idx)492eda14cbcSMatt Macy uu_avl_insert(uu_avl_t *ap, void *elem, uu_avl_index_t idx)
493eda14cbcSMatt Macy {
494eda14cbcSMatt Macy if (ap->ua_debug) {
495eda14cbcSMatt Macy uu_avl_pool_t *pp = ap->ua_pool;
496eda14cbcSMatt Macy uintptr_t *na = NODE_ARRAY(pp, elem);
497eda14cbcSMatt Macy
498eda14cbcSMatt Macy if (na[1] != 0)
499eda14cbcSMatt Macy uu_panic("uu_avl_insert(%p, %p, %p): node already "
500eda14cbcSMatt Macy "in tree, or corrupt\n",
501eda14cbcSMatt Macy (void *)ap, elem, (void *)idx);
502eda14cbcSMatt Macy if (na[0] == 0)
503eda14cbcSMatt Macy uu_panic("uu_avl_insert(%p, %p, %p): node not "
504eda14cbcSMatt Macy "initialized\n",
505eda14cbcSMatt Macy (void *)ap, elem, (void *)idx);
506eda14cbcSMatt Macy if (na[0] != POOL_TO_MARKER(pp))
507eda14cbcSMatt Macy uu_panic("uu_avl_insert(%p, %p, %p): node from "
508eda14cbcSMatt Macy "other pool, or corrupt\n",
509eda14cbcSMatt Macy (void *)ap, elem, (void *)idx);
510eda14cbcSMatt Macy
511eda14cbcSMatt Macy if (!INDEX_VALID(ap, idx))
512eda14cbcSMatt Macy uu_panic("uu_avl_insert(%p, %p, %p): %s\n",
513eda14cbcSMatt Macy (void *)ap, elem, (void *)idx,
514eda14cbcSMatt Macy INDEX_CHECK(idx)? "outdated index" :
515eda14cbcSMatt Macy "invalid index");
516eda14cbcSMatt Macy
517eda14cbcSMatt Macy /*
518eda14cbcSMatt Macy * invalidate outstanding uu_avl_index_ts.
519eda14cbcSMatt Macy */
520eda14cbcSMatt Macy ap->ua_index = INDEX_NEXT(ap->ua_index);
521eda14cbcSMatt Macy }
522eda14cbcSMatt Macy avl_insert(&ap->ua_tree, elem, INDEX_DECODE(idx));
523eda14cbcSMatt Macy }
524eda14cbcSMatt Macy
525eda14cbcSMatt Macy void *
uu_avl_nearest_next(uu_avl_t * ap,uu_avl_index_t idx)526eda14cbcSMatt Macy uu_avl_nearest_next(uu_avl_t *ap, uu_avl_index_t idx)
527eda14cbcSMatt Macy {
528eda14cbcSMatt Macy if (ap->ua_debug && !INDEX_VALID(ap, idx))
529eda14cbcSMatt Macy uu_panic("uu_avl_nearest_next(%p, %p): %s\n",
530eda14cbcSMatt Macy (void *)ap, (void *)idx, INDEX_CHECK(idx)?
531eda14cbcSMatt Macy "outdated index" : "invalid index");
532eda14cbcSMatt Macy return (avl_nearest(&ap->ua_tree, INDEX_DECODE(idx), AVL_AFTER));
533eda14cbcSMatt Macy }
534eda14cbcSMatt Macy
535eda14cbcSMatt Macy void *
uu_avl_nearest_prev(uu_avl_t * ap,uu_avl_index_t idx)536eda14cbcSMatt Macy uu_avl_nearest_prev(uu_avl_t *ap, uu_avl_index_t idx)
537eda14cbcSMatt Macy {
538eda14cbcSMatt Macy if (ap->ua_debug && !INDEX_VALID(ap, idx))
539eda14cbcSMatt Macy uu_panic("uu_avl_nearest_prev(%p, %p): %s\n",
540eda14cbcSMatt Macy (void *)ap, (void *)idx, INDEX_CHECK(idx)?
541eda14cbcSMatt Macy "outdated index" : "invalid index");
542eda14cbcSMatt Macy return (avl_nearest(&ap->ua_tree, INDEX_DECODE(idx), AVL_BEFORE));
543eda14cbcSMatt Macy }
544eda14cbcSMatt Macy
545eda14cbcSMatt Macy /*
546eda14cbcSMatt Macy * called from uu_lockup() and uu_release(), as part of our fork1()-safety.
547eda14cbcSMatt Macy */
548eda14cbcSMatt Macy void
uu_avl_lockup(void)549eda14cbcSMatt Macy uu_avl_lockup(void)
550eda14cbcSMatt Macy {
551eda14cbcSMatt Macy uu_avl_pool_t *pp;
552eda14cbcSMatt Macy
553eda14cbcSMatt Macy (void) pthread_mutex_lock(&uu_apool_list_lock);
554eda14cbcSMatt Macy for (pp = uu_null_apool.uap_next; pp != &uu_null_apool;
555eda14cbcSMatt Macy pp = pp->uap_next)
556eda14cbcSMatt Macy (void) pthread_mutex_lock(&pp->uap_lock);
557eda14cbcSMatt Macy }
558eda14cbcSMatt Macy
559eda14cbcSMatt Macy void
uu_avl_release(void)560eda14cbcSMatt Macy uu_avl_release(void)
561eda14cbcSMatt Macy {
562eda14cbcSMatt Macy uu_avl_pool_t *pp;
563eda14cbcSMatt Macy
564eda14cbcSMatt Macy for (pp = uu_null_apool.uap_next; pp != &uu_null_apool;
565eda14cbcSMatt Macy pp = pp->uap_next)
566eda14cbcSMatt Macy (void) pthread_mutex_unlock(&pp->uap_lock);
567eda14cbcSMatt Macy (void) pthread_mutex_unlock(&uu_apool_list_lock);
568eda14cbcSMatt Macy }
569