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 #ifndef list_for_each_entry_reverse
 269 /**
 270  * list_for_each_entry_reverse - iterate backwards over list of given type.
 271  * @pos:        the type * to use as a loop counter.
 272  * @head:       the head for your list.
 273  * @member:     the name of the list_struct within the struct.
 274  */
 275 #define list_for_each_entry_reverse(pos, head, member)                  \
 276         for (pos = list_entry((head)->prev, typeof(*pos), member),      \
 277                      prefetch(pos->member.prev);                        \
 278              &pos->member != (head);                                    \
 279              pos = list_entry(pos->member.prev, typeof(*pos), member),  \
 280                      prefetch(pos->member.prev))
 281 #endif
 282
 283 #ifndef NULL
 284 #define NULL ((void *)0)
 285 #endif
 286
 287 /* hlist stuff */
 288 #ifndef __KERNEL__
 289 #define HLIST_HEAD_INIT { .first = NULL }
 290 #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
 291 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
 292 #define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)
 293
 294 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
 295
 296 #ifndef hlist_for_each
 297 #define hlist_for_each(pos, head) \
 298         for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
 299              pos = pos->next)
 300 #endif
 301
 302 #ifndef hlist_for_each_entry_safe
 303 /**
 304  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 305  * @tpos:       the type * to use as a loop counter.
 306  * @pos:        the &struct hlist_node to use as a loop counter.
 307  * @n:          another &struct hlist_node to use as temporary storage
 308  * @head:       the head for your list.
 309  * @member:     the name of the hlist_node within the struct.
 310  */
 311 #define hlist_for_each_entry_safe(tpos, pos, n, head, member)            \
 312         for (pos = (head)->first;                                        \
 313              pos && ({ n = pos->next; 1; }) &&                           \
 314                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 315              pos = n)
 316 #endif
 317
 318 #ifndef hlist_for_each_safe
 319 #define hlist_for_each_safe(pos, n, head) \
 320         for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
 321              pos = n)
 322 #endif
 323
 324 #ifndef hlist_for_each_entry
 325 /**
 326  * hlist_for_each_entry - iterate over list of given type
 327  * @tpos:       the type * to use as a loop counter.
 328  * @pos:        the &struct hlist_node to use as a loop counter.
 329  * @head:       the head for your list.
 330  * @member:     the name of the hlist_node within the struct.
 331  */
 332 #define hlist_for_each_entry(tpos, pos, head, member)                    \
 333         for (pos = (head)->first;                                        \
 334              pos && ({ prefetch(pos->next); 1;}) &&                      \
 335                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 336              pos = pos->next)
 337 #endif
 338
 339 /*
 340  * These are non-NULL pointers that will result in page faults
 341  * under normal circumstances, used to verify that nobody uses
 342  * non-initialized list entries.
 343  */
 344 #define LIST_POISON1  ((void *) 0x00100100)
 345 #define LIST_POISON2  ((void *) 0x00200200)
 346
 347 #ifndef __KERNEL__
 348 struct hlist_head {
 349         struct hlist_node *first;
 350 };
 351
 352 struct hlist_node {
 353         struct hlist_node *next, **pprev;
 354 };
 355
 356 static inline int hlist_unhashed(const struct hlist_node *h)
 357 {
 358         return !h->pprev;
 359 }
 360
 361 static inline int hlist_empty(const struct hlist_head *h)
 362 {
 363         return !h->first;
 364 }
 365
 366 static inline void __hlist_del(struct hlist_node *n)
 367 {
 368         struct hlist_node *next = n->next;
 369         struct hlist_node **pprev = n->pprev;
 370         *pprev = next;
 371         if (next)
 372                 next->pprev = pprev;
 373 }
 374
 375 static inline void hlist_del(struct hlist_node *n)
 376 {
 377         __hlist_del(n);
 378         n->next = LIST_POISON1;
 379         n->pprev = LIST_POISON2;
 380 }
 381
 382 static inline void hlist_del_init(struct hlist_node *n)
 383 {
 384         if (n->pprev)  {
 385                 __hlist_del(n);
 386                 INIT_HLIST_NODE(n);
 387         }
 388 }
 389
 390 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 391 {
 392         struct hlist_node *first = h->first;
 393         n->next = first;
 394         if (first)
 395                 first->pprev = &n->next;
 396         h->first = n;
 397         n->pprev = &h->first;
 398 }
 399 #endif /* __KERNEL__ */
 400 #endif /* HLIST_HEAD */
 401
 402 #endif /* __LIBCFS_LUSTRE_LIST_H__ */