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