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 /* Define a variable with the head and tail of the list.  */
  41 #define CDS_LIST_HEAD(name) \
  42   struct cds_list_head name = { &(name), &(name) }
  43
  44 /* Initialize a new list head.  */
  45 #define CDS_INIT_LIST_HEAD(ptr) \
  46   (ptr)->next = (ptr)->prev = (ptr)
  47
  48 #define CDS_LIST_HEAD_INIT(name) { .prev = &(name), .next = &(name) }
  49
  50 /* Add new element at the head of the list.  */
  51 static inline void
  52 cds_list_add (struct cds_list_head *newp, struct cds_list_head *head)
  53 {
  54   head->next->prev = newp;
  55   newp->next = head->next;
  56   newp->prev = head;
  57   head->next = newp;
  58 }
  59
  60
  61 /* Add new element at the tail of the list.  */
  62 static inline void
  63 cds_list_add_tail (struct cds_list_head *newp, struct cds_list_head *head)
  64 {
  65   head->prev->next = newp;
  66   newp->next = head;
  67   newp->prev = head->prev;
  68   head->prev = newp;
  69 }
  70
  71
  72 /* Remove element from list.  */
  73 static inline void
  74 __cds_list_del (struct cds_list_head *prev, struct cds_list_head *next)
  75 {
  76   next->prev = prev;
  77   prev->next = next;
  78 }
  79
  80 /* Remove element from list.  */
  81 static inline void
  82 cds_list_del (struct cds_list_head *elem)
  83 {
  84   __cds_list_del (elem->prev, elem->next);
  85 }
  86
  87 /* Remove element from list, initializing the element's list pointers. */
  88 static inline void
  89 cds_list_del_init (struct cds_list_head *elem)
  90 {
  91         cds_list_del(elem);
  92         CDS_INIT_LIST_HEAD(elem);
  93 }
  94
  95 /* delete from list, add to another list as head */
  96 static inline void
  97 cds_list_move (struct cds_list_head *elem, struct cds_list_head *head)
  98 {
  99   __cds_list_del (elem->prev, elem->next);
 100   cds_list_add (elem, head);
 101 }
 102
 103 /* replace an old entry.
 104  */
 105 static inline void
 106 cds_list_replace(struct cds_list_head *old, struct cds_list_head *_new)
 107 {
 108         _new->next = old->next;
 109         _new->prev = old->prev;
 110         _new->prev->next = _new;
 111         _new->next->prev = _new;
 112 }
 113
 114 /* Join two lists.  */
 115 static inline void
 116 cds_list_splice (struct cds_list_head *add, struct cds_list_head *head)
 117 {
 118   /* Do nothing if the list which gets added is empty.  */
 119   if (add != add->next)
 120     {
 121       add->next->prev = head;
 122       add->prev->next = head->next;
 123       head->next->prev = add->prev;
 124       head->next = add->next;
 125     }
 126 }
 127
 128 /* Returns 1 if list is empty, 0 otherwise */
 129 static inline
 130 int cds_list_empty(struct cds_list_head *head)
 131 {
 132         return head->next == head->prev;
 133 }
 134
 135 /* Get typed element from list at a given position.  */
 136 #define cds_list_entry(ptr, type, member) \
 137   ((type *) ((char *) (ptr) - (unsigned long) (&((type *) 0)->member)))
 138
 139
 140 /* Get first entry from a list. */
 141 #define cds_list_first_entry(head, type, member) \
 142         cds_list_entry((head)->next, type, member)
 143
 144
 145 /* Iterate forward over the elements of the list.  */
 146 #define cds_list_for_each(pos, head) \
 147   for (pos = (head)->next; pos != (head); pos = pos->next)
 148
 149
 150 /* Iterate forward 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
 155 /* Iterate backwards over the elements list.  The list elements can be
 156    removed from the list while doing this.  */
 157 #define cds_list_for_each_prev_safe(pos, p, head) \
 158   for (pos = (head)->prev, p = pos->prev; \
 159        pos != (head); \
 160        pos = p, p = pos->prev)
 161
 162 #define cds_list_for_each_entry(pos, head, member)                              \
 163         for (pos = cds_list_entry((head)->next, typeof(*pos), member);  \
 164              &pos->member != (head);                                    \
 165              pos = cds_list_entry(pos->member.next, typeof(*pos), member))
 166
 167 #define cds_list_for_each_entry_reverse(pos, head, member)                      \
 168         for (pos = cds_list_entry((head)->prev, typeof(*pos), member);  \
 169              &pos->member != (head);                                    \
 170              pos = cds_list_entry(pos->member.prev, typeof(*pos), member))
 171
 172 #define cds_list_for_each_entry_safe(pos, p, head, member)                      \
 173         for (pos = cds_list_entry((head)->next, typeof(*pos), member),  \
 174                      p = cds_list_entry(pos->member.next,typeof(*pos), member); \
 175              &pos->member != (head);                                    \
 176              pos = p, p = cds_list_entry(pos->member.next, typeof(*pos), member))
 177
 178 static inline int cds_list_empty(struct cds_list_head *head)
 179 {
 180         return head == head->next;
 181 }
 182
 183 static inline void cds_list_replace_init(struct cds_list_head *old,
 184                                      struct cds_list_head *_new)
 185 {
 186         struct cds_list_head *head = old->next;
 187         cds_list_del(old);
 188         cds_list_add_tail(_new, head);
 189         CDS_INIT_LIST_HEAD(old);
 190 }
 191
 192 #endif  /* _CDS_LIST_H */