+++ /dev/null
-/*****************************************************************************
- * Copyright (C) 2007-2010 Lawrence Livermore National Security, LLC.
- * Copyright (C) 2001-2007 The Regents of the University of California.
- * Produced at Lawrence Livermore National Laboratory (cf, DISCLAIMER).
- * Written by Chris Dunlap <cdunlap@llnl.gov>.
- * UCRL-CODE-235197
- *
- * This file is from LSD-Tools, the LLNL Software Development Toolbox.
- *
- * LSD-Tools is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License as published by the
- * Free Software Foundation; either version 2 of the License, or (at your
- * option) any later version.
- *
- * LSD-Tools is distributed in the hope that it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
- * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
- * for more details.
- *
- * You should have received a copy of the GNU General Public License along
- * with LSD-Tools. If not, see <http://www.gnu.org/licenses/>.
- *****************************************************************************
- * Refer to "list.h" for documentation on public functions.
- *****************************************************************************/
-
-#ifdef WITH_PTHREADS
-# include <pthread.h>
-#endif /* WITH_PTHREADS */
-
-#include <assert.h>
-#include <errno.h>
-#include <stdlib.h>
-#include <string.h>
-#include "list.h"
-
-
-/*********************
- * lsd_fatal_error *
- *********************/
-
-#ifdef WITH_LSD_FATAL_ERROR_FUNC
-# undef lsd_fatal_error
- extern void lsd_fatal_error(char *file, int line, char *mesg);
-#else /* !WITH_LSD_FATAL_ERROR_FUNC */
-# ifndef lsd_fatal_error
-# include <errno.h>
-# include <stdio.h>
-# include <string.h>
-# define lsd_fatal_error(file, line, mesg) \
- do { \
- fprintf(stderr, "ERROR: [%s:%d] %s: %s\n", \
- file, line, mesg, strerror(errno)); \
- } while (0)
-# endif /* !lsd_fatal_error */
-#endif /* !WITH_LSD_FATAL_ERROR_FUNC */
-
-
-/*********************
- * lsd_nomem_error *
- *********************/
-
-#ifdef WITH_LSD_NOMEM_ERROR_FUNC
-# undef lsd_nomem_error
- extern void * lsd_nomem_error(char *file, int line, char *mesg);
-#else /* !WITH_LSD_NOMEM_ERROR_FUNC */
-# ifndef lsd_nomem_error
-# define lsd_nomem_error(file, line, mesg) (NULL)
-# endif /* !lsd_nomem_error */
-#endif /* !WITH_LSD_NOMEM_ERROR_FUNC */
-
-
-/***************
- * Constants *
- ***************/
-
-#define LIST_ALLOC 32
-#define LIST_MAGIC 0xDEADBEEF
-
-
-/****************
- * Data Types *
- ****************/
-
-struct listNode {
- void *data; /* node's data */
- struct listNode *next; /* next node in list */
-};
-
-struct listIterator {
- struct list *list; /* the list being iterated */
- struct listNode *pos; /* the next node to be iterated */
- struct listNode **prev; /* addr of 'next' ptr to prv It node */
- struct listIterator *iNext; /* iterator chain for list_destroy() */
-#ifndef NDEBUG
- unsigned int magic; /* sentinel for asserting validity */
-#endif /* !NDEBUG */
-};
-
-struct list {
- struct listNode *head; /* head of the list */
- struct listNode **tail; /* addr of last node's 'next' ptr */
- struct listIterator *iNext; /* iterator chain for list_destroy() */
- ListDelF fDel; /* function to delete node data */
- int count; /* number of nodes in list */
-#ifdef WITH_PTHREADS
- pthread_mutex_t mutex; /* mutex to protect access to list */
-#endif /* WITH_PTHREADS */
-#ifndef NDEBUG
- unsigned int magic; /* sentinel for asserting validity */
-#endif /* !NDEBUG */
-};
-
-typedef struct listNode * ListNode;
-
-
-/****************
- * Prototypes *
- ****************/
-
-static void * list_node_create (List l, ListNode *pp, void *x);
-static void * list_node_destroy (List l, ListNode *pp);
-static List list_alloc (void);
-static void list_free (List l);
-static ListNode list_node_alloc (void);
-static void list_node_free (ListNode p);
-static ListIterator list_iterator_alloc (void);
-static void list_iterator_free (ListIterator i);
-static void * list_alloc_aux (int size, void *pfreelist);
-static void list_free_aux (void *x, void *pfreelist);
-
-
-/***************
- * Variables *
- ***************/
-
-static List list_free_lists = NULL;
-static ListNode list_free_nodes = NULL;
-static ListIterator list_free_iterators = NULL;
-
-#ifdef WITH_PTHREADS
-static pthread_mutex_t list_free_lock = PTHREAD_MUTEX_INITIALIZER;
-#endif /* WITH_PTHREADS */
-
-
-/************
- * Macros *
- ************/
-
-#ifdef WITH_PTHREADS
-
-# define list_mutex_init(mutex) \
- do { \
- int e = pthread_mutex_init(mutex, NULL); \
- if (e != 0) { \
- errno = e; \
- lsd_fatal_error(__FILE__, __LINE__, "list mutex init"); \
- abort(); \
- } \
- } while (0)
-
-# define list_mutex_lock(mutex) \
- do { \
- int e = pthread_mutex_lock(mutex); \
- if (e != 0) { \
- errno = e; \
- lsd_fatal_error(__FILE__, __LINE__, "list mutex lock"); \
- abort(); \
- } \
- } while (0)
-
-# define list_mutex_unlock(mutex) \
- do { \
- int e = pthread_mutex_unlock(mutex); \
- if (e != 0) { \
- errno = e; \
- lsd_fatal_error(__FILE__, __LINE__, "list mutex unlock"); \
- abort(); \
- } \
- } while (0)
-
-# define list_mutex_destroy(mutex) \
- do { \
- int e = pthread_mutex_destroy(mutex); \
- if (e != 0) { \
- errno = e; \
- lsd_fatal_error(__FILE__, __LINE__, "list mutex destroy"); \
- abort(); \
- } \
- } while (0)
-
-# ifndef NDEBUG
- static int list_mutex_is_locked (pthread_mutex_t *mutex);
-# endif /* !NDEBUG */
-
-#else /* !WITH_PTHREADS */
-
-# define list_mutex_init(mutex)
-# define list_mutex_lock(mutex)
-# define list_mutex_unlock(mutex)
-# define list_mutex_destroy(mutex)
-# define list_mutex_is_locked(mutex) (1)
-
-#endif /* !WITH_PTHREADS */
-
-
-/***************
- * Functions *
- ***************/
-
-List
-list_create (ListDelF f)
-{
- List l;
-
- if (!(l = list_alloc()))
- return(lsd_nomem_error(__FILE__, __LINE__, "list create"));
- l->head = NULL;
- l->tail = &l->head;
- l->iNext = NULL;
- l->fDel = f;
- l->count = 0;
- list_mutex_init(&l->mutex);
-#ifndef NDEBUG
- l->magic = LIST_MAGIC;
-#endif
- return(l);
-}
-
-
-void
-list_destroy (List l)
-{
- ListIterator i, iTmp;
- ListNode p, pTmp;
-
- assert(l != NULL);
- list_mutex_lock(&l->mutex);
- assert(l->magic == LIST_MAGIC);
- i = l->iNext;
- while (i) {
- assert(i->magic == LIST_MAGIC);
- iTmp = i->iNext;
-#ifndef NDEBUG
- i->magic = ~LIST_MAGIC;
-#endif /* !NDEBUG */
- list_iterator_free(i);
- i = iTmp;
- }
- p = l->head;
- while (p) {
- pTmp = p->next;
- if (p->data && l->fDel)
- l->fDel(p->data);
- list_node_free(p);
- p = pTmp;
- }
-#ifndef NDEBUG
- l->magic = ~LIST_MAGIC;
-#endif /* !NDEBUG */
- list_mutex_unlock(&l->mutex);
- list_mutex_destroy(&l->mutex);
- list_free(l);
- return;
-}
-
-
-int
-list_is_empty (List l)
-{
- int n;
-
- assert(l != NULL);
- list_mutex_lock(&l->mutex);
- assert(l->magic == LIST_MAGIC);
- n = l->count;
- list_mutex_unlock(&l->mutex);
- return(n == 0);
-}
-
-
-int
-list_count (List l)
-{
- int n;
-
- assert(l != NULL);
- list_mutex_lock(&l->mutex);
- assert(l->magic == LIST_MAGIC);
- n = l->count;
- list_mutex_unlock(&l->mutex);
- return(n);
-}
-
-
-void *
-list_append (List l, void *x)
-{
- void *v;
-
- assert(l != NULL);
- assert(x != NULL);
- list_mutex_lock(&l->mutex);
- assert(l->magic == LIST_MAGIC);
- v = list_node_create(l, l->tail, x);
- list_mutex_unlock(&l->mutex);
- return(v);
-}
-
-
-void *
-list_prepend (List l, void *x)
-{
- void *v;
-
- assert(l != NULL);
- assert(x != NULL);
- list_mutex_lock(&l->mutex);
- assert(l->magic == LIST_MAGIC);
- v = list_node_create(l, &l->head, x);
- list_mutex_unlock(&l->mutex);
- return(v);
-}
-
-
-void *
-list_find_first (List l, ListFindF f, void *key)
-{
- ListNode p;
- void *v = NULL;
-
- assert(l != NULL);
- assert(f != NULL);
- list_mutex_lock(&l->mutex);
- assert(l->magic == LIST_MAGIC);
- for (p=l->head; p; p=p->next) {
- if (f(p->data, key)) {
- v = p->data;
- break;
- }
- }
- list_mutex_unlock(&l->mutex);
- return(v);
-}
-
-
-int
-list_delete_all (List l, ListFindF f, void *key)
-{
- ListNode *pp;
- void *v;
- int n = 0;
-
- assert(l != NULL);
- assert(f != NULL);
- list_mutex_lock(&l->mutex);
- assert(l->magic == LIST_MAGIC);
- pp = &l->head;
- while (*pp) {
- if (f((*pp)->data, key)) {
- if ((v = list_node_destroy(l, pp))) {
- if (l->fDel)
- l->fDel(v);
- n++;
- }
- }
- else {
- pp = &(*pp)->next;
- }
- }
- list_mutex_unlock(&l->mutex);
- return(n);
-}
-
-
-int
-list_for_each (List l, ListForF f, void *arg)
-{
- ListNode p;
- int n = 0;
-
- assert(l != NULL);
- assert(f != NULL);
- list_mutex_lock(&l->mutex);
- assert(l->magic == LIST_MAGIC);
- for (p=l->head; p; p=p->next) {
- n++;
- if (f(p->data, arg) < 0) {
- n = -n;
- break;
- }
- }
- list_mutex_unlock(&l->mutex);
- return(n);
-}
-
-
-void
-list_sort (List l, ListCmpF f)
-{
-/* Note: Time complexity O(n^2).
- */
- ListNode *pp, *ppPrev, *ppPos, pTmp;
- ListIterator i;
-
- assert(l != NULL);
- assert(f != NULL);
- list_mutex_lock(&l->mutex);
- assert(l->magic == LIST_MAGIC);
- if (l->count > 1) {
- ppPrev = &l->head;
- pp = &(*ppPrev)->next;
- while (*pp) {
- if (f((*pp)->data, (*ppPrev)->data) < 0) {
- ppPos = &l->head;
- while (f((*pp)->data, (*ppPos)->data) >= 0)
- ppPos = &(*ppPos)->next;
- pTmp = (*pp)->next;
- (*pp)->next = *ppPos;
- *ppPos = *pp;
- *pp = pTmp;
- if (ppPrev == ppPos)
- ppPrev = &(*ppPrev)->next;
- }
- else {
- ppPrev = pp;
- pp = &(*pp)->next;
- }
- }
- l->tail = pp;
-
- for (i=l->iNext; i; i=i->iNext) {
- assert(i->magic == LIST_MAGIC);
- i->pos = i->list->head;
- i->prev = &i->list->head;
- }
- }
- list_mutex_unlock(&l->mutex);
- return;
-}
-
-
-void *
-list_push (List l, void *x)
-{
- void *v;
-
- assert(l != NULL);
- assert(x != NULL);
- list_mutex_lock(&l->mutex);
- assert(l->magic == LIST_MAGIC);
- v = list_node_create(l, &l->head, x);
- list_mutex_unlock(&l->mutex);
- return(v);
-}
-
-
-void *
-list_pop (List l)
-{
- void *v;
-
- assert(l != NULL);
- list_mutex_lock(&l->mutex);
- assert(l->magic == LIST_MAGIC);
- v = list_node_destroy(l, &l->head);
- list_mutex_unlock(&l->mutex);
- return(v);
-}
-
-
-void *
-list_peek (List l)
-{
- void *v;
-
- assert(l != NULL);
- list_mutex_lock(&l->mutex);
- assert(l->magic == LIST_MAGIC);
- v = (l->head) ? l->head->data : NULL;
- list_mutex_unlock(&l->mutex);
- return(v);
-}
-
-
-void *
-list_enqueue (List l, void *x)
-{
- void *v;
-
- assert(l != NULL);
- assert(x != NULL);
- list_mutex_lock(&l->mutex);
- assert(l->magic == LIST_MAGIC);
- v = list_node_create(l, l->tail, x);
- list_mutex_unlock(&l->mutex);
- return(v);
-}
-
-
-void *
-list_dequeue (List l)
-{
- void *v;
-
- assert(l != NULL);
- list_mutex_lock(&l->mutex);
- assert(l->magic == LIST_MAGIC);
- v = list_node_destroy(l, &l->head);
- list_mutex_unlock(&l->mutex);
- return(v);
-}
-
-
-ListIterator
-list_iterator_create (List l)
-{
- ListIterator i;
-
- assert(l != NULL);
- if (!(i = list_iterator_alloc()))
- return(lsd_nomem_error(__FILE__, __LINE__, "list iterator create"));
- i->list = l;
- list_mutex_lock(&l->mutex);
- assert(l->magic == LIST_MAGIC);
- i->pos = l->head;
- i->prev = &l->head;
- i->iNext = l->iNext;
- l->iNext = i;
-#ifndef NDEBUG
- i->magic = LIST_MAGIC;
-#endif /* !NDEBUG */
- list_mutex_unlock(&l->mutex);
- return(i);
-}
-
-
-void
-list_iterator_reset (ListIterator i)
-{
- assert(i != NULL);
- assert(i->magic == LIST_MAGIC);
- list_mutex_lock(&i->list->mutex);
- assert(i->list->magic == LIST_MAGIC);
- i->pos = i->list->head;
- i->prev = &i->list->head;
- list_mutex_unlock(&i->list->mutex);
- return;
-}
-
-
-void
-list_iterator_destroy (ListIterator i)
-{
- ListIterator *pi;
-
- assert(i != NULL);
- assert(i->magic == LIST_MAGIC);
- list_mutex_lock(&i->list->mutex);
- assert(i->list->magic == LIST_MAGIC);
- for (pi=&i->list->iNext; *pi; pi=&(*pi)->iNext) {
- assert((*pi)->magic == LIST_MAGIC);
- if (*pi == i) {
- *pi = (*pi)->iNext;
- break;
- }
- }
- list_mutex_unlock(&i->list->mutex);
-#ifndef NDEBUG
- i->magic = ~LIST_MAGIC;
-#endif /* !NDEBUG */
- list_iterator_free(i);
- return;
-}
-
-
-void *
-list_next (ListIterator i)
-{
- ListNode p;
-
- assert(i != NULL);
- assert(i->magic == LIST_MAGIC);
- list_mutex_lock(&i->list->mutex);
- assert(i->list->magic == LIST_MAGIC);
- if ((p = i->pos))
- i->pos = p->next;
- if (*i->prev != p)
- i->prev = &(*i->prev)->next;
- list_mutex_unlock(&i->list->mutex);
- return(p ? p->data : NULL);
-}
-
-
-void *
-list_insert (ListIterator i, void *x)
-{
- void *v;
-
- assert(i != NULL);
- assert(x != NULL);
- assert(i->magic == LIST_MAGIC);
- list_mutex_lock(&i->list->mutex);
- assert(i->list->magic == LIST_MAGIC);
- v = list_node_create(i->list, i->prev, x);
- list_mutex_unlock(&i->list->mutex);
- return(v);
-}
-
-
-void *
-list_find (ListIterator i, ListFindF f, void *key)
-{
- void *v;
-
- assert(i != NULL);
- assert(f != NULL);
- assert(i->magic == LIST_MAGIC);
- while ((v=list_next(i)) && !f(v,key)) {;}
- return(v);
-}
-
-
-void *
-list_remove (ListIterator i)
-{
- void *v = NULL;
-
- assert(i != NULL);
- assert(i->magic == LIST_MAGIC);
- list_mutex_lock(&i->list->mutex);
- assert(i->list->magic == LIST_MAGIC);
- if (*i->prev != i->pos)
- v = list_node_destroy(i->list, i->prev);
- list_mutex_unlock(&i->list->mutex);
- return(v);
-}
-
-
-int
-list_delete (ListIterator i)
-{
- void *v;
-
- assert(i != NULL);
- assert(i->magic == LIST_MAGIC);
- if ((v = list_remove(i))) {
- if (i->list->fDel)
- i->list->fDel(v);
- return(1);
- }
- return(0);
-}
-
-
-static void *
-list_node_create (List l, ListNode *pp, void *x)
-{
-/* Inserts data pointed to by [x] into list [l] after [pp],
- * the address of the previous node's "next" ptr.
- * Returns a ptr to data [x], or NULL if insertion fails.
- * This routine assumes the list is already locked upon entry.
- */
- ListNode p;
- ListIterator i;
-
- assert(l != NULL);
- assert(l->magic == LIST_MAGIC);
- assert(list_mutex_is_locked(&l->mutex));
- assert(pp != NULL);
- assert(x != NULL);
- if (!(p = list_node_alloc()))
- return(lsd_nomem_error(__FILE__, __LINE__, "list node create"));
- p->data = x;
- if (!(p->next = *pp))
- l->tail = &p->next;
- *pp = p;
- l->count++;
- for (i=l->iNext; i; i=i->iNext) {
- assert(i->magic == LIST_MAGIC);
- if (i->prev == pp)
- i->prev = &p->next;
- else if (i->pos == p->next)
- i->pos = p;
- assert((i->pos == *i->prev) || (i->pos == (*i->prev)->next));
- }
- return(x);
-}
-
-
-static void *
-list_node_destroy (List l, ListNode *pp)
-{
-/* Removes the node pointed to by [*pp] from from list [l],
- * where [pp] is the address of the previous node's "next" ptr.
- * Returns the data ptr associated with list item being removed,
- * or NULL if [*pp] points to the NULL element.
- * This routine assumes the list is already locked upon entry.
- */
- void *v;
- ListNode p;
- ListIterator i;
-
- assert(l != NULL);
- assert(l->magic == LIST_MAGIC);
- assert(list_mutex_is_locked(&l->mutex));
- assert(pp != NULL);
- if (!(p = *pp))
- return(NULL);
- v = p->data;
- if (!(*pp = p->next))
- l->tail = pp;
- l->count--;
- for (i=l->iNext; i; i=i->iNext) {
- assert(i->magic == LIST_MAGIC);
- if (i->pos == p)
- i->pos = p->next, i->prev = pp;
- else if (i->prev == &p->next)
- i->prev = pp;
- assert((i->pos == *i->prev) || (i->pos == (*i->prev)->next));
- }
- list_node_free(p);
- return(v);
-}
-
-
-static List
-list_alloc (void)
-{
- return(list_alloc_aux(sizeof(struct list), &list_free_lists));
-}
-
-
-static void
-list_free (List l)
-{
- list_free_aux(l, &list_free_lists);
- return;
-}
-
-
-static ListNode
-list_node_alloc (void)
-{
- return(list_alloc_aux(sizeof(struct listNode), &list_free_nodes));
-}
-
-
-static void
-list_node_free (ListNode p)
-{
- list_free_aux(p, &list_free_nodes);
- return;
-}
-
-
-static ListIterator
-list_iterator_alloc (void)
-{
- return(list_alloc_aux(sizeof(struct listIterator), &list_free_iterators));
-}
-
-
-static void
-list_iterator_free (ListIterator i)
-{
- list_free_aux(i, &list_free_iterators);
- return;
-}
-
-
-static void *
-list_alloc_aux (int size, void *pfreelist)
-{
-/* Allocates an object of [size] bytes from the freelist [*pfreelist].
- * Memory is added to the freelist in chunks of size LIST_ALLOC.
- * Returns a ptr to the object, or NULL if the memory request fails.
- */
- void **px;
- void **pfree = pfreelist;
- void **plast;
-
- assert(sizeof(char) == 1);
- assert(size >= (int)sizeof(void *));
- assert(pfreelist != NULL);
- assert(LIST_ALLOC > 0);
- list_mutex_lock(&list_free_lock);
- if (!*pfree) {
- if ((*pfree = malloc(LIST_ALLOC * size))) {
- px = *pfree;
- plast = (void **) ((char *) *pfree + ((LIST_ALLOC - 1) * size));
- while (px < plast)
- *px = (char *) px + size, px = *px;
- *plast = NULL;
- }
- }
- if ((px = *pfree))
- *pfree = *px;
- else
- errno = ENOMEM;
- list_mutex_unlock(&list_free_lock);
- return(px);
-}
-
-
-static void
-list_free_aux (void *x, void *pfreelist)
-{
-/* Frees the object [x], returning it to the freelist [*pfreelist].
- */
- void **px = x;
- void **pfree = pfreelist;
-
- assert(x != NULL);
- assert(pfreelist != NULL);
- list_mutex_lock(&list_free_lock);
- *px = *pfree;
- *pfree = px;
- list_mutex_unlock(&list_free_lock);
- return;
-}
-
-
-#ifndef NDEBUG
-#ifdef WITH_PTHREADS
-static int
-list_mutex_is_locked (pthread_mutex_t *mutex)
-{
-/* Returns true if the mutex is locked; o/w, returns false.
- */
- int rc;
-
- assert(mutex != NULL);
- rc = pthread_mutex_trylock(mutex);
- return(rc == EBUSY ? 1 : 0);
-}
-#endif /* WITH_PTHREADS */
-#endif /* !NDEBUG */
projects / mirror_spl.git / blobdiff