diff options
| -rw-r--r-- | include/ouroboros/list.h | 98 | ||||
| -rw-r--r-- | src/lib/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | src/lib/list.c | 125 |
3 files changed, 135 insertions, 89 deletions
diff --git a/include/ouroboros/list.h b/include/ouroboros/list.h index 5ac68d9f..49163efd 100644 --- a/include/ouroboros/list.h +++ b/include/ouroboros/list.h @@ -49,22 +49,6 @@ struct list_head { (ptr)->next = (ptr); (ptr)->prev = (ptr); \ } while (0) -/* - * Insert a new entry between two known consecutive entries. - * - * This is only for internal list manipulation where we know - * the prev/next entries already! - */ -static void __list_add(struct list_head * new, - struct list_head * prev, - struct list_head * next) -{ - next->prev = new; - new->next = next; - new->prev = prev; - prev->next = new; -} - /** * list_add - add a new entry * @new: new entry to be added @@ -74,10 +58,7 @@ static void __list_add(struct list_head * new, * This is good for implementing stacks. */ void list_add(struct list_head * new, - struct list_head * head) -{ - __list_add(new, head, head->next); -} + struct list_head * head); /** * list_add_tail - add a new entry @@ -88,24 +69,7 @@ void list_add(struct list_head * new, * This is useful for implementing queues. */ void list_add_tail(struct list_head * new, - struct list_head * head) -{ - __list_add(new, head->prev, head); -} - -/* - * Delete a list entry by making the prev/next entries - * point to each other. - * - * This is only for internal list manipulation where we know - * the prev/next entries already! - */ -static void __list_del(struct list_head * prev, - struct list_head * next) -{ - next->prev = prev; - prev->next = next; -} + struct list_head * head); /** * list_del - deletes entry from list. @@ -113,22 +77,13 @@ static void __list_del(struct list_head * prev, * 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) -{ - __list_del(entry->prev, entry->next); - entry->next = (void *) 0; - entry->prev = (void *) 0; -} +void list_del(struct list_head * entry); /** * 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) -{ - __list_del(entry->prev, entry->next); - INIT_LIST_HEAD(entry); -} +void list_del_init(struct list_head * entry); /** * list_move - delete from one list and add as another's head @@ -136,11 +91,7 @@ void list_del_init(struct list_head * entry) * @head: the head that will precede our entry */ void list_move(struct list_head * list, - struct list_head * head) -{ - __list_del(list->prev, list->next); - list_add(list, head); -} + struct list_head * head); /** * list_move_tail - delete from one list and add as another's tail @@ -148,34 +99,13 @@ void list_move(struct list_head * list, * @head: the head that will follow our entry */ void list_move_tail(struct list_head * list, - struct list_head * head) -{ - __list_del(list->prev, list->next); - list_add_tail(list, head); -} + struct list_head * head); /** * list_empty - tests whether a list is empty * @head: the list to test. */ -int list_empty(struct list_head * head) -{ - return head->next == head; -} - -static void __list_splice(struct list_head *list, - struct list_head *head) -{ - struct list_head *first = list->next; - struct list_head *last = list->prev; - struct list_head *at = head->next; - - first->prev = head; - head->next = first; - - last->next = at; - at->prev = last; -} +int list_empty(struct list_head * head); /** * list_splice - join two lists @@ -183,11 +113,7 @@ static void __list_splice(struct list_head *list, * @head: the place to add it in the first list. */ void list_splice(struct list_head * list, - struct list_head * head) -{ - if (!list_empty(list)) - __list_splice(list, head); -} + struct list_head * head); /** * list_splice_init - join two lists and reinitialise the emptied list. @@ -197,13 +123,7 @@ void list_splice(struct list_head * list, * The list at @list is reinitialised */ void list_splice_init(struct list_head * list, - struct list_head * head) -{ - if (!list_empty(list)) { - __list_splice(list, head); - INIT_LIST_HEAD(list); - } -} + struct list_head * head); /** * list_entry - get the struct for this entry diff --git a/src/lib/CMakeLists.txt b/src/lib/CMakeLists.txt index c52a5609..589c8769 100644 --- a/src/lib/CMakeLists.txt +++ b/src/lib/CMakeLists.txt @@ -12,6 +12,7 @@ set(SOURCE_FILES du_buff.c ipcp.c irm.c + list.c rina_name.c sockets.c ) diff --git a/src/lib/list.c b/src/lib/list.c new file mode 100644 index 00000000..75063e22 --- /dev/null +++ b/src/lib/list.c @@ -0,0 +1,125 @@ +/* + * Ouroboros - Copyright (C) 2016 + * + * 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. + * + * 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) + * + * Sander Vrijders <sander.vrijders@intec.ugent.be> + * + * This program 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. + * + * This program 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 this program; if not, write to the Free Software + * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + */ + +#include <ouroboros/list.h> + +static void __list_add(struct list_head * new, + struct list_head * prev, + struct list_head * next) +{ + next->prev = new; + new->next = next; + new->prev = prev; + prev->next = new; +} + +void list_add(struct list_head * new, + struct list_head * head) +{ + __list_add(new, head, head->next); +} + +void list_add_tail(struct list_head * new, + struct list_head * head) +{ + __list_add(new, head->prev, head); +} + +static void __list_del(struct list_head * prev, + struct list_head * next) +{ + next->prev = prev; + prev->next = next; +} + +void list_del(struct list_head * entry) +{ + __list_del(entry->prev, entry->next); + entry->next = (void *) 0; + entry->prev = (void *) 0; +} + +void list_del_init(struct list_head * entry) +{ + __list_del(entry->prev, entry->next); + INIT_LIST_HEAD(entry); +} + +void list_move(struct list_head * list, + struct list_head * head) +{ + __list_del(list->prev, list->next); + list_add(list, head); +} + +void list_move_tail(struct list_head * list, + struct list_head * head) +{ + __list_del(list->prev, list->next); + list_add_tail(list, head); +} + +int list_empty(struct list_head * head) +{ + return head->next == head; +} + +static void __list_splice(struct list_head *list, + struct list_head *head) +{ + struct list_head *first = list->next; + struct list_head *last = list->prev; + struct list_head *at = head->next; + + first->prev = head; + head->next = first; + + last->next = at; + at->prev = last; +} + +void list_splice(struct list_head * list, + struct list_head * head) +{ + if (!list_empty(list)) + __list_splice(list, head); +} + +void list_splice_init(struct list_head * list, + struct list_head * head) +{ + if (!list_empty(list)) { + __list_splice(list, head); + INIT_LIST_HEAD(list); + } +} |