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