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>.
8
* This file is from LSD-Tools, the LLNL Software Development Toolbox.
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.
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
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
*****************************************************************************/
28
#endif /* WITH_PTHREADS */
37
/*********************
39
*********************/
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
49
# define lsd_fatal_error(file, line, mesg) \
51
fprintf(stderr, "ERROR: [%s:%d] %s: %s\n", \
52
file, line, mesg, strerror(errno)); \
54
# endif /* !lsd_fatal_error */
55
#endif /* !WITH_LSD_FATAL_ERROR_FUNC */
58
/*********************
60
*********************/
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 */
77
#define LIST_MAGIC 0xDEADBEEF
85
void *data; /* node's data */
86
struct listNode *next; /* next node in list */
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() */
95
unsigned int magic; /* sentinel for asserting validity */
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 */
106
pthread_mutex_t mutex; /* mutex to protect access to list */
107
#endif /* WITH_PTHREADS */
109
unsigned int magic; /* sentinel for asserting validity */
113
typedef struct listNode * ListNode;
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);
136
static List list_free_lists = NULL;
137
static ListNode list_free_nodes = NULL;
138
static ListIterator list_free_iterators = NULL;
141
static pthread_mutex_t list_free_lock = PTHREAD_MUTEX_INITIALIZER;
142
#endif /* WITH_PTHREADS */
151
# define list_mutex_init(mutex) \
153
int e = pthread_mutex_init(mutex, NULL); \
156
lsd_fatal_error(__FILE__, __LINE__, "list mutex init"); \
161
# define list_mutex_lock(mutex) \
163
int e = pthread_mutex_lock(mutex); \
166
lsd_fatal_error(__FILE__, __LINE__, "list mutex lock"); \
171
# define list_mutex_unlock(mutex) \
173
int e = pthread_mutex_unlock(mutex); \
176
lsd_fatal_error(__FILE__, __LINE__, "list mutex unlock"); \
181
# define list_mutex_destroy(mutex) \
183
int e = pthread_mutex_destroy(mutex); \
186
lsd_fatal_error(__FILE__, __LINE__, "list mutex destroy"); \
192
static int list_mutex_is_locked (pthread_mutex_t *mutex);
193
# endif /* !NDEBUG */
195
#else /* !WITH_PTHREADS */
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)
203
#endif /* !WITH_PTHREADS */
211
list_create (ListDelF f)
215
if (!(l = list_alloc()))
216
return(lsd_nomem_error(__FILE__, __LINE__, "list create"));
222
list_mutex_init(&l->mutex);
223
assert(l->magic = LIST_MAGIC); /* set magic via assert abuse */
229
list_destroy (List l)
231
ListIterator i, iTmp;
235
list_mutex_lock(&l->mutex);
236
assert(l->magic == LIST_MAGIC);
239
assert(i->magic == LIST_MAGIC);
241
assert(i->magic = ~LIST_MAGIC); /* clear magic via assert abuse */
242
list_iterator_free(i);
248
if (p->data && l->fDel)
253
assert(l->magic = ~LIST_MAGIC); /* clear magic via assert abuse */
254
list_mutex_unlock(&l->mutex);
255
list_mutex_destroy(&l->mutex);
262
list_is_empty (List l)
267
list_mutex_lock(&l->mutex);
268
assert(l->magic == LIST_MAGIC);
270
list_mutex_unlock(&l->mutex);
281
list_mutex_lock(&l->mutex);
282
assert(l->magic == LIST_MAGIC);
284
list_mutex_unlock(&l->mutex);
290
list_append (List l, void *x)
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);
305
list_prepend (List l, void *x)
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);
320
list_find_first (List l, ListFindF f, void *key)
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)) {
335
list_mutex_unlock(&l->mutex);
341
list_delete_all (List l, ListFindF f, void *key)
349
list_mutex_lock(&l->mutex);
350
assert(l->magic == LIST_MAGIC);
353
if (f((*pp)->data, key)) {
354
if ((v = list_node_destroy(l, pp))) {
364
list_mutex_unlock(&l->mutex);
370
list_for_each (List l, ListForF f, void *arg)
377
list_mutex_lock(&l->mutex);
378
assert(l->magic == LIST_MAGIC);
379
for (p=l->head; p; p=p->next) {
381
if (f(p->data, arg) < 0) {
386
list_mutex_unlock(&l->mutex);
392
list_sort (List l, ListCmpF f)
394
/* Note: Time complexity O(n^2).
396
ListNode *pp, *ppPrev, *ppPos, pTmp;
401
list_mutex_lock(&l->mutex);
402
assert(l->magic == LIST_MAGIC);
405
pp = &(*ppPrev)->next;
407
if (f((*pp)->data, (*ppPrev)->data) < 0) {
409
while (f((*pp)->data, (*ppPos)->data) >= 0)
410
ppPos = &(*ppPos)->next;
412
(*pp)->next = *ppPos;
416
ppPrev = &(*ppPrev)->next;
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;
431
list_mutex_unlock(&l->mutex);
437
list_push (List l, void *x)
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);
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);
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);
480
list_enqueue (List l, void *x)
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);
495
list_dequeue (List l)
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);
509
list_iterator_create (List l)
514
if (!(i = list_iterator_alloc()))
515
return(lsd_nomem_error(__FILE__, __LINE__, "list iterator create"));
517
list_mutex_lock(&l->mutex);
518
assert(l->magic == LIST_MAGIC);
523
assert(i->magic = LIST_MAGIC); /* set magic via assert abuse */
524
list_mutex_unlock(&l->mutex);
530
list_iterator_reset (ListIterator i)
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);
544
list_iterator_destroy (ListIterator i)
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);
559
list_mutex_unlock(&i->list->mutex);
560
assert(i->magic = ~LIST_MAGIC); /* clear magic via assert abuse */
561
list_iterator_free(i);
567
list_next (ListIterator i)
572
assert(i->magic == LIST_MAGIC);
573
list_mutex_lock(&i->list->mutex);
574
assert(i->list->magic == LIST_MAGIC);
578
i->prev = &(*i->prev)->next;
579
list_mutex_unlock(&i->list->mutex);
580
return(p ? p->data : NULL);
585
list_insert (ListIterator i, void *x)
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);
601
list_find (ListIterator i, ListFindF f, void *key)
607
assert(i->magic == LIST_MAGIC);
608
while ((v=list_next(i)) && !f(v,key)) {;}
614
list_remove (ListIterator i)
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);
630
list_delete (ListIterator i)
635
assert(i->magic == LIST_MAGIC);
636
if ((v = list_remove(i))) {
646
list_node_create (List l, ListNode *pp, void *x)
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.
657
assert(l->magic == LIST_MAGIC);
658
assert(list_mutex_is_locked(&l->mutex));
661
if (!(p = list_node_alloc()))
662
return(lsd_nomem_error(__FILE__, __LINE__, "list node create"));
664
if (!(p->next = *pp))
668
for (i=l->iNext; i; i=i->iNext) {
669
assert(i->magic == LIST_MAGIC);
672
else if (i->pos == p->next)
674
assert((i->pos == *i->prev) || (i->pos == (*i->prev)->next));
681
list_node_destroy (List l, ListNode *pp)
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.
694
assert(l->magic == LIST_MAGIC);
695
assert(list_mutex_is_locked(&l->mutex));
700
if (!(*pp = p->next))
703
for (i=l->iNext; i; i=i->iNext) {
704
assert(i->magic == LIST_MAGIC);
706
i->pos = p->next, i->prev = pp;
707
else if (i->prev == &p->next)
709
assert((i->pos == *i->prev) || (i->pos == (*i->prev)->next));
719
return(list_alloc_aux(sizeof(struct list), &list_free_lists));
726
list_free_aux(l, &list_free_lists);
732
list_node_alloc (void)
734
return(list_alloc_aux(sizeof(struct listNode), &list_free_nodes));
739
list_node_free (ListNode p)
741
list_free_aux(p, &list_free_nodes);
747
list_iterator_alloc (void)
749
return(list_alloc_aux(sizeof(struct listIterator), &list_free_iterators));
754
list_iterator_free (ListIterator i)
756
list_free_aux(i, &list_free_iterators);
762
list_alloc_aux (int size, void *pfreelist)
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.
769
void **pfree = pfreelist;
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);
778
if ((*pfree = malloc(LIST_ALLOC * size))) {
780
plast = (void **) ((char *) *pfree + ((LIST_ALLOC - 1) * size));
782
*px = (char *) px + size, px = *px;
790
list_mutex_unlock(&list_free_lock);
796
list_free_aux (void *x, void *pfreelist)
798
/* Frees the object [x], returning it to the freelist [*pfreelist].
801
void **pfree = pfreelist;
804
assert(pfreelist != NULL);
805
list_mutex_lock(&list_free_lock);
808
list_mutex_unlock(&list_free_lock);
816
list_mutex_is_locked (pthread_mutex_t *mutex)
818
/* Returns true if the mutex is locked; o/w, returns false.
822
assert(mutex != NULL);
823
rc = pthread_mutex_trylock(mutex);
824
return(rc == EBUSY ? 1 : 0);
826
#endif /* WITH_PTHREADS */
added
removed
lib/list.c
