cddl/contrib/opensolaris/lib/libuutil/common/uu_list.c

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21 /*
  22  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
  23  * Use is subject to license terms.
  24  */
  25
  26 #pragma ident   "%Z%%M% %I%     %E% SMI"
  27
  28 #include "libuutil_common.h"
  29
  30 #include <stdlib.h>
  31 #include <string.h>
  32 #include <unistd.h>
  33 #include <sys/time.h>
  34
  35 #define ELEM_TO_NODE(lp, e) \
  36         ((uu_list_node_impl_t *)((uintptr_t)(e) + (lp)->ul_offset))
  37
  38 #define NODE_TO_ELEM(lp, n) \
  39         ((void *)((uintptr_t)(n) - (lp)->ul_offset))
  40
  41 /*
  42  * uu_list_index_ts define a location for insertion.  They are simply a
  43  * pointer to the object after the insertion point.  We store a mark
  44  * in the low-bits of the index, to help prevent mistakes.
  45  *
  46  * When debugging, the index mark changes on every insert and delete, to
  47  * catch stale references.
  48  */
  49 #define INDEX_MAX               (sizeof (uintptr_t) - 1)
  50 #define INDEX_NEXT(m)           (((m) == INDEX_MAX)? 1 : ((m) + 1) & INDEX_MAX)
  51
  52 #define INDEX_TO_NODE(i)        ((uu_list_node_impl_t *)((i) & ~INDEX_MAX))
  53 #define NODE_TO_INDEX(p, n)     (((uintptr_t)(n) & ~INDEX_MAX) | (p)->ul_index)
  54 #define INDEX_VALID(p, i)       (((i) & INDEX_MAX) == (p)->ul_index)
  55 #define INDEX_CHECK(i)          (((i) & INDEX_MAX) != 0)
  56
  57 #define POOL_TO_MARKER(pp) ((void *)((uintptr_t)(pp) | 1))
  58
  59 static uu_list_pool_t   uu_null_lpool = { &uu_null_lpool, &uu_null_lpool };
  60 static pthread_mutex_t  uu_lpool_list_lock = PTHREAD_MUTEX_INITIALIZER;
  61
  62 uu_list_pool_t *
  63 uu_list_pool_create(const char *name, size_t objsize,
  64     size_t nodeoffset, uu_compare_fn_t *compare_func, uint32_t flags)
  65 {
  66         uu_list_pool_t *pp, *next, *prev;
  67
  68         if (name == NULL ||
  69             uu_check_name(name, UU_NAME_DOMAIN) == -1 ||
  70             nodeoffset + sizeof (uu_list_node_t) > objsize) {
  71                 uu_set_error(UU_ERROR_INVALID_ARGUMENT);
  72                 return (NULL);
  73         }
  74
  75         if (flags & ~UU_LIST_POOL_DEBUG) {
  76                 uu_set_error(UU_ERROR_UNKNOWN_FLAG);
  77                 return (NULL);
  78         }
  79
  80         pp = uu_zalloc(sizeof (uu_list_pool_t));
  81         if (pp == NULL) {
  82                 uu_set_error(UU_ERROR_NO_MEMORY);
  83                 return (NULL);
  84         }
  85
  86         (void) strlcpy(pp->ulp_name, name, sizeof (pp->ulp_name));
  87         pp->ulp_nodeoffset = nodeoffset;
  88         pp->ulp_objsize = objsize;
  89         pp->ulp_cmp = compare_func;
  90         if (flags & UU_LIST_POOL_DEBUG)
  91                 pp->ulp_debug = 1;
  92         pp->ulp_last_index = 0;
  93
  94         (void) pthread_mutex_init(&pp->ulp_lock, NULL);
  95
  96         pp->ulp_null_list.ul_next_enc = UU_PTR_ENCODE(&pp->ulp_null_list);
  97         pp->ulp_null_list.ul_prev_enc = UU_PTR_ENCODE(&pp->ulp_null_list);
  98
  99         (void) pthread_mutex_lock(&uu_lpool_list_lock);
 100         pp->ulp_next = next = &uu_null_lpool;
 101         pp->ulp_prev = prev = next->ulp_prev;
 102         next->ulp_prev = pp;
 103         prev->ulp_next = pp;
 104         (void) pthread_mutex_unlock(&uu_lpool_list_lock);
 105
 106         return (pp);
 107 }
 108
 109 void
 110 uu_list_pool_destroy(uu_list_pool_t *pp)
 111 {
 112         if (pp->ulp_debug) {
 113                 if (pp->ulp_null_list.ul_next_enc !=
 114                     UU_PTR_ENCODE(&pp->ulp_null_list) ||
 115                     pp->ulp_null_list.ul_prev_enc !=
 116                     UU_PTR_ENCODE(&pp->ulp_null_list)) {
 117                         uu_panic("uu_list_pool_destroy: Pool \"%.*s\" (%p) has "
 118                             "outstanding lists, or is corrupt.\n",
 119                             (int)sizeof (pp->ulp_name), pp->ulp_name,
 120                             (void *)pp);
 121                 }
 122         }
 123         (void) pthread_mutex_lock(&uu_lpool_list_lock);
 124         pp->ulp_next->ulp_prev = pp->ulp_prev;
 125         pp->ulp_prev->ulp_next = pp->ulp_next;
 126         (void) pthread_mutex_unlock(&uu_lpool_list_lock);
 127         pp->ulp_prev = NULL;
 128         pp->ulp_next = NULL;
 129         uu_free(pp);
 130 }
 131
 132 void
 133 uu_list_node_init(void *base, uu_list_node_t *np_arg, uu_list_pool_t *pp)
 134 {
 135         uu_list_node_impl_t *np = (uu_list_node_impl_t *)np_arg;
 136
 137         if (pp->ulp_debug) {
 138                 uintptr_t offset = (uintptr_t)np - (uintptr_t)base;
 139                 if (offset + sizeof (*np) > pp->ulp_objsize) {
 140                         uu_panic("uu_list_node_init(%p, %p, %p (\"%s\")): "
 141                             "offset %ld doesn't fit in object (size %ld)\n",
 142                             base, (void *)np, (void *)pp, pp->ulp_name,
 143                             (long)offset, (long)pp->ulp_objsize);
 144                 }
 145                 if (offset != pp->ulp_nodeoffset) {
 146                         uu_panic("uu_list_node_init(%p, %p, %p (\"%s\")): "
 147                             "offset %ld doesn't match pool's offset (%ld)\n",
 148                             base, (void *)np, (void *)pp, pp->ulp_name,
 149                             (long)offset, (long)pp->ulp_objsize);
 150                 }
 151         }
 152         np->uln_next = POOL_TO_MARKER(pp);
 153         np->uln_prev = NULL;
 154 }
 155
 156 void
 157 uu_list_node_fini(void *base, uu_list_node_t *np_arg, uu_list_pool_t *pp)
 158 {
 159         uu_list_node_impl_t *np = (uu_list_node_impl_t *)np_arg;
 160
 161         if (pp->ulp_debug) {
 162                 if (np->uln_next == NULL &&
 163                     np->uln_prev == NULL) {
 164                         uu_panic("uu_list_node_fini(%p, %p, %p (\"%s\")): "
 165                             "node already finied\n",
 166                             base, (void *)np_arg, (void *)pp, pp->ulp_name);
 167                 }
 168                 if (np->uln_next != POOL_TO_MARKER(pp) ||
 169                     np->uln_prev != NULL) {
 170                         uu_panic("uu_list_node_fini(%p, %p, %p (\"%s\")): "
 171                             "node corrupt or on list\n",
 172                             base, (void *)np_arg, (void *)pp, pp->ulp_name);
 173                 }
 174         }
 175         np->uln_next = NULL;
 176         np->uln_prev = NULL;
 177 }
 178
 179 uu_list_t *
 180 uu_list_create(uu_list_pool_t *pp, void *parent, uint32_t flags)
 181 {
 182         uu_list_t *lp, *next, *prev;
 183
 184         if (flags & ~(UU_LIST_DEBUG | UU_LIST_SORTED)) {
 185                 uu_set_error(UU_ERROR_UNKNOWN_FLAG);
 186                 return (NULL);
 187         }
 188
 189         if ((flags & UU_LIST_SORTED) && pp->ulp_cmp == NULL) {
 190                 if (pp->ulp_debug)
 191                         uu_panic("uu_list_create(%p, ...): requested "
 192                             "UU_LIST_SORTED, but pool has no comparison func\n",
 193                             (void *)pp);
 194                 uu_set_error(UU_ERROR_NOT_SUPPORTED);
 195                 return (NULL);
 196         }
 197
 198         lp = uu_zalloc(sizeof (*lp));
 199         if (lp == NULL) {
 200                 uu_set_error(UU_ERROR_NO_MEMORY);
 201                 return (NULL);
 202         }
 203
 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));
 211
 212         lp->ul_null_node.uln_next = &lp->ul_null_node;
 213         lp->ul_null_node.uln_prev = &lp->ul_null_node;
 214
 215         lp->ul_null_walk.ulw_next = &lp->ul_null_walk;
 216         lp->ul_null_walk.ulw_prev = &lp->ul_null_walk;
 217
 218         (void) pthread_mutex_lock(&pp->ulp_lock);
 219         next = &pp->ulp_null_list;
 220         prev = UU_PTR_DECODE(next->ul_prev_enc);
 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);
 225         (void) pthread_mutex_unlock(&pp->ulp_lock);
 226
 227         return (lp);
 228 }
 229
 230 void
 231 uu_list_destroy(uu_list_t *lp)
 232 {
 233         uu_list_pool_t *pp = lp->ul_pool;
 234
 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) {
 238                         uu_panic("uu_list_destroy(%p):  list not empty\n",
 239                             (void *)lp);
 240                 }
 241                 if (lp->ul_numnodes != 0) {
 242                         uu_panic("uu_list_destroy(%p):  numnodes is nonzero, "
 243                             "but list is empty\n", (void *)lp);
 244                 }
 245                 if (lp->ul_null_walk.ulw_next != &lp->ul_null_walk ||
 246                     lp->ul_null_walk.ulw_prev != &lp->ul_null_walk) {
 247                         uu_panic("uu_list_destroy(%p):  outstanding walkers\n",
 248                             (void *)lp);
 249                 }
 250         }
 251
 252         (void) pthread_mutex_lock(&pp->ulp_lock);
 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;
 255         (void) pthread_mutex_unlock(&pp->ulp_lock);
 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);
 260 }
 261
 262 static void
 263 list_insert(uu_list_t *lp, uu_list_node_impl_t *np, uu_list_node_impl_t *prev,
 264     uu_list_node_impl_t *next)
 265 {
 266         if (lp->ul_debug) {
 267                 if (next->uln_prev != prev || prev->uln_next != next)
 268                         uu_panic("insert(%p): internal error: %p and %p not "
 269                             "neighbors\n", (void *)lp, (void *)next,
 270                             (void *)prev);
 271
 272                 if (np->uln_next != POOL_TO_MARKER(lp->ul_pool) ||
 273                     np->uln_prev != NULL) {
 274                         uu_panic("insert(%p): elem %p node %p corrupt, "
 275                             "not initialized, or already in a list.\n",
 276                             (void *)lp, NODE_TO_ELEM(lp, np), (void *)np);
 277                 }
 278                 /*
 279                  * invalidate outstanding uu_list_index_ts.
 280                  */
 281                 lp->ul_index = INDEX_NEXT(lp->ul_index);
 282         }
 283         np->uln_next = next;
 284         np->uln_prev = prev;
 285         next->uln_prev = np;
 286         prev->uln_next = np;
 287
 288         lp->ul_numnodes++;
 289 }
 290
 291 void
 292 uu_list_insert(uu_list_t *lp, void *elem, uu_list_index_t idx)
 293 {
 294         uu_list_node_impl_t *np;
 295
 296         np = INDEX_TO_NODE(idx);
 297         if (np == NULL)
 298                 np = &lp->ul_null_node;
 299
 300         if (lp->ul_debug) {
 301                 if (!INDEX_VALID(lp, idx))
 302                         uu_panic("uu_list_insert(%p, %p, %p): %s\n",
 303                             (void *)lp, elem, (void *)idx,
 304                             INDEX_CHECK(idx)? "outdated index" :
 305                             "invalid index");
 306                 if (np->uln_prev == NULL)
 307                         uu_panic("uu_list_insert(%p, %p, %p): out-of-date "
 308                             "index\n", (void *)lp, elem, (void *)idx);
 309         }
 310
 311         list_insert(lp, ELEM_TO_NODE(lp, elem), np->uln_prev, np);
 312 }
 313
 314 void *
 315 uu_list_find(uu_list_t *lp, void *elem, void *private, uu_list_index_t *out)
 316 {
 317         int sorted = lp->ul_sorted;
 318         uu_compare_fn_t *func = lp->ul_pool->ulp_cmp;
 319         uu_list_node_impl_t *np;
 320
 321         if (func == NULL) {
 322                 if (out != NULL)
 323                         *out = 0;
 324                 uu_set_error(UU_ERROR_NOT_SUPPORTED);
 325                 return (NULL);
 326         }
 327         for (np = lp->ul_null_node.uln_next; np != &lp->ul_null_node;
 328             np = np->uln_next) {
 329                 void *ep = NODE_TO_ELEM(lp, np);
 330                 int cmp = func(ep, elem, private);
 331                 if (cmp == 0) {
 332                         if (out != NULL)
 333                                 *out = NODE_TO_INDEX(lp, np);
 334                         return (ep);
 335                 }
 336                 if (sorted && cmp > 0) {
 337                         if (out != NULL)
 338                                 *out = NODE_TO_INDEX(lp, np);
 339                         return (NULL);
 340                 }
 341         }
 342         if (out != NULL)
 343                 *out = NODE_TO_INDEX(lp, 0);
 344         return (NULL);
 345 }
 346
 347 void *
 348 uu_list_nearest_next(uu_list_t *lp, uu_list_index_t idx)
 349 {
 350         uu_list_node_impl_t *np = INDEX_TO_NODE(idx);
 351
 352         if (np == NULL)
 353                 np = &lp->ul_null_node;
 354
 355         if (lp->ul_debug) {
 356                 if (!INDEX_VALID(lp, idx))
 357                         uu_panic("uu_list_nearest_next(%p, %p): %s\n",
 358                             (void *)lp, (void *)idx,
 359                             INDEX_CHECK(idx)? "outdated index" :
 360                             "invalid index");
 361                 if (np->uln_prev == NULL)
 362                         uu_panic("uu_list_nearest_next(%p, %p): out-of-date "
 363                             "index\n", (void *)lp, (void *)idx);
 364         }
 365
 366         if (np == &lp->ul_null_node)
 367                 return (NULL);
 368         else
 369                 return (NODE_TO_ELEM(lp, np));
 370 }
 371
 372 void *
 373 uu_list_nearest_prev(uu_list_t *lp, uu_list_index_t idx)
 374 {
 375         uu_list_node_impl_t *np = INDEX_TO_NODE(idx);
 376
 377         if (np == NULL)
 378                 np = &lp->ul_null_node;
 379
 380         if (lp->ul_debug) {
 381                 if (!INDEX_VALID(lp, idx))
 382                         uu_panic("uu_list_nearest_prev(%p, %p): %s\n",
 383                             (void *)lp, (void *)idx, INDEX_CHECK(idx)?
 384                             "outdated index" : "invalid index");
 385                 if (np->uln_prev == NULL)
 386                         uu_panic("uu_list_nearest_prev(%p, %p): out-of-date "
 387                             "index\n", (void *)lp, (void *)idx);
 388         }
 389
 390         if ((np = np->uln_prev) == &lp->ul_null_node)
 391                 return (NULL);
 392         else
 393                 return (NODE_TO_ELEM(lp, np));
 394 }
 395
 396 static void
 397 list_walk_init(uu_list_walk_t *wp, uu_list_t *lp, uint32_t flags)
 398 {
 399         uu_list_walk_t *next, *prev;
 400
 401         int robust = (flags & UU_WALK_ROBUST);
 402         int direction = (flags & UU_WALK_REVERSE)? -1 : 1;
 403
 404         (void) memset(wp, 0, sizeof (*wp));
 405         wp->ulw_list = lp;
 406         wp->ulw_robust = robust;
 407         wp->ulw_dir = direction;
 408         if (direction > 0)
 409                 wp->ulw_next_result = lp->ul_null_node.uln_next;
 410         else
 411                 wp->ulw_next_result = lp->ul_null_node.uln_prev;
 412
 413         if (lp->ul_debug || robust) {
 414                 /*
 415                  * Add this walker to the list's list of walkers so
 416                  * uu_list_remove() can advance us if somebody tries to
 417                  * remove ulw_next_result.
 418                  */
 419                 wp->ulw_next = next = &lp->ul_null_walk;
 420                 wp->ulw_prev = prev = next->ulw_prev;
 421                 next->ulw_prev = wp;
 422                 prev->ulw_next = wp;
 423         }
 424 }
 425
 426 static uu_list_node_impl_t *
 427 list_walk_advance(uu_list_walk_t *wp, uu_list_t *lp)
 428 {
 429         uu_list_node_impl_t *np = wp->ulw_next_result;
 430         uu_list_node_impl_t *next;
 431
 432         if (np == &lp->ul_null_node)
 433                 return (NULL);
 434
 435         next = (wp->ulw_dir > 0)? np->uln_next : np->uln_prev;
 436
 437         wp->ulw_next_result = next;
 438         return (np);
 439 }
 440
 441 static void
 442 list_walk_fini(uu_list_walk_t *wp)
 443 {
 444         /* GLXXX debugging? */
 445         if (wp->ulw_next != NULL) {
 446                 wp->ulw_next->ulw_prev = wp->ulw_prev;
 447                 wp->ulw_prev->ulw_next = wp->ulw_next;
 448                 wp->ulw_next = NULL;
 449                 wp->ulw_prev = NULL;
 450         }
 451         wp->ulw_list = NULL;
 452         wp->ulw_next_result = NULL;
 453 }
 454
 455 uu_list_walk_t *
 456 uu_list_walk_start(uu_list_t *lp, uint32_t flags)
 457 {
 458         uu_list_walk_t *wp;
 459
 460         if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) {
 461                 uu_set_error(UU_ERROR_UNKNOWN_FLAG);
 462                 return (NULL);
 463         }
 464
 465         wp = uu_zalloc(sizeof (*wp));
 466         if (wp == NULL) {
 467                 uu_set_error(UU_ERROR_NO_MEMORY);
 468                 return (NULL);
 469         }
 470
 471         list_walk_init(wp, lp, flags);
 472         return (wp);
 473 }
 474
 475 void *
 476 uu_list_walk_next(uu_list_walk_t *wp)
 477 {
 478         uu_list_t *lp = wp->ulw_list;
 479         uu_list_node_impl_t *np = list_walk_advance(wp, lp);
 480
 481         if (np == NULL)
 482                 return (NULL);
 483
 484         return (NODE_TO_ELEM(lp, np));
 485 }
 486
 487 void
 488 uu_list_walk_end(uu_list_walk_t *wp)
 489 {
 490         list_walk_fini(wp);
 491         uu_free(wp);
 492 }
 493
 494 int
 495 uu_list_walk(uu_list_t *lp, uu_walk_fn_t *func, void *private, uint32_t flags)
 496 {
 497         uu_list_node_impl_t *np;
 498
 499         int status = UU_WALK_NEXT;
 500
 501         int robust = (flags & UU_WALK_ROBUST);
 502         int reverse = (flags & UU_WALK_REVERSE);
 503
 504         if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) {
 505                 uu_set_error(UU_ERROR_UNKNOWN_FLAG);
 506                 return (-1);
 507         }
 508
 509         if (lp->ul_debug || robust) {
 510                 uu_list_walk_t my_walk;
 511                 void *e;
 512
 513                 list_walk_init(&my_walk, lp, flags);
 514                 while (status == UU_WALK_NEXT &&
 515                     (e = uu_list_walk_next(&my_walk)) != NULL)
 516                         status = (*func)(e, private);
 517                 list_walk_fini(&my_walk);
 518         } else {
 519                 if (!reverse) {
 520                         for (np = lp->ul_null_node.uln_next;
 521                             status == UU_WALK_NEXT && np != &lp->ul_null_node;
 522                             np = np->uln_next) {
 523                                 status = (*func)(NODE_TO_ELEM(lp, np), private);
 524                         }
 525                 } else {
 526                         for (np = lp->ul_null_node.uln_prev;
 527                             status == UU_WALK_NEXT && np != &lp->ul_null_node;
 528                             np = np->uln_prev) {
 529                                 status = (*func)(NODE_TO_ELEM(lp, np), private);
 530                         }
 531                 }
 532         }
 533         if (status >= 0)
 534                 return (0);
 535         uu_set_error(UU_ERROR_CALLBACK_FAILED);
 536         return (-1);
 537 }
 538
 539 void
 540 uu_list_remove(uu_list_t *lp, void *elem)
 541 {
 542         uu_list_node_impl_t *np = ELEM_TO_NODE(lp, elem);
 543         uu_list_walk_t *wp;
 544
 545         if (lp->ul_debug) {
 546                 if (np->uln_prev == NULL)
 547                         uu_panic("uu_list_remove(%p, %p): elem not on list\n",
 548                             (void *)lp, elem);
 549                 /*
 550                  * invalidate outstanding uu_list_index_ts.
 551                  */
 552                 lp->ul_index = INDEX_NEXT(lp->ul_index);
 553         }
 554
 555         /*
 556          * robust walkers must be advanced.  In debug mode, non-robust
 557          * walkers are also on the list.  If there are any, it's an error.
 558          */
 559         for (wp = lp->ul_null_walk.ulw_next; wp != &lp->ul_null_walk;
 560             wp = wp->ulw_next) {
 561                 if (wp->ulw_robust) {
 562                         if (np == wp->ulw_next_result)
 563                                 (void) list_walk_advance(wp, lp);
 564                 } else if (wp->ulw_next_result != NULL) {
 565                         uu_panic("uu_list_remove(%p, %p): active non-robust "
 566                             "walker\n", (void *)lp, elem);
 567                 }
 568         }
 569
 570         np->uln_next->uln_prev = np->uln_prev;
 571         np->uln_prev->uln_next = np->uln_next;
 572
 573         lp->ul_numnodes--;
 574
 575         np->uln_next = POOL_TO_MARKER(lp->ul_pool);
 576         np->uln_prev = NULL;
 577 }
 578
 579 void *
 580 uu_list_teardown(uu_list_t *lp, void **cookie)
 581 {
 582         void *ep;
 583
 584         /*
 585          * XXX: disable list modification until list is empty
 586          */
 587         if (lp->ul_debug && *cookie != NULL)
 588                 uu_panic("uu_list_teardown(%p, %p): unexpected cookie\n",
 589                     (void *)lp, (void *)cookie);
 590
 591         ep = uu_list_first(lp);
 592         if (ep)
 593                 uu_list_remove(lp, ep);
 594         return (ep);
 595 }
 596
 597 int
 598 uu_list_insert_before(uu_list_t *lp, void *target, void *elem)
 599 {
 600         uu_list_node_impl_t *np = ELEM_TO_NODE(lp, target);
 601
 602         if (target == NULL)
 603                 np = &lp->ul_null_node;
 604
 605         if (lp->ul_debug) {
 606                 if (np->uln_prev == NULL)
 607                         uu_panic("uu_list_insert_before(%p, %p, %p): %p is "
 608                             "not currently on a list\n",
 609                             (void *)lp, target, elem, target);
 610         }
 611         if (lp->ul_sorted) {
 612                 if (lp->ul_debug)
 613                         uu_panic("uu_list_insert_before(%p, ...): list is "
 614                             "UU_LIST_SORTED\n", (void *)lp);
 615                 uu_set_error(UU_ERROR_NOT_SUPPORTED);
 616                 return (-1);
 617         }
 618
 619         list_insert(lp, ELEM_TO_NODE(lp, elem), np->uln_prev, np);
 620         return (0);
 621 }
 622
 623 int
 624 uu_list_insert_after(uu_list_t *lp, void *target, void *elem)
 625 {
 626         uu_list_node_impl_t *np = ELEM_TO_NODE(lp, target);
 627
 628         if (target == NULL)
 629                 np = &lp->ul_null_node;
 630
 631         if (lp->ul_debug) {
 632                 if (np->uln_prev == NULL)
 633                         uu_panic("uu_list_insert_after(%p, %p, %p): %p is "
 634                             "not currently on a list\n",
 635                             (void *)lp, target, elem, target);
 636         }
 637         if (lp->ul_sorted) {
 638                 if (lp->ul_debug)
 639                         uu_panic("uu_list_insert_after(%p, ...): list is "
 640                             "UU_LIST_SORTED\n", (void *)lp);
 641                 uu_set_error(UU_ERROR_NOT_SUPPORTED);
 642                 return (-1);
 643         }
 644
 645         list_insert(lp, ELEM_TO_NODE(lp, elem), np, np->uln_next);
 646         return (0);
 647 }
 648
 649 size_t
 650 uu_list_numnodes(uu_list_t *lp)
 651 {
 652         return (lp->ul_numnodes);
 653 }
 654
 655 void *
 656 uu_list_first(uu_list_t *lp)
 657 {
 658         uu_list_node_impl_t *n = lp->ul_null_node.uln_next;
 659         if (n == &lp->ul_null_node)
 660                 return (NULL);
 661         return (NODE_TO_ELEM(lp, n));
 662 }
 663
 664 void *
 665 uu_list_last(uu_list_t *lp)
 666 {
 667         uu_list_node_impl_t *n = lp->ul_null_node.uln_prev;
 668         if (n == &lp->ul_null_node)
 669                 return (NULL);
 670         return (NODE_TO_ELEM(lp, n));
 671 }
 672
 673 void *
 674 uu_list_next(uu_list_t *lp, void *elem)
 675 {
 676         uu_list_node_impl_t *n = ELEM_TO_NODE(lp, elem);
 677
 678         n = n->uln_next;
 679         if (n == &lp->ul_null_node)
 680                 return (NULL);
 681         return (NODE_TO_ELEM(lp, n));
 682 }
 683
 684 void *
 685 uu_list_prev(uu_list_t *lp, void *elem)
 686 {
 687         uu_list_node_impl_t *n = ELEM_TO_NODE(lp, elem);
 688
 689         n = n->uln_prev;
 690         if (n == &lp->ul_null_node)
 691                 return (NULL);
 692         return (NODE_TO_ELEM(lp, n));
 693 }
 694
 695 /*
 696  * called from uu_lockup() and uu_release(), as part of our fork1()-safety.
 697  */
 698 void
 699 uu_list_lockup(void)
 700 {
 701         uu_list_pool_t *pp;
 702
 703         (void) pthread_mutex_lock(&uu_lpool_list_lock);
 704         for (pp = uu_null_lpool.ulp_next; pp != &uu_null_lpool;
 705             pp = pp->ulp_next)
 706                 (void) pthread_mutex_lock(&pp->ulp_lock);
 707 }
 708
 709 void
 710 uu_list_release(void)
 711 {
 712         uu_list_pool_t *pp;
 713
 714         for (pp = uu_null_lpool.ulp_next; pp != &uu_null_lpool;
 715             pp = pp->ulp_next)
 716                 (void) pthread_mutex_unlock(&pp->ulp_lock);
 717         (void) pthread_mutex_unlock(&uu_lpool_list_lock);
 718 }