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>.
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 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)
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
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 *****************************************************************************/
30 #endif /* HAVE_CONFIG_H */
34 #endif /* WITH_PTHREADS */
43 /*********************
45 *********************/
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
55 # define lsd_fatal_error(file, line, mesg) \
57 fprintf(stderr, "ERROR: [%s:%d] %s: %s\n", \
58 file, line, mesg, strerror(errno)); \
60 # endif /* !lsd_fatal_error */
61 #endif /* !WITH_LSD_FATAL_ERROR_FUNC */
64 /*********************
66 *********************/
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 */
83 #define LIST_MAGIC 0xDEADBEEF
91 void *data
; /* node's data */
92 struct listNode
*next
; /* next node in list */
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() */
101 unsigned int magic
; /* sentinel for asserting validity */
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 */
112 pthread_mutex_t mutex
; /* mutex to protect access to list */
113 #endif /* WITH_PTHREADS */
115 unsigned int magic
; /* sentinel for asserting validity */
119 typedef struct listNode
* ListNode
;
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
);
142 static List list_free_lists
= NULL
;
143 static ListNode list_free_nodes
= NULL
;
144 static ListIterator list_free_iterators
= NULL
;
147 static pthread_mutex_t list_free_lock
= PTHREAD_MUTEX_INITIALIZER
;
148 #endif /* WITH_PTHREADS */
157 # define list_mutex_init(mutex) \
159 int e = pthread_mutex_init(mutex, NULL); \
162 lsd_fatal_error(__FILE__, __LINE__, "list mutex init"); \
167 # define list_mutex_lock(mutex) \
169 int e = pthread_mutex_lock(mutex); \
172 lsd_fatal_error(__FILE__, __LINE__, "list mutex lock"); \
177 # define list_mutex_unlock(mutex) \
179 int e = pthread_mutex_unlock(mutex); \
182 lsd_fatal_error(__FILE__, __LINE__, "list mutex unlock"); \
187 # define list_mutex_destroy(mutex) \
189 int e = pthread_mutex_destroy(mutex); \
192 lsd_fatal_error(__FILE__, __LINE__, "list mutex destroy"); \
198 static int list_mutex_is_locked (pthread_mutex_t
*mutex
);
199 # endif /* !NDEBUG */
201 #else /* !WITH_PTHREADS */
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)
209 #endif /* !WITH_PTHREADS */
217 list_create (ListDelF f
)
221 if (!(l
= list_alloc()))
222 return(lsd_nomem_error(__FILE__
, __LINE__
, "list create"));
228 list_mutex_init(&l
->mutex
);
229 assert(l
->magic
= LIST_MAGIC
); /* set magic via assert abuse */
235 list_destroy (List l
)
237 ListIterator i
, iTmp
;
241 list_mutex_lock(&l
->mutex
);
242 assert(l
->magic
== LIST_MAGIC
);
245 assert(i
->magic
== LIST_MAGIC
);
247 assert(i
->magic
= ~LIST_MAGIC
); /* clear magic via assert abuse */
248 list_iterator_free(i
);
254 if (p
->data
&& l
->fDel
)
259 assert(l
->magic
= ~LIST_MAGIC
); /* clear magic via assert abuse */
260 list_mutex_unlock(&l
->mutex
);
261 list_mutex_destroy(&l
->mutex
);
268 list_is_empty (List l
)
273 list_mutex_lock(&l
->mutex
);
274 assert(l
->magic
== LIST_MAGIC
);
276 list_mutex_unlock(&l
->mutex
);
287 list_mutex_lock(&l
->mutex
);
288 assert(l
->magic
== LIST_MAGIC
);
290 list_mutex_unlock(&l
->mutex
);
296 list_append (List l
, void *x
)
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
);
311 list_prepend (List l
, void *x
)
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
);
326 list_find_first (List l
, ListFindF f
, void *key
)
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
)) {
341 list_mutex_unlock(&l
->mutex
);
347 list_delete_all (List l
, ListFindF f
, void *key
)
355 list_mutex_lock(&l
->mutex
);
356 assert(l
->magic
== LIST_MAGIC
);
359 if (f((*pp
)->data
, key
)) {
360 if ((v
= list_node_destroy(l
, pp
))) {
370 list_mutex_unlock(&l
->mutex
);
376 list_for_each (List l
, ListForF f
, void *arg
)
383 list_mutex_lock(&l
->mutex
);
384 assert(l
->magic
== LIST_MAGIC
);
385 for (p
=l
->head
; p
; p
=p
->next
) {
387 if (f(p
->data
, arg
) < 0) {
392 list_mutex_unlock(&l
->mutex
);
398 list_sort (List l
, ListCmpF f
)
400 /* Note: Time complexity O(n^2).
402 ListNode
*pp
, *ppPrev
, *ppPos
, pTmp
;
407 list_mutex_lock(&l
->mutex
);
408 assert(l
->magic
== LIST_MAGIC
);
411 pp
= &(*ppPrev
)->next
;
413 if (f((*pp
)->data
, (*ppPrev
)->data
) < 0) {
415 while (f((*pp
)->data
, (*ppPos
)->data
) >= 0)
416 ppPos
= &(*ppPos
)->next
;
418 (*pp
)->next
= *ppPos
;
422 ppPrev
= &(*ppPrev
)->next
;
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
;
437 list_mutex_unlock(&l
->mutex
);
443 list_push (List l
, void *x
)
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
);
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
);
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
);
486 list_enqueue (List l
, void *x
)
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
);
501 list_dequeue (List l
)
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
);
515 list_iterator_create (List l
)
520 if (!(i
= list_iterator_alloc()))
521 return(lsd_nomem_error(__FILE__
, __LINE__
, "list iterator create"));
523 list_mutex_lock(&l
->mutex
);
524 assert(l
->magic
== LIST_MAGIC
);
529 assert(i
->magic
= LIST_MAGIC
); /* set magic via assert abuse */
530 list_mutex_unlock(&l
->mutex
);
536 list_iterator_reset (ListIterator i
)
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
);
550 list_iterator_destroy (ListIterator i
)
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
);
565 list_mutex_unlock(&i
->list
->mutex
);
566 assert(i
->magic
= ~LIST_MAGIC
); /* clear magic via assert abuse */
567 list_iterator_free(i
);
573 list_next (ListIterator i
)
578 assert(i
->magic
== LIST_MAGIC
);
579 list_mutex_lock(&i
->list
->mutex
);
580 assert(i
->list
->magic
== LIST_MAGIC
);
584 i
->prev
= &(*i
->prev
)->next
;
585 list_mutex_unlock(&i
->list
->mutex
);
586 return(p
? p
->data
: NULL
);
591 list_insert (ListIterator i
, void *x
)
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
);
607 list_find (ListIterator i
, ListFindF f
, void *key
)
613 assert(i
->magic
== LIST_MAGIC
);
614 while ((v
=list_next(i
)) && !f(v
,key
)) {;}
620 list_remove (ListIterator i
)
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
);
636 list_delete (ListIterator i
)
641 assert(i
->magic
== LIST_MAGIC
);
642 if ((v
= list_remove(i
))) {
652 list_node_create (List l
, ListNode
*pp
, void *x
)
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.
663 assert(l
->magic
== LIST_MAGIC
);
664 assert(list_mutex_is_locked(&l
->mutex
));
667 if (!(p
= list_node_alloc()))
668 return(lsd_nomem_error(__FILE__
, __LINE__
, "list node create"));
670 if (!(p
->next
= *pp
))
674 for (i
=l
->iNext
; i
; i
=i
->iNext
) {
675 assert(i
->magic
== LIST_MAGIC
);
678 else if (i
->pos
== p
->next
)
680 assert((i
->pos
== *i
->prev
) || (i
->pos
== (*i
->prev
)->next
));
687 list_node_destroy (List l
, ListNode
*pp
)
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.
700 assert(l
->magic
== LIST_MAGIC
);
701 assert(list_mutex_is_locked(&l
->mutex
));
706 if (!(*pp
= p
->next
))
709 for (i
=l
->iNext
; i
; i
=i
->iNext
) {
710 assert(i
->magic
== LIST_MAGIC
);
712 i
->pos
= p
->next
, i
->prev
= pp
;
713 else if (i
->prev
== &p
->next
)
715 assert((i
->pos
== *i
->prev
) || (i
->pos
== (*i
->prev
)->next
));
725 return(list_alloc_aux(sizeof(struct list
), &list_free_lists
));
732 list_free_aux(l
, &list_free_lists
);
738 list_node_alloc (void)
740 return(list_alloc_aux(sizeof(struct listNode
), &list_free_nodes
));
745 list_node_free (ListNode p
)
747 list_free_aux(p
, &list_free_nodes
);
753 list_iterator_alloc (void)
755 return(list_alloc_aux(sizeof(struct listIterator
), &list_free_iterators
));
760 list_iterator_free (ListIterator i
)
762 list_free_aux(i
, &list_free_iterators
);
768 list_alloc_aux (int size
, void *pfreelist
)
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.
775 void **pfree
= pfreelist
;
778 assert(sizeof(char) == 1);
779 assert(size
>= sizeof(void *));
780 assert(pfreelist
!= NULL
);
781 assert(LIST_ALLOC
> 0);
782 list_mutex_lock(&list_free_lock
);
784 if ((*pfree
= malloc(LIST_ALLOC
* size
))) {
786 plast
= (void **) ((char *) *pfree
+ ((LIST_ALLOC
- 1) * size
));
788 *px
= (char *) px
+ size
, px
= *px
;
796 list_mutex_unlock(&list_free_lock
);
802 list_free_aux (void *x
, void *pfreelist
)
804 /* Frees the object [x], returning it to the freelist [*pfreelist].
807 void **pfree
= pfreelist
;
810 assert(pfreelist
!= NULL
);
811 list_mutex_lock(&list_free_lock
);
814 list_mutex_unlock(&list_free_lock
);
822 list_mutex_is_locked (pthread_mutex_t
*mutex
)
824 /* Returns true if the mutex is locked; o/w, returns false.
828 assert(mutex
!= NULL
);
829 rc
= pthread_mutex_trylock(mutex
);
830 return(rc
== EBUSY
? 1 : 0);
832 #endif /* WITH_PTHREADS */