lnet/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 #else /* !defined (__linux__) && defined(__KERNEL__) */
  13
  14 /*
  15  * Simple doubly linked list implementation.
  16  *
  17  * Some of the internal functions ("__xxx") are useful when
  18  * manipulating whole lists rather than single entries, as
  19  * sometimes we already know the next/prev entries and we can
  20  * generate better code by using them directly rather than
  21  * using the generic single-entry routines.
  22  */
  23
  24 #define prefetch(a) ((void)a)
  25
  26 struct list_head {
  27         struct list_head *next, *prev;
  28 };
  29
  30 typedef struct list_head list_t;
  31
  32 #define CFS_LIST_HEAD_INIT(name) { &(name), &(name) }
  33
  34 #define CFS_LIST_HEAD(name) \
  35         struct list_head name = LIST_HEAD_INIT(name)
  36
  37 #define CFS_INIT_LIST_HEAD(ptr) do { \
  38         (ptr)->next = (ptr); (ptr)->prev = (ptr); \
  39 } while (0)
  40
  41 #ifndef __APPLE__
  42 #define LIST_HEAD(n)            CFS_LIST_HEAD(n)
  43 #endif
  44
  45 #define LIST_HEAD_INIT(n)       CFS_LIST_HEAD_INIT(n)
  46 #define INIT_LIST_HEAD(p)       CFS_INIT_LIST_HEAD(p)
  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  * list_add - add a new entry
  66  * @new: new entry to be added
  67  * @head: list head to add it after
  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  * list_add_tail - add a new entry
  79  * @new: new entry to be added
  80  * @head: list head to add it before
  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  * list_del - deletes entry from list.
 105  * @entry: the element to delete from the list.
 106  * Note: list_empty on 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  * list_del_init - deletes entry from list and reinitialize it.
 115  * @entry: the element to delete from the list.
 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  * list_move - delete from one list and add as another's head
 125  * @list: the entry to move
 126  * @head: the head that will precede our entry
 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  * list_move_tail - delete from one list and add as another's tail
 136  * @list: the entry to move
 137  * @head: the head that will follow our entry
 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  * list_empty - tests whether a list is empty
 148  * @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 static inline void __list_splice(struct list_head *list,
 156                                  struct list_head *head)
 157 {
 158         struct list_head *first = list->next;
 159         struct list_head *last = list->prev;
 160         struct list_head *at = head->next;
 161
 162         first->prev = head;
 163         head->next = first;
 164
 165         last->next = at;
 166         at->prev = last;
 167 }
 168
 169 /**
 170  * list_splice - join two lists
 171  * @list: the new list to add.
 172  * @head: the place to add it in the first list.
 173  */
 174 static inline void list_splice(struct list_head *list, struct list_head *head)
 175 {
 176         if (!list_empty(list))
 177                 __list_splice(list, head);
 178 }
 179
 180 /**
 181  * list_splice_init - join two lists and reinitialise the emptied list.
 182  * @list: the new list to add.
 183  * @head: the place to add it in the first list.
 184  *
 185  * The list at @list is reinitialised
 186  */
 187 static inline void list_splice_init(struct list_head *list,
 188                                     struct list_head *head)
 189 {
 190         if (!list_empty(list)) {
 191                 __list_splice(list, head);
 192                 CFS_INIT_LIST_HEAD(list);
 193         }
 194 }
 195
 196 /**
 197  * list_entry - get the struct for this entry
 198  * @ptr:        the &struct list_head pointer.
 199  * @type:       the type of the struct this is embedded in.
 200  * @member:     the name of the list_struct within the struct.
 201  */
 202 #define list_entry(ptr, type, member) \
 203         ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
 204
 205 /**
 206  * list_for_each        -       iterate over a list
 207  * @pos:        the &struct list_head to use as a loop counter.
 208  * @head:       the head for your list.
 209  */
 210 #define list_for_each(pos, head) \
 211         for (pos = (head)->next, prefetch(pos->next); pos != (head); \
 212                 pos = pos->next, prefetch(pos->next))
 213
 214 /**
 215  * list_for_each_safe   -       iterate over a list safe against removal of list entry
 216  * @pos:        the &struct list_head to use as a loop counter.
 217  * @n:          another &struct list_head to use as temporary storage
 218  * @head:       the head for your list.
 219  */
 220 #define list_for_each_safe(pos, n, head) \
 221         for (pos = (head)->next, n = pos->next; pos != (head); \
 222                 pos = n, n = pos->next)
 223
 224 #endif /* __linux__*/
 225
 226 #ifndef list_for_each_prev
 227 /**
 228  * list_for_each_prev   -       iterate over a list in reverse order
 229  * @pos:        the &struct list_head to use as a loop counter.
 230  * @head:       the head for your list.
 231  */
 232 #define list_for_each_prev(pos, head) \
 233         for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \
 234                 pos = pos->prev, prefetch(pos->prev))
 235
 236 #endif /* list_for_each_prev */
 237
 238 #ifndef list_for_each_entry
 239 /**
 240  * list_for_each_entry  -       iterate over list of given type
 241  * @pos:        the type * to use as a loop counter.
 242  * @head:       the head for your list.
 243  * @member:     the name of the list_struct within the struct.
 244  */
 245 #define list_for_each_entry(pos, head, member)                          \
 246         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 247                      prefetch(pos->member.next);                        \
 248              &pos->member != (head);                                    \
 249              pos = list_entry(pos->member.next, typeof(*pos), member),  \
 250              prefetch(pos->member.next))
 251 #endif /* list_for_each_entry */
 252
 253 #ifndef list_for_each_entry_safe
 254 /**
 255  * list_for_each_entry_safe  -       iterate over list of given type safe against removal of list entry
 256  * @pos:        the type * to use as a loop counter.
 257  * @n:          another type * to use as temporary storage
 258  * @head:       the head for your list.
 259  * @member:     the name of the list_struct within the struct.
 260  */
 261 #define list_for_each_entry_safe(pos, n, head, member)                  \
 262         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 263                 n = list_entry(pos->member.next, typeof(*pos), member); \
 264              &pos->member != (head);                                    \
 265              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 266 #endif /* list_for_each_entry_safe */
 267
 268 #endif /* __LIBCFS_LUSTRE_LIST_H__ */