1 /*
2 * Stolen from Linux 2.6.7
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License as
6 * published by the Free Software Foundation; version 2 of the
7 * License.
8 *
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see <http://www.gnu.org/licenses/>.
16 */
17
18 #ifndef CMUS_LIST_H
19 #define CMUS_LIST_H
20
21 #include "compiler.h" /* container_of */
22
prefetch(const void * x)23 static inline void prefetch(const void *x)
24 {
25 }
26
27 /*
28 * These are non-NULL pointers that will result in page faults
29 * under normal circumstances, used to verify that nobody uses
30 * non-initialized list entries.
31 */
32 #define LIST_POISON1 ((void *) 0x00100100)
33 #define LIST_POISON2 ((void *) 0x00200200)
34
35 /*
36 * Simple doubly linked list implementation.
37 *
38 * Some of the internal functions ("_xxx") are useful when
39 * manipulating whole lists rather than single entries, as
40 * sometimes we already know the next/prev entries and we can
41 * generate better code by using them directly rather than
42 * using the generic single-entry routines.
43 */
44
45 struct list_head {
46 struct list_head *next, *prev;
47 };
48
49 #define LIST_HEAD_INIT(name) { &(name), &(name) }
50
51 #define LIST_HEAD(name) \
52 struct list_head name = LIST_HEAD_INIT(name)
53
list_init(struct list_head * head)54 static inline void list_init(struct list_head *head)
55 {
56 head->next = head;
57 head->prev = head;
58 }
59
60 /*
61 * Insert a new entry between two known consecutive entries.
62 *
63 * This is only for internal list manipulation where we know
64 * the prev/next entries already!
65 */
_list_add(struct list_head * new,struct list_head * prev,struct list_head * next)66 static inline void _list_add(struct list_head *new,
67 struct list_head *prev,
68 struct list_head *next)
69 {
70 next->prev = new;
71 new->next = next;
72 new->prev = prev;
73 prev->next = new;
74 }
75
list_prev(struct list_head * list)76 static inline struct list_head *list_prev(struct list_head *list)
77 {
78 return list->prev;
79 }
80
list_next(struct list_head * list)81 static inline struct list_head *list_next(struct list_head *list)
82 {
83 return list->next;
84 }
85
86 /**
87 * list_add - add a new entry
88 * @new: new entry to be added
89 * @head: list head to add it after
90 *
91 * Insert a new entry after the specified head.
92 * This is good for implementing stacks.
93 */
list_add(struct list_head * new,struct list_head * head)94 static inline void list_add(struct list_head *new, struct list_head *head)
95 {
96 _list_add(new, head, head->next);
97 }
98
99 /**
100 * list_add_tail - add a new entry
101 * @new: new entry to be added
102 * @head: list head to add it before
103 *
104 * Insert a new entry before the specified head.
105 * This is useful for implementing queues.
106 */
list_add_tail(struct list_head * new,struct list_head * head)107 static inline void list_add_tail(struct list_head *new, struct list_head *head)
108 {
109 _list_add(new, head->prev, head);
110 }
111
112 /*
113 * Delete a list entry by making the prev/next entries
114 * point to each other.
115 *
116 * This is only for internal list manipulation where we know
117 * the prev/next entries already!
118 */
_list_del(struct list_head * prev,struct list_head * next)119 static inline void _list_del(struct list_head *prev, struct list_head *next)
120 {
121 next->prev = prev;
122 prev->next = next;
123 }
124
125 /**
126 * list_del - deletes entry from list.
127 * @entry: the element to delete from the list.
128 * Note: list_empty on entry does not return true after this, the entry is
129 * in an undefined state.
130 */
list_del(struct list_head * entry)131 static inline void list_del(struct list_head *entry)
132 {
133 _list_del(entry->prev, entry->next);
134 entry->next = LIST_POISON1;
135 entry->prev = LIST_POISON2;
136 }
137
138 /**
139 * list_del_init - deletes entry from list and reinitialize it.
140 * @entry: the element to delete from the list.
141 */
list_del_init(struct list_head * entry)142 static inline void list_del_init(struct list_head *entry)
143 {
144 _list_del(entry->prev, entry->next);
145 list_init(entry);
146 }
147
148 /**
149 * list_move - delete from one list and add as another one's head
150 * @list: the entry to move
151 * @head: the head that will precede our entry
152 */
list_move(struct list_head * list,struct list_head * head)153 static inline void list_move(struct list_head *list, struct list_head *head)
154 {
155 _list_del(list->prev, list->next);
156 list_add(list, head);
157 }
158
159 /**
160 * list_move_tail - delete from one list and add as another one's tail
161 * @list: the entry to move
162 * @head: the head that will follow our entry
163 */
list_move_tail(struct list_head * list,struct list_head * head)164 static inline void list_move_tail(struct list_head *list,
165 struct list_head *head)
166 {
167 _list_del(list->prev, list->next);
168 list_add_tail(list, head);
169 }
170
171 /**
172 * list_empty - tests whether a list is empty
173 * @head: the list to test.
174 */
list_empty(const struct list_head * head)175 static inline int list_empty(const struct list_head *head)
176 {
177 return head->next == head;
178 }
179
_list_splice(struct list_head * list,struct list_head * head)180 static inline void _list_splice(struct list_head *list,
181 struct list_head *head)
182 {
183 struct list_head *first = list->next;
184 struct list_head *last = list->prev;
185 struct list_head *at = head->next;
186
187 first->prev = head;
188 head->next = first;
189
190 last->next = at;
191 at->prev = last;
192 }
193
194 /**
195 * list_splice - join two lists
196 * @list: the new list to add.
197 * @head: the place to add it in the first list.
198 */
list_splice(struct list_head * list,struct list_head * head)199 static inline void list_splice(struct list_head *list, struct list_head *head)
200 {
201 if (!list_empty(list))
202 _list_splice(list, head);
203 }
204
205 /**
206 * list_splice_init - join two lists and reinitialize the emptied list.
207 * @list: the new list to add.
208 * @head: the place to add it in the first list.
209 *
210 * The list at @list is reinitialized
211 */
list_splice_init(struct list_head * list,struct list_head * head)212 static inline void list_splice_init(struct list_head *list,
213 struct list_head *head)
214 {
215 if (!list_empty(list)) {
216 _list_splice(list, head);
217 list_init(list);
218 }
219 }
220
221 /**
222 * list_entry - get the struct for this entry
223 * @ptr: the &struct list_head pointer.
224 * @type: the type of the struct this is embedded in.
225 * @member: the name of the list_struct within the struct.
226 */
227 #define list_entry(ptr, type, member) \
228 container_of(ptr, type, member)
229
230 /**
231 * list_for_each - iterate over a list
232 * @pos: the &struct list_head to use as a loop counter.
233 * @head: the head for your list.
234 */
235 #define list_for_each(pos, head) \
236 for (pos = (head)->next, prefetch(pos->next); pos != (head); \
237 pos = pos->next, prefetch(pos->next))
238
239 /**
240 * _list_for_each - iterate over a list
241 * @pos: the &struct list_head to use as a loop counter.
242 * @head: the head for your list.
243 *
244 * This variant differs from list_for_each() in that it's the
245 * simplest possible list iteration code, no prefetching is done.
246 * Use this for code that knows the list to be very short (empty
247 * or 1 entry) most of the time.
248 */
249 #define _list_for_each(pos, head) \
250 for (pos = (head)->next; pos != (head); pos = pos->next)
251
252 /**
253 * list_for_each_prev - iterate over a list backwards
254 * @pos: the &struct list_head to use as a loop counter.
255 * @head: the head for your list.
256 */
257 #define list_for_each_prev(pos, head) \
258 for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \
259 pos = pos->prev, prefetch(pos->prev))
260
261 /**
262 * list_for_each_safe - iterate over a list safe against removal of list entry
263 * @pos: the &struct list_head to use as a loop counter.
264 * @n: another &struct list_head to use as temporary storage
265 * @head: the head for your list.
266 */
267 #define list_for_each_safe(pos, n, head) \
268 for (pos = (head)->next, n = pos->next; pos != (head); \
269 pos = n, n = pos->next)
270
271 /**
272 * list_for_each_entry - iterate over list of given type
273 * @pos: the type * to use as a loop counter.
274 * @head: the head for your list.
275 * @member: the name of the list_struct within the struct.
276 */
277 #define list_for_each_entry(pos, head, member) \
278 for (pos = list_entry((head)->next, __typeof__(*pos), member), \
279 prefetch(pos->member.next); \
280 &pos->member != (head); \
281 pos = list_entry(pos->member.next, __typeof__(*pos), member), \
282 prefetch(pos->member.next))
283
284 /**
285 * list_for_each_entry_reverse - iterate backwards over list of given type.
286 * @pos: the type * to use as a loop counter.
287 * @head: the head for your list.
288 * @member: the name of the list_struct within the struct.
289 */
290 #define list_for_each_entry_reverse(pos, head, member) \
291 for (pos = list_entry((head)->prev, __typeof__(*pos), member), \
292 prefetch(pos->member.prev); \
293 &pos->member != (head); \
294 pos = list_entry(pos->member.prev, __typeof__(*pos), member), \
295 prefetch(pos->member.prev))
296
297 /**
298 * list_prepare_entry - prepare a pos entry for use as a start point in
299 * list_for_each_entry_continue
300 * @pos: the type * to use as a start point
301 * @head: the head of the list
302 * @member: the name of the list_struct within the struct.
303 */
304 #define list_prepare_entry(pos, head, member) \
305 ((pos) ? : list_entry(head, __typeof__(*pos), member))
306
307 /**
308 * list_for_each_entry_continue - iterate over list of given type
309 * continuing after existing point
310 * @pos: the type * to use as a loop counter.
311 * @head: the head for your list.
312 * @member: the name of the list_struct within the struct.
313 */
314 #define list_for_each_entry_continue(pos, head, member) \
315 for (pos = list_entry(pos->member.next, __typeof__(*pos), member), \
316 prefetch(pos->member.next); \
317 &pos->member != (head); \
318 pos = list_entry(pos->member.next, __typeof__(*pos), member), \
319 prefetch(pos->member.next))
320
321 /**
322 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
323 * @pos: the type * to use as a loop counter.
324 * @n: another type * to use as temporary storage
325 * @head: the head for your list.
326 * @member: the name of the list_struct within the struct.
327 */
328 #define list_for_each_entry_safe(pos, n, head, member) \
329 for (pos = list_entry((head)->next, __typeof__(*pos), member), \
330 n = list_entry(pos->member.next, __typeof__(*pos), member); \
331 &pos->member != (head); \
332 pos = n, n = list_entry(n->member.next, __typeof__(*n), member))
333
334
335 /**
336 * list_len - get the length of a list
337 * @list: the list to measure
338 */
list_len(struct list_head * list)339 static inline size_t list_len(struct list_head *list)
340 {
341 size_t len = 0;
342 struct list_head *pos;
343 list_for_each(pos, list)
344 len++;
345 return len;
346 }
347
348 #endif
349