Branch data Line data Source code
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/null.h>
48 : : #include <sys/queue.h>
49 : : #include <linux/kernel.h>
50 : : #include <stddef.h>
51 : : #include <stdbool.h>
52 : :
53 : : /*
54 : : * Doubly-linked lists.
55 : : */
56 : :
57 : : struct list_head {
58 : : struct list_head *prev;
59 : : struct list_head *next;
60 : : };
61 : :
62 : : #define LIST_HEAD_INIT(name) { .prev = &(name), .next = &(name) }
63 : :
64 : : static inline void
65 : 142 : INIT_LIST_HEAD(struct list_head *head)
66 : : {
67 : 142 : head->prev = head;
68 [ + + # ]: 88 : head->next = head;
69 : 3 : }
70 : :
71 : : static inline struct list_head *
72 : 262 : list_first(const struct list_head *head)
73 : : {
74 : 267 : return head->next;
75 : : }
76 : :
77 : : static inline struct list_head *
78 : 0 : list_last(const struct list_head *head)
79 : : {
80 : 0 : return head->prev;
81 : : }
82 : :
83 : : static inline struct list_head *
84 : 259 : list_next(const struct list_head *node)
85 : : {
86 [ + + # # : 259 : return node->next;
# # ]
87 : : }
88 : :
89 : : static inline struct list_head *
90 : 0 : list_prev(const struct list_head *node)
91 : : {
92 : 0 : return node->prev;
93 : : }
94 : :
95 : : static inline int
96 : 0 : list_is_last(const struct list_head *list, const struct list_head *head)
97 : : {
98 [ # # # # ]: 0 : return list->next == head;
99 : : }
100 : :
101 : : static inline int
102 : 15 : list_empty(const struct list_head *head)
103 : : {
104 [ - - - + : 10 : return (head->next == head);
- - + - +
- - - - -
- - - - -
- - - - -
- - - - -
- - - - -
- - - - -
- - - - -
- - - - -
- - - # #
# # # # #
# # # ]
105 : : }
106 : :
107 : : static inline int
108 : 4 : list_is_singular(const struct list_head *head)
109 : : {
110 : :
111 [ + - ]: 4 : if (list_empty(head))
112 : : return false;
113 [ - + ]: 4 : if (head->next != head->prev)
114 : 0 : return false;
115 : : return true;
116 : : }
117 : :
118 : : static inline void
119 : 73 : __list_add_between(struct list_head *prev, struct list_head *node,
120 : : struct list_head *next)
121 : : {
122 : 73 : prev->next = node;
123 : 73 : node->prev = prev;
124 : 73 : node->next = next;
125 : 73 : next->prev = node;
126 : : }
127 : :
128 : : static inline void
129 : 3 : list_add(struct list_head *node, struct list_head *head)
130 : : {
131 : 3 : __list_add_between(head, node, head->next);
132 : 3 : }
133 : :
134 : : static inline void
135 : 70 : list_add_tail(struct list_head *node, struct list_head *head)
136 : : {
137 [ + - ]: 65 : __list_add_between(head->prev, node, head);
138 : 2 : }
139 : :
140 : : static inline void
141 : 74 : list_del(struct list_head *entry)
142 : : {
143 : 74 : entry->prev->next = entry->next;
144 [ + - ]: 74 : entry->next->prev = entry->prev;
145 : : }
146 : :
147 : : static inline void
148 : 1 : __list_splice_between(struct list_head *prev, const struct list_head *list,
149 : : struct list_head *next)
150 : : {
151 : 1 : struct list_head *first = list->next;
152 : 1 : struct list_head *last = list->prev;
153 : :
154 : 1 : first->prev = prev;
155 : 1 : prev->next = first;
156 : :
157 : 1 : last->next = next;
158 : 1 : next->prev = last;
159 : 1 : }
160 : :
161 : : static inline void
162 : 0 : list_splice(const struct list_head *list, struct list_head *head)
163 : : {
164 [ # # # # ]: 0 : if (!list_empty(list))
165 : 0 : __list_splice_between(head, list, head->next);
166 : : }
167 : :
168 : : static inline void
169 : 5 : list_splice_tail(const struct list_head *list, struct list_head *head)
170 : : {
171 [ + + ]: 5 : if (!list_empty(list))
172 : 1 : __list_splice_between(head->prev, list, head);
173 : : }
174 : :
175 : : static inline void
176 : 0 : list_move(struct list_head *node, struct list_head *head)
177 : : {
178 : 0 : list_del(node);
179 [ # # ]: 0 : list_add(node, head);
180 : 0 : }
181 : :
182 : : static inline void
183 : 3 : list_move_tail(struct list_head *node, struct list_head *head)
184 : : {
185 : 3 : list_del(node);
186 [ # # ]: 3 : list_add_tail(node, head);
187 : : }
188 : :
189 : : static inline void
190 : : list_replace(struct list_head *old, struct list_head *new)
191 : : {
192 : : new->prev = old->prev;
193 : : old->prev->next = new;
194 : : new->next = old->next;
195 : : old->next->prev = new;
196 : : }
197 : :
198 : : static inline void
199 : 9 : list_del_init(struct list_head *node)
200 : : {
201 : 9 : list_del(node);
202 [ + + ]: 9 : INIT_LIST_HEAD(node);
203 : : }
204 : :
205 : : #define check_type(expr, type) \
206 : : ((typeof(expr) *)0 != (type *)0)
207 : :
208 : : #define check_types_match(expr1, expr2) \
209 : : ((typeof(expr1) *)0 != (typeof(expr2) *)0)
210 : :
211 : : #define container_off(containing_type, member) \
212 : : offsetof(containing_type, member)
213 : :
214 : : #define container_of(member_ptr, containing_type, member) \
215 : : ((containing_type *) \
216 : : ((char *)(member_ptr) \
217 : : - container_off(containing_type, member)) \
218 : : + check_types_match(*(member_ptr), ((containing_type *)0)->member))
219 : :
220 : : #define list_entry(PTR, TYPE, FIELD) container_of(PTR, TYPE, FIELD)
221 : : #define list_first_entry(PTR, TYPE, FIELD) \
222 : : list_entry(list_first((PTR)), TYPE, FIELD)
223 : : #define list_last_entry(PTR, TYPE, FIELD) \
224 : : list_entry(list_last((PTR)), TYPE, FIELD)
225 : : #define list_next_entry(ENTRY, FIELD) \
226 : : list_entry(list_next(&(ENTRY)->FIELD), typeof(*(ENTRY)), FIELD)
227 : : #define list_prev_entry(ENTRY, FIELD) \
228 : : list_entry(list_prev(&(ENTRY)->FIELD), typeof(*(ENTRY)), FIELD)
229 : :
230 : : #define list_for_each(VAR, HEAD) \
231 : : for ((VAR) = list_first((HEAD)); \
232 : : (VAR) != (HEAD); \
233 : : (VAR) = list_next((VAR)))
234 : :
235 : : #define list_for_each_safe(VAR, NEXT, HEAD) \
236 : : for ((VAR) = list_first((HEAD)); \
237 : : ((VAR) != (HEAD)) && ((NEXT) = list_next((VAR)), 1); \
238 : : (VAR) = (NEXT))
239 : :
240 : : #define list_for_each_entry(VAR, HEAD, FIELD) \
241 : : for ((VAR) = list_entry(list_first((HEAD)), typeof(*(VAR)), FIELD); \
242 : : &(VAR)->FIELD != (HEAD); \
243 : : (VAR) = list_entry(list_next(&(VAR)->FIELD), typeof(*(VAR)), \
244 : : FIELD))
245 : :
246 : : #define list_for_each_entry_reverse(VAR, HEAD, FIELD) \
247 : : for ((VAR) = list_entry(list_last((HEAD)), typeof(*(VAR)), FIELD); \
248 : : &(VAR)->FIELD != (HEAD); \
249 : : (VAR) = list_entry(list_prev(&(VAR)->FIELD), typeof(*(VAR)), \
250 : : FIELD))
251 : :
252 : : #define list_for_each_entry_safe(VAR, NEXT, HEAD, FIELD) \
253 : : for ((VAR) = list_entry(list_first((HEAD)), typeof(*(VAR)), FIELD); \
254 : : (&(VAR)->FIELD != (HEAD)) && \
255 : : ((NEXT) = list_entry(list_next(&(VAR)->FIELD), \
256 : : typeof(*(VAR)), FIELD), 1); \
257 : : (VAR) = (NEXT))
258 : :
259 : : #define list_for_each_entry_continue(VAR, HEAD, FIELD) \
260 : : for ((VAR) = list_next_entry((VAR), FIELD); \
261 : : &(VAR)->FIELD != (HEAD); \
262 : : (VAR) = list_next_entry((VAR), FIELD))
263 : :
264 : : #define list_for_each_entry_continue_reverse(VAR, HEAD, FIELD) \
265 : : for ((VAR) = list_prev_entry((VAR), FIELD); \
266 : : &(VAR)->FIELD != (HEAD); \
267 : : (VAR) = list_prev_entry((VAR), FIELD))
268 : :
269 : : #define list_for_each_entry_safe_from(VAR, NEXT, HEAD, FIELD) \
270 : : for (; \
271 : : (&(VAR)->FIELD != (HEAD)) && \
272 : : ((NEXT) = list_next_entry((VAR), FIELD)); \
273 : : (VAR) = (NEXT))
274 : :
275 : : /*
276 : : * `H'ead-only/`H'ash-table doubly-linked lists.
277 : : */
278 : :
279 : : LIST_HEAD(hlist_head, hlist_node);
280 : : struct hlist_node {
281 : : LIST_ENTRY(hlist_node) hln_entry;
282 : : };
283 : :
284 : : static inline struct hlist_node *
285 : : hlist_first(struct hlist_head *head)
286 : : {
287 : : return LIST_FIRST(head);
288 : : }
289 : :
290 : : static inline struct hlist_node *
291 : : hlist_next(struct hlist_node *node)
292 : : {
293 : : return LIST_NEXT(node, hln_entry);
294 : : }
295 : :
296 : : static inline void
297 : : hlist_add_head(struct hlist_node *node, struct hlist_head *head)
298 : : {
299 : : LIST_INSERT_HEAD(head, node, hln_entry);
300 : : }
301 : :
302 : : static inline void
303 : : hlist_add_after(struct hlist_node *node, struct hlist_node *next)
304 : : {
305 : : LIST_INSERT_AFTER(node, next, hln_entry);
306 : : }
307 : :
308 : : static inline void
309 : : hlist_del(struct hlist_node *node)
310 : : {
311 : : LIST_REMOVE(node, hln_entry);
312 : : }
313 : :
314 : : static inline void
315 : : hlist_del_init(struct hlist_node *node)
316 : : {
317 : : LIST_REMOVE(node, hln_entry);
318 : : }
319 : :
320 : : #define hlist_entry(PTR, TYPE, FIELD) container_of(PTR, TYPE, FIELD)
321 : : #define hlist_for_each(VAR, HEAD) LIST_FOREACH(VAR, HEAD, hln_entry)
322 : : #define hlist_for_each_safe(VAR, NEXT, HEAD) \
323 : : LIST_FOREACH_SAFE(VAR, HEAD, hln_entry, NEXT)
324 : :
325 : : #define hlist_for_each_entry(VAR, HEAD, FIELD) \
326 : : for ((VAR) = hlist_entry(LIST_FIRST((HEAD)), typeof(*(VAR)), FIELD); \
327 : : &(VAR)->FIELD != NULL; \
328 : : (VAR) = hlist_entry(LIST_NEXT(&(VAR)->FIELD, hln_entry), \
329 : : typeof(*(VAR)), FIELD))
330 : :
331 : : /*
332 : : * XXX The nominally RCU-safe APIs below lack dependent read barriers,
333 : : * so they're not actually RCU-safe...on the alpha, anyway. Someone^TM
334 : : * should fix this.
335 : : */
336 : :
337 : : #define hlist_add_after_rcu hlist_add_after
338 : : #define hlist_add_head_rcu hlist_add_head
339 : : #define hlist_del_init_rcu hlist_del_init
340 : : #define hlist_for_each_entry_rcu hlist_for_each_entry
341 : :
342 : : #endif /* _LINUX_LIST_H_ */
|
