uu_list.c revision 177698
190075Sobrien/* 290075Sobrien * CDDL HEADER START 3169689Skan * 4169689Skan * The contents of this file are subject to the terms of the 590075Sobrien * Common Development and Distribution License, Version 1.0 only 690075Sobrien * (the "License"). You may not use this file except in compliance 790075Sobrien * with the License. 890075Sobrien * 990075Sobrien * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 1090075Sobrien * or http://www.opensolaris.org/os/licensing. 1190075Sobrien * See the License for the specific language governing permissions 1290075Sobrien * and limitations under the License. 1390075Sobrien * 1490075Sobrien * When distributing Covered Code, include this CDDL HEADER in each 1590075Sobrien * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 1690075Sobrien * If applicable, add the following below this CDDL HEADER, with the 1790075Sobrien * fields enclosed by brackets "[]" replaced with your own identifying 1890075Sobrien * information: Portions Copyright [yyyy] [name of copyright owner] 1990075Sobrien * 20169689Skan * CDDL HEADER END 21169689Skan */ 2290075Sobrien/* 2390075Sobrien * Copyright 2005 Sun Microsystems, Inc. All rights reserved. 24132718Skan * Use is subject to license terms. 2590075Sobrien */ 2690075Sobrien 2790075Sobrien#pragma ident "%Z%%M% %I% %E% SMI" 2890075Sobrien 2990075Sobrien#include "libuutil_common.h" 3090075Sobrien 3190075Sobrien#include <stdlib.h> 3290075Sobrien#include <string.h> 3390075Sobrien#include <unistd.h> 3490075Sobrien#include <sys/time.h> 3590075Sobrien 3690075Sobrien#define ELEM_TO_NODE(lp, e) \ 3790075Sobrien ((uu_list_node_impl_t *)((uintptr_t)(e) + (lp)->ul_offset)) 3890075Sobrien 3990075Sobrien#define NODE_TO_ELEM(lp, n) \ 4090075Sobrien ((void *)((uintptr_t)(n) - (lp)->ul_offset)) 4190075Sobrien 42117395Skan/* 43132718Skan * uu_list_index_ts define a location for insertion. They are simply a 44132718Skan * pointer to the object after the insertion point. We store a mark 45132718Skan * in the low-bits of the index, to help prevent mistakes. 46132718Skan * 4790075Sobrien * When debugging, the index mark changes on every insert and delete, to 4890075Sobrien * catch stale references. 4990075Sobrien */ 5090075Sobrien#define INDEX_MAX (sizeof (uintptr_t) - 1) 51132718Skan#define INDEX_NEXT(m) (((m) == INDEX_MAX)? 1 : ((m) + 1) & INDEX_MAX) 52132718Skan 5390075Sobrien#define INDEX_TO_NODE(i) ((uu_list_node_impl_t *)((i) & ~INDEX_MAX)) 5490075Sobrien#define NODE_TO_INDEX(p, n) (((uintptr_t)(n) & ~INDEX_MAX) | (p)->ul_index) 5590075Sobrien#define INDEX_VALID(p, i) (((i) & INDEX_MAX) == (p)->ul_index) 5690075Sobrien#define INDEX_CHECK(i) (((i) & INDEX_MAX) != 0) 5790075Sobrien 5890075Sobrien#define POOL_TO_MARKER(pp) ((void *)((uintptr_t)(pp) | 1)) 5990075Sobrien 6090075Sobrienstatic uu_list_pool_t uu_null_lpool = { &uu_null_lpool, &uu_null_lpool }; 6190075Sobrienstatic pthread_mutex_t uu_lpool_list_lock = PTHREAD_MUTEX_INITIALIZER; 6290075Sobrien 6390075Sobrienuu_list_pool_t * 64169689Skanuu_list_pool_create(const char *name, size_t objsize, 65169689Skan size_t nodeoffset, uu_compare_fn_t *compare_func, uint32_t flags) 66169689Skan{ 67169689Skan uu_list_pool_t *pp, *next, *prev; 68132718Skan 6990075Sobrien if (name == NULL || 7090075Sobrien uu_check_name(name, UU_NAME_DOMAIN) == -1 || 7190075Sobrien nodeoffset + sizeof (uu_list_node_t) > objsize) { 72169689Skan uu_set_error(UU_ERROR_INVALID_ARGUMENT); 7390075Sobrien return (NULL); 74132718Skan } 75132718Skan 7690075Sobrien if (flags & ~UU_LIST_POOL_DEBUG) { 77169689Skan uu_set_error(UU_ERROR_UNKNOWN_FLAG); 78169689Skan return (NULL); 7990075Sobrien } 8090075Sobrien 8190075Sobrien pp = uu_zalloc(sizeof (uu_list_pool_t)); 82132718Skan if (pp == NULL) { 8390075Sobrien uu_set_error(UU_ERROR_NO_MEMORY); 84169689Skan return (NULL); 85169689Skan } 8690075Sobrien 87169689Skan (void) strlcpy(pp->ulp_name, name, sizeof (pp->ulp_name)); 88169689Skan pp->ulp_nodeoffset = nodeoffset; 89169689Skan pp->ulp_objsize = objsize; 90169689Skan pp->ulp_cmp = compare_func; 91169689Skan if (flags & UU_LIST_POOL_DEBUG) 92169689Skan pp->ulp_debug = 1; 9390075Sobrien pp->ulp_last_index = 0; 9490075Sobrien 9590075Sobrien (void) pthread_mutex_init(&pp->ulp_lock, NULL); 9690075Sobrien 9790075Sobrien pp->ulp_null_list.ul_next_enc = UU_PTR_ENCODE(&pp->ulp_null_list); 9890075Sobrien pp->ulp_null_list.ul_prev_enc = UU_PTR_ENCODE(&pp->ulp_null_list); 99169689Skan 10090075Sobrien (void) pthread_mutex_lock(&uu_lpool_list_lock); 10190075Sobrien pp->ulp_next = next = &uu_null_lpool; 102169689Skan pp->ulp_prev = prev = next->ulp_prev; 10390075Sobrien next->ulp_prev = pp; 10490075Sobrien prev->ulp_next = pp; 10590075Sobrien (void) pthread_mutex_unlock(&uu_lpool_list_lock); 10690075Sobrien 10790075Sobrien return (pp); 108132718Skan} 10990075Sobrien 110117395Skanvoid 11190075Sobrienuu_list_pool_destroy(uu_list_pool_t *pp) 112169689Skan{ 11390075Sobrien if (pp->ulp_debug) { 114117395Skan if (pp->ulp_null_list.ul_next_enc != 11590075Sobrien UU_PTR_ENCODE(&pp->ulp_null_list) || 116169689Skan pp->ulp_null_list.ul_prev_enc != 117169689Skan UU_PTR_ENCODE(&pp->ulp_null_list)) { 118169689Skan uu_panic("uu_list_pool_destroy: Pool \"%.*s\" (%p) has " 119169689Skan "outstanding lists, or is corrupt.\n", 12090075Sobrien sizeof (pp->ulp_name), pp->ulp_name, pp); 12190075Sobrien } 122169689Skan } 123169689Skan (void) pthread_mutex_lock(&uu_lpool_list_lock); 124169689Skan pp->ulp_next->ulp_prev = pp->ulp_prev; 125169689Skan pp->ulp_prev->ulp_next = pp->ulp_next; 12690075Sobrien (void) pthread_mutex_unlock(&uu_lpool_list_lock); 127169689Skan pp->ulp_prev = NULL; 12890075Sobrien pp->ulp_next = NULL; 12990075Sobrien uu_free(pp); 13090075Sobrien} 13190075Sobrien 13290075Sobrienvoid 133132718Skanuu_list_node_init(void *base, uu_list_node_t *np_arg, uu_list_pool_t *pp) 13490075Sobrien{ 13590075Sobrien uu_list_node_impl_t *np = (uu_list_node_impl_t *)np_arg; 136169689Skan 13790075Sobrien if (pp->ulp_debug) { 13890075Sobrien uintptr_t offset = (uintptr_t)np - (uintptr_t)base; 13990075Sobrien if (offset + sizeof (*np) > pp->ulp_objsize) { 140117395Skan uu_panic("uu_list_node_init(%p, %p, %p (\"%s\")): " 141117395Skan "offset %ld doesn't fit in object (size %ld)\n", 142132718Skan base, np, pp, pp->ulp_name, offset, 143117395Skan pp->ulp_objsize); 144117395Skan } 145117395Skan if (offset != pp->ulp_nodeoffset) { 146117395Skan uu_panic("uu_list_node_init(%p, %p, %p (\"%s\")): " 147117395Skan "offset %ld doesn't match pool's offset (%ld)\n", 148117395Skan base, np, pp, pp->ulp_name, offset, 14990075Sobrien pp->ulp_objsize); 150117395Skan } 15190075Sobrien } 152132718Skan np->uln_next = POOL_TO_MARKER(pp); 15396263Sobrien np->uln_prev = NULL; 154117395Skan} 155117395Skan 156169689Skanvoid 157169689Skanuu_list_node_fini(void *base, uu_list_node_t *np_arg, uu_list_pool_t *pp) 158117395Skan{ 159117395Skan uu_list_node_impl_t *np = (uu_list_node_impl_t *)np_arg; 160117395Skan 161117395Skan if (pp->ulp_debug) { 162132718Skan if (np->uln_next == NULL && 163117395Skan np->uln_prev == NULL) { 164117395Skan uu_panic("uu_list_node_fini(%p, %p, %p (\"%s\")): " 165117395Skan "node already finied\n", 166132718Skan base, np_arg, pp, pp->ulp_name); 167169689Skan } 168169689Skan if (np->uln_next != POOL_TO_MARKER(pp) || 169169689Skan np->uln_prev != NULL) { 170169689Skan uu_panic("uu_list_node_fini(%p, %p, %p (\"%s\")): " 171169689Skan "node corrupt or on list\n", 172117395Skan base, np_arg, pp, pp->ulp_name); 173169689Skan } 174117395Skan } 175117395Skan np->uln_next = NULL; 176117395Skan np->uln_prev = NULL; 177117395Skan} 178169689Skan 179117395Skanuu_list_t * 180169689Skanuu_list_create(uu_list_pool_t *pp, void *parent, uint32_t flags) 181169689Skan{ 182169689Skan uu_list_t *lp, *next, *prev; 183117395Skan 184117395Skan if (flags & ~(UU_LIST_DEBUG | UU_LIST_SORTED)) { 185117395Skan uu_set_error(UU_ERROR_UNKNOWN_FLAG); 186117395Skan return (NULL); 187117395Skan } 188117395Skan 189132718Skan if ((flags & UU_LIST_SORTED) && pp->ulp_cmp == NULL) { 190117395Skan if (pp->ulp_debug) 191117395Skan uu_panic("uu_list_create(%p, ...): requested " 192169689Skan "UU_LIST_SORTED, but pool has no comparison func\n", 193117395Skan pp); 194169689Skan uu_set_error(UU_ERROR_NOT_SUPPORTED); 195169689Skan return (NULL); 196169689Skan } 197169689Skan 198169689Skan lp = uu_zalloc(sizeof (*lp)); 19996263Sobrien if (lp == NULL) { 200117395Skan uu_set_error(UU_ERROR_NO_MEMORY); 201169689Skan return (NULL); 202169689Skan } 203169689Skan 204169689Skan lp->ul_pool = pp; 205169689Skan lp->ul_parent_enc = UU_PTR_ENCODE(parent); 206169689Skan lp->ul_offset = pp->ulp_nodeoffset; 207169689Skan lp->ul_debug = pp->ulp_debug || (flags & UU_LIST_DEBUG); 208169689Skan lp->ul_sorted = (flags & UU_LIST_SORTED); 209169689Skan lp->ul_numnodes = 0; 210169689Skan lp->ul_index = (pp->ulp_last_index = INDEX_NEXT(pp->ulp_last_index)); 211169689Skan 212169689Skan lp->ul_null_node.uln_next = &lp->ul_null_node; 213169689Skan lp->ul_null_node.uln_prev = &lp->ul_null_node; 214169689Skan 215169689Skan lp->ul_null_walk.ulw_next = &lp->ul_null_walk; 216169689Skan lp->ul_null_walk.ulw_prev = &lp->ul_null_walk; 217169689Skan 218169689Skan (void) pthread_mutex_lock(&pp->ulp_lock); 219169689Skan next = &pp->ulp_null_list; 220169689Skan prev = UU_PTR_DECODE(next->ul_prev_enc); 221169689Skan lp->ul_next_enc = UU_PTR_ENCODE(next); 222169689Skan lp->ul_prev_enc = UU_PTR_ENCODE(prev); 223169689Skan next->ul_prev_enc = UU_PTR_ENCODE(lp); 224169689Skan prev->ul_next_enc = UU_PTR_ENCODE(lp); 225169689Skan (void) pthread_mutex_unlock(&pp->ulp_lock); 226169689Skan 227169689Skan return (lp); 228169689Skan} 229169689Skan 230169689Skanvoid 231169689Skanuu_list_destroy(uu_list_t *lp) 232169689Skan{ 233169689Skan uu_list_pool_t *pp = lp->ul_pool; 234169689Skan 235169689Skan if (lp->ul_debug) { 236169689Skan if (lp->ul_null_node.uln_next != &lp->ul_null_node || 237169689Skan lp->ul_null_node.uln_prev != &lp->ul_null_node) { 238169689Skan uu_panic("uu_list_destroy(%p): list not empty\n", 239169689Skan lp); 240169689Skan } 241169689Skan if (lp->ul_numnodes != 0) { 242169689Skan uu_panic("uu_list_destroy(%p): numnodes is nonzero, " 243169689Skan "but list is empty\n", lp); 244169689Skan } 245169689Skan if (lp->ul_null_walk.ulw_next != &lp->ul_null_walk || 246169689Skan lp->ul_null_walk.ulw_prev != &lp->ul_null_walk) { 247169689Skan uu_panic("uu_list_destroy(%p): outstanding walkers\n", 248169689Skan lp); 249169689Skan } 250169689Skan } 251169689Skan 252169689Skan (void) pthread_mutex_lock(&pp->ulp_lock); 253169689Skan UU_LIST_PTR(lp->ul_next_enc)->ul_prev_enc = lp->ul_prev_enc; 254169689Skan UU_LIST_PTR(lp->ul_prev_enc)->ul_next_enc = lp->ul_next_enc; 255169689Skan (void) pthread_mutex_unlock(&pp->ulp_lock); 256169689Skan lp->ul_prev_enc = UU_PTR_ENCODE(NULL); 257169689Skan lp->ul_next_enc = UU_PTR_ENCODE(NULL); 258117395Skan lp->ul_pool = NULL; 259117395Skan uu_free(lp); 260117395Skan} 26196263Sobrien 262117395Skanstatic void 263132718Skanlist_insert(uu_list_t *lp, uu_list_node_impl_t *np, uu_list_node_impl_t *prev, 26490075Sobrien uu_list_node_impl_t *next) 265117395Skan{ 266169689Skan if (lp->ul_debug) { 267117395Skan if (next->uln_prev != prev || prev->uln_next != next) 26890075Sobrien uu_panic("insert(%p): internal error: %p and %p not " 269117395Skan "neighbors\n", lp, next, prev); 270117395Skan 271117395Skan if (np->uln_next != POOL_TO_MARKER(lp->ul_pool) || 27296263Sobrien np->uln_prev != NULL) { 273169689Skan uu_panic("insert(%p): elem %p node %p corrupt, " 274169689Skan "not initialized, or already in a list.\n", 275117395Skan lp, NODE_TO_ELEM(lp, np), np); 276169689Skan } 277169689Skan /* 278117395Skan * invalidate outstanding uu_list_index_ts. 27990075Sobrien */ 280132718Skan lp->ul_index = INDEX_NEXT(lp->ul_index); 28190075Sobrien } 28290075Sobrien np->uln_next = next; 28390075Sobrien np->uln_prev = prev; 28490075Sobrien next->uln_prev = np; 285169689Skan prev->uln_next = np; 28690075Sobrien 287169689Skan lp->ul_numnodes++; 288169689Skan} 289169689Skan 290169689Skanvoid 29190075Sobrienuu_list_insert(uu_list_t *lp, void *elem, uu_list_index_t idx) 292169689Skan{ 293169689Skan uu_list_node_impl_t *np; 294169689Skan 295169689Skan np = INDEX_TO_NODE(idx); 296169689Skan if (np == NULL) 297169689Skan np = &lp->ul_null_node; 298169689Skan 299169689Skan if (lp->ul_debug) { 30090075Sobrien if (!INDEX_VALID(lp, idx)) 301169689Skan uu_panic("uu_list_insert(%p, %p, %p): %s\n", 302169689Skan lp, elem, idx, 303169689Skan INDEX_CHECK(idx)? "outdated index" : 30490075Sobrien "invalid index"); 305169689Skan if (np->uln_prev == NULL) 306169689Skan uu_panic("uu_list_insert(%p, %p, %p): out-of-date " 30790075Sobrien "index\n", lp, elem, idx); 30890075Sobrien } 309169689Skan 31090075Sobrien list_insert(lp, ELEM_TO_NODE(lp, elem), np->uln_prev, np); 31190075Sobrien} 31290075Sobrien 31390075Sobrienvoid * 31490075Sobrienuu_list_find(uu_list_t *lp, void *elem, void *private, uu_list_index_t *out) 31590075Sobrien{ 316132718Skan int sorted = lp->ul_sorted; 31790075Sobrien uu_compare_fn_t *func = lp->ul_pool->ulp_cmp; 318169689Skan uu_list_node_impl_t *np; 319169689Skan 320169689Skan if (func == NULL) { 321169689Skan if (out != NULL) 322169689Skan *out = 0; 323169689Skan uu_set_error(UU_ERROR_NOT_SUPPORTED); 324169689Skan return (NULL); 325169689Skan } 326169689Skan for (np = lp->ul_null_node.uln_next; np != &lp->ul_null_node; 327169689Skan np = np->uln_next) { 32890075Sobrien void *ep = NODE_TO_ELEM(lp, np); 32990075Sobrien int cmp = func(ep, elem, private); 33090075Sobrien if (cmp == 0) { 33190075Sobrien if (out != NULL) 33290075Sobrien *out = NODE_TO_INDEX(lp, np); 33390075Sobrien return (ep); 334132718Skan } 33590075Sobrien if (sorted && cmp > 0) { 33690075Sobrien if (out != NULL) 33790075Sobrien *out = NODE_TO_INDEX(lp, np); 33890075Sobrien return (NULL); 33990075Sobrien } 34090075Sobrien } 34190075Sobrien if (out != NULL) 34290075Sobrien *out = NODE_TO_INDEX(lp, 0); 34390075Sobrien return (NULL); 34490075Sobrien} 34590075Sobrien 346132718Skanvoid * 34790075Sobrienuu_list_nearest_next(uu_list_t *lp, uu_list_index_t idx) 348169689Skan{ 349169689Skan uu_list_node_impl_t *np = INDEX_TO_NODE(idx); 35090075Sobrien 351169689Skan if (np == NULL) 352169689Skan np = &lp->ul_null_node; 35390075Sobrien 35490075Sobrien if (lp->ul_debug) { 35590075Sobrien if (!INDEX_VALID(lp, idx)) 35690075Sobrien uu_panic("uu_list_nearest_next(%p, %p): %s\n", 35790075Sobrien lp, idx, INDEX_CHECK(idx)? "outdated index" : 35890075Sobrien "invalid index"); 35990075Sobrien if (np->uln_prev == NULL) 360132718Skan uu_panic("uu_list_nearest_next(%p, %p): out-of-date " 36190075Sobrien "index\n", lp, idx); 362169689Skan } 36390075Sobrien 364169689Skan if (np == &lp->ul_null_node) 36590075Sobrien return (NULL); 366169689Skan else 367169689Skan return (NODE_TO_ELEM(lp, np)); 36890075Sobrien} 369169689Skan 370169689Skanvoid * 371169689Skanuu_list_nearest_prev(uu_list_t *lp, uu_list_index_t idx) 37290075Sobrien{ 37390075Sobrien uu_list_node_impl_t *np = INDEX_TO_NODE(idx); 37490075Sobrien 37590075Sobrien if (np == NULL) 37690075Sobrien np = &lp->ul_null_node; 377132718Skan 37890075Sobrien if (lp->ul_debug) { 37990075Sobrien if (!INDEX_VALID(lp, idx)) 38090075Sobrien uu_panic("uu_list_nearest_prev(%p, %p): %s\n", 381169689Skan lp, idx, INDEX_CHECK(idx)? "outdated index" : 382169689Skan "invalid index"); 38390075Sobrien if (np->uln_prev == NULL) 38490075Sobrien uu_panic("uu_list_nearest_prev(%p, %p): out-of-date " 38590075Sobrien "index\n", lp, idx); 386117395Skan } 387117395Skan 38890075Sobrien if ((np = np->uln_prev) == &lp->ul_null_node) 38990075Sobrien return (NULL); 39090075Sobrien else 39190075Sobrien return (NODE_TO_ELEM(lp, np)); 39290075Sobrien} 39390075Sobrien 39490075Sobrienstatic void 39590075Sobrienlist_walk_init(uu_list_walk_t *wp, uu_list_t *lp, uint32_t flags) 39690075Sobrien{ 39790075Sobrien uu_list_walk_t *next, *prev; 39890075Sobrien 39990075Sobrien int robust = (flags & UU_WALK_ROBUST); 40090075Sobrien int direction = (flags & UU_WALK_REVERSE)? -1 : 1; 401132718Skan 40290075Sobrien (void) memset(wp, 0, sizeof (*wp)); 403169689Skan wp->ulw_list = lp; 40490075Sobrien wp->ulw_robust = robust; 405169689Skan wp->ulw_dir = direction; 40690075Sobrien if (direction > 0) 40790075Sobrien wp->ulw_next_result = lp->ul_null_node.uln_next; 408169689Skan else 40990075Sobrien wp->ulw_next_result = lp->ul_null_node.uln_prev; 410117395Skan 411169689Skan if (lp->ul_debug || robust) { 412117395Skan wp->ulw_next = next = &lp->ul_null_walk; 413132718Skan wp->ulw_prev = prev = next->ulw_prev; 414117395Skan next->ulw_prev = wp; 415117395Skan prev->ulw_next = wp; 416117395Skan } 417117395Skan} 418169689Skan 419169689Skanstatic uu_list_node_impl_t * 420117395Skanlist_walk_advance(uu_list_walk_t *wp, uu_list_t *lp) 42190075Sobrien{ 422169689Skan uu_list_node_impl_t *np = wp->ulw_next_result; 423169689Skan uu_list_node_impl_t *next; 424169689Skan 425169689Skan if (np == &lp->ul_null_node) 426169689Skan return (NULL); 42790075Sobrien 428169689Skan next = (wp->ulw_dir > 0)? np->uln_next : np->uln_prev; 42990075Sobrien 430169689Skan wp->ulw_next_result = next; 431169689Skan return (np); 432169689Skan} 433169689Skan 43490075Sobrienstatic void 435169689Skanlist_walk_fini(uu_list_walk_t *wp) 436169689Skan{ 43790075Sobrien /* GLXXX debugging? */ 438169689Skan if (wp->ulw_next != NULL) { 439169689Skan wp->ulw_next->ulw_prev = wp->ulw_prev; 440169689Skan wp->ulw_prev->ulw_next = wp->ulw_next; 441169689Skan wp->ulw_next = NULL; 442169689Skan wp->ulw_prev = NULL; 443169689Skan } 444169689Skan wp->ulw_list = NULL; 445169689Skan wp->ulw_next_result = NULL; 446169689Skan} 447169689Skan 448169689Skanuu_list_walk_t * 449169689Skanuu_list_walk_start(uu_list_t *lp, uint32_t flags) 450169689Skan{ 451169689Skan uu_list_walk_t *wp; 452169689Skan 453169689Skan if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) { 454169689Skan uu_set_error(UU_ERROR_UNKNOWN_FLAG); 455169689Skan return (NULL); 456169689Skan } 457169689Skan 458169689Skan wp = uu_zalloc(sizeof (*wp)); 459169689Skan if (wp == NULL) { 460169689Skan uu_set_error(UU_ERROR_NO_MEMORY); 461169689Skan return (NULL); 462169689Skan } 463169689Skan 464169689Skan list_walk_init(wp, lp, flags); 465169689Skan return (wp); 466169689Skan} 467169689Skan 468169689Skanvoid * 469169689Skanuu_list_walk_next(uu_list_walk_t *wp) 470169689Skan{ 471169689Skan uu_list_t *lp = wp->ulw_list; 472169689Skan uu_list_node_impl_t *np = list_walk_advance(wp, lp); 473169689Skan 474169689Skan if (np == NULL) 475169689Skan return (NULL); 476169689Skan 477169689Skan return (NODE_TO_ELEM(lp, np)); 478169689Skan} 479169689Skan 480169689Skanvoid 481169689Skanuu_list_walk_end(uu_list_walk_t *wp) 48290075Sobrien{ 483169689Skan list_walk_fini(wp); 48490075Sobrien uu_free(wp); 485169689Skan} 486169689Skan 487169689Skanint 488169689Skanuu_list_walk(uu_list_t *lp, uu_walk_fn_t *func, void *private, uint32_t flags) 489169689Skan{ 490169689Skan uu_list_node_impl_t *np; 49190075Sobrien 492117395Skan int status = UU_WALK_NEXT; 493117395Skan 494117395Skan int robust = (flags & UU_WALK_ROBUST); 495117395Skan int reverse = (flags & UU_WALK_REVERSE); 496117395Skan 497117395Skan if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) { 49890075Sobrien uu_set_error(UU_ERROR_UNKNOWN_FLAG); 499169689Skan return (-1); 500169689Skan } 50190075Sobrien 502169689Skan if (lp->ul_debug || robust) { 50390075Sobrien uu_list_walk_t my_walk; 504169689Skan void *e; 505169689Skan 506169689Skan list_walk_init(&my_walk, lp, flags); 507169689Skan while (status == UU_WALK_NEXT && 50890075Sobrien (e = uu_list_walk_next(&my_walk)) != NULL) 509169689Skan status = (*func)(e, private); 51090075Sobrien list_walk_fini(&my_walk); 511169689Skan } else { 512169689Skan if (!reverse) { 513169689Skan for (np = lp->ul_null_node.uln_next; 514169689Skan status == UU_WALK_NEXT && np != &lp->ul_null_node; 515169689Skan np = np->uln_next) { 516169689Skan status = (*func)(NODE_TO_ELEM(lp, np), private); 517169689Skan } 518169689Skan } else { 51990075Sobrien for (np = lp->ul_null_node.uln_prev; 520169689Skan status == UU_WALK_NEXT && np != &lp->ul_null_node; 521169689Skan np = np->uln_prev) { 522169689Skan status = (*func)(NODE_TO_ELEM(lp, np), private); 523169689Skan } 524169689Skan } 525169689Skan } 52690075Sobrien if (status >= 0) 527169689Skan return (0); 528169689Skan uu_set_error(UU_ERROR_CALLBACK_FAILED); 529117395Skan return (-1); 530169689Skan} 531169689Skan 532169689Skanvoid 533169689Skanuu_list_remove(uu_list_t *lp, void *elem) 534169689Skan{ 535169689Skan uu_list_node_impl_t *np = ELEM_TO_NODE(lp, elem); 536169689Skan uu_list_walk_t *wp; 537169689Skan 538169689Skan if (lp->ul_debug) { 539169689Skan if (np->uln_prev == NULL) 540169689Skan uu_panic("uu_list_remove(%p, %p): elem not on list\n", 541169689Skan lp, elem); 542169689Skan /* 543169689Skan * invalidate outstanding uu_list_index_ts. 544169689Skan */ 545169689Skan lp->ul_index = INDEX_NEXT(lp->ul_index); 546169689Skan } 547169689Skan 548169689Skan /* 549169689Skan * robust walkers must be advanced. In debug mode, non-robust 550169689Skan * walkers are also on the list. If there are any, it's an error. 551169689Skan */ 552169689Skan for (wp = lp->ul_null_walk.ulw_next; wp != &lp->ul_null_walk; 553169689Skan wp = wp->ulw_next) { 554169689Skan if (wp->ulw_robust) { 555169689Skan if (np == wp->ulw_next_result) 556169689Skan (void) list_walk_advance(wp, lp); 557169689Skan } else if (wp->ulw_next_result != NULL) { 558169689Skan uu_panic("uu_list_remove(%p, %p): active non-robust " 559169689Skan "walker\n", lp, elem); 560169689Skan } 561169689Skan } 562169689Skan 563169689Skan np->uln_next->uln_prev = np->uln_prev; 564169689Skan np->uln_prev->uln_next = np->uln_next; 565169689Skan 566169689Skan lp->ul_numnodes--; 567169689Skan 568169689Skan np->uln_next = POOL_TO_MARKER(lp->ul_pool); 569169689Skan np->uln_prev = NULL; 570169689Skan} 571169689Skan 572169689Skanvoid * 573169689Skanuu_list_teardown(uu_list_t *lp, void **cookie) 574169689Skan{ 575169689Skan void *ep; 576169689Skan 577169689Skan /* 578169689Skan * XXX: disable list modification until list is empty 579169689Skan */ 580169689Skan if (lp->ul_debug && *cookie != NULL) 581169689Skan uu_panic("uu_list_teardown(%p, %p): unexpected cookie\n", lp, 582169689Skan cookie); 58390075Sobrien 58490075Sobrien ep = uu_list_first(lp); 585169689Skan if (ep) 586169689Skan uu_list_remove(lp, ep); 587169689Skan return (ep); 588169689Skan} 589169689Skan 590169689Skanint 591169689Skanuu_list_insert_before(uu_list_t *lp, void *target, void *elem) 59290075Sobrien{ 59390075Sobrien uu_list_node_impl_t *np = ELEM_TO_NODE(lp, target); 59490075Sobrien 59590075Sobrien if (target == NULL) 596132718Skan np = &lp->ul_null_node; 59790075Sobrien 598169689Skan if (lp->ul_debug) { 59990075Sobrien if (np->uln_prev == NULL) 60090075Sobrien uu_panic("uu_list_insert_before(%p, %p, %p): %p is " 60190075Sobrien "not currently on a list\n", 602132718Skan lp, target, elem, target); 60390075Sobrien } 60490075Sobrien if (lp->ul_sorted) { 60590075Sobrien if (lp->ul_debug) 60690075Sobrien uu_panic("uu_list_insert_before(%p, ...): list is " 60790075Sobrien "UU_LIST_SORTED\n", lp); 60890075Sobrien uu_set_error(UU_ERROR_NOT_SUPPORTED); 60990075Sobrien return (-1); 61090075Sobrien } 61190075Sobrien 61290075Sobrien list_insert(lp, ELEM_TO_NODE(lp, elem), np->uln_prev, np); 61390075Sobrien return (0); 61490075Sobrien} 61590075Sobrien 61690075Sobrienint 61790075Sobrienuu_list_insert_after(uu_list_t *lp, void *target, void *elem) 61890075Sobrien{ 61990075Sobrien uu_list_node_impl_t *np = ELEM_TO_NODE(lp, target); 62090075Sobrien 62190075Sobrien if (target == NULL) 62290075Sobrien np = &lp->ul_null_node; 62390075Sobrien 624132718Skan if (lp->ul_debug) { 625132718Skan if (np->uln_prev == NULL) 626169689Skan uu_panic("uu_list_insert_after(%p, %p, %p): %p is " 627169689Skan "not currently on a list\n", 628132718Skan lp, target, elem, target); 62990075Sobrien } 63090075Sobrien if (lp->ul_sorted) { 63190075Sobrien if (lp->ul_debug) 63290075Sobrien uu_panic("uu_list_insert_after(%p, ...): list is " 63390075Sobrien "UU_LIST_SORTED\n", lp); 63490075Sobrien uu_set_error(UU_ERROR_NOT_SUPPORTED); 63590075Sobrien return (-1); 63690075Sobrien } 63790075Sobrien 63890075Sobrien list_insert(lp, ELEM_TO_NODE(lp, elem), np, np->uln_next); 63990075Sobrien return (0); 64090075Sobrien} 64190075Sobrien 64290075Sobriensize_t 64390075Sobrienuu_list_numnodes(uu_list_t *lp) 64490075Sobrien{ 64590075Sobrien return (lp->ul_numnodes); 64690075Sobrien} 64790075Sobrien 64890075Sobrienvoid * 64990075Sobrienuu_list_first(uu_list_t *lp) 65090075Sobrien{ 65190075Sobrien uu_list_node_impl_t *n = lp->ul_null_node.uln_next; 65290075Sobrien if (n == &lp->ul_null_node) 65390075Sobrien return (NULL); 65490075Sobrien return (NODE_TO_ELEM(lp, n)); 65590075Sobrien} 65690075Sobrien 65790075Sobrienvoid * 658117395Skanuu_list_last(uu_list_t *lp) 65990075Sobrien{ 66090075Sobrien uu_list_node_impl_t *n = lp->ul_null_node.uln_prev; 66190075Sobrien if (n == &lp->ul_null_node) 662132718Skan return (NULL); 66390075Sobrien return (NODE_TO_ELEM(lp, n)); 66490075Sobrien} 665169689Skan 66690075Sobrienvoid * 66790075Sobrienuu_list_next(uu_list_t *lp, void *elem) 66890075Sobrien{ 66990075Sobrien uu_list_node_impl_t *n = ELEM_TO_NODE(lp, elem); 67090075Sobrien 67190075Sobrien n = n->uln_next; 67290075Sobrien if (n == &lp->ul_null_node) 67390075Sobrien return (NULL); 674132718Skan return (NODE_TO_ELEM(lp, n)); 67590075Sobrien} 67690075Sobrien 67790075Sobrienvoid * 67890075Sobrienuu_list_prev(uu_list_t *lp, void *elem) 67990075Sobrien{ 68090075Sobrien uu_list_node_impl_t *n = ELEM_TO_NODE(lp, elem); 68190075Sobrien 68290075Sobrien n = n->uln_prev; 683169689Skan if (n == &lp->ul_null_node) 684169689Skan return (NULL); 685169689Skan return (NODE_TO_ELEM(lp, n)); 68690075Sobrien} 687132718Skan 68890075Sobrien/* 68990075Sobrien * called from uu_lockup() and uu_release(), as part of our fork1()-safety. 690117395Skan */ 69190075Sobrienvoid 692117395Skanuu_list_lockup(void) 693117395Skan{ 69490075Sobrien uu_list_pool_t *pp; 69590075Sobrien 69690075Sobrien (void) pthread_mutex_lock(&uu_lpool_list_lock); 69790075Sobrien for (pp = uu_null_lpool.ulp_next; pp != &uu_null_lpool; 69890075Sobrien pp = pp->ulp_next) 69990075Sobrien (void) pthread_mutex_lock(&pp->ulp_lock); 700132718Skan} 70190075Sobrien 702117395Skanvoid 70390075Sobrienuu_list_release(void) 704117395Skan{ 705117395Skan uu_list_pool_t *pp; 70690075Sobrien 70790075Sobrien for (pp = uu_null_lpool.ulp_next; pp != &uu_null_lpool; 70890075Sobrien pp = pp->ulp_next) 70990075Sobrien (void) pthread_mutex_unlock(&pp->ulp_lock); 71090075Sobrien (void) pthread_mutex_unlock(&uu_lpool_list_lock); 71190075Sobrien} 712132718Skan