• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*-
2  * Copyright (c) 2010 Isilon Systems, Inc.
3  * Copyright (c) 2010 iX Systems, Inc.
4  * Copyright (c) 2010 Panasas, Inc.
5  * Copyright (c) 2013-2016 Mellanox Technologies, Ltd.
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  * $FreeBSD: releng/12.2/sys/compat/linuxkpi/common/include/linux/list.h 364652 2020-08-24 10:28:15Z manu $
30  */
31 #ifndef _LINUX_LIST_H_
32 #define _LINUX_LIST_H_
33 
34 #include "linux/compiler.h"
35 #include "los_list.h"
36 
37 #ifdef __cplusplus
38 #if __cplusplus
39 extern "C" {
40 #endif /* __cplusplus */
41 #endif /* __cplusplus */
42 
43 #ifndef prefetch
44 #define	prefetch(x)
45 #endif
46 
47 #define LINUX_LIST_HEAD_INIT(name) { &(name), &(name) }
48 
49 #define LINUX_LIST_HEAD(name) \
50 		struct list_head name = LINUX_LIST_HEAD_INIT(name)
51 
52 #ifndef LIST_HEAD_DEF
53 #define	LIST_HEAD_DEF
54 	struct list_head {
55 		struct list_head *next;
56 		struct list_head *prev;
57 	};
58 #endif
59 
60 #define container_of LOS_DL_LIST_ENTRY
61 
62 static inline void
INIT_LIST_HEAD(struct list_head * list)63 INIT_LIST_HEAD(struct list_head *list)
64 {
65 
66 	list->next = list->prev = list;
67 }
68 
69 static inline int
list_empty(const struct list_head * head)70 list_empty(const struct list_head *head)
71 {
72 
73 	return (head->next == head);
74 }
75 
76 static inline int
list_empty_careful(const struct list_head * head)77 list_empty_careful(const struct list_head *head)
78 {
79 	struct list_head *next = head->next;
80 
81 	return ((next == head) && (next == head->prev));
82 }
83 
84 static inline void
__list_del(struct list_head * prev,struct list_head * next)85 __list_del(struct list_head *prev, struct list_head *next)
86 {
87 	next->prev = prev;
88 	WRITE_ONCE(prev->next, next);
89 }
90 
91 static inline void
__list_del_entry(struct list_head * entry)92 __list_del_entry(struct list_head *entry)
93 {
94 
95 	__list_del(entry->prev, entry->next);
96 }
97 
98 static inline void
list_del(struct list_head * entry)99 list_del(struct list_head *entry)
100 {
101 
102 	__list_del(entry->prev, entry->next);
103 }
104 
105 static inline void
list_replace(struct list_head * old,struct list_head * new)106 list_replace(struct list_head *old, struct list_head *new)
107 {
108 	new->next = old->next;
109 	new->next->prev = new;
110 	new->prev = old->prev;
111 	new->prev->next = new;
112 }
113 
114 static inline void
list_replace_init(struct list_head * old,struct list_head * new)115 list_replace_init(struct list_head *old, struct list_head *new)
116 {
117 	list_replace(old, new);
118 	INIT_LIST_HEAD(old);
119 }
120 
121 static inline void
linux_list_add(struct list_head * new,struct list_head * prev,struct list_head * next)122 linux_list_add(struct list_head *new, struct list_head *prev,
123 	struct list_head *next)
124 {
125 
126 	next->prev = new;
127 	new->next = next;
128 	new->prev = prev;
129 	prev->next = new;
130 }
131 
132 static inline void
list_del_init(struct list_head * entry)133 list_del_init(struct list_head *entry)
134 {
135 
136 	list_del(entry);
137 	INIT_LIST_HEAD(entry);
138 }
139 
140 #define	list_entry(ptr, type, field)	container_of(ptr, type, field)
141 
142 #define	list_first_entry(ptr, type, member) \
143 	list_entry((ptr)->next, type, member)
144 
145 #define	list_last_entry(ptr, type, member)	\
146 	list_entry((ptr)->prev, type, member)
147 
148 #define	list_first_entry_or_null(ptr, type, member) \
149 	(!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL)
150 
151 #define	list_next_entry(ptr, member)					\
152 	list_entry(((ptr)->member.next), typeof(*(ptr)), member)
153 
154 #define	list_safe_reset_next(ptr, n, member) \
155 	(n) = list_next_entry(ptr, member)
156 
157 #define	list_prev_entry(ptr, member)					\
158 	list_entry(((ptr)->member.prev), typeof(*(ptr)), member)
159 
160 #define	list_for_each(p, head)						\
161 	for (p = (head)->next; p != (head); p = (p)->next)
162 
163 #define	list_for_each_safe(p, n, head)					\
164 	for (p = (head)->next, n = (p)->next; p != (head); p = n, n = (p)->next)
165 
166 #define list_for_each_entry(p, h, field)				\
167 	for (p = list_entry((h)->next, typeof(*p), field); &(p)->field != (h); \
168 		p = list_entry((p)->field.next, typeof(*p), field))
169 
170 #define list_for_each_entry_safe(p, n, h, field)			\
171 	for (p = list_entry((h)->next, typeof(*p), field),		\
172 		n = list_entry((p)->field.next, typeof(*p), field); &(p)->field != (h);\
173 		p = n, n = list_entry(n->field.next, typeof(*n), field))
174 
175 #define	list_for_each_entry_from(p, h, field) \
176 	for ( ; &(p)->field != (h); \
177 		p = list_entry((p)->field.next, typeof(*p), field))
178 
179 #define	list_for_each_entry_continue(p, h, field)			\
180 	for (p = list_next_entry((p), field); &(p)->field != (h);	\
181 		p = list_next_entry((p), field))
182 
183 #define	list_for_each_entry_safe_from(pos, n, head, member)			\
184 	for (n = list_entry((pos)->member.next, typeof(*pos), member);		\
185 		 &(pos)->member != (head);						\
186 		 pos = n, n = list_entry(n->member.next, typeof(*n), member))
187 
188 #define	list_for_each_entry_reverse(p, h, field)			\
189 	for (p = list_entry((h)->prev, typeof(*p), field); &(p)->field != (h); \
190 		p = list_entry((p)->field.prev, typeof(*p), field))
191 
192 #define	list_for_each_entry_safe_reverse(p, n, h, field)		\
193 	for (p = list_entry((h)->prev, typeof(*p), field),		\
194 		n = list_entry((p)->field.prev, typeof(*p), field); &(p)->field != (h); \
195 		p = n, n = list_entry(n->field.prev, typeof(*n), field))
196 
197 #define	list_for_each_entry_continue_reverse(p, h, field) \
198 	for (p = list_entry((p)->field.prev, typeof(*p), field); &(p)->field != (h); \
199 		p = list_entry((p)->field.prev, typeof(*p), field))
200 
201 #define	list_for_each_prev(p, h) for (p = (h)->prev; p != (h); p = (p)->prev)
202 
203 #define	list_for_each_entry_from_reverse(p, h, field)	\
204 	for (; &p->field != (h);			\
205 		 p = list_prev_entry(p, field))
206 
207 static inline void
list_add(struct list_head * new,struct list_head * head)208 list_add(struct list_head *new, struct list_head *head)
209 {
210 
211 	linux_list_add(new, head, head->next);
212 }
213 
214 static inline void
list_add_tail(struct list_head * new,struct list_head * head)215 list_add_tail(struct list_head *new, struct list_head *head)
216 {
217 
218 	linux_list_add(new, head->prev, head);
219 }
220 
221 static inline void
list_move(struct list_head * list,struct list_head * head)222 list_move(struct list_head *list, struct list_head *head)
223 {
224 
225 	list_del(list);
226 	list_add(list, head);
227 }
228 
229 static inline void
list_move_tail(struct list_head * entry,struct list_head * head)230 list_move_tail(struct list_head *entry, struct list_head *head)
231 {
232 
233 	list_del(entry);
234 	list_add_tail(entry, head);
235 }
236 
237 static inline void
list_bulk_move_tail(struct list_head * head,struct list_head * first,struct list_head * last)238 list_bulk_move_tail(struct list_head *head, struct list_head *first,
239 	struct list_head *last)
240 {
241 	first->prev->next = last->next;
242 	last->next->prev = first->prev;
243 	head->prev->next = first;
244 	first->prev = head->prev;
245 	last->next = head;
246 	head->prev = last;
247 }
248 
249 static inline void
linux_list_splice(const struct list_head * list,struct list_head * prev,struct list_head * next)250 linux_list_splice(const struct list_head *list, struct list_head *prev,
251 	struct list_head *next)
252 {
253 	struct list_head *first = NULL;
254 	struct list_head *last = NULL;
255 
256 	if (list_empty(list))
257 		return;
258 	first = list->next;
259 	last = list->prev;
260 	first->prev = prev;
261 	prev->next = first;
262 	last->next = next;
263 	next->prev = last;
264 }
265 
266 static inline void
list_splice(const struct list_head * list,struct list_head * head)267 list_splice(const struct list_head *list, struct list_head *head)
268 {
269 
270 	linux_list_splice(list, head, head->next);
271 }
272 
273 static inline void
list_splice_tail(struct list_head * list,struct list_head * head)274 list_splice_tail(struct list_head *list, struct list_head *head)
275 {
276 
277 	linux_list_splice(list, head->prev, head);
278 }
279 
280 static inline void
list_splice_init(struct list_head * list,struct list_head * head)281 list_splice_init(struct list_head *list, struct list_head *head)
282 {
283 
284 	linux_list_splice(list, head, head->next);
285 	INIT_LIST_HEAD(list);
286 }
287 
288 static inline void
list_splice_tail_init(struct list_head * list,struct list_head * head)289 list_splice_tail_init(struct list_head *list, struct list_head *head)
290 {
291 
292 	linux_list_splice(list, head->prev, head);
293 	INIT_LIST_HEAD(list);
294 }
295 
296 
297 struct hlist_head {
298 	struct hlist_node *first;
299 };
300 
301 struct hlist_node {
302 	struct hlist_node *next, **pprev;
303 };
304 
305 #define	HLIST_HEAD_INIT { }
306 #define	HLIST_HEAD(name) struct hlist_head name = HLIST_HEAD_INIT
307 #define	INIT_HLIST_HEAD(head) (head)->first = NULL
308 #define	INIT_HLIST_NODE(node)						\
309 do {									\
310 	(node)->next = NULL;						\
311 	(node)->pprev = NULL;						\
312 } while (0)
313 
314 static inline int
hlist_unhashed(const struct hlist_node * h)315 hlist_unhashed(const struct hlist_node *h)
316 {
317 
318 	return !h->pprev;
319 }
320 
321 static inline int
hlist_empty(const struct hlist_head * h)322 hlist_empty(const struct hlist_head *h)
323 {
324 
325 	return !READ_ONCE(h->first);
326 }
327 
328 static inline void
hlist_del(struct hlist_node * n)329 hlist_del(struct hlist_node *n)
330 {
331 
332 	WRITE_ONCE(*(n->pprev), n->next);
333 	if (n->next != NULL)
334 		n->next->pprev = n->pprev;
335 }
336 
337 static inline void
hlist_del_init(struct hlist_node * n)338 hlist_del_init(struct hlist_node *n)
339 {
340 
341 	if (hlist_unhashed(n))
342 		return;
343 	hlist_del(n);
344 	INIT_HLIST_NODE(n);
345 }
346 
347 static inline void
hlist_add_head(struct hlist_node * n,struct hlist_head * h)348 hlist_add_head(struct hlist_node *n, struct hlist_head *h)
349 {
350 
351 	n->next = h->first;
352 	if (h->first != NULL)
353 		h->first->pprev = &n->next;
354 	WRITE_ONCE(h->first, n);
355 	n->pprev = &h->first;
356 }
357 
358 static inline void
hlist_add_before(struct hlist_node * n,struct hlist_node * next)359 hlist_add_before(struct hlist_node *n, struct hlist_node *next)
360 {
361 
362 	n->pprev = next->pprev;
363 	n->next = next;
364 	next->pprev = &n->next;
365 	WRITE_ONCE(*(n->pprev), n);
366 }
367 
368 static inline void
hlist_add_behind(struct hlist_node * n,struct hlist_node * prev)369 hlist_add_behind(struct hlist_node *n, struct hlist_node *prev)
370 {
371 
372 	n->next = prev->next;
373 	WRITE_ONCE(prev->next, n);
374 	n->pprev = &prev->next;
375 
376 	if (n->next != NULL)
377 		n->next->pprev = &n->next;
378 }
379 
380 static inline void
hlist_move_list(struct hlist_head * old,struct hlist_head * new)381 hlist_move_list(struct hlist_head *old, struct hlist_head *new)
382 {
383 
384 	new->first = old->first;
385 	if (new->first)
386 		new->first->pprev = &new->first;
387 	old->first = NULL;
388 }
389 
list_is_singular(const struct list_head * head)390 static inline int list_is_singular(const struct list_head *head)
391 {
392 	return !list_empty(head) && (head->next == head->prev);
393 }
394 
__list_cut_position(struct list_head * list,struct list_head * head,struct list_head * entry)395 static inline void __list_cut_position(struct list_head *list,
396 		struct list_head *head, struct list_head *entry)
397 {
398 	struct list_head *new_first = entry->next;
399 	list->next = head->next;
400 	list->next->prev = list;
401 	list->prev = entry;
402 	entry->next = list;
403 	head->next = new_first;
404 	new_first->prev = head;
405 }
406 
list_cut_position(struct list_head * list,struct list_head * head,struct list_head * entry)407 static inline void list_cut_position(struct list_head *list,
408 		struct list_head *head, struct list_head *entry)
409 {
410 	if (list_empty(head))
411 		return;
412 	if (list_is_singular(head) &&
413 		(head->next != entry && head != entry))
414 		return;
415 	if (entry == head)
416 		INIT_LIST_HEAD(list);
417 	else
418 		__list_cut_position(list, head, entry);
419 }
420 
list_is_first(const struct list_head * list,const struct list_head * head)421 static inline int list_is_first(const struct list_head *list,
422 				const struct list_head *head)
423 {
424 
425 	return (list->prev == head);
426 }
427 
list_is_last(const struct list_head * list,const struct list_head * head)428 static inline int list_is_last(const struct list_head *list,
429 				const struct list_head *head)
430 {
431 	return list->next == head;
432 }
433 
434 #define	hlist_entry(ptr, type, field)	container_of(ptr, type, field)
435 
436 #define	hlist_for_each(p, head)						\
437 	for (p = (head)->first; p; p = (p)->next)
438 
439 #define	hlist_for_each_safe(p, n, head)					\
440 	for (p = (head)->first; p && ({ n = (p)->next; 1; }); p = n)
441 
442 #define	hlist_entry_safe(ptr, type, member) \
443 	((ptr) ? hlist_entry(ptr, type, member) : NULL)
444 
445 #define	hlist_for_each_entry(pos, head, member)				\
446 	for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
447 		 pos;							\
448 		 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
449 
450 #define	hlist_for_each_entry_continue(pos, member)			\
451 	for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member); \
452 		 (pos); 						\
453 		 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
454 
455 #define	hlist_for_each_entry_from(pos, member)				\
456 	for (; (pos);								\
457 		 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
458 
459 #define	hlist_for_each_entry_safe(pos, n, head, member)			\
460 	for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member); \
461 		 (pos) && ({ n = (pos)->member.next; 1; }); 		\
462 		 pos = hlist_entry_safe(n, typeof(*(pos)), member))
463 
464 extern void list_sort(void *priv, struct list_head *head, int (*cmp)(void *priv,
465 	struct list_head *a, struct list_head *b));
466 
467 
468 #ifdef __cplusplus
469 #if __cplusplus
470 }
471 #endif /* __cplusplus */
472 #endif /* __cplusplus */
473 
474 #endif /* _LINUX_LIST_H_ */
475