From ba46a8b5c5717cdff25b39a2cd03a461998921c5 Mon Sep 17 00:00:00 2001 From: dimitri staessens Date: Mon, 9 Jan 2017 15:37:49 +0100 Subject: lib: Revise implementation of list Adds LGPL license to the ouroboros lists. --- include/ouroboros/list.h | 176 +++++++++-------------------------------------- 1 file changed, 31 insertions(+), 145 deletions(-) (limited to 'include') 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 + * Dimitri Staessense * - * Sander Vrijders + * 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 +#include 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 -- cgit v1.2.3