list.h

   1 /*-
   2  * Copyright (c) 2011 Felix Fietkau <nbd@openwrt.org>
   3  * Copyright (c) 2010 Isilon Systems, Inc.
   4  * Copyright (c) 2010 iX Systems, Inc.
   5  * Copyright (c) 2010 Panasas, Inc.
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice unmodified, this list of conditions, and the following
  13  *    disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in the
  16  *    documentation and/or other materials provided with the distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  19  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  20  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  21  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  22  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  23  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  27  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29 #ifndef _LINUX_LIST_H_
  30 #define _LINUX_LIST_H_
  31
  32 #include <stddef.h>
  33 #include <stdbool.h>
  34
  35 #define prefetch(x)
  36
  37 #ifndef container_of
  38 #define container_of(ptr, type, member)                                 \
  39         ({                                                              \
  40                 const typeof(((type *) NULL)->member) *__mptr = (ptr);  \
  41                 (type *) ((char *) __mptr - offsetof(type, member));    \
  42         })
  43 #endif
  44
  45 struct list_head {
  46         struct list_head *next;
  47         struct list_head *prev;
  48 };
  49
  50 #define LIST_HEAD_INIT(name) { &(name), &(name) }
  51 #undef LIST_HEAD
  52 #define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)
  53
  54 static inline void
  55 INIT_LIST_HEAD(struct list_head *list)
  56 {
  57         list->next = list->prev = list;
  58 }
  59
  60 static inline bool
  61 list_empty(const struct list_head *head)
  62 {
  63         return (head->next == head);
  64 }
  65
  66 static inline bool
  67 list_is_first(const struct list_head *list,
  68               const struct list_head *head)
  69 {
  70         return list->prev == head;
  71 }
  72
  73 static inline bool
  74 list_is_last(const struct list_head *list,
  75              const struct list_head *head)
  76 {
  77         return list->next == head;
  78 }
  79
  80 static inline void
  81 _list_del(struct list_head *entry)
  82 {
  83         entry->next->prev = entry->prev;
  84         entry->prev->next = entry->next;
  85 }
  86
  87 static inline void
  88 list_del(struct list_head *entry)
  89 {
  90         _list_del(entry);
  91         entry->next = entry->prev = NULL;
  92 }
  93
  94 static inline void
  95 _list_add(struct list_head *_new, struct list_head *prev,
  96     struct list_head *next)
  97 {
  98
  99         next->prev = _new;
 100         _new->next = next;
 101         _new->prev = prev;
 102         prev->next = _new;
 103 }
 104
 105 static inline void
 106 list_del_init(struct list_head *entry)
 107 {
 108         _list_del(entry);
 109         INIT_LIST_HEAD(entry);
 110 }
 111
 112 #define list_entry(ptr, type, field)    container_of(ptr, type, field)
 113 #define list_first_entry(ptr, type, field)      list_entry((ptr)->next, type, field)
 114 #define list_last_entry(ptr, type, field)       list_entry((ptr)->prev, type, field)
 115
 116 #define list_for_each(p, head)                                          \
 117         for (p = (head)->next; p != (head); p = p->next)
 118
 119 #define list_for_each_safe(p, n, head)                                  \
 120         for (p = (head)->next, n = p->next; p != (head); p = n, n = p->next)
 121
 122 #define list_for_each_entry(p, h, field)                                \
 123         for (p = list_first_entry(h, typeof(*p), field); &p->field != (h); \
 124             p = list_entry(p->field.next, typeof(*p), field))
 125
 126 #define list_for_each_entry_safe(p, n, h, field)                        \
 127         for (p = list_first_entry(h, typeof(*p), field),                \
 128             n = list_entry(p->field.next, typeof(*p), field); &p->field != (h);\
 129             p = n, n = list_entry(n->field.next, typeof(*n), field))
 130
 131 #define list_for_each_entry_reverse(p, h, field)                        \
 132         for (p = list_last_entry(h, typeof(*p), field); &p->field != (h); \
 133             p = list_entry(p->field.prev, typeof(*p), field))
 134
 135 #define list_for_each_prev(p, h) for (p = (h)->prev; p != (h); p = p->prev)
 136 #define list_for_each_prev_safe(p, n, h) for (p = (h)->prev, n = p->prev; p != (h); p = n, n = p->prev)
 137
 138 static inline void
 139 list_add(struct list_head *_new, struct list_head *head)
 140 {
 141         _list_add(_new, head, head->next);
 142 }
 143
 144 static inline void
 145 list_add_tail(struct list_head *_new, struct list_head *head)
 146 {
 147         _list_add(_new, head->prev, head);
 148 }
 149
 150 static inline void
 151 list_move(struct list_head *list, struct list_head *head)
 152 {
 153         _list_del(list);
 154         list_add(list, head);
 155 }
 156
 157 static inline void
 158 list_move_tail(struct list_head *entry, struct list_head *head)
 159 {
 160         _list_del(entry);
 161         list_add_tail(entry, head);
 162 }
 163
 164 static inline void
 165 _list_splice(const struct list_head *list, struct list_head *prev,
 166     struct list_head *next)
 167 {
 168         struct list_head *first;
 169         struct list_head *last;
 170
 171         if (list_empty(list))
 172                 return;
 173
 174         first = list->next;
 175         last = list->prev;
 176         first->prev = prev;
 177         prev->next = first;
 178         last->next = next;
 179         next->prev = last;
 180 }
 181
 182 static inline void
 183 list_splice(const struct list_head *list, struct list_head *head)
 184 {
 185         _list_splice(list, head, head->next);
 186 }
 187
 188 static inline void
 189 list_splice_tail(struct list_head *list, struct list_head *head)
 190 {
 191         _list_splice(list, head->prev, head);
 192 }
 193
 194 static inline void
 195 list_splice_init(struct list_head *list, struct list_head *head)
 196 {
 197         _list_splice(list, head, head->next);
 198         INIT_LIST_HEAD(list);
 199 }
 200
 201 static inline void
 202 list_splice_tail_init(struct list_head *list, struct list_head *head)
 203 {
 204         _list_splice(list, head->prev, head);
 205         INIT_LIST_HEAD(list);
 206 }
 207
 208 #endif /* _LINUX_LIST_H_ */