datapath/linux-2.4/compat-2.4/include/linux/list.h

   1 #ifndef __LINUX_LIST_WRAPPER_H
   2 #define __LINUX_LIST_WRAPPER_H
   3
   4 #ifdef __KERNEL__
   5
   6 #include_next <linux/list.h>
   7 #include <asm/system.h>
   8
   9 #define LIST_POISON1  ((void *) 0x00100100)
  10 #define LIST_POISON2  ((void *) 0x00200200)
  11
  12 /*
  13  * Insert a new entry between two known consecutive entries.
  14  *
  15  * This is only for internal list manipulation where we know
  16  * the prev/next entries already!
  17  */
  18 static inline void __list_add_rcu(struct list_head * new,
  19                 struct list_head * prev, struct list_head * next)
  20 {
  21         new->next = next;
  22         new->prev = prev;
  23         smp_wmb();
  24         next->prev = new;
  25         prev->next = new;
  26 }
  27
  28 /**
  29  * list_add_rcu - add a new entry to rcu-protected list
  30  * @new: new entry to be added
  31  * @head: list head to add it after
  32  *
  33  * Insert a new entry after the specified head.
  34  * This is good for implementing stacks.
  35  *
  36  * The caller must take whatever precautions are necessary
  37  * (such as holding appropriate locks) to avoid racing
  38  * with another list-mutation primitive, such as list_add_rcu()
  39  * or list_del_rcu(), running on this same list.
  40  * However, it is perfectly legal to run concurrently with
  41  * the _rcu list-traversal primitives, such as
  42  * list_for_each_entry_rcu().
  43  */
  44 static inline void list_add_rcu(struct list_head *new, struct list_head *head)
  45 {
  46         __list_add_rcu(new, head, head->next);
  47 }
  48
  49 /**
  50  * list_add_tail_rcu - add a new entry to rcu-protected list
  51  * @new: new entry to be added
  52  * @head: list head to add it before
  53  *
  54  * Insert a new entry before the specified head.
  55  * This is useful for implementing queues.
  56  *
  57  * The caller must take whatever precautions are necessary
  58  * (such as holding appropriate locks) to avoid racing
  59  * with another list-mutation primitive, such as list_add_tail_rcu()
  60  * or list_del_rcu(), running on this same list.
  61  * However, it is perfectly legal to run concurrently with
  62  * the _rcu list-traversal primitives, such as
  63  * list_for_each_entry_rcu().
  64  */
  65 static inline void list_add_tail_rcu(struct list_head *new,
  66                                         struct list_head *head)
  67 {
  68         __list_add_rcu(new, head->prev, head);
  69 }
  70
  71 /**
  72  * list_del_rcu - deletes entry from list without re-initialization
  73  * @entry: the element to delete from the list.
  74  *
  75  * Note: list_empty() on entry does not return true after this,
  76  * the entry is in an undefined state. It is useful for RCU based
  77  * lockfree traversal.
  78  *
  79  * In particular, it means that we can not poison the forward
  80  * pointers that may still be used for walking the list.
  81  *
  82  * The caller must take whatever precautions are necessary
  83  * (such as holding appropriate locks) to avoid racing
  84  * with another list-mutation primitive, such as list_del_rcu()
  85  * or list_add_rcu(), running on this same list.
  86  * However, it is perfectly legal to run concurrently with
  87  * the _rcu list-traversal primitives, such as
  88  * list_for_each_entry_rcu().
  89  *
  90  * Note that the caller is not permitted to immediately free
  91  * the newly deleted entry.  Instead, either synchronize_rcu()
  92  * or call_rcu() must be used to defer freeing until an RCU
  93  * grace period has elapsed.
  94  */
  95 static inline void list_del_rcu(struct list_head *entry)
  96 {
  97         __list_del(entry->prev, entry->next);
  98         entry->prev = LIST_POISON2;
  99 }
 100
 101 /**
 102  * list_replace_rcu - replace old entry by new one
 103  * @old : the element to be replaced
 104  * @new : the new element to insert
 105  *
 106  * The @old entry will be replaced with the @new entry atomically.
 107  * Note: @old should not be empty.
 108  */
 109 static inline void list_replace_rcu(struct list_head *old,
 110                                 struct list_head *new)
 111 {
 112         new->next = old->next;
 113         new->prev = old->prev;
 114         smp_wmb();
 115         new->next->prev = new;
 116         new->prev->next = new;
 117         old->prev = LIST_POISON2;
 118 }
 119 /**
 120  * list_for_each_rcu    -       iterate over an rcu-protected list
 121  * @pos:        the &struct list_head to use as a loop cursor.
 122  * @head:       the head for your list.
 123  *
 124  * This list-traversal primitive may safely run concurrently with
 125  * the _rcu list-mutation primitives such as list_add_rcu()
 126  * as long as the traversal is guarded by rcu_read_lock().
 127  */
 128 #define list_for_each_rcu(pos, head) \
 129         for (pos = (head)->next; \
 130                 prefetch(rcu_dereference(pos)->next), pos != (head); \
 131                         pos = pos->next)
 132
 133 #define __list_for_each_rcu(pos, head) \
 134         for (pos = (head)->next; \
 135                 rcu_dereference(pos) != (head); \
 136                         pos = pos->next)
 137
 138 /**
 139  * list_for_each_safe_rcu
 140  * @pos:        the &struct list_head to use as a loop cursor.
 141  * @n:          another &struct list_head to use as temporary storage
 142  * @head:       the head for your list.
 143  *
 144  * Iterate over an rcu-protected list, safe against removal of list entry.
 145  *
 146  * This list-traversal primitive may safely run concurrently with
 147  * the _rcu list-mutation primitives such as list_add_rcu()
 148  * as long as the traversal is guarded by rcu_read_lock().
 149  */
 150 #define list_for_each_safe_rcu(pos, n, head) \
 151         for (pos = (head)->next; \
 152                 n = rcu_dereference(pos)->next, pos != (head); \
 153                 pos = n)
 154
 155 /**
 156  * list_for_each_entry_rcu      -       iterate over rcu list of given type
 157  * @pos:        the type * to use as a loop cursor.
 158  * @head:       the head for your list.
 159  * @member:     the name of the list_struct within the struct.
 160  *
 161  * This list-traversal primitive may safely run concurrently with
 162  * the _rcu list-mutation primitives such as list_add_rcu()
 163  * as long as the traversal is guarded by rcu_read_lock().
 164  */
 165 #define list_for_each_entry_rcu(pos, head, member) \
 166         for (pos = list_entry((head)->next, typeof(*pos), member); \
 167                 prefetch(rcu_dereference(pos)->member.next), \
 168                         &pos->member != (head); \
 169                 pos = list_entry(pos->member.next, typeof(*pos), member))
 170
 171
 172 /**
 173  * list_for_each_continue_rcu
 174  * @pos:        the &struct list_head to use as a loop cursor.
 175  * @head:       the head for your list.
 176  *
 177  * Iterate over an rcu-protected list, continuing after current point.
 178  *
 179  * This list-traversal primitive may safely run concurrently with
 180  * the _rcu list-mutation primitives such as list_add_rcu()
 181  * as long as the traversal is guarded by rcu_read_lock().
 182  */
 183 #define list_for_each_continue_rcu(pos, head) \
 184         for ((pos) = (pos)->next; \
 185                 prefetch(rcu_dereference((pos))->next), (pos) != (head); \
 186                         (pos) = (pos)->next)
 187
 188 /*
 189  * Double linked lists with a single pointer list head.
 190  * Mostly useful for hash tables where the two pointer list head is
 191  * too wasteful.
 192  * You lose the ability to access the tail in O(1).
 193  */
 194
 195 struct hlist_head {
 196         struct hlist_node *first;
 197 };
 198
 199 struct hlist_node {
 200         struct hlist_node *next, **pprev;
 201 };
 202
 203 #define HLIST_HEAD_INIT { .first = NULL }
 204 #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
 205 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
 206 static inline void INIT_HLIST_NODE(struct hlist_node *h)
 207 {
 208         h->next = NULL;
 209         h->pprev = NULL;
 210 }
 211
 212 static inline int hlist_unhashed(const struct hlist_node *h)
 213 {
 214         return !h->pprev;
 215 }
 216
 217 static inline int hlist_empty(const struct hlist_head *h)
 218 {
 219         return !h->first;
 220 }
 221
 222 static inline void __hlist_del(struct hlist_node *n)
 223 {
 224         struct hlist_node *next = n->next;
 225         struct hlist_node **pprev = n->pprev;
 226         *pprev = next;
 227         if (next)
 228                 next->pprev = pprev;
 229 }
 230
 231 static inline void hlist_del(struct hlist_node *n)
 232 {
 233         __hlist_del(n);
 234         n->next = LIST_POISON1;
 235         n->pprev = LIST_POISON2;
 236 }
 237
 238 /**
 239  * hlist_del_rcu - deletes entry from hash list without re-initialization
 240  * @n: the element to delete from the hash list.
 241  *
 242  * Note: list_unhashed() on entry does not return true after this,
 243  * the entry is in an undefined state. It is useful for RCU based
 244  * lockfree traversal.
 245  *
 246  * In particular, it means that we can not poison the forward
 247  * pointers that may still be used for walking the hash list.
 248  *
 249  * The caller must take whatever precautions are necessary
 250  * (such as holding appropriate locks) to avoid racing
 251  * with another list-mutation primitive, such as hlist_add_head_rcu()
 252  * or hlist_del_rcu(), running on this same list.
 253  * However, it is perfectly legal to run concurrently with
 254  * the _rcu list-traversal primitives, such as
 255  * hlist_for_each_entry().
 256  */
 257 static inline void hlist_del_rcu(struct hlist_node *n)
 258 {
 259         __hlist_del(n);
 260         n->pprev = LIST_POISON2;
 261 }
 262
 263 static inline void hlist_del_init(struct hlist_node *n)
 264 {
 265         if (!hlist_unhashed(n)) {
 266                 __hlist_del(n);
 267                 INIT_HLIST_NODE(n);
 268         }
 269 }
 270
 271 /**
 272  * hlist_replace_rcu - replace old entry by new one
 273  * @old : the element to be replaced
 274  * @new : the new element to insert
 275  *
 276  * The @old entry will be replaced with the @new entry atomically.
 277  */
 278 static inline void hlist_replace_rcu(struct hlist_node *old,
 279                                         struct hlist_node *new)
 280 {
 281         struct hlist_node *next = old->next;
 282
 283         new->next = next;
 284         new->pprev = old->pprev;
 285         smp_wmb();
 286         if (next)
 287                 new->next->pprev = &new->next;
 288         *new->pprev = new;
 289         old->pprev = LIST_POISON2;
 290 }
 291
 292 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 293 {
 294         struct hlist_node *first = h->first;
 295         n->next = first;
 296         if (first)
 297                 first->pprev = &n->next;
 298         h->first = n;
 299         n->pprev = &h->first;
 300 }
 301
 302
 303 /**
 304  * hlist_add_head_rcu
 305  * @n: the element to add to the hash list.
 306  * @h: the list to add to.
 307  *
 308  * Description:
 309  * Adds the specified element to the specified hlist,
 310  * while permitting racing traversals.
 311  *
 312  * The caller must take whatever precautions are necessary
 313  * (such as holding appropriate locks) to avoid racing
 314  * with another list-mutation primitive, such as hlist_add_head_rcu()
 315  * or hlist_del_rcu(), running on this same list.
 316  * However, it is perfectly legal to run concurrently with
 317  * the _rcu list-traversal primitives, such as
 318  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
 319  * problems on Alpha CPUs.  Regardless of the type of CPU, the
 320  * list-traversal primitive must be guarded by rcu_read_lock().
 321  */
 322 static inline void hlist_add_head_rcu(struct hlist_node *n,
 323                                         struct hlist_head *h)
 324 {
 325         struct hlist_node *first = h->first;
 326         n->next = first;
 327         n->pprev = &h->first;
 328         smp_wmb();
 329         if (first)
 330                 first->pprev = &n->next;
 331         h->first = n;
 332 }
 333
 334 /* next must be != NULL */
 335 static inline void hlist_add_before(struct hlist_node *n,
 336                                         struct hlist_node *next)
 337 {
 338         n->pprev = next->pprev;
 339         n->next = next;
 340         next->pprev = &n->next;
 341         *(n->pprev) = n;
 342 }
 343
 344 static inline void hlist_add_after(struct hlist_node *n,
 345                                         struct hlist_node *next)
 346 {
 347         next->next = n->next;
 348         n->next = next;
 349         next->pprev = &n->next;
 350
 351         if(next->next)
 352                 next->next->pprev  = &next->next;
 353 }
 354
 355 /**
 356  * hlist_add_before_rcu
 357  * @n: the new element to add to the hash list.
 358  * @next: the existing element to add the new element before.
 359  *
 360  * Description:
 361  * Adds the specified element to the specified hlist
 362  * before the specified node while permitting racing traversals.
 363  *
 364  * The caller must take whatever precautions are necessary
 365  * (such as holding appropriate locks) to avoid racing
 366  * with another list-mutation primitive, such as hlist_add_head_rcu()
 367  * or hlist_del_rcu(), running on this same list.
 368  * However, it is perfectly legal to run concurrently with
 369  * the _rcu list-traversal primitives, such as
 370  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
 371  * problems on Alpha CPUs.
 372  */
 373 static inline void hlist_add_before_rcu(struct hlist_node *n,
 374                                         struct hlist_node *next)
 375 {
 376         n->pprev = next->pprev;
 377         n->next = next;
 378         smp_wmb();
 379         next->pprev = &n->next;
 380         *(n->pprev) = n;
 381 }
 382
 383 /**
 384  * hlist_add_after_rcu
 385  * @prev: the existing element to add the new element after.
 386  * @n: the new element to add to the hash list.
 387  *
 388  * Description:
 389  * Adds the specified element to the specified hlist
 390  * after the specified node while permitting racing traversals.
 391  *
 392  * The caller must take whatever precautions are necessary
 393  * (such as holding appropriate locks) to avoid racing
 394  * with another list-mutation primitive, such as hlist_add_head_rcu()
 395  * or hlist_del_rcu(), running on this same list.
 396  * However, it is perfectly legal to run concurrently with
 397  * the _rcu list-traversal primitives, such as
 398  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
 399  * problems on Alpha CPUs.
 400  */
 401 static inline void hlist_add_after_rcu(struct hlist_node *prev,
 402                                            struct hlist_node *n)
 403 {
 404         n->next = prev->next;
 405         n->pprev = &prev->next;
 406         smp_wmb();
 407         prev->next = n;
 408         if (n->next)
 409                 n->next->pprev = &n->next;
 410 }
 411
 412 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
 413
 414 #define hlist_for_each(pos, head) \
 415         for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
 416                  pos = pos->next)
 417
 418 #define hlist_for_each_safe(pos, n, head) \
 419         for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
 420                  pos = n)
 421
 422 /**
 423  * hlist_for_each_entry - iterate over list of given type
 424  * @tpos:       the type * to use as a loop cursor.
 425  * @pos:        the &struct hlist_node to use as a loop cursor.
 426  * @head:       the head for your list.
 427  * @member:     the name of the hlist_node within the struct.
 428  */
 429 #define hlist_for_each_entry(tpos, pos, head, member)                    \
 430         for (pos = (head)->first;                                        \
 431                  pos && ({ prefetch(pos->next); 1;}) &&                  \
 432                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 433                  pos = pos->next)
 434
 435 /**
 436  * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
 437  * @tpos:       the type * to use as a loop cursor.
 438  * @pos:        the &struct hlist_node to use as a loop cursor.
 439  * @member:     the name of the hlist_node within the struct.
 440  */
 441 #define hlist_for_each_entry_continue(tpos, pos, member)                 \
 442         for (pos = (pos)->next;                                          \
 443                  pos && ({ prefetch(pos->next); 1;}) &&                  \
 444                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 445                  pos = pos->next)
 446
 447 /**
 448  * hlist_for_each_entry_from - iterate over a hlist continuing from current point
 449  * @tpos:       the type * to use as a loop cursor.
 450  * @pos:        the &struct hlist_node to use as a loop cursor.
 451  * @member:     the name of the hlist_node within the struct.
 452  */
 453 #define hlist_for_each_entry_from(tpos, pos, member)                     \
 454         for (; pos && ({ prefetch(pos->next); 1;}) &&                    \
 455                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 456                  pos = pos->next)
 457
 458 /**
 459  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 460  * @tpos:       the type * to use as a loop cursor.
 461  * @pos:        the &struct hlist_node to use as a loop cursor.
 462  * @n:          another &struct hlist_node to use as temporary storage
 463  * @head:       the head for your list.
 464  * @member:     the name of the hlist_node within the struct.
 465  */
 466 #define hlist_for_each_entry_safe(tpos, pos, n, head, member)            \
 467         for (pos = (head)->first;                                        \
 468                  pos && ({ n = pos->next; 1; }) &&                               \
 469                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 470                  pos = n)
 471
 472 /**
 473  * hlist_for_each_entry_rcu - iterate over rcu list of given type
 474  * @tpos:       the type * to use as a loop cursor.
 475  * @pos:        the &struct hlist_node to use as a loop cursor.
 476  * @head:       the head for your list.
 477  * @member:     the name of the hlist_node within the struct.
 478  *
 479  * This list-traversal primitive may safely run concurrently with
 480  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
 481  * as long as the traversal is guarded by rcu_read_lock().
 482  */
 483 #define hlist_for_each_entry_rcu(tpos, pos, head, member)                \
 484         for (pos = (head)->first;                                        \
 485                  rcu_dereference(pos) && ({ prefetch(pos->next); 1;}) &&         \
 486                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 487                  pos = pos->next)
 488
 489
 490 #if LINUX_VERSION_CODE < KERNEL_VERSION(2,4,23)
 491 /**
 492  * list_for_each_entry_safe - iterate over list of given type safe against remov
 493 al of list entry
 494  * @pos:        the type * to use as a loop counter.
 495  * @n:      another type * to use as temporary storage
 496  * @head:   the head for your list.
 497  * @member: the name of the list_struct within the struct.
 498  */
 499 #define list_for_each_entry_safe(pos, n, head, member)            \
 500         for (pos = list_entry((head)->next, typeof(*pos), member),  \
 501                 n = list_entry(pos->member.next, typeof(*pos), member); \
 502                  &pos->member != (head);                                        \
 503                  pos = n, n = list_entry(n->member.next, typeof(*n), member))
 504 #endif /* linux kernel < 2.4.23 */
 505
 506
 507 #else
 508 #warning "don't include kernel headers in userspace"
 509 #endif /* __KERNEL__ */
 510 #endif