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_first_entry_or_null(ptr, type, member) \
373 (!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL)
374
375
376
377
378
379
380#define list_for_each(pos, head) \
381 for (pos = (head)->next; pos != (head); pos = pos->next)
382
383
384
385
386
387
388#define list_for_each_prev(pos, head) \
389 for (pos = (head)->prev; pos != (head); pos = pos->prev)
390
391
392
393
394
395
396
397#define list_for_each_safe(pos, n, head) \
398 for (pos = (head)->next, n = pos->next; pos != (head); \
399 pos = n, n = pos->next)
400
401
402
403
404
405
406
407#define list_for_each_prev_safe(pos, n, head) \
408 for (pos = (head)->prev, n = pos->prev; \
409 pos != (head); \
410 pos = n, n = pos->prev)
411
412
413
414
415
416
417
418#define list_for_each_entry(pos, head, member) \
419 for (pos = list_entry((head)->next, typeof(*pos), member); \
420 &pos->member != (head); \
421 pos = list_entry(pos->member.next, typeof(*pos), member))
422
423
424
425
426
427
428
429#define list_for_each_entry_reverse(pos, head, member) \
430 for (pos = list_entry((head)->prev, typeof(*pos), member); \
431 &pos->member != (head); \
432 pos = list_entry(pos->member.prev, typeof(*pos), member))
433
434
435
436
437
438
439
440
441
442#define list_prepare_entry(pos, head, member) \
443 ((pos) ? : list_entry(head, typeof(*pos), member))
444
445
446
447
448
449
450
451
452
453
454#define list_for_each_entry_continue(pos, head, member) \
455 for (pos = list_entry(pos->member.next, typeof(*pos), member); \
456 &pos->member != (head); \
457 pos = list_entry(pos->member.next, typeof(*pos), member))
458
459
460
461
462
463
464
465
466
467
468#define list_for_each_entry_continue_reverse(pos, head, member) \
469 for (pos = list_entry(pos->member.prev, typeof(*pos), member); \
470 &pos->member != (head); \
471 pos = list_entry(pos->member.prev, typeof(*pos), member))
472
473
474
475
476
477
478
479
480
481#define list_for_each_entry_from(pos, head, member) \
482 for (; &pos->member != (head); \
483 pos = list_entry(pos->member.next, typeof(*pos), member))
484
485
486
487
488
489
490
491
492#define list_for_each_entry_safe(pos, n, head, member) \
493 for (pos = list_entry((head)->next, typeof(*pos), member), \
494 n = list_entry(pos->member.next, typeof(*pos), member); \
495 &pos->member != (head); \
496 pos = n, n = list_entry(n->member.next, typeof(*n), member))
497
498
499
500
501
502
503
504
505
506
507
508#define list_for_each_entry_safe_continue(pos, n, head, member) \
509 for (pos = list_entry(pos->member.next, typeof(*pos), member), \
510 n = list_entry(pos->member.next, typeof(*pos), member); \
511 &pos->member != (head); \
512 pos = n, n = list_entry(n->member.next, typeof(*n), member))
513
514
515
516
517
518
519
520
521
522
523
524#define list_for_each_entry_safe_from(pos, n, head, member) \
525 for (n = list_entry(pos->member.next, typeof(*pos), member); \
526 &pos->member != (head); \
527 pos = n, n = list_entry(n->member.next, typeof(*n), member))
528
529
530
531
532
533
534
535
536
537
538
539#define list_for_each_entry_safe_reverse(pos, n, head, member) \
540 for (pos = list_entry((head)->prev, typeof(*pos), member), \
541 n = list_entry(pos->member.prev, typeof(*pos), member); \
542 &pos->member != (head); \
543 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
544
545
546
547
548
549
550
551
552
553
554
555
556
557#define list_safe_reset_next(pos, n, member) \
558 n = list_entry(pos->member.next, typeof(*pos), member)
559
560
561
562
563
564
565
566
567#define HLIST_HEAD_INIT { .first = NULL }
568#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
569#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
570static inline void INIT_HLIST_NODE(struct hlist_node *h)
571{
572 h->next = NULL;
573 h->pprev = NULL;
574}
575
576static inline int hlist_unhashed(const struct hlist_node *h)
577{
578 return !h->pprev;
579}
580
581static inline int hlist_empty(const struct hlist_head *h)
582{
583 return !h->first;
584}
585
586static inline void __hlist_del(struct hlist_node *n)
587{
588 struct hlist_node *next = n->next;
589 struct hlist_node **pprev = n->pprev;
590 *pprev = next;
591 if (next)
592 next->pprev = pprev;
593}
594
595static inline void hlist_del(struct hlist_node *n)
596{
597 __hlist_del(n);
598 n->next = LIST_POISON1;
599 n->pprev = LIST_POISON2;
600}
601
602static inline void hlist_del_init(struct hlist_node *n)
603{
604 if (!hlist_unhashed(n)) {
605 __hlist_del(n);
606 INIT_HLIST_NODE(n);
607 }
608}
609
610static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
611{
612 struct hlist_node *first = h->first;
613 n->next = first;
614 if (first)
615 first->pprev = &n->next;
616 h->first = n;
617 n->pprev = &h->first;
618}
619
620
621static inline void hlist_add_before(struct hlist_node *n,
622 struct hlist_node *next)
623{
624 n->pprev = next->pprev;
625 n->next = next;
626 next->pprev = &n->next;
627 *(n->pprev) = n;
628}
629
630static inline void hlist_add_after(struct hlist_node *n,
631 struct hlist_node *next)
632{
633 next->next = n->next;
634 n->next = next;
635 next->pprev = &n->next;
636
637 if(next->next)
638 next->next->pprev = &next->next;
639}
640
641
642static inline void hlist_add_fake(struct hlist_node *n)
643{
644 n->pprev = &n->next;
645}
646
647
648
649
650
651static inline void hlist_move_list(struct hlist_head *old,
652 struct hlist_head *new)
653{
654 new->first = old->first;
655 if (new->first)
656 new->first->pprev = &new->first;
657 old->first = NULL;
658}
659
660#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
661
662#define hlist_for_each(pos, head) \
663 for (pos = (head)->first; pos ; pos = pos->next)
664
665#define hlist_for_each_safe(pos, n, head) \
666 for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
667 pos = n)
668
669#define hlist_entry_safe(ptr, type, member) \
670 ({ typeof(ptr) ____ptr = (ptr); \
671 ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
672 })
673
674
675
676
677
678
679
680#define hlist_for_each_entry(pos, head, member) \
681 for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
682 pos; \
683 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
684
685
686
687
688
689
690#define hlist_for_each_entry_continue(pos, member) \
691 for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\
692 pos; \
693 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
694
695
696
697
698
699
700#define hlist_for_each_entry_from(pos, member) \
701 for (; pos; \
702 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
703
704
705
706
707
708
709
710
711#define hlist_for_each_entry_safe(pos, n, head, member) \
712 for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
713 pos && ({ n = pos->member.next; 1; }); \
714 pos = hlist_entry_safe(n, typeof(*pos), member))
715
716#endif
717