~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/include/linux/list.h

Version: ~ [ linux-5.3 ] ~ [ linux-5.2.15 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.73 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.144 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.193 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.193 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.73 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 #ifndef _LINUX_LIST_H
  2 #define _LINUX_LIST_H
  3 
  4 #ifdef __KERNEL__
  5 
  6 #include <linux/stddef.h>
  7 #include <linux/prefetch.h>
  8 #include <asm/system.h>
  9 
 10 /*
 11  * These are non-NULL pointers that will result in page faults
 12  * under normal circumstances, used to verify that nobody uses
 13  * non-initialized list entries.
 14  */
 15 #define LIST_POISON1  ((void *) 0x00100100)
 16 #define LIST_POISON2  ((void *) 0x00200200)
 17 
 18 /*
 19  * Simple doubly linked list implementation.
 20  *
 21  * Some of the internal functions ("__xxx") are useful when
 22  * manipulating whole lists rather than single entries, as
 23  * sometimes we already know the next/prev entries and we can
 24  * generate better code by using them directly rather than
 25  * using the generic single-entry routines.
 26  */
 27 
 28 struct list_head {
 29         struct list_head *next, *prev;
 30 };
 31 
 32 #define LIST_HEAD_INIT(name) { &(name), &(name) }
 33 
 34 #define LIST_HEAD(name) \
 35         struct list_head name = LIST_HEAD_INIT(name)
 36 
 37 #define INIT_LIST_HEAD(ptr) do { \
 38         (ptr)->next = (ptr); (ptr)->prev = (ptr); \
 39 } while (0)
 40 
 41 /*
 42  * Insert a new entry between two known consecutive entries. 
 43  *
 44  * This is only for internal list manipulation where we know
 45  * the prev/next entries already!
 46  */
 47 static inline void __list_add(struct list_head *new,
 48                               struct list_head *prev,
 49                               struct list_head *next)
 50 {
 51         next->prev = new;
 52         new->next = next;
 53         new->prev = prev;
 54         prev->next = new;
 55 }
 56 
 57 /**
 58  * list_add - add a new entry
 59  * @new: new entry to be added
 60  * @head: list head to add it after
 61  *
 62  * Insert a new entry after the specified head.
 63  * This is good for implementing stacks.
 64  */
 65 static inline void list_add(struct list_head *new, struct list_head *head)
 66 {
 67         __list_add(new, head, head->next);
 68 }
 69 
 70 /**
 71  * list_add_tail - add a new entry
 72  * @new: new entry to be added
 73  * @head: list head to add it before
 74  *
 75  * Insert a new entry before the specified head.
 76  * This is useful for implementing queues.
 77  */
 78 static inline void list_add_tail(struct list_head *new, struct list_head *head)
 79 {
 80         __list_add(new, head->prev, head);
 81 }
 82 
 83 /*
 84  * Insert a new entry between two known consecutive entries. 
 85  *
 86  * This is only for internal list manipulation where we know
 87  * the prev/next entries already!
 88  */
 89 static __inline__ void __list_add_rcu(struct list_head * new,
 90         struct list_head * prev,
 91         struct list_head * next)
 92 {
 93         new->next = next;
 94         new->prev = prev;
 95         smp_wmb();
 96         next->prev = new;
 97         prev->next = new;
 98 }
 99 
