common/klist.h

   1 /* -*- Mode: C ; c-basic-offset: 2 -*- */
   2 /*
   3  * LADI Session Handler (ladish)
   4  *
   5  * Linux kernel header adapted for user-mode. The 2.6.17-rt1 version was used.
   6  *
   7  * Original copyright holders of this code are unknown, they were not
   8  * mentioned in the original file.
   9  *
  10  **************************************************************************
  11  * This file contains implementation of double linked list (kernel style)
  12  **************************************************************************
  13  *
  14  * LADI Session Handler is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU General Public License as published by
  16  * the Free Software Foundation; either version 2 of the License.
  17  *
  18  * LADI Session Handler is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU General Public License for more details.
  22  *
  23  * You should have received a copy of the GNU General Public License
  24  * along with LADI Session Handler. If not, see <http://www.gnu.org/licenses/>
  25  * or write to the Free Software Foundation, Inc.,
  26  * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  27  */
  28
  29 #ifndef _LINUX_LIST_H
  30 #define _LINUX_LIST_H
  31
  32 #include <stddef.h>
  33
  34 #if !defined(offsetof)
  35 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
  36 #endif
  37
  38 /**
  39  * container_of - cast a member of a structure out to the containing structure
  40  * @ptr:  the pointer to the member.
  41  * @type: the type of the container struct this is embedded in.
  42  * @member: the name of the member within the struct.
  43  *
  44  */
  45 #define container_of(ptr, type, member) ({      \
  46         const typeof( ((type *)0)->member ) *__mptr = (ptr);  \
  47         (type *)( (char *)__mptr - offsetof(type,member) );})
  48
  49 #define prefetch(x) (x = x)
  50
  51 /*
  52  * These are non-NULL pointers that will result in page faults
  53  * under normal circumstances, used to verify that nobody uses
  54  * non-initialized list entries.
  55  */
  56 #define LIST_POISON1  ((void *) 0x00100100)
  57 #define LIST_POISON2  ((void *) 0x00200200)
  58
  59 /*
  60  * Simple doubly linked list implementation.
  61  *
  62  * Some of the internal functions ("__xxx") are useful when
  63  * manipulating whole lists rather than single entries, as
  64  * sometimes we already know the next/prev entries and we can
  65  * generate better code by using them directly rather than
  66  * using the generic single-entry routines.
  67  */
  68
  69 struct list_head {
  70   struct list_head *next, *prev;
  71 };
  72
  73 #define LIST_HEAD_INIT(name) { &(name), &(name) }
  74
  75 #define LIST_HEAD(name) \
  76   struct list_head name = LIST_HEAD_INIT(name)
  77
  78 static inline void INIT_LIST_HEAD(struct list_head *list)
  79 {
  80   list->next = list;
  81   list->prev = list;
  82 }
  83
  84 /*
  85  * Insert a new entry between two known consecutive entries.
  86  *
  87  * This is only for internal list manipulation where we know
  88  * the prev/next entries already!
  89  */
  90 static inline void __list_add(struct list_head *new,
  91             struct list_head *prev,
  92             struct list_head *next)
  93 {
  94   next->prev = new;
  95   new->next = next;
  96   new->prev = prev;
  97   prev->next = new;
  98 }
  99
 100 /**
 101  * list_add - add a new entry
 102  * @new: new entry to be added
 103  * @head: list head to add it after
 104  *
 105  * Insert a new entry after the specified head.
 106  * This is good for implementing stacks.
 107  */
 108 static inline void list_add(struct list_head *new, struct list_head *head)
 109 {
 110   __list_add(new, head, head->next);
 111 }
 112
 113 /**
 114  * list_add_tail - add a new entry
 115  * @new: new entry to be added
 116  * @head: list head to add it before
 117  *
 118  * Insert a new entry before the specified head.
 119  * This is useful for implementing queues.
 120  */
 121 static inline void list_add_tail(struct list_head *new, struct list_head *head)
 122 {
 123   __list_add(new, head->prev, head);
 124 }
 125
 126 /*
 127  * Insert a new entry between two known consecutive entries.
 128  *
 129  * This is only for internal list manipulation where we know
 130  * the prev/next entries already!
 131  */
 132 static inline void __list_add_rcu(struct list_head * new,
 133     struct list_head * prev, struct list_head * next)
 134 {
 135   new->next = next;
 136   new->prev = prev;
 137 //  smp_wmb();
 138   next->prev = new;
 139   prev->next = new;
 140 }
 141
 142 /**
 143  * list_add_rcu - add a new entry to rcu-protected list
 144  * @new: new entry to be added
 145  * @head: list head to add it after
 146  *
 147  * Insert a new entry after the specified head.
 148  * This is good for implementing stacks.
 149  *
 150  * The caller must take whatever precautions are necessary
 151  * (such as holding appropriate locks) to avoid racing
 152  * with another list-mutation primitive, such as list_add_rcu()
 153  * or list_del_rcu(), running on this same list.
 154  * However, it is perfectly legal to run concurrently with
 155  * the _rcu list-traversal primitives, such as
 156  * list_for_each_entry_rcu().
 157  */
 158 static inline void list_add_rcu(struct list_head *new, struct list_head *head)
 159 {
 160   __list_add_rcu(new, head, head->next);
 161 }
 162
 163 /**
 164  * list_add_tail_rcu - add a new entry to rcu-protected list
 165  * @new: new entry to be added
 166  * @head: list head to add it before
 167  *
 168  * Insert a new entry before the specified head.
 169  * This is useful for implementing queues.
 170  *
 171  * The caller must take whatever precautions are necessary
 172  * (such as holding appropriate locks) to avoid racing
 173  * with another list-mutation primitive, such as list_add_tail_rcu()
 174  * or list_del_rcu(), running on this same list.
 175  * However, it is perfectly legal to run concurrently with
 176  * the _rcu list-traversal primitives, such as
 177  * list_for_each_entry_rcu().
 178  */
 179 static inline void list_add_tail_rcu(struct list_head *new,
 180           struct list_head *head)
 181 {
 182   __list_add_rcu(new, head->prev, head);
 183 }
 184
 185 /*
 186  * Delete a list entry by making the prev/next entries
 187  * point to each other.
 188  *
 189  * This is only for internal list manipulation where we know
 190  * the prev/next entries already!
 191  */
 192 static inline void __list_del(struct list_head * prev, struct list_head * next)
 193 {
 194   next->prev = prev;
 195   prev->next = next;
 196 }
 197
 198 /**
 199  * list_del - deletes entry from list.
 200  * @entry: the element to delete from the list.
 201  * Note: list_empty on entry does not return true after this, the entry is
 202  * in an undefined state.
 203  */
 204 static inline void list_del(struct list_head *entry)
 205 {
 206   __list_del(entry->prev, entry->next);
 207   entry->next = LIST_POISON1;
 208   entry->prev = LIST_POISON2;
 209 }
 210
 211 /**
 212  * list_del_rcu - deletes entry from list without re-initialization
 213  * @entry: the element to delete from the list.
 214  *
 215  * Note: list_empty on entry does not return true after this,
 216  * the entry is in an undefined state. It is useful for RCU based
 217  * lockfree traversal.
 218  *
 219  * In particular, it means that we can not poison the forward
 220  * pointers that may still be used for walking the list.
 221  *
 222  * The caller must take whatever precautions are necessary
 223  * (such as holding appropriate locks) to avoid racing
 224  * with another list-mutation primitive, such as list_del_rcu()
 225  * or list_add_rcu(), running on this same list.
 226  * However, it is perfectly legal to run concurrently with
 227  * the _rcu list-traversal primitives, such as
 228  * list_for_each_entry_rcu().
 229  *
 230  * Note that the caller is not permitted to immediately free
 231  * the newly deleted entry.  Instead, either synchronize_rcu()
 232  * or call_rcu() must be used to defer freeing until an RCU
 233  * grace period has elapsed.
 234  */
 235 static inline void list_del_rcu(struct list_head *entry)
 236 {
 237   __list_del(entry->prev, entry->next);
 238   entry->prev = LIST_POISON2;
 239 }
 240
 241 /*
 242  * list_replace_rcu - replace old entry by new one
 243  * @old : the element to be replaced
 244  * @new : the new element to insert
 245  *
 246  * The old entry will be replaced with the new entry atomically.
 247  */
 248 static inline void list_replace_rcu(struct list_head *old,
 249         struct list_head *new)
 250 {
 251   new->next = old->next;
 252   new->prev = old->prev;
 253 //  smp_wmb();
 254   new->next->prev = new;
 255   new->prev->next = new;
 256   old->prev = LIST_POISON2;
 257 }
 258
 259 /**
 260  * list_del_init - deletes entry from list and reinitialize it.
 261  * @entry: the element to delete from the list.
 262  */
 263 static inline void list_del_init(struct list_head *entry)
 264 {
 265   __list_del(entry->prev, entry->next);
 266   INIT_LIST_HEAD(entry);
 267 }
 268
 269 /**
 270  * list_move - delete from one list and add as another's head
 271  * @list: the entry to move
 272  * @head: the head that will precede our entry
 273  */
 274 static inline void list_move(struct list_head *list, struct list_head *head)
 275 {
 276         __list_del(list->prev, list->next);
 277         list_add(list, head);
 278 }
 279
 280 /**
 281  * list_move_tail - delete from one list and add as another's tail
 282  * @list: the entry to move
 283  * @head: the head that will follow our entry
 284  */
 285 static inline void list_move_tail(struct list_head *list,
 286           struct list_head *head)
 287 {
 288         __list_del(list->prev, list->next);
 289         list_add_tail(list, head);
 290 }
 291
 292 /**
 293  * list_empty - tests whether a list is empty
 294  * @head: the list to test.
 295  */
 296 static inline int list_empty(const struct list_head *head)
 297 {
 298   return head->next == head;
 299 }
 300
 301 /**
 302  * list_empty_careful - tests whether a list is
 303  * empty _and_ checks that no other CPU might be
 304  * in the process of still modifying either member
 305  *
 306  * NOTE: using list_empty_careful() without synchronization
 307  * can only be safe if the only activity that can happen
 308  * to the list entry is list_del_init(). Eg. it cannot be used
 309  * if another CPU could re-list_add() it.
 310  *
 311  * @head: the list to test.
 312  */
 313 static inline int list_empty_careful(const struct list_head *head)
 314 {
 315   struct list_head *next = head->next;
 316   return (next == head) && (next == head->prev);
 317 }
 318
 319 static inline void __list_splice(struct list_head *list,
 320          struct list_head *head)
 321 {
 322   struct list_head *first = list->next;
 323   struct list_head *last = list->prev;
 324   struct list_head *at = head->next;
 325
 326   first->prev = head;
 327   head->next = first;
 328
 329   last->next = at;
 330   at->prev = last;
 331 }
 332
 333 /**
 334  * list_splice - join two lists
 335  * @list: the new list to add.
 336  * @head: the place to add it in the first list.
 337  */
 338 static inline void list_splice(struct list_head *list, struct list_head *head)
 339 {
 340   if (!list_empty(list))
 341     __list_splice(list, head);
 342 }
 343
 344 /**
 345  * list_splice_init - join two lists and reinitialise the emptied list.
 346  * @list: the new list to add.
 347  * @head: the place to add it in the first list.
 348  *
 349  * The list at @list is reinitialised
 350  */
 351 static inline void list_splice_init(struct list_head *list,
 352             struct list_head *head)
 353 {
 354   if (!list_empty(list)) {
 355     __list_splice(list, head);
 356     INIT_LIST_HEAD(list);
 357   }
 358 }
 359
 360 /**
 361  * list_entry - get the struct for this entry
 362  * @ptr:  the &struct list_head pointer.
 363  * @type: the type of the struct this is embedded in.
 364  * @member: the name of the list_struct within the struct.
 365  */
 366 #define list_entry(ptr, type, member) \
 367   container_of(ptr, type, member)
 368
 369 /**
 370  * list_for_each  - iterate over a list
 371  * @pos:  the &struct list_head to use as a loop counter.
 372  * @head: the head for your list.
 373  */
 374 #define list_for_each(pos, head) \
 375   for (pos = (head)->next; prefetch(pos->next), pos != (head); \
 376           pos = pos->next)
 377
 378 /**
 379  * __list_for_each  - iterate over a list
 380  * @pos:  the &struct list_head to use as a loop counter.
 381  * @head: the head for your list.
 382  *
 383  * This variant differs from list_for_each() in that it's the
 384  * simplest possible list iteration code, no prefetching is done.
 385  * Use this for code that knows the list to be very short (empty
 386  * or 1 entry) most of the time.
 387  */
 388 #define __list_for_each(pos, head) \
 389   for (pos = (head)->next; pos != (head); pos = pos->next)
 390
 391 /**
 392  * list_for_each_prev - iterate over a list backwards
 393  * @pos:  the &struct list_head to use as a loop counter.
 394  * @head: the head for your list.
 395  */
 396 #define list_for_each_prev(pos, head) \
 397   for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
 398           pos = pos->prev)
 399
 400 /**
 401  * list_for_each_safe - iterate over a list safe against removal of list entry
 402  * @pos:  the &struct list_head to use as a loop counter.
 403  * @n:    another &struct list_head to use as temporary storage
 404  * @head: the head for your list.
 405  */
 406 #define list_for_each_safe(pos, n, head) \
 407   for (pos = (head)->next, n = pos->next; pos != (head); \
 408     pos = n, n = pos->next)
 409
 410 /**
 411  * list_for_each_entry  - iterate over list of given type
 412  * @pos:  the type * to use as a loop counter.
 413  * @head: the head for your list.
 414  * @member: the name of the list_struct within the struct.
 415  */
 416 #define list_for_each_entry(pos, head, member)        \
 417   for (pos = list_entry((head)->next, typeof(*pos), member);  \
 418        prefetch(pos->member.next), &pos->member != (head);  \
 419        pos = list_entry(pos->member.next, typeof(*pos), member))
 420
 421 /**
 422  * list_for_each_entry_reverse - iterate backwards over list of given type.
 423  * @pos:  the type * to use as a loop counter.
 424  * @head: the head for your list.
 425  * @member: the name of the list_struct within the struct.
 426  */
 427 #define list_for_each_entry_reverse(pos, head, member)      \
 428   for (pos = list_entry((head)->prev, typeof(*pos), member);  \
 429        prefetch(pos->member.prev), &pos->member != (head);  \
 430        pos = list_entry(pos->member.prev, typeof(*pos), member))
 431
 432 /**
 433  * list_prepare_entry - prepare a pos entry for use as a start point in
 434  *      list_for_each_entry_continue
 435  * @pos:  the type * to use as a start point
 436  * @head: the head of the list
 437  * @member: the name of the list_struct within the struct.
 438  */
 439 #define list_prepare_entry(pos, head, member) \
 440   ((pos) ? : list_entry(head, typeof(*pos), member))
 441
 442 /**
 443  * list_for_each_entry_continue - iterate over list of given type
 444  *      continuing after existing point
 445  * @pos:  the type * to use as a loop counter.
 446  * @head: the head for your list.
 447  * @member: the name of the list_struct within the struct.
 448  */
 449 #define list_for_each_entry_continue(pos, head, member)     \
 450   for (pos = list_entry(pos->member.next, typeof(*pos), member);  \
 451        prefetch(pos->member.next), &pos->member != (head);  \
 452        pos = list_entry(pos->member.next, typeof(*pos), member))
 453
 454 /**
 455  * list_for_each_entry_from - iterate over list of given type
 456  *      continuing from existing point
 457  * @pos:  the type * to use as a loop counter.
 458  * @head: the head for your list.
 459  * @member: the name of the list_struct within the struct.
 460  */
 461 #define list_for_each_entry_from(pos, head, member)       \
 462   for (; prefetch(pos->member.next), &pos->member != (head);  \
 463        pos = list_entry(pos->member.next, typeof(*pos), member))
 464
 465 /**
 466  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 467  * @pos:  the type * to use as a loop counter.
 468  * @n:    another type * to use as temporary storage
 469  * @head: the head for your list.
 470  * @member: the name of the list_struct within the struct.
 471  */
 472 #define list_for_each_entry_safe(pos, n, head, member)      \
 473   for (pos = list_entry((head)->next, typeof(*pos), member),  \
 474     n = list_entry(pos->member.next, typeof(*pos), member); \
 475        &pos->member != (head);          \
 476        pos = n, n = list_entry(n->member.next, typeof(*n), member))
 477
 478 /**
 479  * list_for_each_entry_safe_continue -  iterate over list of given type
 480  *      continuing after existing point safe against removal of list entry
 481  * @pos:  the type * to use as a loop counter.
 482  * @n:    another type * to use as temporary storage
 483  * @head: the head for your list.
 484  * @member: the name of the list_struct within the struct.
 485  */
 486 #define list_for_each_entry_safe_continue(pos, n, head, member)     \
 487   for (pos = list_entry(pos->member.next, typeof(*pos), member),    \
 488     n = list_entry(pos->member.next, typeof(*pos), member);   \
 489        &pos->member != (head);            \
 490        pos = n, n = list_entry(n->member.next, typeof(*n), member))
 491
 492 /**
 493  * list_for_each_entry_safe_from - iterate over list of given type
 494  *      from existing point safe against removal of list entry
 495  * @pos:  the type * to use as a loop counter.
 496  * @n:    another type * to use as temporary storage
 497  * @head: the head for your list.
 498  * @member: the name of the list_struct within the struct.
 499  */
 500 #define list_for_each_entry_safe_from(pos, n, head, member)       \
 501   for (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
 505 /**
 506  * list_for_each_entry_safe_reverse - iterate backwards over list of given type safe against
 507  *              removal of list entry
 508  * @pos:  the type * to use as a loop counter.
 509  * @n:    another type * to use as temporary storage
 510  * @head: the head for your list.
 511  * @member: the name of the list_struct within the struct.
 512  */
 513 #define list_for_each_entry_safe_reverse(pos, n, head, member)    \
 514   for (pos = list_entry((head)->prev, typeof(*pos), member),  \
 515     n = list_entry(pos->member.prev, typeof(*pos), member); \
 516        &pos->member != (head);          \
 517        pos = n, n = list_entry(n->member.prev, typeof(*n), member))
 518
 519 /**
 520  * list_for_each_rcu  - iterate over an rcu-protected list
 521  * @pos:  the &struct list_head to use as a loop counter.
 522  * @head: the head for your list.
 523  *
 524  * This list-traversal primitive may safely run concurrently with
 525  * the _rcu list-mutation primitives such as list_add_rcu()
 526  * as long as the traversal is guarded by rcu_read_lock().
 527  */
 528 #define list_for_each_rcu(pos, head) \
 529   for (pos = (head)->next; \
 530     prefetch(rcu_dereference(pos)->next), pos != (head); \
 531           pos = pos->next)
 532
 533 #define __list_for_each_rcu(pos, head) \
 534   for (pos = (head)->next; \
 535     rcu_dereference(pos) != (head); \
 536           pos = pos->next)
 537
 538 /**
 539  * list_for_each_safe_rcu - iterate over an rcu-protected list safe
 540  *          against removal of list entry
 541  * @pos:  the &struct list_head to use as a loop counter.
 542  * @n:    another &struct list_head to use as temporary storage
 543  * @head: the head for your list.
 544  *
 545  * This list-traversal primitive may safely run concurrently with
 546  * the _rcu list-mutation primitives such as list_add_rcu()
 547  * as long as the traversal is guarded by rcu_read_lock().
 548  */
 549 #define list_for_each_safe_rcu(pos, n, head) \
 550   for (pos = (head)->next; \
 551     n = rcu_dereference(pos)->next, pos != (head); \
 552     pos = n)
 553
 554 /**
 555  * list_for_each_entry_rcu  - iterate over rcu list of given type
 556  * @pos:  the type * to use as a loop counter.
 557  * @head: the head for your list.
 558  * @member: the name of the list_struct within the struct.
 559  *
 560  * This list-traversal primitive may safely run concurrently with
 561  * the _rcu list-mutation primitives such as list_add_rcu()
 562  * as long as the traversal is guarded by rcu_read_lock().
 563  */
 564 #define list_for_each_entry_rcu(pos, head, member) \
 565   for (pos = list_entry((head)->next, typeof(*pos), member); \
 566     prefetch(rcu_dereference(pos)->member.next), \
 567       &pos->member != (head); \
 568     pos = list_entry(pos->member.next, typeof(*pos), member))
 569
 570
 571 /**
 572  * list_for_each_continue_rcu - iterate over an rcu-protected list
 573  *      continuing after existing point.
 574  * @pos:  the &struct list_head to use as a loop counter.
 575  * @head: the head for your list.
 576  *
 577  * This list-traversal primitive may safely run concurrently with
 578  * the _rcu list-mutation primitives such as list_add_rcu()
 579  * as long as the traversal is guarded by rcu_read_lock().
 580  */
 581 #define list_for_each_continue_rcu(pos, head) \
 582   for ((pos) = (pos)->next; \
 583     prefetch(rcu_dereference((pos))->next), (pos) != (head); \
 584           (pos) = (pos)->next)
 585
 586 /*
 587  * Double linked lists with a single pointer list head.
 588  * Mostly useful for hash tables where the two pointer list head is
 589  * too wasteful.
 590  * You lose the ability to access the tail in O(1).
 591  */
 592
 593 struct hlist_head {
 594   struct hlist_node *first;
 595 };
 596
 597 struct hlist_node {
 598   struct hlist_node *next, **pprev;
 599 };
 600
 601 #define HLIST_HEAD_INIT { .first = NULL }
 602 #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
 603 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
 604 static inline void INIT_HLIST_NODE(struct hlist_node *h)
 605 {
 606   h->next = NULL;
 607   h->pprev = NULL;
 608 }
 609
 610 static inline int hlist_unhashed(const struct hlist_node *h)
 611 {
 612   return !h->pprev;
 613 }
 614
 615 static inline int hlist_empty(const struct hlist_head *h)
 616 {
 617   return !h->first;
 618 }
 619
 620 static inline void __hlist_del(struct hlist_node *n)
 621 {
 622   struct hlist_node *next = n->next;
 623   struct hlist_node **pprev = n->pprev;
 624   *pprev = next;
 625   if (next)
 626     next->pprev = pprev;
 627 }
 628
 629 static inline void hlist_del(struct hlist_node *n)
 630 {
 631   __hlist_del(n);
 632   n->next = LIST_POISON1;
 633   n->pprev = LIST_POISON2;
 634 }
 635
 636 /**
 637  * hlist_del_rcu - deletes entry from hash list without re-initialization
 638  * @n: the element to delete from the hash list.
 639  *
 640  * Note: list_unhashed() on entry does not return true after this,
 641  * the entry is in an undefined state. It is useful for RCU based
 642  * lockfree traversal.
 643  *
 644  * In particular, it means that we can not poison the forward
 645  * pointers that may still be used for walking the hash list.
 646  *
 647  * The caller must take whatever precautions are necessary
 648  * (such as holding appropriate locks) to avoid racing
 649  * with another list-mutation primitive, such as hlist_add_head_rcu()
 650  * or hlist_del_rcu(), running on this same list.
 651  * However, it is perfectly legal to run concurrently with
 652  * the _rcu list-traversal primitives, such as
 653  * hlist_for_each_entry().
 654  */
 655 static inline void hlist_del_rcu(struct hlist_node *n)
 656 {
 657   __hlist_del(n);
 658   n->pprev = LIST_POISON2;
 659 }
 660
 661 static inline void hlist_del_init(struct hlist_node *n)
 662 {
 663   if (!hlist_unhashed(n)) {
 664     __hlist_del(n);
 665     INIT_HLIST_NODE(n);
 666   }
 667 }
 668
 669 /*
 670  * hlist_replace_rcu - replace old entry by new one
 671  * @old : the element to be replaced
 672  * @new : the new element to insert
 673  *
 674  * The old entry will be replaced with the new entry atomically.
 675  */
 676 static inline void hlist_replace_rcu(struct hlist_node *old,
 677           struct hlist_node *new)
 678 {
 679   struct hlist_node *next = old->next;
 680
 681   new->next = next;
 682   new->pprev = old->pprev;
 683 //  smp_wmb();
 684   if (next)
 685     new->next->pprev = &new->next;
 686   *new->pprev = new;
 687   old->pprev = LIST_POISON2;
 688 }
 689
 690 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 691 {
 692   struct hlist_node *first = h->first;
 693   n->next = first;
 694   if (first)
 695     first->pprev = &n->next;
 696   h->first = n;
 697   n->pprev = &h->first;
 698 }
 699
 700
 701 /**
 702  * hlist_add_head_rcu - adds the specified element to the specified hlist,
 703  * while permitting racing traversals.
 704  * @n: the element to add to the hash list.
 705  * @h: the list to add to.
 706  *
 707  * The caller must take whatever precautions are necessary
 708  * (such as holding appropriate locks) to avoid racing
 709  * with another list-mutation primitive, such as hlist_add_head_rcu()
 710  * or hlist_del_rcu(), running on this same list.
 711  * However, it is perfectly legal to run concurrently with
 712  * the _rcu list-traversal primitives, such as
 713  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
 714  * problems on Alpha CPUs.  Regardless of the type of CPU, the
 715  * list-traversal primitive must be guarded by rcu_read_lock().
 716  */
 717 static inline void hlist_add_head_rcu(struct hlist_node *n,
 718           struct hlist_head *h)
 719 {
 720   struct hlist_node *first = h->first;
 721   n->next = first;
 722   n->pprev = &h->first;
 723 //  smp_wmb();
 724   if (first)
 725     first->pprev = &n->next;
 726   h->first = n;
 727 }
 728
 729 /* next must be != NULL */
 730 static inline void hlist_add_before(struct hlist_node *n,
 731           struct hlist_node *next)
 732 {
 733   n->pprev = next->pprev;
 734   n->next = next;
 735   next->pprev = &n->next;
 736   *(n->pprev) = n;
 737 }
 738
 739 static inline void hlist_add_after(struct hlist_node *n,
 740           struct hlist_node *next)
 741 {
 742   next->next = n->next;
 743   n->next = next;
 744   next->pprev = &n->next;
 745
 746   if(next->next)
 747     next->next->pprev  = &next->next;
 748 }
 749
 750 /**
 751  * hlist_add_before_rcu - adds the specified element to the specified hlist
 752  * before the specified node while permitting racing traversals.
 753  * @n: the new element to add to the hash list.
 754  * @next: the existing element to add the new element before.
 755  *
 756  * The caller must take whatever precautions are necessary
 757  * (such as holding appropriate locks) to avoid racing
 758  * with another list-mutation primitive, such as hlist_add_head_rcu()
 759  * or hlist_del_rcu(), running on this same list.
 760  * However, it is perfectly legal to run concurrently with
 761  * the _rcu list-traversal primitives, such as
 762  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
 763  * problems on Alpha CPUs.
 764  */
 765 static inline void hlist_add_before_rcu(struct hlist_node *n,
 766           struct hlist_node *next)
 767 {
 768   n->pprev = next->pprev;
 769   n->next = next;
 770 //  smp_wmb();
 771   next->pprev = &n->next;
 772   *(n->pprev) = n;
 773 }
 774
 775 /**
 776  * hlist_add_after_rcu - adds the specified element to the specified hlist
 777  * after the specified node while permitting racing traversals.
 778  * @prev: the existing element to add the new element after.
 779  * @n: the new element to add to the hash list.
 780  *
 781  * The caller must take whatever precautions are necessary
 782  * (such as holding appropriate locks) to avoid racing
 783  * with another list-mutation primitive, such as hlist_add_head_rcu()
 784  * or hlist_del_rcu(), running on this same list.
 785  * However, it is perfectly legal to run concurrently with
 786  * the _rcu list-traversal primitives, such as
 787  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
 788  * problems on Alpha CPUs.
 789  */
 790 static inline void hlist_add_after_rcu(struct hlist_node *prev,
 791                struct hlist_node *n)
 792 {
 793   n->next = prev->next;
 794   n->pprev = &prev->next;
 795 //  smp_wmb();
 796   prev->next = n;
 797   if (n->next)
 798     n->next->pprev = &n->next;
 799 }
 800
 801 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
 802
 803 #define hlist_for_each(pos, head) \
 804   for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
 805        pos = pos->next)
 806
 807 #define hlist_for_each_safe(pos, n, head) \
 808   for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
 809        pos = n)
 810
 811 /**
 812  * hlist_for_each_entry - iterate over list of given type
 813  * @tpos: the type * to use as a loop counter.
 814  * @pos:  the &struct hlist_node to use as a loop counter.
 815  * @head: the head for your list.
 816  * @member: the name of the hlist_node within the struct.
 817  */
 818 #define hlist_for_each_entry(tpos, pos, head, member)      \
 819   for (pos = (head)->first;          \
 820        pos && ({ prefetch(pos->next); 1;}) &&      \
 821     ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 822        pos = pos->next)
 823
 824 /**
 825  * hlist_for_each_entry_continue - iterate over a hlist continuing after existing point
 826  * @tpos: the type * to use as a loop counter.
 827  * @pos:  the &struct hlist_node to use as a loop counter.
 828  * @member: the name of the hlist_node within the struct.
 829  */
 830 #define hlist_for_each_entry_continue(tpos, pos, member)     \
 831   for (pos = (pos)->next;            \
 832        pos && ({ prefetch(pos->next); 1;}) &&      \
 833     ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 834        pos = pos->next)
 835
 836 /**
 837  * hlist_for_each_entry_from - iterate over a hlist continuing from existing point
 838  * @tpos: the type * to use as a loop counter.
 839  * @pos:  the &struct hlist_node to use as a loop counter.
 840  * @member: the name of the hlist_node within the struct.
 841  */
 842 #define hlist_for_each_entry_from(tpos, pos, member)       \
 843   for (; pos && ({ prefetch(pos->next); 1;}) &&      \
 844     ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 845        pos = pos->next)
 846
 847 /**
 848  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 849  * @tpos: the type * to use as a loop counter.
 850  * @pos:  the &struct hlist_node to use as a loop counter.
 851  * @n:    another &struct hlist_node to use as temporary storage
 852  * @head: the head for your list.
 853  * @member: the name of the hlist_node within the struct.
 854  */
 855 #define hlist_for_each_entry_safe(tpos, pos, n, head, member)      \
 856   for (pos = (head)->first;          \
 857        pos && ({ n = pos->next; 1; }) &&         \
 858     ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 859        pos = n)
 860
 861 /**
 862  * hlist_for_each_entry_rcu - iterate over rcu list of given type
 863  * @tpos: the type * to use as a loop counter.
 864  * @pos:  the &struct hlist_node to use as a loop counter.
 865  * @head: the head for your list.
 866  * @member: the name of the hlist_node within the struct.
 867  *
 868  * This list-traversal primitive may safely run concurrently with
 869  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
 870  * as long as the traversal is guarded by rcu_read_lock().
 871  */
 872 #define hlist_for_each_entry_rcu(tpos, pos, head, member)    \
 873   for (pos = (head)->first;          \
 874        rcu_dereference(pos) && ({ prefetch(pos->next); 1;}) &&   \
 875     ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 876        pos = pos->next)
 877
 878 #endif