uu_list.c revision 168404
1168404Spjd/* 2168404Spjd * CDDL HEADER START 3168404Spjd * 4168404Spjd * The contents of this file are subject to the terms of the 5168404Spjd * Common Development and Distribution License, Version 1.0 only 6168404Spjd * (the "License"). You may not use this file except in compliance 7168404Spjd * with the License. 8168404Spjd * 9168404Spjd * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10168404Spjd * or http://www.opensolaris.org/os/licensing. 11168404Spjd * See the License for the specific language governing permissions 12168404Spjd * and limitations under the License. 13168404Spjd * 14168404Spjd * When distributing Covered Code, include this CDDL HEADER in each 15168404Spjd * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16168404Spjd * If applicable, add the following below this CDDL HEADER, with the 17168404Spjd * fields enclosed by brackets "[]" replaced with your own identifying 18168404Spjd * information: Portions Copyright [yyyy] [name of copyright owner] 19168404Spjd * 20168404Spjd * CDDL HEADER END 21168404Spjd */ 22168404Spjd/* 23168404Spjd * Copyright 2005 Sun Microsystems, Inc. All rights reserved. 24168404Spjd * Use is subject to license terms. 25168404Spjd */ 26168404Spjd 27168404Spjd#pragma ident "%Z%%M% %I% %E% SMI" 28168404Spjd 29168404Spjd#include "libuutil_common.h" 30168404Spjd 31168404Spjd#include <stdlib.h> 32168404Spjd#include <string.h> 33168404Spjd#include <unistd.h> 34168404Spjd#include <sys/time.h> 35168404Spjd 36168404Spjd#define ELEM_TO_NODE(lp, e) \ 37168404Spjd ((uu_list_node_impl_t *)((uintptr_t)(e) + (lp)->ul_offset)) 38168404Spjd 39168404Spjd#define NODE_TO_ELEM(lp, n) \ 40168404Spjd ((void *)((uintptr_t)(n) - (lp)->ul_offset)) 41168404Spjd 42168404Spjd/* 43168404Spjd * uu_list_index_ts define a location for insertion. They are simply a 44168404Spjd * pointer to the object after the insertion point. We store a mark 45168404Spjd * in the low-bits of the index, to help prevent mistakes. 46168404Spjd * 47168404Spjd * When debugging, the index mark changes on every insert and delete, to 48168404Spjd * catch stale references. 49168404Spjd */ 50168404Spjd#define INDEX_MAX (sizeof (uintptr_t) - 1) 51168404Spjd#define INDEX_NEXT(m) (((m) == INDEX_MAX)? 1 : ((m) + 1) & INDEX_MAX) 52168404Spjd 53168404Spjd#define INDEX_TO_NODE(i) ((uu_list_node_impl_t *)((i) & ~INDEX_MAX)) 54168404Spjd#define NODE_TO_INDEX(p, n) (((uintptr_t)(n) & ~INDEX_MAX) | (p)->ul_index) 55168404Spjd#define INDEX_VALID(p, i) (((i) & INDEX_MAX) == (p)->ul_index) 56168404Spjd#define INDEX_CHECK(i) (((i) & INDEX_MAX) != 0) 57168404Spjd 58168404Spjd#define POOL_TO_MARKER(pp) ((void *)((uintptr_t)(pp) | 1)) 59168404Spjd 60168404Spjdstatic uu_list_pool_t uu_null_lpool = { &uu_null_lpool, &uu_null_lpool }; 61168404Spjdstatic pthread_mutex_t uu_lpool_list_lock = PTHREAD_MUTEX_INITIALIZER; 62168404Spjd 63168404Spjduu_list_pool_t * 64168404Spjduu_list_pool_create(const char *name, size_t objsize, 65168404Spjd size_t nodeoffset, uu_compare_fn_t *compare_func, uint32_t flags) 66168404Spjd{ 67168404Spjd uu_list_pool_t *pp, *next, *prev; 68168404Spjd 69168404Spjd if (name == NULL || 70168404Spjd uu_check_name(name, UU_NAME_DOMAIN) == -1 || 71168404Spjd nodeoffset + sizeof (uu_list_node_t) > objsize) { 72168404Spjd uu_set_error(UU_ERROR_INVALID_ARGUMENT); 73168404Spjd return (NULL); 74168404Spjd } 75168404Spjd 76168404Spjd if (flags & ~UU_LIST_POOL_DEBUG) { 77168404Spjd uu_set_error(UU_ERROR_UNKNOWN_FLAG); 78168404Spjd return (NULL); 79168404Spjd } 80168404Spjd 81168404Spjd pp = uu_zalloc(sizeof (uu_list_pool_t)); 82168404Spjd if (pp == NULL) { 83168404Spjd uu_set_error(UU_ERROR_NO_MEMORY); 84168404Spjd return (NULL); 85168404Spjd } 86168404Spjd 87168404Spjd (void) strlcpy(pp->ulp_name, name, sizeof (pp->ulp_name)); 88168404Spjd pp->ulp_nodeoffset = nodeoffset; 89168404Spjd pp->ulp_objsize = objsize; 90168404Spjd pp->ulp_cmp = compare_func; 91168404Spjd if (flags & UU_LIST_POOL_DEBUG) 92168404Spjd pp->ulp_debug = 1; 93168404Spjd pp->ulp_last_index = 0; 94168404Spjd 95168404Spjd (void) pthread_mutex_init(&pp->ulp_lock, NULL); 96168404Spjd 97168404Spjd pp->ulp_null_list.ul_next_enc = UU_PTR_ENCODE(&pp->ulp_null_list); 98168404Spjd pp->ulp_null_list.ul_prev_enc = UU_PTR_ENCODE(&pp->ulp_null_list); 99168404Spjd 100168404Spjd (void) pthread_mutex_lock(&uu_lpool_list_lock); 101168404Spjd pp->ulp_next = next = &uu_null_lpool; 102168404Spjd pp->ulp_prev = prev = next->ulp_prev; 103168404Spjd next->ulp_prev = pp; 104168404Spjd prev->ulp_next = pp; 105168404Spjd (void) pthread_mutex_unlock(&uu_lpool_list_lock); 106168404Spjd 107168404Spjd return (pp); 108168404Spjd} 109168404Spjd 110168404Spjdvoid 111168404Spjduu_list_pool_destroy(uu_list_pool_t *pp) 112168404Spjd{ 113168404Spjd if (pp->ulp_debug) { 114168404Spjd if (pp->ulp_null_list.ul_next_enc != 115168404Spjd UU_PTR_ENCODE(&pp->ulp_null_list) || 116168404Spjd pp->ulp_null_list.ul_prev_enc != 117168404Spjd UU_PTR_ENCODE(&pp->ulp_null_list)) { 118168404Spjd uu_panic("uu_list_pool_destroy: Pool \"%.*s\" (%p) has " 119168404Spjd "outstanding lists, or is corrupt.\n", 120168404Spjd sizeof (pp->ulp_name), pp->ulp_name, pp); 121168404Spjd } 122168404Spjd } 123168404Spjd (void) pthread_mutex_lock(&uu_lpool_list_lock); 124168404Spjd pp->ulp_next->ulp_prev = pp->ulp_prev; 125168404Spjd pp->ulp_prev->ulp_next = pp->ulp_next; 126168404Spjd (void) pthread_mutex_unlock(&uu_lpool_list_lock); 127168404Spjd pp->ulp_prev = NULL; 128168404Spjd pp->ulp_next = NULL; 129168404Spjd uu_free(pp); 130168404Spjd} 131168404Spjd 132168404Spjdvoid 133168404Spjduu_list_node_init(void *base, uu_list_node_t *np_arg, uu_list_pool_t *pp) 134168404Spjd{ 135168404Spjd uu_list_node_impl_t *np = (uu_list_node_impl_t *)np_arg; 136168404Spjd 137168404Spjd if (pp->ulp_debug) { 138168404Spjd uintptr_t offset = (uintptr_t)np - (uintptr_t)base; 139168404Spjd if (offset + sizeof (*np) > pp->ulp_objsize) { 140168404Spjd uu_panic("uu_list_node_init(%p, %p, %p (\"%s\")): " 141168404Spjd "offset %ld doesn't fit in object (size %ld)\n", 142168404Spjd base, np, pp, pp->ulp_name, offset, 143168404Spjd pp->ulp_objsize); 144168404Spjd } 145168404Spjd if (offset != pp->ulp_nodeoffset) { 146168404Spjd uu_panic("uu_list_node_init(%p, %p, %p (\"%s\")): " 147168404Spjd "offset %ld doesn't match pool's offset (%ld)\n", 148168404Spjd base, np, pp, pp->ulp_name, offset, 149168404Spjd pp->ulp_objsize); 150168404Spjd } 151168404Spjd } 152168404Spjd np->uln_next = POOL_TO_MARKER(pp); 153168404Spjd np->uln_prev = NULL; 154168404Spjd} 155168404Spjd 156168404Spjdvoid 157168404Spjduu_list_node_fini(void *base, uu_list_node_t *np_arg, uu_list_pool_t *pp) 158168404Spjd{ 159168404Spjd uu_list_node_impl_t *np = (uu_list_node_impl_t *)np_arg; 160168404Spjd 161168404Spjd if (pp->ulp_debug) { 162168404Spjd if (np->uln_next == NULL && 163168404Spjd np->uln_prev == NULL) { 164168404Spjd uu_panic("uu_list_node_fini(%p, %p, %p (\"%s\")): " 165168404Spjd "node already finied\n", 166168404Spjd base, np_arg, pp, pp->ulp_name); 167168404Spjd } 168168404Spjd if (np->uln_next != POOL_TO_MARKER(pp) || 169168404Spjd np->uln_prev != NULL) { 170168404Spjd uu_panic("uu_list_node_fini(%p, %p, %p (\"%s\")): " 171168404Spjd "node corrupt or on list\n", 172168404Spjd base, np_arg, pp, pp->ulp_name); 173168404Spjd } 174168404Spjd } 175168404Spjd np->uln_next = NULL; 176168404Spjd np->uln_prev = NULL; 177168404Spjd} 178168404Spjd 179168404Spjduu_list_t * 180168404Spjduu_list_create(uu_list_pool_t *pp, void *parent, uint32_t flags) 181168404Spjd{ 182168404Spjd uu_list_t *lp, *next, *prev; 183168404Spjd 184168404Spjd if (flags & ~(UU_LIST_DEBUG | UU_LIST_SORTED)) { 185168404Spjd uu_set_error(UU_ERROR_UNKNOWN_FLAG); 186168404Spjd return (NULL); 187168404Spjd } 188168404Spjd 189168404Spjd if ((flags & UU_LIST_SORTED) && pp->ulp_cmp == NULL) { 190168404Spjd if (pp->ulp_debug) 191168404Spjd uu_panic("uu_list_create(%p, ...): requested " 192168404Spjd "UU_LIST_SORTED, but pool has no comparison func\n", 193168404Spjd pp); 194168404Spjd uu_set_error(UU_ERROR_NOT_SUPPORTED); 195168404Spjd return (NULL); 196168404Spjd } 197168404Spjd 198168404Spjd lp = uu_zalloc(sizeof (*lp)); 199168404Spjd if (lp == NULL) { 200168404Spjd uu_set_error(UU_ERROR_NO_MEMORY); 201168404Spjd return (NULL); 202168404Spjd } 203168404Spjd 204168404Spjd lp->ul_pool = pp; 205168404Spjd lp->ul_parent_enc = UU_PTR_ENCODE(parent); 206168404Spjd lp->ul_offset = pp->ulp_nodeoffset; 207168404Spjd lp->ul_debug = pp->ulp_debug || (flags & UU_LIST_DEBUG); 208168404Spjd lp->ul_sorted = (flags & UU_LIST_SORTED); 209168404Spjd lp->ul_numnodes = 0; 210168404Spjd lp->ul_index = (pp->ulp_last_index = INDEX_NEXT(pp->ulp_last_index)); 211168404Spjd 212168404Spjd lp->ul_null_node.uln_next = &lp->ul_null_node; 213168404Spjd lp->ul_null_node.uln_prev = &lp->ul_null_node; 214168404Spjd 215168404Spjd lp->ul_null_walk.ulw_next = &lp->ul_null_walk; 216168404Spjd lp->ul_null_walk.ulw_prev = &lp->ul_null_walk; 217168404Spjd 218168404Spjd (void) pthread_mutex_lock(&pp->ulp_lock); 219168404Spjd next = &pp->ulp_null_list; 220168404Spjd prev = UU_PTR_DECODE(next->ul_prev_enc); 221168404Spjd lp->ul_next_enc = UU_PTR_ENCODE(next); 222168404Spjd lp->ul_prev_enc = UU_PTR_ENCODE(prev); 223168404Spjd next->ul_prev_enc = UU_PTR_ENCODE(lp); 224168404Spjd prev->ul_next_enc = UU_PTR_ENCODE(lp); 225168404Spjd (void) pthread_mutex_unlock(&pp->ulp_lock); 226168404Spjd 227168404Spjd return (lp); 228168404Spjd} 229168404Spjd 230168404Spjdvoid 231168404Spjduu_list_destroy(uu_list_t *lp) 232168404Spjd{ 233168404Spjd uu_list_pool_t *pp = lp->ul_pool; 234168404Spjd 235168404Spjd if (lp->ul_debug) { 236168404Spjd if (lp->ul_null_node.uln_next != &lp->ul_null_node || 237168404Spjd lp->ul_null_node.uln_prev != &lp->ul_null_node) { 238168404Spjd uu_panic("uu_list_destroy(%p): list not empty\n", 239168404Spjd lp); 240168404Spjd } 241168404Spjd if (lp->ul_numnodes != 0) { 242168404Spjd uu_panic("uu_list_destroy(%p): numnodes is nonzero, " 243168404Spjd "but list is empty\n", lp); 244168404Spjd } 245168404Spjd if (lp->ul_null_walk.ulw_next != &lp->ul_null_walk || 246168404Spjd lp->ul_null_walk.ulw_prev != &lp->ul_null_walk) { 247168404Spjd uu_panic("uu_list_destroy(%p): outstanding walkers\n", 248168404Spjd lp); 249168404Spjd } 250168404Spjd } 251168404Spjd 252168404Spjd (void) pthread_mutex_lock(&pp->ulp_lock); 253168404Spjd UU_LIST_PTR(lp->ul_next_enc)->ul_prev_enc = lp->ul_prev_enc; 254168404Spjd UU_LIST_PTR(lp->ul_prev_enc)->ul_next_enc = lp->ul_next_enc; 255168404Spjd (void) pthread_mutex_unlock(&pp->ulp_lock); 256168404Spjd lp->ul_prev_enc = UU_PTR_ENCODE(NULL); 257168404Spjd lp->ul_next_enc = UU_PTR_ENCODE(NULL); 258168404Spjd lp->ul_pool = NULL; 259168404Spjd uu_free(lp); 260168404Spjd} 261168404Spjd 262168404Spjdstatic void 263168404Spjdlist_insert(uu_list_t *lp, uu_list_node_impl_t *np, uu_list_node_impl_t *prev, 264168404Spjd uu_list_node_impl_t *next) 265168404Spjd{ 266168404Spjd if (lp->ul_debug) { 267168404Spjd if (next->uln_prev != prev || prev->uln_next != next) 268168404Spjd uu_panic("insert(%p): internal error: %p and %p not " 269168404Spjd "neighbors\n", lp, next, prev); 270168404Spjd 271168404Spjd if (np->uln_next != POOL_TO_MARKER(lp->ul_pool) || 272168404Spjd np->uln_prev != NULL) { 273168404Spjd uu_panic("insert(%p): elem %p node %p corrupt, " 274168404Spjd "not initialized, or already in a list.\n", 275168404Spjd lp, NODE_TO_ELEM(lp, np), np); 276168404Spjd } 277168404Spjd /* 278168404Spjd * invalidate outstanding uu_list_index_ts. 279168404Spjd */ 280168404Spjd lp->ul_index = INDEX_NEXT(lp->ul_index); 281168404Spjd } 282168404Spjd np->uln_next = next; 283168404Spjd np->uln_prev = prev; 284168404Spjd next->uln_prev = np; 285168404Spjd prev->uln_next = np; 286168404Spjd 287168404Spjd lp->ul_numnodes++; 288168404Spjd} 289168404Spjd 290168404Spjdvoid 291168404Spjduu_list_insert(uu_list_t *lp, void *elem, uu_list_index_t idx) 292168404Spjd{ 293168404Spjd uu_list_node_impl_t *np; 294168404Spjd 295168404Spjd np = INDEX_TO_NODE(idx); 296168404Spjd if (np == NULL) 297168404Spjd np = &lp->ul_null_node; 298168404Spjd 299168404Spjd if (lp->ul_debug) { 300168404Spjd if (!INDEX_VALID(lp, idx)) 301168404Spjd uu_panic("uu_list_insert(%p, %p, %p): %s\n", 302168404Spjd lp, elem, idx, 303168404Spjd INDEX_CHECK(idx)? "outdated index" : 304168404Spjd "invalid index"); 305168404Spjd if (np->uln_prev == NULL) 306168404Spjd uu_panic("uu_list_insert(%p, %p, %p): out-of-date " 307168404Spjd "index\n", lp, elem, idx); 308168404Spjd } 309168404Spjd 310168404Spjd list_insert(lp, ELEM_TO_NODE(lp, elem), np->uln_prev, np); 311168404Spjd} 312168404Spjd 313168404Spjdvoid * 314168404Spjduu_list_find(uu_list_t *lp, void *elem, void *private, uu_list_index_t *out) 315168404Spjd{ 316168404Spjd int sorted = lp->ul_sorted; 317168404Spjd uu_compare_fn_t *func = lp->ul_pool->ulp_cmp; 318168404Spjd uu_list_node_impl_t *np; 319168404Spjd 320168404Spjd if (func == NULL) { 321168404Spjd if (out != NULL) 322168404Spjd *out = 0; 323168404Spjd uu_set_error(UU_ERROR_NOT_SUPPORTED); 324168404Spjd return (NULL); 325168404Spjd } 326168404Spjd for (np = lp->ul_null_node.uln_next; np != &lp->ul_null_node; 327168404Spjd np = np->uln_next) { 328168404Spjd void *ep = NODE_TO_ELEM(lp, np); 329168404Spjd int cmp = func(ep, elem, private); 330168404Spjd if (cmp == 0) { 331168404Spjd if (out != NULL) 332168404Spjd *out = NODE_TO_INDEX(lp, np); 333168404Spjd return (ep); 334168404Spjd } 335168404Spjd if (sorted && cmp > 0) { 336168404Spjd if (out != NULL) 337168404Spjd *out = NODE_TO_INDEX(lp, np); 338168404Spjd return (NULL); 339168404Spjd } 340168404Spjd } 341168404Spjd if (out != NULL) 342168404Spjd *out = NODE_TO_INDEX(lp, 0); 343168404Spjd return (NULL); 344168404Spjd} 345168404Spjd 346168404Spjdvoid * 347168404Spjduu_list_nearest_next(uu_list_t *lp, uu_list_index_t idx) 348168404Spjd{ 349168404Spjd uu_list_node_impl_t *np = INDEX_TO_NODE(idx); 350168404Spjd 351168404Spjd if (np == NULL) 352168404Spjd np = &lp->ul_null_node; 353168404Spjd 354168404Spjd if (lp->ul_debug) { 355168404Spjd if (!INDEX_VALID(lp, idx)) 356168404Spjd uu_panic("uu_list_nearest_next(%p, %p): %s\n", 357168404Spjd lp, idx, INDEX_CHECK(idx)? "outdated index" : 358168404Spjd "invalid index"); 359168404Spjd if (np->uln_prev == NULL) 360168404Spjd uu_panic("uu_list_nearest_next(%p, %p): out-of-date " 361168404Spjd "index\n", lp, idx); 362168404Spjd } 363168404Spjd 364168404Spjd if (np == &lp->ul_null_node) 365168404Spjd return (NULL); 366168404Spjd else 367168404Spjd return (NODE_TO_ELEM(lp, np)); 368168404Spjd} 369168404Spjd 370168404Spjdvoid * 371168404Spjduu_list_nearest_prev(uu_list_t *lp, uu_list_index_t idx) 372168404Spjd{ 373168404Spjd uu_list_node_impl_t *np = INDEX_TO_NODE(idx); 374168404Spjd 375168404Spjd if (np == NULL) 376168404Spjd np = &lp->ul_null_node; 377168404Spjd 378168404Spjd if (lp->ul_debug) { 379168404Spjd if (!INDEX_VALID(lp, idx)) 380168404Spjd uu_panic("uu_list_nearest_prev(%p, %p): %s\n", 381168404Spjd lp, idx, INDEX_CHECK(idx)? "outdated index" : 382168404Spjd "invalid index"); 383168404Spjd if (np->uln_prev == NULL) 384168404Spjd uu_panic("uu_list_nearest_prev(%p, %p): out-of-date " 385168404Spjd "index\n", lp, idx); 386168404Spjd } 387168404Spjd 388168404Spjd if ((np = np->uln_prev) == &lp->ul_null_node) 389168404Spjd return (NULL); 390168404Spjd else 391168404Spjd return (NODE_TO_ELEM(lp, np)); 392168404Spjd} 393168404Spjd 394168404Spjdstatic void 395168404Spjdlist_walk_init(uu_list_walk_t *wp, uu_list_t *lp, uint32_t flags) 396168404Spjd{ 397168404Spjd uu_list_walk_t *next, *prev; 398168404Spjd 399168404Spjd int robust = (flags & UU_WALK_ROBUST); 400168404Spjd int direction = (flags & UU_WALK_REVERSE)? -1 : 1; 401168404Spjd 402168404Spjd (void) memset(wp, 0, sizeof (*wp)); 403168404Spjd wp->ulw_list = lp; 404168404Spjd wp->ulw_robust = robust; 405168404Spjd wp->ulw_dir = direction; 406168404Spjd if (direction > 0) 407168404Spjd wp->ulw_next_result = lp->ul_null_node.uln_next; 408168404Spjd else 409168404Spjd wp->ulw_next_result = lp->ul_null_node.uln_prev; 410168404Spjd 411168404Spjd if (lp->ul_debug || robust) { 412168404Spjd wp->ulw_next = next = &lp->ul_null_walk; 413168404Spjd wp->ulw_prev = prev = next->ulw_prev; 414168404Spjd next->ulw_prev = wp; 415168404Spjd prev->ulw_next = wp; 416168404Spjd } 417168404Spjd} 418168404Spjd 419168404Spjdstatic uu_list_node_impl_t * 420168404Spjdlist_walk_advance(uu_list_walk_t *wp, uu_list_t *lp) 421168404Spjd{ 422168404Spjd uu_list_node_impl_t *np = wp->ulw_next_result; 423168404Spjd uu_list_node_impl_t *next; 424168404Spjd 425168404Spjd if (np == &lp->ul_null_node) 426168404Spjd return (NULL); 427168404Spjd 428168404Spjd next = (wp->ulw_dir > 0)? np->uln_next : np->uln_prev; 429168404Spjd 430168404Spjd wp->ulw_next_result = next; 431168404Spjd return (np); 432168404Spjd} 433168404Spjd 434168404Spjdstatic void 435168404Spjdlist_walk_fini(uu_list_walk_t *wp) 436168404Spjd{ 437168404Spjd /* GLXXX debugging? */ 438168404Spjd if (wp->ulw_next != NULL) { 439168404Spjd wp->ulw_next->ulw_prev = wp->ulw_prev; 440168404Spjd wp->ulw_prev->ulw_next = wp->ulw_next; 441168404Spjd wp->ulw_next = NULL; 442168404Spjd wp->ulw_prev = NULL; 443168404Spjd } 444168404Spjd wp->ulw_list = NULL; 445168404Spjd wp->ulw_next_result = NULL; 446168404Spjd} 447168404Spjd 448168404Spjduu_list_walk_t * 449168404Spjduu_list_walk_start(uu_list_t *lp, uint32_t flags) 450168404Spjd{ 451168404Spjd uu_list_walk_t *wp; 452168404Spjd 453168404Spjd if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) { 454168404Spjd uu_set_error(UU_ERROR_UNKNOWN_FLAG); 455168404Spjd return (NULL); 456168404Spjd } 457168404Spjd 458168404Spjd wp = uu_zalloc(sizeof (*wp)); 459168404Spjd if (wp == NULL) { 460168404Spjd uu_set_error(UU_ERROR_NO_MEMORY); 461168404Spjd return (NULL); 462168404Spjd } 463168404Spjd 464168404Spjd list_walk_init(wp, lp, flags); 465168404Spjd return (wp); 466168404Spjd} 467168404Spjd 468168404Spjdvoid * 469168404Spjduu_list_walk_next(uu_list_walk_t *wp) 470168404Spjd{ 471168404Spjd uu_list_t *lp = wp->ulw_list; 472168404Spjd uu_list_node_impl_t *np = list_walk_advance(wp, lp); 473168404Spjd 474168404Spjd if (np == NULL) 475168404Spjd return (NULL); 476168404Spjd 477168404Spjd return (NODE_TO_ELEM(lp, np)); 478168404Spjd} 479168404Spjd 480168404Spjdvoid 481168404Spjduu_list_walk_end(uu_list_walk_t *wp) 482168404Spjd{ 483168404Spjd list_walk_fini(wp); 484168404Spjd uu_free(wp); 485168404Spjd} 486168404Spjd 487168404Spjdint 488168404Spjduu_list_walk(uu_list_t *lp, uu_walk_fn_t *func, void *private, uint32_t flags) 489168404Spjd{ 490168404Spjd uu_list_node_impl_t *np; 491168404Spjd 492168404Spjd int status = UU_WALK_NEXT; 493168404Spjd 494168404Spjd int robust = (flags & UU_WALK_ROBUST); 495168404Spjd int reverse = (flags & UU_WALK_REVERSE); 496168404Spjd 497168404Spjd if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) { 498168404Spjd uu_set_error(UU_ERROR_UNKNOWN_FLAG); 499168404Spjd return (-1); 500168404Spjd } 501168404Spjd 502168404Spjd if (lp->ul_debug || robust) { 503168404Spjd uu_list_walk_t my_walk; 504168404Spjd void *e; 505168404Spjd 506168404Spjd list_walk_init(&my_walk, lp, flags); 507168404Spjd while (status == UU_WALK_NEXT && 508168404Spjd (e = uu_list_walk_next(&my_walk)) != NULL) 509168404Spjd status = (*func)(e, private); 510168404Spjd list_walk_fini(&my_walk); 511168404Spjd } else { 512168404Spjd if (!reverse) { 513168404Spjd for (np = lp->ul_null_node.uln_next; 514168404Spjd status == UU_WALK_NEXT && np != &lp->ul_null_node; 515168404Spjd np = np->uln_next) { 516168404Spjd status = (*func)(NODE_TO_ELEM(lp, np), private); 517168404Spjd } 518168404Spjd } else { 519168404Spjd for (np = lp->ul_null_node.uln_prev; 520168404Spjd status == UU_WALK_NEXT && np != &lp->ul_null_node; 521168404Spjd np = np->uln_prev) { 522168404Spjd status = (*func)(NODE_TO_ELEM(lp, np), private); 523168404Spjd } 524168404Spjd } 525168404Spjd } 526168404Spjd if (status >= 0) 527168404Spjd return (0); 528168404Spjd uu_set_error(UU_ERROR_CALLBACK_FAILED); 529168404Spjd return (-1); 530168404Spjd} 531168404Spjd 532168404Spjdvoid 533168404Spjduu_list_remove(uu_list_t *lp, void *elem) 534168404Spjd{ 535168404Spjd uu_list_node_impl_t *np = ELEM_TO_NODE(lp, elem); 536168404Spjd uu_list_walk_t *wp; 537168404Spjd 538168404Spjd if (lp->ul_debug) { 539168404Spjd if (np->uln_prev == NULL) 540168404Spjd uu_panic("uu_list_remove(%p, %p): elem not on list\n", 541168404Spjd lp, elem); 542168404Spjd /* 543168404Spjd * invalidate outstanding uu_list_index_ts. 544168404Spjd */ 545168404Spjd lp->ul_index = INDEX_NEXT(lp->ul_index); 546168404Spjd } 547168404Spjd 548168404Spjd /* 549168404Spjd * robust walkers must be advanced. In debug mode, non-robust 550168404Spjd * walkers are also on the list. If there are any, it's an error. 551168404Spjd */ 552168404Spjd for (wp = lp->ul_null_walk.ulw_next; wp != &lp->ul_null_walk; 553168404Spjd wp = wp->ulw_next) { 554168404Spjd if (wp->ulw_robust) { 555168404Spjd if (np == wp->ulw_next_result) 556168404Spjd (void) list_walk_advance(wp, lp); 557168404Spjd } else if (wp->ulw_next_result != NULL) { 558168404Spjd uu_panic("uu_list_remove(%p, %p): active non-robust " 559168404Spjd "walker\n", lp, elem); 560168404Spjd } 561168404Spjd } 562168404Spjd 563168404Spjd np->uln_next->uln_prev = np->uln_prev; 564168404Spjd np->uln_prev->uln_next = np->uln_next; 565168404Spjd 566168404Spjd lp->ul_numnodes--; 567168404Spjd 568168404Spjd np->uln_next = POOL_TO_MARKER(lp->ul_pool); 569168404Spjd np->uln_prev = NULL; 570168404Spjd} 571168404Spjd 572168404Spjdvoid * 573168404Spjduu_list_teardown(uu_list_t *lp, void **cookie) 574168404Spjd{ 575168404Spjd void *ep; 576168404Spjd 577168404Spjd /* 578168404Spjd * XXX: disable list modification until list is empty 579168404Spjd */ 580168404Spjd if (lp->ul_debug && *cookie != NULL) 581168404Spjd uu_panic("uu_list_teardown(%p, %p): unexpected cookie\n", lp, 582168404Spjd cookie); 583168404Spjd 584168404Spjd ep = uu_list_first(lp); 585168404Spjd if (ep) 586168404Spjd uu_list_remove(lp, ep); 587168404Spjd return (ep); 588168404Spjd} 589168404Spjd 590168404Spjdint 591168404Spjduu_list_insert_before(uu_list_t *lp, void *target, void *elem) 592168404Spjd{ 593168404Spjd uu_list_node_impl_t *np = ELEM_TO_NODE(lp, target); 594168404Spjd 595168404Spjd if (target == NULL) 596168404Spjd np = &lp->ul_null_node; 597168404Spjd 598168404Spjd if (lp->ul_debug) { 599168404Spjd if (np->uln_prev == NULL) 600168404Spjd uu_panic("uu_list_insert_before(%p, %p, %p): %p is " 601168404Spjd "not currently on a list\n", 602168404Spjd lp, target, elem, target); 603168404Spjd } 604168404Spjd if (lp->ul_sorted) { 605168404Spjd if (lp->ul_debug) 606168404Spjd uu_panic("uu_list_insert_before(%p, ...): list is " 607168404Spjd "UU_LIST_SORTED\n", lp); 608168404Spjd uu_set_error(UU_ERROR_NOT_SUPPORTED); 609168404Spjd return (-1); 610168404Spjd } 611168404Spjd 612168404Spjd list_insert(lp, ELEM_TO_NODE(lp, elem), np->uln_prev, np); 613168404Spjd return (0); 614168404Spjd} 615168404Spjd 616168404Spjdint 617168404Spjduu_list_insert_after(uu_list_t *lp, void *target, void *elem) 618168404Spjd{ 619168404Spjd uu_list_node_impl_t *np = ELEM_TO_NODE(lp, target); 620168404Spjd 621168404Spjd if (target == NULL) 622168404Spjd np = &lp->ul_null_node; 623168404Spjd 624168404Spjd if (lp->ul_debug) { 625168404Spjd if (np->uln_prev == NULL) 626168404Spjd uu_panic("uu_list_insert_after(%p, %p, %p): %p is " 627168404Spjd "not currently on a list\n", 628168404Spjd lp, target, elem, target); 629168404Spjd } 630168404Spjd if (lp->ul_sorted) { 631168404Spjd if (lp->ul_debug) 632168404Spjd uu_panic("uu_list_insert_after(%p, ...): list is " 633168404Spjd "UU_LIST_SORTED\n", lp); 634168404Spjd uu_set_error(UU_ERROR_NOT_SUPPORTED); 635168404Spjd return (-1); 636168404Spjd } 637168404Spjd 638168404Spjd list_insert(lp, ELEM_TO_NODE(lp, elem), np, np->uln_next); 639168404Spjd return (0); 640168404Spjd} 641168404Spjd 642168404Spjdsize_t 643168404Spjduu_list_numnodes(uu_list_t *lp) 644168404Spjd{ 645168404Spjd return (lp->ul_numnodes); 646168404Spjd} 647168404Spjd 648168404Spjdvoid * 649168404Spjduu_list_first(uu_list_t *lp) 650168404Spjd{ 651168404Spjd uu_list_node_impl_t *n = lp->ul_null_node.uln_next; 652168404Spjd if (n == &lp->ul_null_node) 653168404Spjd return (NULL); 654168404Spjd return (NODE_TO_ELEM(lp, n)); 655168404Spjd} 656168404Spjd 657168404Spjdvoid * 658168404Spjduu_list_last(uu_list_t *lp) 659168404Spjd{ 660168404Spjd uu_list_node_impl_t *n = lp->ul_null_node.uln_prev; 661168404Spjd if (n == &lp->ul_null_node) 662168404Spjd return (NULL); 663168404Spjd return (NODE_TO_ELEM(lp, n)); 664168404Spjd} 665168404Spjd 666168404Spjdvoid * 667168404Spjduu_list_next(uu_list_t *lp, void *elem) 668168404Spjd{ 669168404Spjd uu_list_node_impl_t *n = ELEM_TO_NODE(lp, elem); 670168404Spjd 671168404Spjd n = n->uln_next; 672168404Spjd if (n == &lp->ul_null_node) 673168404Spjd return (NULL); 674168404Spjd return (NODE_TO_ELEM(lp, n)); 675168404Spjd} 676168404Spjd 677168404Spjdvoid * 678168404Spjduu_list_prev(uu_list_t *lp, void *elem) 679168404Spjd{ 680168404Spjd uu_list_node_impl_t *n = ELEM_TO_NODE(lp, elem); 681168404Spjd 682168404Spjd n = n->uln_prev; 683168404Spjd if (n == &lp->ul_null_node) 684168404Spjd return (NULL); 685168404Spjd return (NODE_TO_ELEM(lp, n)); 686168404Spjd} 687168404Spjd 688168404Spjd/* 689168404Spjd * called from uu_lockup() and uu_release(), as part of our fork1()-safety. 690168404Spjd */ 691168404Spjdvoid 692168404Spjduu_list_lockup(void) 693168404Spjd{ 694168404Spjd uu_list_pool_t *pp; 695168404Spjd 696168404Spjd (void) pthread_mutex_lock(&uu_lpool_list_lock); 697168404Spjd for (pp = uu_null_lpool.ulp_next; pp != &uu_null_lpool; 698168404Spjd pp = pp->ulp_next) 699168404Spjd (void) pthread_mutex_lock(&pp->ulp_lock); 700168404Spjd} 701168404Spjd 702168404Spjdvoid 703168404Spjduu_list_release(void) 704168404Spjd{ 705168404Spjd uu_list_pool_t *pp; 706168404Spjd 707168404Spjd for (pp = uu_null_lpool.ulp_next; pp != &uu_null_lpool; 708168404Spjd pp = pp->ulp_next) 709168404Spjd (void) pthread_mutex_unlock(&pp->ulp_lock); 710168404Spjd (void) pthread_mutex_unlock(&uu_lpool_list_lock); 711168404Spjd} 712