list.h

   1 /*
   2  * Copyright (C) 2002 Free Software Foundation, Inc.
   3  * (originally part of the GNU C Library and Userspace RCU)
   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, see
  22  * <http://www.gnu.org/licenses/>.
  23  */
  24
  25 #ifndef LIST_H
  26 #define LIST_H  1
  27
  28 /*
  29  * The definitions of this file are adopted from those which can be
  30  * found in the Linux kernel headers to enable people familiar with the
  31  * latter find their way in these sources as well.
  32  */
  33
  34 /* Basic type for the double-link list. */
  35 struct list_head {
  36         struct list_head *next, *prev;
  37 };
  38
  39 /* avoid conflicts with BSD-only sys/queue.h */
  40 #undef LIST_HEAD
  41 /* Define a variable with the head and tail of the list. */
  42 #define LIST_HEAD(name) \
  43         struct list_head name = { &(name), &(name) }
  44
  45 /* Initialize a new list head. */
  46 #define INIT_LIST_HEAD(ptr) \
  47         (ptr)->next = (ptr)->prev = (ptr)
  48
  49 #define LIST_HEAD_INIT(name) { &(name), &(name) }
  50
  51 /* Add new element at the head of the list. */
  52 static inline void list_add(struct list_head *newp, struct 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 /* Add new element at the tail of the list. */
  61 static inline void list_add_tail(struct list_head *newp, struct list_head *head)
  62 {
  63         head->prev->next = newp;
  64         newp->next = head;
  65         newp->prev = head->prev;
  66         head->prev = newp;
  67 }
  68
  69 /* Remove element from list. */
  70 static inline void __list_del(struct list_head *prev, struct list_head *next)
  71 {
  72         next->prev = prev;
  73         prev->next = next;
  74 }
  75
  76 /* Remove element from list. */
  77 static inline void list_del(struct list_head *elem)
  78 {
  79         __list_del(elem->prev, elem->next);
  80 }
  81
  82 /* Remove element from list, initializing the element's list pointers. */
  83 static inline void list_del_init(struct list_head *elem)
  84 {
  85         list_del(elem);
  86         INIT_LIST_HEAD(elem);
  87 }
  88
  89 /* Delete from list, add to another list as head. */
  90 static inline void list_move(struct list_head *elem, struct list_head *head)
  91 {
  92         __list_del(elem->prev, elem->next);
  93         list_add(elem, head);
  94 }
  95
  96 /* Replace an old entry. */
  97 static inline void list_replace(struct list_head *old, struct list_head *newp)
  98 {
  99         newp->next = old->next;
 100         newp->prev = old->prev;
 101         newp->prev->next = newp;
 102         newp->next->prev = newp;
 103 }
 104
 105 /* Join two lists. */
 106 static inline void list_splice(struct list_head *add, struct list_head *head)
 107 {
 108         /* Do nothing if the list which gets added is empty. */
 109         if (add != add->next) {
 110                 add->next->prev = head;
 111                 add->prev->next = head->next;
 112                 head->next->prev = add->prev;
 113                 head->next = add->next;
 114         }
 115 }
 116
 117 /* Get typed element from list at a given position. */
 118 #define list_entry(ptr, type, member) \
 119         ((type *) ((char *) (ptr) - offsetof(type, member)))
 120
 121 /* Get first entry from a list. */
 122 #define list_first_entry(ptr, type, member) \
 123         list_entry((ptr)->next, type, member)
 124
 125 /* Iterate forward over the elements of the list. */
 126 #define list_for_each(pos, head) \
 127         for (pos = (head)->next; pos != (head); pos = pos->next)
 128
 129 /*
 130  * Iterate forward over the elements list. The list elements can be
 131  * removed from the list while doing this.
 132  */
 133 #define list_for_each_safe(pos, p, head) \
 134         for (pos = (head)->next, p = pos->next; \
 135                 pos != (head); \
 136                 pos = p, p = pos->next)
 137
 138 /* Iterate backward over the elements of the list. */
 139 #define list_for_each_prev(pos, head) \
 140         for (pos = (head)->prev; pos != (head); pos = pos->prev)
 141
 142 /*
 143  * Iterate backwards over the elements list. The list elements can be
 144  * removed from the list while doing this.
 145  */
 146 #define list_for_each_prev_safe(pos, p, head) \
 147         for (pos = (head)->prev, p = pos->prev; \
 148                 pos != (head); \
 149                 pos = p, p = pos->prev)
 150
 151 static inline int list_empty(struct list_head *head)
 152 {
 153         return head == head->next;
 154 }
 155
 156 static inline void list_replace_init(struct list_head *old,
 157                                      struct list_head *newp)
 158 {
 159         struct list_head *head = old->next;
 160
 161         list_del(old);
 162         list_add_tail(newp, head);
 163         INIT_LIST_HEAD(old);
 164 }
 165
 166 /*
 167  * This is exactly the same as a normal list_head, except that it can be
 168  * declared volatile (e.g., if you have a list that may be accessed from signal
 169  * handlers).
 170  */
 171 struct volatile_list_head {
 172         volatile struct volatile_list_head *next, *prev;
 173 };
 174
 175 #define VOLATILE_LIST_HEAD(name) \
 176         volatile struct volatile_list_head name = { &(name), &(name) }
 177
 178 static inline void __volatile_list_del(volatile struct volatile_list_head *prev,
 179                                        volatile struct volatile_list_head *next)
 180 {
 181         next->prev = prev;
 182         prev->next = next;
 183 }
 184
 185 static inline void volatile_list_del(volatile struct volatile_list_head *elem)
 186 {
 187         __volatile_list_del(elem->prev, elem->next);
 188 }
 189
 190 static inline int volatile_list_empty(volatile struct volatile_list_head *head)
 191 {
 192         return head == head->next;
 193 }
 194
 195 static inline void volatile_list_add(volatile struct volatile_list_head *newp,
 196                                      volatile struct volatile_list_head *head)
 197 {
 198         head->next->prev = newp;
 199         newp->next = head->next;
 200         newp->prev = head;
 201         head->next = newp;
 202 }
 203
 204 #endif /* LIST_H */