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