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. --- src/lib/cdap.c | 6 +-- src/lib/cdap_req.c | 2 +- src/lib/hashtable.c | 4 +- src/lib/list.c | 128 ++++++++++++++++------------------------------------ 4 files changed, 44 insertions(+), 96 deletions(-) (limited to 'src/lib') diff --git a/src/lib/cdap.c b/src/lib/cdap.c index 17104770..869e929d 100644 --- a/src/lib/cdap.c +++ b/src/lib/cdap.c @@ -365,8 +365,8 @@ struct cdap * cdap_create(int fd) return NULL; } - INIT_LIST_HEAD(&instance->sent); - INIT_LIST_HEAD(&instance->rcvd); + list_head_init(&instance->sent); + list_head_init(&instance->rcvd); instance->fd = fd; @@ -573,7 +573,7 @@ cdap_key_t cdap_request_wait(struct cdap * instance, pthread_cleanup_push((void(*)(void *))pthread_mutex_unlock, (void *) &instance->rcvd_lock); - while (list_empty(&instance->rcvd)) + while (list_is_empty(&instance->rcvd)) pthread_cond_wait(&instance->rcvd_cond, &instance->rcvd_lock); rcvd = list_first_entry(&instance->rcvd, struct cdap_rcvd, next); diff --git a/src/lib/cdap_req.c b/src/lib/cdap_req.c index 57ad22c5..0c0d98c0 100644 --- a/src/lib/cdap_req.c +++ b/src/lib/cdap_req.c @@ -51,7 +51,7 @@ struct cdap_req * cdap_req_create(cdap_key_t key) pthread_cond_init(&creq->cond, &cattr); pthread_mutex_init(&creq->lock, NULL); - INIT_LIST_HEAD(&creq->next); + list_head_init(&creq->next); clock_gettime(PTHREAD_COND_CLOCK, &creq->birth); diff --git a/src/lib/hashtable.c b/src/lib/hashtable.c index 8dcd4ec1..e2b00de0 100644 --- a/src/lib/hashtable.c +++ b/src/lib/hashtable.c @@ -69,7 +69,7 @@ struct htable * htable_create(uint64_t buckets, bool hash_key) } for (i = 0; i < buckets; i++) - INIT_LIST_HEAD(&(tmp->buckets[i])); + list_head_init(&(tmp->buckets[i])); return tmp; } @@ -136,7 +136,7 @@ int htable_insert(struct htable * table, uint64_t key, void * val) entry->key = key; entry->val = val; - INIT_LIST_HEAD(&entry->next); + list_head_init(&entry->next); list_add(&entry->next, &(table->buckets[lookup_key])); diff --git a/src/lib/list.c b/src/lib/list.c index 0f3493e3..6bdb3461 100644 --- a/src/lib/list.c +++ b/src/lib/list.c @@ -3,122 +3,70 @@ * * 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 * - * 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) + * 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. * - * Sander Vrijders - * - * 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 */ #include -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; -} +#include -void list_del(struct list_head * entry) +void list_head_init(struct list_head * h) { - __list_del(entry->prev, entry->next); - entry->next = (void *) 0; - entry->prev = (void *) 0; + h->nxt = h; + h->prv = h; } -void list_del_init(struct list_head * entry) +static void add_list(struct list_head * n, + struct list_head * prv, + struct list_head * nxt) { - __list_del(entry->prev, entry->next); - INIT_LIST_HEAD(entry); + nxt->prv = n; + n->nxt = nxt; + n->prv = prv; + prv->nxt = n; } -void list_move(struct list_head * list, - struct list_head * head) +static void del_list(struct list_head * prv, + struct list_head * nxt) { - __list_del(list->prev, list->next); - list_add(list, head); + nxt->prv = prv; + prv->nxt = nxt; } -void list_move_tail(struct list_head * list, - struct list_head * head) +void list_add(struct list_head * n, + struct list_head * h) { - __list_del(list->prev, list->next); - list_add_tail(list, head); + add_list(n, h, h->nxt); } -int list_empty(struct list_head * head) +void list_add_tail(struct list_head * n, + struct list_head * h) { - 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; + add_list(n, h->prv, h); } -void list_splice(struct list_head * list, - struct list_head * head) +void list_del(struct list_head * e) { - if (!list_empty(list)) - __list_splice(list, head); + del_list(e->prv, e->nxt); + e->nxt = e->prv = NULL; } -void list_splice_init(struct list_head * list, - struct list_head * head) +bool list_is_empty(struct list_head * h) { - if (!list_empty(list)) { - __list_splice(list, head); - INIT_LIST_HEAD(list); - } + return h->nxt == h; } -- cgit v1.2.3