btrfs-progs: make libbtrfs usable from C++
[platform/upstream/btrfs-progs.git] / list.h
1 /*
2  * Copyright (C) 2007 Oracle.  All rights reserved.
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public
6  * License v2 as published by the Free Software Foundation.
7  *
8  * This program is distributed in the hope that it will be useful,
9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
11  * General Public License for more details.
12  *
13  * You should have received a copy of the GNU General Public
14  * License along with this program; if not, write to the
15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16  * Boston, MA 021110-1307, USA.
17  */
18
19 #ifndef _LINUX_LIST_H
20 #define _LINUX_LIST_H
21
22 #define LIST_POISON1  ((struct list_head *) 0x00100100)
23 #define LIST_POISON2  ((struct list_head *) 0x00200200)
24
25 /*
26  * Simple doubly linked list implementation.
27  *
28  * Some of the internal functions ("__xxx") are useful when
29  * manipulating whole lists rather than single entries, as
30  * sometimes we already know the next/prev entries and we can
31  * generate better code by using them directly rather than
32  * using the generic single-entry routines.
33  */
34
35 struct list_head {
36         struct list_head *next, *prev;
37 };
38
39 #define LIST_HEAD_INIT(name) { &(name), &(name) }
40
41 #define LIST_HEAD(name) \
42         struct list_head name = LIST_HEAD_INIT(name)
43
44 static inline void INIT_LIST_HEAD(struct list_head *list)
45 {
46         list->next = list;
47         list->prev = list;
48 }
49
50 /*
51  * Insert a new entry between two known consecutive entries.
52  *
53  * This is only for internal list manipulation where we know
54  * the prev/next entries already!
55  */
56 #ifndef CONFIG_DEBUG_LIST
57 static inline void __list_add(struct list_head *xnew,
58                               struct list_head *prev,
59                               struct list_head *next)
60 {
61         next->prev = xnew;
62         xnew->next = next;
63         xnew->prev = prev;
64         prev->next = xnew;
65 }
66 #else
67 extern void __list_add(struct list_head *xnew,
68                               struct list_head *prev,
69                               struct list_head *next);
70 #endif
71
72 /**
73  * list_add - add a new entry
74  * @new: new entry to be added
75  * @head: list head to add it after
76  *
77  * Insert a new entry after the specified head.
78  * This is good for implementing stacks.
79  */
80 #ifndef CONFIG_DEBUG_LIST
81 static inline void list_add(struct list_head *xnew, struct list_head *head)
82 {
83         __list_add(xnew, head, head->next);
84 }
85 #else
86 extern void list_add(struct list_head *xnew, struct list_head *head);
87 #endif
88
89
90 /**
91  * list_add_tail - add a new entry
92  * @new: new entry to be added
93  * @head: list head to add it before
94  *
95  * Insert a new entry before the specified head.
96  * This is useful for implementing queues.
97  */
98 static inline void list_add_tail(struct list_head *xnew, struct list_head *head)
99 {
100         __list_add(xnew, head->prev, head);
101 }
102
103 /*
104  * Delete a list entry by making the prev/next entries
105  * point to each other.
106  *
107  * This is only for internal list manipulation where we know
108  * the prev/next entries already!
109  */
110 static inline void __list_del(struct list_head * prev, struct list_head * next)
111 {
112         next->prev = prev;
113         prev->next = next;
114 }
115
116 /**
117  * list_del - deletes entry from list.
118  * @entry: the element to delete from the list.
119  * Note: list_empty on entry does not return true after this, the entry is
120  * in an undefined state.
121  */
122 #ifndef CONFIG_DEBUG_LIST
123 static inline void list_del(struct list_head *entry)
124 {
125         __list_del(entry->prev, entry->next);
126         entry->next = LIST_POISON1;
127         entry->prev = LIST_POISON2;
128 }
129 #else
130 extern void list_del(struct list_head *entry);
131 #endif
132
133 /**
134  * list_replace - replace old entry by new one
135  * @old : the element to be replaced
136  * @new : the new element to insert
137  * Note: if 'old' was empty, it will be overwritten.
138  */
139 static inline void list_replace(struct list_head *old,
140                                 struct list_head *xnew)
141 {
142         xnew->next = old->next;
143         xnew->next->prev = xnew;
144         xnew->prev = old->prev;
145         xnew->prev->next = xnew;
146 }
147
148 static inline void list_replace_init(struct list_head *old,
149                                         struct list_head *xnew)
150 {
151         list_replace(old, xnew);
152         INIT_LIST_HEAD(old);
153 }
154 /**
155  * list_del_init - deletes entry from list and reinitialize it.
156  * @entry: the element to delete from the list.
157  */
158 static inline void list_del_init(struct list_head *entry)
159 {
160         __list_del(entry->prev, entry->next);
161         INIT_LIST_HEAD(entry);
162 }
163
164 /**
165  * list_move - delete from one list and add as another's head
166  * @list: the entry to move
167  * @head: the head that will precede our entry
168  */
169 static inline void list_move(struct list_head *list, struct list_head *head)
170 {
171         __list_del(list->prev, list->next);
172         list_add(list, head);
173 }
174
175 /**
176  * list_move_tail - delete from one list and add as another's tail
177  * @list: the entry to move
178  * @head: the head that will follow our entry
179  */
180 static inline void list_move_tail(struct list_head *list,
181                                   struct list_head *head)
182 {
183         __list_del(list->prev, list->next);
184         list_add_tail(list, head);
185 }
186
187 /**
188  * list_is_last - tests whether @list is the last entry in list @head
189  * @list: the entry to test
190  * @head: the head of the list
191  */
192 static inline int list_is_last(const struct list_head *list,
193                                 const struct list_head *head)
194 {
195         return list->next == head;
196 }
197
198 /**
199  * list_empty - tests whether a list is empty
200  * @head: the list to test.
201  */
202 static inline int list_empty(const struct list_head *head)
203 {
204         return head->next == head;
205 }
206
207 /**
208  * list_empty_careful - tests whether a list is empty and not being modified
209  * @head: the list to test
210  *
211  * Description:
212  * tests whether a list is empty _and_ checks that no other CPU might be
213  * in the process of modifying either member (next or prev)
214  *
215  * NOTE: using list_empty_careful() without synchronization
216  * can only be safe if the only activity that can happen
217  * to the list entry is list_del_init(). Eg. it cannot be used
218  * if another CPU could re-list_add() it.
219  */
220 static inline int list_empty_careful(const struct list_head *head)
221 {
222         struct list_head *next = head->next;
223         return (next == head) && (next == head->prev);
224 }
225
226 static inline void __list_splice(struct list_head *list,
227                                  struct list_head *head)
228 {
229         struct list_head *first = list->next;
230         struct list_head *last = list->prev;
231         struct list_head *at = head->next;
232
233         first->prev = head;
234         head->next = first;
235
236         last->next = at;
237         at->prev = last;
238 }
239
240 /**
241  * list_splice - join two lists
242  * @list: the new list to add.
243  * @head: the place to add it in the first list.
244  */
245 static inline void list_splice(struct list_head *list, struct list_head *head)
246 {
247         if (!list_empty(list))
248                 __list_splice(list, head);
249 }
250
251 /**
252  * list_splice_init - join two lists and reinitialise the emptied list.
253  * @list: the new list to add.
254  * @head: the place to add it in the first list.
255  *
256  * The list at @list is reinitialised
257  */
258 static inline void list_splice_init(struct list_head *list,
259                                     struct list_head *head)
260 {
261         if (!list_empty(list)) {
262                 __list_splice(list, head);
263                 INIT_LIST_HEAD(list);
264         }
265 }
266
267 /**
268  * list_entry - get the struct for this entry
269  * @ptr:        the &struct list_head pointer.
270  * @type:       the type of the struct this is embedded in.
271  * @member:     the name of the list_struct within the struct.
272  */
273 #define list_entry(ptr, type, member) \
274         container_of(ptr, type, member)
275
276 /**
277  * list_for_each        -       iterate over a list
278  * @pos:        the &struct list_head to use as a loop cursor.
279  * @head:       the head for your list.
280  */
281 #define list_for_each(pos, head) \
282         for (pos = (head)->next; pos != (head); \
283                 pos = pos->next)
284
285 /**
286  * __list_for_each      -       iterate over a list
287  * @pos:        the &struct list_head to use as a loop cursor.
288  * @head:       the head for your list.
289  *
290  * This variant differs from list_for_each() in that it's the
291  * simplest possible list iteration code, no prefetching is done.
292  * Use this for code that knows the list to be very short (empty
293  * or 1 entry) most of the time.
294  */
295 #define __list_for_each(pos, head) \
296         for (pos = (head)->next; pos != (head); pos = pos->next)
297
298 /**
299  * list_for_each_prev   -       iterate over a list backwards
300  * @pos:        the &struct list_head to use as a loop cursor.
301  * @head:       the head for your list.
302  */
303 #define list_for_each_prev(pos, head) \
304         for (pos = (head)->prev; pos != (head); \
305                 pos = pos->prev)
306
307 /**
308  * list_for_each_safe - iterate over a list safe against removal of list entry
309  * @pos:        the &struct list_head to use as a loop cursor.
310  * @n:          another &struct list_head to use as temporary storage
311  * @head:       the head for your list.
312  */
313 #define list_for_each_safe(pos, n, head) \
314         for (pos = (head)->next, n = pos->next; pos != (head); \
315                 pos = n, n = pos->next)
316
317 /**
318  * list_for_each_entry  -       iterate over list of given type
319  * @pos:        the type * to use as a loop cursor.
320  * @head:       the head for your list.
321  * @member:     the name of the list_struct within the struct.
322  */
323 #define list_for_each_entry(pos, head, member)                          \
324         for (pos = list_entry((head)->next, typeof(*pos), member);      \
325              &pos->member != (head);    \
326              pos = list_entry(pos->member.next, typeof(*pos), member))
327
328 /**
329  * list_for_each_entry_reverse - iterate backwards over list of given type.
330  * @pos:        the type * to use as a loop cursor.
331  * @head:       the head for your list.
332  * @member:     the name of the list_struct within the struct.
333  */
334 #define list_for_each_entry_reverse(pos, head, member)                  \
335         for (pos = list_entry((head)->prev, typeof(*pos), member);      \
336              &pos->member != (head);    \
337              pos = list_entry(pos->member.prev, typeof(*pos), member))
338
339 /**
340  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue
341  * @pos:        the type * to use as a start point
342  * @head:       the head of the list
343  * @member:     the name of the list_struct within the struct.
344  *
345  * Prepares a pos entry for use as a start point in list_for_each_entry_continue.
346  */
347 #define list_prepare_entry(pos, head, member) \
348         ((pos) ? : list_entry(head, typeof(*pos), member))
349
350 /**
351  * list_for_each_entry_continue - continue iteration over list of given type
352  * @pos:        the type * to use as a loop cursor.
353  * @head:       the head for your list.
354  * @member:     the name of the list_struct within the struct.
355  *
356  * Continue to iterate over list of given type, continuing after
357  * the current position.
358  */
359 #define list_for_each_entry_continue(pos, head, member)                 \
360         for (pos = list_entry(pos->member.next, typeof(*pos), member);  \
361              &pos->member != (head);    \
362              pos = list_entry(pos->member.next, typeof(*pos), member))
363
364 /**
365  * list_for_each_entry_from - iterate over list of given type from the current point
366  * @pos:        the type * to use as a loop cursor.
367  * @head:       the head for your list.
368  * @member:     the name of the list_struct within the struct.
369  *
370  * Iterate over list of given type, continuing from current position.
371  */
372 #define list_for_each_entry_from(pos, head, member)                     \
373         for (; &pos->member != (head);  \
374              pos = list_entry(pos->member.next, typeof(*pos), member))
375
376 /**
377  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
378  * @pos:        the type * to use as a loop cursor.
379  * @n:          another type * to use as temporary storage
380  * @head:       the head for your list.
381  * @member:     the name of the list_struct within the struct.
382  */
383 #define list_for_each_entry_safe(pos, n, head, member)                  \
384         for (pos = list_entry((head)->next, typeof(*pos), member),      \
385                 n = list_entry(pos->member.next, typeof(*pos), member); \
386              &pos->member != (head);                                    \
387              pos = n, n = list_entry(n->member.next, typeof(*n), member))
388
389 /**
390  * list_for_each_entry_safe_continue
391  * @pos:        the type * to use as a loop cursor.
392  * @n:          another type * to use as temporary storage
393  * @head:       the head for your list.
394  * @member:     the name of the list_struct within the struct.
395  *
396  * Iterate over list of given type, continuing after current point,
397  * safe against removal of list entry.
398  */
399 #define list_for_each_entry_safe_continue(pos, n, head, member)                 \
400         for (pos = list_entry(pos->member.next, typeof(*pos), member),          \
401                 n = list_entry(pos->member.next, typeof(*pos), member);         \
402              &pos->member != (head);                                            \
403              pos = n, n = list_entry(n->member.next, typeof(*n), member))
404
405 /**
406  * list_for_each_entry_safe_from
407  * @pos:        the type * to use as a loop cursor.
408  * @n:          another type * to use as temporary storage
409  * @head:       the head for your list.
410  * @member:     the name of the list_struct within the struct.
411  *
412  * Iterate over list of given type from current point, safe against
413  * removal of list entry.
414  */
415 #define list_for_each_entry_safe_from(pos, n, head, member)                     \
416         for (n = list_entry(pos->member.next, typeof(*pos), member);            \
417              &pos->member != (head);                                            \
418              pos = n, n = list_entry(n->member.next, typeof(*n), member))
419
420 /**
421  * list_for_each_entry_safe_reverse
422  * @pos:        the type * to use as a loop cursor.
423  * @n:          another type * to use as temporary storage
424  * @head:       the head for your list.
425  * @member:     the name of the list_struct within the struct.
426  *
427  * Iterate backwards over list of given type, safe against removal
428  * of list entry.
429  */
430 #define list_for_each_entry_safe_reverse(pos, n, head, member)          \
431         for (pos = list_entry((head)->prev, typeof(*pos), member),      \
432                 n = list_entry(pos->member.prev, typeof(*pos), member); \
433              &pos->member != (head);                                    \
434              pos = n, n = list_entry(n->member.prev, typeof(*n), member))
435
436 #endif