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     (type *)( (char *)ptr - offsetof(type,member) ))
  40 #endif
  41
  42 struct list_head {
  43         struct list_head *next;
  44         struct list_head *prev;
  45 };
  46
  47 #define LIST_HEAD_INIT(name) { &(name), &(name) }
  48 #define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)
  49
  50 static inline void
  51 INIT_LIST_HEAD(struct list_head *list)
  52 {
  53         list->next = list->prev = list;
  54 }
  55
  56 static inline bool
  57 list_empty(const struct list_head *head)
  58 {
  59         return (head->next == head);
  60 }
  61
  62 static inline bool
  63 list_is_first(const struct list_head *list,
  64               const struct list_head *head)
  65 {
  66         return list->prev == head;
  67 }
  68
  69 static inline bool
  70 list_is_last(const struct list_head *list,
  71              const struct list_head *head)
  72 {
  73         return list->next == head;
  74 }
  75
  76 static inline void
  77 _list_del(struct list_head *entry)
  78 {
  79         entry->next->prev = entry->prev;
  80         entry->prev->next = entry->next;
  81 }
  82
  83 static inline void
  84 list_del(struct list_head *entry)
  85 {
  86         _list_del(entry);
  87         entry->next = entry->prev = NULL;
  88 }
  89
  90 static inline void
  91 _list_add(struct list_head *_new, struct list_head *prev,
  92     struct list_head *next)
  93 {
  94
  95         next->prev = _new;
  96         _new->next = next;
  97         _new->prev = prev;
  98         prev->next = _new;
  99 }
 100
 101 static inline void
 102 list_del_init(struct list_head *entry)
 103 {
 104         _list_del(entry);
 105         INIT_LIST_HEAD(entry);
 106 }
 107
 108 #define list_entry(ptr, type, field)    container_of(ptr, type, field)
 109 #define list_first_entry(ptr, type, field)      list_entry((ptr)->next, type, field)
 110 #define list_last_entry(ptr, type, field)       list_entry((ptr)->prev, type, field)
 111
 112 #define list_for_each(p, head)                                          \
 113         for (p = (head)->next; p != (head); p = p->next)
 114
 115 #define list_for_each_safe(p, n, head)                                  \
 116         for (p = (head)->next, n = p->next; p != (head); p = n, n = p->next)
 117
 118 #define list_for_each_entry(p, h, field)                                \
 119         for (p = list_first_entry(h, typeof(*p), field); &p->field != (h); \
 120             p = list_entry(p->field.next, typeof(*p), field))
 121
 122 #define list_for_each_entry_safe(p, n, h, field)                        \
 123         for (p = list_first_entry(h, typeof(*p), field),                \
 124             n = list_entry(p->field.next, typeof(*p), field); &p->field != (h);\
 125             p = n, n = list_entry(n->field.next, typeof(*n), field))
 126
 127 #define list_for_each_entry_reverse(p, h, field)                        \
 128         for (p = list_last_entry(h, typeof(*p), field); &p->field != (h); \
 129             p = list_entry(p->field.prev, typeof(*p), field))
 130
 131 #define list_for_each_prev(p, h) for (p = (h)->prev; p != (h); p = p->prev)
 132 #define list_for_each_prev_safe(p, n, h) for (p = (h)->prev, n = p->prev; p != (h); p = n, n = p->prev)
 133
 134 static inline void
 135 list_add(struct list_head *_new, struct list_head *head)
 136 {
 137         _list_add(_new, head, head->next);
 138 }
 139
 140 static inline void
 141 list_add_tail(struct list_head *_new, struct list_head *head)
 142 {
 143         _list_add(_new, head->prev, head);
 144 }
 145
 146 static inline void
 147 list_move(struct list_head *list, struct list_head *head)
 148 {
 149         _list_del(list);
 150         list_add(list, head);
 151 }
 152
 153 static inline void
 154 list_move_tail(struct list_head *entry, struct list_head *head)
 155 {
 156         _list_del(entry);
 157         list_add_tail(entry, head);
 158 }
 159
 160 static inline void
 161 _list_splice(const struct list_head *list, struct list_head *prev,
 162     struct list_head *next)
 163 {
 164         struct list_head *first;
 165         struct list_head *last;
 166
 167         if (list_empty(list))
 168                 return;
 169
 170         first = list->next;
 171         last = list->prev;
 172         first->prev = prev;
 173         prev->next = first;
 174         last->next = next;
 175         next->prev = last;
 176 }
 177
 178 static inline void
 179 list_splice(const struct list_head *list, struct list_head *head)
 180 {
 181         _list_splice(list, head, head->next);
 182 }
 183
 184 static inline void
 185 list_splice_tail(struct list_head *list, struct list_head *head)
 186 {
 187         _list_splice(list, head->prev, head);
 188 }
 189
 190 static inline void
 191 list_splice_init(struct list_head *list, struct list_head *head)
 192 {
 193         _list_splice(list, head, head->next);
 194         INIT_LIST_HEAD(list);
 195 }
 196
 197 static inline void
 198 list_splice_tail_init(struct list_head *list, struct list_head *head)
 199 {
 200         _list_splice(list, head->prev, head);
 201         INIT_LIST_HEAD(list);
 202 }
 203
 204 #endif /* _LINUX_LIST_H_ */