urcu/list.h

   1 /*
   2  * Copyright (C) 2002 Free Software Foundation, Inc.
   3  * (originally part of the GNU C Library)
   4  * Contributed by Ulrich Drepper <drepper@redhat.com>, 2002.
   5  *
   6  * Copyright (C) 2009 Pierre-Marc Fournier
   7  * Conversion to RCU list.
   8  * Copyright (C) 2010 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   9  *
  10  * This library is free software; you can redistribute it and/or
  11  * modify it under the terms of the GNU Lesser General Public
  12  * License as published by the Free Software Foundation; either
  13  * version 2.1 of the License, or (at your option) any later version.
  14  *
  15  * This library is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18  * Lesser General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU Lesser General Public
  21  * License along with this library; if not, write to the Free Software
  22  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  23  */
  24
  25 #ifndef _CDS_LIST_H
  26 #define _CDS_LIST_H     1
  27
  28 /* The definitions of this file are adopted from those which can be
  29    found in the Linux kernel headers to enable people familiar with
  30    the latter find their way in these sources as well.  */
  31
  32
  33 /* Basic type for the double-link list.  */
  34 struct cds_list_head
  35 {
  36   struct cds_list_head *next;
  37   struct cds_list_head *prev;
  38 };
  39
  40
  41 /* Define a variable with the head and tail of the list.  */
  42 #define CDS_LIST_HEAD(name) \
  43   struct cds_list_head name = { &(name), &(name) }
  44
  45 /* Initialize a new list head.  */
  46 #define CDS_INIT_LIST_HEAD(ptr) \
  47   (ptr)->next = (ptr)->prev = (ptr)
  48
  49 #define CDS_LIST_HEAD_INIT(name) { .prev = &(name), .next = &(name) }
  50
  51 /* Add new element at the head of the list.  */
  52 static inline void
  53 cds_list_add (struct cds_list_head *newp, struct cds_list_head *head)
  54 {
  55   head->next->prev = newp;
  56   newp->next = head->next;
  57   newp->prev = head;
  58   head->next = newp;
  59 }
  60
  61
  62 /* Add new element at the tail of the list.  */
  63 static inline void
  64 cds_list_add_tail (struct cds_list_head *newp, struct cds_list_head *head)
  65 {
  66   head->prev->next = newp;
  67   newp->next = head;
  68   newp->prev = head->prev;
  69   head->prev = newp;
  70 }
  71
  72
  73 /* Remove element from list.  */
  74 static inline void
  75 __cds_list_del (struct cds_list_head *prev, struct cds_list_head *next)
  76 {
  77   next->prev = prev;
  78   prev->next = next;
  79 }
  80
  81 /* Remove element from list.  */
  82 static inline void
  83 cds_list_del (struct cds_list_head *elem)
  84 {
  85   __cds_list_del (elem->prev, elem->next);
  86 }
  87
  88 /* Remove element from list, initializing the element's list pointers. */
  89 static inline void
  90 cds_list_del_init (struct cds_list_head *elem)
  91 {
  92         cds_list_del(elem);
  93         CDS_INIT_LIST_HEAD(elem);
  94 }
  95
  96 /* delete from list, add to another list as head */
  97 static inline void
  98 cds_list_move (struct cds_list_head *elem, struct cds_list_head *head)
  99 {
 100   __cds_list_del (elem->prev, elem->next);
 101   cds_list_add (elem, head);
 102 }
 103
 104 /* replace an old entry.
 105  */
 106 static inline void
 107 cds_list_replace(struct cds_list_head *old, struct cds_list_head *_new)
 108 {
 109         _new->next = old->next;
 110         _new->prev = old->prev;
 111         _new->prev->next = _new;
 112         _new->next->prev = _new;
 113 }
 114
 115 /* Join two lists.  */
 116 static inline void
 117 cds_list_splice (struct cds_list_head *add, struct cds_list_head *head)
 118 {
 119   /* Do nothing if the list which gets added is empty.  */
 120   if (add != add->next)
 121     {
 122       add->next->prev = head;
 123       add->prev->next = head->next;
 124       head->next->prev = add->prev;
 125       head->next = add->next;
 126     }
 127 }
 128
 129 /* Get typed element from list at a given position.  */
 130 #define cds_list_entry(ptr, type, member) \
 131   ((type *) ((char *) (ptr) - (unsigned long) (&((type *) 0)->member)))
 132
 133
 134 /* Get first entry from a list. */
 135 #define cds_list_first_entry(ptr, type, member) \
 136         cds_list_entry((ptr)->next, type, member)
 137
 138
 139 /* Iterate forward over the elements of the list.  */
 140 #define cds_list_for_each(pos, head) \
 141   for (pos = (head)->next; pos != (head); pos = pos->next)
 142
 143 /* Iterate forward over the elements list. The list elements can be
 144    removed from the list while doing this.  */
 145 #define cds_list_for_each_safe(pos, p, head) \
 146   for (pos = (head)->next, p = pos->next; \
 147        pos != (head); \
 148        pos = p, p = pos->next)
 149
 150 /* Iterate backward over the elements of the list.  */
 151 #define cds_list_for_each_prev(pos, head) \
 152   for (pos = (head)->prev; pos != (head); pos = pos->prev)
 153
 154 /* Iterate backwards over the elements list.  The list elements can be
 155    removed from the list while doing this.  */
 156 #define cds_list_for_each_prev_safe(pos, p, head) \
 157   for (pos = (head)->prev, p = pos->prev; \
 158        pos != (head); \
 159        pos = p, p = pos->prev)
 160
 161 #define cds_list_for_each_entry(pos, head, member)                              \
 162         for (pos = cds_list_entry((head)->next, __typeof__(*pos), member); \
 163              &pos->member != (head);                                    \
 164              pos = cds_list_entry(pos->member.next, __typeof__(*pos), member))
 165
 166 #define cds_list_for_each_entry_reverse(pos, head, member)                      \
 167         for (pos = cds_list_entry((head)->prev, __typeof__(*pos), member); \
 168              &pos->member != (head);                                    \
 169              pos = cds_list_entry(pos->member.prev, __typeof__(*pos), member))
 170
 171 #define cds_list_for_each_entry_safe(pos, p, head, member)                      \
 172         for (pos = cds_list_entry((head)->next, __typeof__(*pos), member), \
 173                      p = cds_list_entry(pos->member.next, __typeof__(*pos), member); \
 174              &pos->member != (head);                                    \
 175              pos = p, p = cds_list_entry(pos->member.next, __typeof__(*pos), member))
 176
 177 static inline int cds_list_empty(struct cds_list_head *head)
 178 {
 179         return head == head->next;
 180 }
 181
 182 static inline void cds_list_replace_init(struct cds_list_head *old,
 183                                      struct cds_list_head *_new)
 184 {
 185         struct cds_list_head *head = old->next;
 186         cds_list_del(old);
 187         cds_list_add_tail(_new, head);
 188         CDS_INIT_LIST_HEAD(old);
 189 }
 190
 191 #endif  /* _CDS_LIST_H */