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