lib/libuutil/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 https://opensource.org/licenses/CDDL-1.0.
  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
  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 = &pp->ulp_null_list;
  97         pp->ulp_null_list.ul_prev = &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 != &pp->ulp_null_list ||
 114                     pp->ulp_null_list.ul_prev != &pp->ulp_null_list) {
 115                         uu_panic("uu_list_pool_destroy: Pool \"%.*s\" (%p) has "
 116                             "outstanding lists, or is corrupt.\n",
 117                             (int)sizeof (pp->ulp_name), pp->ulp_name,
 118                             (void *)pp);
 119                 }
 120         }
 121         (void) pthread_mutex_lock(&uu_lpool_list_lock);
 122         pp->ulp_next->ulp_prev = pp->ulp_prev;
 123         pp->ulp_prev->ulp_next = pp->ulp_next;
 124         (void) pthread_mutex_unlock(&uu_lpool_list_lock);
 125         pp->ulp_prev = NULL;
 126         pp->ulp_next = NULL;
 127         uu_free(pp);
 128 }
 129
 130 void
 131 uu_list_node_init(void *base, uu_list_node_t *np_arg, uu_list_pool_t *pp)
 132 {
 133         uu_list_node_impl_t *np = (uu_list_node_impl_t *)np_arg;
 134
 135         if (pp->ulp_debug) {
 136                 uintptr_t offset = (uintptr_t)np - (uintptr_t)base;
 137                 if (offset + sizeof (*np) > pp->ulp_objsize) {
 138                         uu_panic("uu_list_node_init(%p, %p, %p (\"%s\")): "
 139                             "offset %ld doesn't fit in object (size %ld)\n",
 140                             base, (void *)np, (void *)pp, pp->ulp_name,
 141                             (long)offset, (long)pp->ulp_objsize);
 142                 }
 143                 if (offset != pp->ulp_nodeoffset) {
 144                         uu_panic("uu_list_node_init(%p, %p, %p (\"%s\")): "
 145                             "offset %ld doesn't match pool's offset (%ld)\n",
 146                             base, (void *)np, (void *)pp, pp->ulp_name,
 147                             (long)offset, (long)pp->ulp_objsize);
 148                 }
 149         }
 150         np->uln_next = POOL_TO_MARKER(pp);
 151         np->uln_prev = NULL;
 152 }
 153
 154 void
 155 uu_list_node_fini(void *base, uu_list_node_t *np_arg, uu_list_pool_t *pp)
 156 {
 157         uu_list_node_impl_t *np = (uu_list_node_impl_t *)np_arg;
 158
 159         if (pp->ulp_debug) {
 160                 if (np->uln_next == NULL &&
 161                     np->uln_prev == NULL) {
 162                         uu_panic("uu_list_node_fini(%p, %p, %p (\"%s\")): "
 163                             "node already finied\n",
 164                             base, (void *)np_arg, (void *)pp, pp->ulp_name);
 165                 }
 166                 if (np->uln_next != POOL_TO_MARKER(pp) ||
 167                     np->uln_prev != NULL) {
 168                         uu_panic("uu_list_node_fini(%p, %p, %p (\"%s\")): "
 169                             "node corrupt or on list\n",
 170                             base, (void *)np_arg, (void *)pp, pp->ulp_name);
 171                 }
 172         }
 173         np->uln_next = NULL;
 174         np->uln_prev = NULL;
 175 }
 176
 177 uu_list_t *
 178 uu_list_create(uu_list_pool_t *pp, void *parent, uint32_t flags)
 179 {
 180         uu_list_t *lp, *next, *prev;
 181
 182         if (flags & ~(UU_LIST_DEBUG | UU_LIST_SORTED)) {
 183                 uu_set_error(UU_ERROR_UNKNOWN_FLAG);
 184                 return (NULL);
 185         }
 186
 187         if ((flags & UU_LIST_SORTED) && pp->ulp_cmp == NULL) {
 188                 if (pp->ulp_debug)
 189                         uu_panic("uu_list_create(%p, ...): requested "
 190                             "UU_LIST_SORTED, but pool has no comparison func\n",
 191                             (void *)pp);
 192                 uu_set_error(UU_ERROR_NOT_SUPPORTED);
 193                 return (NULL);
 194         }
 195
 196         lp = uu_zalloc(sizeof (*lp));
 197         if (lp == NULL) {
 198                 uu_set_error(UU_ERROR_NO_MEMORY);
 199                 return (NULL);
 200         }
 201
 202         lp->ul_pool = pp;
 203         lp->ul_parent = parent;
 204         lp->ul_offset = pp->ulp_nodeoffset;
 205         lp->ul_debug = pp->ulp_debug || (flags & UU_LIST_DEBUG);
 206         lp->ul_sorted = (flags & UU_LIST_SORTED);
 207         lp->ul_numnodes = 0;
 208         lp->ul_index = (pp->ulp_last_index = INDEX_NEXT(pp->ulp_last_index));
 209
 210         lp->ul_null_node.uln_next = &lp->ul_null_node;
 211         lp->ul_null_node.uln_prev = &lp->ul_null_node;
 212
 213         lp->ul_null_walk.ulw_next = &lp->ul_null_walk;
 214         lp->ul_null_walk.ulw_prev = &lp->ul_null_walk;
 215
 216         (void) pthread_mutex_lock(&pp->ulp_lock);
 217         next = &pp->ulp_null_list;
 218         prev = next->ul_prev;
 219         lp->ul_next = next;
 220         lp->ul_prev = prev;
 221         next->ul_prev = lp;
 222         prev->ul_next = lp;
 223         (void) pthread_mutex_unlock(&pp->ulp_lock);
 224
 225         return (lp);
 226 }
 227
 228 void
 229 uu_list_destroy(uu_list_t *lp)
 230 {
 231         uu_list_pool_t *pp = lp->ul_pool;
 232
 233         if (lp->ul_debug) {
 234                 if (lp->ul_null_node.uln_next != &lp->ul_null_node ||
 235                     lp->ul_null_node.uln_prev != &lp->ul_null_node) {
 236                         uu_panic("uu_list_destroy(%p):  list not empty\n",
 237                             (void *)lp);
 238                 }
 239                 if (lp->ul_numnodes != 0) {
 240                         uu_panic("uu_list_destroy(%p):  numnodes is nonzero, "
 241                             "but list is empty\n", (void *)lp);
 242                 }
 243                 if (lp->ul_null_walk.ulw_next != &lp->ul_null_walk ||
 244                     lp->ul_null_walk.ulw_prev != &lp->ul_null_walk) {
 245                         uu_panic("uu_list_destroy(%p):  outstanding walkers\n",
 246                             (void *)lp);
 247                 }
 248         }
 249
 250         (void) pthread_mutex_lock(&pp->ulp_lock);
 251         lp->ul_next->ul_prev = lp->ul_prev;
 252         lp->ul_prev->ul_next = lp->ul_next;
 253         (void) pthread_mutex_unlock(&pp->ulp_lock);
 254         lp->ul_prev = NULL;
 255         lp->ul_next = NULL;
 256         lp->ul_pool = NULL;
 257         uu_free(lp);
 258 }
 259
 260 static void
 261 list_insert(uu_list_t *lp, uu_list_node_impl_t *np, uu_list_node_impl_t *prev,
 262     uu_list_node_impl_t *next)
 263 {
 264         if (lp->ul_debug) {
 265                 if (next->uln_prev != prev || prev->uln_next != next)
 266                         uu_panic("insert(%p): internal error: %p and %p not "
 267                             "neighbors\n", (void *)lp, (void *)next,
 268                             (void *)prev);
 269
 270                 if (np->uln_next != POOL_TO_MARKER(lp->ul_pool) ||
 271                     np->uln_prev != NULL) {
 272                         uu_panic("insert(%p): elem %p node %p corrupt, "
 273                             "not initialized, or already in a list.\n",
 274                             (void *)lp, NODE_TO_ELEM(lp, np), (void *)np);
 275                 }
 276                 /*
 277                  * invalidate outstanding uu_list_index_ts.
 278                  */
 279                 lp->ul_index = INDEX_NEXT(lp->ul_index);
 280         }
 281         np->uln_next = next;
 282         np->uln_prev = prev;
 283         next->uln_prev = np;
 284         prev->uln_next = np;
 285
 286         lp->ul_numnodes++;
 287 }
 288
 289 void
 290 uu_list_insert(uu_list_t *lp, void *elem, uu_list_index_t idx)
 291 {
 292         uu_list_node_impl_t *np;
 293
 294         np = INDEX_TO_NODE(idx);
 295         if (np == NULL)
 296                 np = &lp->ul_null_node;
 297
 298         if (lp->ul_debug) {
 299                 if (!INDEX_VALID(lp, idx))
 300                         uu_panic("uu_list_insert(%p, %p, %p): %s\n",
 301                             (void *)lp, elem, (void *)idx,
 302                             INDEX_CHECK(idx)? "outdated index" :
 303                             "invalid index");
 304                 if (np->uln_prev == NULL)
 305                         uu_panic("uu_list_insert(%p, %p, %p): out-of-date "
 306                             "index\n", (void *)lp, elem, (void *)idx);
 307         }
 308
 309         list_insert(lp, ELEM_TO_NODE(lp, elem), np->uln_prev, np);
 310 }
 311
 312 void *
 313 uu_list_find(uu_list_t *lp, void *elem, void *private, uu_list_index_t *out)
 314 {
 315         int sorted = lp->ul_sorted;
 316         uu_compare_fn_t *func = lp->ul_pool->ulp_cmp;
 317         uu_list_node_impl_t *np;
 318
 319         if (func == NULL) {
 320                 if (out != NULL)
 321                         *out = 0;
 322                 uu_set_error(UU_ERROR_NOT_SUPPORTED);
 323                 return (NULL);
 324         }
 325         for (np = lp->ul_null_node.uln_next; np != &lp->ul_null_node;
 326             np = np->uln_next) {
 327                 void *ep = NODE_TO_ELEM(lp, np);
 328                 int cmp = func(ep, elem, private);
 329                 if (cmp == 0) {
 330                         if (out != NULL)
 331                                 *out = NODE_TO_INDEX(lp, np);
 332                         return (ep);
 333                 }
 334                 if (sorted && cmp > 0) {
 335                         if (out != NULL)
 336                                 *out = NODE_TO_INDEX(lp, np);
 337                         return (NULL);
 338                 }
 339         }
 340         if (out != NULL)
 341                 *out = NODE_TO_INDEX(lp, 0);
 342         return (NULL);
 343 }
 344
 345 void *
 346 uu_list_nearest_next(uu_list_t *lp, uu_list_index_t idx)
 347 {
 348         uu_list_node_impl_t *np = INDEX_TO_NODE(idx);
 349
 350         if (np == NULL)
 351                 np = &lp->ul_null_node;
 352
 353         if (lp->ul_debug) {
 354                 if (!INDEX_VALID(lp, idx))
 355                         uu_panic("uu_list_nearest_next(%p, %p): %s\n",
 356                             (void *)lp, (void *)idx,
 357                             INDEX_CHECK(idx)? "outdated index" :
 358                             "invalid index");
 359                 if (np->uln_prev == NULL)
 360                         uu_panic("uu_list_nearest_next(%p, %p): out-of-date "
 361                             "index\n", (void *)lp, (void *)idx);
 362         }
 363
 364         if (np == &lp->ul_null_node)
 365                 return (NULL);
 366         else
 367                 return (NODE_TO_ELEM(lp, np));
 368 }
 369
 370 void *
 371 uu_list_nearest_prev(uu_list_t *lp, uu_list_index_t idx)
 372 {
 373         uu_list_node_impl_t *np = INDEX_TO_NODE(idx);
 374
 375         if (np == NULL)
 376                 np = &lp->ul_null_node;
 377
 378         if (lp->ul_debug) {
 379                 if (!INDEX_VALID(lp, idx))
 380                         uu_panic("uu_list_nearest_prev(%p, %p): %s\n",
 381                             (void *)lp, (void *)idx, INDEX_CHECK(idx)?
 382                             "outdated index" : "invalid index");
 383                 if (np->uln_prev == NULL)
 384                         uu_panic("uu_list_nearest_prev(%p, %p): out-of-date "
 385                             "index\n", (void *)lp, (void *)idx);
 386         }
 387
 388         if ((np = np->uln_prev) == &lp->ul_null_node)
 389                 return (NULL);
 390         else
 391                 return (NODE_TO_ELEM(lp, np));
 392 }
 393
 394 static void
 395 list_walk_init(uu_list_walk_t *wp, uu_list_t *lp, uint32_t flags)
 396 {
 397         uu_list_walk_t *next, *prev;
 398
 399         int robust = (flags & UU_WALK_ROBUST);
 400         int direction = (flags & UU_WALK_REVERSE)? -1 : 1;
 401
 402         (void) memset(wp, 0, sizeof (*wp));
 403         wp->ulw_list = lp;
 404         wp->ulw_robust = robust;
 405         wp->ulw_dir = direction;
 406         if (direction > 0)
 407                 wp->ulw_next_result = lp->ul_null_node.uln_next;
 408         else
 409                 wp->ulw_next_result = lp->ul_null_node.uln_prev;
 410
 411         if (lp->ul_debug || robust) {
 412                 /*
 413                  * Add this walker to the list's list of walkers so
 414                  * uu_list_remove() can advance us if somebody tries to
 415                  * remove ulw_next_result.
 416                  */
 417                 wp->ulw_next = next = &lp->ul_null_walk;
 418                 wp->ulw_prev = prev = next->ulw_prev;
 419                 next->ulw_prev = wp;
 420                 prev->ulw_next = wp;
 421         }
 422 }
 423
 424 static uu_list_node_impl_t *
 425 list_walk_advance(uu_list_walk_t *wp, uu_list_t *lp)
 426 {
 427         uu_list_node_impl_t *np = wp->ulw_next_result;
 428         uu_list_node_impl_t *next;
 429
 430         if (np == &lp->ul_null_node)
 431                 return (NULL);
 432
 433         next = (wp->ulw_dir > 0)? np->uln_next : np->uln_prev;
 434
 435         wp->ulw_next_result = next;
 436         return (np);
 437 }
 438
 439 static void
 440 list_walk_fini(uu_list_walk_t *wp)
 441 {
 442         /* GLXXX debugging? */
 443         if (wp->ulw_next != NULL) {
 444                 wp->ulw_next->ulw_prev = wp->ulw_prev;
 445                 wp->ulw_prev->ulw_next = wp->ulw_next;
 446                 wp->ulw_next = NULL;
 447                 wp->ulw_prev = NULL;
 448         }
 449         wp->ulw_list = NULL;
 450         wp->ulw_next_result = NULL;
 451 }
 452
 453 uu_list_walk_t *
 454 uu_list_walk_start(uu_list_t *lp, uint32_t flags)
 455 {
 456         uu_list_walk_t *wp;
 457
 458         if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) {
 459                 uu_set_error(UU_ERROR_UNKNOWN_FLAG);
 460                 return (NULL);
 461         }
 462
 463         wp = uu_zalloc(sizeof (*wp));
 464         if (wp == NULL) {
 465                 uu_set_error(UU_ERROR_NO_MEMORY);
 466                 return (NULL);
 467         }
 468
 469         list_walk_init(wp, lp, flags);
 470         return (wp);
 471 }
 472
 473 void *
 474 uu_list_walk_next(uu_list_walk_t *wp)
 475 {
 476         uu_list_t *lp = wp->ulw_list;
 477         uu_list_node_impl_t *np = list_walk_advance(wp, lp);
 478
 479         if (np == NULL)
 480                 return (NULL);
 481
 482         return (NODE_TO_ELEM(lp, np));
 483 }
 484
 485 void
 486 uu_list_walk_end(uu_list_walk_t *wp)
 487 {
 488         list_walk_fini(wp);
 489         uu_free(wp);
 490 }
 491
 492 int
 493 uu_list_walk(uu_list_t *lp, uu_walk_fn_t *func, void *private, uint32_t flags)
 494 {
 495         uu_list_node_impl_t *np;
 496
 497         int status = UU_WALK_NEXT;
 498
 499         int robust = (flags & UU_WALK_ROBUST);
 500         int reverse = (flags & UU_WALK_REVERSE);
 501
 502         if (flags & ~(UU_WALK_ROBUST | UU_WALK_REVERSE)) {
 503                 uu_set_error(UU_ERROR_UNKNOWN_FLAG);
 504                 return (-1);
 505         }
 506
 507         if (lp->ul_debug || robust) {
 508                 uu_list_walk_t my_walk;
 509                 void *e;
 510
 511                 list_walk_init(&my_walk, lp, flags);
 512                 while (status == UU_WALK_NEXT &&
 513                     (e = uu_list_walk_next(&my_walk)) != NULL)
 514                         status = (*func)(e, private);
 515                 list_walk_fini(&my_walk);
 516         } else {
 517                 if (!reverse) {
 518                         for (np = lp->ul_null_node.uln_next;
 519                             status == UU_WALK_NEXT && np != &lp->ul_null_node;
 520                             np = np->uln_next) {
 521                                 status = (*func)(NODE_TO_ELEM(lp, np), private);
 522                         }
 523                 } else {
 524                         for (np = lp->ul_null_node.uln_prev;
 525                             status == UU_WALK_NEXT && np != &lp->ul_null_node;
 526                             np = np->uln_prev) {
 527                                 status = (*func)(NODE_TO_ELEM(lp, np), private);
 528                         }
 529                 }
 530         }
 531         if (status >= 0)
 532                 return (0);
 533         uu_set_error(UU_ERROR_CALLBACK_FAILED);
 534         return (-1);
 535 }
 536
 537 void
 538 uu_list_remove(uu_list_t *lp, void *elem)
 539 {
 540         uu_list_node_impl_t *np = ELEM_TO_NODE(lp, elem);
 541         uu_list_walk_t *wp;
 542
 543         if (lp->ul_debug) {
 544                 if (np->uln_prev == NULL)
 545                         uu_panic("uu_list_remove(%p, %p): elem not on list\n",
 546                             (void *)lp, elem);
 547                 /*
 548                  * invalidate outstanding uu_list_index_ts.
 549                  */
 550                 lp->ul_index = INDEX_NEXT(lp->ul_index);
 551         }
 552
 553         /*
 554          * robust walkers must be advanced.  In debug mode, non-robust
 555          * walkers are also on the list.  If there are any, it's an error.
 556          */
 557         for (wp = lp->ul_null_walk.ulw_next; wp != &lp->ul_null_walk;
 558             wp = wp->ulw_next) {
 559                 if (wp->ulw_robust) {
 560                         if (np == wp->ulw_next_result)
 561                                 (void) list_walk_advance(wp, lp);
 562                 } else if (wp->ulw_next_result != NULL) {
 563                         uu_panic("uu_list_remove(%p, %p): active non-robust "
 564                             "walker\n", (void *)lp, elem);
 565                 }
 566         }
 567
 568         np->uln_next->uln_prev = np->uln_prev;
 569         np->uln_prev->uln_next = np->uln_next;
 570
 571         lp->ul_numnodes--;
 572
 573         np->uln_next = POOL_TO_MARKER(lp->ul_pool);
 574         np->uln_prev = NULL;
 575 }
 576
 577 void *
 578 uu_list_teardown(uu_list_t *lp, void **cookie)
 579 {
 580         void *ep;
 581
 582         /*
 583          * XXX: disable list modification until list is empty
 584          */
 585         if (lp->ul_debug && *cookie != NULL)
 586                 uu_panic("uu_list_teardown(%p, %p): unexpected cookie\n",
 587                     (void *)lp, (void *)cookie);
 588
 589         ep = uu_list_first(lp);
 590         if (ep)
 591                 uu_list_remove(lp, ep);
 592         return (ep);
 593 }
 594
 595 int
 596 uu_list_insert_before(uu_list_t *lp, void *target, void *elem)
 597 {
 598         uu_list_node_impl_t *np = ELEM_TO_NODE(lp, target);
 599
 600         if (target == NULL)
 601                 np = &lp->ul_null_node;
 602
 603         if (lp->ul_debug) {
 604                 if (np->uln_prev == NULL)
 605                         uu_panic("uu_list_insert_before(%p, %p, %p): %p is "
 606                             "not currently on a list\n",
 607                             (void *)lp, target, elem, target);
 608         }
 609         if (lp->ul_sorted) {
 610                 if (lp->ul_debug)
 611                         uu_panic("uu_list_insert_before(%p, ...): list is "
 612                             "UU_LIST_SORTED\n", (void *)lp);
 613                 uu_set_error(UU_ERROR_NOT_SUPPORTED);
 614                 return (-1);
 615         }
 616
 617         list_insert(lp, ELEM_TO_NODE(lp, elem), np->uln_prev, np);
 618         return (0);
 619 }
 620
 621 int
 622 uu_list_insert_after(uu_list_t *lp, void *target, void *elem)
 623 {
 624         uu_list_node_impl_t *np = ELEM_TO_NODE(lp, target);
 625
 626         if (target == NULL)
 627                 np = &lp->ul_null_node;
 628
 629         if (lp->ul_debug) {
 630                 if (np->uln_prev == NULL)
 631                         uu_panic("uu_list_insert_after(%p, %p, %p): %p is "
 632                             "not currently on a list\n",
 633                             (void *)lp, target, elem, target);
 634         }
 635         if (lp->ul_sorted) {
 636                 if (lp->ul_debug)
 637                         uu_panic("uu_list_insert_after(%p, ...): list is "
 638                             "UU_LIST_SORTED\n", (void *)lp);
 639                 uu_set_error(UU_ERROR_NOT_SUPPORTED);
 640                 return (-1);
 641         }
 642
 643         list_insert(lp, ELEM_TO_NODE(lp, elem), np, np->uln_next);
 644         return (0);
 645 }
 646
 647 size_t
 648 uu_list_numnodes(uu_list_t *lp)
 649 {
 650         return (lp->ul_numnodes);
 651 }
 652
 653 void *
 654 uu_list_first(uu_list_t *lp)
 655 {
 656         uu_list_node_impl_t *n = lp->ul_null_node.uln_next;
 657         if (n == &lp->ul_null_node)
 658                 return (NULL);
 659         return (NODE_TO_ELEM(lp, n));
 660 }
 661
 662 void *
 663 uu_list_last(uu_list_t *lp)
 664 {
 665         uu_list_node_impl_t *n = lp->ul_null_node.uln_prev;
 666         if (n == &lp->ul_null_node)
 667                 return (NULL);
 668         return (NODE_TO_ELEM(lp, n));
 669 }
 670
 671 void *
 672 uu_list_next(uu_list_t *lp, void *elem)
 673 {
 674         uu_list_node_impl_t *n = ELEM_TO_NODE(lp, elem);
 675
 676         n = n->uln_next;
 677         if (n == &lp->ul_null_node)
 678                 return (NULL);
 679         return (NODE_TO_ELEM(lp, n));
 680 }
 681
 682 void *
 683 uu_list_prev(uu_list_t *lp, void *elem)
 684 {
 685         uu_list_node_impl_t *n = ELEM_TO_NODE(lp, elem);
 686
 687         n = n->uln_prev;
 688         if (n == &lp->ul_null_node)
 689                 return (NULL);
 690         return (NODE_TO_ELEM(lp, n));
 691 }
 692
 693 /*
 694  * called from uu_lockup() and uu_release(), as part of our fork1()-safety.
 695  */
 696 void
 697 uu_list_lockup(void)
 698 {
 699         uu_list_pool_t *pp;
 700
 701         (void) pthread_mutex_lock(&uu_lpool_list_lock);
 702         for (pp = uu_null_lpool.ulp_next; pp != &uu_null_lpool;
 703             pp = pp->ulp_next)
 704                 (void) pthread_mutex_lock(&pp->ulp_lock);
 705 }
 706
 707 void
 708 uu_list_release(void)
 709 {
 710         uu_list_pool_t *pp;
 711
 712         for (pp = uu_null_lpool.ulp_next; pp != &uu_null_lpool;
 713             pp = pp->ulp_next)
 714                 (void) pthread_mutex_unlock(&pp->ulp_lock);
 715         (void) pthread_mutex_unlock(&uu_lpool_list_lock);
 716 }