1 /* $NetBSD: list.h,v 1.5 2014/08/20 15:26:52 riastradh Exp $ */
4 * Copyright (c) 2013 The NetBSD Foundation, Inc.
7 * This code is derived from software contributed to The NetBSD Foundation
8 * by Taylor R. Campbell.
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
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.
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.
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.
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).
44 #ifndef _LINUX_LIST_H_
45 #define _LINUX_LIST_H_
47 #include <sys/queue.h>
49 #define container_of(ptr, type, member) \
51 __typeof(((type *)0)->member) *_p = (ptr); \
52 (type *)((char *)_p - offsetof(type, member)); \
56 * Doubly-linked lists.
60 struct list_head *prev;
61 struct list_head *next;
64 #define LIST_HEAD_INIT(name) { .prev = &(name), .next = &(name) }
67 INIT_LIST_HEAD(struct list_head *head)
73 static inline struct list_head *
74 list_first(const struct list_head *head)
79 static inline struct list_head *
80 list_last(const struct list_head *head)
85 static inline struct list_head *
86 list_next(const struct list_head *node)
91 static inline struct list_head *
92 list_prev(const struct list_head *node)
98 list_empty(const struct list_head *head)
100 return (head->next == head);
104 list_is_singular(const struct list_head *head)
107 if (list_empty(head))
109 if (head->next != head->prev)
115 __list_add_between(struct list_head *prev, struct list_head *node,
116 struct list_head *next)
125 list_add(struct list_head *node, struct list_head *head)
127 __list_add_between(head, node, head->next);
131 list_add_tail(struct list_head *node, struct list_head *head)
133 __list_add_between(head->prev, node, head);
137 list_del(struct list_head *entry)
139 entry->prev->next = entry->next;
140 entry->next->prev = entry->prev;
144 __list_splice_between(struct list_head *prev, const struct list_head *list,
145 struct list_head *next)
147 struct list_head *first = list->next;
148 struct list_head *last = list->prev;
158 list_splice(const struct list_head *list, struct list_head *head)
160 if (!list_empty(list))
161 __list_splice_between(head, list, head->next);
165 list_splice_tail(const struct list_head *list, struct list_head *head)
167 if (!list_empty(list))
168 __list_splice_between(head->prev, list, head);
172 list_move(struct list_head *node, struct list_head *head)
175 list_add(node, head);
179 list_move_tail(struct list_head *node, struct list_head *head)
182 list_add_tail(node, head);
186 list_replace(struct list_head *old, struct list_head *new)
188 new->prev = old->prev;
189 old->prev->next = new;
190 new->next = old->next;
191 old->next->prev = new;
195 list_del_init(struct list_head *node)
198 INIT_LIST_HEAD(node);
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)
211 #define list_for_each(VAR, HEAD) \
212 for ((VAR) = list_first((HEAD)); \
214 (VAR) = list_next((VAR)))
216 #define list_for_each_safe(VAR, NEXT, HEAD) \
217 for ((VAR) = list_first((HEAD)); \
218 ((VAR) != (HEAD)) && ((NEXT) = list_next((VAR)), 1); \
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)), \
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)), \
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); \
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))
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))
250 #define list_for_each_entry_safe_from(VAR, NEXT, HEAD, FIELD) \
252 (&(VAR)->FIELD != (HEAD)) && \
253 ((NEXT) = list_next_entry((VAR), FIELD)); \
256 #endif /* _LINUX_LIST_H_ */