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