1#ifndef _LINUX_LIST_H
2#define _LINUX_LIST_H
3
4#include <linux/types.h>
5#include <linux/stddef.h>
6#include <linux/poison.h>
7#include <linux/const.h>
8#include <linux/kernel.h>
9
10
11
12
13
14
15
16
17
18
19
20#define LIST_HEAD_INIT(name) { &(name), &(name) }
21
22#define LIST_HEAD(name) \
23 struct list_head name = LIST_HEAD_INIT(name)
24
25static inline void INIT_LIST_HEAD(struct list_head *list)
26{
27 WRITE_ONCE(list->next, list);
28 list->prev = list;
29}
30
31#ifdef CONFIG_DEBUG_LIST
32extern bool __list_add_valid(struct list_head *new,
33 struct list_head *prev,
34 struct list_head *next);
35extern bool __list_del_entry_valid(struct list_head *entry);
36#else
37static inline bool __list_add_valid(struct list_head *new,
38 struct list_head *prev,
39 struct list_head *next)
40{
41 return true;
42}
43static inline bool __list_del_entry_valid(struct list_head *entry)
44{
45 return true;
46}
47#endif
48
49
50
51
52
53
54
55static inline void __list_add(struct list_head *new,
56 struct list_head *prev,
57 struct list_head *next)
58{
59 if (!__list_add_valid(new, prev, next))
60 return;
61
62 next->prev = new;
63 new->next = next;
64 new->prev = prev;
65 WRITE_ONCE(prev->next, new);
66}
67
68
69
70
71
72
73
74
75
76static inline void list_add(struct list_head *new, struct list_head *head)
77{
78 __list_add(new, head, head->next);
79}
80
81
82
83
84
85
86
87
88
89
90static inline void list_add_tail(struct list_head *new, struct list_head *head)
91{
92 __list_add(new, head->prev, head);
93}
94
95
96
97
98
99
100
101
102static inline void __list_del(struct list_head * prev, struct list_head * next)
103{
104 next->prev = prev;
105 WRITE_ONCE(prev->next, next);
106}
107
108
109
110
111
112
113
114static inline void __list_del_entry(struct list_head *entry)
115{
116 if (!__list_del_entry_valid(entry))
117 return;
118
119 __list_del(entry->prev, entry->next);
120}
121
122static inline void list_del(struct list_head *entry)
123{
124 __list_del_entry(entry);
125 entry->next = LIST_POISON1;
126 entry->prev = LIST_POISON2;
127}
128
129
130
131
132
133
134
135
136static inline void list_replace(struct list_head *old,
137 struct list_head *new)
138{
139 new->next = old->next;
140 new->next->prev = new;
141 new->prev = old->prev;
142 new->prev->next = new;
143}
144
145static inline void list_replace_init(struct list_head *old,
146 struct list_head *new)
147{
148 list_replace(old, new);
149 INIT_LIST_HEAD(old);
150}
151
152
153
154
155
156static inline void list_del_init(struct list_head *entry)
157{
158 __list_del_entry(entry);
159 INIT_LIST_HEAD(entry);
160}
161
162
163
164
165
166
167static inline void list_move(struct list_head *list, struct list_head *head)
168{
169 __list_del_entry(list);
170 list_add(list, head);
171}
172
173
174
175
176
177
178static inline void list_move_tail(struct list_head *list,
179 struct list_head *head)
180{
181 __list_del_entry(list);
182 list_add_tail(list, head);
183}
184
185
186
187
188
189
190static inline int list_is_last(const struct list_head *list,
191 const struct list_head *head)
192{
193 return list->next == head;
194}
195
196
197
198
199
200static inline int list_empty(const struct list_head *head)
201{
202 return READ_ONCE(head->next) == head;
203}
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218static inline int list_empty_careful(const struct list_head *head)
219{
220 struct list_head *next = head->next;
221 return (next == head) && (next == head->prev);
222}
223
224
225
226
227
228static inline void list_rotate_left(struct list_head *head)
229{
230 struct list_head *first;
231
232 if (!list_empty(head)) {
233 first = head->next;
234 list_move_tail(first, head);
235 }
236}
237
238
239
240
241
242static inline int list_is_singular(const struct list_head *head)
243{
244 return !list_empty(head) && (head->next == head->prev);
245}
246
247static inline void __list_cut_position(struct list_head *list,
248 struct list_head *head, struct list_head *entry)
249{
250 struct list_head *new_first = entry->next;
251 list->next = head->next;
252 list->next->prev = list;
253 list->prev = entry;
254 entry->next = list;
255 head->next = new_first;
256 new_first->prev = head;
257}
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273static inline void list_cut_position(struct list_head *list,
274 struct list_head *head, struct list_head *entry)
275{
276 if (list_empty(head))
277 return;
278 if (list_is_singular(head) &&
279 (head->next != entry && head != entry))
280 return;
281 if (entry == head)
282 INIT_LIST_HEAD(list);
283 else
284 __list_cut_position(list, head, entry);
285}
286
287static inline void __list_splice(const struct list_head *list,
288 struct list_head *prev,
289 struct list_head *next)
290{
291 struct list_head *first = list->next;
292 struct list_head *last = list->prev;
293
294 first->prev = prev;
295 prev->next = first;
296
297 last->next = next;
298 next->prev = last;
299}
300
301
302
303
304
305
306static inline void list_splice(const struct list_head *list,
307 struct list_head *head)
308{
309 if (!list_empty(list))
310 __list_splice(list, head, head->next);
311}
312
313
314
315
316
317
318static inline void list_splice_tail(struct list_head *list,
319 struct list_head *head)
320{
321 if (!list_empty(list))
322 __list_splice(list, head->prev, head);
323}
324
325
326
327
328
329
330
331
332static inline void list_splice_init(struct list_head *list,
333 struct list_head *head)
334{
335 if (!list_empty(list)) {
336 __list_splice(list, head, head->next);
337 INIT_LIST_HEAD(list);
338 }
339}
340
341
342
343
344
345
346
347
348
349static inline void list_splice_tail_init(struct list_head *list,
350 struct list_head *head)
351{
352 if (!list_empty(list)) {
353 __list_splice(list, head->prev, head);
354 INIT_LIST_HEAD(list);
355 }
356}
357
358
359
360
361
362
363
364#define list_entry(ptr, type, member) \
365 container_of(ptr, type, member)
366
367
368
369
370
371
372
373
374
375#define list_first_entry(ptr, type, member) \
376 list_entry((ptr)->next, type, member)
377
378
379
380
381
382
383
384
385
386#define list_last_entry(ptr, type, member) \
387 list_entry((ptr)->prev, type, member)
388
389
390
391
392
393
394
395
396
397#define list_first_entry_or_null(ptr, type, member) ({ \
398 struct list_head *head__ = (ptr); \
399 struct list_head *pos__ = READ_ONCE(head__->next); \
400 pos__ != head__ ? list_entry(pos__, type, member) : NULL; \
401})
402
403
404
405
406
407
408#define list_next_entry(pos, member) \
409 list_entry((pos)->member.next, typeof(*(pos)), member)
410
411
412
413
414
415
416#define list_prev_entry(pos, member) \
417 list_entry((pos)->member.prev, typeof(*(pos)), member)
418
419
420
421
422
423
424#define list_for_each(pos, head) \
425 for (pos = (head)->next; pos != (head); pos = pos->next)
426
427
428
429
430
431
432#define list_for_each_prev(pos, head) \
433 for (pos = (head)->prev; pos != (head); pos = pos->prev)
434
435
436
437
438
439
440
441#define list_for_each_safe(pos, n, head) \
442 for (pos = (head)->next, n = pos->next; pos != (head); \
443 pos = n, n = pos->next)
444
445
446
447
448
449
450
451#define list_for_each_prev_safe(pos, n, head) \
452 for (pos = (head)->prev, n = pos->prev; \
453 pos != (head); \
454 pos = n, n = pos->prev)
455
456
457
458
459
460
461
462#define list_for_each_entry(pos, head, member) \
463 for (pos = list_first_entry(head, typeof(*pos), member); \
464 &pos->member != (head); \
465 pos = list_next_entry(pos, member))
466
467
468
469
470
471
472
473#define list_for_each_entry_reverse(pos, head, member) \
474 for (pos = list_last_entry(head, typeof(*pos), member); \
475 &pos->member != (head); \
476 pos = list_prev_entry(pos, member))
477
478
479
480
481
482
483
484
485
486#define list_prepare_entry(pos, head, member) \
487 ((pos) ? : list_entry(head, typeof(*pos), member))
488
489
490
491
492
493
494
495
496
497
498#define list_for_each_entry_continue(pos, head, member) \
499 for (pos = list_next_entry(pos, member); \
500 &pos->member != (head); \
501 pos = list_next_entry(pos, member))
502
503
504
505
506
507
508
509
510
511
512#define list_for_each_entry_continue_reverse(pos, head, member) \
513 for (pos = list_prev_entry(pos, member); \
514 &pos->member != (head); \
515 pos = list_prev_entry(pos, member))
516
517
518
519
520
521
522
523
524
525#define list_for_each_entry_from(pos, head, member) \
526 for (; &pos->member != (head); \
527 pos = list_next_entry(pos, member))
528
529
530
531
532
533
534
535
536
537
538#define list_for_each_entry_from_reverse(pos, head, member) \
539 for (; &pos->member != (head); \
540 pos = list_prev_entry(pos, member))
541
542
543
544
545
546
547
548
549#define list_for_each_entry_safe(pos, n, head, member) \
550 for (pos = list_first_entry(head, typeof(*pos), member), \
551 n = list_next_entry(pos, member); \
552 &pos->member != (head); \
553 pos = n, n = list_next_entry(n, member))
554
555
556
557
558
559
560
561
562
563
564
565#define list_for_each_entry_safe_continue(pos, n, head, member) \
566 for (pos = list_next_entry(pos, member), \
567 n = list_next_entry(pos, member); \
568 &pos->member != (head); \
569 pos = n, n = list_next_entry(n, member))
570
571
572
573
574
575
576
577
578
579
580
581#define list_for_each_entry_safe_from(pos, n, head, member) \
582 for (n = list_next_entry(pos, member); \
583 &pos->member != (head); \
584 pos = n, n = list_next_entry(n, member))
585
586
587
588
589
590
591
592
593
594
595
596#define list_for_each_entry_safe_reverse(pos, n, head, member) \
597 for (pos = list_last_entry(head, typeof(*pos), member), \
598 n = list_prev_entry(pos, member); \
599 &pos->member != (head); \
600 pos = n, n = list_prev_entry(n, member))
601
602
603
604
605
606
607
608
609
610
611
612
613
614#define list_safe_reset_next(pos, n, member) \
615 n = list_next_entry(pos, member)
616
617
618
619
620
621
622
623
624#define HLIST_HEAD_INIT { .first = NULL }
625#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
626#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
627static inline void INIT_HLIST_NODE(struct hlist_node *h)
628{
629 h->next = NULL;
630 h->pprev = NULL;
631}
632
633static inline int hlist_unhashed(const struct hlist_node *h)
634{
635 return !h->pprev;
636}
637
638static inline int hlist_empty(const struct hlist_head *h)
639{
640 return !READ_ONCE(h->first);
641}
642
643static inline void __hlist_del(struct hlist_node *n)
644{
645 struct hlist_node *next = n->next;
646 struct hlist_node **pprev = n->pprev;
647
648 WRITE_ONCE(*pprev, next);
649 if (next)
650 next->pprev = pprev;
651}
652
653static inline void hlist_del(struct hlist_node *n)
654{
655 __hlist_del(n);
656 n->next = LIST_POISON1;
657 n->pprev = LIST_POISON2;
658}
659
660static inline void hlist_del_init(struct hlist_node *n)
661{
662 if (!hlist_unhashed(n)) {
663 __hlist_del(n);
664 INIT_HLIST_NODE(n);
665 }
666}
667
668static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
669{
670 struct hlist_node *first = h->first;
671 n->next = first;
672 if (first)
673 first->pprev = &n->next;
674 WRITE_ONCE(h->first, n);
675 n->pprev = &h->first;
676}
677
678
679static inline void hlist_add_before(struct hlist_node *n,
680 struct hlist_node *next)
681{
682 n->pprev = next->pprev;
683 n->next = next;
684 next->pprev = &n->next;
685 WRITE_ONCE(*(n->pprev), n);
686}
687
688static inline void hlist_add_behind(struct hlist_node *n,
689 struct hlist_node *prev)
690{
691 n->next = prev->next;
692 WRITE_ONCE(prev->next, n);
693 n->pprev = &prev->next;
694
695 if (n->next)
696 n->next->pprev = &n->next;
697}
698
699
700static inline void hlist_add_fake(struct hlist_node *n)
701{
702 n->pprev = &n->next;
703}
704
705static inline bool hlist_fake(struct hlist_node *h)
706{
707 return h->pprev == &h->next;
708}
709
710
711
712
713
714static inline bool
715hlist_is_singular_node(struct hlist_node *n, struct hlist_head *h)
716{
717 return !n->next && n->pprev == &h->first;
718}
719
720
721
722
723
724static inline void hlist_move_list(struct hlist_head *old,
725 struct hlist_head *new)
726{
727 new->first = old->first;
728 if (new->first)
729 new->first->pprev = &new->first;
730 old->first = NULL;
731}
732
733#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
734
735#define hlist_for_each(pos, head) \
736 for (pos = (head)->first; pos ; pos = pos->next)
737
738#define hlist_for_each_safe(pos, n, head) \
739 for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
740 pos = n)
741
742#define hlist_entry_safe(ptr, type, member) \
743 ({ typeof(ptr) ____ptr = (ptr); \
744 ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
745 })
746
747
748
749
750
751
752
753#define hlist_for_each_entry(pos, head, member) \
754 for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
755 pos; \
756 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
757
758
759
760
761
762
763#define hlist_for_each_entry_continue(pos, member) \
764 for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\
765 pos; \
766 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
767
768
769
770
771
772
773#define hlist_for_each_entry_from(pos, member) \
774 for (; pos; \
775 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
776
777
778
779
780
781
782
783
784#define hlist_for_each_entry_safe(pos, n, head, member) \
785 for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
786 pos && ({ n = pos->member.next; 1; }); \
787 pos = hlist_entry_safe(n, typeof(*pos), member))
788
789#endif
790