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