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 #ifdef __KERNEL__
  27 # include <linux/list.h>
  28 #else /* __KERNEL__ */
  29
  30 /*
  31  * Simple doubly linked list implementation.
  32  *
  33  * Some of the internal functions ("__xxx") are useful when
  34  * manipulating whole lists rather than single entries, as
  35  * sometimes we already know the next/prev entries and we can
  36  * generate better code by using them directly rather than
  37  * using the generic single-entry routines.
  38  */
  39
  40 #define prefetch(a) ((void)a)
  41
  42 struct list_head {
  43         struct list_head *next, *prev;
  44 };
  45
  46 #define LIST_HEAD_INIT(name) { &(name), &(name) }
  47
  48 #define INIT_LIST_HEAD(ptr) do { \
  49         (ptr)->next = (ptr); (ptr)->prev = (ptr); \
  50 } while (0)
  51
  52 /**
  53  * Insert a new entry between two known consecutive entries.
  54  *
  55  * This is only for internal list manipulation where we know
  56  * the prev/next entries already!
  57  */
  58 static inline void __list_add(struct list_head * new,
  59                                   struct list_head * prev,
  60                                   struct list_head * next)
  61 {
  62         next->prev = new;
  63         new->next = next;
  64         new->prev = prev;
  65         prev->next = new;
  66 }
  67
  68 /**
  69  * Insert an entry at the start of a list.
  70  * \param new  new entry to be inserted
  71  * \param head list to add it to
  72  *
  73  * Insert a new entry after the specified head.
  74  * This is good for implementing stacks.
  75  */
  76 static inline void list_add(struct list_head *new,
  77                                 struct list_head *head)
  78 {
  79         __list_add(new, head, head->next);
  80 }
  81
  82 /**
  83  * Insert an entry at the end of a list.
  84  * \param new  new entry to be inserted
  85  * \param head list to add it to
  86  *
  87  * Insert a new entry before the specified head.
  88  * This is useful for implementing queues.
  89  */
  90 static inline void list_add_tail(struct list_head *new,
  91                                      struct list_head *head)
  92 {
  93         __list_add(new, head->prev, head);
  94 }
  95
  96 /*
  97  * Delete a list entry by making the prev/next entries
  98  * point to each other.
  99  *
 100  * This is only for internal list manipulation where we know
 101  * the prev/next entries already!
 102  */
 103 static inline void __list_del(struct list_head *prev,
 104                                   struct list_head *next)
 105 {
 106         next->prev = prev;
 107         prev->next = next;
 108 }
 109
 110 /**
 111  * Remove an entry from the list it is currently in.
 112  * \param entry the entry to remove
 113  * Note: list_empty(entry) does not return true after this, the entry is in an
 114  * undefined state.
 115  */
 116 static inline void list_del(struct list_head *entry)
 117 {
 118         __list_del(entry->prev, entry->next);
 119 }
 120
 121 /**
 122  * Remove an entry from the list it is currently in and reinitialize it.
 123  * \param entry the entry to remove.
 124  */
 125 static inline void list_del_init(struct list_head *entry)
 126 {
 127         __list_del(entry->prev, entry->next);
 128         INIT_LIST_HEAD(entry);
 129 }
 130
 131 /**
 132  * Remove an entry from the list it is currently in and insert it at the start
 133  * of another list.
 134  * \param list the entry to move
 135  * \param head the list to move it to
 136  */
 137 static inline void list_move(struct list_head *list,
 138                                  struct list_head *head)
 139 {
 140         __list_del(list->prev, list->next);
 141         list_add(list, head);
 142 }
 143
 144 /**
 145  * Remove an entry from the list it is currently in and insert it at the end of
 146  * another list.
 147  * \param list the entry to move
 148  * \param head the list to move it to
 149  */
 150 static inline void list_move_tail(struct list_head *list,
 151                                       struct list_head *head)
 152 {
 153         __list_del(list->prev, list->next);
 154         list_add_tail(list, head);
 155 }
 156
 157 /**
 158  * Test whether a list is empty
 159  * \param head the list to test.
 160  */
 161 static inline int list_empty(struct list_head *head)
 162 {
 163         return head->next == head;
 164 }
 165
 166 /**
 167  * Test whether a list is empty and not being modified
 168  * \param head the list to test
 169  *
 170  * Tests whether a list is empty _and_ checks that no other CPU might be
 171  * in the process of modifying either member (next or prev)
 172  *
 173  * NOTE: using list_empty_careful() without synchronization
 174  * can only be safe if the only activity that can happen
 175  * to the list entry is list_del_init(). Eg. it cannot be used
 176  * if another CPU could re-list_add() it.
 177  */
 178 static inline int list_empty_careful(const struct list_head *head)
 179 {
 180         struct list_head *next = head->next;
 181         return (next == head) && (next == head->prev);
 182 }
 183
 184 static inline void __list_splice(struct list_head *list,
 185                                      struct list_head *head)
 186 {
 187         struct list_head *first = list->next;
 188         struct list_head *last = list->prev;
 189         struct list_head *at = head->next;
 190
 191         first->prev = head;
 192         head->next = first;
 193
 194         last->next = at;
 195         at->prev = last;
 196 }
 197
 198 /**
 199  * Join two lists
 200  * \param list the new list to add.
 201  * \param head the place to add it in the first list.
 202  *
 203  * The contents of \a list are added at the start of \a head.  \a list is in an
 204  * undefined state on return.
 205  */
 206 static inline void list_splice(struct list_head *list,
 207                                    struct list_head *head)
 208 {
 209         if (!list_empty(list))
 210                 __list_splice(list, head);
 211 }
 212
 213 static inline void list_splice_tail(struct list_head *list, struct list_head *head)
 214 {
 215         if (!list_empty(list))
 216                 __list_splice(list, head->prev);
 217 }
 218
 219 /**
 220  * Join two lists and reinitialise the emptied list.
 221  * \param list the new list to add.
 222  * \param head the place to add it in the first list.
 223  *
 224  * The contents of \a list are added at the start of \a head.  \a list is empty
 225  * on return.
 226  */
 227 static inline void list_splice_init(struct list_head *list,
 228                                         struct list_head *head)
 229 {
 230         if (!list_empty(list)) {
 231                 __list_splice(list, head);
 232                 INIT_LIST_HEAD(list);
 233         }
 234 }
 235
 236 /**
 237  * Get the container of a list
 238  * \param ptr    the embedded list.
 239  * \param type   the type of the struct this is embedded in.
 240  * \param member the member name of the list within the struct.
 241  */
 242 #define list_entry(ptr, type, member) \
 243         ((type *)((char *)(ptr)-(char *)(&((type *)0)->member)))
 244
 245 /**
 246  * Iterate over a list
 247  * \param pos   the iterator
 248  * \param head  the list to iterate over
 249  *
 250  * Behaviour is undefined if \a pos is removed from the list in the body of the
 251  * loop.
 252  */
 253 #define list_for_each(pos, head) \
 254         for (pos = (head)->next, prefetch(pos->next); pos != (head); \
 255                 pos = pos->next, prefetch(pos->next))
 256
 257 /**
 258  * Iterate over a list safely
 259  * \param pos   the iterator
 260  * \param n     temporary storage
 261  * \param head  the list to iterate over
 262  *
 263  * This is safe to use if \a pos could be removed from the list in the body of
 264  * the loop.
 265  */
 266 #define list_for_each_safe(pos, n, head) \
 267         for (pos = (head)->next, n = pos->next; pos != (head); \
 268                 pos = n, n = pos->next)
 269
 270 /**
 271  * Iterate over a list continuing after existing point
 272  * \param pos    the type * to use as a loop counter
 273  * \param head   the list head
 274  * \param member the name of the list_struct within the struct
 275  */
 276 #define list_for_each_entry_continue(pos, head, member)                 \
 277         for (pos = list_entry(pos->member.next, typeof(*pos), member);  \
 278              prefetch(pos->member.next), &pos->member != (head);        \
 279              pos = list_entry(pos->member.next, typeof(*pos), member))
 280
 281 /**
 282  * \defgroup hlist Hash List
 283  * Double linked lists with a single pointer list head.
 284  * Mostly useful for hash tables where the two pointer list head is too
 285  * wasteful.  You lose the ability to access the tail in O(1).
 286  * @{
 287  */
 288
 289 struct hlist_node {
 290         struct hlist_node *next, **pprev;
 291 };
 292
 293 struct hlist_head {
 294         struct hlist_node *first;
 295 };
 296
 297 /* @} */
 298
 299 /*
 300  * "NULL" might not be defined at this point
 301  */
 302 #ifdef NULL
 303 #define NULL_P NULL
 304 #else
 305 #define NULL_P ((void *)0)
 306 #endif
 307
 308 /**
 309  * \addtogroup hlist
 310  * @{
 311  */
 312
 313 #define HLIST_HEAD_INIT { NULL_P }
 314 #define HLIST_HEAD(name) struct hlist_head name = { NULL_P }
 315 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL_P)
 316 #define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL_P, (ptr)->pprev = NULL_P)
 317
 318 static inline int hlist_unhashed(const struct hlist_node *h)
 319 {
 320         return !h->pprev;
 321 }
 322
 323 static inline int hlist_empty(const struct hlist_head *h)
 324 {
 325         return !h->first;
 326 }
 327
 328 static inline void __hlist_del(struct hlist_node *n)
 329 {
 330         struct hlist_node *next = n->next;
 331         struct hlist_node **pprev = n->pprev;
 332         *pprev = next;
 333         if (next)
 334                 next->pprev = pprev;
 335 }
 336
 337 static inline void hlist_del(struct hlist_node *n)
 338 {
 339         __hlist_del(n);
 340 }
 341
 342 static inline void hlist_del_init(struct hlist_node *n)
 343 {
 344         if (n->pprev)  {
 345                 __hlist_del(n);
 346                 INIT_HLIST_NODE(n);
 347         }
 348 }
 349
 350 static inline void hlist_add_head(struct hlist_node *n,
 351                                       struct hlist_head *h)
 352 {
 353         struct hlist_node *first = h->first;
 354         n->next = first;
 355         if (first)
 356                 first->pprev = &n->next;
 357         h->first = n;
 358         n->pprev = &h->first;
 359 }
 360
 361 /* next must be != NULL */
 362 static inline void hlist_add_before(struct hlist_node *n,
 363                                         struct hlist_node *next)
 364 {
 365         n->pprev = next->pprev;
 366         n->next = next;
 367         next->pprev = &n->next;
 368         *(n->pprev) = n;
 369 }
 370
 371 static inline void hlist_add_after(struct hlist_node *n,
 372                                        struct hlist_node *next)
 373 {
 374         next->next = n->next;
 375         n->next = next;
 376         next->pprev = &n->next;
 377
 378         if(next->next)
 379                 next->next->pprev  = &next->next;
 380 }
 381
 382 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
 383
 384 #define hlist_for_each(pos, head) \
 385         for (pos = (head)->first; pos && (prefetch(pos->next), 1); \
 386              pos = pos->next)
 387
 388 #define hlist_for_each_safe(pos, n, head) \
 389         for (pos = (head)->first; pos && (n = pos->next, 1); \
 390              pos = n)
 391
 392 /**
 393  * Iterate over an hlist of given type
 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 head   the head for your list.
 397  * \param member the name of the hlist_node within the struct.
 398  */
 399 #define hlist_for_each_entry(tpos, pos, head, member)                    \
 400         for (pos = (head)->first;                                            \
 401              pos && ({ prefetch(pos->next); 1;}) &&                          \
 402                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 403              pos = pos->next)
 404
 405 /**
 406  * Iterate over an hlist continuing after existing point
 407  * \param tpos   the type * to use as a loop counter.
 408  * \param pos    the &struct hlist_node to use as a loop counter.
 409  * \param member the name of the hlist_node within the struct.
 410  */
 411 #define hlist_for_each_entry_continue(tpos, pos, member)                 \
 412         for (pos = (pos)->next;                                              \
 413              pos && ({ prefetch(pos->next); 1;}) &&                          \
 414                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 415              pos = pos->next)
 416
 417 /**
 418  * Iterate over an hlist continuing from an existing point
 419  * \param tpos   the type * to use as a loop counter.
 420  * \param pos    the &struct hlist_node to use as a loop counter.
 421  * \param member the name of the hlist_node within the struct.
 422  */
 423 #define hlist_for_each_entry_from(tpos, pos, member)                     \
 424         for (; pos && ({ prefetch(pos->next); 1;}) &&                        \
 425                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 426              pos = pos->next)
 427
 428 /**
 429  * Iterate over an hlist of given type safe against removal of list entry
 430  * \param tpos   the type * to use as a loop counter.
 431  * \param pos    the &struct hlist_node to use as a loop counter.
 432  * \param n      another &struct hlist_node to use as temporary storage
 433  * \param head   the head for your list.
 434  * \param member the name of the hlist_node within the struct.
 435  */
 436 #define hlist_for_each_entry_safe(tpos, pos, n, head, member)            \
 437         for (pos = (head)->first;                                            \
 438              pos && ({ n = pos->next; 1; }) &&                               \
 439                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 440              pos = n)
 441
 442 /* @} */
 443
 444 /**
 445  * Iterate over a list in reverse order
 446  * \param pos   the &struct list_head to use as a loop counter.
 447  * \param head  the head for your list.
 448  */
 449 #define list_for_each_prev(pos, head) \
 450         for (pos = (head)->prev, prefetch(pos->prev); pos != (head);     \
 451                 pos = pos->prev, prefetch(pos->prev))
 452
 453 /**
 454  * Iterate over a list of given type
 455  * \param pos        the type * to use as a loop counter.
 456  * \param head       the head for your list.
 457  * \param member     the name of the list_struct within the struct.
 458  */
 459 #define list_for_each_entry(pos, head, member)                          \
 460         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 461                      prefetch(pos->member.next);                            \
 462              &pos->member != (head);                                        \
 463              pos = list_entry(pos->member.next, typeof(*pos), member),  \
 464              prefetch(pos->member.next))
 465
 466 /**
 467  * Iterate backwards over a list of given type.
 468  * \param pos        the type * to use as a loop counter.
 469  * \param head       the head for your list.
 470  * \param member     the name of the list_struct within the struct.
 471  */
 472 #define list_for_each_entry_reverse(pos, head, member)                  \
 473         for (pos = list_entry((head)->prev, typeof(*pos), member);      \
 474              prefetch(pos->member.prev), &pos->member != (head);            \
 475              pos = list_entry(pos->member.prev, typeof(*pos), member))
 476
 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 /* __KERNEL__ */
 491
 492 #ifdef HAVE_HLIST_FOR_EACH_3ARG
 493 #define cfs_hlist_for_each_entry(tpos, pos, head, member) \
 494         hlist_for_each_entry(tpos, head, member)
 495 #define cfs_hlist_for_each_entry_safe(tpos, pos, n, head, member) \
 496         hlist_for_each_entry_safe(tpos, n, head, member)
 497 #define cfs_hlist_for_each_entry_continue(tpos, pos, member) \
 498         hlist_for_each_entry_continue(tpos, member)
 499 #define cfs_hlist_for_each_entry_from(tpos, pos, member) \
 500         hlist_for_each_entry_from(tpos, member)
 501 #else
 502 #define cfs_hlist_for_each_entry(tpos, pos, head, member) \
 503         hlist_for_each_entry(tpos, pos, head, member)
 504 #define cfs_hlist_for_each_entry_safe(tpos, pos, n, head, member) \
 505         hlist_for_each_entry_safe(tpos, pos, n, head, member)
 506 #define cfs_hlist_for_each_entry_continue(tpos, pos, member) \
 507         hlist_for_each_entry_continue(tpos, pos, member)
 508 #define cfs_hlist_for_each_entry_from(tpos, pos, member) \
 509         hlist_for_each_entry_from(tpos, pos, member)
 510 #endif
 511
 512 #ifdef HAVE_HLIST_ADD_AFTER
 513 #define hlist_add_behind(hnode, tail)   hlist_add_after(tail, hnode)
 514 #endif /* HAVE_HLIST_ADD_AFTER */
 515
 516 #endif /* __LIBCFS_LUSTRE_LIST_H__ */