1168404Spjd/* 2168404Spjd * CDDL HEADER START 3168404Spjd * 4168404Spjd * The contents of this file are subject to the terms of the 5185029Spjd * Common Development and Distribution License (the "License"). 6185029Spjd * You may not use this file except in compliance with the License. 7168404Spjd * 8168404Spjd * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9168404Spjd * or http://www.opensolaris.org/os/licensing. 10168404Spjd * See the License for the specific language governing permissions 11168404Spjd * and limitations under the License. 12168404Spjd * 13168404Spjd * When distributing Covered Code, include this CDDL HEADER in each 14168404Spjd * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15168404Spjd * If applicable, add the following below this CDDL HEADER, with the 16168404Spjd * fields enclosed by brackets "[]" replaced with your own identifying 17168404Spjd * information: Portions Copyright [yyyy] [name of copyright owner] 18168404Spjd * 19168404Spjd * CDDL HEADER END 20168404Spjd */ 21168404Spjd/* 22185029Spjd * Copyright 2008 Sun Microsystems, Inc. All rights reserved. 23168404Spjd * Use is subject to license terms. 24168404Spjd */ 25168404Spjd 26168404Spjd#pragma ident "%Z%%M% %I% %E% SMI" 27168404Spjd 28168404Spjd#include "libuutil_common.h" 29168404Spjd 30168404Spjd#include <stdlib.h> 31168404Spjd#include <string.h> 32168404Spjd#include <unistd.h> 33168404Spjd#include <sys/time.h> 34168404Spjd 35168404Spjd#define ELEM_TO_NODE(lp, e) \ 36168404Spjd ((uu_list_node_impl_t *)((uintptr_t)(e) + (lp)->ul_offset)) 37168404Spjd 38168404Spjd#define NODE_TO_ELEM(lp, n) \ 39168404Spjd ((void *)((uintptr_t)(n) - (lp)->ul_offset)) 40168404Spjd 41168404Spjd/* 42168404Spjd * uu_list_index_ts define a location for insertion. They are simply a 43168404Spjd * pointer to the object after the insertion point. We store a mark 44168404Spjd * in the low-bits of the index, to help prevent mistakes. 45168404Spjd * 46168404Spjd * When debugging, the index mark changes on every insert and delete, to 47168404Spjd * catch stale references. 48168404Spjd */ 49168404Spjd#define INDEX_MAX (sizeof (uintptr_t) - 1) 50168404Spjd#define INDEX_NEXT(m) (((m) == INDEX_MAX)? 1 : ((m) + 1) & INDEX_MAX) 51168404Spjd 52168404Spjd#define INDEX_TO_NODE(i) ((uu_list_node_impl_t *)((i) & ~INDEX_MAX)) 53168404Spjd#define NODE_TO_INDEX(p, n) (((uintptr_t)(n) & ~INDEX_MAX) | (p)->ul_index) 54168404Spjd#define INDEX_VALID(p, i) (((i) & INDEX_MAX) == (p)->ul_index) 55168404Spjd#define INDEX_CHECK(i) (((i) & INDEX_MAX) != 0) 56168404Spjd 57168404Spjd#define POOL_TO_MARKER(pp) ((void *)((uintptr_t)(pp) | 1)) 58168404Spjd 59168404Spjdstatic uu_list_pool_t uu_null_lpool = { &uu_null_lpool, &uu_null_lpool }; 60168404Spjdstatic pthread_mutex_t uu_lpool_list_lock = PTHREAD_MUTEX_INITIALIZER; 61168404Spjd 62168404Spjduu_list_pool_t * 63168404Spjduu_list_pool_create(const char *name, size_t objsize, 64168404Spjd size_t nodeoffset, uu_compare_fn_t *compare_func, uint32_t flags) 65168404Spjd{ 66168404Spjd uu_list_pool_t *pp, *next, *prev; 67168404Spjd 68168404Spjd if (name == NULL || 69168404Spjd uu_check_name(name, UU_NAME_DOMAIN) == -1 || 70168404Spjd nodeoffset + sizeof (uu_list_node_t) > objsize) { 71168404Spjd uu_set_error(UU_ERROR_INVALID_ARGUMENT); 72168404Spjd return (NULL); 73168404Spjd } 74168404Spjd 75168404Spjd if (flags & ~UU_LIST_POOL_DEBUG) { 76168404Spjd uu_set_error(UU_ERROR_UNKNOWN_FLAG); 77168404Spjd return (NULL); 78168404Spjd } 79168404Spjd 80168404Spjd pp = uu_zalloc(sizeof (uu_list_pool_t)); 81168404Spjd if (pp == NULL) { 82168404Spjd uu_set_error(UU_ERROR_NO_MEMORY); 83168404Spjd return (NULL); 84168404Spjd } 85168404Spjd 86168404Spjd (void) strlcpy(pp->ulp_name, name, sizeof (pp->ulp_name)); 87168404Spjd pp->ulp_nodeoffset = nodeoffset; 88168404Spjd pp->ulp_objsize = objsize; 89168404Spjd pp->ulp_cmp = compare_func; 90168404Spjd if (flags & UU_LIST_POOL_DEBUG) 91168404Spjd pp->ulp_debug = 1; 92168404Spjd pp->ulp_last_index = 0; 93168404Spjd 94168404Spjd (void) pthread_mutex_init(&pp->ulp_lock, NULL); 95168404Spjd 96168404Spjd pp->ulp_null_list.ul_next_enc = UU_PTR_ENCODE(&pp->ulp_null_list); 97168404Spjd pp->ulp_null_list.ul_prev_enc = UU_PTR_ENCODE(&pp->ulp_null_list); 98168404Spjd 99168404Spjd (void) pthread_mutex_lock(&uu_lpool_list_lock); 100168404Spjd pp->ulp_next = next = &uu_null_lpool; 101168404Spjd pp->ulp_prev = prev = next->ulp_prev; 102168404Spjd next->ulp_prev = pp; 103168404Spjd prev->ulp_next = pp; 104168404Spjd (void) pthread_mutex_unlock(&uu_lpool_list_lock); 105168404Spjd 106168404Spjd return (pp); 107168404Spjd} 108168404Spjd 109168404Spjdvoid 110168404Spjduu_list_pool_destroy(uu_list_pool_t *pp) 111168404Spjd{ 112168404Spjd if (pp->ulp_debug) { 113168404Spjd if (pp->ulp_null_list.ul_next_enc != 114168404Spjd UU_PTR_ENCODE(&pp->ulp_null_list) || 115168404Spjd pp->ulp_null_list.ul_prev_enc != 116168404Spjd UU_PTR_ENCODE(&pp->ulp_null_list)) { 117168404Spjd uu_panic("uu_list_pool_destroy: Pool \"%.*s\" (%p) has " 118168404Spjd "outstanding lists, or is corrupt.\n", 119185029Spjd (int)sizeof (pp->ulp_name), pp->ulp_name, 120185029Spjd (void *)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", 142185029Spjd base, (void *)np, (void *)pp, pp->ulp_name, 143185029Spjd (long)offset, (long)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", 148185029Spjd base, (void *)np, (void *)pp, pp->ulp_name, 149185029Spjd (long)offset, (long)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", 166185029Spjd base, (void *)np_arg, (void *)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", 172185029Spjd base, (void *)np_arg, (void *)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", 193185029Spjd (void *)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", 239185029Spjd (void *)lp); 240168404Spjd } 241168404Spjd if (lp->ul_numnodes != 0) { 242168404Spjd uu_panic("uu_list_destroy(%p): numnodes is nonzero, " 243185029Spjd "but list is empty\n", (void *)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", 248185029Spjd (void *)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 " 269185029Spjd "neighbors\n", (void *)lp, (void *)next, 270185029Spjd (void *)prev); 271168404Spjd 272168404Spjd if (np->uln_next != POOL_TO_MARKER(lp->ul_pool) || 273168404Spjd np->uln_prev != NULL) { 274168404Spjd uu_panic("insert(%p): elem %p node %p corrupt, " 275168404Spjd "not initialized, or already in a list.\n", 276185029Spjd (void *)lp, NODE_TO_ELEM(lp, np), (void *)np); 277168404Spjd } 278168404Spjd /* 279168404Spjd * invalidate outstanding uu_list_index_ts. 280168404Spjd */ 281168404Spjd lp->ul_index = INDEX_NEXT(lp->ul_index); 282168404Spjd } 283168404Spjd np->uln_next = next; 284168404Spjd np->uln_prev = prev; 285168404Spjd next->uln_prev = np; 286168404Spjd prev->uln_next = np; 287168404Spjd 288168404Spjd lp->ul_numnodes++; 289168404Spjd} 290168404Spjd 291168404Spjdvoid 292168404Spjduu_list_insert(uu_list_t *lp, void *elem, uu_list_index_t idx) 293168404Spjd{ 294168404Spjd uu_list_node_impl_t *np; 295168404Spjd 296168404Spjd np = INDEX_TO_NODE(idx); 297168404Spjd if (np == NULL) 298168404Spjd np = &lp->ul_null_node; 299168404Spjd 300168404Spjd if (lp->ul_debug) { 301168404Spjd if (!INDEX_VALID(lp, idx)) 302168404Spjd uu_panic("uu_list_insert(%p, %p, %p): %s\n", 303185029Spjd (void *)lp, elem, (void *)idx, 304168404Spjd INDEX_CHECK(idx)? "outdated index" : 305168404Spjd "invalid index"); 306168404Spjd if (np->uln_prev == NULL) 307168404Spjd uu_panic("uu_list_insert(%p, %p, %p): out-of-date " 308185029Spjd "index\n", (void *)lp, elem, (void *)idx); 309168404Spjd } 310168404Spjd 311168404Spjd list_insert(lp, ELEM_TO_NODE(lp, elem), np->uln_prev, np); 312168404Spjd} 313168404Spjd 314168404Spjdvoid * 315168404Spjduu_list_find(uu_list_t *lp, void *elem, void *private, uu_list_index_t *out) 316168404Spjd{ 317168404Spjd int sorted = lp->ul_sorted; 318168404Spjd uu_compare_fn_t *func = lp->ul_pool->ulp_cmp; 319168404Spjd uu_list_node_impl_t *np; 320168404Spjd 321168404Spjd if (func == NULL) { 322168404Spjd if (out != NULL) 323168404Spjd *out = 0; 324168404Spjd uu_set_error(UU_ERROR_NOT_SUPPORTED); 325168404Spjd return (NULL); 326168404Spjd } 327168404Spjd for (np = lp->ul_null_node.uln_next; np != &lp->ul_null_node; 328168404Spjd np = np->uln_next) { 329168404Spjd void *ep = NODE_TO_ELEM(lp, np); 330168404Spjd int cmp = func(ep, elem, private); 331168404Spjd if (cmp == 0) { 332168404Spjd if (out != NULL) 333168404Spjd *out = NODE_TO_INDEX(lp, np); 334168404Spjd return (ep); 335168404Spjd } 336168404Spjd if (sorted && cmp > 0) { 337168404Spjd if (out != NULL) 338168404Spjd *out = NODE_TO_INDEX(lp, np); 339168404Spjd return (NULL); 340168404Spjd } 341168404Spjd } 342168404Spjd if (out != NULL) 343168404Spjd *out = NODE_TO_INDEX(lp, 0); 344168404Spjd return (NULL); 345168404Spjd} 346168404Spjd 347168404Spjdvoid * 348168404Spjduu_list_nearest_next(uu_list_t *lp, uu_list_index_t idx) 349168404Spjd{ 350168404Spjd uu_list_node_impl_t *np = INDEX_TO_NODE(idx); 351168404Spjd 352168404Spjd if (np == NULL) 353168404Spjd np = &lp->ul_null_node; 354168404Spjd 355168404Spjd if (lp->ul_debug) { 356168404Spjd if (!INDEX_VALID(lp, idx)) 357168404Spjd uu_panic("uu_list_nearest_next(%p, %p): %s\n", 358185029Spjd (void *)lp, (void *)idx, 359185029Spjd INDEX_CHECK(idx)? "outdated index" : 360168404Spjd "invalid index"); 361168404Spjd if (np->uln_prev == NULL) 362168404Spjd uu_panic("uu_list_nearest_next(%p, %p): out-of-date " 363185029Spjd "index\n", (void *)lp, (void *)idx); 364168404Spjd } 365168404Spjd 366168404Spjd if (np == &lp->ul_null_node) 367168404Spjd return (NULL); 368168404Spjd else 369168404Spjd return (NODE_TO_ELEM(lp, np)); 370168404Spjd} 371168404Spjd 372168404Spjdvoid * 373168404Spjduu_list_nearest_prev(uu_list_t *lp, uu_list_index_t idx) 374168404Spjd{ 375168404Spjd uu_list_node_impl_t *np = INDEX_TO_NODE(idx); 376168404Spjd 377168404Spjd if (np == NULL) 378168404Spjd np = &lp->ul_null_node; 379168404Spjd 380168404Spjd if (lp->ul_debug) { 381168404Spjd if (!INDEX_VALID(lp, idx)) 382168404Spjd uu_panic("uu_list_nearest_prev(%p, %p): %s\n", 383185029Spjd (void *)lp, (void *)idx, INDEX_CHECK(idx)? 384185029Spjd "outdated index" : "invalid index"); 385168404Spjd if (np->uln_prev == NULL) 386168404Spjd uu_panic("uu_list_nearest_prev(%p, %p): out-of-date " 387185029Spjd "index\n", (void *)lp, (void *)idx); 388168404Spjd } 389168404Spjd 390168404Spjd if ((np = np->uln_prev) == &lp->ul_null_node) 391168404Spjd return (NULL); 392168404Spjd else 393168404Spjd return (NODE_TO_ELEM(lp, np)); 394168404Spjd} 395168404Spjd 396168404Spjdstatic void 397168404Spjdlist_walk_init(uu_list_walk_t *wp, uu_list_t *lp, uint32_t flags) 398168404Spjd{ 399168404Spjd uu_list_walk_t *next, *prev; 400168404Spjd 401168404Spjd int robust = (flags & UU_WALK_ROBUST); 402168404Spjd int direction = (flags & UU_WALK_REVERSE)? -1 : 1; 403168404Spjd 404168404Spjd (void) memset(wp, 0, sizeof (*wp)); 405168404Spjd wp->ulw_list = lp; 406168404Spjd wp->ulw_robust = robust; 407168404Spjd wp->ulw_dir = direction; 408168404Spjd if (direction > 0) 409168404Spjd wp->ulw_next_result = lp->ul_null_node.uln_next; 410168404Spjd else 411168404Spjd wp->ulw_next_result = lp->ul_null_node.uln_prev; 412168404Spjd 413168404Spjd if (lp->ul_debug || robust) { 414185029Spjd /* 415185029Spjd * Add this walker to the list's list of walkers so 416185029Spjd * uu_list_remove() can advance us if somebody tries to 417185029Spjd * remove ulw_next_result. 418185029Spjd */ 419168404Spjd wp->ulw_next = next = &lp->ul_null_walk; 420168404Spjd wp->ulw_prev = prev = next->ulw_prev; 421168404Spjd next->ulw_prev = wp; 422168404Spjd prev->ulw_next = wp; 423168404Spjd } 424168404Spjd} 425168404Spjd 426168404Spjdstatic uu_list_node_impl_t * 427168404Spjdlist_walk_advance(uu_list_walk_t *wp, uu_list_t *lp) 428168404Spjd{ 429168404Spjd uu_list_node_impl_t *np = wp->ulw_next_result; 430168404Spjd uu_list_node_impl_t *next; 431168404Spjd 432168404Spjd if (np == &lp->ul_null_node) 433168404Spjd return (NULL); 434168404Spjd 435168404Spjd next = (wp->ulw_dir > 0)? np->uln_next : np->uln_prev; 436168404Spjd 437168404Spjd wp->ulw_next_result = next; 438168404Spjd return (np); 439168404Spjd} 440168404Spjd 441168404Spjdstatic void 442168404Spjdlist_walk_fini(uu_list_walk_t *wp) 443168404Spjd{ 444168404Spjd /* GLXXX debugging? */ 445168404Spjd if (wp->ulw_next != NULL) { 446168404Spjd wp->ulw_next->ulw_prev = wp->ulw_prev; 447168404Spjd wp->ulw_prev->ulw_next = wp->ulw_next; 448168404Spjd wp->ulw_next = NULL; 449168404Spjd wp->ulw_prev = NULL; 450168404Spjd } 451168404Spjd wp->ulw_list = NULL; 452168404Spjd wp->ulw_next_result = NULL; 453168404Spjd} 454168404Spjd 455168404Spjduu_list_walk_t * 456168404Spjduu_list_walk_start(uu_list_t *lp, uint32_t flags) 457168404Spjd{ 458168404Spjd uu_list_walk_t *wp; 459168404Spjd 460168404Spjd if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) { 461168404Spjd uu_set_error(UU_ERROR_UNKNOWN_FLAG); 462168404Spjd return (NULL); 463168404Spjd } 464168404Spjd 465168404Spjd wp = uu_zalloc(sizeof (*wp)); 466168404Spjd if (wp == NULL) { 467168404Spjd uu_set_error(UU_ERROR_NO_MEMORY); 468168404Spjd return (NULL); 469168404Spjd } 470168404Spjd 471168404Spjd list_walk_init(wp, lp, flags); 472168404Spjd return (wp); 473168404Spjd} 474168404Spjd 475168404Spjdvoid * 476168404Spjduu_list_walk_next(uu_list_walk_t *wp) 477168404Spjd{ 478168404Spjd uu_list_t *lp = wp->ulw_list; 479168404Spjd uu_list_node_impl_t *np = list_walk_advance(wp, lp); 480168404Spjd 481168404Spjd if (np == NULL) 482168404Spjd return (NULL); 483168404Spjd 484168404Spjd return (NODE_TO_ELEM(lp, np)); 485168404Spjd} 486168404Spjd 487168404Spjdvoid 488168404Spjduu_list_walk_end(uu_list_walk_t *wp) 489168404Spjd{ 490168404Spjd list_walk_fini(wp); 491168404Spjd uu_free(wp); 492168404Spjd} 493168404Spjd 494168404Spjdint 495168404Spjduu_list_walk(uu_list_t *lp, uu_walk_fn_t *func, void *private, uint32_t flags) 496168404Spjd{ 497168404Spjd uu_list_node_impl_t *np; 498168404Spjd 499168404Spjd int status = UU_WALK_NEXT; 500168404Spjd 501168404Spjd int robust = (flags & UU_WALK_ROBUST); 502168404Spjd int reverse = (flags & UU_WALK_REVERSE); 503168404Spjd 504168404Spjd if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) { 505168404Spjd uu_set_error(UU_ERROR_UNKNOWN_FLAG); 506168404Spjd return (-1); 507168404Spjd } 508168404Spjd 509168404Spjd if (lp->ul_debug || robust) { 510168404Spjd uu_list_walk_t my_walk; 511168404Spjd void *e; 512168404Spjd 513168404Spjd list_walk_init(&my_walk, lp, flags); 514168404Spjd while (status == UU_WALK_NEXT && 515168404Spjd (e = uu_list_walk_next(&my_walk)) != NULL) 516168404Spjd status = (*func)(e, private); 517168404Spjd list_walk_fini(&my_walk); 518168404Spjd } else { 519168404Spjd if (!reverse) { 520168404Spjd for (np = lp->ul_null_node.uln_next; 521168404Spjd status == UU_WALK_NEXT && np != &lp->ul_null_node; 522168404Spjd np = np->uln_next) { 523168404Spjd status = (*func)(NODE_TO_ELEM(lp, np), private); 524168404Spjd } 525168404Spjd } else { 526168404Spjd for (np = lp->ul_null_node.uln_prev; 527168404Spjd status == UU_WALK_NEXT && np != &lp->ul_null_node; 528168404Spjd np = np->uln_prev) { 529168404Spjd status = (*func)(NODE_TO_ELEM(lp, np), private); 530168404Spjd } 531168404Spjd } 532168404Spjd } 533168404Spjd if (status >= 0) 534168404Spjd return (0); 535168404Spjd uu_set_error(UU_ERROR_CALLBACK_FAILED); 536168404Spjd return (-1); 537168404Spjd} 538168404Spjd 539168404Spjdvoid 540168404Spjduu_list_remove(uu_list_t *lp, void *elem) 541168404Spjd{ 542168404Spjd uu_list_node_impl_t *np = ELEM_TO_NODE(lp, elem); 543168404Spjd uu_list_walk_t *wp; 544168404Spjd 545168404Spjd if (lp->ul_debug) { 546168404Spjd if (np->uln_prev == NULL) 547168404Spjd uu_panic("uu_list_remove(%p, %p): elem not on list\n", 548185029Spjd (void *)lp, elem); 549168404Spjd /* 550168404Spjd * invalidate outstanding uu_list_index_ts. 551168404Spjd */ 552168404Spjd lp->ul_index = INDEX_NEXT(lp->ul_index); 553168404Spjd } 554168404Spjd 555168404Spjd /* 556168404Spjd * robust walkers must be advanced. In debug mode, non-robust 557168404Spjd * walkers are also on the list. If there are any, it's an error. 558168404Spjd */ 559168404Spjd for (wp = lp->ul_null_walk.ulw_next; wp != &lp->ul_null_walk; 560168404Spjd wp = wp->ulw_next) { 561168404Spjd if (wp->ulw_robust) { 562168404Spjd if (np == wp->ulw_next_result) 563168404Spjd (void) list_walk_advance(wp, lp); 564168404Spjd } else if (wp->ulw_next_result != NULL) { 565168404Spjd uu_panic("uu_list_remove(%p, %p): active non-robust " 566185029Spjd "walker\n", (void *)lp, elem); 567168404Spjd } 568168404Spjd } 569168404Spjd 570168404Spjd np->uln_next->uln_prev = np->uln_prev; 571168404Spjd np->uln_prev->uln_next = np->uln_next; 572168404Spjd 573168404Spjd lp->ul_numnodes--; 574168404Spjd 575168404Spjd np->uln_next = POOL_TO_MARKER(lp->ul_pool); 576168404Spjd np->uln_prev = NULL; 577168404Spjd} 578168404Spjd 579168404Spjdvoid * 580168404Spjduu_list_teardown(uu_list_t *lp, void **cookie) 581168404Spjd{ 582168404Spjd void *ep; 583168404Spjd 584168404Spjd /* 585168404Spjd * XXX: disable list modification until list is empty 586168404Spjd */ 587168404Spjd if (lp->ul_debug && *cookie != NULL) 588185029Spjd uu_panic("uu_list_teardown(%p, %p): unexpected cookie\n", 589185029Spjd (void *)lp, (void *)cookie); 590168404Spjd 591168404Spjd ep = uu_list_first(lp); 592168404Spjd if (ep) 593168404Spjd uu_list_remove(lp, ep); 594168404Spjd return (ep); 595168404Spjd} 596168404Spjd 597168404Spjdint 598168404Spjduu_list_insert_before(uu_list_t *lp, void *target, void *elem) 599168404Spjd{ 600168404Spjd uu_list_node_impl_t *np = ELEM_TO_NODE(lp, target); 601168404Spjd 602168404Spjd if (target == NULL) 603168404Spjd np = &lp->ul_null_node; 604168404Spjd 605168404Spjd if (lp->ul_debug) { 606168404Spjd if (np->uln_prev == NULL) 607168404Spjd uu_panic("uu_list_insert_before(%p, %p, %p): %p is " 608168404Spjd "not currently on a list\n", 609185029Spjd (void *)lp, target, elem, target); 610168404Spjd } 611168404Spjd if (lp->ul_sorted) { 612168404Spjd if (lp->ul_debug) 613168404Spjd uu_panic("uu_list_insert_before(%p, ...): list is " 614185029Spjd "UU_LIST_SORTED\n", (void *)lp); 615168404Spjd uu_set_error(UU_ERROR_NOT_SUPPORTED); 616168404Spjd return (-1); 617168404Spjd } 618168404Spjd 619168404Spjd list_insert(lp, ELEM_TO_NODE(lp, elem), np->uln_prev, np); 620168404Spjd return (0); 621168404Spjd} 622168404Spjd 623168404Spjdint 624168404Spjduu_list_insert_after(uu_list_t *lp, void *target, void *elem) 625168404Spjd{ 626168404Spjd uu_list_node_impl_t *np = ELEM_TO_NODE(lp, target); 627168404Spjd 628168404Spjd if (target == NULL) 629168404Spjd np = &lp->ul_null_node; 630168404Spjd 631168404Spjd if (lp->ul_debug) { 632168404Spjd if (np->uln_prev == NULL) 633168404Spjd uu_panic("uu_list_insert_after(%p, %p, %p): %p is " 634168404Spjd "not currently on a list\n", 635185029Spjd (void *)lp, target, elem, target); 636168404Spjd } 637168404Spjd if (lp->ul_sorted) { 638168404Spjd if (lp->ul_debug) 639168404Spjd uu_panic("uu_list_insert_after(%p, ...): list is " 640185029Spjd "UU_LIST_SORTED\n", (void *)lp); 641168404Spjd uu_set_error(UU_ERROR_NOT_SUPPORTED); 642168404Spjd return (-1); 643168404Spjd } 644168404Spjd 645168404Spjd list_insert(lp, ELEM_TO_NODE(lp, elem), np, np->uln_next); 646168404Spjd return (0); 647168404Spjd} 648168404Spjd 649168404Spjdsize_t 650168404Spjduu_list_numnodes(uu_list_t *lp) 651168404Spjd{ 652168404Spjd return (lp->ul_numnodes); 653168404Spjd} 654168404Spjd 655168404Spjdvoid * 656168404Spjduu_list_first(uu_list_t *lp) 657168404Spjd{ 658168404Spjd uu_list_node_impl_t *n = lp->ul_null_node.uln_next; 659168404Spjd if (n == &lp->ul_null_node) 660168404Spjd return (NULL); 661168404Spjd return (NODE_TO_ELEM(lp, n)); 662168404Spjd} 663168404Spjd 664168404Spjdvoid * 665168404Spjduu_list_last(uu_list_t *lp) 666168404Spjd{ 667168404Spjd uu_list_node_impl_t *n = lp->ul_null_node.uln_prev; 668168404Spjd if (n == &lp->ul_null_node) 669168404Spjd return (NULL); 670168404Spjd return (NODE_TO_ELEM(lp, n)); 671168404Spjd} 672168404Spjd 673168404Spjdvoid * 674168404Spjduu_list_next(uu_list_t *lp, void *elem) 675168404Spjd{ 676168404Spjd uu_list_node_impl_t *n = ELEM_TO_NODE(lp, elem); 677168404Spjd 678168404Spjd n = n->uln_next; 679168404Spjd if (n == &lp->ul_null_node) 680168404Spjd return (NULL); 681168404Spjd return (NODE_TO_ELEM(lp, n)); 682168404Spjd} 683168404Spjd 684168404Spjdvoid * 685168404Spjduu_list_prev(uu_list_t *lp, void *elem) 686168404Spjd{ 687168404Spjd uu_list_node_impl_t *n = ELEM_TO_NODE(lp, elem); 688168404Spjd 689168404Spjd n = n->uln_prev; 690168404Spjd if (n == &lp->ul_null_node) 691168404Spjd return (NULL); 692168404Spjd return (NODE_TO_ELEM(lp, n)); 693168404Spjd} 694168404Spjd 695168404Spjd/* 696168404Spjd * called from uu_lockup() and uu_release(), as part of our fork1()-safety. 697168404Spjd */ 698168404Spjdvoid 699168404Spjduu_list_lockup(void) 700168404Spjd{ 701168404Spjd uu_list_pool_t *pp; 702168404Spjd 703168404Spjd (void) pthread_mutex_lock(&uu_lpool_list_lock); 704168404Spjd for (pp = uu_null_lpool.ulp_next; pp != &uu_null_lpool; 705168404Spjd pp = pp->ulp_next) 706168404Spjd (void) pthread_mutex_lock(&pp->ulp_lock); 707168404Spjd} 708168404Spjd 709168404Spjdvoid 710168404Spjduu_list_release(void) 711168404Spjd{ 712168404Spjd uu_list_pool_t *pp; 713168404Spjd 714168404Spjd for (pp = uu_null_lpool.ulp_next; pp != &uu_null_lpool; 715168404Spjd pp = pp->ulp_next) 716168404Spjd (void) pthread_mutex_unlock(&pp->ulp_lock); 717168404Spjd (void) pthread_mutex_unlock(&uu_lpool_list_lock); 718168404Spjd} 719