libcfs/include/libcfs/list.h

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