lib/list.c

   1 /*****************************************************************************
   2  *  $Id: list.c 3709 2006-11-29 00:51:22Z dun $
   3  *****************************************************************************
   4  *  Copyright (C) 2001-2002 The Regents of the University of California.
   5  *  Produced at Lawrence Livermore National Laboratory (cf, DISCLAIMER).
   6  *  Written by Chris Dunlap <cdunlap@llnl.gov>.
   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 under
  11  *  the terms of the GNU General Public License as published by the Free
  12  *  Software Foundation; either version 2 of the License, or (at your option)
  13  *  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 for
  18  *  more details.
  19  *
  20  *  You should have received a copy of the GNU General Public License along
  21  *  with LSD-Tools; if not, write to the Free Software Foundation, Inc.,
  22  *  59 Temple Place, Suite 330, Boston, MA  02111-1307  USA.
  23  *****************************************************************************
  24  *  Refer to "list.h" for documentation on public functions.
  25  *****************************************************************************/
  26
  27
  28 #ifdef HAVE_CONFIG_H
  29 #  include "spl_config.h"
  30 #endif /* HAVE_CONFIG_H */
  31
  32 #ifdef WITH_PTHREADS
  33 #  include <pthread.h>
  34 #endif /* WITH_PTHREADS */
  35
  36 #include <assert.h>
  37 #include <errno.h>
  38 #include <stdlib.h>
  39 #include <string.h>
  40 #include "list.h"
  41
  42
  43 /*********************
  44  *  lsd_fatal_error  *
  45  *********************/
  46
  47 #ifdef WITH_LSD_FATAL_ERROR_FUNC
  48 #  undef lsd_fatal_error
  49    extern void lsd_fatal_error(char *file, int line, char *mesg);
  50 #else /* !WITH_LSD_FATAL_ERROR_FUNC */
  51 #  ifndef lsd_fatal_error
  52 #    include <errno.h>
  53 #    include <stdio.h>
  54 #    include <string.h>
  55 #    define lsd_fatal_error(file, line, mesg)                                 \
  56        do {                                                                   \
  57            fprintf(stderr, "ERROR: [%s:%d] %s: %s\n",                         \
  58                    file, line, mesg, strerror(errno));                        \
  59        } while (0)
  60 #  endif /* !lsd_fatal_error */
  61 #endif /* !WITH_LSD_FATAL_ERROR_FUNC */
  62
  63
  64 /*********************
  65  *  lsd_nomem_error  *
  66  *********************/
  67
  68 #ifdef WITH_LSD_NOMEM_ERROR_FUNC
  69 #  undef lsd_nomem_error
  70    extern void * lsd_nomem_error(char *file, int line, char *mesg);
  71 #else /* !WITH_LSD_NOMEM_ERROR_FUNC */
  72 #  ifndef lsd_nomem_error
  73 #    define lsd_nomem_error(file, line, mesg) (NULL)
  74 #  endif /* !lsd_nomem_error */
  75 #endif /* !WITH_LSD_NOMEM_ERROR_FUNC */
  76
  77
  78 /***************
  79  *  Constants  *
  80  ***************/
  81
  82 #define LIST_ALLOC 32
  83 #define LIST_MAGIC 0xDEADBEEF
  84
  85
  86 /****************
  87  *  Data Types  *
  88  ****************/
  89
  90 struct listNode {
  91     void                 *data;         /* node's data                       */
  92     struct listNode      *next;         /* next node in list                 */
  93 };
  94
  95 struct listIterator {
  96     struct list          *list;         /* the list being iterated           */
  97     struct listNode      *pos;          /* the next node to be iterated      */
  98     struct listNode     **prev;         /* addr of 'next' ptr to prv It node */
  99     struct listIterator  *iNext;        /* iterator chain for list_destroy() */
 100 #ifndef NDEBUG
 101     unsigned int          magic;        /* sentinel for asserting validity   */
 102 #endif /* !NDEBUG */
 103 };
 104
 105 struct list {
 106     struct listNode      *head;         /* head of the list                  */
 107     struct listNode     **tail;         /* addr of last node's 'next' ptr    */
 108     struct listIterator  *iNext;        /* iterator chain for list_destroy() */
 109     ListDelF              fDel;         /* function to delete node data      */
 110     int                   count;        /* number of nodes in list           */
 111 #ifdef WITH_PTHREADS
 112     pthread_mutex_t       mutex;        /* mutex to protect access to list   */
 113 #endif /* WITH_PTHREADS */
 114 #ifndef NDEBUG
 115     unsigned int          magic;        /* sentinel for asserting validity   */
 116 #endif /* !NDEBUG */
 117 };
 118
 119 typedef struct listNode * ListNode;
 120
 121
 122 /****************
 123  *  Prototypes  *
 124  ****************/
 125
 126 static void * list_node_create (List l, ListNode *pp, void *x);
 127 static void * list_node_destroy (List l, ListNode *pp);
 128 static List list_alloc (void);
 129 static void list_free (List l);
 130 static ListNode list_node_alloc (void);
 131 static void list_node_free (ListNode p);
 132 static ListIterator list_iterator_alloc (void);
 133 static void list_iterator_free (ListIterator i);
 134 static void * list_alloc_aux (int size, void *pfreelist);
 135 static void list_free_aux (void *x, void *pfreelist);
 136
 137
 138 /***************
 139  *  Variables  *
 140  ***************/
 141
 142 static List list_free_lists = NULL;
 143 static ListNode list_free_nodes = NULL;
 144 static ListIterator list_free_iterators = NULL;
 145
 146 #ifdef WITH_PTHREADS
 147 static pthread_mutex_t list_free_lock = PTHREAD_MUTEX_INITIALIZER;
 148 #endif /* WITH_PTHREADS */
 149
 150
 151 /************
 152  *  Macros  *
 153  ************/
 154
 155 #ifdef WITH_PTHREADS
 156
 157 #  define list_mutex_init(mutex)                                              \
 158      do {                                                                     \
 159          int e = pthread_mutex_init(mutex, NULL);                             \
 160          if (e != 0) {                                                        \
 161              errno = e;                                                       \
 162              lsd_fatal_error(__FILE__, __LINE__, "list mutex init");          \
 163              abort();                                                         \
 164          }                                                                    \
 165      } while (0)
 166
 167 #  define list_mutex_lock(mutex)                                              \
 168      do {                                                                     \
 169          int e = pthread_mutex_lock(mutex);                                   \
 170          if (e != 0) {                                                        \
 171              errno = e;                                                       \
 172              lsd_fatal_error(__FILE__, __LINE__, "list mutex lock");          \
 173              abort();                                                         \
 174          }                                                                    \
 175      } while (0)
 176
 177 #  define list_mutex_unlock(mutex)                                            \
 178      do {                                                                     \
 179          int e = pthread_mutex_unlock(mutex);                                 \
 180          if (e != 0) {                                                        \
 181              errno = e;                                                       \
 182              lsd_fatal_error(__FILE__, __LINE__, "list mutex unlock");        \
 183              abort();                                                         \
 184          }                                                                    \
 185      } while (0)
 186
 187 #  define list_mutex_destroy(mutex)                                           \
 188      do {                                                                     \
 189          int e = pthread_mutex_destroy(mutex);                                \
 190          if (e != 0) {                                                        \
 191              errno = e;                                                       \
 192              lsd_fatal_error(__FILE__, __LINE__, "list mutex destroy");       \
 193              abort();                                                         \
 194          }                                                                    \
 195      } while (0)
 196
 197 #  ifndef NDEBUG
 198      static int list_mutex_is_locked (pthread_mutex_t *mutex);
 199 #  endif /* !NDEBUG */
 200
 201 #else /* !WITH_PTHREADS */
 202
 203 #  define list_mutex_init(mutex)
 204 #  define list_mutex_lock(mutex)
 205 #  define list_mutex_unlock(mutex)
 206 #  define list_mutex_destroy(mutex)
 207 #  define list_mutex_is_locked(mutex) (1)
 208
 209 #endif /* !WITH_PTHREADS */
 210
 211
 212 /***************
 213  *  Functions  *
 214  ***************/
 215
 216 List
 217 list_create (ListDelF f)
 218 {
 219     List l;
 220
 221     if (!(l = list_alloc()))
 222         return(lsd_nomem_error(__FILE__, __LINE__, "list create"));
 223     l->head = NULL;
 224     l->tail = &l->head;
 225     l->iNext = NULL;
 226     l->fDel = f;
 227     l->count = 0;
 228     list_mutex_init(&l->mutex);
 229     assert(l->magic = LIST_MAGIC);      /* set magic via assert abuse */
 230     return(l);
 231 }
 232
 233
 234 void
 235 list_destroy (List l)
 236 {
 237     ListIterator i, iTmp;
 238     ListNode p, pTmp;
 239
 240     assert(l != NULL);
 241     list_mutex_lock(&l->mutex);
 242     assert(l->magic == LIST_MAGIC);
 243     i = l->iNext;
 244     while (i) {
 245         assert(i->magic == LIST_MAGIC);
 246         iTmp = i->iNext;
 247         assert(i->magic = ~LIST_MAGIC); /* clear magic via assert abuse */
 248         list_iterator_free(i);
 249         i = iTmp;
 250     }
 251     p = l->head;
 252     while (p) {
 253         pTmp = p->next;
 254         if (p->data && l->fDel)
 255             l->fDel(p->data);
 256         list_node_free(p);
 257         p = pTmp;
 258     }
 259     assert(l->magic = ~LIST_MAGIC);     /* clear magic via assert abuse */
 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     assert(i->magic = LIST_MAGIC);      /* set magic via assert abuse */
 530     list_mutex_unlock(&l->mutex);
 531     return(i);
 532 }
 533
 534
 535 void
 536 list_iterator_reset (ListIterator i)
 537 {
 538     assert(i != NULL);
 539     assert(i->magic == LIST_MAGIC);
 540     list_mutex_lock(&i->list->mutex);
 541     assert(i->list->magic == LIST_MAGIC);
 542     i->pos = i->list->head;
 543     i->prev = &i->list->head;
 544     list_mutex_unlock(&i->list->mutex);
 545     return;
 546 }
 547
 548
 549 void
 550 list_iterator_destroy (ListIterator i)
 551 {
 552     ListIterator *pi;
 553
 554     assert(i != NULL);
 555     assert(i->magic == LIST_MAGIC);
 556     list_mutex_lock(&i->list->mutex);
 557     assert(i->list->magic == LIST_MAGIC);
 558     for (pi=&i->list->iNext; *pi; pi=&(*pi)->iNext) {
 559         assert((*pi)->magic == LIST_MAGIC);
 560         if (*pi == i) {
 561             *pi = (*pi)->iNext;
 562             break;
 563         }
 564     }
 565     list_mutex_unlock(&i->list->mutex);
 566     assert(i->magic = ~LIST_MAGIC);     /* clear magic via assert abuse */
 567     list_iterator_free(i);
 568     return;
 569 }
 570
 571
 572 void *
 573 list_next (ListIterator i)
 574 {
 575     ListNode p;
 576
 577     assert(i != NULL);
 578     assert(i->magic == LIST_MAGIC);
 579     list_mutex_lock(&i->list->mutex);
 580     assert(i->list->magic == LIST_MAGIC);
 581     if ((p = i->pos))
 582         i->pos = p->next;
 583     if (*i->prev != p)
 584         i->prev = &(*i->prev)->next;
 585     list_mutex_unlock(&i->list->mutex);
 586     return(p ? p->data : NULL);
 587 }
 588
 589
 590 void *
 591 list_insert (ListIterator i, void *x)
 592 {
 593     void *v;
 594
 595     assert(i != NULL);
 596     assert(x != NULL);
 597     assert(i->magic == LIST_MAGIC);
 598     list_mutex_lock(&i->list->mutex);
 599     assert(i->list->magic == LIST_MAGIC);
 600     v = list_node_create(i->list, i->prev, x);
 601     list_mutex_unlock(&i->list->mutex);
 602     return(v);
 603 }
 604
 605
 606 void *
 607 list_find (ListIterator i, ListFindF f, void *key)
 608 {
 609     void *v;
 610
 611     assert(i != NULL);
 612     assert(f != NULL);
 613     assert(i->magic == LIST_MAGIC);
 614     while ((v=list_next(i)) && !f(v,key)) {;}
 615     return(v);
 616 }
 617
 618
 619 void *
 620 list_remove (ListIterator i)
 621 {
 622     void *v = NULL;
 623
 624     assert(i != NULL);
 625     assert(i->magic == LIST_MAGIC);
 626     list_mutex_lock(&i->list->mutex);
 627     assert(i->list->magic == LIST_MAGIC);
 628     if (*i->prev != i->pos)
 629         v = list_node_destroy(i->list, i->prev);
 630     list_mutex_unlock(&i->list->mutex);
 631     return(v);
 632 }
 633
 634
 635 int
 636 list_delete (ListIterator i)
 637 {
 638     void *v;
 639
 640     assert(i != NULL);
 641     assert(i->magic == LIST_MAGIC);
 642     if ((v = list_remove(i))) {
 643         if (i->list->fDel)
 644             i->list->fDel(v);
 645         return(1);
 646     }
 647     return(0);
 648 }
 649
 650
 651 static void *
 652 list_node_create (List l, ListNode *pp, void *x)
 653 {
 654 /*  Inserts data pointed to by [x] into list [l] after [pp],
 655  *    the address of the previous node's "next" ptr.
 656  *  Returns a ptr to data [x], or NULL if insertion fails.
 657  *  This routine assumes the list is already locked upon entry.
 658  */
 659     ListNode p;
 660     ListIterator i;
 661
 662     assert(l != NULL);
 663     assert(l->magic == LIST_MAGIC);
 664     assert(list_mutex_is_locked(&l->mutex));
 665     assert(pp != NULL);
 666     assert(x != NULL);
 667     if (!(p = list_node_alloc()))
 668         return(lsd_nomem_error(__FILE__, __LINE__, "list node create"));
 669     p->data = x;
 670     if (!(p->next = *pp))
 671         l->tail = &p->next;
 672     *pp = p;
 673     l->count++;
 674     for (i=l->iNext; i; i=i->iNext) {
 675         assert(i->magic == LIST_MAGIC);
 676         if (i->prev == pp)
 677             i->prev = &p->next;
 678         else if (i->pos == p->next)
 679             i->pos = p;
 680         assert((i->pos == *i->prev) || (i->pos == (*i->prev)->next));
 681     }
 682     return(x);
 683 }
 684
 685
 686 static void *
 687 list_node_destroy (List l, ListNode *pp)
 688 {
 689 /*  Removes the node pointed to by [*pp] from from list [l],
 690  *    where [pp] is the address of the previous node's "next" ptr.
 691  *  Returns the data ptr associated with list item being removed,
 692  *    or NULL if [*pp] points to the NULL element.
 693  *  This routine assumes the list is already locked upon entry.
 694  */
 695     void *v;
 696     ListNode p;
 697     ListIterator i;
 698
 699     assert(l != NULL);
 700     assert(l->magic == LIST_MAGIC);
 701     assert(list_mutex_is_locked(&l->mutex));
 702     assert(pp != NULL);
 703     if (!(p = *pp))
 704         return(NULL);
 705     v = p->data;
 706     if (!(*pp = p->next))
 707         l->tail = pp;
 708     l->count--;
 709     for (i=l->iNext; i; i=i->iNext) {
 710         assert(i->magic == LIST_MAGIC);
 711         if (i->pos == p)
 712             i->pos = p->next, i->prev = pp;
 713         else if (i->prev == &p->next)
 714             i->prev = pp;
 715         assert((i->pos == *i->prev) || (i->pos == (*i->prev)->next));
 716     }
 717     list_node_free(p);
 718     return(v);
 719 }
 720
 721
 722 static List
 723 list_alloc (void)
 724 {
 725     return(list_alloc_aux(sizeof(struct list), &list_free_lists));
 726 }
 727
 728
 729 static void
 730 list_free (List l)
 731 {
 732     list_free_aux(l, &list_free_lists);
 733     return;
 734 }
 735
 736
 737 static ListNode
 738 list_node_alloc (void)
 739 {
 740     return(list_alloc_aux(sizeof(struct listNode), &list_free_nodes));
 741 }
 742
 743
 744 static void
 745 list_node_free (ListNode p)
 746 {
 747     list_free_aux(p, &list_free_nodes);
 748     return;
 749 }
 750
 751
 752 static ListIterator
 753 list_iterator_alloc (void)
 754 {
 755     return(list_alloc_aux(sizeof(struct listIterator), &list_free_iterators));
 756 }
 757
 758
 759 static void
 760 list_iterator_free (ListIterator i)
 761 {
 762     list_free_aux(i, &list_free_iterators);
 763     return;
 764 }
 765
 766
 767 static void *
 768 list_alloc_aux (int size, void *pfreelist)
 769 {
 770 /*  Allocates an object of [size] bytes from the freelist [*pfreelist].
 771  *  Memory is added to the freelist in chunks of size LIST_ALLOC.
 772  *  Returns a ptr to the object, or NULL if the memory request fails.
 773  */
 774     void **px;
 775     void **pfree = pfreelist;
 776     void **plast;
 777
 778     assert(sizeof(char) == 1);
 779     assert(size >= (int)sizeof(void *));
 780     assert(pfreelist != NULL);
 781     assert(LIST_ALLOC > 0);
 782     list_mutex_lock(&list_free_lock);
 783     if (!*pfree) {
 784         if ((*pfree = malloc(LIST_ALLOC * size))) {
 785             px = *pfree;
 786             plast = (void **) ((char *) *pfree + ((LIST_ALLOC - 1) * size));
 787             while (px < plast)
 788                 *px = (char *) px + size, px = *px;
 789             *plast = NULL;
 790         }
 791     }
 792     if ((px = *pfree))
 793         *pfree = *px;
 794     else
 795         errno = ENOMEM;
 796     list_mutex_unlock(&list_free_lock);
 797     return(px);
 798 }
 799
 800
 801 static void
 802 list_free_aux (void *x, void *pfreelist)
 803 {
 804 /*  Frees the object [x], returning it to the freelist [*pfreelist].
 805  */
 806     void **px = x;
 807     void **pfree = pfreelist;
 808
 809     assert(x != NULL);
 810     assert(pfreelist != NULL);
 811     list_mutex_lock(&list_free_lock);
 812     *px = *pfree;
 813     *pfree = px;
 814     list_mutex_unlock(&list_free_lock);
 815     return;
 816 }
 817
 818
 819 #ifndef NDEBUG
 820 #ifdef WITH_PTHREADS
 821 static int
 822 list_mutex_is_locked (pthread_mutex_t *mutex)
 823 {
 824 /*  Returns true if the mutex is locked; o/w, returns false.
 825  */
 826     int rc;
 827
 828     assert(mutex != NULL);
 829     rc = pthread_mutex_trylock(mutex);
 830     return(rc == EBUSY ? 1 : 0);
 831 }
 832 #endif /* WITH_PTHREADS */
 833 #endif /* !NDEBUG */