Root/
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_empty - tests whether a lock-less list is empty |
129 | * @head: the list to test |
130 | * |
131 | * Not guaranteed to be accurate or up to date. Just a quick way to |
132 | * test whether the list is empty without deleting something from the |
133 | * list. |
134 | */ |
135 | static inline bool llist_empty(const struct llist_head *head) |
136 | { |
137 | return ACCESS_ONCE(head->first) == NULL; |
138 | } |
139 | |
140 | static inline struct llist_node *llist_next(struct llist_node *node) |
141 | { |
142 | return node->next; |
143 | } |
144 | |
145 | extern bool llist_add_batch(struct llist_node *new_first, |
146 | struct llist_node *new_last, |
147 | struct llist_head *head); |
148 | /** |
149 | * llist_add - add a new entry |
150 | * @new: new entry to be added |
151 | * @head: the head for your lock-less list |
152 | * |
153 | * Returns true if the list was empty prior to adding this entry. |
154 | */ |
155 | static inline bool llist_add(struct llist_node *new, struct llist_head *head) |
156 | { |
157 | return llist_add_batch(new, new, head); |
158 | } |
159 | |
160 | /** |
161 | * llist_del_all - delete all entries from lock-less list |
162 | * @head: the head of lock-less list to delete all entries |
163 | * |
164 | * If list is empty, return NULL, otherwise, delete all entries and |
165 | * return the pointer to the first entry. The order of entries |
166 | * deleted is from the newest to the oldest added one. |
167 | */ |
168 | static inline struct llist_node *llist_del_all(struct llist_head *head) |
169 | { |
170 | return xchg(&head->first, NULL); |
171 | } |
172 | |
173 | extern struct llist_node *llist_del_first(struct llist_head *head); |
174 | |
175 | #endif /* LLIST_H */ |
176 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9