--- /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);
+ assert(l->magic = LIST_MAGIC); /* set magic via assert abuse */
+ 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;
+ assert(i->magic = ~LIST_MAGIC); /* clear magic via assert abuse */
+ 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;
+ }
+ assert(l->magic = ~LIST_MAGIC); /* clear magic via assert abuse */
+ 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;
+ assert(i->magic = LIST_MAGIC); /* set magic via assert abuse */
+ 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);
+ assert(i->magic = ~LIST_MAGIC); /* clear magic via assert abuse */
+ 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_ubuntu-artful-kernel.git / blobdiff