From 5db941e8f87f9728883c2dd0446698d13d5b9fec Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Thu, 18 Feb 2010 23:45:40 -0500 Subject: [PATCH] RCU list: add rcuhlist.h, add list_replace_rcu Signed-off-by: Mathieu Desnoyers --- Makefile.am | 2 +- urcu/hlist.h | 2 ++ urcu/list.h | 11 +++++++++ urcu/rcuhlist.h | 64 +++++++++++++++++++++++++++++++++++++++++++++++++ urcu/rculist.h | 22 +++++++++++++++-- 5 files changed, 98 insertions(+), 3 deletions(-) create mode 100644 urcu/rcuhlist.h diff --git a/Makefile.am b/Makefile.am index 4f915e1..33c7b53 100644 --- a/Makefile.am +++ b/Makefile.am @@ -6,7 +6,7 @@ SUBDIRS = . tests include_HEADERS = urcu.h $(top_srcdir)/urcu-*.h nobase_dist_include_HEADERS = urcu/compiler.h urcu/hlist.h urcu/list.h \ - urcu/rculist.h urcu/system.h urcu/urcu-futex.h + urcu/rculist.h urcu/rcuhlist.h urcu/system.h urcu/urcu-futex.h nobase_nodist_include_HEADERS = urcu/arch.h urcu/uatomic_arch.h urcu/config.h EXTRA_DIST = $(top_srcdir)/urcu/arch_*.h $(top_srcdir)/urcu/uatomic_arch_*.h \ diff --git a/urcu/hlist.h b/urcu/hlist.h index 1bec11a..9f7776f 100644 --- a/urcu/hlist.h +++ b/urcu/hlist.h @@ -9,6 +9,8 @@ * * Author: Jan Blunck * + * Copyright (C) 2010 Mathieu Desnoyers + * * This program 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. diff --git a/urcu/list.h b/urcu/list.h index 6384728..d267512 100644 --- a/urcu/list.h +++ b/urcu/list.h @@ -88,6 +88,17 @@ list_move (list_t *elem, list_t *head) list_add (elem, head); } +/* replace an old entry. + */ +static inline void +list_replace(list_t *old, list_t *_new) +{ + _new->next = old->next; + _new->prev = old->prev; + _new->prev->next = _new; + _new->next->prev = _new; +} + /* Join two lists. */ static inline void list_splice (list_t *add, list_t *head) diff --git a/urcu/rcuhlist.h b/urcu/rcuhlist.h new file mode 100644 index 0000000..be74145 --- /dev/null +++ b/urcu/rcuhlist.h @@ -0,0 +1,64 @@ +/* Copyright (C) 2002 Free Software Foundation, Inc. + This file is part of the GNU C Library. + Contributed by Ulrich Drepper , 2002. + + Copyright (C) 2009 Pierre-Marc Fournier + Conversion to RCU list. + Copyright (C) 2010 Mathieu Desnoyers + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, write to the Free + Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA + 02111-1307 USA. */ + +#ifndef _URCU_RCUHLIST_H +#define _URCU_RCUHLIST_H + +#include +#include +#include + +/* Add new element at the head of the list. + */ +static inline void hlist_add_head(struct hlist_node *newp, + struct hlist_head *head) +{ + newp->next = head->next; + newp->prev = (struct hlist_node *)head; + smp_wmb(); + if (head->next) + head->next->prev = newp; + head->next = newp; +} + +/* Remove element from list. */ +static inline void hlist_del_rcu(struct hlist_node *elem) +{ + if (elem->next) + elem->next->prev = elem->prev; + elem->prev->next = elem->next; +} + + +/* Iterate through elements of the list. + * This must be done while rcu_read_lock() is held. + */ + +#define hlist_for_each_entry_rcu(entry, pos, head, member) \ + for (pos = rcu_dereference((head)->next), \ + entry = hlist_entry(pos, typeof(*entry), member); \ + pos != NULL; \ + pos = rcu_dereference(pos->next), \ + entry = hlist_entry(pos, typeof(*entry), member)) + +#endif /* _URCU_RCUHLIST_H */ diff --git a/urcu/rculist.h b/urcu/rculist.h index e0ff939..b0c4f1a 100644 --- a/urcu/rculist.h +++ b/urcu/rculist.h @@ -4,6 +4,7 @@ Copyright (C) 2009 Pierre-Marc Fournier Conversion to RCU list. + Copyright (C) 2010 Mathieu Desnoyers The GNU C Library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public @@ -38,6 +39,15 @@ static inline void list_add_rcu(list_t *newp, list_t *head) head->next = newp; } +/* replace an old entry atomically. + */ +static inline void list_replace_rcu(list_t *old, list_t *_new) +{ + _new->next = old->next; + _new->prev = old->prev; + rcu_assign_pointer(_new->prev->next, _new); + _new->next->prev = _new; +} /* Remove element from list. */ static inline void list_del_rcu(list_t *elem) @@ -46,11 +56,19 @@ static inline void list_del_rcu(list_t *elem) elem->prev->next = elem->next; } +/* + * Iteration through all elements of the list must be done while rcu_read_lock() + * is held. + */ + +/* Iterate forward over the elements of the list. */ +#define list_for_each_rcu(pos, head) \ + for (pos = rcu_dereference((head)->next); pos != (head); \ + pos = rcu_dereference(pos->next)) + /* Iterate through elements of the list. - * This must be done while rcu_read_lock() is held. */ - #define list_for_each_entry_rcu(pos, head, member) \ for (pos = list_entry(rcu_dereference((head)->next), typeof(*pos), member); \ &pos->member != (head); \ -- 2.34.1