100 /**
101  * list_add_rcu - add a new entry to rcu-protected list
102  * @new: new entry to be added
103  * @head: list head to add it after
104  *
105  * Insert a new entry after the specified head.
106  * This is good for implementing stacks.
107  */
108 static __inline__ void list_add_rcu(struct list_head *new, struct list_head *head)
109 {
110         __list_add_rcu(new, head, head->next);
111 }
112 
113 /**
114  * list_add_tail_rcu - add a new entry to rcu-protected list
115  * @new: new entry to be added
116  * @head: list head to add it before
117  *
118  * Insert a new entry before the specified head.
119  * This is useful for implementing queues.
120  */
121 static __inline__ void list_add_tail_rcu(struct list_head *new, struct list_head *head)
122 {
123         __list_add_rcu(new, head->prev, head);
124 }
125 
126 /*
127  * Delete a list entry by making the prev/next entries
128  * point to each other.
129  *
130  * This is only for internal list manipulation where we know
131  * the prev/next entries already!
132  */
133 static inline void __list_del(struct list_head * prev, struct list_head * next)
134 {
135         next->prev = prev;
136         prev->next = next;
137 }
138 
139 /**
140  * list_del - deletes entry from list.
141  * @entry: the element to delete from the list.
142  * Note: list_empty on entry does not return true after this, the entry is
143  * in an undefined state.
144  */
145 static inline void list_del(struct list_head *entry)
146 {
147         __list_del(entry->prev, entry->next);
148         entry->next = LIST_POISON1;
149         entry->prev = LIST_POISON2;
150 }
151 
152 /**
153  * list_del_rcu - deletes entry from list without re-initialization
154  * @entry: the element to delete from the list.
155  *
156  * Note: list_empty on entry does not return true after this, 
157  * the entry is in an undefined state. It is useful for RCU based
158  * lockfree traversal.
159  *
160  * In particular, it means that we can not poison the forward 
161  * pointers that may still be used for walking the list.
162  */
163 static inline void list_del_rcu(struct list_head *entry)
164 {
165         __list_del(entry->prev, entry->next);
166         entry->prev = LIST_POISON2;
167 }
168 
169 /**
170  * list_del_init - deletes entry from list and reinitialize it.
171  * @entry: the element to delete from the list.
172  */
173 static inline void list_del_init(struct list_head *entry)
174 {
175         __list_del(entry->prev, entry->next);
176         INIT_LIST_HEAD(entry); 
177 }
178 
179 /**
180  * list_move - delete from one list and add as another's head
181  * @list: the entry to move
182  * @head: the head that will precede our entry
183  */
184 static inline void list_move(struct list_head *list, struct list_head *head)
185 {
186         __list_del(list->prev, list->next);
187         list_add(list, head);
188 }
189 
190 /**
191  * list_move_tail - delete from one list and add as another's tail
192  * @list: the entry to move
193  * @head: the head that will follow our entry
194  */
195 static inline void list_move_tail(struct list_head *list,
196                                   struct list_head *head)
197 {
198         __list_del(list->prev, list->next);
199         list_add_tail(list, head);
200 }
201 
202 /**
203  * list_empty - tests whether a list is empty
204  * @head: the list to test.
205  */
206 static inline int list_empty(const struct list_head *head)
207 {
208         return head->next == head;
209 }
210 
211 /**
212  * list_empty_careful - tests whether a list is
213  * empty _and_ checks that no other CPU might be
214  * in the process of still modifying either member
215  * @head: the list to test.
216  */
217 static inline int list_empty_careful(const struct list_head *head)
218 {
219         struct list_head *next = head->next;
220         return (next == head) && (next == head->prev);
221 }
222 
223 static inline void __list_splice(struct list_head *list,
224                                  struct list_head *head)
225 {
226         struct list_head *first = list->next;
227         struct list_head *last = list->prev;
228         struct list_head *at = head->next;
229 
230         first->prev = head;
231         head->next = first;
232 
233         last->next = at;
234         at->prev = last;
235 }
236 
237 /**
238  * list_splice - join two lists
239  * @list: the new list to add.
240  * @head: the place to add it in the first list.
241  */
242 static inline void list_splice(struct list_head *list, struct list_head *head)
243 {
244         if (!list_empty(list))
245                 __list_splice(list, head);
246 }
247 
248 /**
249  * list_splice_init - join two lists and reinitialise the emptied list.
250  * @list: the new list to add.
251  * @head: the place to add it in the first list.
252  *
253  * The list at @list is reinitialised
254  */
255 static inline void list_splice_init(struct list_head *list,
256                                     struct list_head *head)
257 {
258         if (!list_empty(list)) {
259                 __list_splice(list, head);
260                 INIT_LIST_HEAD(list);
261         }
262 }
263 
264 /**
265  * list_entry - get the struct for this entry
266  * @ptr:        the &struct list_head pointer.
267  * @type:       the type of the struct this is embedded in.
268  * @member:     the name of the list_struct within the struct.
269  */
270 #define list_entry(ptr, type, member) \
271         container_of(ptr, type, member)
272 
273 /**
274  * list_for_each        -       iterate over a list
275  * @pos:        the &struct list_head to use as a loop counter.
276  * @head:       the head for your list.
277  */
278 #define list_for_each(pos, head) \
279         for (pos = (head)->next, prefetch(pos->next); pos != (head); \
280                 pos = pos->next, prefetch(pos->next))
281 
282 /**
283  * __list_for_each      -       iterate over a list
284  * @pos:        the &struct list_head to use as a loop counter.
285  * @head:       the head for your list.
286  *
287  * This variant differs from list_for_each() in that it's the
288  * simplest possible list iteration code, no prefetching is done.
289  * Use this for code that knows the list to be very short (empty
290  * or 1 entry) most of the time.
291  */
292 #define __list_for_each(pos, head) \
293         for (pos = (head)->next; pos != (head); pos = pos->next)
294 
295 /**
296  * list_for_each_prev   -       iterate over a list backwards
297  * @pos:        the &struct list_head to use as a loop counter.
298  * @head:       the head for your list.
299  */
300 #define list_for_each_prev(pos, head) \
301         for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \
302                 pos = pos->prev, prefetch(pos->prev))
303                 
304 /**
305  * list_for_each_safe   -       iterate over a list safe against removal of list entry
306  * @pos:        the &struct list_head to use as a loop counter.
307  * @n:          another &struct list_head to use as temporary storage
308  * @head:       the head for your list.
309  */
310 #define list_for_each_safe(pos, n, head) \
311         for (pos = (head)->next, n = pos->next; pos != (head); \
312                 pos = n, n = pos->next)
313 
314 /**
315  * list_for_each_entry  -       iterate over list of given type
316  * @pos:        the type * to use as a loop counter.
317  * @head:       the head for your list.
318  * @member:     the name of the list_struct within the struct.
319  */
320 #define list_for_each_entry(pos, head, member)                          \
321         for (pos = list_entry((head)->next, typeof(*pos), member),      \
322                      prefetch(pos->member.next);                        \
323              &pos->member != (head);                                    \
324              pos = list_entry(pos->member.next, typeof(*pos), member),  \
325                      prefetch(pos->member.next))
326 
327 /**
328  * list_for_each_entry_reverse - iterate backwards over list of given type.
329  * @pos:        the type * to use as a loop counter.
330  * @head:       the head for your list.
331  * @member:     the name of the list_struct within the struct.
332  */
333 #define list_for_each_entry_reverse(pos, head, member)                  \
334         for (pos = list_entry((head)->prev, typeof(*pos), member),      \
335                      prefetch(pos->member.prev);                        \
336              &pos->member != (head);                                    \
337              pos = list_entry(pos->member.prev, typeof(*pos), member),  \
338                      prefetch(pos->member.prev))
339 
340 /**
341  * list_for_each_entry_continue -       iterate over list of given type
342  *                      continuing after existing point
343  * @pos:        the type * to use as a loop counter.
344  * @head:       the head for your list.
345  * @member:     the name of the list_struct within the struct.
346  */
347 #define list_for_each_entry_continue(pos, head, member)                 \
348         for (pos = list_entry(pos->member.next, typeof(*pos), member),  \
349                      prefetch(pos->member.next);                        \
350              &pos->member != (head);                                    \
351              pos = list_entry(pos->member.next, typeof(*pos), member),  \
352                      prefetch(pos->member.next))
353 
354 /**
355  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
356  * @pos:        the type * to use as a loop counter.
357  * @n:          another type * to use as temporary storage
358  * @head:       the head for your list.
359  * @member:     the name of the list_struct within the struct.
360  */
361 #define list_for_each_entry_safe(pos, n, head, member)                  \
362         for (pos = list_entry((head)->next, typeof(*pos), member),      \
363                 n = list_entry(pos->member.next, typeof(*pos), member); \
364              &pos->member != (head);                                    \
365              pos = n, n = list_entry(n->member.next, typeof(*n), member))
366 
367 /**
368  * list_for_each_rcu    -       iterate over an rcu-protected list
369  * @pos:        the &struct list_head to use as a loop counter.
370  * @head:       the head for your list.
371  */
372 #define list_for_each_rcu(pos, head) \
373         for (pos = (head)->next, prefetch(pos->next); pos != (head); \
374                 pos = pos->next, ({ smp_read_barrier_depends(); 0;}), prefetch(pos->next))
375                 
376 #define __list_for_each_rcu(pos, head) \
377         for (pos = (head)->next; pos != (head); \
378                 pos = pos->next, ({ smp_read_barrier_depends(); 0;}))
379                 
380 /**
381  * list_for_each_safe_rcu       -       iterate over an rcu-protected list safe
382  *                                      against removal of list entry
383  * @pos:        the &struct list_head to use as a loop counter.
384  * @n:          another &struct list_head to use as temporary storage
385  * @head:       the head for your list.
386  */
387 #define list_for_each_safe_rcu(pos, n, head) \
388         for (pos = (head)->next, n = pos->next; pos != (head); \
389                 pos = n, ({ smp_read_barrier_depends(); 0;}), n = pos->next)
390 
391 /**
392  * list_for_each_entry_rcu      -       iterate over rcu list of given type
393  * @pos:        the type * to use as a loop counter.
394  * @head:       the head for your list.
395  * @member:     the name of the list_struct within the struct.
396  */
397 #define list_for_each_entry_rcu(pos, head, member)                      \
398         for (pos = list_entry((head)->next, typeof(*pos), member),      \
399                      prefetch(pos->member.next);                        \
400              &pos->member != (head);                                    \
401              pos = list_entry(pos->member.next, typeof(*pos), member),  \
402                      ({ smp_read_barrier_depends(); 0;}),               \
403                      prefetch(pos->member.next))
404 
405 
406 /**
407  * list_for_each_continue_rcu   -       iterate over an rcu-protected list 
408  *                      continuing after existing point.
409  * @pos:        the &struct list_head to use as a loop counter.
410  * @head:       the head for your list.
411  */
412 #define list_for_each_continue_rcu(pos, head) \
413         for ((pos) = (pos)->next, prefetch((pos)->next); (pos) != (head); \
414                 (pos) = (pos)->next, ({ smp_read_barrier_depends(); 0;}), prefetch((pos)->next))
415 
416 /* 
417  * Double linked lists with a single pointer list head. 
418  * Mostly useful for hash tables where the two pointer list head is 
419  * too wasteful.
420  * You lose the ability to access the tail in O(1).
421  */ 
422 
423 struct hlist_head { 
424         struct hlist_node *first; 
425 }; 
426 
427 struct hlist_node { 
428         struct hlist_node *next, **pprev; 
429 }; 
430 
431 #define HLIST_HEAD_INIT { .first = NULL } 
432 #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
433 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL) 
434 #define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)
435 
436 static __inline__ int hlist_unhashed(const struct hlist_node *h) 
437 { 
438         return !h->pprev;
439 } 
440 
441 static __inline__ int hlist_empty(const struct hlist_head *h) 
442 { 
443         return !h->first;
444 } 
445 
446 static __inline__ void __hlist_del(struct hlist_node *n) 
447 {
448         struct hlist_node *next = n->next;
449         struct hlist_node **pprev = n->pprev;
450         *pprev = next;  
451         if (next) 
452                 next->pprev = pprev;
453 }  
454 
455 static __inline__ void hlist_del(struct hlist_node *n)
456 {
457         __hlist_del(n);
458         n->next = LIST_POISON1;
459         n->pprev = LIST_POISON2;
460 }
461 
462 /**
463  * hlist_del_rcu - deletes entry from hash list without re-initialization
464  * @n: the element to delete from the hash list.
465  *
466  * Note: list_unhashed() on entry does not return true after this, 
467  * the entry is in an undefined state. It is useful for RCU based
468  * lockfree traversal.
469  *
470  * In particular, it means that we can not poison the forward
471  * pointers that may still be used for walking the hash list.
472  */
473 static inline void hlist_del_rcu(struct hlist_node *n)
474 {
475         __hlist_del(n);
476         n->pprev = LIST_POISON2;
477 }
478 
479 static __inline__ void hlist_del_init(struct hlist_node *n) 
480 {
481         if (n->pprev)  {
482                 __hlist_del(n);
483                 INIT_HLIST_NODE(n);
484         }
485 }  
486 
487 #define hlist_del_rcu_init hlist_del_init
488 
489 static __inline__ void hlist_add_head(struct hlist_node *n, struct hlist_head *h) 
490 { 
491         struct hlist_node *first = h->first;
492         n->next = first; 
493         if (first) 
494                 first->pprev = &n->next;
495         h->first = n; 
496         n->pprev = &h->first; 
497 } 
498 
499 static __inline__ void hlist_add_head_rcu(struct hlist_node *n, struct hlist_head *h) 
500 { 
501         struct hlist_node *first = h->first;
502         n->next = first;
503         n->pprev = &h->first; 
504         smp_wmb();
505         if (first) 
506                 first->pprev = &n->next;
507         h->first = n; 
508 } 
509 
510 /* next must be != NULL */
511 static __inline__ void hlist_add_before(struct hlist_node *n, struct hlist_node *next)
512 {
513         n->pprev = next->pprev;
514         n->next = next; 
515         next->pprev = &n->next; 
516         *(n->pprev) = n;
517 }
518 
519 static __inline__ void hlist_add_after(struct hlist_node *n,
520                                        struct hlist_node *next)
521 {
522         next->next      = n->next;
523         *(next->pprev)  = n;
524         n->next         = next;
525 }
526 
527 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
528 
529 /* Cannot easily do prefetch unfortunately */
530 #define hlist_for_each(pos, head) \
531         for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
532              pos = pos->next) 
533 
534 #define hlist_for_each_safe(pos, n, head) \
535         for (pos = (head)->first; n = pos ? pos->next : 0, pos; \
536              pos = n)
537 
538 /**
539  * hlist_for_each_entry - iterate over list of given type
540  * @tpos:       the type * to use as a loop counter.
541  * @pos:        the &struct hlist_node to use as a loop counter.
542  * @head:       the head for your list.
543  * @member:     the name of the hlist_node within the struct.
544  */
545 #define hlist_for_each_entry(tpos, pos, head, member)                    \
546         for (pos = (head)->first;                                        \
547              pos && ({ prefetch(pos->next); 1;}) &&                      \
548                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
549              pos = pos->next)
550 
551 /**
552  * hlist_for_each_entry_continue - iterate over a hlist continuing after existing point
553  * @tpos:       the type * to use as a loop counter.
554  * @pos:        the &struct hlist_node to use as a loop counter.
555  * @member:     the name of the hlist_node within the struct.
556  */
557 #define hlist_for_each_entry_continue(tpos, pos, member)                 \
558         for (pos = (pos)->next;                                          \
559              pos && ({ prefetch(pos->next); 1;}) &&                      \
560                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
561              pos = pos->next)
562 
563 /**
564  * hlist_for_each_entry_from - iterate over a hlist continuing from existing point
565  * @tpos:       the type * to use as a loop counter.
566  * @pos:        the &struct hlist_node to use as a loop counter.
567  * @member:     the name of the hlist_node within the struct.
568  */
569 #define hlist_for_each_entry_from(tpos, pos, member)                     \
570         for (; pos && ({ prefetch(pos->next); 1;}) &&                    \
571                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
572              pos = pos->next)
573 
574 /**
575  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
576  * @tpos:       the type * to use as a loop counter.
577  * @pos:        the &struct hlist_node to use as a loop counter.
578  * @n:          another &struct hlist_node to use as temporary storage
579  * @head:       the head for your list.
580  * @member:     the name of the hlist_node within the struct.
581  */
582 #define hlist_for_each_entry_safe(tpos, pos, n, head, member)            \
583         for (pos = (head)->first;                                        \
584              pos && ({ n = pos->next; 1; }) &&                           \
585                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
586              pos = n)
587 #else
588 #warning "don't include kernel headers in userspace"
589 #endif /* __KERNEL__ */
590 #endif
591 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp