1 /* $NetBSD: list.h,v 1.5 2014/08/20 15:26:52 riastradh Exp $ */
2
3 /*-
4 * Copyright (c) 2013 The NetBSD Foundation, Inc.
5 * All rights reserved.
6 *
7 * This code is derived from software contributed to The NetBSD Foundation
8 * by Taylor R. Campbell.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 /*
33 * Notes on porting:
34 *
35 * - LIST_HEAD(x) means a declaration `struct list_head x =
36 * LIST_HEAD_INIT(x)' in Linux, but something else in NetBSD.
37 * Replace by the expansion.
38 *
39 * - The `_rcu' routines here are not actually pserialize(9)-safe.
40 * They need dependent read memory barriers added. Please fix this
41 * if you need to use them with pserialize(9).
42 */
43
44 #ifndef _LINUX_LIST_H_
45 #define _LINUX_LIST_H_
46
47 #include <sys/queue.h>
48
49 #define container_of(ptr, type, member) \
50 ({ \
51 __typeof(((type *)0)->member) *_p = (ptr); \
52 (type *)((char *)_p - offsetof(type, member)); \
53 })
54
55 /*
56 * Doubly-linked lists.
57 */
58
59 struct list_head {
60 struct list_head *prev;
61 struct list_head *next;
62 };
63
64 #define LIST_HEAD_INIT(name) { .prev = &(name), .next = &(name) }
65
66 static inline void
INIT_LIST_HEAD(struct list_head * head)67 INIT_LIST_HEAD(struct list_head *head)
68 {
69 head->prev = head;
70 head->next = head;
71 }
72
73 static inline struct list_head *
list_first(const struct list_head * head)74 list_first(const struct list_head *head)
75 {
76 return head->next;
77 }
78
79 static inline struct list_head *
list_last(const struct list_head * head)80 list_last(const struct list_head *head)
81 {
82 return head->prev;
83 }
84
85 static inline struct list_head *
list_next(const struct list_head * node)86 list_next(const struct list_head *node)
87 {
88 return node->next;
89 }
90
91 static inline struct list_head *
list_prev(const struct list_head * node)92 list_prev(const struct list_head *node)
93 {
94 return node->prev;
95 }
96
97 static inline int
list_empty(const struct list_head * head)98 list_empty(const struct list_head *head)
99 {
100 return (head->next == head);
101 }
102
103 static inline int
list_is_singular(const struct list_head * head)104 list_is_singular(const struct list_head *head)
105 {
106
107 if (list_empty(head))
108 return false;
109 if (head->next != head->prev)
110 return false;
111 return true;
112 }
113
114 static inline void
__list_add_between(struct list_head * prev,struct list_head * node,struct list_head * next)115 __list_add_between(struct list_head *prev, struct list_head *node,
116 struct list_head *next)
117 {
118 prev->next = node;
119 node->prev = prev;
120 node->next = next;
121 next->prev = node;
122 }
123
124 static inline void
list_add(struct list_head * node,struct list_head * head)125 list_add(struct list_head *node, struct list_head *head)
126 {
127 __list_add_between(head, node, head->next);
128 }
129
130 static inline void
list_add_tail(struct list_head * node,struct list_head * head)131 list_add_tail(struct list_head *node, struct list_head *head)
132 {
133 __list_add_between(head->prev, node, head);
134 }
135
136 static inline void
list_del(struct list_head * entry)137 list_del(struct list_head *entry)
138 {
139 entry->prev->next = entry->next;
140 entry->next->prev = entry->prev;
141 }
142
143 static inline void
__list_splice_between(struct list_head * prev,const struct list_head * list,struct list_head * next)144 __list_splice_between(struct list_head *prev, const struct list_head *list,
145 struct list_head *next)
146 {
147 struct list_head *first = list->next;
148 struct list_head *last = list->prev;
149
150 first->prev = prev;
151 prev->next = first;
152
153 last->next = next;
154 next->prev = last;
155 }
156
157 static inline void
list_splice(const struct list_head * list,struct list_head * head)158 list_splice(const struct list_head *list, struct list_head *head)
159 {
160 if (!list_empty(list))
161 __list_splice_between(head, list, head->next);
162 }
163
164 static inline void
list_splice_tail(const struct list_head * list,struct list_head * head)165 list_splice_tail(const struct list_head *list, struct list_head *head)
166 {
167 if (!list_empty(list))
168 __list_splice_between(head->prev, list, head);
169 }
170
171 static inline void
list_move(struct list_head * node,struct list_head * head)172 list_move(struct list_head *node, struct list_head *head)
173 {
174 list_del(node);
175 list_add(node, head);
176 }
177
178 static inline void
list_move_tail(struct list_head * node,struct list_head * head)179 list_move_tail(struct list_head *node, struct list_head *head)
180 {
181 list_del(node);
182 list_add_tail(node, head);
183 }
184
185 static inline void
list_replace(struct list_head * old,struct list_head * new)186 list_replace(struct list_head *old, struct list_head *new)
187 {
188 new->prev = old->prev;
189 old->prev->next = new;
190 new->next = old->next;
191 old->next->prev = new;
192 }
193
194 static inline void
list_del_init(struct list_head * node)195 list_del_init(struct list_head *node)
196 {
197 list_del(node);
198 INIT_LIST_HEAD(node);
199 }
200
201 #define list_entry(PTR, TYPE, FIELD) container_of(PTR, TYPE, FIELD)
202 #define list_first_entry(PTR, TYPE, FIELD) \
203 list_entry(list_first((PTR)), TYPE, FIELD)
204 #define list_last_entry(PTR, TYPE, FIELD) \
205 list_entry(list_last((PTR)), TYPE, FIELD)
206 #define list_next_entry(ENTRY, FIELD) \
207 list_entry(list_next(&(ENTRY)->FIELD), typeof(*(ENTRY)), FIELD)
208 #define list_prev_entry(ENTRY, FIELD) \
209 list_entry(list_prev(&(ENTRY)->FIELD), typeof(*(ENTRY)), FIELD)
210
211 #define list_for_each(VAR, HEAD) \
212 for ((VAR) = list_first((HEAD)); \
213 (VAR) != (HEAD); \
214 (VAR) = list_next((VAR)))
215
216 #define list_for_each_safe(VAR, NEXT, HEAD) \
217 for ((VAR) = list_first((HEAD)); \
218 ((VAR) != (HEAD)) && ((NEXT) = list_next((VAR)), 1); \
219 (VAR) = (NEXT))
220
221 #define list_for_each_entry(VAR, HEAD, FIELD) \
222 for ((VAR) = list_entry(list_first((HEAD)), typeof(*(VAR)), FIELD); \
223 &(VAR)->FIELD != (HEAD); \
224 (VAR) = list_entry(list_next(&(VAR)->FIELD), typeof(*(VAR)), \
225 FIELD))
226
227 #define list_for_each_entry_reverse(VAR, HEAD, FIELD) \
228 for ((VAR) = list_entry(list_last((HEAD)), typeof(*(VAR)), FIELD); \
229 &(VAR)->FIELD != (HEAD); \
230 (VAR) = list_entry(list_prev(&(VAR)->FIELD), typeof(*(VAR)), \
231 FIELD))
232
233 #define list_for_each_entry_safe(VAR, NEXT, HEAD, FIELD) \
234 for ((VAR) = list_entry(list_first((HEAD)), typeof(*(VAR)), FIELD); \
235 (&(VAR)->FIELD != (HEAD)) && \
236 ((NEXT) = list_entry(list_next(&(VAR)->FIELD), \
237 typeof(*(VAR)), FIELD), 1); \
238 (VAR) = (NEXT))
239
240 #define list_for_each_entry_continue(VAR, HEAD, FIELD) \
241 for ((VAR) = list_next_entry((VAR), FIELD); \
242 &(VAR)->FIELD != (HEAD); \
243 (VAR) = list_next_entry((VAR), FIELD))
244
245 #define list_for_each_entry_continue_reverse(VAR, HEAD, FIELD) \
246 for ((VAR) = list_prev_entry((VAR), FIELD); \
247 &(VAR)->FIELD != (HEAD); \
248 (VAR) = list_prev_entry((VAR), FIELD))
249
250 #define list_for_each_entry_safe_from(VAR, NEXT, HEAD, FIELD) \
251 for (; \
252 (&(VAR)->FIELD != (HEAD)) && \
253 ((NEXT) = list_next_entry((VAR), FIELD)); \
254 (VAR) = (NEXT))
255
256 #endif /* _LINUX_LIST_H_ */
257