File: /Users/paulross/dev/linux/linux-3.13/include/linux/llist.h

Green shading in the line number column means the source is part of the translation unit, red means it is conditionally excluded. Highlighted line numbers link to the translation unit page. Highlighted macros link to the macro page.

       1: #ifndef LLIST_H
       2: #define LLIST_H
       3: /*
       4:  * Lock-less NULL terminated single linked list
       5:  *
       6:  * If there are multiple producers and multiple consumers, llist_add
       7:  * can be used in producers and llist_del_all can be used in
       8:  * consumers.  They can work simultaneously without lock.  But
       9:  * llist_del_first can not be used here.  Because llist_del_first
      10:  * depends on list->first->next does not changed if list->first is not
      11:  * changed during its operation, but llist_del_first, llist_add,
      12:  * llist_add (or llist_del_all, llist_add, llist_add) sequence in
      13:  * another consumer may violate that.
      14:  *
      15:  * If there are multiple producers and one consumer, llist_add can be
      16:  * used in producers and llist_del_all or llist_del_first can be used
      17:  * in the consumer.
      18:  *
      19:  * This can be summarized as follow:
      20:  *
      21:  *           |   add    | del_first |  del_all
      22:  * add       |    -     |     -     |     -
      23:  * del_first |          |     L     |     L
      24:  * del_all   |          |           |     -
      25:  *
      26:  * Where "-" stands for no lock is needed, while "L" stands for lock
      27:  * is needed.
      28:  *
      29:  * The list entries deleted via llist_del_all can be traversed with
      30:  * traversing function such as llist_for_each etc.  But the list
      31:  * entries can not be traversed safely before deleted from the list.
      32:  * The order of deleted entries is from the newest to the oldest added
      33:  * one.  If you want to traverse from the oldest to the newest, you
      34:  * must reverse the order by yourself before traversing.
      35:  *
      36:  * The basic atomic operation of this list is cmpxchg on long.  On
      37:  * architectures that don't have NMI-safe cmpxchg implementation, the
      38:  * list can NOT be used in NMI handlers.  So code that uses the list in
      39:  * an NMI handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG.
      40:  *
      41:  * Copyright 2010,2011 Intel Corp.
      42:  *   Author: Huang Ying <ying.huang@intel.com>
      43:  *
      44:  * This program is free software; you can redistribute it and/or
      45:  * modify it under the terms of the GNU General Public License version
      46:  * 2 as published by the Free Software Foundation;
      47:  *
      48:  * This program is distributed in the hope that it will be useful,
      49:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      50:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      51:  * GNU General Public License for more details.
      52:  *
      53:  * You should have received a copy of the GNU General Public License
      54:  * along with this program; if not, write to the Free Software
      55:  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
      56:  */
      57: 
      58: #include <linux/kernel.h>
      59: #include <asm/cmpxchg.h>
      60: 
      61: struct llist_head {
      62:     struct llist_node *first;
      63: };
      64: 
      65: struct llist_node {
      66:     struct llist_node *next;
      67: };
      68: 
      69: #define LLIST_HEAD_INIT(name)    { NULL }
      70: #define LLIST_HEAD(name)    struct llist_head name = LLIST_HEAD_INIT(name)
      71: 
      72: /**
      73:  * init_llist_head - initialize lock-less list head
      74:  * @head:    the head for your lock-less list
      75:  */
      76: static inline void init_llist_head(struct llist_head *list)
      77: {
      78:     list->first = NULL;
      79: }
      80: 
      81: /**
      82:  * llist_entry - get the struct of this entry
      83:  * @ptr:    the &struct llist_node pointer.
      84:  * @type:    the type of the struct this is embedded in.
      85:  * @member:    the name of the llist_node within the struct.
      86:  */
      87: #define llist_entry(ptr, type, member)        \
      88:     container_of(ptr, type, member)
      89: 
      90: /**
      91:  * llist_for_each - iterate over some deleted entries of a lock-less list
      92:  * @pos:    the &struct llist_node to use as a loop cursor
      93:  * @node:    the first entry of deleted list entries
      94:  *
      95:  * In general, some entries of the lock-less list can be traversed
      96:  * safely only after being deleted from list, so start with an entry
      97:  * instead of list head.
      98:  *
      99:  * If being used on entries deleted from lock-less list directly, the
     100:  * traverse order is from the newest to the oldest added entry.  If
     101:  * you want to traverse from the oldest to the newest, you must
     102:  * reverse the order by yourself before traversing.
     103:  */
     104: #define llist_for_each(pos, node)            \
     105:     for ((pos) = (node); pos; (pos) = (pos)->next)
     106: 
     107: /**
     108:  * llist_for_each_entry - iterate over some deleted entries of lock-less list of given type
     109:  * @pos:    the type * to use as a loop cursor.
     110:  * @node:    the fist entry of deleted list entries.
     111:  * @member:    the name of the llist_node with the struct.
     112:  *
     113:  * In general, some entries of the lock-less list can be traversed
     114:  * safely only after being removed from list, so start with an entry
     115:  * instead of list head.
     116:  *
     117:  * If being used on entries deleted from lock-less list directly, the
     118:  * traverse order is from the newest to the oldest added entry.  If
     119:  * you want to traverse from the oldest to the newest, you must
     120:  * reverse the order by yourself before traversing.
     121:  */
     122: #define llist_for_each_entry(pos, node, member)                \
     123:     for ((pos) = llist_entry((node), typeof(*(pos)), member);    \
     124:          &(pos)->member != NULL;                    \
     125:          (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member))
     126: 
     127: /**
     128:  * llist_for_each_entry_safe - iterate over some deleted entries of lock-less list of given type
     129:  *                   safe against removal of list entry
     130:  * @pos:    the type * to use as a loop cursor.
     131:  * @n:        another type * to use as temporary storage
     132:  * @node:    the first entry of deleted list entries.
     133:  * @member:    the name of the llist_node with the struct.
     134:  *
     135:  * In general, some entries of the lock-less list can be traversed
     136:  * safely only after being removed from list, so start with an entry
     137:  * instead of list head.
     138:  *
     139:  * If being used on entries deleted from lock-less list directly, the
     140:  * traverse order is from the newest to the oldest added entry.  If
     141:  * you want to traverse from the oldest to the newest, you must
     142:  * reverse the order by yourself before traversing.
     143:  */
     144: #define llist_for_each_entry_safe(pos, n, node, member)                   \
     145:     for (pos = llist_entry((node), typeof(*pos), member);               \
     146:          &pos->member != NULL &&                           \
     147:             (n = llist_entry(pos->member.next, typeof(*n), member), true); \
     148:          pos = n)
     149: 
     150: /**
     151:  * llist_empty - tests whether a lock-less list is empty
     152:  * @head:    the list to test
     153:  *
     154:  * Not guaranteed to be accurate or up to date.  Just a quick way to
     155:  * test whether the list is empty without deleting something from the
     156:  * list.
     157:  */
     158: static inline bool llist_empty(const struct llist_head *head)
     159: {
     160:     return ACCESS_ONCE(head->first) == NULL;
     161: }
     162: 
     163: static inline struct llist_node *llist_next(struct llist_node *node)
     164: {
     165:     return node->next;
     166: }
     167: 
     168: extern bool llist_add_batch(struct llist_node *new_first,
     169:                 struct llist_node *new_last,
     170:                 struct llist_head *head);
     171: /**
     172:  * llist_add - add a new entry
     173:  * @new:    new entry to be added
     174:  * @head:    the head for your lock-less list
     175:  *
     176:  * Returns true if the list was empty prior to adding this entry.
     177:  */
     178: static inline bool llist_add(struct llist_node *new, struct llist_head *head)
     179: {
     180:     return llist_add_batch(new, new, head);
     181: }
     182: 
     183: /**
     184:  * llist_del_all - delete all entries from lock-less list
     185:  * @head:    the head of lock-less list to delete all entries
     186:  *
     187:  * If list is empty, return NULL, otherwise, delete all entries and
     188:  * return the pointer to the first entry.  The order of entries
     189:  * deleted is from the newest to the oldest added one.
     190:  */
     191: static inline struct llist_node *llist_del_all(struct llist_head *head)
     192: {
     193:     return xchg(&head->first, NULL);
     194: }
     195: 
     196: extern struct llist_node *llist_del_first(struct llist_head *head);
     197: 
     198: struct llist_node *llist_reverse_order(struct llist_node *head);
     199: 
     200: #endif /* LLIST_H */
     201: