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