blob_attr_equal: un-inline, add pointer checks
[project/libubox.git] / list.h
1 #ifndef _LINUX_LIST_H
2 #define _LINUX_LIST_H
3
4 #include <stddef.h>
5 /**
6  * container_of - cast a member of a structure out to the containing structure
7  * @ptr:        the pointer to the member.
8  * @type:       the type of the container struct this is embedded in.
9  * @member:     the name of the member within the struct.
10  *
11  */
12 #ifndef container_of
13 #define container_of(ptr, type, member) (                       \
14         (type *)( (char *)ptr - offsetof(type,member) ))
15 #endif
16
17
18 /*
19  * Simple doubly linked list implementation.
20  *
21  * Some of the internal functions ("__xxx") are useful when
22  * manipulating whole lists rather than single entries, as
23  * sometimes we already know the next/prev entries and we can
24  * generate better code by using them directly rather than
25  * using the generic single-entry routines.
26  */
27
28 struct list_head {
29         struct list_head *next, *prev;
30 };
31
32 #define LIST_HEAD_INIT(name) { &(name), &(name) }
33
34 #define LIST_HEAD(name) \
35         struct list_head name = LIST_HEAD_INIT(name)
36
37 static inline void INIT_LIST_HEAD(struct list_head *list)
38 {
39         list->next = list;
40         list->prev = list;
41 }
42
43 /*
44  * Insert a new entry between two known consecutive entries.
45  *
46  * This is only for internal list manipulation where we know
47  * the prev/next entries already!
48  */
49 static inline void __list_add(struct list_head *new,
50                               struct list_head *prev,
51                               struct list_head *next)
52 {
53         next->prev = new;
54         new->next = next;
55         new->prev = prev;
56         prev->next = new;
57 }
58
59 /**
60  * list_add - add a new entry
61  * @new: new entry to be added
62  * @head: list head to add it after
63  *
64  * Insert a new entry after the specified head.
65  * This is good for implementing stacks.
66  */
67 static inline void list_add(struct list_head *new, struct list_head *head)
68 {
69         __list_add(new, head, head->next);
70 }
71
72
73 /**
74  * list_add_tail - add a new entry
75  * @new: new entry to be added
76  * @head: list head to add it before
77  *
78  * Insert a new entry before the specified head.
79  * This is useful for implementing queues.
80  */
81 static inline void list_add_tail(struct list_head *new, struct list_head *head)
82 {
83         __list_add(new, head->prev, head);
84 }
85
86
87 /*
88  * Delete a list entry by making the prev/next entries
89  * point to each other.
90  *
91  * This is only for internal list manipulation where we know
92  * the prev/next entries already!
93  */
94 static inline void __list_del(struct list_head * prev, struct list_head * next)
95 {
96         next->prev = prev;
97         prev->next = next;
98 }
99
100 /**
101  * list_del - deletes entry from list.
102  * @entry: the element to delete from the list.
103  * Note: list_empty() on entry does not return true after this, the entry is
104  * in an undefined state.
105  */
106 static inline void list_del(struct list_head *entry)
107 {
108         __list_del(entry->prev, entry->next);
109         entry->next = NULL;
110         entry->prev = NULL;
111 }
112
113 /**
114  * list_replace - replace old entry by new one
115  * @old : the element to be replaced
116  * @new : the new element to insert
117  *
118  * If @old was empty, it will be overwritten.
119  */
120 static inline void list_replace(struct list_head *old,
121                                 struct list_head *new)
122 {
123         new->next = old->next;
124         new->next->prev = new;
125         new->prev = old->prev;
126         new->prev->next = new;
127 }
128
129 static inline void list_replace_init(struct list_head *old,
130                                         struct list_head *new)
131 {
132         list_replace(old, new);
133         INIT_LIST_HEAD(old);
134 }
135
136 /**
137  * list_del_init - deletes entry from list and reinitialize it.
138  * @entry: the element to delete from the list.
139  */
140 static inline void list_del_init(struct list_head *entry)
141 {
142         __list_del(entry->prev, entry->next);
143         INIT_LIST_HEAD(entry);
144 }
145
146 /**
147  * list_move - delete from one list and add as another's head
148  * @list: the entry to move
149  * @head: the head that will precede our entry
150  */
151 static inline void list_move(struct list_head *list, struct list_head *head)
152 {
153         __list_del(list->prev, list->next);
154         list_add(list, head);
155 }
156
157 /**
158  * list_move_tail - delete from one list and add as another's tail
159  * @list: the entry to move
160  * @head: the head that will follow our entry
161  */
162 static inline void list_move_tail(struct list_head *list,
163                                   struct list_head *head)
164 {
165         __list_del(list->prev, list->next);
166         list_add_tail(list, head);
167 }
168
169 /**
170  * list_is_first - tests whether @list is the first entry in list @head
171  * @list: the entry to test
172  * @head: the head of the list
173  */
174 static inline int list_is_first(const struct list_head *list,
175                                 const struct list_head *head)
176 {
177         return list->prev == head;
178 }
179
180 /**
181  * list_is_last - tests whether @list is the last entry in list @head
182  * @list: the entry to test
183  * @head: the head of the list
184  */
185 static inline int list_is_last(const struct list_head *list,
186                                 const struct list_head *head)
187 {
188         return list->next == head;
189 }
190
191 /**
192  * list_empty - tests whether a list is empty
193  * @head: the list to test.
194  */
195 static inline int list_empty(const struct list_head *head)
196 {
197         return head->next == head;
198 }
199
200 /**
201  * list_empty_careful - tests whether a list is empty and not being modified
202  * @head: the list to test
203  *
204  * Description:
205  * tests whether a list is empty _and_ checks that no other CPU might be
206  * in the process of modifying either member (next or prev)
207  *
208  * NOTE: using list_empty_careful() without synchronization
209  * can only be safe if the only activity that can happen
210  * to the list entry is list_del_init(). Eg. it cannot be used
211  * if another CPU could re-list_add() it.
212  */
213 static inline int list_empty_careful(const struct list_head *head)
214 {
215         struct list_head *next = head->next;
216         return (next == head) && (next == head->prev);
217 }
218
219 static inline void __list_splice(struct list_head *list,
220                                  struct list_head *head)
221 {
222         struct list_head *first = list->next;
223         struct list_head *last = list->prev;
224         struct list_head *at = head->next;
225
226         first->prev = head;
227         head->next = first;
228
229         last->next = at;
230         at->prev = last;
231 }
232
233 /**
234  * list_splice - join two lists
235  * @list: the new list to add.
236  * @head: the place to add it in the first list.
237  */
238 static inline void list_splice(struct list_head *list, struct list_head *head)
239 {
240         if (!list_empty(list))
241                 __list_splice(list, head);
242 }
243
244 /**
245  * list_splice_init - join two lists and reinitialise the emptied list.
246  * @list: the new list to add.
247  * @head: the place to add it in the first list.
248  *
249  * The list at @list is reinitialised
250  */
251 static inline void list_splice_init(struct list_head *list,
252                                     struct list_head *head)
253 {
254         if (!list_empty(list)) {
255                 __list_splice(list, head);
256                 INIT_LIST_HEAD(list);
257         }
258 }
259
260 /**
261  * list_entry - get the struct for this entry
262  * @ptr:        the &struct list_head pointer.
263  * @type:       the type of the struct this is embedded in.
264  * @member:     the name of the list_struct within the struct.
265  */
266 #define list_entry(ptr, type, member) \
267         container_of(ptr, type, member)
268
269 /**
270  * list_first_entry - get the first element from a list
271  * @ptr:        the list head to take the element from.
272  * @type:       the type of the struct this is embedded in.
273  * @member:     the name of the list_struct within the struct.
274  *
275  * Note, that list is expected to be not empty.
276  */
277 #define list_first_entry(ptr, type, member) \
278         list_entry((ptr)->next, type, member)
279
280 /**
281  * list_for_each        -       iterate over a list
282  * @pos:        the &struct list_head to use as a loop cursor.
283  * @head:       the head for your list.
284  */
285 #define list_for_each(pos, head) \
286         for (pos = (head)->next; pos != (head); \
287                 pos = pos->next)
288
289 /**
290  * __list_for_each      -       iterate over a list
291  * @pos:        the &struct list_head to use as a loop cursor.
292  * @head:       the head for your list.
293  *
294  * This variant differs from list_for_each() in that it's the
295  * simplest possible list iteration code, no prefetching is done.
296  * Use this for code that knows the list to be very short (empty
297  * or 1 entry) most of the time.
298  */
299 #define __list_for_each(pos, head) \
300         for (pos = (head)->next; pos != (head); pos = pos->next)
301
302 /**
303  * list_for_each_prev   -       iterate over a list backwards
304  * @pos:        the &struct list_head to use as a loop cursor.
305  * @head:       the head for your list.
306  */
307 #define list_for_each_prev(pos, head) \
308         for (pos = (head)->prev; pos != (head); \
309                 pos = pos->prev)
310
311 /**
312  * list_for_each_safe - iterate over a list safe against removal of list entry
313  * @pos:        the &struct list_head to use as a loop cursor.
314  * @n:          another &struct list_head to use as temporary storage
315  * @head:       the head for your list.
316  */
317 #define list_for_each_safe(pos, n, head) \
318         for (pos = (head)->next, n = pos->next; pos != (head); \
319                 pos = n, n = pos->next)
320
321 /**
322  * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
323  * @pos:        the &struct list_head to use as a loop cursor.
324  * @n:          another &struct list_head to use as temporary storage
325  * @head:       the head for your list.
326  */
327 #define list_for_each_prev_safe(pos, n, head) \
328         for (pos = (head)->prev, n = pos->prev; \
329              pos != (head); \
330              pos = n, n = pos->prev)
331
332 /**
333  * list_for_each_entry  -       iterate over list of given type
334  * @pos:        the type * to use as a loop cursor.
335  * @head:       the head for your list.
336  * @member:     the name of the list_struct within the struct.
337  */
338 #define list_for_each_entry(pos, head, member)                          \
339         for (pos = list_entry((head)->next, typeof(*pos), member);      \
340              &pos->member != (head);    \
341              pos = list_entry(pos->member.next, typeof(*pos), member))
342
343 /**
344  * list_for_each_entry_reverse - iterate backwards over list of given type.
345  * @pos:        the type * to use as a loop cursor.
346  * @head:       the head for your list.
347  * @member:     the name of the list_struct within the struct.
348  */
349 #define list_for_each_entry_reverse(pos, head, member)                  \
350         for (pos = list_entry((head)->prev, typeof(*pos), member);      \
351              &pos->member != (head);    \
352              pos = list_entry(pos->member.prev, typeof(*pos), member))
353
354 /**
355  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
356  * @pos:        the type * to use as a start point
357  * @head:       the head of the list
358  * @member:     the name of the list_struct within the struct.
359  *
360  * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
361  */
362 #define list_prepare_entry(pos, head, member) \
363         ((pos) ? : list_entry(head, typeof(*pos), member))
364
365 /**
366  * list_for_each_entry_continue - continue iteration over list of given type
367  * @pos:        the type * to use as a loop cursor.
368  * @head:       the head for your list.
369  * @member:     the name of the list_struct within the struct.
370  *
371  * Continue to iterate over list of given type, continuing after
372  * the current position.
373  */
374 #define list_for_each_entry_continue(pos, head, member)                 \
375         for (pos = list_entry(pos->member.next, typeof(*pos), member);  \
376              &pos->member != (head);    \
377              pos = list_entry(pos->member.next, typeof(*pos), member))
378
379 /**
380  * list_for_each_entry_continue_reverse - iterate backwards from the given point
381  * @pos:        the type * to use as a loop cursor.
382  * @head:       the head for your list.
383  * @member:     the name of the list_struct within the struct.
384  *
385  * Start to iterate over list of given type backwards, continuing after
386  * the current position.
387  */
388 #define list_for_each_entry_continue_reverse(pos, head, member)         \
389         for (pos = list_entry(pos->member.prev, typeof(*pos), member);  \
390              &pos->member != (head);    \
391              pos = list_entry(pos->member.prev, typeof(*pos), member))
392
393 /**
394  * list_for_each_entry_from - iterate over list of given type from the current point
395  * @pos:        the type * to use as a loop cursor.
396  * @head:       the head for your list.
397  * @member:     the name of the list_struct within the struct.
398  *
399  * Iterate over list of given type, continuing from current position.
400  */
401 #define list_for_each_entry_from(pos, head, member)                     \
402         for (; &pos->member != (head);  \
403              pos = list_entry(pos->member.next, typeof(*pos), member))
404
405 /**
406  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
407  * @pos:        the type * to use as a loop cursor.
408  * @n:          another type * to use as temporary storage
409  * @head:       the head for your list.
410  * @member:     the name of the list_struct within the struct.
411  */
412 #define list_for_each_entry_safe(pos, n, head, member)                  \
413         for (pos = list_entry((head)->next, typeof(*pos), member),      \
414                 n = list_entry(pos->member.next, typeof(*pos), member); \
415              &pos->member != (head);                                    \
416              pos = n, n = list_entry(n->member.next, typeof(*n), member))
417
418 /**
419  * list_for_each_entry_safe_continue
420  * @pos:        the type * to use as a loop cursor.
421  * @n:          another type * to use as temporary storage
422  * @head:       the head for your list.
423  * @member:     the name of the list_struct within the struct.
424  *
425  * Iterate over list of given type, continuing after current point,
426  * safe against removal of list entry.
427  */
428 #define list_for_each_entry_safe_continue(pos, n, head, member)                 \
429         for (pos = list_entry(pos->member.next, typeof(*pos), member),          \
430                 n = list_entry(pos->member.next, typeof(*pos), member);         \
431              &pos->member != (head);                                            \
432              pos = n, n = list_entry(n->member.next, typeof(*n), member))
433
434 /**
435  * list_for_each_entry_safe_from
436  * @pos:        the type * to use as a loop cursor.
437  * @n:          another type * to use as temporary storage
438  * @head:       the head for your list.
439  * @member:     the name of the list_struct within the struct.
440  *
441  * Iterate over list of given type from current point, safe against
442  * removal of list entry.
443  */
444 #define list_for_each_entry_safe_from(pos, n, head, member)                     \
445         for (n = list_entry(pos->member.next, typeof(*pos), member);            \
446              &pos->member != (head);                                            \
447              pos = n, n = list_entry(n->member.next, typeof(*n), member))
448
449 /**
450  * list_for_each_entry_safe_reverse
451  * @pos:        the type * to use as a loop cursor.
452  * @n:          another type * to use as temporary storage
453  * @head:       the head for your list.
454  * @member:     the name of the list_struct within the struct.
455  *
456  * Iterate backwards over list of given type, safe against removal
457  * of list entry.
458  */
459 #define list_for_each_entry_safe_reverse(pos, n, head, member)          \
460         for (pos = list_entry((head)->prev, typeof(*pos), member),      \
461                 n = list_entry(pos->member.prev, typeof(*pos), member); \
462              &pos->member != (head);                                    \
463              pos = n, n = list_entry(n->member.prev, typeof(*n), member))
464
465 #endif