lib: Revise implementation of list

Adds LGPL license to the ouroboros lists.

1 files changed, 31 insertions, 145 deletions

diff --git a/include/ouroboros/list.h b/include/ouroboros/list.h
index 91fe6660..debc6742 100644
--- a/include/ouroboros/list.h
+++ b/include/ouroboros/list.h
@@ -3,171 +3,57 @@
  *
  * Simple doubly linked list implementation.
  *
- * Some of the internal functions ("__xxx") are useful when
- * manipulating whole lists rather than single entries, as
- * sometimes we already know the next/prev entries and we can
- * generate better code by using them directly rather than
- * using the generic single-entry routines.
+ *    Sander Vrijders    <sander.vrijders@intec.ugent.be>
+ *    Dimitri Staessense <dimitri.staessens@intec.ugent.be>
  *
- *    Sander Vrijders <sander.vrijders@intec.ugent.be>
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public License
+ * version 2.1 as published by the Free Software Foundation.
  *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License version 2 as
- * published by the Free Software Foundation.
- *
- * This program is distributed in the hope that it will be useful,
+ * This library 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.
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
  *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ * 02110-1301 USA
  */
 
 #ifndef OUROBOROS_LIST_H
 #define OUROBOROS_LIST_H
 
-/*
- * This file is from the Linux Kernel (include/linux/list.h)
- * and modified by simply removing hardware prefetching of list items.
- * Here by copyright, credits attributed to wherever they belong.
- * Kulesh Shanmugasundaram (kulesh [squiggly] isis.poly.edu)
- */
+#include <stdbool.h>
+#include <sys/types.h>
 
 struct list_head {
-        struct list_head * next, * prev;
+        struct list_head * nxt, * prv;
 };
 
-#define LIST_HEAD_INIT(name) { &(name), &(name) }
-
-#define LIST_HEAD(name)                                 \
-        struct list_head name = LIST_HEAD_INIT(name)
+#define list_entry(ptr, type, mbr)                              \
+        ((type *)((char *)(ptr)-(size_t)(&((type *)0)->mbr)))
 
-#define INIT_LIST_HEAD(ptr) do {                                \
-                (ptr)->next = (ptr); (ptr)->prev = (ptr);       \
-        } while (0)
-
-/**
- * list_add - add a new entry
- * @new: new entry to be added
- * @head: list head to add it after
- *
- * Insert a new entry after the specified head.
- * This is good for implementing stacks.
- */
-void list_add(struct list_head * new,
-              struct list_head * head);
+#define list_first_entry(ptr, type, mbr)        \
+        list_entry((ptr)->nxt, type, mbr)
 
-/**
- * list_add_tail - add a new entry
- * @new: new entry to be added
- * @head: list head to add it before
- *
- * Insert a new entry before the specified head.
- * This is useful for implementing queues.
- */
-void list_add_tail(struct list_head * new,
-                   struct list_head * head);
+#define list_for_each(p, h)                             \
+        for (p = (h)->nxt; p != (h); p = p->nxt)
 
-/**
- * list_del - deletes entry from list.
- * @entry: the element to delete from the list.
- * Note: list_empty on entry does not return true after this,
- * the entry is in an undefined state.
- */
-void list_del(struct list_head * entry);
+#define list_for_each_safe(p, t, h)               \
+        for (p = (h)->nxt, t = p->nxt; p != (h);  \
+             p = t, t = p->nxt)
 
-/**
- * list_del_init - deletes entry from list and reinitialize it.
- * @entry: the element to delete from the list.
- */
-void list_del_init(struct list_head * entry);
+void list_head_init(struct list_head * h);
 
-/**
- * list_move - delete from one list and add as another's head
- * @list: the entry to move
- * @head: the head that will precede our entry
- */
-void list_move(struct list_head * list,
-               struct list_head * head);
+void list_add(struct list_head * e,
+              struct list_head * h);
 
-/**
- * list_move_tail - delete from one list and add as another's tail
- * @list: the entry to move
- * @head: the head that will follow our entry
- */
-void list_move_tail(struct list_head * list,
-                    struct list_head * head);
+void list_add_tail(struct list_head * e,
+                   struct list_head * h);
 
-/**
- * list_empty - tests whether a list is empty
- * @head: the list to test.
- */
-int list_empty(struct list_head * head);
+void list_del(struct list_head * e);
 
-/**
- * list_splice - join two lists
- * @list: the new list to add.
- * @head: the place to add it in the first list.
- */
-void list_splice(struct list_head * list,
-                 struct list_head * head);
-
-/**
- * list_splice_init - join two lists and reinitialise the emptied list.
- * @list: the new list to add.
- * @head: the place to add it in the first list.
- *
- * The list at @list is reinitialised
- */
-void list_splice_init(struct list_head * list,
-                      struct list_head * head);
-
-/**
- * list_entry - get the struct for this entry
- * @ptr:        the &struct list_head pointer.
- * @type:       the type of the struct this is embedded in.
- * @member:     the name of the list_struct within the struct.
- */
-#define list_entry(ptr, type, member)                                   \
-        ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
-
-/**
- * list_first_entry - get the struct for the first entry
- * expects the list to be non-empty
- * @ptr:        the &struct list_head pointer.
- * @type:       the type of the struct this is embedded in.
- * @member:     the name of the list_struct within the struct.
- */
-#define list_first_entry(ptr, type, member) \
-        list_entry((ptr)->next, type, member)
-
-/**
- * list_for_each - iterate over a list
- * @pos:        the &struct list_head to use as a loop counter.
- * @head:       the head for your list.
- */
-#define list_for_each(pos, head)                \
-        for (pos = (head)->next; pos != (head); \
-             pos = pos->next)
-/**
- * list_for_each_prev   -       iterate over a list backwards
- * @pos:        the &struct list_head to use as a loop counter.
- * @head:       the head for your list.
- */
-#define list_for_each_prev(pos, head)           \
-        for (pos = (head)->prev; pos != (head); \
-             pos = pos->prev)
-
-/**
- * list_for_each_safe - iterate over a list safe against removal of list entry
- * @pos:        the &struct list_head to use as a loop counter.
- * @n:          another &struct list_head to use as temporary storage
- * @head:       the head for your list.
- */
-#define list_for_each_safe(pos, n, head)                        \
-        for (pos = (head)->next, n = pos->next; pos != (head);  \
-             pos = n, n = pos->next)
+bool list_is_empty(struct list_head * h);
 
 #endif