35 #define	ELEM_TO_NODE(lp, e) \  argument
36 	((uu_list_node_impl_t *)((uintptr_t)(e) + (lp)->ul_offset))
38 #define	NODE_TO_ELEM(lp, n) \  argument
39 	((void *)((uintptr_t)(n) - (lp)->ul_offset))
180 	uu_list_t *lp, *next, *prev;  in uu_list_create()  local
196 	lp = uu_zalloc(sizeof (*lp));  in uu_list_create()
197 	if (lp == NULL) {  in uu_list_create()
202 	lp->ul_pool = pp;  in uu_list_create()
203 	lp->ul_parent = parent;  in uu_list_create()
204 	lp->ul_offset = pp->ulp_nodeoffset;  in uu_list_create()
205 	lp->ul_debug = pp->ulp_debug || (flags & UU_LIST_DEBUG);  in uu_list_create()
206 	lp->ul_sorted = (flags & UU_LIST_SORTED);  in uu_list_create()
207 	lp->ul_numnodes = 0;  in uu_list_create()
208 	lp->ul_index = (pp->ulp_last_index = INDEX_NEXT(pp->ulp_last_index));  in uu_list_create()
210 	lp->ul_null_node.uln_next = &lp->ul_null_node;  in uu_list_create()
211 	lp->ul_null_node.uln_prev = &lp->ul_null_node;  in uu_list_create()
213 	lp->ul_null_walk.ulw_next = &lp->ul_null_walk;  in uu_list_create()
214 	lp->ul_null_walk.ulw_prev = &lp->ul_null_walk;  in uu_list_create()
219 	lp->ul_next = next;  in uu_list_create()
220 	lp->ul_prev = prev;  in uu_list_create()
221 	next->ul_prev = lp;  in uu_list_create()
222 	prev->ul_next = lp;  in uu_list_create()
225 	return (lp);  in uu_list_create()
229 uu_list_destroy(uu_list_t *lp)  in uu_list_destroy()  argument
231 	uu_list_pool_t *pp = lp->ul_pool;  in uu_list_destroy()
233 	if (lp->ul_debug) {  in uu_list_destroy()
234 		if (lp->ul_null_node.uln_next != &lp->ul_null_node ||  in uu_list_destroy()
235 		    lp->ul_null_node.uln_prev != &lp->ul_null_node) {  in uu_list_destroy()
237 			    (void *)lp);  in uu_list_destroy()
239 		if (lp->ul_numnodes != 0) {  in uu_list_destroy()
241 			    "but list is empty\n", (void *)lp);  in uu_list_destroy()
243 		if (lp->ul_null_walk.ulw_next != &lp->ul_null_walk ||  in uu_list_destroy()
244 		    lp->ul_null_walk.ulw_prev != &lp->ul_null_walk) {  in uu_list_destroy()
246 			    (void *)lp);  in uu_list_destroy()
251 	lp->ul_next->ul_prev = lp->ul_prev;  in uu_list_destroy()
252 	lp->ul_prev->ul_next = lp->ul_next;  in uu_list_destroy()
254 	lp->ul_prev = NULL;  in uu_list_destroy()
255 	lp->ul_next = NULL;  in uu_list_destroy()
256 	lp->ul_pool = NULL;  in uu_list_destroy()
257 	uu_free(lp);  in uu_list_destroy()
261 list_insert(uu_list_t *lp, uu_list_node_impl_t *np, uu_list_node_impl_t *prev,  in list_insert()  argument
264 	if (lp->ul_debug) {  in list_insert()
267 			    "neighbors\n", (void *)lp, (void *)next,  in list_insert()
270 		if (np->uln_next != POOL_TO_MARKER(lp->ul_pool) ||  in list_insert()
274 			    (void *)lp, NODE_TO_ELEM(lp, np), (void *)np);  in list_insert()
279 		lp->ul_index = INDEX_NEXT(lp->ul_index);  in list_insert()
286 	lp->ul_numnodes++;  in list_insert()
290 uu_list_insert(uu_list_t *lp, void *elem, uu_list_index_t idx)  in uu_list_insert()  argument
296 		np = &lp->ul_null_node;  in uu_list_insert()
298 	if (lp->ul_debug) {  in uu_list_insert()
299 		if (!INDEX_VALID(lp, idx))  in uu_list_insert()
301 			    (void *)lp, elem, (void *)idx,  in uu_list_insert()
306 			    "index\n", (void *)lp, elem, (void *)idx);  in uu_list_insert()
309 	list_insert(lp, ELEM_TO_NODE(lp, elem), np->uln_prev, np);  in uu_list_insert()
313 uu_list_find(uu_list_t *lp, void *elem, void *private, uu_list_index_t *out)  in uu_list_find()  argument
315 	int sorted = lp->ul_sorted;  in uu_list_find()
316 	uu_compare_fn_t *func = lp->ul_pool->ulp_cmp;  in uu_list_find()
325 	for (np = lp->ul_null_node.uln_next; np != &lp->ul_null_node;  in uu_list_find()
327 		void *ep = NODE_TO_ELEM(lp, np);  in uu_list_find()
331 				*out = NODE_TO_INDEX(lp, np);  in uu_list_find()
336 				*out = NODE_TO_INDEX(lp, np);  in uu_list_find()
341 		*out = NODE_TO_INDEX(lp, 0);  in uu_list_find()
346 uu_list_nearest_next(uu_list_t *lp, uu_list_index_t idx)  in uu_list_nearest_next()  argument
351 		np = &lp->ul_null_node;  in uu_list_nearest_next()
353 	if (lp->ul_debug) {  in uu_list_nearest_next()
354 		if (!INDEX_VALID(lp, idx))  in uu_list_nearest_next()
356 			    (void *)lp, (void *)idx,  in uu_list_nearest_next()
361 			    "index\n", (void *)lp, (void *)idx);  in uu_list_nearest_next()
364 	if (np == &lp->ul_null_node)  in uu_list_nearest_next()
367 		return (NODE_TO_ELEM(lp, np));  in uu_list_nearest_next()
371 uu_list_nearest_prev(uu_list_t *lp, uu_list_index_t idx)  in uu_list_nearest_prev()  argument
376 		np = &lp->ul_null_node;  in uu_list_nearest_prev()
378 	if (lp->ul_debug) {  in uu_list_nearest_prev()
379 		if (!INDEX_VALID(lp, idx))  in uu_list_nearest_prev()
381 			    (void *)lp, (void *)idx, INDEX_CHECK(idx)?  in uu_list_nearest_prev()
385 			    "index\n", (void *)lp, (void *)idx);  in uu_list_nearest_prev()
388 	if ((np = np->uln_prev) == &lp->ul_null_node)  in uu_list_nearest_prev()
391 		return (NODE_TO_ELEM(lp, np));  in uu_list_nearest_prev()
395 list_walk_init(uu_list_walk_t *wp, uu_list_t *lp, uint32_t flags)  in list_walk_init()  argument
403 	wp->ulw_list = lp;  in list_walk_init()
407 		wp->ulw_next_result = lp->ul_null_node.uln_next;  in list_walk_init()
409 		wp->ulw_next_result = lp->ul_null_node.uln_prev;  in list_walk_init()
411 	if (lp->ul_debug || robust) {  in list_walk_init()
417 		wp->ulw_next = next = &lp->ul_null_walk;  in list_walk_init()
425 list_walk_advance(uu_list_walk_t *wp, uu_list_t *lp)  in list_walk_advance()  argument
430 	if (np == &lp->ul_null_node)  in list_walk_advance()
454 uu_list_walk_start(uu_list_t *lp, uint32_t flags)  in uu_list_walk_start()  argument
469 	list_walk_init(wp, lp, flags);  in uu_list_walk_start()
476 	uu_list_t *lp = wp->ulw_list;  in uu_list_walk_next()  local
477 	uu_list_node_impl_t *np = list_walk_advance(wp, lp);  in uu_list_walk_next()
482 	return (NODE_TO_ELEM(lp, np));  in uu_list_walk_next()
493 uu_list_walk(uu_list_t *lp, uu_walk_fn_t *func, void *private, uint32_t flags)  in uu_list_walk()  argument
507 	if (lp->ul_debug || robust) {  in uu_list_walk()
515 		list_walk_init(my_walk, lp, flags);  in uu_list_walk()
524 			for (np = lp->ul_null_node.uln_next;  in uu_list_walk()
525 			    status == UU_WALK_NEXT && np != &lp->ul_null_node;  in uu_list_walk()
527 				status = (*func)(NODE_TO_ELEM(lp, np), private);  in uu_list_walk()
530 			for (np = lp->ul_null_node.uln_prev;  in uu_list_walk()
531 			    status == UU_WALK_NEXT && np != &lp->ul_null_node;  in uu_list_walk()
533 				status = (*func)(NODE_TO_ELEM(lp, np), private);  in uu_list_walk()
544 uu_list_remove(uu_list_t *lp, void *elem)  in uu_list_remove()  argument
546 	uu_list_node_impl_t *np = ELEM_TO_NODE(lp, elem);  in uu_list_remove()
549 	if (lp->ul_debug) {  in uu_list_remove()
552 			    (void *)lp, elem);  in uu_list_remove()
556 		lp->ul_index = INDEX_NEXT(lp->ul_index);  in uu_list_remove()
563 	for (wp = lp->ul_null_walk.ulw_next; wp != &lp->ul_null_walk;  in uu_list_remove()
567 				(void) list_walk_advance(wp, lp);  in uu_list_remove()
570 			    "walker\n", (void *)lp, elem);  in uu_list_remove()
577 	lp->ul_numnodes--;  in uu_list_remove()
579 	np->uln_next = POOL_TO_MARKER(lp->ul_pool);  in uu_list_remove()
584 uu_list_teardown(uu_list_t *lp, void **cookie)  in uu_list_teardown()  argument
591 	if (lp->ul_debug && *cookie != NULL)  in uu_list_teardown()
593 		    (void *)lp, (void *)cookie);  in uu_list_teardown()
595 	ep = uu_list_first(lp);  in uu_list_teardown()
597 		uu_list_remove(lp, ep);  in uu_list_teardown()
602 uu_list_insert_before(uu_list_t *lp, void *target, void *elem)  in uu_list_insert_before()  argument
604 	uu_list_node_impl_t *np = ELEM_TO_NODE(lp, target);  in uu_list_insert_before()
607 		np = &lp->ul_null_node;  in uu_list_insert_before()
609 	if (lp->ul_debug) {  in uu_list_insert_before()
613 			    (void *)lp, target, elem, target);  in uu_list_insert_before()
615 	if (lp->ul_sorted) {  in uu_list_insert_before()
616 		if (lp->ul_debug)  in uu_list_insert_before()
618 			    "UU_LIST_SORTED\n", (void *)lp);  in uu_list_insert_before()
623 	list_insert(lp, ELEM_TO_NODE(lp, elem), np->uln_prev, np);  in uu_list_insert_before()
628 uu_list_insert_after(uu_list_t *lp, void *target, void *elem)  in uu_list_insert_after()  argument
630 	uu_list_node_impl_t *np = ELEM_TO_NODE(lp, target);  in uu_list_insert_after()
633 		np = &lp->ul_null_node;  in uu_list_insert_after()
635 	if (lp->ul_debug) {  in uu_list_insert_after()
639 			    (void *)lp, target, elem, target);  in uu_list_insert_after()
641 	if (lp->ul_sorted) {  in uu_list_insert_after()
642 		if (lp->ul_debug)  in uu_list_insert_after()
644 			    "UU_LIST_SORTED\n", (void *)lp);  in uu_list_insert_after()
649 	list_insert(lp, ELEM_TO_NODE(lp, elem), np, np->uln_next);  in uu_list_insert_after()
654 uu_list_numnodes(uu_list_t *lp)  in uu_list_numnodes()  argument
656 	return (lp->ul_numnodes);  in uu_list_numnodes()
660 uu_list_first(uu_list_t *lp)  in uu_list_first()  argument
662 	uu_list_node_impl_t *n = lp->ul_null_node.uln_next;  in uu_list_first()
663 	if (n == &lp->ul_null_node)  in uu_list_first()
665 	return (NODE_TO_ELEM(lp, n));  in uu_list_first()
669 uu_list_last(uu_list_t *lp)  in uu_list_last()  argument
671 	uu_list_node_impl_t *n = lp->ul_null_node.uln_prev;  in uu_list_last()
672 	if (n == &lp->ul_null_node)  in uu_list_last()
674 	return (NODE_TO_ELEM(lp, n));  in uu_list_last()
678 uu_list_next(uu_list_t *lp, void *elem)  in uu_list_next()  argument
680 	uu_list_node_impl_t *n = ELEM_TO_NODE(lp, elem);  in uu_list_next()
683 	if (n == &lp->ul_null_node)  in uu_list_next()
685 	return (NODE_TO_ELEM(lp, n));  in uu_list_next()
689 uu_list_prev(uu_list_t *lp, void *elem)  in uu_list_prev()  argument
691 	uu_list_node_impl_t *n = ELEM_TO_NODE(lp, elem);  in uu_list_prev()
694 	if (n == &lp->ul_null_node)  in uu_list_prev()
696 	return (NODE_TO_ELEM(lp, n));  in uu_list_prev()