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
59struct 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
66static inline void
67INIT_LIST_HEAD(struct list_head *head)
68{
69	head->prev = head;
70	head->next = head;
71}
72
73static inline struct list_head *
74list_first(const struct list_head *head)
75{
76	return head->next;
77}
78
79static inline struct list_head *
80list_last(const struct list_head *head)
81{
82	return head->prev;
83}
84
85static inline struct list_head *
86list_next(const struct list_head *node)
87{
88	return node->next;
89}
90
91static inline struct list_head *
92list_prev(const struct list_head *node)
93{
94	return node->prev;
95}
96
97static inline int
98list_empty(const struct list_head *head)
99{
100	return (head->next == head);
101}
102
103static inline int
104list_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
114static inline void
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
124static inline void
125list_add(struct list_head *node, struct list_head *head)
126{
127	__list_add_between(head, node, head->next);
128}
129
130static inline void
131list_add_tail(struct list_head *node, struct list_head *head)
132{
133	__list_add_between(head->prev, node, head);
134}
135
136static inline void
137list_del(struct list_head *entry)
138{
139	entry->prev->next = entry->next;
140	entry->next->prev = entry->prev;
141}
142
143static inline void
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
157static inline void
158list_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
164static inline void
165list_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
171static inline void
172list_move(struct list_head *node, struct list_head *head)
173{
174	list_del(node);
175	list_add(node, head);
176}
177
178static inline void
179list_move_tail(struct list_head *node, struct list_head *head)
180{
181	list_del(node);
182	list_add_tail(node, head);
183}
184
185static inline void
186list_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
194static inline void
195list_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