/[vps]/baselayout-vserver/trunk/src/core/list.h
Gentoo

Diff of /baselayout-vserver/trunk/src/core/list.h

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

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

Legend:
Removed from v.126  
changed lines
  Added in v.127

  ViewVC Help
Powered by ViewVC 1.1.20