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  * 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  * This is not safe to use if @list is already on the same list as @head.
 129  */
 130 static inline void list_move(struct list_head *list, struct list_head *head)
 131 {
 132         __list_del(list->prev, list->next);
 133         list_add(list, head);
 134 }
 135
 136 /**
 137  * list_move_tail - delete from one list and add as another's tail
 138  * @list: the entry to move
 139  * @head: the head that will follow our entry
 140  *
 141  * This is not safe to use if @list is already on the same list as @head.
 142  */
 143 static inline void list_move_tail(struct list_head *list,
 144                                   struct list_head *head)
 145 {
 146         __list_del(list->prev, list->next);
 147         list_add_tail(list, head);
 148 }
 149
 150 /**
 151  * list_empty - tests whether a list is empty
 152  * @head: the list to test.
 153  */
 154 static inline int list_empty(struct list_head *head)
 155 {
 156         return head->next == head;
 157 }
 158
 159 static inline void __list_splice(struct list_head *list,
 160                                  struct list_head *head)
 161 {
 162         struct list_head *first = list->next;
 163         struct list_head *last = list->prev;
 164         struct list_head *at = head->next;
 165
 166         first->prev = head;
 167         head->next = first;
 168
 169         last->next = at;
 170         at->prev = last;
 171 }
 172
 173 /**
 174  * list_splice - join two lists
 175  * @list: the new list to add.
 176  * @head: the place to add it in the first list.
 177  */
 178 static inline void list_splice(struct list_head *list, struct list_head *head)
 179 {
 180         if (!list_empty(list))
 181                 __list_splice(list, head);
 182 }
 183
 184 /**
 185  * list_splice_init - join two lists and reinitialise the emptied list.
 186  * @list: the new list to add.
 187  * @head: the place to add it in the first list.
 188  *
 189  * The list at @list is reinitialised
 190  */
 191 static inline void list_splice_init(struct list_head *list,
 192                                     struct list_head *head)
 193 {
 194         if (!list_empty(list)) {
 195                 __list_splice(list, head);
 196                 CFS_INIT_LIST_HEAD(list);
 197         }
 198 }
 199
 200 /**
 201  * list_entry - get the struct for this entry
 202  * @ptr:        the &struct list_head pointer.
 203  * @type:       the type of the struct this is embedded in.
 204  * @member:     the name of the list_struct within the struct.
 205  */
 206 #define list_entry(ptr, type, member) \
 207         ((type *)((char *)(ptr)-(char *)(&((type *)0)->member)))
 208
 209 /**
 210  * list_for_each        -       iterate over a list
 211  * @pos:        the &struct list_head to use as a loop counter.
 212  * @head:       the head for your list.
 213  */
 214 #define list_for_each(pos, head) \
 215         for (pos = (head)->next, prefetch(pos->next); pos != (head); \
 216                 pos = pos->next, prefetch(pos->next))
 217
 218 /**
 219  * list_for_each_safe   -       iterate over a list safe against removal of list entry
 220  * @pos:        the &struct list_head to use as a loop counter.
 221  * @n:          another &struct list_head to use as temporary storage
 222  * @head:       the head for your list.
 223  */
 224 #define list_for_each_safe(pos, n, head) \
 225         for (pos = (head)->next, n = pos->next; pos != (head); \
 226                 pos = n, n = pos->next)
 227
 228 /*
 229  * Double linked lists with a single pointer list head.
 230  * Mostly useful for hash tables where the two pointer list head is
 231  * too wasteful.
 232  * You lose the ability to access the tail in O(1).
 233  */
 234
 235 struct hlist_head {
 236         struct hlist_node *first;
 237 };
 238
 239 struct hlist_node {
 240         struct hlist_node *next, **pprev;
 241 };
 242
 243 /*
 244  * "NULL" might not be defined at this point
 245  */
 246 #ifdef NULL
 247 #define NULL_P NULL
 248 #else
 249 #define NULL_P ((void *)0)
 250 #endif
 251
 252 #define CFS_HLIST_HEAD_INIT { NULL_P }
 253 #define CFS_HLIST_HEAD(name) struct hlist_head name = { NULL_P }
 254 #define CFS_INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL_P)
 255 #define CFS_INIT_HLIST_NODE(ptr) ((ptr)->next = NULL_P, (ptr)->pprev = NULL_P)
 256
 257 #define HLIST_HEAD_INIT         CFS_HLIST_HEAD_INIT
 258 #define HLIST_HEAD(n)           CFS_HLIST_HEAD(n)
 259 #define INIT_HLIST_HEAD(p)      CFS_INIT_HLIST_HEAD(p)
 260 #define INIT_HLIST_NODE(p)      CFS_INIT_HLIST_NODE(p)
 261
 262 static inline int hlist_unhashed(const struct hlist_node *h)
 263 {
 264         return !h->pprev;
 265 }
 266
 267 static inline int hlist_empty(const struct hlist_head *h)
 268 {
 269         return !h->first;
 270 }
 271
 272 static inline void __hlist_del(struct hlist_node *n)
 273 {
 274         struct hlist_node *next = n->next;
 275         struct hlist_node **pprev = n->pprev;
 276         *pprev = next;
 277         if (next)
 278                 next->pprev = pprev;
 279 }
 280
 281 static inline void hlist_del(struct hlist_node *n)
 282 {
 283         __hlist_del(n);
 284 }
 285
 286 static inline void hlist_del_init(struct hlist_node *n)
 287 {
 288         if (n->pprev)  {
 289                 __hlist_del(n);
 290                 INIT_HLIST_NODE(n);
 291         }
 292 }
 293
 294 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 295 {
 296         struct hlist_node *first = h->first;
 297         n->next = first;
 298         if (first)
 299                 first->pprev = &n->next;
 300         h->first = n;
 301         n->pprev = &h->first;
 302 }
 303
 304 /* next must be != NULL */
 305 static inline void hlist_add_before(struct hlist_node *n,
 306                                         struct hlist_node *next)
 307 {
 308         n->pprev = next->pprev;
 309         n->next = next;
 310         next->pprev = &n->next;
 311         *(n->pprev) = n;
 312 }
 313
 314 static inline void hlist_add_after(struct hlist_node *n,
 315                                         struct hlist_node *next)
 316 {
 317         next->next = n->next;
 318         n->next = next;
 319         next->pprev = &n->next;
 320
 321         if(next->next)
 322                 next->next->pprev  = &next->next;
 323 }
 324
 325 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
 326
 327 #define hlist_for_each(pos, head) \
 328         for (pos = (head)->first; pos && (prefetch(pos->next), 1); \
 329              pos = pos->next)
 330
 331 #define hlist_for_each_safe(pos, n, head) \
 332         for (pos = (head)->first; pos && (n = pos->next, 1); \
 333              pos = n)
 334
 335 /**
 336  * hlist_for_each_entry - iterate over list of given type
 337  * @tpos:       the type * to use as a loop counter.
 338  * @pos:        the &struct hlist_node to use as a loop counter.
 339  * @head:       the head for your list.
 340  * @member:     the name of the hlist_node within the struct.
 341  */
 342 #define hlist_for_each_entry(tpos, pos, head, member)                    \
 343         for (pos = (head)->first;                                        \
 344              pos && ({ prefetch(pos->next); 1;}) &&                      \
 345                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 346              pos = pos->next)
 347
 348 /**
 349  * hlist_for_each_entry_continue - iterate over a hlist continuing after existing point
 350  * @tpos:       the type * to use as a loop counter.
 351  * @pos:        the &struct hlist_node to use as a loop counter.
 352  * @member:     the name of the hlist_node within the struct.
 353  */
 354 #define hlist_for_each_entry_continue(tpos, pos, member)                 \
 355         for (pos = (pos)->next;                                          \
 356              pos && ({ prefetch(pos->next); 1;}) &&                      \
 357                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 358              pos = pos->next)
 359
 360 /**
 361  * hlist_for_each_entry_from - iterate over a hlist continuing from existing point
 362  * @tpos:       the type * to use as a loop counter.
 363  * @pos:        the &struct hlist_node to use as a loop counter.
 364  * @member:     the name of the hlist_node within the struct.
 365  */
 366 #define hlist_for_each_entry_from(tpos, pos, member)                     \
 367         for (; pos && ({ prefetch(pos->next); 1;}) &&                    \
 368                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 369              pos = pos->next)
 370
 371 /**
 372  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 373  * @tpos:       the type * to use as a loop counter.
 374  * @pos:        the &struct hlist_node to use as a loop counter.
 375  * @n:          another &struct hlist_node to use as temporary storage
 376  * @head:       the head for your list.
 377  * @member:     the name of the hlist_node within the struct.
 378  */
 379 #define hlist_for_each_entry_safe(tpos, pos, n, head, member)            \
 380         for (pos = (head)->first;                                        \
 381              pos && ({ n = pos->next; 1; }) &&                           \
 382                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 383              pos = n)
 384
 385 #endif /* __linux__ && __KERNEL__ */
 386
 387 #ifndef list_for_each_prev
 388 /**
 389  * list_for_each_prev   -       iterate over a list in reverse order
 390  * @pos:        the &struct list_head to use as a loop counter.
 391  * @head:       the head for your list.
 392  */
 393 #define list_for_each_prev(pos, head) \
 394         for (pos = (head)->prev, prefetch(pos->prev); pos != (head);     \
 395                 pos = pos->prev, prefetch(pos->prev))
 396
 397 #endif /* list_for_each_prev */
 398
 399 #ifndef list_for_each_entry
 400 /**
 401  * list_for_each_entry  -       iterate over list of given type
 402  * @pos:        the type * to use as a loop counter.
 403  * @head:       the head for your list.
 404  * @member:     the name of the list_struct within the struct.
 405  */
 406 #define list_for_each_entry(pos, head, member)                          \
 407         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 408                      prefetch(pos->member.next);                        \
 409              &pos->member != (head);                                    \
 410              pos = list_entry(pos->member.next, typeof(*pos), member),  \
 411              prefetch(pos->member.next))
 412 #endif /* list_for_each_entry */
 413
 414 #ifndef list_for_each_entry_reverse
 415 /**
 416  * list_for_each_entry_reverse - iterate backwards over list of given type.
 417  * @pos:        the type * to use as a loop counter.
 418  * @head:       the head for your list.
 419  * @member:     the name of the list_struct within the struct.
 420  */
 421 #define list_for_each_entry_reverse(pos, head, member)                  \
 422         for (pos = list_entry((head)->prev, typeof(*pos), member);      \
 423              prefetch(pos->member.prev), &pos->member != (head);        \
 424              pos = list_entry(pos->member.prev, typeof(*pos), member))
 425 #endif /* list_for_each_entry_reverse */
 426
 427 #ifndef list_for_each_entry_safe
 428 /**
 429  * list_for_each_entry_safe  -       iterate over list of given type safe against removal of list entry
 430  * @pos:        the type * to use as a loop counter.
 431  * @n:          another type * to use as temporary storage
 432  * @head:       the head for your list.
 433  * @member:     the name of the list_struct within the struct.
 434  */
 435 #define list_for_each_entry_safe(pos, n, head, member)                  \
 436         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 437                 n = list_entry(pos->member.next, typeof(*pos), member); \
 438              &pos->member != (head);                                    \
 439              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 440
 441 #endif /* list_for_each_entry_safe */
 442
 443 #ifndef list_for_each_entry_safe_from
 444 /**
 445  * list_for_each_entry_safe_from
 446  * @pos:        the type * to use as a loop cursor.
 447  * @n:          another type * to use as temporary storage
 448  * @head:       the head for your list.
 449  * @member:     the name of the list_struct within the struct.
 450  *
 451  * Iterate over list of given type from current point, safe against
 452  * removal of list entry.
 453  */
 454 #define list_for_each_entry_safe_from(pos, n, head, member)             \
 455         for (n = list_entry(pos->member.next, typeof(*pos), member);    \
 456              &pos->member != (head);                                    \
 457              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 458 #endif /* list_for_each_entry_safe_from */
 459
 460 #define cfs_list_for_each_entry_typed(pos, head, type, member)          \
 461         for (pos = list_entry((head)->next, type, member),              \
 462                      prefetch(pos->member.next);                        \
 463              &pos->member != (head);                                    \
 464              pos = list_entry(pos->member.next, type, member),          \
 465              prefetch(pos->member.next))
 466
 467 #define cfs_list_for_each_entry_reverse_typed(pos, head, type, member)  \
 468         for (pos = list_entry((head)->prev, type, member);              \
 469              prefetch(pos->member.prev), &pos->member != (head);        \
 470              pos = list_entry(pos->member.prev, type, member))
 471
 472 #define cfs_list_for_each_entry_safe_typed(pos, n, head, type, member)  \
 473     for (pos = list_entry((head)->next, type, member),                  \
 474                 n = list_entry(pos->member.next, type, member);         \
 475              &pos->member != (head);                                    \
 476              pos = n, n = list_entry(n->member.next, type, member))
 477
 478 #define cfs_list_for_each_entry_safe_from_typed(pos, n, head, type, member)   \
 479         for (n = list_entry(pos->member.next, type, member);            \
 480              &pos->member != (head);                                    \
 481              pos = n, n = list_entry(n->member.next, type, member))
 482 #define cfs_hlist_for_each_entry_typed(tpos, pos, head, type, member)   \
 483         for (pos = (head)->first;                                       \
 484              pos && (prefetch(pos->next), 1) &&                         \
 485                 (tpos = hlist_entry(pos, type, member), 1);             \
 486              pos = pos->next)
 487
 488 #define cfs_hlist_for_each_entry_safe_typed(tpos, pos, n, head, type, member)\
 489         for (pos = (head)->first;                                       \
 490              pos && (n = pos->next, 1) &&                               \
 491                 (tpos = hlist_entry(pos, type, member), 1);             \
 492              pos = n)
 493
 494 #endif /* __LIBCFS_LUSTRE_LIST_H__ */