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 #ifndef NDEBUG
 224     l->magic = LIST_MAGIC;
 225 #endif
 226     return(l);
 227 }
 228
 229
 230 void
 231 list_destroy (List l)
 232 {
 233     ListIterator i, iTmp;
 234     ListNode p, pTmp;
 235
 236     assert(l != NULL);
 237     list_mutex_lock(&l->mutex);
 238     assert(l->magic == LIST_MAGIC);
 239     i = l->iNext;
 240     while (i) {
 241         assert(i->magic == LIST_MAGIC);
 242         iTmp = i->iNext;
 243 #ifndef NDEBUG
 244         i->magic = ~LIST_MAGIC;
 245 #endif /* !NDEBUG */
 246         list_iterator_free(i);
 247         i = iTmp;
 248     }
 249     p = l->head;
 250     while (p) {
 251         pTmp = p->next;
 252         if (p->data && l->fDel)
 253             l->fDel(p->data);
 254         list_node_free(p);
 255         p = pTmp;
 256     }
 257 #ifndef NDEBUG
 258     l->magic = ~LIST_MAGIC;
 259 #endif /* !NDEBUG */
 260     list_mutex_unlock(&l->mutex);
 261     list_mutex_destroy(&l->mutex);
 262     list_free(l);
 263     return;
 264 }
 265
 266
 267 int
 268 list_is_empty (List l)
 269 {
 270     int n;
 271
 272     assert(l != NULL);
 273     list_mutex_lock(&l->mutex);
 274     assert(l->magic == LIST_MAGIC);
 275     n = l->count;
 276     list_mutex_unlock(&l->mutex);
 277     return(n == 0);
 278 }
 279
 280
 281 int
 282 list_count (List l)
 283 {
 284     int n;
 285
 286     assert(l != NULL);
 287     list_mutex_lock(&l->mutex);
 288     assert(l->magic == LIST_MAGIC);
 289     n = l->count;
 290     list_mutex_unlock(&l->mutex);
 291     return(n);
 292 }
 293
 294
 295 void *
 296 list_append (List l, void *x)
 297 {
 298     void *v;
 299
 300     assert(l != NULL);
 301     assert(x != NULL);
 302     list_mutex_lock(&l->mutex);
 303     assert(l->magic == LIST_MAGIC);
 304     v = list_node_create(l, l->tail, x);
 305     list_mutex_unlock(&l->mutex);
 306     return(v);
 307 }
 308
 309
 310 void *
 311 list_prepend (List l, void *x)
 312 {
 313     void *v;
 314
 315     assert(l != NULL);
 316     assert(x != NULL);
 317     list_mutex_lock(&l->mutex);
 318     assert(l->magic == LIST_MAGIC);
 319     v = list_node_create(l, &l->head, x);
 320     list_mutex_unlock(&l->mutex);
 321     return(v);
 322 }
 323
 324
 325 void *
 326 list_find_first (List l, ListFindF f, void *key)
 327 {
 328     ListNode p;
 329     void *v = NULL;
 330
 331     assert(l != NULL);
 332     assert(f != NULL);
 333     list_mutex_lock(&l->mutex);
 334     assert(l->magic == LIST_MAGIC);
 335     for (p=l->head; p; p=p->next) {
 336         if (f(p->data, key)) {
 337             v = p->data;
 338             break;
 339         }
 340     }
 341     list_mutex_unlock(&l->mutex);
 342     return(v);
 343 }
 344
 345
 346 int
 347 list_delete_all (List l, ListFindF f, void *key)
 348 {
 349     ListNode *pp;
 350     void *v;
 351     int n = 0;
 352
 353     assert(l != NULL);
 354     assert(f != NULL);
 355     list_mutex_lock(&l->mutex);
 356     assert(l->magic == LIST_MAGIC);
 357     pp = &l->head;
 358     while (*pp) {
 359         if (f((*pp)->data, key)) {
 360             if ((v = list_node_destroy(l, pp))) {
 361                 if (l->fDel)
 362                     l->fDel(v);
 363                 n++;
 364             }
 365         }
 366         else {
 367             pp = &(*pp)->next;
 368         }
 369     }
 370     list_mutex_unlock(&l->mutex);
 371     return(n);
 372 }
 373
 374
 375 int
 376 list_for_each (List l, ListForF f, void *arg)
 377 {
 378     ListNode p;
 379     int n = 0;
 380
 381     assert(l != NULL);
 382     assert(f != NULL);
 383     list_mutex_lock(&l->mutex);
 384     assert(l->magic == LIST_MAGIC);
 385     for (p=l->head; p; p=p->next) {
 386         n++;
 387         if (f(p->data, arg) < 0) {
 388             n = -n;
 389             break;
 390         }
 391     }
 392     list_mutex_unlock(&l->mutex);
 393     return(n);
 394 }
 395
 396
 397 void
 398 list_sort (List l, ListCmpF f)
 399 {
 400 /*  Note: Time complexity O(n^2).
 401  */
 402     ListNode *pp, *ppPrev, *ppPos, pTmp;
 403     ListIterator i;
 404
 405     assert(l != NULL);
 406     assert(f != NULL);
 407     list_mutex_lock(&l->mutex);
 408     assert(l->magic == LIST_MAGIC);
 409     if (l->count > 1) {
 410         ppPrev = &l->head;
 411         pp = &(*ppPrev)->next;
 412         while (*pp) {
 413             if (f((*pp)->data, (*ppPrev)->data) < 0) {
 414                 ppPos = &l->head;
 415                 while (f((*pp)->data, (*ppPos)->data) >= 0)
 416                     ppPos = &(*ppPos)->next;
 417                 pTmp = (*pp)->next;
 418                 (*pp)->next = *ppPos;
 419                 *ppPos = *pp;
 420                 *pp = pTmp;
 421                 if (ppPrev == ppPos)
 422                     ppPrev = &(*ppPrev)->next;
 423             }
 424             else {
 425                 ppPrev = pp;
 426                 pp = &(*pp)->next;
 427             }
 428         }
 429         l->tail = pp;
 430
 431         for (i=l->iNext; i; i=i->iNext) {
 432             assert(i->magic == LIST_MAGIC);
 433             i->pos = i->list->head;
 434             i->prev = &i->list->head;
 435         }
 436     }
 437     list_mutex_unlock(&l->mutex);
 438     return;
 439 }
 440
 441
 442 void *
 443 list_push (List l, void *x)
 444 {
 445     void *v;
 446
 447     assert(l != NULL);
 448     assert(x != NULL);
 449     list_mutex_lock(&l->mutex);
 450     assert(l->magic == LIST_MAGIC);
 451     v = list_node_create(l, &l->head, x);
 452     list_mutex_unlock(&l->mutex);
 453     return(v);
 454 }
 455
 456
 457 void *
 458 list_pop (List l)
 459 {
 460     void *v;
 461
 462     assert(l != NULL);
 463     list_mutex_lock(&l->mutex);
 464     assert(l->magic == LIST_MAGIC);
 465     v = list_node_destroy(l, &l->head);
 466     list_mutex_unlock(&l->mutex);
 467     return(v);
 468 }
 469
 470
 471 void *
 472 list_peek (List l)
 473 {
 474     void *v;
 475
 476     assert(l != NULL);
 477     list_mutex_lock(&l->mutex);
 478     assert(l->magic == LIST_MAGIC);
 479     v = (l->head) ? l->head->data : NULL;
 480     list_mutex_unlock(&l->mutex);
 481     return(v);
 482 }
 483
 484
 485 void *
 486 list_enqueue (List l, void *x)
 487 {
 488     void *v;
 489
 490     assert(l != NULL);
 491     assert(x != NULL);
 492     list_mutex_lock(&l->mutex);
 493     assert(l->magic == LIST_MAGIC);
 494     v = list_node_create(l, l->tail, x);
 495     list_mutex_unlock(&l->mutex);
 496     return(v);
 497 }
 498
 499
 500 void *
 501 list_dequeue (List l)
 502 {
 503     void *v;
 504
 505     assert(l != NULL);
 506     list_mutex_lock(&l->mutex);
 507     assert(l->magic == LIST_MAGIC);
 508     v = list_node_destroy(l, &l->head);
 509     list_mutex_unlock(&l->mutex);
 510     return(v);
 511 }
 512
 513
 514 ListIterator
 515 list_iterator_create (List l)
 516 {
 517     ListIterator i;
 518
 519     assert(l != NULL);
 520     if (!(i = list_iterator_alloc()))
 521         return(lsd_nomem_error(__FILE__, __LINE__, "list iterator create"));
 522     i->list = l;
 523     list_mutex_lock(&l->mutex);
 524     assert(l->magic == LIST_MAGIC);
 525     i->pos = l->head;
 526     i->prev = &l->head;
 527     i->iNext = l->iNext;
 528     l->iNext = i;
 529 #ifndef NDEBUG
 530     i->magic = LIST_MAGIC;
 531 #endif /* !NDEBUG */
 532     list_mutex_unlock(&l->mutex);
 533     return(i);
 534 }
 535
 536
 537 void
 538 list_iterator_reset (ListIterator i)
 539 {
 540     assert(i != NULL);
 541     assert(i->magic == LIST_MAGIC);
 542     list_mutex_lock(&i->list->mutex);
 543     assert(i->list->magic == LIST_MAGIC);
 544     i->pos = i->list->head;
 545     i->prev = &i->list->head;
 546     list_mutex_unlock(&i->list->mutex);
 547     return;
 548 }
 549
 550
 551 void
 552 list_iterator_destroy (ListIterator i)
 553 {
 554     ListIterator *pi;
 555
 556     assert(i != NULL);
 557     assert(i->magic == LIST_MAGIC);
 558     list_mutex_lock(&i->list->mutex);
 559     assert(i->list->magic == LIST_MAGIC);
 560     for (pi=&i->list->iNext; *pi; pi=&(*pi)->iNext) {
 561         assert((*pi)->magic == LIST_MAGIC);
 562         if (*pi == i) {
 563             *pi = (*pi)->iNext;
 564             break;
 565         }
 566     }
 567     list_mutex_unlock(&i->list->mutex);
 568 #ifndef NDEBUG
 569     i->magic = ~LIST_MAGIC;
 570 #endif /* !NDEBUG */
 571     list_iterator_free(i);
 572     return;
 573 }
 574
 575
 576 void *
 577 list_next (ListIterator i)
 578 {
 579     ListNode p;
 580
 581     assert(i != NULL);
 582     assert(i->magic == LIST_MAGIC);
 583     list_mutex_lock(&i->list->mutex);
 584     assert(i->list->magic == LIST_MAGIC);
 585     if ((p = i->pos))
 586         i->pos = p->next;
 587     if (*i->prev != p)
 588         i->prev = &(*i->prev)->next;
 589     list_mutex_unlock(&i->list->mutex);
 590     return(p ? p->data : NULL);
 591 }
 592
 593
 594 void *
 595 list_insert (ListIterator i, void *x)
 596 {
 597     void *v;
 598
 599     assert(i != NULL);
 600     assert(x != NULL);
 601     assert(i->magic == LIST_MAGIC);
 602     list_mutex_lock(&i->list->mutex);
 603     assert(i->list->magic == LIST_MAGIC);
 604     v = list_node_create(i->list, i->prev, x);
 605     list_mutex_unlock(&i->list->mutex);
 606     return(v);
 607 }
 608
 609
 610 void *
 611 list_find (ListIterator i, ListFindF f, void *key)
 612 {
 613     void *v;
 614
 615     assert(i != NULL);
 616     assert(f != NULL);
 617     assert(i->magic == LIST_MAGIC);
 618     while ((v=list_next(i)) && !f(v,key)) {;}
 619     return(v);
 620 }
 621
 622
 623 void *
 624 list_remove (ListIterator i)
 625 {
 626     void *v = NULL;
 627
 628     assert(i != NULL);
 629     assert(i->magic == LIST_MAGIC);
 630     list_mutex_lock(&i->list->mutex);
 631     assert(i->list->magic == LIST_MAGIC);
 632     if (*i->prev != i->pos)
 633         v = list_node_destroy(i->list, i->prev);
 634     list_mutex_unlock(&i->list->mutex);
 635     return(v);
 636 }
 637
 638
 639 int
 640 list_delete (ListIterator i)
 641 {
 642     void *v;
 643
 644     assert(i != NULL);
 645     assert(i->magic == LIST_MAGIC);
 646     if ((v = list_remove(i))) {
 647         if (i->list->fDel)
 648             i->list->fDel(v);
 649         return(1);
 650     }
 651     return(0);
 652 }
 653
 654
 655 static void *
 656 list_node_create (List l, ListNode *pp, void *x)
 657 {
 658 /*  Inserts data pointed to by [x] into list [l] after [pp],
 659  *    the address of the previous node's "next" ptr.
 660  *  Returns a ptr to data [x], or NULL if insertion fails.
 661  *  This routine assumes the list is already locked upon entry.
 662  */
 663     ListNode p;
 664     ListIterator i;
 665
 666     assert(l != NULL);
 667     assert(l->magic == LIST_MAGIC);
 668     assert(list_mutex_is_locked(&l->mutex));
 669     assert(pp != NULL);
 670     assert(x != NULL);
 671     if (!(p = list_node_alloc()))
 672         return(lsd_nomem_error(__FILE__, __LINE__, "list node create"));
 673     p->data = x;
 674     if (!(p->next = *pp))
 675         l->tail = &p->next;
 676     *pp = p;
 677     l->count++;
 678     for (i=l->iNext; i; i=i->iNext) {
 679         assert(i->magic == LIST_MAGIC);
 680         if (i->prev == pp)
 681             i->prev = &p->next;
 682         else if (i->pos == p->next)
 683             i->pos = p;
 684         assert((i->pos == *i->prev) || (i->pos == (*i->prev)->next));
 685     }
 686     return(x);
 687 }
 688
 689
 690 static void *
 691 list_node_destroy (List l, ListNode *pp)
 692 {
 693 /*  Removes the node pointed to by [*pp] from from list [l],
 694  *    where [pp] is the address of the previous node's "next" ptr.
 695  *  Returns the data ptr associated with list item being removed,
 696  *    or NULL if [*pp] points to the NULL element.
 697  *  This routine assumes the list is already locked upon entry.
 698  */
 699     void *v;
 700     ListNode p;
 701     ListIterator i;
 702
 703     assert(l != NULL);
 704     assert(l->magic == LIST_MAGIC);
 705     assert(list_mutex_is_locked(&l->mutex));
 706     assert(pp != NULL);
 707     if (!(p = *pp))
 708         return(NULL);
 709     v = p->data;
 710     if (!(*pp = p->next))
 711         l->tail = pp;
 712     l->count--;
 713     for (i=l->iNext; i; i=i->iNext) {
 714         assert(i->magic == LIST_MAGIC);
 715         if (i->pos == p)
 716             i->pos = p->next, i->prev = pp;
 717         else if (i->prev == &p->next)
 718             i->prev = pp;
 719         assert((i->pos == *i->prev) || (i->pos == (*i->prev)->next));
 720     }
 721     list_node_free(p);
 722     return(v);
 723 }
 724
 725
 726 static List
 727 list_alloc (void)
 728 {
 729     return(list_alloc_aux(sizeof(struct list), &list_free_lists));
 730 }
 731
 732
 733 static void
 734 list_free (List l)
 735 {
 736     list_free_aux(l, &list_free_lists);
 737     return;
 738 }
 739
 740
 741 static ListNode
 742 list_node_alloc (void)
 743 {
 744     return(list_alloc_aux(sizeof(struct listNode), &list_free_nodes));
 745 }
 746
 747
 748 static void
 749 list_node_free (ListNode p)
 750 {
 751     list_free_aux(p, &list_free_nodes);
 752     return;
 753 }
 754
 755
 756 static ListIterator
 757 list_iterator_alloc (void)
 758 {
 759     return(list_alloc_aux(sizeof(struct listIterator), &list_free_iterators));
 760 }
 761
 762
 763 static void
 764 list_iterator_free (ListIterator i)
 765 {
 766     list_free_aux(i, &list_free_iterators);
 767     return;
 768 }
 769
 770
 771 static void *
 772 list_alloc_aux (int size, void *pfreelist)
 773 {
 774 /*  Allocates an object of [size] bytes from the freelist [*pfreelist].
 775  *  Memory is added to the freelist in chunks of size LIST_ALLOC.
 776  *  Returns a ptr to the object, or NULL if the memory request fails.
 777  */
 778     void **px;
 779     void **pfree = pfreelist;
 780     void **plast;
 781
 782     assert(sizeof(char) == 1);
 783     assert(size >= (int)sizeof(void *));
 784     assert(pfreelist != NULL);
 785     assert(LIST_ALLOC > 0);
 786     list_mutex_lock(&list_free_lock);
 787     if (!*pfree) {
 788         if ((*pfree = malloc(LIST_ALLOC * size))) {
 789             px = *pfree;
 790             plast = (void **) ((char *) *pfree + ((LIST_ALLOC - 1) * size));
 791             while (px < plast)
 792                 *px = (char *) px + size, px = *px;
 793             *plast = NULL;
 794         }
 795     }
 796     if ((px = *pfree))
 797         *pfree = *px;
 798     else
 799         errno = ENOMEM;
 800     list_mutex_unlock(&list_free_lock);
 801     return(px);
 802 }
 803
 804
 805 static void
 806 list_free_aux (void *x, void *pfreelist)
 807 {
 808 /*  Frees the object [x], returning it to the freelist [*pfreelist].
 809  */
 810     void **px = x;
 811     void **pfree = pfreelist;
 812
 813     assert(x != NULL);
 814     assert(pfreelist != NULL);
 815     list_mutex_lock(&list_free_lock);
 816     *px = *pfree;
 817     *pfree = px;
 818     list_mutex_unlock(&list_free_lock);
 819     return;
 820 }
 821
 822
 823 #ifndef NDEBUG
 824 #ifdef WITH_PTHREADS
 825 static int
 826 list_mutex_is_locked (pthread_mutex_t *mutex)
 827 {
 828 /*  Returns true if the mutex is locked; o/w, returns false.
 829  */
 830     int rc;
 831
 832     assert(mutex != NULL);
 833     rc = pthread_mutex_trylock(mutex);
 834     return(rc == EBUSY ? 1 : 0);
 835 }
 836 #endif /* WITH_PTHREADS */
 837 #endif /* !NDEBUG */