diff options
| -rw-r--r-- | include/ouroboros/list.h | 176 | ||||
| -rw-r--r-- | src/ipcpd/ipcp-data.c | 8 | ||||
| -rw-r--r-- | src/ipcpd/normal/ribmgr.c | 14 | ||||
| -rw-r--r-- | src/ipcpd/timerwheel.c | 4 | ||||
| -rw-r--r-- | src/irmd/api_table.c | 4 | ||||
| -rw-r--r-- | src/irmd/apn_table.c | 4 | ||||
| -rw-r--r-- | src/irmd/main.c | 18 | ||||
| -rw-r--r-- | src/irmd/registry.c | 18 | ||||
| -rw-r--r-- | src/lib/cdap.c | 6 | ||||
| -rw-r--r-- | src/lib/cdap_req.c | 2 | ||||
| -rw-r--r-- | src/lib/hashtable.c | 4 | ||||
| -rw-r--r-- | src/lib/list.c | 128 |
12 files changed, 110 insertions, 276 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 diff --git a/src/ipcpd/ipcp-data.c b/src/ipcpd/ipcp-data.c index 132684c2..2d1d2752 100644 --- a/src/ipcpd/ipcp-data.c +++ b/src/ipcpd/ipcp-data.c @@ -119,9 +119,9 @@ struct ipcp_data * ipcp_data_init(struct ipcp_data * dst, dst->dif_name = NULL; /* init the lists */ - INIT_LIST_HEAD(&dst->registry); - INIT_LIST_HEAD(&dst->directory); - INIT_LIST_HEAD(&dst->dir_queries); + list_head_init(&dst->registry); + list_head_init(&dst->directory); + list_head_init(&dst->dir_queries); /* init the locks */ pthread_rwlock_init(&dst->reg_lock, NULL); @@ -437,7 +437,7 @@ struct dir_query * ipcp_data_dir_query_create(char * name) pthread_cond_init(&query->cond, &cattr); pthread_mutex_init(&query->lock, NULL); - INIT_LIST_HEAD(&query->next); + list_head_init(&query->next); return query; } diff --git a/src/ipcpd/normal/ribmgr.c b/src/ipcpd/normal/ribmgr.c index e52db08a..6356d48c 100644 --- a/src/ipcpd/normal/ribmgr.c +++ b/src/ipcpd/normal/ribmgr.c @@ -471,9 +471,9 @@ static int write_ro_msg(struct cdap * neighbor, int ribmgr_init() { - INIT_LIST_HEAD(&rib.flows); - INIT_LIST_HEAD(&rib.subs); - INIT_LIST_HEAD(&rib.ro_ids); + list_head_init(&rib.flows); + list_head_init(&rib.subs); + list_head_init(&rib.ro_ids); rib.root = malloc(sizeof(*(rib.root))); if (rib.root == NULL) @@ -993,7 +993,7 @@ static int ro_id_create(char * name, ro_msg_t * msg) tmp->seqno = msg->seqno; tmp->full_name = strdup(name); - INIT_LIST_HEAD(&tmp->next); + list_head_init(&tmp->next); if (tmp->full_name == NULL) { free(tmp); @@ -1154,7 +1154,7 @@ static int ribmgr_add_flow(int fd) return -1; } - INIT_LIST_HEAD(&flow->next); + list_head_init(&flow->next); flow->instance = instance; flow->fd = fd; @@ -1310,7 +1310,7 @@ int ribmgr_enrol() pthread_rwlock_wrlock(&rib.flows_lock); - assert(!list_empty(&rib.flows)); + assert(!list_is_empty(&rib.flows)); flow = list_first_entry((&rib.flows), struct mgmt_flow, next); instance = flow->instance; @@ -1631,7 +1631,7 @@ int ro_subscribe(const char * name, struct ro_sub_ops * ops) if (sub == NULL) return -ENOMEM; - INIT_LIST_HEAD(&sub->next); + list_head_init(&sub->next); sub->name = strdup(name); if (sub->name == NULL) { diff --git a/src/ipcpd/timerwheel.c b/src/ipcpd/timerwheel.c index 4ef7ce2f..1d842c8f 100644 --- a/src/ipcpd/timerwheel.c +++ b/src/ipcpd/timerwheel.c @@ -232,7 +232,7 @@ struct timerwheel * timerwheel_create(unsigned int resolution, tw->intv.tv_sec = (tw->resolution / FRAC) / 1000; tw->intv.tv_nsec = ((tw->resolution / FRAC) % 1000) * MILLION; - INIT_LIST_HEAD(&tw->wq); + list_head_init(&tw->wq); if (pthread_mutex_init(&tw->lock, NULL)) { LOG_DBG("Could not init mutex."); @@ -265,7 +265,7 @@ struct timerwheel * timerwheel_create(unsigned int resolution, now.tv_nsec -= (now.tv_nsec % MILLION); for (i = 0; i < tw->elements; ++i) { - INIT_LIST_HEAD(&tw->wheel[i].funcs); + list_head_init(&tw->wheel[i].funcs); tw->wheel[i].expiry = now; ts_add(&now, &res_ts, &now); } diff --git a/src/irmd/api_table.c b/src/irmd/api_table.c index 97b8eb0f..4b9d9ecb 100644 --- a/src/irmd/api_table.c +++ b/src/irmd/api_table.c @@ -42,8 +42,8 @@ struct api_entry * api_entry_create(pid_t api, char * apn) if (e == NULL) return NULL; - INIT_LIST_HEAD(&e->next); - INIT_LIST_HEAD(&e->names); + list_head_init(&e->next); + list_head_init(&e->names); e->api = api; e->apn = apn; diff --git a/src/irmd/apn_table.c b/src/irmd/apn_table.c index 34983f78..7edba361 100644 --- a/src/irmd/apn_table.c +++ b/src/irmd/apn_table.c @@ -41,8 +41,8 @@ struct apn_entry * apn_entry_create(char * apn, if (e == NULL) return NULL; - INIT_LIST_HEAD(&e->next); - INIT_LIST_HEAD(&e->names); + list_head_init(&e->next); + list_head_init(&e->names); e->apn = apn; e->ap = ap; diff --git a/src/irmd/main.c b/src/irmd/main.c index b7292e74..295e3320 100644 --- a/src/irmd/main.c +++ b/src/irmd/main.c @@ -150,7 +150,7 @@ static struct ipcp_entry * ipcp_entry_create(void) e->name = NULL; e->dif_name = NULL; - INIT_LIST_HEAD(&e->next); + list_head_init(&e->next); return e; } @@ -260,7 +260,7 @@ static pid_t create_ipcp(char * name, enum ipcp_type ipcp_type) return -1; } - INIT_LIST_HEAD(&tmp->next); + list_head_init(&tmp->next); tmp->api = api->pid; tmp->name = strdup(name); @@ -743,7 +743,7 @@ static int name_reg(char * name, char ** difs, size_t len) pthread_rwlock_wrlock(&irmd->reg_lock); - if (list_empty(&irmd->ipcps)) { + if (list_is_empty(&irmd->ipcps)) { pthread_rwlock_unlock(&irmd->reg_lock); pthread_rwlock_unlock(&irmd->state_lock); return -1; @@ -1988,12 +1988,12 @@ static int irm_create(void) return -1; } - INIT_LIST_HEAD(&irmd->ipcps); - INIT_LIST_HEAD(&irmd->api_table); - INIT_LIST_HEAD(&irmd->apn_table); - INIT_LIST_HEAD(&irmd->spawned_apis); - INIT_LIST_HEAD(&irmd->registry); - INIT_LIST_HEAD(&irmd->irm_flows); + list_head_init(&irmd->ipcps); + list_head_init(&irmd->api_table); + list_head_init(&irmd->apn_table); + list_head_init(&irmd->spawned_apis); + list_head_init(&irmd->registry); + list_head_init(&irmd->irm_flows); irmd->port_ids = bmp_create(IRMD_MAX_FLOWS, 0); if (irmd->port_ids == NULL) { diff --git a/src/irmd/registry.c b/src/irmd/registry.c index 34d0a921..e1f8419e 100644 --- a/src/irmd/registry.c +++ b/src/irmd/registry.c @@ -63,10 +63,10 @@ static struct reg_entry * reg_entry_init(struct reg_entry * e, if (e == NULL || name == NULL) return NULL; - INIT_LIST_HEAD(&e->next); - INIT_LIST_HEAD(&e->difs); - INIT_LIST_HEAD(&e->reg_apns); - INIT_LIST_HEAD(&e->reg_apis); + list_head_init(&e->next); + list_head_init(&e->difs); + list_head_init(&e->reg_apns); + list_head_init(&e->reg_apis); e->name = name; @@ -228,7 +228,7 @@ void reg_entry_del_apn(struct reg_entry * e, char * apn) } } - if (e->state == REG_NAME_AUTO_ACCEPT && list_empty(&e->reg_apns)) { + if (e->state == REG_NAME_AUTO_ACCEPT && list_is_empty(&e->reg_apns)) { e->state = REG_NAME_IDLE; pthread_cond_broadcast(&e->state_cond); } @@ -237,7 +237,7 @@ void reg_entry_del_apn(struct reg_entry * e, char * apn) char * reg_entry_get_apn(struct reg_entry * e) { - if (!list_empty(&e->reg_apis) || list_empty(&e->reg_apns)) + if (!list_is_empty(&e->reg_apis) || list_is_empty(&e->reg_apns)) return NULL; return list_first_entry(&e->reg_apns, struct str_el, next)->str; @@ -311,8 +311,8 @@ void reg_entry_del_api(struct reg_entry * e, pid_t api) } } - if (list_empty(&e->reg_apis)) { - if (!list_empty(&e->reg_apns)) + if (list_is_empty(&e->reg_apis)) { + if (!list_is_empty(&e->reg_apns)) e->state = REG_NAME_AUTO_ACCEPT; else e->state = REG_NAME_IDLE; @@ -328,7 +328,7 @@ pid_t reg_entry_get_api(struct reg_entry * e) if (e == NULL) return -1; - if (list_empty(&e->reg_apis)) + if (list_is_empty(&e->reg_apis)) return -1; return list_first_entry(&e->reg_apis, struct pid_el, next)->pid; 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 <sander.vrijders@intec.ugent.be> + * Dimitri Staessense <dimitri.staessens@intec.ugent.be> * - * 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 <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 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 <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; -} +#include <stddef.h> -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; } |