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) { \
  50         .next = &(name), \
  51         .prev = &(name), \
  52 }
  53
  54 /* Add new element at the head of the list. */
  55 static inline void list_add(struct list_head *newp, struct list_head *head)
  56 {
  57         head->next->prev = newp;
  58         newp->next = head->next;
  59         newp->prev = head;
  60         head->next = newp;
  61 }
  62
  63 /* Add new element at the tail of the list. */
  64 static inline void list_add_tail(struct list_head *newp, struct 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 /* Remove element from list. */
  73 static inline void __list_del(struct list_head *prev, struct list_head *next)
  74 {
  75         next->prev = prev;
  76         prev->next = next;
  77 }
  78
  79 /* Remove element from list. */
  80 static inline void list_del(struct list_head *elem)
  81 {
  82         __list_del(elem->prev, elem->next);
  83 }
  84
  85 /* Remove element from list, initializing the element's list pointers. */
  86 static inline void list_del_init(struct list_head *elem)
  87 {
  88         list_del(elem);
  89         INIT_LIST_HEAD(elem);
  90 }
  91
  92 /* Delete from list, add to another list as head. */
  93 static inline void list_move(struct list_head *elem, struct list_head *head)
  94 {
  95         __list_del(elem->prev, elem->next);
  96         list_add(elem, head);
  97 }
  98
  99 /* Replace an old entry. */
 100 static inline void list_replace(struct list_head *old, struct list_head *newp)
 101 {
 102         newp->next = old->next;
 103         newp->prev = old->prev;
 104         newp->prev->next = newp;
 105         newp->next->prev = newp;
 106 }
 107
 108 /* Join two lists. */
 109 static inline void list_splice(struct list_head *add, struct list_head *head)
 110 {
 111         /* Do nothing if the list which gets added is empty. */
 112         if (add != add->next) {
 113                 add->next->prev = head;
 114                 add->prev->next = head->next;
 115                 head->next->prev = add->prev;
 116                 head->next = add->next;
 117         }
 118 }
 119
 120 /* Get typed element from list at a given position. */
 121 #define list_entry(ptr, type, member) \
 122         ((type *) ((char *) (ptr) - offsetof(type, member)))
 123
 124 /* Get first entry from a list. */
 125 #define list_first_entry(ptr, type, member) \
 126         list_entry((ptr)->next, type, member)
 127
 128 /* Iterate forward over the elements of the list. */
 129 #define list_for_each(pos, head) \
 130         for (pos = (head)->next; pos != (head); pos = pos->next)
 131
 132 /*
 133  * Iterate forward over the elements list. The list elements can be
 134  * removed from the list while doing this.
 135  */
 136 #define list_for_each_safe(pos, p, head) \
 137         for (pos = (head)->next, p = pos->next; \
 138                 pos != (head); \
 139                 pos = p, p = pos->next)
 140
 141 /* Iterate backward over the elements of the list. */
 142 #define list_for_each_prev(pos, head) \
 143         for (pos = (head)->prev; pos != (head); pos = pos->prev)
 144
 145 /*
 146  * Iterate backwards over the elements list. The list elements can be
 147  * removed from the list while doing this.
 148  */
 149 #define list_for_each_prev_safe(pos, p, head) \
 150         for (pos = (head)->prev, p = pos->prev; \
 151                 pos != (head); \
 152                 pos = p, p = pos->prev)
 153
 154 static inline int list_empty(struct list_head *head)
 155 {
 156         return head == head->next;
 157 }
 158
 159 static inline void list_replace_init(struct list_head *old,
 160                                      struct list_head *newp)
 161 {
 162         struct list_head *head = old->next;
 163
 164         list_del(old);
 165         list_add_tail(newp, head);
 166         INIT_LIST_HEAD(old);
 167 }
 168
 169 /*
 170  * This is exactly the same as a normal list_head, except that it can be
 171  * declared volatile (e.g., if you have a list that may be accessed from signal
 172  * handlers).
 173  */
 174 struct volatile_list_head {
 175         volatile struct volatile_list_head *next, *prev;
 176 };
 177
 178 #define VOLATILE_LIST_HEAD(name) \
 179         volatile struct volatile_list_head name = { &(name), &(name) }
 180
 181 static inline void __volatile_list_del(volatile struct volatile_list_head *prev,
 182                                        volatile struct volatile_list_head *next)
 183 {
 184         next->prev = prev;
 185         prev->next = next;
 186 }
 187
 188 static inline void volatile_list_del(volatile struct volatile_list_head *elem)
 189 {
 190         __volatile_list_del(elem->prev, elem->next);
 191 }
 192
 193 static inline int volatile_list_empty(volatile struct volatile_list_head *head)
 194 {
 195         return head == head->next;
 196 }
 197
 198 static inline void volatile_list_add(volatile struct volatile_list_head *newp,
 199                                      volatile struct volatile_list_head *head)
 200 {
 201         head->next->prev = newp;
 202         newp->next = head->next;
 203         newp->prev = head;
 204         head->next = newp;
 205 }
 206
 207 #endif /* LIST_H */