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 /* Define a variable with the head and tail of the list. */
  40 #define LIST_HEAD(name) \
  41         struct list_head name = { &(name), &(name) }
  42
  43 /* Initialize a new list head. */
  44 #define INIT_LIST_HEAD(ptr) \
  45         (ptr)->next = (ptr)->prev = (ptr)
  46
  47 #define LIST_HEAD_INIT(name) { &(name), &(name) }
  48
  49 /* Add new element at the head of the list. */
  50 static inline void list_add(struct list_head *newp, struct list_head *head)
  51 {
  52         head->next->prev = newp;
  53         newp->next = head->next;
  54         newp->prev = head;
  55         head->next = newp;
  56 }
  57
  58 /* Add new element at the tail of the list. */
  59 static inline void list_add_tail(struct list_head *newp, struct list_head *head)
  60 {
  61         head->prev->next = newp;
  62         newp->next = head;
  63         newp->prev = head->prev;
  64         head->prev = newp;
  65 }
  66
  67 /* Remove element from list. */
  68 static inline void __list_del(struct list_head *prev, struct list_head *next)
  69 {
  70         next->prev = prev;
  71         prev->next = next;
  72 }
  73
  74 /* Remove element from list. */
  75 static inline void list_del(struct list_head *elem)
  76 {
  77         __list_del(elem->prev, elem->next);
  78 }
  79
  80 /* Remove element from list, initializing the element's list pointers. */
  81 static inline void list_del_init(struct list_head *elem)
  82 {
  83         list_del(elem);
  84         INIT_LIST_HEAD(elem);
  85 }
  86
  87 /* Delete from list, add to another list as head. */
  88 static inline void list_move(struct list_head *elem, struct list_head *head)
  89 {
  90         __list_del(elem->prev, elem->next);
  91         list_add(elem, head);
  92 }
  93
  94 /* Replace an old entry. */
  95 static inline void list_replace(struct list_head *old, struct list_head *newp)
  96 {
  97         newp->next = old->next;
  98         newp->prev = old->prev;
  99         newp->prev->next = newp;
 100         newp->next->prev = newp;
 101 }
 102
 103 /* Join two lists. */
 104 static inline void list_splice(struct list_head *add, struct list_head *head)
 105 {
 106         /* Do nothing if the list which gets added is empty. */
 107         if (add != add->next) {
 108                 add->next->prev = head;
 109                 add->prev->next = head->next;
 110                 head->next->prev = add->prev;
 111                 head->next = add->next;
 112         }
 113 }
 114
 115 /* Get typed element from list at a given position. */
 116 #define list_entry(ptr, type, member) \
 117         ((type *) ((char *) (ptr) - offsetof(type, member)))
 118
 119 /* Get first entry from a list. */
 120 #define list_first_entry(ptr, type, member) \
 121         list_entry((ptr)->next, type, member)
 122
 123 /* Iterate forward over the elements of the list. */
 124 #define list_for_each(pos, head) \
 125         for (pos = (head)->next; pos != (head); pos = pos->next)
 126
 127 /*
 128  * Iterate forward over the elements list. The list elements can be
 129  * removed from the list while doing this.
 130  */
 131 #define list_for_each_safe(pos, p, head) \
 132         for (pos = (head)->next, p = pos->next; \
 133                 pos != (head); \
 134                 pos = p, p = pos->next)
 135
 136 /* Iterate backward over the elements of the list. */
 137 #define list_for_each_prev(pos, head) \
 138         for (pos = (head)->prev; pos != (head); pos = pos->prev)
 139
 140 /*
 141  * Iterate backwards over the elements list. The list elements can be
 142  * removed from the list while doing this.
 143  */
 144 #define list_for_each_prev_safe(pos, p, head) \
 145         for (pos = (head)->prev, p = pos->prev; \
 146                 pos != (head); \
 147                 pos = p, p = pos->prev)
 148
 149 static inline int list_empty(struct list_head *head)
 150 {
 151         return head == head->next;
 152 }
 153
 154 static inline void list_replace_init(struct list_head *old,
 155                                      struct list_head *newp)
 156 {
 157         struct list_head *head = old->next;
 158
 159         list_del(old);
 160         list_add_tail(newp, head);
 161         INIT_LIST_HEAD(old);
 162 }
 163
 164 #endif /* LIST_H */