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 #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 #ifndef __WINNT__
  32 #define prefetch(a) ((void)a)
  33 #else
  34 #define prefetch(a) ((void *)a)
  35 #endif
  36
  37 struct list_head {
  38         struct list_head *next, *prev;
  39 };
  40
  41 typedef struct list_head list_t;
  42
  43 #define CFS_LIST_HEAD_INIT(name) { &(name), &(name) }
  44
  45 #define CFS_LIST_HEAD(name) \
  46         struct list_head name = LIST_HEAD_INIT(name)
  47
  48 #define CFS_INIT_LIST_HEAD(ptr) do { \
  49         (ptr)->next = (ptr); (ptr)->prev = (ptr); \
  50 } while (0)
  51
  52 #ifndef __APPLE__
  53 #define LIST_HEAD(n)            CFS_LIST_HEAD(n)
  54 #endif
  55
  56 #define LIST_HEAD_INIT(n)       CFS_LIST_HEAD_INIT(n)
  57 #define INIT_LIST_HEAD(p)       CFS_INIT_LIST_HEAD(p)
  58
  59 /*
  60  * Insert a new entry between two known consecutive entries.
  61  *
  62  * This is only for internal list manipulation where we know
  63  * the prev/next entries already!
  64  */
  65 static inline void __list_add(struct list_head * new,
  66                               struct list_head * prev,
  67                               struct list_head * next)
  68 {
  69         next->prev = new;
  70         new->next = next;
  71         new->prev = prev;
  72         prev->next = new;
  73 }
  74
  75 /**
  76  * list_add - add a new entry
  77  * @new: new entry to be added
  78  * @head: list head to add it after
  79  *
  80  * Insert a new entry after the specified head.
  81  * This is good for implementing stacks.
  82  */
  83 static inline void list_add(struct list_head *new, struct list_head *head)
  84 {
  85         __list_add(new, head, head->next);
  86 }
  87
  88 /**
  89  * list_add_tail - add a new entry
  90  * @new: new entry to be added
  91  * @head: list head to add it before
  92  *
  93  * Insert a new entry before the specified head.
  94  * This is useful for implementing queues.
  95  */
  96 static inline void list_add_tail(struct list_head *new, struct list_head *head)
  97 {
  98         __list_add(new, head->prev, head);
  99 }
 100
 101 /*
 102  * Delete a list entry by making the prev/next entries
 103  * point to each other.
 104  *
 105  * This is only for internal list manipulation where we know
 106  * the prev/next entries already!
 107  */
 108 static inline void __list_del(struct list_head * prev, struct list_head * next)
 109 {
 110         next->prev = prev;
 111         prev->next = next;
 112 }
 113
 114 /**
 115  * list_del - deletes entry from list.
 116  * @entry: the element to delete from the list.
 117  * Note: list_empty on entry does not return true after this, the entry is in an undefined state.
 118  */
 119 static inline void list_del(struct list_head *entry)
 120 {
 121         __list_del(entry->prev, entry->next);
 122 }
 123
 124 /**
 125  * list_del_init - deletes entry from list and reinitialize it.
 126  * @entry: the element to delete from the list.
 127  */
 128 static inline void list_del_init(struct list_head *entry)
 129 {
 130         __list_del(entry->prev, entry->next);
 131         CFS_INIT_LIST_HEAD(entry);
 132 }
 133
 134 /**
 135  * list_move - delete from one list and add as another's head
 136  * @list: the entry to move
 137  * @head: the head that will precede our entry
 138  *
 139  * This is not safe to use if @list is already on the same list as @head.
 140  */
 141 static inline void list_move(struct list_head *list, struct list_head *head)
 142 {
 143         __list_del(list->prev, list->next);
 144         list_add(list, head);
 145 }
 146
 147 /**
 148  * list_move_tail - delete from one list and add as another's tail
 149  * @list: the entry to move
 150  * @head: the head that will follow our entry
 151  *
 152  * This is not safe to use if @list is already on the same list as @head.
 153  */
 154 static inline void list_move_tail(struct list_head *list,
 155                                   struct list_head *head)
 156 {
 157         __list_del(list->prev, list->next);
 158         list_add_tail(list, head);
 159 }
 160
 161 /**
 162  * list_empty - tests whether a list is empty
 163  * @head: the list to test.
 164  */
 165 static inline int list_empty(struct list_head *head)
 166 {
 167         return head->next == head;
 168 }
 169
 170 static inline void __list_splice(struct list_head *list,
 171                                  struct list_head *head)
 172 {
 173         struct list_head *first = list->next;
 174         struct list_head *last = list->prev;
 175         struct list_head *at = head->next;
 176
 177         first->prev = head;
 178         head->next = first;
 179
 180         last->next = at;
 181         at->prev = last;
 182 }
 183
 184 /**
 185  * list_splice - join two lists
 186  * @list: the new list to add.
 187  * @head: the place to add it in the first list.
 188  */
 189 static inline void list_splice(struct list_head *list, struct list_head *head)
 190 {
 191         if (!list_empty(list))
 192                 __list_splice(list, head);
 193 }
 194
 195 /**
 196  * list_splice_init - join two lists and reinitialise the emptied list.
 197  * @list: the new list to add.
 198  * @head: the place to add it in the first list.
 199  *
 200  * The list at @list is reinitialised
 201  */
 202 static inline void list_splice_init(struct list_head *list,
 203                                     struct list_head *head)
 204 {
 205         if (!list_empty(list)) {
 206                 __list_splice(list, head);
 207                 CFS_INIT_LIST_HEAD(list);
 208         }
 209 }
 210
 211 /**
 212  * list_entry - get the struct for this entry
 213  * @ptr:        the &struct list_head pointer.
 214  * @type:       the type of the struct this is embedded in.
 215  * @member:     the name of the list_struct within the struct.
 216  */
 217 #define list_entry(ptr, type, member) \
 218         ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
 219
 220 /**
 221  * list_for_each        -       iterate over a list
 222  * @pos:        the &struct list_head to use as a loop counter.
 223  * @head:       the head for your list.
 224  */
 225 #define list_for_each(pos, head) \
 226         for (pos = (head)->next, prefetch(pos->next); pos != (head); \
 227                 pos = pos->next, prefetch(pos->next))
 228
 229 /**
 230  * list_for_each_safe   -       iterate over a list safe against removal of list entry
 231  * @pos:        the &struct list_head to use as a loop counter.
 232  * @n:          another &struct list_head to use as temporary storage
 233  * @head:       the head for your list.
 234  */
 235 #define list_for_each_safe(pos, n, head) \
 236         for (pos = (head)->next, n = pos->next; pos != (head); \
 237                 pos = n, n = pos->next)
 238
 239 /*
 240  * Double linked lists with a single pointer list head.
 241  * Mostly useful for hash tables where the two pointer list head is
 242  * too wasteful.
 243  * You lose the ability to access the tail in O(1).
 244  */
 245
 246 struct hlist_head {
 247         struct hlist_node *first;
 248 };
 249
 250 struct hlist_node {
 251         struct hlist_node *next, **pprev;
 252 };
 253
 254 /*
 255  * "NULL" might not be defined at this point
 256  */
 257 #ifdef NULL
 258 #define NULL_P NULL
 259 #else
 260 #define NULL_P ((void *)0)
 261 #endif
 262
 263 #define CFS_HLIST_HEAD_INIT { .first = NULL_P }
 264 #define CFS_HLIST_HEAD(name) struct hlist_head name = {  .first = NULL_P }
 265 #define CFS_INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL_P)
 266 #define CFS_INIT_HLIST_NODE(ptr) ((ptr)->next = NULL_P, (ptr)->pprev = NULL_P)
 267
 268 #define HLIST_HEAD_INIT         CFS_HLIST_HEAD_INIT
 269 #define HLIST_HEAD(n)           CFS_HLIST_HEAD(n)
 270 #define INIT_HLIST_HEAD(p)      CFS_INIT_HLIST_HEAD(p)
 271 #define INIT_HLIST_NODE(p)      CFS_INIT_HLIST_NODE(p)
 272
 273 static inline int hlist_unhashed(const struct hlist_node *h)
 274 {
 275         return !h->pprev;
 276 }
 277
 278 static inline int hlist_empty(const struct hlist_head *h)
 279 {
 280         return !h->first;
 281 }
 282
 283 static inline void __hlist_del(struct hlist_node *n)
 284 {
 285         struct hlist_node *next = n->next;
 286         struct hlist_node **pprev = n->pprev;
 287         *pprev = next;
 288         if (next)
 289                 next->pprev = pprev;
 290 }
 291
 292 static inline void hlist_del(struct hlist_node *n)
 293 {
 294         __hlist_del(n);
 295 }
 296
 297 static inline void hlist_del_init(struct hlist_node *n)
 298 {
 299         if (n->pprev)  {
 300                 __hlist_del(n);
 301                 INIT_HLIST_NODE(n);
 302         }
 303 }
 304
 305 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 306 {
 307         struct hlist_node *first = h->first;
 308         n->next = first;
 309         if (first)
 310                 first->pprev = &n->next;
 311         h->first = n;
 312         n->pprev = &h->first;
 313 }
 314
 315 /* next must be != NULL */
 316 static inline void hlist_add_before(struct hlist_node *n,
 317                                         struct hlist_node *next)
 318 {
 319         n->pprev = next->pprev;
 320         n->next = next;
 321         next->pprev = &n->next;
 322         *(n->pprev) = n;
 323 }
 324
 325 static inline void hlist_add_after(struct hlist_node *n,
 326                                         struct hlist_node *next)
 327 {
 328         next->next = n->next;
 329         n->next = next;
 330         next->pprev = &n->next;
 331
 332         if(next->next)
 333                 next->next->pprev  = &next->next;
 334 }
 335
 336 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
 337
 338 #define hlist_for_each(pos, head) \
 339         for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
 340              pos = pos->next)
 341
 342 #define hlist_for_each_safe(pos, n, head) \
 343         for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
 344              pos = n)
 345
 346 /**
 347  * hlist_for_each_entry - iterate over list of given type
 348  * @tpos:       the type * to use as a loop counter.
 349  * @pos:        the &struct hlist_node to use as a loop counter.
 350  * @head:       the head for your list.
 351  * @member:     the name of the hlist_node within the struct.
 352  */
 353 #define hlist_for_each_entry(tpos, pos, head, member)                    \
 354         for (pos = (head)->first;                                        \
 355              pos && ({ prefetch(pos->next); 1;}) &&                      \
 356                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 357              pos = pos->next)
 358
 359 /**
 360  * hlist_for_each_entry_continue - iterate over a hlist continuing after existing point
 361  * @tpos:       the type * to use as a loop counter.
 362  * @pos:        the &struct hlist_node to use as a loop counter.
 363  * @member:     the name of the hlist_node within the struct.
 364  */
 365 #define hlist_for_each_entry_continue(tpos, pos, member)                 \
 366         for (pos = (pos)->next;                                          \
 367              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_from - iterate over a hlist continuing from existing point
 373  * @tpos:       the type * to use as a loop counter.
 374  * @pos:        the &struct hlist_node to use as a loop counter.
 375  * @member:     the name of the hlist_node within the struct.
 376  */
 377 #define hlist_for_each_entry_from(tpos, pos, member)                     \
 378         for (; pos && ({ prefetch(pos->next); 1;}) &&                    \
 379                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 380              pos = pos->next)
 381
 382 /**
 383  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 384  * @tpos:       the type * to use as a loop counter.
 385  * @pos:        the &struct hlist_node to use as a loop counter.
 386  * @n:          another &struct hlist_node to use as temporary storage
 387  * @head:       the head for your list.
 388  * @member:     the name of the hlist_node within the struct.
 389  */
 390 #define hlist_for_each_entry_safe(tpos, pos, n, head, member)            \
 391         for (pos = (head)->first;                                        \
 392              pos && ({ n = pos->next; 1; }) &&                           \
 393                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 394              pos = n)
 395
 396 #endif /* __linux__ && __KERNEL__ */
 397
 398 #ifndef list_for_each_prev
 399 /**
 400  * list_for_each_prev   -       iterate over a list in reverse order
 401  * @pos:        the &struct list_head to use as a loop counter.
 402  * @head:       the head for your list.
 403  */
 404 #define list_for_each_prev(pos, head) \
 405         for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \
 406                 pos = pos->prev, prefetch(pos->prev))
 407
 408 #endif /* list_for_each_prev */
 409
 410 #ifndef list_for_each_entry
 411 /**
 412  * list_for_each_entry  -       iterate over list of given type
 413  * @pos:        the type * to use as a loop counter.
 414  * @head:       the head for your list.
 415  * @member:     the name of the list_struct within the struct.
 416  */
 417 #define list_for_each_entry(pos, head, member)                          \
 418         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 419                      prefetch(pos->member.next);                        \
 420              &pos->member != (head);                                    \
 421              pos = list_entry(pos->member.next, typeof(*pos), member),  \
 422              prefetch(pos->member.next))
 423 #endif /* list_for_each_entry */
 424
 425 #ifndef list_for_each_entry_reverse
 426 /**
 427  * list_for_each_entry_reverse - iterate backwards over list of given type.
 428  * @pos:        the type * to use as a loop counter.
 429  * @head:       the head for your list.
 430  * @member:     the name of the list_struct within the struct.
 431  */
 432 #define list_for_each_entry_reverse(pos, head, member)                  \
 433         for (pos = list_entry((head)->prev, typeof(*pos), member);      \
 434              prefetch(pos->member.prev), &pos->member != (head);        \
 435              pos = list_entry(pos->member.prev, typeof(*pos), member))
 436 #endif /* list_for_each_entry_reverse */
 437
 438 #ifndef list_for_each_entry_safe
 439 /**
 440  * list_for_each_entry_safe  -       iterate over list of given type safe against removal of list entry
 441  * @pos:        the type * to use as a loop counter.
 442  * @n:          another type * to use as temporary storage
 443  * @head:       the head for your list.
 444  * @member:     the name of the list_struct within the struct.
 445  */
 446 #define list_for_each_entry_safe(pos, n, head, member)                  \
 447         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 448                 n = list_entry(pos->member.next, typeof(*pos), member); \
 449              &pos->member != (head);                                    \
 450              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 451 #endif /* list_for_each_entry_safe */
 452
 453 #endif /* __LIBCFS_LUSTRE_LIST_H__ */