4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License version 2 only,
8 * as published by the Free Software Foundation.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License version 2 for more details. A copy is
14 * included in the COPYING file that accompanied this code.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23 #ifndef __LIBCFS_LIST_H__
24 #define __LIBCFS_LIST_H__
26 #if defined (__linux__) && defined(__KERNEL__)
28 #include <linux/list.h>
30 typedef struct list_head cfs_list_t;
32 #define __cfs_list_add(new, prev, next) __list_add(new, prev, next)
33 #define cfs_list_add(new, head) list_add(new, head)
35 #define cfs_list_add_tail(new, head) list_add_tail(new, head)
37 #define __cfs_list_del(prev, next) __list_del(prev, next)
38 #define cfs_list_del(entry) list_del(entry)
39 #define cfs_list_del_init(entry) list_del_init(entry)
41 #define cfs_list_move(list, head) list_move(list, head)
42 #define cfs_list_move_tail(list, head) list_move_tail(list, head)
44 #define cfs_list_empty(head) list_empty(head)
45 #define cfs_list_empty_careful(head) list_empty_careful(head)
47 #define __cfs_list_splice(list, head) __list_splice(list, head)
48 #define cfs_list_splice(list, head) list_splice(list, head)
50 #define cfs_list_splice_init(list, head) list_splice_init(list, head)
52 #define cfs_list_entry(ptr, type, member) list_entry(ptr, type, member)
53 #define cfs_list_for_each(pos, head) list_for_each(pos, head)
54 #define cfs_list_for_each_safe(pos, n, head) list_for_each_safe(pos, n, head)
55 #define cfs_list_for_each_prev(pos, head) list_for_each_prev(pos, head)
56 #define cfs_list_for_each_entry(pos, head, member) \
57 list_for_each_entry(pos, head, member)
58 #define cfs_list_for_each_entry_reverse(pos, head, member) \
59 list_for_each_entry_reverse(pos, head, member)
60 #define cfs_list_for_each_entry_safe_reverse(pos, n, head, member) \
61 list_for_each_entry_safe_reverse(pos, n, head, member)
62 #define cfs_list_for_each_entry_safe(pos, n, head, member) \
63 list_for_each_entry_safe(pos, n, head, member)
64 #ifdef list_for_each_entry_safe_from
65 #define cfs_list_for_each_entry_safe_from(pos, n, head, member) \
66 list_for_each_entry_safe_from(pos, n, head, member)
67 #endif /* list_for_each_entry_safe_from */
68 #define cfs_list_for_each_entry_continue(pos, head, member) \
69 list_for_each_entry_continue(pos, head, member)
71 #define CFS_LIST_HEAD_INIT(n) LIST_HEAD_INIT(n)
72 #define CFS_LIST_HEAD(n) LIST_HEAD(n)
73 #define CFS_INIT_LIST_HEAD(p) INIT_LIST_HEAD(p)
75 typedef struct hlist_head cfs_hlist_head_t;
76 typedef struct hlist_node cfs_hlist_node_t;
78 #define cfs_hlist_unhashed(h) hlist_unhashed(h)
80 #define cfs_hlist_empty(h) hlist_empty(h)
82 #define __cfs_hlist_del(n) __hlist_del(n)
83 #define cfs_hlist_del(n) hlist_del(n)
84 #define cfs_hlist_del_init(n) hlist_del_init(n)
86 #define cfs_hlist_add_head(n, next) hlist_add_head(n, next)
87 #define cfs_hlist_add_before(n, next) hlist_add_before(n, next)
88 #define cfs_hlist_add_after(n, next) hlist_add_after(n, next)
90 #define cfs_hlist_entry(ptr, type, member) hlist_entry(ptr, type, member)
91 #define cfs_hlist_for_each(pos, head) hlist_for_each(pos, head)
92 #define cfs_hlist_for_each_safe(pos, n, head) \
93 hlist_for_each_safe(pos, n, head)
94 #define cfs_hlist_for_each_entry(tpos, pos, head, member) \
95 hlist_for_each_entry(tpos, pos, head, member)
96 #define cfs_hlist_for_each_entry_continue(tpos, pos, member) \
97 hlist_for_each_entry_continue(tpos, pos, member)
98 #define cfs_hlist_for_each_entry_from(tpos, pos, member) \
99 hlist_for_each_entry_from(tpos, pos, member)
100 #define cfs_hlist_for_each_entry_safe(tpos, pos, n, head, member) \
101 hlist_for_each_entry_safe(tpos, pos, n, head, member)
103 #define CFS_HLIST_HEAD_INIT HLIST_HEAD_INIT
104 #define CFS_HLIST_HEAD(n) HLIST_HEAD(n)
105 #define CFS_INIT_HLIST_HEAD(p) INIT_HLIST_HEAD(p)
106 #define CFS_INIT_HLIST_NODE(p) INIT_HLIST_NODE(p)
108 #else /* !defined (__linux__) || !defined(__KERNEL__) */
111 * Simple doubly linked list implementation.
113 * Some of the internal functions ("__xxx") are useful when
114 * manipulating whole lists rather than single entries, as
115 * sometimes we already know the next/prev entries and we can
116 * generate better code by using them directly rather than
117 * using the generic single-entry routines.
120 #define prefetch(a) ((void)a)
122 struct cfs_list_head {
123 struct cfs_list_head *next, *prev;
126 typedef struct cfs_list_head cfs_list_t;
128 #define CFS_LIST_HEAD_INIT(name) { &(name), &(name) }
130 #define CFS_LIST_HEAD(name) \
131 cfs_list_t name = CFS_LIST_HEAD_INIT(name)
133 #define CFS_INIT_LIST_HEAD(ptr) do { \
134 (ptr)->next = (ptr); (ptr)->prev = (ptr); \
138 * Insert a new entry between two known consecutive entries.
140 * This is only for internal list manipulation where we know
141 * the prev/next entries already!
143 static inline void __cfs_list_add(cfs_list_t * new,
154 * Insert an entry at the start of a list.
155 * \param new new entry to be inserted
156 * \param head list to add it to
158 * Insert a new entry after the specified head.
159 * This is good for implementing stacks.
161 static inline void cfs_list_add(cfs_list_t *new,
164 __cfs_list_add(new, head, head->next);
168 * Insert an entry at the end of a list.
169 * \param new new entry to be inserted
170 * \param head list to add it to
172 * Insert a new entry before the specified head.
173 * This is useful for implementing queues.
175 static inline void cfs_list_add_tail(cfs_list_t *new,
178 __cfs_list_add(new, head->prev, head);
182 * Delete a list entry by making the prev/next entries
183 * point to each other.
185 * This is only for internal list manipulation where we know
186 * the prev/next entries already!
188 static inline void __cfs_list_del(cfs_list_t *prev,
196 * Remove an entry from the list it is currently in.
197 * \param entry the entry to remove
198 * Note: list_empty(entry) does not return true after this, the entry is in an
201 static inline void cfs_list_del(cfs_list_t *entry)
203 __cfs_list_del(entry->prev, entry->next);
207 * Remove an entry from the list it is currently in and reinitialize it.
208 * \param entry the entry to remove.
210 static inline void cfs_list_del_init(cfs_list_t *entry)
212 __cfs_list_del(entry->prev, entry->next);
213 CFS_INIT_LIST_HEAD(entry);
217 * Remove an entry from the list it is currently in and insert it at the start
219 * \param list the entry to move
220 * \param head the list to move it to
222 static inline void cfs_list_move(cfs_list_t *list,
225 __cfs_list_del(list->prev, list->next);
226 cfs_list_add(list, head);
230 * Remove an entry from the list it is currently in and insert it at the end of
232 * \param list the entry to move
233 * \param head the list to move it to
235 static inline void cfs_list_move_tail(cfs_list_t *list,
238 __cfs_list_del(list->prev, list->next);
239 cfs_list_add_tail(list, head);
243 * Test whether a list is empty
244 * \param head the list to test.
246 static inline int cfs_list_empty(cfs_list_t *head)
248 return head->next == head;
252 * Test whether a list is empty and not being modified
253 * \param head the list to test
255 * Tests whether a list is empty _and_ checks that no other CPU might be
256 * in the process of modifying either member (next or prev)
258 * NOTE: using cfs_list_empty_careful() without synchronization
259 * can only be safe if the only activity that can happen
260 * to the list entry is cfs_list_del_init(). Eg. it cannot be used
261 * if another CPU could re-list_add() it.
263 static inline int cfs_list_empty_careful(const cfs_list_t *head)
265 cfs_list_t *next = head->next;
266 return (next == head) && (next == head->prev);
269 static inline void __cfs_list_splice(cfs_list_t *list,
272 cfs_list_t *first = list->next;
273 cfs_list_t *last = list->prev;
274 cfs_list_t *at = head->next;
285 * \param list the new list to add.
286 * \param head the place to add it in the first list.
288 * The contents of \a list are added at the start of \a head. \a list is in an
289 * undefined state on return.
291 static inline void cfs_list_splice(cfs_list_t *list,
294 if (!cfs_list_empty(list))
295 __cfs_list_splice(list, head);
299 * Join two lists and reinitialise the emptied list.
300 * \param list the new list to add.
301 * \param head the place to add it in the first list.
303 * The contents of \a list are added at the start of \a head. \a list is empty
306 static inline void cfs_list_splice_init(cfs_list_t *list,
309 if (!cfs_list_empty(list)) {
310 __cfs_list_splice(list, head);
311 CFS_INIT_LIST_HEAD(list);
316 * Get the container of a list
317 * \param ptr the embedded list.
318 * \param type the type of the struct this is embedded in.
319 * \param member the member name of the list within the struct.
321 #define cfs_list_entry(ptr, type, member) \
322 ((type *)((char *)(ptr)-(char *)(&((type *)0)->member)))
325 * Iterate over a list
326 * \param pos the iterator
327 * \param head the list to iterate over
329 * Behaviour is undefined if \a pos is removed from the list in the body of the
332 #define cfs_list_for_each(pos, head) \
333 for (pos = (head)->next, prefetch(pos->next); pos != (head); \
334 pos = pos->next, prefetch(pos->next))
337 * Iterate over a list safely
338 * \param pos the iterator
339 * \param n temporary storage
340 * \param head the list to iterate over
342 * This is safe to use if \a pos could be removed from the list in the body of
345 #define cfs_list_for_each_safe(pos, n, head) \
346 for (pos = (head)->next, n = pos->next; pos != (head); \
347 pos = n, n = pos->next)
350 * Iterate over a list continuing after existing point
351 * \param pos the type * to use as a loop counter
352 * \param head the list head
353 * \param member the name of the list_struct within the struct
355 #define cfs_list_for_each_entry_continue(pos, head, member) \
356 for (pos = cfs_list_entry(pos->member.next, typeof(*pos), member); \
357 prefetch(pos->member.next), &pos->member != (head); \
358 pos = cfs_list_entry(pos->member.next, typeof(*pos), member))
361 * \defgroup hlist Hash List
362 * Double linked lists with a single pointer list head.
363 * Mostly useful for hash tables where the two pointer list head is too
364 * wasteful. You lose the ability to access the tail in O(1).
368 typedef struct cfs_hlist_node {
369 struct cfs_hlist_node *next, **pprev;
372 typedef struct cfs_hlist_head {
373 cfs_hlist_node_t *first;
379 * "NULL" might not be defined at this point
384 #define NULL_P ((void *)0)
392 #define CFS_HLIST_HEAD_INIT { NULL_P }
393 #define CFS_HLIST_HEAD(name) cfs_hlist_head_t name = { NULL_P }
394 #define CFS_INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL_P)
395 #define CFS_INIT_HLIST_NODE(ptr) ((ptr)->next = NULL_P, (ptr)->pprev = NULL_P)
397 static inline int cfs_hlist_unhashed(const cfs_hlist_node_t *h)
402 static inline int cfs_hlist_empty(const cfs_hlist_head_t *h)
407 static inline void __cfs_hlist_del(cfs_hlist_node_t *n)
409 cfs_hlist_node_t *next = n->next;
410 cfs_hlist_node_t **pprev = n->pprev;
416 static inline void cfs_hlist_del(cfs_hlist_node_t *n)
421 static inline void cfs_hlist_del_init(cfs_hlist_node_t *n)
425 CFS_INIT_HLIST_NODE(n);
429 static inline void cfs_hlist_add_head(cfs_hlist_node_t *n,
432 cfs_hlist_node_t *first = h->first;
435 first->pprev = &n->next;
437 n->pprev = &h->first;
440 /* next must be != NULL */
441 static inline void cfs_hlist_add_before(cfs_hlist_node_t *n,
442 cfs_hlist_node_t *next)
444 n->pprev = next->pprev;
446 next->pprev = &n->next;
450 static inline void cfs_hlist_add_after(cfs_hlist_node_t *n,
451 cfs_hlist_node_t *next)
453 next->next = n->next;
455 next->pprev = &n->next;
458 next->next->pprev = &next->next;
461 #define cfs_hlist_entry(ptr, type, member) container_of(ptr,type,member)
463 #define cfs_hlist_for_each(pos, head) \
464 for (pos = (head)->first; pos && (prefetch(pos->next), 1); \
467 #define cfs_hlist_for_each_safe(pos, n, head) \
468 for (pos = (head)->first; pos && (n = pos->next, 1); \
472 * Iterate over an hlist of given type
473 * \param tpos the type * to use as a loop counter.
474 * \param pos the &struct hlist_node to use as a loop counter.
475 * \param head the head for your list.
476 * \param member the name of the hlist_node within the struct.
478 #define cfs_hlist_for_each_entry(tpos, pos, head, member) \
479 for (pos = (head)->first; \
480 pos && ({ prefetch(pos->next); 1;}) && \
481 ({ tpos = cfs_hlist_entry(pos, typeof(*tpos), member); 1;}); \
485 * Iterate over an hlist continuing after existing point
486 * \param tpos the type * to use as a loop counter.
487 * \param pos the &struct hlist_node to use as a loop counter.
488 * \param member the name of the hlist_node within the struct.
490 #define cfs_hlist_for_each_entry_continue(tpos, pos, member) \
491 for (pos = (pos)->next; \
492 pos && ({ prefetch(pos->next); 1;}) && \
493 ({ tpos = cfs_hlist_entry(pos, typeof(*tpos), member); 1;}); \
497 * Iterate over an hlist continuing from an existing point
498 * \param tpos the type * to use as a loop counter.
499 * \param pos the &struct hlist_node to use as a loop counter.
500 * \param member the name of the hlist_node within the struct.
502 #define cfs_hlist_for_each_entry_from(tpos, pos, member) \
503 for (; pos && ({ prefetch(pos->next); 1;}) && \
504 ({ tpos = cfs_hlist_entry(pos, typeof(*tpos), member); 1;}); \
508 * Iterate over an hlist of given type safe against removal of list entry
509 * \param tpos the type * to use as a loop counter.
510 * \param pos the &struct hlist_node to use as a loop counter.
511 * \param n another &struct hlist_node to use as temporary storage
512 * \param head the head for your list.
513 * \param member the name of the hlist_node within the struct.
515 #define cfs_hlist_for_each_entry_safe(tpos, pos, n, head, member) \
516 for (pos = (head)->first; \
517 pos && ({ n = pos->next; 1; }) && \
518 ({ tpos = cfs_hlist_entry(pos, typeof(*tpos), member); 1;}); \
523 #endif /* __linux__ && __KERNEL__ */
525 #ifndef cfs_list_for_each_prev
527 * Iterate over a list in reverse order
528 * \param pos the &struct list_head to use as a loop counter.
529 * \param head the head for your list.
531 #define cfs_list_for_each_prev(pos, head) \
532 for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \
533 pos = pos->prev, prefetch(pos->prev))
535 #endif /* cfs_list_for_each_prev */
537 #ifndef cfs_list_for_each_entry
539 * Iterate over a list of given type
540 * \param pos the type * to use as a loop counter.
541 * \param head the head for your list.
542 * \param member the name of the list_struct within the struct.
544 #define cfs_list_for_each_entry(pos, head, member) \
545 for (pos = cfs_list_entry((head)->next, typeof(*pos), member), \
546 prefetch(pos->member.next); \
547 &pos->member != (head); \
548 pos = cfs_list_entry(pos->member.next, typeof(*pos), member), \
549 prefetch(pos->member.next))
550 #endif /* cfs_list_for_each_entry */
552 #ifndef cfs_list_for_each_entry_rcu
553 #define cfs_list_for_each_entry_rcu(pos, head, member) \
554 list_for_each_entry(pos, head, member)
557 #ifndef cfs_list_for_each_entry_rcu
558 #define cfs_list_for_each_entry_rcu(pos, head, member) \
559 list_for_each_entry(pos, head, member)
562 #ifndef cfs_list_for_each_entry_reverse
564 * Iterate backwards over a list of given type.
565 * \param pos the type * to use as a loop counter.
566 * \param head the head for your list.
567 * \param member the name of the list_struct within the struct.
569 #define cfs_list_for_each_entry_reverse(pos, head, member) \
570 for (pos = cfs_list_entry((head)->prev, typeof(*pos), member); \
571 prefetch(pos->member.prev), &pos->member != (head); \
572 pos = cfs_list_entry(pos->member.prev, typeof(*pos), member))
573 #endif /* cfs_list_for_each_entry_reverse */
575 #ifndef cfs_list_for_each_entry_safe
577 * Iterate over a list of given type safe against removal of list entry
578 * \param pos the type * to use as a loop counter.
579 * \param n another type * to use as temporary storage
580 * \param head the head for your list.
581 * \param member the name of the list_struct within the struct.
583 #define cfs_list_for_each_entry_safe(pos, n, head, member) \
584 for (pos = cfs_list_entry((head)->next, typeof(*pos), member), \
585 n = cfs_list_entry(pos->member.next, typeof(*pos), member); \
586 &pos->member != (head); \
587 pos = n, n = cfs_list_entry(n->member.next, typeof(*n), member))
589 #endif /* cfs_list_for_each_entry_safe */
591 #ifndef cfs_list_for_each_entry_safe_from
593 * Iterate over a list continuing from an existing point
594 * \param pos the type * to use as a loop cursor.
595 * \param n another type * to use as temporary storage
596 * \param head the head for your list.
597 * \param member the name of the list_struct within the struct.
599 * Iterate over list of given type from current point, safe against
600 * removal of list entry.
602 #define cfs_list_for_each_entry_safe_from(pos, n, head, member) \
603 for (n = cfs_list_entry(pos->member.next, typeof(*pos), member); \
604 &pos->member != (head); \
605 pos = n, n = cfs_list_entry(n->member.next, typeof(*n), member))
606 #endif /* cfs_list_for_each_entry_safe_from */
608 #define cfs_list_for_each_entry_typed(pos, head, type, member) \
609 for (pos = cfs_list_entry((head)->next, type, member), \
610 prefetch(pos->member.next); \
611 &pos->member != (head); \
612 pos = cfs_list_entry(pos->member.next, type, member), \
613 prefetch(pos->member.next))
615 #define cfs_list_for_each_entry_reverse_typed(pos, head, type, member) \
616 for (pos = cfs_list_entry((head)->prev, type, member); \
617 prefetch(pos->member.prev), &pos->member != (head); \
618 pos = cfs_list_entry(pos->member.prev, type, member))
620 #define cfs_list_for_each_entry_safe_typed(pos, n, head, type, member) \
621 for (pos = cfs_list_entry((head)->next, type, member), \
622 n = cfs_list_entry(pos->member.next, type, member); \
623 &pos->member != (head); \
624 pos = n, n = cfs_list_entry(n->member.next, type, member))
626 #define cfs_list_for_each_entry_safe_from_typed(pos, n, head, type, member) \
627 for (n = cfs_list_entry(pos->member.next, type, member); \
628 &pos->member != (head); \
629 pos = n, n = cfs_list_entry(n->member.next, type, member))
631 #define cfs_hlist_for_each_entry_typed(tpos, pos, head, type, member) \
632 for (pos = (head)->first; \
633 pos && (prefetch(pos->next), 1) && \
634 (tpos = cfs_hlist_entry(pos, type, member), 1); \
637 #define cfs_hlist_for_each_entry_safe_typed(tpos, pos, n, head, type, member) \
638 for (pos = (head)->first; \
639 pos && (n = pos->next, 1) && \
640 (tpos = cfs_hlist_entry(pos, type, member), 1); \
643 #endif /* __LIBCFS_LUSTRE_LIST_H__ */