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
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 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
176
177
178
179
180static inline void list_bulk_move_tail(struct list_head *head,
181 struct list_head *first,
182 struct list_head *last)
183{
184 first->prev->next = last->next;
185 last->next->prev = first->prev;
186
187 head->prev->next = first;
188 first->prev = head->prev;
189
190 last->next = head;
191 head->prev = last;
192}
193
194
195
196
197
198
199static inline int list_is_last(const struct list_head *list,
200 const struct list_head *head)
201{
202 return list->next == head;
203}
204
205
206
207
208
209static inline int list_empty(const struct list_head *head)
210{
211 return head->next == head;
212}
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227static inline int list_empty_careful(const struct list_head *head)
228{
229 struct list_head *next = head->next;
230 return (next == head) && (next == head->prev);
231}
232
233
234
235
236
237static inline void list_rotate_left(struct list_head *head)
238{
239 struct list_head *first;
240
241 if (!list_empty(head)) {
242 first = head->next;
243 list_move_tail(first, head);
244 }
245}
246
247
248
249
250
251static inline int list_is_singular(const struct list_head *head)
252{
253 return !list_empty(head) && (head->next == head->prev);
254}
255
256static inline void __list_cut_position(struct list_head *list,
257 struct list_head *head, struct list_head *entry)
258{
259 struct list_head *new_first = entry->next;
260 list->next = head->next;
261 list->next->prev = list;
262 list->prev = entry;
263 entry->next = list;
264 head->next = new_first;
265 new_first->prev = head;
266}
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282static inline void list_cut_position(struct list_head *list,
283 struct list_head *head, struct list_head *entry)
284{
285 if (list_empty(head))
286 return;
287 if (list_is_singular(head) &&
288 (head->next != entry && head != entry))
289 return;
290 if (entry == head)
291 INIT_LIST_HEAD(list);
292 else
293 __list_cut_position(list, head, entry);
294}
295
296static inline void __list_splice(const struct list_head *list,
297 struct list_head *prev,
298 struct list_head *next)
299{
300 struct list_head *first = list->next;
301 struct list_head *last = list->prev;
302
303 first->prev = prev;
304 prev->next = first;
305
306 last->next = next;
307 next->prev = last;
308}
309
310
311
312
313
314
315static inline void list_splice(const struct list_head *list,
316 struct list_head *head)
317{
318 if (!list_empty(list))
319 __list_splice(list, head, head->next);
320}
321
322
323
324
325
326
327static inline void list_splice_tail(struct list_head *list,
328 struct list_head *head)
329{
330 if (!list_empty(list))
331 __list_splice(list, head->prev, head);
332}
333
334
335
336
337
338
339
340
341static inline void list_splice_init(struct list_head *list,
342 struct list_head *head)
343{
344 if (!list_empty(list)) {
345 __list_splice(list, head, head->next);
346 INIT_LIST_HEAD(list);
347 }
348}
349
350
351
352
353
354
355
356
357
358static inline void list_splice_tail_init(struct list_head *list,
359 struct list_head *head)
360{
361 if (!list_empty(list)) {
362 __list_splice(list, head->prev, head);
363 INIT_LIST_HEAD(list);
364 }
365}
366
367
368
369
370
371
372
373#define list_entry(ptr, type, member) \
374 container_of(ptr, type, member)
375
376
377
378
379
380
381
382
383
384#define list_first_entry(ptr, type, member) \
385 list_entry((ptr)->next, type, member)
386
387
388
389
390
391
392
393
394
395#define list_last_entry(ptr, type, member) \
396 list_entry((ptr)->prev, type, member)
397
398
399
400
401
402
403
404
405
406#define list_first_entry_or_null(ptr, type, member) \
407 (!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL)
408
409
410
411
412
413
414#define list_next_entry(pos, member) \
415 list_entry((pos)->member.next, typeof(*(pos)), member)
416
417
418
419
420
421
422#define list_prev_entry(pos, member) \
423 list_entry((pos)->member.prev, typeof(*(pos)), member)
424
425
426
427
428
429
430#define list_for_each(pos, head) \
431 for (pos = (head)->next; pos != (head); pos = pos->next)
432
433
434
435
436
437
438
439
440
441#define __list_for_each(pos, head) \
442 for (pos = (head)->next; pos != (head); pos = pos->next)
443
444
445
446
447
448
449#define list_for_each_prev(pos, head) \
450 for (pos = (head)->prev; pos != (head); pos = pos->prev)
451
452
453
454
455
456
457
458#define list_for_each_safe(pos, n, head) \
459 for (pos = (head)->next, n = pos->next; pos != (head); \
460 pos = n, n = pos->next)
461
462
463
464
465
466
467
468#define list_for_each_prev_safe(pos, n, head) \
469 for (pos = (head)->prev, n = pos->prev; \
470 pos != (head); \
471 pos = n, n = pos->prev)
472
473
474
475
476
477
478
479#define list_for_each_entry(pos, head, member) \
480 for (pos = list_entry((head)->next, typeof(*pos), member); \
481 &pos->member != (head); \
482 pos = list_entry(pos->member.next, typeof(*pos), member))
483
484
485
486
487
488
489
490#define list_for_each_entry_reverse(pos, head, member) \
491 for (pos = list_entry((head)->prev, typeof(*pos), member); \
492 &pos->member != (head); \
493 pos = list_entry(pos->member.prev, typeof(*pos), member))
494
495
496
497
498
499
500
501
502
503#define list_prepare_entry(pos, head, member) \
504 ((pos) ? : list_entry(head, typeof(*pos), member))
505
506
507
508
509
510
511
512
513
514
515#define list_for_each_entry_continue(pos, head, member) \
516 for (pos = list_entry(pos->member.next, typeof(*pos), member); \
517 &pos->member != (head); \
518 pos = list_entry(pos->member.next, typeof(*pos), member))
519
520
521
522
523
524
525
526
527
528
529#define list_for_each_entry_continue_reverse(pos, head, member) \
530 for (pos = list_entry(pos->member.prev, typeof(*pos), member); \
531 &pos->member != (head); \
532 pos = list_entry(pos->member.prev, typeof(*pos), member))
533
534
535
536
537
538
539
540
541
542#define list_for_each_entry_from(pos, head, member) \
543 for (; &pos->member != (head); \
544 pos = list_entry(pos->member.next, typeof(*pos), member))
545
546
547
548
549
550
551
552
553
554
555#define list_for_each_entry_from_reverse(pos, head, member) \
556 for (; &pos->member != (head); \
557 pos = list_prev_entry(pos, member))
558
559
560
561
562
563
564
565
566#define list_for_each_entry_safe(pos, n, head, member) \
567 for (pos = list_entry((head)->next, typeof(*pos), member), \
568 n = list_entry(pos->member.next, typeof(*pos), member); \
569 &pos->member != (head); \
570 pos = n, n = list_entry(n->member.next, typeof(*n), member))
571
572
573
574
575
576
577
578
579
580
581
582#define list_for_each_entry_safe_continue(pos, n, head, member) \
583 for (pos = list_entry(pos->member.next, typeof(*pos), member), \
584 n = list_entry(pos->member.next, typeof(*pos), member); \
585 &pos->member != (head); \
586 pos = n, n = list_entry(n->member.next, typeof(*n), member))
587
588
589
590
591
592
593
594
595
596
597
598#define list_for_each_entry_safe_from(pos, n, head, member) \
599 for (n = list_entry(pos->member.next, typeof(*pos), member); \
600 &pos->member != (head); \
601 pos = n, n = list_entry(n->member.next, typeof(*n), member))
602
603
604
605
606
607
608
609
610
611
612
613#define list_for_each_entry_safe_reverse(pos, n, head, member) \
614 for (pos = list_entry((head)->prev, typeof(*pos), member), \
615 n = list_entry(pos->member.prev, typeof(*pos), member); \
616 &pos->member != (head); \
617 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
618
619
620
621
622
623
624
625
626
627
628
629
630
631#define list_safe_reset_next(pos, n, member) \
632 n = list_entry(pos->member.next, typeof(*pos), member)
633
634
635
636
637
638
639
640
641#define HLIST_HEAD_INIT { .first = NULL }
642#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
643#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
644static inline void INIT_HLIST_NODE(struct hlist_node *h)
645{
646 h->next = NULL;
647 h->pprev = NULL;
648}
649
650static inline int hlist_unhashed(const struct hlist_node *h)
651{
652 return !h->pprev;
653}
654
655static inline int hlist_empty(const struct hlist_head *h)
656{
657 return !h->first;
658}
659
660static inline void __hlist_del(struct hlist_node *n)
661{
662 struct hlist_node *next = n->next;
663 struct hlist_node **pprev = n->pprev;
664 *pprev = next;
665 if (next)
666 next->pprev = pprev;
667}
668
669static inline void hlist_del(struct hlist_node *n)
670{
671 __hlist_del(n);
672 n->next = LIST_POISON1;
673 n->pprev = LIST_POISON2;
674}
675
676static inline void hlist_del_init(struct hlist_node *n)
677{
678 if (!hlist_unhashed(n)) {
679 __hlist_del(n);
680 INIT_HLIST_NODE(n);
681 }
682}
683
684static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
685{
686 struct hlist_node *first = h->first;
687 n->next = first;
688 if (first)
689 first->pprev = &n->next;
690 h->first = n;
691 n->pprev = &h->first;
692}
693
694
695static inline void hlist_add_before(struct hlist_node *n,
696 struct hlist_node *next)
697{
698 n->pprev = next->pprev;
699 n->next = next;
700 next->pprev = &n->next;
701 *(n->pprev) = n;
702}
703
704static inline void hlist_add_behind(struct hlist_node *n,
705 struct hlist_node *prev)
706{
707 n->next = prev->next;
708 prev->next = n;
709 n->pprev = &prev->next;
710
711 if (n->next)
712 n->next->pprev = &n->next;
713}
714
715
716static inline void hlist_add_fake(struct hlist_node *n)
717{
718 n->pprev = &n->next;
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