summaryrefslogtreecommitdiff
path: root/include
diff options
context:
space:
mode:
authordimitri staessens <dimitri.staessens@intec.ugent.be>2017-01-09 15:37:49 +0100
committerdimitri staessens <dimitri.staessens@intec.ugent.be>2017-01-09 15:37:49 +0100
commitba46a8b5c5717cdff25b39a2cd03a461998921c5 (patch)
treedc5a1a48c70977d1c5b0abe90f068b17fd262f9c /include
parente56d24010287127fc6b9c9da8d1f7cf160c50253 (diff)
downloadouroboros-ba46a8b5c5717cdff25b39a2cd03a461998921c5.tar.gz
ouroboros-ba46a8b5c5717cdff25b39a2cd03a461998921c5.zip
lib: Revise implementation of list
Adds LGPL license to the ouroboros lists.
Diffstat (limited to 'include')
-rw-r--r--include/ouroboros/list.h176
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