Whamcloud - gitweb
b=20500
[fs/lustre-release.git] / libcfs / include / libcfs / list.h
1 #ifndef __LIBCFS_LIST_H__
2 #define __LIBCFS_LIST_H__
3
4 #if defined (__linux__) && defined(__KERNEL__)
5
6 #include <linux/list.h>
7
8 #define CFS_LIST_HEAD_INIT(n)           LIST_HEAD_INIT(n)
9 #define CFS_LIST_HEAD(n)                LIST_HEAD(n)
10 #define CFS_INIT_LIST_HEAD(p)           INIT_LIST_HEAD(p)
11
12 #if LINUX_VERSION_CODE >= KERNEL_VERSION(2,6,0)
13 #define CFS_HLIST_HEAD_INIT             HLIST_HEAD_INIT
14 #define CFS_HLIST_HEAD(n)               HLIST_HEAD(n)
15 #define CFS_INIT_HLIST_HEAD(p)          INIT_HLIST_HEAD(p)
16 #define CFS_INIT_HLIST_NODE(p)          INIT_HLIST_NODE(p)
17 #endif
18
19 #else /* !defined (__linux__) || !defined(__KERNEL__) */
20
21 /*
22  * Simple doubly linked list implementation.
23  *
24  * Some of the internal functions ("__xxx") are useful when
25  * manipulating whole lists rather than single entries, as
26  * sometimes we already know the next/prev entries and we can
27  * generate better code by using them directly rather than
28  * using the generic single-entry routines.
29  */
30
31 #define prefetch(a) ((void)a)
32
33 struct list_head {
34         struct list_head *next, *prev;
35 };
36
37 typedef struct list_head list_t;
38
39 #define CFS_LIST_HEAD_INIT(name) { &(name), &(name) }
40
41 #define CFS_LIST_HEAD(name) \
42         struct list_head name = CFS_LIST_HEAD_INIT(name)
43
44 #define CFS_INIT_LIST_HEAD(ptr) do { \
45         (ptr)->next = (ptr); (ptr)->prev = (ptr); \
46 } while (0)
47
48 /**
49  * Insert a new entry between two known consecutive entries.
50  *
51  * This is only for internal list manipulation where we know
52  * the prev/next entries already!
53  */
54 static inline void __list_add(struct list_head * new,
55                               struct list_head * prev,
56                               struct list_head * next)
57 {
58         next->prev = new;
59         new->next = next;
60         new->prev = prev;
61         prev->next = new;
62 }
63
64 /**
65  * Insert an entry at the start of a list.
66  * \param new  new entry to be inserted
67  * \param head list to add it to
68  *
69  * Insert a new entry after the specified head.
70  * This is good for implementing stacks.
71  */
72 static inline void list_add(struct list_head *new, struct list_head *head)
73 {
74         __list_add(new, head, head->next);
75 }
76
77 /**
78  * Insert an entry at the end of a list.
79  * \param new  new entry to be inserted
80  * \param head list to add it to
81  *
82  * Insert a new entry before the specified head.
83  * This is useful for implementing queues.
84  */
85 static inline void list_add_tail(struct list_head *new, struct list_head *head)
86 {
87         __list_add(new, head->prev, head);
88 }
89
90 /*
91  * Delete a list entry by making the prev/next entries
92  * point to each other.
93  *
94  * This is only for internal list manipulation where we know
95  * the prev/next entries already!
96  */
97 static inline void __list_del(struct list_head * prev, struct list_head * next)
98 {
99         next->prev = prev;
100         prev->next = next;
101 }
102
103 /**
104  * Remove an entry from the list it is currently in.
105  * \param entry the entry to remove
106  * Note: list_empty(entry) does not return true after this, the entry is in an undefined state.
107  */
108 static inline void list_del(struct list_head *entry)
109 {
110         __list_del(entry->prev, entry->next);
111 }
112
113 /**
114  * Remove an entry from the list it is currently in and reinitialize it.
115  * \param entry the entry to remove.
116  */
117 static inline void list_del_init(struct list_head *entry)
118 {
119         __list_del(entry->prev, entry->next);
120         CFS_INIT_LIST_HEAD(entry);
121 }
122
123 /**
124  * Remove an entry from the list it is currently in and insert it at the start of another list.
125  * \param list the entry to move
126  * \param head the list to move it to
127  */
128 static inline void list_move(struct list_head *list, struct list_head *head)
129 {
130         __list_del(list->prev, list->next);
131         list_add(list, head);
132 }
133
134 /**
135  * Remove an entry from the list it is currently in and insert it at the end of another list.
136  * \param list the entry to move
137  * \param head the list to move it to
138  */
139 static inline void list_move_tail(struct list_head *list,
140                                   struct list_head *head)
141 {
142         __list_del(list->prev, list->next);
143         list_add_tail(list, head);
144 }
145
146 /**
147  * Test whether a list is empty
148  * \param head the list to test.
149  */
150 static inline int list_empty(struct list_head *head)
151 {
152         return head->next == head;
153 }
154
155 /**
156  * Test whether a list is empty and not being modified
157  * \param head the list to test
158  *
159  * Tests whether a list is empty _and_ checks that no other CPU might be
160  * in the process of modifying either member (next or prev)
161  *
162  * NOTE: using list_empty_careful() without synchronization
163  * can only be safe if the only activity that can happen
164  * to the list entry is list_del_init(). Eg. it cannot be used
165  * if another CPU could re-list_add() it.
166  */
167 static inline int list_empty_careful(const struct list_head *head)
168 {
169         struct list_head *next = head->next;
170         return (next == head) && (next == head->prev);
171 }
172
173 static inline void __list_splice(struct list_head *list,
174                                  struct list_head *head)
175 {
176         struct list_head *first = list->next;
177         struct list_head *last = list->prev;
178         struct list_head *at = head->next;
179
180         first->prev = head;
181         head->next = first;
182
183         last->next = at;
184         at->prev = last;
185 }
186
187 /**
188  * Join two lists
189  * \param list the new list to add.
190  * \param head the place to add it in the first list.
191  *
192  * The contents of \a list are added at the start of \a head.  \a list is in an
193  * undefined state on return.
194  */
195 static inline void list_splice(struct list_head *list, struct list_head *head)
196 {
197         if (!list_empty(list))
198                 __list_splice(list, head);
199 }
200
201 /**
202  * Join two lists and reinitialise the emptied list.
203  * \param list the new list to add.
204  * \param head the place to add it in the first list.
205  *
206  * The contents of \a list are added at the start of \a head.  \a list is empty
207  * on return.
208  */
209 static inline void list_splice_init(struct list_head *list,
210                                     struct list_head *head)
211 {
212         if (!list_empty(list)) {
213                 __list_splice(list, head);
214                 CFS_INIT_LIST_HEAD(list);
215         }
216 }
217
218 /**
219  * Get the container of a list 
220  * \param ptr    the embedded list.
221  * \param type   the type of the struct this is embedded in.
222  * \param member the member name of the list within the struct.
223  */
224 #define list_entry(ptr, type, member) \
225         ((type *)((char *)(ptr)-(char *)(&((type *)0)->member)))
226
227 /**
228  * Iterate over a list
229  * \param pos   the iterator
230  * \param head  the list to iterate over
231  * 
232  * Behaviour is undefined if \a pos is removed from the list in the body of the
233  * loop.
234  */
235 #define list_for_each(pos, head) \
236         for (pos = (head)->next, prefetch(pos->next); pos != (head); \
237                 pos = pos->next, prefetch(pos->next))
238
239 /**
240  * iterate over a list safely
241  * \param pos   the iterator
242  * \param n     temporary storage
243  * \param head  the list to iterate over
244  *
245  * This is safe to use if \a pos could be removed from the list in the body of
246  * the loop.
247  */
248 #define list_for_each_safe(pos, n, head) \
249         for (pos = (head)->next, n = pos->next; pos != (head); \
250                 pos = n, n = pos->next)
251
252 /**
253  * \defgroup hlist Hash List
254  * Double linked lists with a single pointer list head.
255  * Mostly useful for hash tables where the two pointer list head is too
256  * wasteful.  You lose the ability to access the tail in O(1).
257  * @{
258  */
259
260 struct hlist_head {
261         struct hlist_node *first;
262 };
263
264 struct hlist_node {
265         struct hlist_node *next, **pprev;
266 };
267
268 /* @} */
269
270 /*
271  * "NULL" might not be defined at this point
272  */
273 #ifdef NULL
274 #define NULL_P NULL
275 #else
276 #define NULL_P ((void *)0)
277 #endif
278
279 /**
280  * \addtogroup hlist
281  * @{
282  */
283
284 #define CFS_HLIST_HEAD_INIT { NULL_P }
285 #define CFS_HLIST_HEAD(name) struct hlist_head name = { NULL_P }
286 #define CFS_INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL_P)
287 #define CFS_INIT_HLIST_NODE(ptr) ((ptr)->next = NULL_P, (ptr)->pprev = NULL_P)
288
289 #define HLIST_HEAD_INIT         CFS_HLIST_HEAD_INIT
290 #define HLIST_HEAD(n)           CFS_HLIST_HEAD(n)
291 #define INIT_HLIST_HEAD(p)      CFS_INIT_HLIST_HEAD(p)
292 #define INIT_HLIST_NODE(p)      CFS_INIT_HLIST_NODE(p)
293
294 static inline int hlist_unhashed(const struct hlist_node *h)
295 {
296         return !h->pprev;
297 }
298
299 static inline int hlist_empty(const struct hlist_head *h)
300 {
301         return !h->first;
302 }
303
304 static inline void __hlist_del(struct hlist_node *n)
305 {
306         struct hlist_node *next = n->next;
307         struct hlist_node **pprev = n->pprev;
308         *pprev = next;
309         if (next)
310                 next->pprev = pprev;
311 }
312
313 static inline void hlist_del(struct hlist_node *n)
314 {
315         __hlist_del(n);
316 }
317
318 static inline void hlist_del_init(struct hlist_node *n)
319 {
320         if (n->pprev)  {
321                 __hlist_del(n);
322                 INIT_HLIST_NODE(n);
323         }
324 }
325
326 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
327 {
328         struct hlist_node *first = h->first;
329         n->next = first;
330         if (first)
331                 first->pprev = &n->next;
332         h->first = n;
333         n->pprev = &h->first;
334 }
335
336 /* next must be != NULL */
337 static inline void hlist_add_before(struct hlist_node *n,
338                                         struct hlist_node *next)
339 {
340         n->pprev = next->pprev;
341         n->next = next;
342         next->pprev = &n->next;
343         *(n->pprev) = n;
344 }
345
346 static inline void hlist_add_after(struct hlist_node *n,
347                                         struct hlist_node *next)
348 {
349         next->next = n->next;
350         n->next = next;
351         next->pprev = &n->next;
352
353         if(next->next)
354                 next->next->pprev  = &next->next;
355 }
356
357 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
358
359 #define hlist_for_each(pos, head) \
360         for (pos = (head)->first; pos && (prefetch(pos->next), 1); \
361              pos = pos->next)
362
363 #define hlist_for_each_safe(pos, n, head) \
364         for (pos = (head)->first; pos && (n = pos->next, 1); \
365              pos = n)
366
367 /**
368  * Iterate over an hlist of given type
369  * \param tpos   the type * to use as a loop counter.
370  * \param pos    the &struct hlist_node to use as a loop counter.
371  * \param head   the head for your list.
372  * \param member the name of the hlist_node within the struct.
373  */
374 #define hlist_for_each_entry(tpos, pos, head, member)                    \
375         for (pos = (head)->first;                                        \
376              pos && ({ prefetch(pos->next); 1;}) &&                      \
377                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
378              pos = pos->next)
379
380 /**
381  * Iterate over an hlist continuing after existing point
382  * \param tpos   the type * to use as a loop counter.
383  * \param pos    the &struct hlist_node to use as a loop counter.
384  * \param member the name of the hlist_node within the struct.
385  */
386 #define hlist_for_each_entry_continue(tpos, pos, member)                 \
387         for (pos = (pos)->next;                                          \
388              pos && ({ prefetch(pos->next); 1;}) &&                      \
389                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
390              pos = pos->next)
391
392 /**
393  * Iterate over an hlist continuing from an existing point
394  * \param tpos   the type * to use as a loop counter.
395  * \param pos    the &struct hlist_node to use as a loop counter.
396  * \param member the name of the hlist_node within the struct.
397  */
398 #define hlist_for_each_entry_from(tpos, pos, member)                     \
399         for (; pos && ({ prefetch(pos->next); 1;}) &&                    \
400                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
401              pos = pos->next)
402
403 /**
404  * Iterate over an hlist of given type safe against removal of list entry
405  * \param tpos   the type * to use as a loop counter.
406  * \param pos    the &struct hlist_node to use as a loop counter.
407  * \param n      another &struct hlist_node to use as temporary storage
408  * \param head   the head for your list.
409  * \param member the name of the hlist_node within the struct.
410  */
411 #define hlist_for_each_entry_safe(tpos, pos, n, head, member)            \
412         for (pos = (head)->first;                                        \
413              pos && ({ n = pos->next; 1; }) &&                           \
414                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
415              pos = n)
416
417 /* @} */
418
419 #endif /* __linux__ && __KERNEL__ */
420
421 #ifndef list_for_each_prev
422 /**
423  * Iterate over a list in reverse order
424  * \param pos   the &struct list_head to use as a loop counter.
425  * \param head  the head for your list.
426  */
427 #define list_for_each_prev(pos, head) \
428         for (pos = (head)->prev, prefetch(pos->prev); pos != (head);     \
429                 pos = pos->prev, prefetch(pos->prev))
430
431 #endif /* list_for_each_prev */
432
433 #ifndef list_for_each_entry
434 /**
435  * Iterate over a list of given type
436  * \param pos        the type * to use as a loop counter.
437  * \param head       the head for your list.
438  * \param member     the name of the list_struct within the struct.
439  */
440 #define list_for_each_entry(pos, head, member)                          \
441         for (pos = list_entry((head)->next, typeof(*pos), member),      \
442                      prefetch(pos->member.next);                        \
443              &pos->member != (head);                                    \
444              pos = list_entry(pos->member.next, typeof(*pos), member),  \
445              prefetch(pos->member.next))
446 #endif /* list_for_each_entry */
447
448 #ifndef list_for_each_entry_reverse
449 /**
450  * Iterate backwards over a list of given type.
451  * \param pos        the type * to use as a loop counter.
452  * \param head       the head for your list.
453  * \param member     the name of the list_struct within the struct.
454  */
455 #define list_for_each_entry_reverse(pos, head, member)                  \
456         for (pos = list_entry((head)->prev, typeof(*pos), member);      \
457              prefetch(pos->member.prev), &pos->member != (head);        \
458              pos = list_entry(pos->member.prev, typeof(*pos), member))
459 #endif /* list_for_each_entry_reverse */
460
461 #ifndef list_for_each_entry_safe
462 /**
463  * Iterate over a list of given type safe against removal of list entry
464  * \param pos        the type * to use as a loop counter.
465  * \param n          another type * to use as temporary storage
466  * \param head       the head for your list.
467  * \param member     the name of the list_struct within the struct.
468  */
469 #define list_for_each_entry_safe(pos, n, head, member)                  \
470         for (pos = list_entry((head)->next, typeof(*pos), member),      \
471                 n = list_entry(pos->member.next, typeof(*pos), member); \
472              &pos->member != (head);                                    \
473              pos = n, n = list_entry(n->member.next, typeof(*n), member))
474
475 #endif /* list_for_each_entry_safe */
476
477 #ifndef list_for_each_entry_safe_from
478 /**
479  * Iterate over a list continuing from an existing point
480  * \param pos        the type * to use as a loop cursor.
481  * \param n          another type * to use as temporary storage
482  * \param head       the head for your list.
483  * \param member     the name of the list_struct within the struct.
484  *
485  * Iterate over list of given type from current point, safe against
486  * removal of list entry.
487  */
488 #define list_for_each_entry_safe_from(pos, n, head, member)             \
489         for (n = list_entry(pos->member.next, typeof(*pos), member);    \
490              &pos->member != (head);                                    \
491              pos = n, n = list_entry(n->member.next, typeof(*n), member))
492 #endif /* list_for_each_entry_safe_from */
493
494 #define cfs_list_for_each_entry_typed(pos, head, type, member)          \
495         for (pos = list_entry((head)->next, type, member),              \
496                      prefetch(pos->member.next);                        \
497              &pos->member != (head);                                    \
498              pos = list_entry(pos->member.next, type, member),          \
499              prefetch(pos->member.next))
500
501 #define cfs_list_for_each_entry_reverse_typed(pos, head, type, member)  \
502         for (pos = list_entry((head)->prev, type, member);              \
503              prefetch(pos->member.prev), &pos->member != (head);        \
504              pos = list_entry(pos->member.prev, type, member))
505
506 #define cfs_list_for_each_entry_safe_typed(pos, n, head, type, member)  \
507     for (pos = list_entry((head)->next, type, member),                  \
508                 n = list_entry(pos->member.next, type, member);         \
509              &pos->member != (head);                                    \
510              pos = n, n = list_entry(n->member.next, type, member))
511
512 #define cfs_list_for_each_entry_safe_from_typed(pos, n, head, type, member)   \
513         for (n = list_entry(pos->member.next, type, member);            \
514              &pos->member != (head);                                    \
515              pos = n, n = list_entry(n->member.next, type, member))
516 #define cfs_hlist_for_each_entry_typed(tpos, pos, head, type, member)   \
517         for (pos = (head)->first;                                       \
518              pos && (prefetch(pos->next), 1) &&                         \
519                 (tpos = hlist_entry(pos, type, member), 1);             \
520              pos = pos->next)
521
522 #define cfs_hlist_for_each_entry_safe_typed(tpos, pos, n, head, type, member)\
523         for (pos = (head)->first;                                       \
524              pos && (n = pos->next, 1) &&                               \
525                 (tpos = hlist_entry(pos, type, member), 1);             \
526              pos = n)
527
528 #endif /* __LIBCFS_LUSTRE_LIST_H__ */