1 /*
2  * CDDL HEADER START
3  *
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.
7  *
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.
12  *
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]
18  *
19  * CDDL HEADER END
20  */
21 
22 /*
23  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
24  * Use is subject to license terms.
25  *
26  * Copyright 2011 Jason King.  All rights reserved.
27  */
28 
29 #include "libuutil_common.h"
30 
31 #include <stdlib.h>
32 #include <string.h>
33 #include <unistd.h>
34 #include <sys/time.h>
35 
36 #define	ELEM_TO_NODE(lp, e) \
37 	((uu_list_node_impl_t *)((uintptr_t)(e) + (lp)->ul_offset))
38 
39 #define	NODE_TO_ELEM(lp, n) \
40 	((void *)((uintptr_t)(n) - (lp)->ul_offset))
41 
42 /*
43  * uu_list_index_ts define a location for insertion.  They are simply a
44  * pointer to the object after the insertion point.  We store a mark
45  * in the low-bits of the index, to help prevent mistakes.
46  *
47  * When debugging, the index mark changes on every insert and delete, to
48  * catch stale references.
49  */
50 #define	INDEX_MAX		(sizeof (uintptr_t) - 1)
51 #define	INDEX_NEXT(m)		(((m) == INDEX_MAX)? 1 : ((m) + 1) & INDEX_MAX)
52 
53 #define	INDEX_TO_NODE(i)	((uu_list_node_impl_t *)((i) & ~INDEX_MAX))
54 #define	NODE_TO_INDEX(p, n)	(((uintptr_t)(n) & ~INDEX_MAX) | (p)->ul_index)
55 #define	INDEX_VALID(p, i)	(((i) & INDEX_MAX) == (p)->ul_index)
56 #define	INDEX_CHECK(i)		(((i) & INDEX_MAX) != 0)
57 
58 #define	POOL_TO_MARKER(pp) ((void *)((uintptr_t)(pp) | 1))
59 
60 static uu_list_pool_t	uu_null_lpool = { &uu_null_lpool, &uu_null_lpool };
61 static pthread_mutex_t	uu_lpool_list_lock = PTHREAD_MUTEX_INITIALIZER;
62 
63 uu_list_pool_t *
uu_list_pool_create(const char * name,size_t objsize,size_t nodeoffset,uu_compare_fn_t * compare_func,uint32_t flags)64 uu_list_pool_create(const char *name, size_t objsize,
65     size_t nodeoffset, uu_compare_fn_t *compare_func, uint32_t flags)
66 {
67 	uu_list_pool_t *pp, *next, *prev;
68 
69 	if (name == NULL ||
70 	    uu_check_name(name, UU_NAME_DOMAIN) == -1 ||
71 	    nodeoffset + sizeof (uu_list_node_t) > objsize) {
72 		uu_set_error(UU_ERROR_INVALID_ARGUMENT);
73 		return (NULL);
74 	}
75 
76 	if (flags & ~UU_LIST_POOL_DEBUG) {
77 		uu_set_error(UU_ERROR_UNKNOWN_FLAG);
78 		return (NULL);
79 	}
80 
81 	pp = uu_zalloc(sizeof (uu_list_pool_t));
82 	if (pp == NULL) {
83 		uu_set_error(UU_ERROR_NO_MEMORY);
84 		return (NULL);
85 	}
86 
87 	(void) strlcpy(pp->ulp_name, name, sizeof (pp->ulp_name));
88 	pp->ulp_nodeoffset = nodeoffset;
89 	pp->ulp_objsize = objsize;
90 	pp->ulp_cmp = compare_func;
91 	if (flags & UU_LIST_POOL_DEBUG)
92 		pp->ulp_debug = 1;
93 	pp->ulp_last_index = 0;
94 
95 	(void) pthread_mutex_init(&pp->ulp_lock, NULL);
96 
97 	pp->ulp_null_list.ul_next_enc = UU_PTR_ENCODE(&pp->ulp_null_list);
98 	pp->ulp_null_list.ul_prev_enc = UU_PTR_ENCODE(&pp->ulp_null_list);
99 
100 	(void) pthread_mutex_lock(&uu_lpool_list_lock);
101 	pp->ulp_next = next = &uu_null_lpool;
102 	pp->ulp_prev = prev = next->ulp_prev;
103 	next->ulp_prev = pp;
104 	prev->ulp_next = pp;
105 	(void) pthread_mutex_unlock(&uu_lpool_list_lock);
106 
107 	return (pp);
108 }
109 
110 void
uu_list_pool_destroy(uu_list_pool_t * pp)111 uu_list_pool_destroy(uu_list_pool_t *pp)
112 {
113 	if (pp->ulp_debug) {
114 		if (pp->ulp_null_list.ul_next_enc !=
115 		    UU_PTR_ENCODE(&pp->ulp_null_list) ||
116 		    pp->ulp_null_list.ul_prev_enc !=
117 		    UU_PTR_ENCODE(&pp->ulp_null_list)) {
118 			uu_panic("uu_list_pool_destroy: Pool \"%.*s\" (%p) has "
119 			    "outstanding lists, or is corrupt.\n",
120 			    (int)sizeof (pp->ulp_name), pp->ulp_name,
121 			    (void *)pp);
122 		}
123 	}
124 	(void) pthread_mutex_lock(&uu_lpool_list_lock);
125 	pp->ulp_next->ulp_prev = pp->ulp_prev;
126 	pp->ulp_prev->ulp_next = pp->ulp_next;
127 	(void) pthread_mutex_unlock(&uu_lpool_list_lock);
128 	pp->ulp_prev = NULL;
129 	pp->ulp_next = NULL;
130 	uu_free(pp);
131 }
132 
133 void
uu_list_node_init(void * base,uu_list_node_t * np_arg,uu_list_pool_t * pp)134 uu_list_node_init(void *base, uu_list_node_t *np_arg, uu_list_pool_t *pp)
135 {
136 	uu_list_node_impl_t *np = (uu_list_node_impl_t *)np_arg;
137 
138 	if (pp->ulp_debug) {
139 		uintptr_t offset = (uintptr_t)np - (uintptr_t)base;
140 		if (offset + sizeof (*np) > pp->ulp_objsize) {
141 			uu_panic("uu_list_node_init(%p, %p, %p (\"%s\")): "
142 			    "offset %ld doesn't fit in object (size %ld)\n",
143 			    base, (void *)np, (void *)pp, pp->ulp_name,
144 			    (long)offset, (long)pp->ulp_objsize);
145 		}
146 		if (offset != pp->ulp_nodeoffset) {
147 			uu_panic("uu_list_node_init(%p, %p, %p (\"%s\")): "
148 			    "offset %ld doesn't match pool's offset (%ld)\n",
149 			    base, (void *)np, (void *)pp, pp->ulp_name,
150 			    (long)offset, (long)pp->ulp_objsize);
151 		}
152 	}
153 	np->uln_next = POOL_TO_MARKER(pp);
154 	np->uln_prev = NULL;
155 }
156 
157 void
uu_list_node_fini(void * base,uu_list_node_t * np_arg,uu_list_pool_t * pp)158 uu_list_node_fini(void *base, uu_list_node_t *np_arg, uu_list_pool_t *pp)
159 {
160 	uu_list_node_impl_t *np = (uu_list_node_impl_t *)np_arg;
161 
162 	if (pp->ulp_debug) {
163 		if (np->uln_next == NULL &&
164 		    np->uln_prev == NULL) {
165 			uu_panic("uu_list_node_fini(%p, %p, %p (\"%s\")): "
166 			    "node already finied\n",
167 			    base, (void *)np_arg, (void *)pp, pp->ulp_name);
168 		}
169 		if (np->uln_next != POOL_TO_MARKER(pp) ||
170 		    np->uln_prev != NULL) {
171 			uu_panic("uu_list_node_fini(%p, %p, %p (\"%s\")): "
172 			    "node corrupt or on list\n",
173 			    base, (void *)np_arg, (void *)pp, pp->ulp_name);
174 		}
175 	}
176 	np->uln_next = NULL;
177 	np->uln_prev = NULL;
178 }
179 
180 uu_list_t *
uu_list_create(uu_list_pool_t * pp,void * parent,uint32_t flags)181 uu_list_create(uu_list_pool_t *pp, void *parent, uint32_t flags)
182 {
183 	uu_list_t *lp, *next, *prev;
184 
185 	if (flags & ~(UU_LIST_DEBUG | UU_LIST_SORTED)) {
186 		uu_set_error(UU_ERROR_UNKNOWN_FLAG);
187 		return (NULL);
188 	}
189 
190 	if ((flags & UU_LIST_SORTED) && pp->ulp_cmp == NULL) {
191 		if (pp->ulp_debug)
192 			uu_panic("uu_list_create(%p, ...): requested "
193 			    "UU_LIST_SORTED, but pool has no comparison func\n",
194 			    (void *)pp);
195 		uu_set_error(UU_ERROR_NOT_SUPPORTED);
196 		return (NULL);
197 	}
198 
199 	lp = uu_zalloc(sizeof (*lp));
200 	if (lp == NULL) {
201 		uu_set_error(UU_ERROR_NO_MEMORY);
202 		return (NULL);
203 	}
204 
205 	lp->ul_pool = pp;
206 	lp->ul_parent_enc = UU_PTR_ENCODE(parent);
207 	lp->ul_offset = pp->ulp_nodeoffset;
208 	lp->ul_debug = pp->ulp_debug || (flags & UU_LIST_DEBUG);
209 	lp->ul_sorted = (flags & UU_LIST_SORTED);
210 	lp->ul_numnodes = 0;
211 	lp->ul_index = (pp->ulp_last_index = INDEX_NEXT(pp->ulp_last_index));
212 
213 	lp->ul_null_node.uln_next = &lp->ul_null_node;
214 	lp->ul_null_node.uln_prev = &lp->ul_null_node;
215 
216 	lp->ul_null_walk.ulw_next = &lp->ul_null_walk;
217 	lp->ul_null_walk.ulw_prev = &lp->ul_null_walk;
218 
219 	(void) pthread_mutex_lock(&pp->ulp_lock);
220 	next = &pp->ulp_null_list;
221 	prev = UU_PTR_DECODE(next->ul_prev_enc);
222 	lp->ul_next_enc = UU_PTR_ENCODE(next);
223 	lp->ul_prev_enc = UU_PTR_ENCODE(prev);
224 	next->ul_prev_enc = UU_PTR_ENCODE(lp);
225 	prev->ul_next_enc = UU_PTR_ENCODE(lp);
226 	(void) pthread_mutex_unlock(&pp->ulp_lock);
227 
228 	return (lp);
229 }
230 
231 void
uu_list_destroy(uu_list_t * lp)232 uu_list_destroy(uu_list_t *lp)
233 {
234 	uu_list_pool_t *pp = lp->ul_pool;
235 
236 	if (lp->ul_debug) {
237 		if (lp->ul_null_node.uln_next != &lp->ul_null_node ||
238 		    lp->ul_null_node.uln_prev != &lp->ul_null_node) {
239 			uu_panic("uu_list_destroy(%p):  list not empty\n",
240 			    (void *)lp);
241 		}
242 		if (lp->ul_numnodes != 0) {
243 			uu_panic("uu_list_destroy(%p):  numnodes is nonzero, "
244 			    "but list is empty\n", (void *)lp);
245 		}
246 		if (lp->ul_null_walk.ulw_next != &lp->ul_null_walk ||
247 		    lp->ul_null_walk.ulw_prev != &lp->ul_null_walk) {
248 			uu_panic("uu_list_destroy(%p):  outstanding walkers\n",
249 			    (void *)lp);
250 		}
251 	}
252 
253 	(void) pthread_mutex_lock(&pp->ulp_lock);
254 	UU_LIST_PTR(lp->ul_next_enc)->ul_prev_enc = lp->ul_prev_enc;
255 	UU_LIST_PTR(lp->ul_prev_enc)->ul_next_enc = lp->ul_next_enc;
256 	(void) pthread_mutex_unlock(&pp->ulp_lock);
257 	lp->ul_prev_enc = UU_PTR_ENCODE(NULL);
258 	lp->ul_next_enc = UU_PTR_ENCODE(NULL);
259 	lp->ul_pool = NULL;
260 	uu_free(lp);
261 }
262 
263 static void
list_insert(uu_list_t * lp,uu_list_node_impl_t * np,uu_list_node_impl_t * prev,uu_list_node_impl_t * next)264 list_insert(uu_list_t *lp, uu_list_node_impl_t *np, uu_list_node_impl_t *prev,
265     uu_list_node_impl_t *next)
266 {
267 	if (lp->ul_debug) {
268 		if (next->uln_prev != prev || prev->uln_next != next)
269 			uu_panic("insert(%p): internal error: %p and %p not "
270 			    "neighbors\n", (void *)lp, (void *)next,
271 			    (void *)prev);
272 
273 		if (np->uln_next != POOL_TO_MARKER(lp->ul_pool) ||
274 		    np->uln_prev != NULL) {
275 			uu_panic("insert(%p): elem %p node %p corrupt, "
276 			    "not initialized, or already in a list.\n",
277 			    (void *)lp, NODE_TO_ELEM(lp, np), (void *)np);
278 		}
279 		/*
280 		 * invalidate outstanding uu_list_index_ts.
281 		 */
282 		lp->ul_index = INDEX_NEXT(lp->ul_index);
283 	}
284 	np->uln_next = next;
285 	np->uln_prev = prev;
286 	next->uln_prev = np;
287 	prev->uln_next = np;
288 
289 	lp->ul_numnodes++;
290 }
291 
292 void
uu_list_insert(uu_list_t * lp,void * elem,uu_list_index_t idx)293 uu_list_insert(uu_list_t *lp, void *elem, uu_list_index_t idx)
294 {
295 	uu_list_node_impl_t *np;
296 
297 	np = INDEX_TO_NODE(idx);
298 	if (np == NULL)
299 		np = &lp->ul_null_node;
300 
301 	if (lp->ul_debug) {
302 		if (!INDEX_VALID(lp, idx))
303 			uu_panic("uu_list_insert(%p, %p, %p): %s\n",
304 			    (void *)lp, elem, (void *)idx,
305 			    INDEX_CHECK(idx)? "outdated index" :
306 			    "invalid index");
307 		if (np->uln_prev == NULL)
308 			uu_panic("uu_list_insert(%p, %p, %p): out-of-date "
309 			    "index\n", (void *)lp, elem, (void *)idx);
310 	}
311 
312 	list_insert(lp, ELEM_TO_NODE(lp, elem), np->uln_prev, np);
313 }
314 
315 void *
uu_list_find(uu_list_t * lp,void * elem,void * private,uu_list_index_t * out)316 uu_list_find(uu_list_t *lp, void *elem, void *private, uu_list_index_t *out)
317 {
318 	int sorted = lp->ul_sorted;
319 	uu_compare_fn_t *func = lp->ul_pool->ulp_cmp;
320 	uu_list_node_impl_t *np;
321 
322 	uu_set_error(UU_ERROR_NONE);
323 
324 	if (func == NULL) {
325 		if (out != NULL)
326 			*out = 0;
327 		uu_set_error(UU_ERROR_NOT_SUPPORTED);
328 		return (NULL);
329 	}
330 	for (np = lp->ul_null_node.uln_next; np != &lp->ul_null_node;
331 	    np = np->uln_next) {
332 		void *ep = NODE_TO_ELEM(lp, np);
333 		int cmp = func(ep, elem, private);
334 		if (cmp == 0) {
335 			if (out != NULL)
336 				*out = NODE_TO_INDEX(lp, np);
337 			return (ep);
338 		}
339 		if (sorted && cmp > 0) {
340 			if (out != NULL)
341 				*out = NODE_TO_INDEX(lp, np);
342 			return (NULL);
343 		}
344 	}
345 	if (out != NULL)
346 		*out = NODE_TO_INDEX(lp, 0);
347 	return (NULL);
348 }
349 
350 void *
uu_list_nearest_next(uu_list_t * lp,uu_list_index_t idx)351 uu_list_nearest_next(uu_list_t *lp, uu_list_index_t idx)
352 {
353 	uu_list_node_impl_t *np = INDEX_TO_NODE(idx);
354 
355 	if (np == NULL)
356 		np = &lp->ul_null_node;
357 
358 	if (lp->ul_debug) {
359 		if (!INDEX_VALID(lp, idx))
360 			uu_panic("uu_list_nearest_next(%p, %p): %s\n",
361 			    (void *)lp, (void *)idx,
362 			    INDEX_CHECK(idx)? "outdated index" :
363 			    "invalid index");
364 		if (np->uln_prev == NULL)
365 			uu_panic("uu_list_nearest_next(%p, %p): out-of-date "
366 			    "index\n", (void *)lp, (void *)idx);
367 	}
368 
369 	if (np == &lp->ul_null_node)
370 		return (NULL);
371 	else
372 		return (NODE_TO_ELEM(lp, np));
373 }
374 
375 void *
uu_list_nearest_prev(uu_list_t * lp,uu_list_index_t idx)376 uu_list_nearest_prev(uu_list_t *lp, uu_list_index_t idx)
377 {
378 	uu_list_node_impl_t *np = INDEX_TO_NODE(idx);
379 
380 	if (np == NULL)
381 		np = &lp->ul_null_node;
382 
383 	if (lp->ul_debug) {
384 		if (!INDEX_VALID(lp, idx))
385 			uu_panic("uu_list_nearest_prev(%p, %p): %s\n",
386 			    (void *)lp, (void *)idx, INDEX_CHECK(idx)?
387 			    "outdated index" : "invalid index");
388 		if (np->uln_prev == NULL)
389 			uu_panic("uu_list_nearest_prev(%p, %p): out-of-date "
390 			    "index\n", (void *)lp, (void *)idx);
391 	}
392 
393 	if ((np = np->uln_prev) == &lp->ul_null_node)
394 		return (NULL);
395 	else
396 		return (NODE_TO_ELEM(lp, np));
397 }
398 
399 static void
list_walk_init(uu_list_walk_t * wp,uu_list_t * lp,uint32_t flags)400 list_walk_init(uu_list_walk_t *wp, uu_list_t *lp, uint32_t flags)
401 {
402 	uu_list_walk_t *next, *prev;
403 
404 	int robust = (flags & UU_WALK_ROBUST);
405 	int direction = (flags & UU_WALK_REVERSE)? -1 : 1;
406 
407 	(void) memset(wp, 0, sizeof (*wp));
408 	wp->ulw_list = lp;
409 	wp->ulw_robust = robust;
410 	wp->ulw_dir = direction;
411 	if (direction > 0)
412 		wp->ulw_next_result = lp->ul_null_node.uln_next;
413 	else
414 		wp->ulw_next_result = lp->ul_null_node.uln_prev;
415 
416 	if (lp->ul_debug || robust) {
417 		/*
418 		 * Add this walker to the list's list of walkers so
419 		 * uu_list_remove() can advance us if somebody tries to
420 		 * remove ulw_next_result.
421 		 */
422 		wp->ulw_next = next = &lp->ul_null_walk;
423 		wp->ulw_prev = prev = next->ulw_prev;
424 		next->ulw_prev = wp;
425 		prev->ulw_next = wp;
426 	}
427 }
428 
429 static uu_list_node_impl_t *
list_walk_advance(uu_list_walk_t * wp,uu_list_t * lp)430 list_walk_advance(uu_list_walk_t *wp, uu_list_t *lp)
431 {
432 	uu_list_node_impl_t *np = wp->ulw_next_result;
433 	uu_list_node_impl_t *next;
434 
435 	if (np == &lp->ul_null_node)
436 		return (NULL);
437 
438 	next = (wp->ulw_dir > 0)? np->uln_next : np->uln_prev;
439 
440 	wp->ulw_next_result = next;
441 	return (np);
442 }
443 
444 static void
list_walk_fini(uu_list_walk_t * wp)445 list_walk_fini(uu_list_walk_t *wp)
446 {
447 	/* GLXXX debugging? */
448 	if (wp->ulw_next != NULL) {
449 		wp->ulw_next->ulw_prev = wp->ulw_prev;
450 		wp->ulw_prev->ulw_next = wp->ulw_next;
451 		wp->ulw_next = NULL;
452 		wp->ulw_prev = NULL;
453 	}
454 	wp->ulw_list = NULL;
455 	wp->ulw_next_result = NULL;
456 }
457 
458 uu_list_walk_t *
uu_list_walk_start(uu_list_t * lp,uint32_t flags)459 uu_list_walk_start(uu_list_t *lp, uint32_t flags)
460 {
461 	uu_list_walk_t *wp;
462 
463 	if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) {
464 		uu_set_error(UU_ERROR_UNKNOWN_FLAG);
465 		return (NULL);
466 	}
467 
468 	wp = uu_zalloc(sizeof (*wp));
469 	if (wp == NULL) {
470 		uu_set_error(UU_ERROR_NO_MEMORY);
471 		return (NULL);
472 	}
473 
474 	list_walk_init(wp, lp, flags);
475 	return (wp);
476 }
477 
478 void *
uu_list_walk_next(uu_list_walk_t * wp)479 uu_list_walk_next(uu_list_walk_t *wp)
480 {
481 	uu_list_t *lp = wp->ulw_list;
482 	uu_list_node_impl_t *np = list_walk_advance(wp, lp);
483 
484 	if (np == NULL)
485 		return (NULL);
486 
487 	return (NODE_TO_ELEM(lp, np));
488 }
489 
490 void
uu_list_walk_end(uu_list_walk_t * wp)491 uu_list_walk_end(uu_list_walk_t *wp)
492 {
493 	list_walk_fini(wp);
494 	uu_free(wp);
495 }
496 
497 int
uu_list_walk(uu_list_t * lp,uu_walk_fn_t * func,void * private,uint32_t flags)498 uu_list_walk(uu_list_t *lp, uu_walk_fn_t *func, void *private, uint32_t flags)
499 {
500 	uu_list_node_impl_t *np;
501 
502 	int status = UU_WALK_NEXT;
503 
504 	int robust = (flags & UU_WALK_ROBUST);
505 	int reverse = (flags & UU_WALK_REVERSE);
506 
507 	if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) {
508 		uu_set_error(UU_ERROR_UNKNOWN_FLAG);
509 		return (-1);
510 	}
511 
512 	if (lp->ul_debug || robust) {
513 		uu_list_walk_t my_walk;
514 		void *e;
515 
516 		list_walk_init(&my_walk, lp, flags);
517 		while (status == UU_WALK_NEXT &&
518 		    (e = uu_list_walk_next(&my_walk)) != NULL)
519 			status = (*func)(e, private);
520 		list_walk_fini(&my_walk);
521 	} else {
522 		if (!reverse) {
523 			for (np = lp->ul_null_node.uln_next;
524 			    status == UU_WALK_NEXT && np != &lp->ul_null_node;
525 			    np = np->uln_next) {
526 				status = (*func)(NODE_TO_ELEM(lp, np), private);
527 			}
528 		} else {
529 			for (np = lp->ul_null_node.uln_prev;
530 			    status == UU_WALK_NEXT && np != &lp->ul_null_node;
531 			    np = np->uln_prev) {
532 				status = (*func)(NODE_TO_ELEM(lp, np), private);
533 			}
534 		}
535 	}
536 	if (status >= 0)
537 		return (0);
538 	uu_set_error(UU_ERROR_CALLBACK_FAILED);
539 	return (-1);
540 }
541 
542 void
uu_list_remove(uu_list_t * lp,void * elem)543 uu_list_remove(uu_list_t *lp, void *elem)
544 {
545 	uu_list_node_impl_t *np = ELEM_TO_NODE(lp, elem);
546 	uu_list_walk_t *wp;
547 
548 	if (lp->ul_debug) {
549 		if (np->uln_prev == NULL)
550 			uu_panic("uu_list_remove(%p, %p): elem not on list\n",
551 			    (void *)lp, elem);
552 		/*
553 		 * invalidate outstanding uu_list_index_ts.
554 		 */
555 		lp->ul_index = INDEX_NEXT(lp->ul_index);
556 	}
557 
558 	/*
559 	 * robust walkers must be advanced.  In debug mode, non-robust
560 	 * walkers are also on the list.  If there are any, it's an error.
561 	 */
562 	for (wp = lp->ul_null_walk.ulw_next; wp != &lp->ul_null_walk;
563 	    wp = wp->ulw_next) {
564 		if (wp->ulw_robust) {
565 			if (np == wp->ulw_next_result)
566 				(void) list_walk_advance(wp, lp);
567 		} else if (wp->ulw_next_result != NULL) {
568 			uu_panic("uu_list_remove(%p, %p): active non-robust "
569 			    "walker\n", (void *)lp, elem);
570 		}
571 	}
572 
573 	np->uln_next->uln_prev = np->uln_prev;
574 	np->uln_prev->uln_next = np->uln_next;
575 
576 	lp->ul_numnodes--;
577 
578 	np->uln_next = POOL_TO_MARKER(lp->ul_pool);
579 	np->uln_prev = NULL;
580 }
581 
582 void *
uu_list_teardown(uu_list_t * lp,void ** cookie)583 uu_list_teardown(uu_list_t *lp, void **cookie)
584 {
585 	void *ep;
586 
587 	/*
588 	 * XXX: disable list modification until list is empty
589 	 */
590 	if (lp->ul_debug && *cookie != NULL)
591 		uu_panic("uu_list_teardown(%p, %p): unexpected cookie\n",
592 		    (void *)lp, (void *)cookie);
593 
594 	ep = uu_list_first(lp);
595 	if (ep)
596 		uu_list_remove(lp, ep);
597 	return (ep);
598 }
599 
600 int
uu_list_insert_before(uu_list_t * lp,void * target,void * elem)601 uu_list_insert_before(uu_list_t *lp, void *target, void *elem)
602 {
603 	uu_list_node_impl_t *np = ELEM_TO_NODE(lp, target);
604 
605 	if (target == NULL)
606 		np = &lp->ul_null_node;
607 
608 	if (lp->ul_debug) {
609 		if (np->uln_prev == NULL)
610 			uu_panic("uu_list_insert_before(%p, %p, %p): %p is "
611 			    "not currently on a list\n",
612 			    (void *)lp, target, elem, target);
613 	}
614 	if (lp->ul_sorted) {
615 		if (lp->ul_debug)
616 			uu_panic("uu_list_insert_before(%p, ...): list is "
617 			    "UU_LIST_SORTED\n", (void *)lp);
618 		uu_set_error(UU_ERROR_NOT_SUPPORTED);
619 		return (-1);
620 	}
621 
622 	list_insert(lp, ELEM_TO_NODE(lp, elem), np->uln_prev, np);
623 	return (0);
624 }
625 
626 int
uu_list_insert_after(uu_list_t * lp,void * target,void * elem)627 uu_list_insert_after(uu_list_t *lp, void *target, void *elem)
628 {
629 	uu_list_node_impl_t *np = ELEM_TO_NODE(lp, target);
630 
631 	if (target == NULL)
632 		np = &lp->ul_null_node;
633 
634 	if (lp->ul_debug) {
635 		if (np->uln_prev == NULL)
636 			uu_panic("uu_list_insert_after(%p, %p, %p): %p is "
637 			    "not currently on a list\n",
638 			    (void *)lp, target, elem, target);
639 	}
640 	if (lp->ul_sorted) {
641 		if (lp->ul_debug)
642 			uu_panic("uu_list_insert_after(%p, ...): list is "
643 			    "UU_LIST_SORTED\n", (void *)lp);
644 		uu_set_error(UU_ERROR_NOT_SUPPORTED);
645 		return (-1);
646 	}
647 
648 	list_insert(lp, ELEM_TO_NODE(lp, elem), np, np->uln_next);
649 	return (0);
650 }
651 
652 size_t
uu_list_numnodes(uu_list_t * lp)653 uu_list_numnodes(uu_list_t *lp)
654 {
655 	return (lp->ul_numnodes);
656 }
657 
658 void *
uu_list_first(uu_list_t * lp)659 uu_list_first(uu_list_t *lp)
660 {
661 	uu_list_node_impl_t *n = lp->ul_null_node.uln_next;
662 	if (n == &lp->ul_null_node)
663 		return (NULL);
664 	return (NODE_TO_ELEM(lp, n));
665 }
666 
667 void *
uu_list_last(uu_list_t * lp)668 uu_list_last(uu_list_t *lp)
669 {
670 	uu_list_node_impl_t *n = lp->ul_null_node.uln_prev;
671 	if (n == &lp->ul_null_node)
672 		return (NULL);
673 	return (NODE_TO_ELEM(lp, n));
674 }
675 
676 void *
uu_list_next(uu_list_t * lp,void * elem)677 uu_list_next(uu_list_t *lp, void *elem)
678 {
679 	uu_list_node_impl_t *n = ELEM_TO_NODE(lp, elem);
680 
681 	n = n->uln_next;
682 	if (n == &lp->ul_null_node)
683 		return (NULL);
684 	return (NODE_TO_ELEM(lp, n));
685 }
686 
687 void *
uu_list_prev(uu_list_t * lp,void * elem)688 uu_list_prev(uu_list_t *lp, void *elem)
689 {
690 	uu_list_node_impl_t *n = ELEM_TO_NODE(lp, elem);
691 
692 	n = n->uln_prev;
693 	if (n == &lp->ul_null_node)
694 		return (NULL);
695 	return (NODE_TO_ELEM(lp, n));
696 }
697 
698 /*
699  * called from uu_lockup() and uu_release(), as part of our fork1()-safety.
700  */
701 void
uu_list_lockup(void)702 uu_list_lockup(void)
703 {
704 	uu_list_pool_t *pp;
705 
706 	(void) pthread_mutex_lock(&uu_lpool_list_lock);
707 	for (pp = uu_null_lpool.ulp_next; pp != &uu_null_lpool;
708 	    pp = pp->ulp_next)
709 		(void) pthread_mutex_lock(&pp->ulp_lock);
710 }
711 
712 void
uu_list_release(void)713 uu_list_release(void)
714 {
715 	uu_list_pool_t *pp;
716 
717 	for (pp = uu_null_lpool.ulp_next; pp != &uu_null_lpool;
718 	    pp = pp->ulp_next)
719 		(void) pthread_mutex_unlock(&pp->ulp_lock);
720 	(void) pthread_mutex_unlock(&uu_lpool_list_lock);
721 }
722