libuutil/common/uu_list.c

35 #define	ELEM_TO_NODE(lp, e) \
36 	((uu_list_node_impl_t *)((uintptr_t)(e) + (lp)->ul_offset))
38 #define	NODE_TO_ELEM(lp, n) \
39 	((void *)((uintptr_t)(n) - (lp)->ul_offset))
182 	uu_list_t *lp, *next, *prev;
198 	lp = uu_zalloc(sizeof (*lp));
199 	if (lp == NULL) {
204 	lp->ul_pool = pp;
205 	lp->ul_parent_enc = UU_PTR_ENCODE(parent);
206 	lp->ul_offset = pp->ulp_nodeoffset;
207 	lp->ul_debug = pp->ulp_debug || (flags & UU_LIST_DEBUG);
208 	lp->ul_sorted = (flags & UU_LIST_SORTED);
209 	lp->ul_numnodes = 0;
210 	lp->ul_index = (pp->ulp_last_index = INDEX_NEXT(pp->ulp_last_index));
212 	lp->ul_null_node.uln_next = &lp->ul_null_node;
213 	lp->ul_null_node.uln_prev = &lp->ul_null_node;
215 	lp->ul_null_walk.ulw_next = &lp->ul_null_walk;
216 	lp->ul_null_walk.ulw_prev = &lp->ul_null_walk;
221 	lp->ul_next_enc = UU_PTR_ENCODE(next);
222 	lp->ul_prev_enc = UU_PTR_ENCODE(prev);
223 	next->ul_prev_enc = UU_PTR_ENCODE(lp);
224 	prev->ul_next_enc = UU_PTR_ENCODE(lp);
227 	return (lp);
231 uu_list_destroy(uu_list_t *lp)
233 	uu_list_pool_t *pp = lp->ul_pool;
235 	if (lp->ul_debug) {
236 		if (lp->ul_null_node.uln_next != &lp->ul_null_node ||
237 		    lp->ul_null_node.uln_prev != &lp->ul_null_node) {
239 			    (void *)lp);
241 		if (lp->ul_numnodes != 0) {
243 			    "but list is empty\n", (void *)lp);
245 		if (lp->ul_null_walk.ulw_next != &lp->ul_null_walk ||
246 		    lp->ul_null_walk.ulw_prev != &lp->ul_null_walk) {
248 			    (void *)lp);
253 	UU_LIST_PTR(lp->ul_next_enc)->ul_prev_enc = lp->ul_prev_enc;
254 	UU_LIST_PTR(lp->ul_prev_enc)->ul_next_enc = lp->ul_next_enc;
256 	lp->ul_prev_enc = UU_PTR_ENCODE(NULL);
257 	lp->ul_next_enc = UU_PTR_ENCODE(NULL);
258 	lp->ul_pool = NULL;
259 	uu_free(lp);
263 list_insert(uu_list_t *lp, uu_list_node_impl_t *np, uu_list_node_impl_t *prev,
266 	if (lp->ul_debug) {
269 			    "neighbors\n", (void *)lp, (void *)next,
272 		if (np->uln_next != POOL_TO_MARKER(lp->ul_pool) ||
276 			    (void *)lp, NODE_TO_ELEM(lp, np), (void *)np);
281 		lp->ul_index = INDEX_NEXT(lp->ul_index);
288 	lp->ul_numnodes++;
292 uu_list_insert(uu_list_t *lp, void *elem, uu_list_index_t idx)
298 		np = &lp->ul_null_node;
300 	if (lp->ul_debug) {
301 		if (!INDEX_VALID(lp, idx))
303 			    (void *)lp, elem, (void *)idx,
308 			    "index\n", (void *)lp, elem, (void *)idx);
311 	list_insert(lp, ELEM_TO_NODE(lp, elem), np->uln_prev, np);
315 uu_list_find(uu_list_t *lp, void *elem, void *private, uu_list_index_t *out)
317 	int sorted = lp->ul_sorted;
318 	uu_compare_fn_t *func = lp->ul_pool->ulp_cmp;
327 	for (np = lp->ul_null_node.uln_next; np != &lp->ul_null_node;
329 		void *ep = NODE_TO_ELEM(lp, np);
333 				*out = NODE_TO_INDEX(lp, np);
338 				*out = NODE_TO_INDEX(lp, np);
343 		*out = NODE_TO_INDEX(lp, 0);
348 uu_list_nearest_next(uu_list_t *lp, uu_list_index_t idx)
353 		np = &lp->ul_null_node;
355 	if (lp->ul_debug) {
356 		if (!INDEX_VALID(lp, idx))
358 			    (void *)lp, (void *)idx,
363 			    "index\n", (void *)lp, (void *)idx);
366 	if (np == &lp->ul_null_node)
369 		return (NODE_TO_ELEM(lp, np));
373 uu_list_nearest_prev(uu_list_t *lp, uu_list_index_t idx)
378 		np = &lp->ul_null_node;
380 	if (lp->ul_debug) {
381 		if (!INDEX_VALID(lp, idx))
383 			    (void *)lp, (void *)idx, INDEX_CHECK(idx)?
387 			    "index\n", (void *)lp, (void *)idx);
390 	if ((np = np->uln_prev) == &lp->ul_null_node)
393 		return (NODE_TO_ELEM(lp, np));
397 list_walk_init(uu_list_walk_t *wp, uu_list_t *lp, uint32_t flags)
405 	wp->ulw_list = lp;
409 		wp->ulw_next_result = lp->ul_null_node.uln_next;
411 		wp->ulw_next_result = lp->ul_null_node.uln_prev;
413 	if (lp->ul_debug || robust) {
419 		wp->ulw_next = next = &lp->ul_null_walk;
427 list_walk_advance(uu_list_walk_t *wp, uu_list_t *lp)
432 	if (np == &lp->ul_null_node)
456 uu_list_walk_start(uu_list_t *lp, uint32_t flags)
471 	list_walk_init(wp, lp, flags);
478 	uu_list_t *lp = wp->ulw_list;
479 	uu_list_node_impl_t *np = list_walk_advance(wp, lp);
484 	return (NODE_TO_ELEM(lp, np));
495 uu_list_walk(uu_list_t *lp, uu_walk_fn_t *func, void *private, uint32_t flags)
509 	if (lp->ul_debug || robust) {
513 		list_walk_init(&my_walk, lp, flags);
520 			for (np = lp->ul_null_node.uln_next;
521 			    status == UU_WALK_NEXT && np != &lp->ul_null_node;
523 				status = (*func)(NODE_TO_ELEM(lp, np), private);
526 			for (np = lp->ul_null_node.uln_prev;
527 			    status == UU_WALK_NEXT && np != &lp->ul_null_node;
529 				status = (*func)(NODE_TO_ELEM(lp, np), private);
540 uu_list_remove(uu_list_t *lp, void *elem)
542 	uu_list_node_impl_t *np = ELEM_TO_NODE(lp, elem);
545 	if (lp->ul_debug) {
548 			    (void *)lp, elem);
552 		lp->ul_index = INDEX_NEXT(lp->ul_index);
559 	for (wp = lp->ul_null_walk.ulw_next; wp != &lp->ul_null_walk;
563 				(void) list_walk_advance(wp, lp);
566 			    "walker\n", (void *)lp, elem);
573 	lp->ul_numnodes--;
575 	np->uln_next = POOL_TO_MARKER(lp->ul_pool);
580 uu_list_teardown(uu_list_t *lp, void **cookie)
587 	if (lp->ul_debug && *cookie != NULL)
589 		    (void *)lp, (void *)cookie);
591 	ep = uu_list_first(lp);
593 		uu_list_remove(lp, ep);
598 uu_list_insert_before(uu_list_t *lp, void *target, void *elem)
600 	uu_list_node_impl_t *np = ELEM_TO_NODE(lp, target);
603 		np = &lp->ul_null_node;
605 	if (lp->ul_debug) {
609 			    (void *)lp, target, elem, target);
611 	if (lp->ul_sorted) {
612 		if (lp->ul_debug)
614 			    "UU_LIST_SORTED\n", (void *)lp);
619 	list_insert(lp, ELEM_TO_NODE(lp, elem), np->uln_prev, np);
624 uu_list_insert_after(uu_list_t *lp, void *target, void *elem)
626 	uu_list_node_impl_t *np = ELEM_TO_NODE(lp, target);
629 		np = &lp->ul_null_node;
631 	if (lp->ul_debug) {
635 			    (void *)lp, target, elem, target);
637 	if (lp->ul_sorted) {
638 		if (lp->ul_debug)
640 			    "UU_LIST_SORTED\n", (void *)lp);
645 	list_insert(lp, ELEM_TO_NODE(lp, elem), np, np->uln_next);
650 uu_list_numnodes(uu_list_t *lp)
652 	return (lp->ul_numnodes);
656 uu_list_first(uu_list_t *lp)
658 	uu_list_node_impl_t *n = lp->ul_null_node.uln_next;
659 	if (n == &lp->ul_null_node)
661 	return (NODE_TO_ELEM(lp, n));
665 uu_list_last(uu_list_t *lp)
667 	uu_list_node_impl_t *n = lp->ul_null_node.uln_prev;
668 	if (n == &lp->ul_null_node)
670 	return (NODE_TO_ELEM(lp, n));
674 uu_list_next(uu_list_t *lp, void *elem)
676 	uu_list_node_impl_t *n = ELEM_TO_NODE(lp, elem);
679 	if (n == &lp->ul_null_node)
681 	return (NODE_TO_ELEM(lp, n));
685 uu_list_prev(uu_list_t *lp, void *elem)
687 	uu_list_node_impl_t *n = ELEM_TO_NODE(lp, elem);
690 	if (n == &lp->ul_null_node)
692 	return (NODE_TO_ELEM(lp, n));