lib/list.c

   1 /*****************************************************************************
   2  *  Copyright (C) 2007-2010 Lawrence Livermore National Security, LLC.
   3  *  Copyright (C) 2001-2007 The Regents of the University of California.
   4  *  Produced at Lawrence Livermore National Laboratory (cf, DISCLAIMER).
   5  *  Written by Chris Dunlap <cdunlap@llnl.gov>.
   6  *  UCRL-CODE-235197
   7  *
   8  *  This file is from LSD-Tools, the LLNL Software Development Toolbox.
   9  *
  10  *  LSD-Tools is free software; you can redistribute it and/or modify it
  11  *  under the terms of the GNU General Public License as published by the
  12  *  Free Software Foundation; either version 2 of the License, or (at your
  13  *  option) any later version.
  14  *
  15  *  LSD-Tools is distributed in the hope that it will be useful, but WITHOUT
  16  *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  17  *  FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  18  *  for more details.
  19  *
  20  *  You should have received a copy of the GNU General Public License along
  21  *  with LSD-Tools.  If not, see <http://www.gnu.org/licenses/>.
  22  *****************************************************************************
  23  *  Refer to "list.h" for documentation on public functions.
  24  *****************************************************************************/
  25
  26 #ifdef WITH_PTHREADS
  27 #  include <pthread.h>
  28 #endif /* WITH_PTHREADS */
  29
  30 #include <assert.h>
  31 #include <errno.h>
  32 #include <stdlib.h>
  33 #include <string.h>
  34 #include "list.h"
  35
  36
  37 /*********************
  38  *  lsd_fatal_error  *
  39  *********************/
  40
  41 #ifdef WITH_LSD_FATAL_ERROR_FUNC
  42 #  undef lsd_fatal_error
  43    extern void lsd_fatal_error(char *file, int line, char *mesg);
  44 #else /* !WITH_LSD_FATAL_ERROR_FUNC */
  45 #  ifndef lsd_fatal_error
  46 #    include <errno.h>
  47 #    include <stdio.h>
  48 #    include <string.h>
  49 #    define lsd_fatal_error(file, line, mesg)                                 \
  50        do {                                                                   \
  51            fprintf(stderr, "ERROR: [%s:%d] %s: %s\n",                         \
  52                    file, line, mesg, strerror(errno));                        \
  53        } while (0)
  54 #  endif /* !lsd_fatal_error */
  55 #endif /* !WITH_LSD_FATAL_ERROR_FUNC */
  56
  57
  58 /*********************
  59  *  lsd_nomem_error  *
  60  *********************/
  61
  62 #ifdef WITH_LSD_NOMEM_ERROR_FUNC
  63 #  undef lsd_nomem_error
  64    extern void * lsd_nomem_error(char *file, int line, char *mesg);
  65 #else /* !WITH_LSD_NOMEM_ERROR_FUNC */
  66 #  ifndef lsd_nomem_error
  67 #    define lsd_nomem_error(file, line, mesg) (NULL)
  68 #  endif /* !lsd_nomem_error */
  69 #endif /* !WITH_LSD_NOMEM_ERROR_FUNC */
  70
  71
  72 /***************
  73  *  Constants  *
  74  ***************/
  75
  76 #define LIST_ALLOC 32
  77 #define LIST_MAGIC 0xDEADBEEF
  78
  79
  80 /****************
  81  *  Data Types  *
  82  ****************/
  83
  84 struct listNode {
  85     void                 *data;         /* node's data                       */
  86     struct listNode      *next;         /* next node in list                 */
  87 };
  88
  89 struct listIterator {
  90     struct list          *list;         /* the list being iterated           */
  91     struct listNode      *pos;          /* the next node to be iterated      */
  92     struct listNode     **prev;         /* addr of 'next' ptr to prv It node */
  93     struct listIterator  *iNext;        /* iterator chain for list_destroy() */
  94 #ifndef NDEBUG
  95     unsigned int          magic;        /* sentinel for asserting validity   */
  96 #endif /* !NDEBUG */
  97 };
  98
  99 struct list {
 100     struct listNode      *head;         /* head of the list                  */
 101     struct listNode     **tail;         /* addr of last node's 'next' ptr    */
 102     struct listIterator  *iNext;        /* iterator chain for list_destroy() */
 103     ListDelF              fDel;         /* function to delete node data      */
 104     int                   count;        /* number of nodes in list           */
 105 #ifdef WITH_PTHREADS
 106     pthread_mutex_t       mutex;        /* mutex to protect access to list   */
 107 #endif /* WITH_PTHREADS */
 108 #ifndef NDEBUG
 109     unsigned int          magic;        /* sentinel for asserting validity   */
 110 #endif /* !NDEBUG */
 111 };
 112
 113 typedef struct listNode * ListNode;
 114
 115
 116 /****************
 117  *  Prototypes  *
 118  ****************/
 119
 120 static void * list_node_create (List l, ListNode *pp, void *x);
 121 static void * list_node_destroy (List l, ListNode *pp);
 122 static List list_alloc (void);
 123 static void list_free (List l);
 124 static ListNode list_node_alloc (void);
 125 static void list_node_free (ListNode p);
 126 static ListIterator list_iterator_alloc (void);
 127 static void list_iterator_free (ListIterator i);
 128 static void * list_alloc_aux (int size, void *pfreelist);
 129 static void list_free_aux (void *x, void *pfreelist);
 130
 131
 132 /***************
 133  *  Variables  *
 134  ***************/
 135
 136 static List list_free_lists = NULL;
 137 static ListNode list_free_nodes = NULL;
 138 static ListIterator list_free_iterators = NULL;
 139
 140 #ifdef WITH_PTHREADS
 141 static pthread_mutex_t list_free_lock = PTHREAD_MUTEX_INITIALIZER;
 142 #endif /* WITH_PTHREADS */
 143
 144
 145 /************
 146  *  Macros  *
 147  ************/
 148
 149 #ifdef WITH_PTHREADS
 150
 151 #  define list_mutex_init(mutex)                                              \
 152      do {                                                                     \
 153          int e = pthread_mutex_init(mutex, NULL);                             \
 154          if (e != 0) {                                                        \
 155              errno = e;                                                       \
 156              lsd_fatal_error(__FILE__, __LINE__, "list mutex init");          \
 157              abort();                                                         \
 158          }                                                                    \
 159      } while (0)
 160
 161 #  define list_mutex_lock(mutex)                                              \
 162      do {                                                                     \
 163          int e = pthread_mutex_lock(mutex);                                   \
 164          if (e != 0) {                                                        \
 165              errno = e;                                                       \
 166              lsd_fatal_error(__FILE__, __LINE__, "list mutex lock");          \
 167              abort();                                                         \
 168          }                                                                    \
 169      } while (0)
 170
 171 #  define list_mutex_unlock(mutex)                                            \
 172      do {                                                                     \
 173          int e = pthread_mutex_unlock(mutex);                                 \
 174          if (e != 0) {                                                        \
 175              errno = e;                                                       \
 176              lsd_fatal_error(__FILE__, __LINE__, "list mutex unlock");        \
 177              abort();                                                         \
 178          }                                                                    \
 179      } while (0)
 180
 181 #  define list_mutex_destroy(mutex)                                           \
 182      do {                                                                     \
 183          int e = pthread_mutex_destroy(mutex);                                \
 184          if (e != 0) {                                                        \
 185              errno = e;                                                       \
 186              lsd_fatal_error(__FILE__, __LINE__, "list mutex destroy");       \
 187              abort();                                                         \
 188          }                                                                    \
 189      } while (0)
 190
 191 #  ifndef NDEBUG
 192      static int list_mutex_is_locked (pthread_mutex_t *mutex);
 193 #  endif /* !NDEBUG */
 194
 195 #else /* !WITH_PTHREADS */
 196
 197 #  define list_mutex_init(mutex)
 198 #  define list_mutex_lock(mutex)
 199 #  define list_mutex_unlock(mutex)
 200 #  define list_mutex_destroy(mutex)
 201 #  define list_mutex_is_locked(mutex) (1)
 202
 203 #endif /* !WITH_PTHREADS */
 204
 205
 206 /***************
 207  *  Functions  *
 208  ***************/
 209
 210 List
 211 list_create (ListDelF f)
 212 {
 213     List l;
 214
 215     if (!(l = list_alloc()))
 216         return(lsd_nomem_error(__FILE__, __LINE__, "list create"));
 217     l->head = NULL;
 218     l->tail = &l->head;
 219     l->iNext = NULL;
 220     l->fDel = f;
 221     l->count = 0;
 222     list_mutex_init(&l->mutex);
 223     assert(l->magic = LIST_MAGIC);      /* set magic via assert abuse */
 224     return(l);
 225 }
 226
 227
 228 void
 229 list_destroy (List l)
 230 {
 231     ListIterator i, iTmp;
 232     ListNode p, pTmp;
 233
 234     assert(l != NULL);
 235     list_mutex_lock(&l->mutex);
 236     assert(l->magic == LIST_MAGIC);
 237     i = l->iNext;
 238     while (i) {
 239         assert(i->magic == LIST_MAGIC);
 240         iTmp = i->iNext;
 241         assert(i->magic = ~LIST_MAGIC); /* clear magic via assert abuse */
 242         list_iterator_free(i);
 243         i = iTmp;
 244     }
 245     p = l->head;
 246     while (p) {
 247         pTmp = p->next;
 248         if (p->data && l->fDel)
 249             l->fDel(p->data);
 250         list_node_free(p);
 251         p = pTmp;
 252     }
 253     assert(l->magic = ~LIST_MAGIC);     /* clear magic via assert abuse */
 254     list_mutex_unlock(&l->mutex);
 255     list_mutex_destroy(&l->mutex);
 256     list_free(l);
 257     return;
 258 }
 259
 260
 261 int
 262 list_is_empty (List l)
 263 {
 264     int n;
 265
 266     assert(l != NULL);
 267     list_mutex_lock(&l->mutex);
 268     assert(l->magic == LIST_MAGIC);
 269     n = l->count;
 270     list_mutex_unlock(&l->mutex);
 271     return(n == 0);
 272 }
 273
 274
 275 int
 276 list_count (List l)
 277 {
 278     int n;
 279
 280     assert(l != NULL);
 281     list_mutex_lock(&l->mutex);
 282     assert(l->magic == LIST_MAGIC);
 283     n = l->count;
 284     list_mutex_unlock(&l->mutex);
 285     return(n);
 286 }
 287
 288
 289 void *
 290 list_append (List l, void *x)
 291 {
 292     void *v;
 293
 294     assert(l != NULL);
 295     assert(x != NULL);
 296     list_mutex_lock(&l->mutex);
 297     assert(l->magic == LIST_MAGIC);
 298     v = list_node_create(l, l->tail, x);
 299     list_mutex_unlock(&l->mutex);
 300     return(v);
 301 }
 302
 303
 304 void *
 305 list_prepend (List l, void *x)
 306 {
 307     void *v;
 308
 309     assert(l != NULL);
 310     assert(x != NULL);
 311     list_mutex_lock(&l->mutex);
 312     assert(l->magic == LIST_MAGIC);
 313     v = list_node_create(l, &l->head, x);
 314     list_mutex_unlock(&l->mutex);
 315     return(v);
 316 }
 317
 318
 319 void *
 320 list_find_first (List l, ListFindF f, void *key)
 321 {
 322     ListNode p;
 323     void *v = NULL;
 324
 325     assert(l != NULL);
 326     assert(f != NULL);
 327     list_mutex_lock(&l->mutex);
 328     assert(l->magic == LIST_MAGIC);
 329     for (p=l->head; p; p=p->next) {
 330         if (f(p->data, key)) {
 331             v = p->data;
 332             break;
 333         }
 334     }
 335     list_mutex_unlock(&l->mutex);
 336     return(v);
 337 }
 338
 339
 340 int
 341 list_delete_all (List l, ListFindF f, void *key)
 342 {
 343     ListNode *pp;
 344     void *v;
 345     int n = 0;
 346
 347     assert(l != NULL);
 348     assert(f != NULL);
 349     list_mutex_lock(&l->mutex);
 350     assert(l->magic == LIST_MAGIC);
 351     pp = &l->head;
 352     while (*pp) {
 353         if (f((*pp)->data, key)) {
 354             if ((v = list_node_destroy(l, pp))) {
 355                 if (l->fDel)
 356                     l->fDel(v);
 357                 n++;
 358             }
 359         }
 360         else {
 361             pp = &(*pp)->next;
 362         }
 363     }
 364     list_mutex_unlock(&l->mutex);
 365     return(n);
 366 }
 367
 368
 369 int
 370 list_for_each (List l, ListForF f, void *arg)
 371 {
 372     ListNode p;
 373     int n = 0;
 374
 375     assert(l != NULL);
 376     assert(f != NULL);
 377     list_mutex_lock(&l->mutex);
 378     assert(l->magic == LIST_MAGIC);
 379     for (p=l->head; p; p=p->next) {
 380         n++;
 381         if (f(p->data, arg) < 0) {
 382             n = -n;
 383             break;
 384         }
 385     }
 386     list_mutex_unlock(&l->mutex);
 387     return(n);
 388 }
 389
 390
 391 void
 392 list_sort (List l, ListCmpF f)
 393 {
 394 /*  Note: Time complexity O(n^2).
 395  */
 396     ListNode *pp, *ppPrev, *ppPos, pTmp;
 397     ListIterator i;
 398
 399     assert(l != NULL);
 400     assert(f != NULL);
 401     list_mutex_lock(&l->mutex);
 402     assert(l->magic == LIST_MAGIC);
 403     if (l->count > 1) {
 404         ppPrev = &l->head;
 405         pp = &(*ppPrev)->next;
 406         while (*pp) {
 407             if (f((*pp)->data, (*ppPrev)->data) < 0) {
 408                 ppPos = &l->head;
 409                 while (f((*pp)->data, (*ppPos)->data) >= 0)
 410                     ppPos = &(*ppPos)->next;
 411                 pTmp = (*pp)->next;
 412                 (*pp)->next = *ppPos;
 413                 *ppPos = *pp;
 414                 *pp = pTmp;
 415                 if (ppPrev == ppPos)
 416                     ppPrev = &(*ppPrev)->next;
 417             }
 418             else {
 419                 ppPrev = pp;
 420                 pp = &(*pp)->next;
 421             }
 422         }
 423         l->tail = pp;
 424
 425         for (i=l->iNext; i; i=i->iNext) {
 426             assert(i->magic == LIST_MAGIC);
 427             i->pos = i->list->head;
 428             i->prev = &i->list->head;
 429         }
 430     }
 431     list_mutex_unlock(&l->mutex);
 432     return;
 433 }
 434
 435
 436 void *
 437 list_push (List l, void *x)
 438 {
 439     void *v;
 440
 441     assert(l != NULL);
 442     assert(x != NULL);
 443     list_mutex_lock(&l->mutex);
 444     assert(l->magic == LIST_MAGIC);
 445     v = list_node_create(l, &l->head, x);
 446     list_mutex_unlock(&l->mutex);
 447     return(v);
 448 }
 449
 450
 451 void *
 452 list_pop (List l)
 453 {
 454     void *v;
 455
 456     assert(l != NULL);
 457     list_mutex_lock(&l->mutex);
 458     assert(l->magic == LIST_MAGIC);
 459     v = list_node_destroy(l, &l->head);
 460     list_mutex_unlock(&l->mutex);
 461     return(v);
 462 }
 463
 464
 465 void *
 466 list_peek (List l)
 467 {
 468     void *v;
 469
 470     assert(l != NULL);
 471     list_mutex_lock(&l->mutex);
 472     assert(l->magic == LIST_MAGIC);
 473     v = (l->head) ? l->head->data : NULL;
 474     list_mutex_unlock(&l->mutex);
 475     return(v);
 476 }
 477
 478
 479 void *
 480 list_enqueue (List l, void *x)
 481 {
 482     void *v;
 483
 484     assert(l != NULL);
 485     assert(x != NULL);
 486     list_mutex_lock(&l->mutex);
 487     assert(l->magic == LIST_MAGIC);
 488     v = list_node_create(l, l->tail, x);
 489     list_mutex_unlock(&l->mutex);
 490     return(v);
 491 }
 492
 493
 494 void *
 495 list_dequeue (List l)
 496 {
 497     void *v;
 498
 499     assert(l != NULL);
 500     list_mutex_lock(&l->mutex);
 501     assert(l->magic == LIST_MAGIC);
 502     v = list_node_destroy(l, &l->head);
 503     list_mutex_unlock(&l->mutex);
 504     return(v);
 505 }
 506
 507
 508 ListIterator
 509 list_iterator_create (List l)
 510 {
 511     ListIterator i;
 512
 513     assert(l != NULL);
 514     if (!(i = list_iterator_alloc()))
 515         return(lsd_nomem_error(__FILE__, __LINE__, "list iterator create"));
 516     i->list = l;
 517     list_mutex_lock(&l->mutex);
 518     assert(l->magic == LIST_MAGIC);
 519     i->pos = l->head;
 520     i->prev = &l->head;
 521     i->iNext = l->iNext;
 522     l->iNext = i;
 523     assert(i->magic = LIST_MAGIC);      /* set magic via assert abuse */
 524     list_mutex_unlock(&l->mutex);
 525     return(i);
 526 }
 527
 528
 529 void
 530 list_iterator_reset (ListIterator i)
 531 {
 532     assert(i != NULL);
 533     assert(i->magic == LIST_MAGIC);
 534     list_mutex_lock(&i->list->mutex);
 535     assert(i->list->magic == LIST_MAGIC);
 536     i->pos = i->list->head;
 537     i->prev = &i->list->head;
 538     list_mutex_unlock(&i->list->mutex);
 539     return;
 540 }
 541
 542
 543 void
 544 list_iterator_destroy (ListIterator i)
 545 {
 546     ListIterator *pi;
 547
 548     assert(i != NULL);
 549     assert(i->magic == LIST_MAGIC);
 550     list_mutex_lock(&i->list->mutex);
 551     assert(i->list->magic == LIST_MAGIC);
 552     for (pi=&i->list->iNext; *pi; pi=&(*pi)->iNext) {
 553         assert((*pi)->magic == LIST_MAGIC);
 554         if (*pi == i) {
 555             *pi = (*pi)->iNext;
 556             break;
 557         }
 558     }
 559     list_mutex_unlock(&i->list->mutex);
 560     assert(i->magic = ~LIST_MAGIC);     /* clear magic via assert abuse */
 561     list_iterator_free(i);
 562     return;
 563 }
 564
 565
 566 void *
 567 list_next (ListIterator i)
 568 {
 569     ListNode p;
 570
 571     assert(i != NULL);
 572     assert(i->magic == LIST_MAGIC);
 573     list_mutex_lock(&i->list->mutex);
 574     assert(i->list->magic == LIST_MAGIC);
 575     if ((p = i->pos))
 576         i->pos = p->next;
 577     if (*i->prev != p)
 578         i->prev = &(*i->prev)->next;
 579     list_mutex_unlock(&i->list->mutex);
 580     return(p ? p->data : NULL);
 581 }
 582
 583
 584 void *
 585 list_insert (ListIterator i, void *x)
 586 {
 587     void *v;
 588
 589     assert(i != NULL);
 590     assert(x != NULL);
 591     assert(i->magic == LIST_MAGIC);
 592     list_mutex_lock(&i->list->mutex);
 593     assert(i->list->magic == LIST_MAGIC);
 594     v = list_node_create(i->list, i->prev, x);
 595     list_mutex_unlock(&i->list->mutex);
 596     return(v);
 597 }
 598
 599
 600 void *
 601 list_find (ListIterator i, ListFindF f, void *key)
 602 {
 603     void *v;
 604
 605     assert(i != NULL);
 606     assert(f != NULL);
 607     assert(i->magic == LIST_MAGIC);
 608     while ((v=list_next(i)) && !f(v,key)) {;}
 609     return(v);
 610 }
 611
 612
 613 void *
 614 list_remove (ListIterator i)
 615 {
 616     void *v = NULL;
 617
 618     assert(i != NULL);
 619     assert(i->magic == LIST_MAGIC);
 620     list_mutex_lock(&i->list->mutex);
 621     assert(i->list->magic == LIST_MAGIC);
 622     if (*i->prev != i->pos)
 623         v = list_node_destroy(i->list, i->prev);
 624     list_mutex_unlock(&i->list->mutex);
 625     return(v);
 626 }
 627
 628
 629 int
 630 list_delete (ListIterator i)
 631 {
 632     void *v;
 633
 634     assert(i != NULL);
 635     assert(i->magic == LIST_MAGIC);
 636     if ((v = list_remove(i))) {
 637         if (i->list->fDel)
 638             i->list->fDel(v);
 639         return(1);
 640     }
 641     return(0);
 642 }
 643
 644
 645 static void *
 646 list_node_create (List l, ListNode *pp, void *x)
 647 {
 648 /*  Inserts data pointed to by [x] into list [l] after [pp],
 649  *    the address of the previous node's "next" ptr.
 650  *  Returns a ptr to data [x], or NULL if insertion fails.
 651  *  This routine assumes the list is already locked upon entry.
 652  */
 653     ListNode p;
 654     ListIterator i;
 655
 656     assert(l != NULL);
 657     assert(l->magic == LIST_MAGIC);
 658     assert(list_mutex_is_locked(&l->mutex));
 659     assert(pp != NULL);
 660     assert(x != NULL);
 661     if (!(p = list_node_alloc()))
 662         return(lsd_nomem_error(__FILE__, __LINE__, "list node create"));
 663     p->data = x;
 664     if (!(p->next = *pp))
 665         l->tail = &p->next;
 666     *pp = p;
 667     l->count++;
 668     for (i=l->iNext; i; i=i->iNext) {
 669         assert(i->magic == LIST_MAGIC);
 670         if (i->prev == pp)
 671             i->prev = &p->next;
 672         else if (i->pos == p->next)
 673             i->pos = p;
 674         assert((i->pos == *i->prev) || (i->pos == (*i->prev)->next));
 675     }
 676     return(x);
 677 }
 678
 679
 680 static void *
 681 list_node_destroy (List l, ListNode *pp)
 682 {
 683 /*  Removes the node pointed to by [*pp] from from list [l],
 684  *    where [pp] is the address of the previous node's "next" ptr.
 685  *  Returns the data ptr associated with list item being removed,
 686  *    or NULL if [*pp] points to the NULL element.
 687  *  This routine assumes the list is already locked upon entry.
 688  */
 689     void *v;
 690     ListNode p;
 691     ListIterator i;
 692
 693     assert(l != NULL);
 694     assert(l->magic == LIST_MAGIC);
 695     assert(list_mutex_is_locked(&l->mutex));
 696     assert(pp != NULL);
 697     if (!(p = *pp))
 698         return(NULL);
 699     v = p->data;
 700     if (!(*pp = p->next))
 701         l->tail = pp;
 702     l->count--;
 703     for (i=l->iNext; i; i=i->iNext) {
 704         assert(i->magic == LIST_MAGIC);
 705         if (i->pos == p)
 706             i->pos = p->next, i->prev = pp;
 707         else if (i->prev == &p->next)
 708             i->prev = pp;
 709         assert((i->pos == *i->prev) || (i->pos == (*i->prev)->next));
 710     }
 711     list_node_free(p);
 712     return(v);
 713 }
 714
 715
 716 static List
 717 list_alloc (void)
 718 {
 719     return(list_alloc_aux(sizeof(struct list), &list_free_lists));
 720 }
 721
 722
 723 static void
 724 list_free (List l)
 725 {
 726     list_free_aux(l, &list_free_lists);
 727     return;
 728 }
 729
 730
 731 static ListNode
 732 list_node_alloc (void)
 733 {
 734     return(list_alloc_aux(sizeof(struct listNode), &list_free_nodes));
 735 }
 736
 737
 738 static void
 739 list_node_free (ListNode p)
 740 {
 741     list_free_aux(p, &list_free_nodes);
 742     return;
 743 }
 744
 745
 746 static ListIterator
 747 list_iterator_alloc (void)
 748 {
 749     return(list_alloc_aux(sizeof(struct listIterator), &list_free_iterators));
 750 }
 751
 752
 753 static void
 754 list_iterator_free (ListIterator i)
 755 {
 756     list_free_aux(i, &list_free_iterators);
 757     return;
 758 }
 759
 760
 761 static void *
 762 list_alloc_aux (int size, void *pfreelist)
 763 {
 764 /*  Allocates an object of [size] bytes from the freelist [*pfreelist].
 765  *  Memory is added to the freelist in chunks of size LIST_ALLOC.
 766  *  Returns a ptr to the object, or NULL if the memory request fails.
 767  */
 768     void **px;
 769     void **pfree = pfreelist;
 770     void **plast;
 771
 772     assert(sizeof(char) == 1);
 773     assert(size >= (int)sizeof(void *));
 774     assert(pfreelist != NULL);
 775     assert(LIST_ALLOC > 0);
 776     list_mutex_lock(&list_free_lock);
 777     if (!*pfree) {
 778         if ((*pfree = malloc(LIST_ALLOC * size))) {
 779             px = *pfree;
 780             plast = (void **) ((char *) *pfree + ((LIST_ALLOC - 1) * size));
 781             while (px < plast)
 782                 *px = (char *) px + size, px = *px;
 783             *plast = NULL;
 784         }
 785     }
 786     if ((px = *pfree))
 787         *pfree = *px;
 788     else
 789         errno = ENOMEM;
 790     list_mutex_unlock(&list_free_lock);
 791     return(px);
 792 }
 793
 794
 795 static void
 796 list_free_aux (void *x, void *pfreelist)
 797 {
 798 /*  Frees the object [x], returning it to the freelist [*pfreelist].
 799  */
 800     void **px = x;
 801     void **pfree = pfreelist;
 802
 803     assert(x != NULL);
 804     assert(pfreelist != NULL);
 805     list_mutex_lock(&list_free_lock);
 806     *px = *pfree;
 807     *pfree = px;
 808     list_mutex_unlock(&list_free_lock);
 809     return;
 810 }
 811
 812
 813 #ifndef NDEBUG
 814 #ifdef WITH_PTHREADS
 815 static int
 816 list_mutex_is_locked (pthread_mutex_t *mutex)
 817 {
 818 /*  Returns true if the mutex is locked; o/w, returns false.
 819  */
 820     int rc;
 821
 822     assert(mutex != NULL);
 823     rc = pthread_mutex_trylock(mutex);
 824     return(rc == EBUSY ? 1 : 0);
 825 }
 826 #endif /* WITH_PTHREADS */
 827 #endif /* !NDEBUG */