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
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 *pprev = next;
618 if (next)
619 next->pprev = pprev;
620}
621
622static inline void hlist_del(struct hlist_node *n)
623{
624 __hlist_del(n);
625 n->next = LIST_POISON1;
626 n->pprev = LIST_POISON2;
627}
628
629static inline void hlist_del_init(struct hlist_node *n)
630{
631 if (!hlist_unhashed(n)) {
632 __hlist_del(n);
633 INIT_HLIST_NODE(n);
634 }
635}
636
637static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
638{
639 struct hlist_node *first = h->first;
640 n->next = first;
641 if (first)
642 first->pprev = &n->next;
643 h->first = n;
644 n->pprev = &h->first;
645}
646
647
648static inline void hlist_add_before(struct hlist_node *n,
649 struct hlist_node *next)
650{
651 n->pprev = next->pprev;
652 n->next = next;
653 next->pprev = &n->next;
654 *(n->pprev) = n;
655}
656
657static inline void hlist_add_after(struct hlist_node *n,
658 struct hlist_node *next)
659{
660 next->next = n->next;
661 n->next = next;
662 next->pprev = &n->next;
663
664 if(next->next)
665 next->next->pprev = &next->next;
666}
667
668
669static inline void hlist_add_fake(struct hlist_node *n)
670{
671 n->pprev = &n->next;
672}
673
674
675
676
677
678static inline void hlist_move_list(struct hlist_head *old,
679 struct hlist_head *new)
680{
681 new->first = old->first;
682 if (new->first)
683 new->first->pprev = &new->first;
684 old->first = NULL;
685}
686
687#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
688
689#define hlist_for_each(pos, head) \
690 for (pos = (head)->first; pos ; pos = pos->next)
691
692#define hlist_for_each_safe(pos, n, head) \
693 for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
694 pos = n)
695
696#define hlist_entry_safe(ptr, type, member) \
697 ({ typeof(ptr) ____ptr = (ptr); \
698 ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
699 })
700
701
702
703
704
705
706
707#define hlist_for_each_entry(pos, head, member) \
708 for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
709 pos; \
710 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
711
712
713
714
715
716
717#define hlist_for_each_entry_continue(pos, member) \
718 for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\
719 pos; \
720 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
721
722
723
724
725
726
727#define hlist_for_each_entry_from(pos, member) \
728 for (; pos; \
729 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
730
731
732
733
734
735
736
737
738#define hlist_for_each_entry_safe(pos, n, head, member) \
739 for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
740 pos && ({ n = pos->member.next; 1; }); \
741 pos = hlist_entry_safe(n, typeof(*pos), member))
742
743#endif
744