]>
git.ipfire.org Git - people/ms/mstpd.git/blob - list.h
3 * I grub it from linux kernel source code and fix it for user space
4 * program. Of course, this is a GPL licensed header file.
6 * Here is a recipe to cook list.h for user space program
8 * 1. copy list.h from linux/include/list.h
10 * - #ifdef __KERNE__ and its #endif
12 * - prefetch() and rcu related functions
13 * 3. add macro offsetof() and container_of
15 * - kazutomo@mcs.anl.gov
21 * @name from other kernel headers
26 * Get offset of a member
29 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
33 * Casts a member of a structure out to the containing structure
34 * @param ptr the pointer to the member.
35 * @param type the type of the container struct this is embedded in.
36 * @param member the name of the member within the struct.
39 #define container_of(ptr, type, member) ({ \
40 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
41 (type *)( (char *)__mptr - offsetof(type,member) );})
46 * These are non-NULL pointers that will result in page faults
47 * under normal circumstances, used to verify that nobody uses
48 * non-initialized list entries.
50 #define LIST_POISON1 ((void *) 0x00100100)
51 #define LIST_POISON2 ((void *) 0x00200200)
54 * Simple doubly linked list implementation.
56 * Some of the internal functions ("__xxx") are useful when
57 * manipulating whole lists rather than single entries, as
58 * sometimes we already know the next/prev entries and we can
59 * generate better code by using them directly rather than
60 * using the generic single-entry routines.
63 struct list_head
*next
, *prev
;
66 #define LIST_HEAD_INIT(name) { &(name), &(name) }
68 #define LIST_HEAD(name) \
69 struct list_head name = LIST_HEAD_INIT(name)
71 #define INIT_LIST_HEAD(ptr) do { \
72 (ptr)->next = (ptr); (ptr)->prev = (ptr); \
76 * Insert a new entry between two known consecutive entries.
78 * This is only for internal list manipulation where we know
79 * the prev/next entries already!
81 static inline void __list_add(struct list_head
*new,
82 struct list_head
*prev
,
83 struct list_head
*next
)
92 * list_add - add a new entry
93 * @new: new entry to be added
94 * @head: list head to add it after
96 * Insert a new entry after the specified head.
97 * This is good for implementing stacks.
99 static inline void list_add(struct list_head
*new, struct list_head
*head
)
101 __list_add(new, head
, head
->next
);
105 * list_add_tail - add a new entry
106 * @new: new entry to be added
107 * @head: list head to add it before
109 * Insert a new entry before the specified head.
110 * This is useful for implementing queues.
112 static inline void list_add_tail(struct list_head
*new, struct list_head
*head
)
114 __list_add(new, head
->prev
, head
);
119 * Delete a list entry by making the prev/next entries
120 * point to each other.
122 * This is only for internal list manipulation where we know
123 * the prev/next entries already!
125 static inline void __list_del(struct list_head
* prev
, struct list_head
* next
)
132 * list_del - deletes entry from list.
133 * @entry: the element to delete from the list.
134 * Note: list_empty on entry does not return true after this, the entry is
135 * in an undefined state.
137 static inline void list_del(struct list_head
*entry
)
139 __list_del(entry
->prev
, entry
->next
);
140 entry
->next
= LIST_POISON1
;
141 entry
->prev
= LIST_POISON2
;
147 * list_del_init - deletes entry from list and reinitialize it.
148 * @entry: the element to delete from the list.
150 static inline void list_del_init(struct list_head
*entry
)
152 __list_del(entry
->prev
, entry
->next
);
153 INIT_LIST_HEAD(entry
);
157 * list_move - delete from one list and add as another's head
158 * @list: the entry to move
159 * @head: the head that will precede our entry
161 static inline void list_move(struct list_head
*list
, struct list_head
*head
)
163 __list_del(list
->prev
, list
->next
);
164 list_add(list
, head
);
168 * list_move_tail - delete from one list and add as another's tail
169 * @list: the entry to move
170 * @head: the head that will follow our entry
172 static inline void list_move_tail(struct list_head
*list
,
173 struct list_head
*head
)
175 __list_del(list
->prev
, list
->next
);
176 list_add_tail(list
, head
);
180 * list_empty - tests whether a list is empty
181 * @head: the list to test.
183 static inline int list_empty(const struct list_head
*head
)
185 return head
->next
== head
;
188 static inline void __list_splice(struct list_head
*list
,
189 struct list_head
*head
)
191 struct list_head
*first
= list
->next
;
192 struct list_head
*last
= list
->prev
;
193 struct list_head
*at
= head
->next
;
203 * list_splice - join two lists
204 * @list: the new list to add.
205 * @head: the place to add it in the first list.
207 static inline void list_splice(struct list_head
*list
, struct list_head
*head
)
209 if (!list_empty(list
))
210 __list_splice(list
, head
);
214 * list_splice_init - join two lists and reinitialise the emptied list.
215 * @list: the new list to add.
216 * @head: the place to add it in the first list.
218 * The list at @list is reinitialised
220 static inline void list_splice_init(struct list_head
*list
,
221 struct list_head
*head
)
223 if (!list_empty(list
)) {
224 __list_splice(list
, head
);
225 INIT_LIST_HEAD(list
);
230 * list_entry - get the struct for this entry
231 * @ptr: the &struct list_head pointer.
232 * @type: the type of the struct this is embedded in.
233 * @member: the name of the list_struct within the struct.
235 #define list_entry(ptr, type, member) \
236 container_of(ptr, type, member)
239 * list_for_each - iterate over a list
240 * @pos: the &struct list_head to use as a loop counter.
241 * @head: the head for your list.
244 #define list_for_each(pos, head) \
245 for (pos = (head)->next; pos != (head); \
249 * __list_for_each - iterate over a list
250 * @pos: the &struct list_head to use as a loop counter.
251 * @head: the head for your list.
253 * This variant differs from list_for_each() in that it's the
254 * simplest possible list iteration code, no prefetching is done.
255 * Use this for code that knows the list to be very short (empty
256 * or 1 entry) most of the time.
258 #define __list_for_each(pos, head) \
259 for (pos = (head)->next; pos != (head); pos = pos->next)
262 * list_for_each_prev - iterate over a list backwards
263 * @pos: the &struct list_head to use as a loop counter.
264 * @head: the head for your list.
266 #define list_for_each_prev(pos, head) \
267 for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
271 * list_for_each_safe - iterate over a list safe against removal of list entry
272 * @pos: the &struct list_head to use as a loop counter.
273 * @n: another &struct list_head to use as temporary storage
274 * @head: the head for your list.
276 #define list_for_each_safe(pos, n, head) \
277 for (pos = (head)->next, n = pos->next; pos != (head); \
278 pos = n, n = pos->next)
281 * list_for_each_entry - iterate over list of given type
282 * @pos: the type * to use as a loop counter.
283 * @head: the head for your list.
284 * @member: the name of the list_struct within the struct.
286 #define list_for_each_entry(pos, head, member) \
287 for (pos = list_entry((head)->next, typeof(*pos), member); \
288 &pos->member != (head); \
289 pos = list_entry(pos->member.next, typeof(*pos), member))
292 * list_for_each_entry_reverse - iterate backwards over list of given type.
293 * @pos: the type * to use as a loop counter.
294 * @head: the head for your list.
295 * @member: the name of the list_struct within the struct.
297 #define list_for_each_entry_reverse(pos, head, member) \
298 for (pos = list_entry((head)->prev, typeof(*pos), member); \
299 &pos->member != (head); \
300 pos = list_entry(pos->member.prev, typeof(*pos), member))
303 * list_prepare_entry - prepare a pos entry for use as a start point in
304 * list_for_each_entry_continue
305 * @pos: the type * to use as a start point
306 * @head: the head of the list
307 * @member: the name of the list_struct within the struct.
309 #define list_prepare_entry(pos, head, member) \
310 ((pos) ? : list_entry(head, typeof(*pos), member))
313 * list_for_each_entry_continue - iterate over list of given type
314 * continuing after existing point
315 * @pos: the type * to use as a loop counter.
316 * @head: the head for your list.
317 * @member: the name of the list_struct within the struct.
319 #define list_for_each_entry_continue(pos, head, member) \
320 for (pos = list_entry(pos->member.next, typeof(*pos), member); \
321 &pos->member != (head); \
322 pos = list_entry(pos->member.next, typeof(*pos), member))
325 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
326 * @pos: the type * to use as a loop counter.
327 * @n: another type * to use as temporary storage
328 * @head: the head for your list.
329 * @member: the name of the list_struct within the struct.
331 #define list_for_each_entry_safe(pos, n, head, member) \
332 for (pos = list_entry((head)->next, typeof(*pos), member), \
333 n = list_entry(pos->member.next, typeof(*pos), member); \
334 &pos->member != (head); \
335 pos = n, n = list_entry(n->member.next, typeof(*n), member))
338 * list_for_each_entry_safe_continue - iterate over list of given type
339 * continuing after existing point safe against removal of list entry
340 * @pos: the type * to use as a loop counter.
341 * @n: another type * to use as temporary storage
342 * @head: the head for your list.
343 * @member: the name of the list_struct within the struct.
345 #define list_for_each_entry_safe_continue(pos, n, head, member) \
346 for (pos = list_entry(pos->member.next, typeof(*pos), member), \
347 n = list_entry(pos->member.next, typeof(*pos), member); \
348 &pos->member != (head); \
349 pos = n, n = list_entry(n->member.next, typeof(*n), member))
352 * list_for_each_entry_safe_reverse - iterate backwards over list of given type safe against
353 * removal of list entry
354 * @pos: the type * to use as a loop counter.
355 * @n: another type * to use as temporary storage
356 * @head: the head for your list.
357 * @member: the name of the list_struct within the struct.
359 #define list_for_each_entry_safe_reverse(pos, n, head, member) \
360 for (pos = list_entry((head)->prev, typeof(*pos), member), \
361 n = list_entry(pos->member.prev, typeof(*pos), member); \
362 &pos->member != (head); \
363 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
369 * Double linked lists with a single pointer list head.
370 * Mostly useful for hash tables where the two pointer list head is
372 * You lose the ability to access the tail in O(1).
376 struct hlist_node
*first
;
380 struct hlist_node
*next
, **pprev
;
383 #define HLIST_HEAD_INIT { .first = NULL }
384 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
385 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
386 #define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)
388 static inline int hlist_unhashed(const struct hlist_node
*h
)
393 static inline int hlist_empty(const struct hlist_head
*h
)
398 static inline void __hlist_del(struct hlist_node
*n
)
400 struct hlist_node
*next
= n
->next
;
401 struct hlist_node
**pprev
= n
->pprev
;
407 static inline void hlist_del(struct hlist_node
*n
)
410 n
->next
= LIST_POISON1
;
411 n
->pprev
= LIST_POISON2
;
415 static inline void hlist_del_init(struct hlist_node
*n
)
423 static inline void hlist_add_head(struct hlist_node
*n
, struct hlist_head
*h
)
425 struct hlist_node
*first
= h
->first
;
428 first
->pprev
= &n
->next
;
430 n
->pprev
= &h
->first
;
435 /* next must be != NULL */
436 static inline void hlist_add_before(struct hlist_node
*n
,
437 struct hlist_node
*next
)
439 n
->pprev
= next
->pprev
;
441 next
->pprev
= &n
->next
;
445 static inline void hlist_add_after(struct hlist_node
*n
,
446 struct hlist_node
*next
)
448 next
->next
= n
->next
;
450 next
->pprev
= &n
->next
;
453 next
->next
->pprev
= &next
->next
;
458 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
460 #define hlist_for_each(pos, head) \
461 for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
464 #define hlist_for_each_safe(pos, n, head) \
465 for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
469 * hlist_for_each_entry - iterate over list of given type
470 * @tpos: the type * to use as a loop counter.
471 * @pos: the &struct hlist_node to use as a loop counter.
472 * @head: the head for your list.
473 * @member: the name of the hlist_node within the struct.
475 #define hlist_for_each_entry(tpos, pos, head, member) \
476 for (pos = (head)->first; \
477 pos && ({ prefetch(pos->next); 1;}) && \
478 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
482 * hlist_for_each_entry_continue - iterate over a hlist continuing after existing point
483 * @tpos: the type * to use as a loop counter.
484 * @pos: the &struct hlist_node to use as a loop counter.
485 * @member: the name of the hlist_node within the struct.
487 #define hlist_for_each_entry_continue(tpos, pos, member) \
488 for (pos = (pos)->next; \
489 pos && ({ prefetch(pos->next); 1;}) && \
490 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
494 * hlist_for_each_entry_from - iterate over a hlist continuing from existing point
495 * @tpos: the type * to use as a loop counter.
496 * @pos: the &struct hlist_node to use as a loop counter.
497 * @member: the name of the hlist_node within the struct.
499 #define hlist_for_each_entry_from(tpos, pos, member) \
500 for (; pos && ({ prefetch(pos->next); 1;}) && \
501 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
505 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
506 * @tpos: the type * to use as a loop counter.
507 * @pos: the &struct hlist_node to use as a loop counter.
508 * @n: another &struct hlist_node to use as temporary storage
509 * @head: the head for your list.
510 * @member: the name of the hlist_node within the struct.
512 #define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
513 for (pos = (head)->first; \
514 pos && ({ n = pos->next; 1; }) && \
515 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \