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_rcu
 449 #define list_for_each_entry_rcu(pos, head, member) \
 450         list_for_each_entry(pos, head, member)
 451 #endif
 452
 453 #ifndef list_for_each_entry_rcu
 454 #define list_for_each_entry_rcu(pos, head, member) \
 455        list_for_each_entry(pos, head, member)
 456 #endif
 457
 458 #ifndef list_for_each_entry_rcu
 459 #define list_for_each_entry_rcu(pos, head, member) \
 460        list_for_each_entry(pos, head, member)
 461 #endif
 462
 463 #ifndef list_for_each_entry_reverse
 464 /**
 465  * Iterate backwards over a list of given type.
 466  * \param pos        the type * to use as a loop counter.
 467  * \param head       the head for your list.
 468  * \param member     the name of the list_struct within the struct.
 469  */
 470 #define list_for_each_entry_reverse(pos, head, member)                  \
 471         for (pos = list_entry((head)->prev, typeof(*pos), member);      \
 472              prefetch(pos->member.prev), &pos->member != (head);        \
 473              pos = list_entry(pos->member.prev, typeof(*pos), member))
 474 #endif /* list_for_each_entry_reverse */
 475
 476 #ifndef list_for_each_entry_safe
 477 /**
 478  * Iterate over a list of given type safe against removal of list entry
 479  * \param pos        the type * to use as a loop counter.
 480  * \param n          another type * to use as temporary storage
 481  * \param head       the head for your list.
 482  * \param member     the name of the list_struct within the struct.
 483  */
 484 #define list_for_each_entry_safe(pos, n, head, member)                  \
 485         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 486                 n = list_entry(pos->member.next, typeof(*pos), member); \
 487              &pos->member != (head);                                    \
 488              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 489
 490 #endif /* list_for_each_entry_safe */
 491
 492 #ifndef list_for_each_entry_safe_from
 493 /**
 494  * Iterate over a list continuing from an existing point
 495  * \param pos        the type * to use as a loop cursor.
 496  * \param n          another type * to use as temporary storage
 497  * \param head       the head for your list.
 498  * \param member     the name of the list_struct within the struct.
 499  *
 500  * Iterate over list of given type from current point, safe against
 501  * removal of list entry.
 502  */
 503 #define list_for_each_entry_safe_from(pos, n, head, member)             \
 504         for (n = list_entry(pos->member.next, typeof(*pos), member);    \
 505              &pos->member != (head);                                    \
 506              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 507 #endif /* list_for_each_entry_safe_from */
 508
 509 #define cfs_list_for_each_entry_typed(pos, head, type, member)          \
 510         for (pos = list_entry((head)->next, type, member),              \
 511                      prefetch(pos->member.next);                        \
 512              &pos->member != (head);                                    \
 513              pos = list_entry(pos->member.next, type, member),          \
 514              prefetch(pos->member.next))
 515
 516 #define cfs_list_for_each_entry_reverse_typed(pos, head, type, member)  \
 517         for (pos = list_entry((head)->prev, type, member);              \
 518              prefetch(pos->member.prev), &pos->member != (head);        \
 519              pos = list_entry(pos->member.prev, type, member))
 520
 521 #define cfs_list_for_each_entry_safe_typed(pos, n, head, type, member)  \
 522     for (pos = list_entry((head)->next, type, member),                  \
 523                 n = list_entry(pos->member.next, type, member);         \
 524              &pos->member != (head);                                    \
 525              pos = n, n = list_entry(n->member.next, type, member))
 526
 527 #define cfs_list_for_each_entry_safe_from_typed(pos, n, head, type, member)   \
 528         for (n = list_entry(pos->member.next, type, member);            \
 529              &pos->member != (head);                                    \
 530              pos = n, n = list_entry(n->member.next, type, member))
 531 #define cfs_hlist_for_each_entry_typed(tpos, pos, head, type, member)   \
 532         for (pos = (head)->first;                                       \
 533              pos && (prefetch(pos->next), 1) &&                         \
 534                 (tpos = hlist_entry(pos, type, member), 1);             \
 535              pos = pos->next)
 536
 537 #define cfs_hlist_for_each_entry_safe_typed(tpos, pos, n, head, type, member)\
 538         for (pos = (head)->first;                                       \
 539              pos && (n = pos->next, 1) &&                               \
 540                 (tpos = hlist_entry(pos, type, member), 1);             \
 541              pos = n)
 542
 543 #endif /* __LIBCFS_LUSTRE_LIST_H__ */