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 */