d167b5d7c0ac0844d9b42fab6a16d486793878c5
[linux-2.6.git] / include / linux / list.h
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/prefetch.h>
8 #include <asm/system.h>
9
10 /*
11  * Simple doubly linked list implementation.
12  *
13  * Some of the internal functions ("__xxx") are useful when
14  * manipulating whole lists rather than single entries, as
15  * sometimes we already know the next/prev entries and we can
16  * generate better code by using them directly rather than
17  * using the generic single-entry routines.
18  */
19
20 #define LIST_HEAD_INIT(name) { &(name), &(name) }
21
22 #define LIST_HEAD(name) \
23         struct list_head name = LIST_HEAD_INIT(name)
24
25 static inline void INIT_LIST_HEAD(struct list_head *list)
26 {
27         list->next = list;
28         list->prev = list;
29 }
30
31 /*
32  * Insert a new entry between two known consecutive entries.
33  *
34  * This is only for internal list manipulation where we know
35  * the prev/next entries already!
36  */
37 #ifndef CONFIG_DEBUG_LIST
38 static inline void __list_add(struct list_head *new,
39                               struct list_head *prev,
40                               struct list_head *next)
41 {
42         next->prev = new;
43         new->next = next;
44         new->prev = prev;
45         prev->next = new;
46 }
47 #else
48 extern void __list_add(struct list_head *new,
49                               struct list_head *prev,
50                               struct list_head *next);
51 #endif
52
53 /**
54  * list_add - add a new entry
55  * @new: new entry to be added
56  * @head: list head to add it after
57  *
58  * Insert a new entry after the specified head.
59  * This is good for implementing stacks.
60  */
61 static inline void list_add(struct list_head *new, struct list_head *head)
62 {
63         __list_add(new, head, head->next);
64 }
65
66
67 /**
68  * list_add_tail - add a new entry
69  * @new: new entry to be added
70  * @head: list head to add it before
71  *
72  * Insert a new entry before the specified head.
73  * This is useful for implementing queues.
74  */
75 static inline void list_add_tail(struct list_head *new, struct list_head *head)
76 {
77         __list_add(new, head->prev, head);
78 }
79
80 /*
81  * Delete a list entry by making the prev/next entries
82  * point to each other.
83  *
84  * This is only for internal list manipulation where we know
85  * the prev/next entries already!
86  */
87 static inline void __list_del(struct list_head * prev, struct list_head * next)
88 {
89         next->prev = prev;
90         prev->next = next;
91 }
92
93 /**
94  * list_del - deletes entry from list.
95  * @entry: the element to delete from the list.
96  * Note: list_empty() on entry does not return true after this, the entry is
97  * in an undefined state.
98  */
99 #ifndef CONFIG_DEBUG_LIST
100 static inline void list_del(struct list_head *entry)
101 {
102         __list_del(entry->prev, entry->next);
103         entry->next = LIST_POISON1;
104         entry->prev = LIST_POISON2;
105 }
106 #else
107 extern void list_del(struct list_head *entry);
108 #endif
109
110 /**
111  * list_replace - replace old entry by new one
112  * @old : the element to be replaced
113  * @new : the new element to insert
114  *
115  * If @old was empty, it will be overwritten.
116  */
117 static inline void list_replace(struct list_head *old,
118                                 struct list_head *new)
119 {
120         new->next = old->next;
121         new->next->prev = new;
122         new->prev = old->prev;
123         new->prev->next = new;
124 }
125
126 static inline void list_replace_init(struct list_head *old,
127                                         struct list_head *new)
128 {
129         list_replace(old, new);
130         INIT_LIST_HEAD(old);
131 }
132
133 /**
134  * list_del_init - deletes entry from list and reinitialize it.
135  * @entry: the element to delete from the list.
136  */
137 static inline void list_del_init(struct list_head *entry)
138 {
139         __list_del(entry->prev, entry->next);
140         INIT_LIST_HEAD(entry);
141 }
142
143 /**
144  * list_move - delete from one list and add as another's head
145  * @list: the entry to move
146  * @head: the head that will precede our entry
147  */
148 static inline void list_move(struct list_head *list, struct list_head *head)
149 {
150         __list_del(list->prev, list->next);
151         list_add(list, head);
152 }
153
154 /**
155  * list_move_tail - delete from one list and add as another's tail
156  * @list: the entry to move
157  * @head: the head that will follow our entry
158  */
159 static inline void list_move_tail(struct list_head *list,
160                                   struct list_head *head)
161 {
162         __list_del(list->prev, list->next);
163         list_add_tail(list, head);
164 }
165
166 /**
167  * list_is_last - tests whether @list is the last entry in list @head
168  * @list: the entry to test
169  * @head: the head of the list
170  */
171 static inline int list_is_last(const struct list_head *list,
172                                 const struct list_head *head)
173 {
174         return list->next == head;
175 }
176
177 /**
178  * list_empty - tests whether a list is empty
179  * @head: the list to test.
180  */
181 static inline int list_empty(const struct list_head *head)
182 {
183         return head->next == head;
184 }
185
186 /**
187  * list_empty_careful - tests whether a list is empty and not being modified
188  * @head: the list to test
189  *
190  * Description:
191  * tests whether a list is empty _and_ checks that no other CPU might be
192  * in the process of modifying either member (next or prev)
193  *
194  * NOTE: using list_empty_careful() without synchronization
195  * can only be safe if the only activity that can happen
196  * to the list entry is list_del_init(). Eg. it cannot be used
197  * if another CPU could re-list_add() it.
198  */
199 static inline int list_empty_careful(const struct list_head *head)
200 {
201         struct list_head *next = head->next;
202         return (next == head) && (next == head->prev);
203 }
204
205 /**
206  * list_rotate_left - rotate the list to the left
207  * @head: the head of the list
208  */
209 static inline void list_rotate_left(struct list_head *head)
210 {
211         struct list_head *first;
212
213         if (!list_empty(head)) {
214                 first = head->next;
215                 list_move_tail(first, head);
216         }
217 }
218
219 /**
220  * list_is_singular - tests whether a list has just one entry.
221  * @head: the list to test.
222  */
223 static inline int list_is_singular(const struct list_head *head)
224 {
225         return !list_empty(head) && (head->next == head->prev);
226 }
227
228 static inline void __list_cut_position(struct list_head *list,
229                 struct list_head *head, struct list_head *entry)
230 {
231         struct list_head *new_first = entry->next;
232         list->next = head->next;
233         list->next->prev = list;
234         list->prev = entry;
235         entry->next = list;
236         head->next = new_first;
237         new_first->prev = head;
238 }
239
240 /**
241  * list_cut_position - cut a list into two
242  * @list: a new list to add all removed entries
243  * @head: a list with entries
244  * @entry: an entry within head, could be the head itself
245  *      and if so we won't cut the list
246  *
247  * This helper moves the initial part of @head, up to and
248  * including @entry, from @head to @list. You should
249  * pass on @entry an element you know is on @head. @list
250  * should be an empty list or a list you do not care about
251  * losing its data.
252  *
253  */
254 static inline void list_cut_position(struct list_head *list,
255                 struct list_head *head, struct list_head *entry)
256 {
257         if (list_empty(head))
258                 return;
259         if (list_is_singular(head) &&
260                 (head->next != entry && head != entry))
261                 return;
262         if (entry == head)
263                 INIT_LIST_HEAD(list);
264         else
265                 __list_cut_position(list, head, entry);
266 }
267
268 static inline void __list_splice(const struct list_head *list,
269                                  struct list_head *prev,
270                                  struct list_head *next)
271 {
272         struct list_head *first = list->next;
273         struct list_head *last = list->prev;
274
275         first->prev = prev;
276         prev->next = first;
277
278         last->next = next;
279         next->prev = last;
280 }
281
282 /**
283  * list_splice - join two lists, this is designed for stacks
284  * @list: the new list to add.
285  * @head: the place to add it in the first list.
286  */
287 static inline void list_splice(const struct list_head *list,
288                                 struct list_head *head)
289 {
290         if (!list_empty(list))
291                 __list_splice(list, head, head->next);
292 }
293
294 /**
295  * list_splice_tail - join two lists, each list being a queue
296  * @list: the new list to add.
297  * @head: the place to add it in the first list.
298  */
299 static inline void list_splice_tail(struct list_head *list,
300                                 struct list_head *head)
301 {
302         if (!list_empty(list))
303                 __list_splice(list, head->prev, head);
304 }
305
306 /**
307  * list_splice_init - join two lists and reinitialise the emptied list.
308  * @list: the new list to add.
309  * @head: the place to add it in the first list.
310  *
311  * The list at @list is reinitialised
312  */
313 static inline void list_splice_init(struct list_head *list,
314                                     struct list_head *head)
315 {
316         if (!list_empty(list)) {
317                 __list_splice(list, head, head->next);
318                 INIT_LIST_HEAD(list);
319         }
320 }
321
322 /**
323  * list_splice_tail_init - join two lists and reinitialise the emptied list
324  * @list: the new list to add.
325  * @head: the place to add it in the first list.
326  *
327  * Each of the lists is a queue.
328  * The list at @list is reinitialised
329  */
330 static inline void list_splice_tail_init(struct list_head *list,
331                                          struct list_head *head)
332 {
333         if (!list_empty(list)) {
334                 __list_splice(list, head->prev, head);
335                 INIT_LIST_HEAD(list);
336         }
337 }
338
339 /**
340  * list_entry - get the struct for this entry
341  * @ptr:        the &struct list_head pointer.
342  * @type:       the type of the struct this is embedded in.
343  * @member:     the name of the list_struct within the struct.
344  */
345 #define list_entry(ptr, type, member) \
346         container_of(ptr, type, member)
347
348 /**
349  * list_first_entry - get the first element from a list
350  * @ptr:        the list head to take the element from.
351  * @type:       the type of the struct this is embedded in.
352  * @member:     the name of the list_struct within the struct.
353  *
354  * Note, that list is expected to be not empty.
355  */
356 #define list_first_entry(ptr, type, member) \
357         list_entry((ptr)->next, type, member)
358
359 /**
360  * list_for_each        -       iterate over a list
361  * @pos:        the &struct list_head to use as a loop cursor.
362  * @head:       the head for your list.
363  */
364 #define list_for_each(pos, head) \
365         for (pos = (head)->next; prefetch(pos->next), pos != (head); \
366                 pos = pos->next)
367
368 /**
369  * __list_for_each      -       iterate over a list
370  * @pos:        the &struct list_head to use as a loop cursor.
371  * @head:       the head for your list.
372  *
373  * This variant differs from list_for_each() in that it's the
374  * simplest possible list iteration code, no prefetching is done.
375  * Use this for code that knows the list to be very short (empty
376  * or 1 entry) most of the time.
377  */
378 #define __list_for_each(pos, head) \
379         for (pos = (head)->next; pos != (head); pos = pos->next)
380
381 /**
382  * list_for_each_prev   -       iterate over a list backwards
383  * @pos:        the &struct list_head to use as a loop cursor.
384  * @head:       the head for your list.
385  */
386 #define list_for_each_prev(pos, head) \
387         for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
388                 pos = pos->prev)
389
390 /**
391  * list_for_each_safe - iterate over a list safe against removal of list entry
392  * @pos:        the &struct list_head to use as a loop cursor.
393  * @n:          another &struct list_head to use as temporary storage
394  * @head:       the head for your list.
395  */
396 #define list_for_each_safe(pos, n, head) \
397         for (pos = (head)->next, n = pos->next; pos != (head); \
398                 pos = n, n = pos->next)
399
400 /**
401  * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
402  * @pos:        the &struct list_head to use as a loop cursor.
403  * @n:          another &struct list_head to use as temporary storage
404  * @head:       the head for your list.
405  */
406 #define list_for_each_prev_safe(pos, n, head) \
407         for (pos = (head)->prev, n = pos->prev; \
408              prefetch(pos->prev), pos != (head); \
409              pos = n, n = pos->prev)
410
411 /**
412  * list_for_each_entry  -       iterate over list of given type
413  * @pos:        the type * to use as a loop cursor.
414  * @head:       the head for your list.
415  * @member:     the name of the list_struct within the struct.
416  */
417 #define list_for_each_entry(pos, head, member)                          \
418         for (pos = list_entry((head)->next, typeof(*pos), member);      \
419              prefetch(pos->member.next), &pos->member != (head);        \
420              pos = list_entry(pos->member.next, typeof(*pos), member))
421
422 /**
423  * list_for_each_entry_reverse - iterate backwards over list of given type.
424  * @pos:        the type * to use as a loop cursor.
425  * @head:       the head for your list.
426  * @member:     the name of the list_struct within the struct.
427  */
428 #define list_for_each_entry_reverse(pos, head, member)                  \
429         for (pos = list_entry((head)->prev, typeof(*pos), member);      \
430              prefetch(pos->member.prev), &pos->member != (head);        \
431              pos = list_entry(pos->member.prev, typeof(*pos), member))
432
433 /**
434  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
435  * @pos:        the type * to use as a start point
436  * @head:       the head of the list
437  * @member:     the name of the list_struct within the struct.
438  *
439  * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
440  */
441 #define list_prepare_entry(pos, head, member) \
442         ((pos) ? : list_entry(head, typeof(*pos), member))
443
444 /**
445  * list_for_each_entry_continue - continue iteration over list of given type
446  * @pos:        the type * to use as a loop cursor.
447  * @head:       the head for your list.
448  * @member:     the name of the list_struct within the struct.
449  *
450  * Continue to iterate over list of given type, continuing after
451  * the current position.
452  */
453 #define list_for_each_entry_continue(pos, head, member)                 \
454         for (pos = list_entry(pos->member.next, typeof(*pos), member);  \
455              prefetch(pos->member.next), &pos->member != (head);        \
456              pos = list_entry(pos->member.next, typeof(*pos), member))
457
458 /**
459  * list_for_each_entry_continue_reverse - iterate backwards from the given point
460  * @pos:        the type * to use as a loop cursor.
461  * @head:       the head for your list.
462  * @member:     the name of the list_struct within the struct.
463  *
464  * Start to iterate over list of given type backwards, continuing after
465  * the current position.
466  */
467 #define list_for_each_entry_continue_reverse(pos, head, member)         \
468         for (pos = list_entry(pos->member.prev, typeof(*pos), member);  \
469              prefetch(pos->member.prev), &pos->member != (head);        \
470              pos = list_entry(pos->member.prev, typeof(*pos), member))
471
472 /**
473  * list_for_each_entry_from - iterate over list of given type from the current point
474  * @pos:        the type * to use as a loop cursor.
475  * @head:       the head for your list.
476  * @member:     the name of the list_struct within the struct.
477  *
478  * Iterate over list of given type, continuing from current position.
479  */
480 #define list_for_each_entry_from(pos, head, member)                     \
481         for (; prefetch(pos->member.next), &pos->member != (head);      \
482              pos = list_entry(pos->member.next, typeof(*pos), member))
483
484 /**
485  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
486  * @pos:        the type * to use as a loop cursor.
487  * @n:          another type * to use as temporary storage
488  * @head:       the head for your list.
489  * @member:     the name of the list_struct within the struct.
490  */
491 #define list_for_each_entry_safe(pos, n, head, member)                  \
492         for (pos = list_entry((head)->next, typeof(*pos), member),      \
493                 n = list_entry(pos->member.next, typeof(*pos), member); \
494              &pos->member != (head);                                    \
495              pos = n, n = list_entry(n->member.next, typeof(*n), member))
496
497 /**
498  * list_for_each_entry_safe_continue - continue list iteration safe against removal
499  * @pos:        the type * to use as a loop cursor.
500  * @n:          another type * to use as temporary storage
501  * @head:       the head for your list.
502  * @member:     the name of the list_struct within the struct.
503  *
504  * Iterate over list of given type, continuing after current point,
505  * safe against removal of list entry.
506  */
507 #define list_for_each_entry_safe_continue(pos, n, head, member)                 \
508         for (pos = list_entry(pos->member.next, typeof(*pos), member),          \
509                 n = list_entry(pos->member.next, typeof(*pos), member);         \
510              &pos->member != (head);                                            \
511              pos = n, n = list_entry(n->member.next, typeof(*n), member))
512
513 /**
514  * list_for_each_entry_safe_from - iterate over list from current point safe against removal
515  * @pos:        the type * to use as a loop cursor.
516  * @n:          another type * to use as temporary storage
517  * @head:       the head for your list.
518  * @member:     the name of the list_struct within the struct.
519  *
520  * Iterate over list of given type from current point, safe against
521  * removal of list entry.
522  */
523 #define list_for_each_entry_safe_from(pos, n, head, member)                     \
524         for (n = list_entry(pos->member.next, typeof(*pos), member);            \
525              &pos->member != (head);                                            \
526              pos = n, n = list_entry(n->member.next, typeof(*n), member))
527
528 /**
529  * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
530  * @pos:        the type * to use as a loop cursor.
531  * @n:          another type * to use as temporary storage
532  * @head:       the head for your list.
533  * @member:     the name of the list_struct within the struct.
534  *
535  * Iterate backwards over list of given type, safe against removal
536  * of list entry.
537  */
538 #define list_for_each_entry_safe_reverse(pos, n, head, member)          \
539         for (pos = list_entry((head)->prev, typeof(*pos), member),      \
540                 n = list_entry(pos->member.prev, typeof(*pos), member); \
541              &pos->member != (head);                                    \
542              pos = n, n = list_entry(n->member.prev, typeof(*n), member))
543
544 /**
545  * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
546  * @pos:        the loop cursor used in the list_for_each_entry_safe loop
547  * @n:          temporary storage used in list_for_each_entry_safe
548  * @member:     the name of the list_struct within the struct.
549  *
550  * list_safe_reset_next is not safe to use in general if the list may be
551  * modified concurrently (eg. the lock is dropped in the loop body). An
552  * exception to this is if the cursor element (pos) is pinned in the list,
553  * and list_safe_reset_next is called after re-taking the lock and before
554  * completing the current iteration of the loop body.
555  */
556 #define list_safe_reset_next(pos, n, member)                            \
557         n = list_entry(pos->member.next, typeof(*pos), member)
558
559 /*
560  * Double linked lists with a single pointer list head.
561  * Mostly useful for hash tables where the two pointer list head is
562  * too wasteful.
563  * You lose the ability to access the tail in O(1).
564  */
565
566 #define HLIST_HEAD_INIT { .first = NULL }
567 #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
568 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
569 static inline void INIT_HLIST_NODE(struct hlist_node *h)
570 {
571         h->next = NULL;
572         h->pprev = NULL;
573 }
574
575 static inline int hlist_unhashed(const struct hlist_node *h)
576 {
577         return !h->pprev;
578 }
579
580 static inline int hlist_empty(const struct hlist_head *h)
581 {
582         return !h->first;
583 }
584
585 static inline void __hlist_del(struct hlist_node *n)
586 {
587         struct hlist_node *next = n->next;
588         struct hlist_node **pprev = n->pprev;
589         *pprev = next;
590         if (next)
591                 next->pprev = pprev;
592 }
593
594 static inline void hlist_del(struct hlist_node *n)
595 {
596         __hlist_del(n);
597         n->next = LIST_POISON1;
598         n->pprev = LIST_POISON2;
599 }
600
601 static inline void hlist_del_init(struct hlist_node *n)
602 {
603         if (!hlist_unhashed(n)) {
604                 __hlist_del(n);
605                 INIT_HLIST_NODE(n);
606         }
607 }
608
609 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
610 {
611         struct hlist_node *first = h->first;
612         n->next = first;
613         if (first)
614                 first->pprev = &n->next;
615         h->first = n;
616         n->pprev = &h->first;
617 }
618
619 /* next must be != NULL */
620 static inline void hlist_add_before(struct hlist_node *n,
621                                         struct hlist_node *next)
622 {
623         n->pprev = next->pprev;
624         n->next = next;
625         next->pprev = &n->next;
626         *(n->pprev) = n;
627 }
628
629 static inline void hlist_add_after(struct hlist_node *n,
630                                         struct hlist_node *next)
631 {
632         next->next = n->next;
633         n->next = next;
634         next->pprev = &n->next;
635
636         if(next->next)
637                 next->next->pprev  = &next->next;
638 }
639
640 /*
641  * Move a list from one list head to another. Fixup the pprev
642  * reference of the first entry if it exists.
643  */
644 static inline void hlist_move_list(struct hlist_head *old,
645                                    struct hlist_head *new)
646 {
647         new->first = old->first;
648         if (new->first)
649                 new->first->pprev = &new->first;
650         old->first = NULL;
651 }
652
653 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
654
655 #define hlist_for_each(pos, head) \
656         for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
657              pos = pos->next)
658
659 #define hlist_for_each_safe(pos, n, head) \
660         for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
661              pos = n)
662
663 /**
664  * hlist_for_each_entry - iterate over list of given type
665  * @tpos:       the type * to use as a loop cursor.
666  * @pos:        the &struct hlist_node to use as a loop cursor.
667  * @head:       the head for your list.
668  * @member:     the name of the hlist_node within the struct.
669  */
670 #define hlist_for_each_entry(tpos, pos, head, member)                    \
671         for (pos = (head)->first;                                        \
672              pos && ({ prefetch(pos->next); 1;}) &&                      \
673                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
674              pos = pos->next)
675
676 /**
677  * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
678  * @tpos:       the type * to use as a loop cursor.
679  * @pos:        the &struct hlist_node to use as a loop cursor.
680  * @member:     the name of the hlist_node within the struct.
681  */
682 #define hlist_for_each_entry_continue(tpos, pos, member)                 \
683         for (pos = (pos)->next;                                          \
684              pos && ({ prefetch(pos->next); 1;}) &&                      \
685                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
686              pos = pos->next)
687
688 /**
689  * hlist_for_each_entry_from - iterate over a hlist continuing from current point
690  * @tpos:       the type * to use as a loop cursor.
691  * @pos:        the &struct hlist_node to use as a loop cursor.
692  * @member:     the name of the hlist_node within the struct.
693  */
694 #define hlist_for_each_entry_from(tpos, pos, member)                     \
695         for (; pos && ({ prefetch(pos->next); 1;}) &&                    \
696                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
697              pos = pos->next)
698
699 /**
700  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
701  * @tpos:       the type * to use as a loop cursor.
702  * @pos:        the &struct hlist_node to use as a loop cursor.
703  * @n:          another &struct hlist_node to use as temporary storage
704  * @head:       the head for your list.
705  * @member:     the name of the hlist_node within the struct.
706  */
707 #define hlist_for_each_entry_safe(tpos, pos, n, head, member)            \
708         for (pos = (head)->first;                                        \
709              pos && ({ n = pos->next; 1; }) &&                           \
710                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
711              pos = n)
712
713 #endif