ia64/xen-unstable

view tools/xenstore/list.h @ 6812:26cf3cfd3bed

Switch vcpu hotplugging to use xstransact.
Signed-off-by: Christian Limpach <Christian.Limpach@cl.cam.ac.uk>
author cl349@firebug.cl.cam.ac.uk
date Tue Sep 13 17:31:13 2005 +0000 (2005-09-13)
parents 6d3e8f90c2df
children 3e2d3d737624
line source
1 #ifndef _LINUX_LIST_H
2 #define _LINUX_LIST_H
3 /* Taken from Linux kernel code, but de-kernelized for userspace. */
4 #include <stddef.h>
6 /*
7 * These are non-NULL pointers that will result in page faults
8 * under normal circumstances, used to verify that nobody uses
9 * non-initialized list entries.
10 */
11 #define LIST_POISON1 ((void *) 0x00100100)
12 #define LIST_POISON2 ((void *) 0x00200200)
14 #define container_of(ptr, type, member) ({ \
15 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
16 (type *)( (char *)__mptr - offsetof(type,member) );})
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 */
28 struct list_head {
29 struct list_head *next, *prev;
30 };
32 #define LIST_HEAD_INIT(name) { &(name), &(name) }
34 #define LIST_HEAD(name) \
35 struct list_head name = LIST_HEAD_INIT(name)
37 #define INIT_LIST_HEAD(ptr) do { \
38 (ptr)->next = (ptr); (ptr)->prev = (ptr); \
39 } while (0)
41 #define list_top(head, type, member) \
42 ({ \
43 struct list_head *_head = (head); \
44 list_empty(_head) ? NULL : list_entry(_head->next, type, member); \
45 })
47 /*
48 * Insert a new entry between two known consecutive entries.
49 *
50 * This is only for internal list manipulation where we know
51 * the prev/next entries already!
52 */
53 static inline void __list_add(struct list_head *new,
54 struct list_head *prev,
55 struct list_head *next)
56 {
57 next->prev = new;
58 new->next = next;
59 new->prev = prev;
60 prev->next = new;
61 }
63 /**
64 * list_add - add a new entry
65 * @new: new entry to be added
66 * @head: list head to add it after
67 *
68 * Insert a new entry after the specified head.
69 * This is good for implementing stacks.
70 */
71 static inline void list_add(struct list_head *new, struct list_head *head)
72 {
73 __list_add(new, head, head->next);
74 }
76 /**
77 * list_add_tail - add a new entry
78 * @new: new entry to be added
79 * @head: list head to add it before
80 *
81 * Insert a new entry before the specified head.
82 * This is useful for implementing queues.
83 */
84 static inline void list_add_tail(struct list_head *new, struct list_head *head)
85 {
86 __list_add(new, head->prev, head);
87 }
89 /*
90 * Insert a new entry between two known consecutive entries.
91 *
92 * This is only for internal list manipulation where we know
93 * the prev/next entries already!
94 */
95 static __inline__ void __list_add_rcu(struct list_head * new,
96 struct list_head * prev,
97 struct list_head * next)
98 {
99 new->next = next;
100 new->prev = prev;
101 next->prev = new;
102 prev->next = new;
103 }
105 /**
106 * list_add_rcu - add a new entry to rcu-protected list
107 * @new: new entry to be added
108 * @head: list head to add it after
109 *
110 * Insert a new entry after the specified head.
111 * This is good for implementing stacks.
112 */
113 static __inline__ void list_add_rcu(struct list_head *new, struct list_head *head)
114 {
115 __list_add_rcu(new, head, head->next);
116 }
118 /**
119 * list_add_tail_rcu - add a new entry to rcu-protected list
120 * @new: new entry to be added
121 * @head: list head to add it before
122 *
123 * Insert a new entry before the specified head.
124 * This is useful for implementing queues.
125 */
126 static __inline__ void list_add_tail_rcu(struct list_head *new, struct list_head *head)
127 {
128 __list_add_rcu(new, head->prev, head);
129 }
131 /*
132 * Delete a list entry by making the prev/next entries
133 * point to each other.
134 *
135 * This is only for internal list manipulation where we know
136 * the prev/next entries already!
137 */
138 static inline void __list_del(struct list_head * prev, struct list_head * next)
139 {
140 next->prev = prev;
141 prev->next = next;
142 }
144 /**
145 * list_del - deletes entry from list.
146 * @entry: the element to delete from the list.
147 * Note: list_empty on entry does not return true after this, the entry is
148 * in an undefined state.
149 */
150 static inline void list_del(struct list_head *entry)
151 {
152 __list_del(entry->prev, entry->next);
153 entry->next = LIST_POISON1;
154 entry->prev = LIST_POISON2;
155 }
157 /**
158 * list_del_rcu - deletes entry from list without re-initialization
159 * @entry: the element to delete from the list.
160 *
161 * Note: list_empty on entry does not return true after this,
162 * the entry is in an undefined state. It is useful for RCU based
163 * lockfree traversal.
164 *
165 * In particular, it means that we can not poison the forward
166 * pointers that may still be used for walking the list.
167 */
168 static inline void list_del_rcu(struct list_head *entry)
169 {
170 __list_del(entry->prev, entry->next);
171 entry->prev = LIST_POISON2;
172 }
174 /**
175 * list_del_init - deletes entry from list and reinitialize it.
176 * @entry: the element to delete from the list.
177 */
178 static inline void list_del_init(struct list_head *entry)
179 {
180 __list_del(entry->prev, entry->next);
181 INIT_LIST_HEAD(entry);
182 }
184 /**
185 * list_move - delete from one list and add as another's head
186 * @list: the entry to move
187 * @head: the head that will precede our entry
188 */
189 static inline void list_move(struct list_head *list, struct list_head *head)
190 {
191 __list_del(list->prev, list->next);
192 list_add(list, head);
193 }
195 /**
196 * list_move_tail - delete from one list and add as another's tail
197 * @list: the entry to move
198 * @head: the head that will follow our entry
199 */
200 static inline void list_move_tail(struct list_head *list,
201 struct list_head *head)
202 {
203 __list_del(list->prev, list->next);
204 list_add_tail(list, head);
205 }
207 /**
208 * list_empty - tests whether a list is empty
209 * @head: the list to test.
210 */
211 static inline int list_empty(struct list_head *head)
212 {
213 return head->next == head;
214 }
216 static inline void __list_splice(struct list_head *list,
217 struct list_head *head)
218 {
219 struct list_head *first = list->next;
220 struct list_head *last = list->prev;
221 struct list_head *at = head->next;
223 first->prev = head;
224 head->next = first;
226 last->next = at;
227 at->prev = last;
228 }
230 /**
231 * list_splice - join two lists
232 * @list: the new list to add.
233 * @head: the place to add it in the first list.
234 */
235 static inline void list_splice(struct list_head *list, struct list_head *head)
236 {
237 if (!list_empty(list))
238 __list_splice(list, head);
239 }
241 /**
242 * list_splice_init - join two lists and reinitialise the emptied list.
243 * @list: the new list to add.
244 * @head: the place to add it in the first list.
245 *
246 * The list at @list is reinitialised
247 */
248 static inline void list_splice_init(struct list_head *list,
249 struct list_head *head)
250 {
251 if (!list_empty(list)) {
252 __list_splice(list, head);
253 INIT_LIST_HEAD(list);
254 }
255 }
257 /**
258 * list_entry - get the struct for this entry
259 * @ptr: the &struct list_head pointer.
260 * @type: the type of the struct this is embedded in.
261 * @member: the name of the list_struct within the struct.
262 */
263 #define list_entry(ptr, type, member) \
264 container_of(ptr, type, member)
266 /**
267 * list_for_each - iterate over a list
268 * @pos: the &struct list_head to use as a loop counter.
269 * @head: the head for your list.
270 */
271 #define list_for_each(pos, head) \
272 for (pos = (head)->next; pos != (head); pos = pos->next)
274 /**
275 * list_for_each_prev - iterate over a list backwards
276 * @pos: the &struct list_head to use as a loop counter.
277 * @head: the head for your list.
278 */
279 #define list_for_each_prev(pos, head) \
280 for (pos = (head)->prev; pos != (head); pos = pos->prev)
282 /**
283 * list_for_each_safe - iterate over a list safe against removal of list entry
284 * @pos: the &struct list_head to use as a loop counter.
285 * @n: another &struct list_head to use as temporary storage
286 * @head: the head for your list.
287 */
288 #define list_for_each_safe(pos, n, head) \
289 for (pos = (head)->next, n = pos->next; pos != (head); \
290 pos = n, n = pos->next)
292 /**
293 * list_for_each_entry - iterate over list of given type
294 * @pos: the type * to use as a loop counter.
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(pos, head, member) \
299 for (pos = list_entry((head)->next, typeof(*pos), member); \
300 &pos->member != (head); \
301 pos = list_entry(pos->member.next, typeof(*pos), member))
303 /**
304 * list_for_each_entry_reverse - iterate backwards over list of given type.
305 * @pos: the type * to use as a loop counter.
306 * @head: the head for your list.
307 * @member: the name of the list_struct within the struct.
308 */
309 #define list_for_each_entry_reverse(pos, head, member) \
310 for (pos = list_entry((head)->prev, typeof(*pos), member); \
311 &pos->member != (head); \
312 pos = list_entry(pos->member.prev, typeof(*pos), member))
315 /**
316 * list_for_each_entry_continue - iterate over list of given type
317 * continuing after existing point
318 * @pos: the type * to use as a loop counter.
319 * @head: the head for your list.
320 * @member: the name of the list_struct within the struct.
321 */
322 #define list_for_each_entry_continue(pos, head, member) \
323 for (pos = list_entry(pos->member.next, typeof(*pos), member); \
324 &pos->member != (head); \
325 pos = list_entry(pos->member.next, typeof(*pos), member))
327 /**
328 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
329 * @pos: the type * to use as a loop counter.
330 * @n: another type * to use as temporary storage
331 * @head: the head for your list.
332 * @member: the name of the list_struct within the struct.
333 */
334 #define list_for_each_entry_safe(pos, n, head, member) \
335 for (pos = list_entry((head)->next, typeof(*pos), member), \
336 n = list_entry(pos->member.next, typeof(*pos), member); \
337 &pos->member != (head); \
338 pos = n, n = list_entry(n->member.next, typeof(*n), member))
341 /*
342 * Double linked lists with a single pointer list head.
343 * Mostly useful for hash tables where the two pointer list head is
344 * too wasteful.
345 * You lose the ability to access the tail in O(1).
346 */
348 struct hlist_head {
349 struct hlist_node *first;
350 };
352 struct hlist_node {
353 struct hlist_node *next, **pprev;
354 };
356 #define HLIST_HEAD_INIT { .first = NULL }
357 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
358 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
359 #define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)
361 static __inline__ int hlist_unhashed(struct hlist_node *h)
362 {
363 return !h->pprev;
364 }
366 static __inline__ int hlist_empty(struct hlist_head *h)
367 {
368 return !h->first;
369 }
371 static __inline__ void __hlist_del(struct hlist_node *n)
372 {
373 struct hlist_node *next = n->next;
374 struct hlist_node **pprev = n->pprev;
375 *pprev = next;
376 if (next)
377 next->pprev = pprev;
378 }
380 static __inline__ void hlist_del(struct hlist_node *n)
381 {
382 __hlist_del(n);
383 n->next = LIST_POISON1;
384 n->pprev = LIST_POISON2;
385 }
387 /**
388 * hlist_del_rcu - deletes entry from hash list without re-initialization
389 * @entry: the element to delete from the hash list.
390 *
391 * Note: list_unhashed() on entry does not return true after this,
392 * the entry is in an undefined state. It is useful for RCU based
393 * lockfree traversal.
394 *
395 * In particular, it means that we can not poison the forward
396 * pointers that may still be used for walking the hash list.
397 */
398 static inline void hlist_del_rcu(struct hlist_node *n)
399 {
400 __hlist_del(n);
401 n->pprev = LIST_POISON2;
402 }
404 static __inline__ void hlist_del_init(struct hlist_node *n)
405 {
406 if (n->pprev) {
407 __hlist_del(n);
408 INIT_HLIST_NODE(n);
409 }
410 }
412 #define hlist_del_rcu_init hlist_del_init
414 static __inline__ void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
415 {
416 struct hlist_node *first = h->first;
417 n->next = first;
418 if (first)
419 first->pprev = &n->next;
420 h->first = n;
421 n->pprev = &h->first;
422 }
424 static __inline__ void hlist_add_head_rcu(struct hlist_node *n, struct hlist_head *h)
425 {
426 struct hlist_node *first = h->first;
427 n->next = first;
428 n->pprev = &h->first;
429 if (first)
430 first->pprev = &n->next;
431 h->first = n;
432 }
434 /* next must be != NULL */
435 static __inline__ void hlist_add_before(struct hlist_node *n, struct hlist_node *next)
436 {
437 n->pprev = next->pprev;
438 n->next = next;
439 next->pprev = &n->next;
440 *(n->pprev) = n;
441 }
443 static __inline__ void hlist_add_after(struct hlist_node *n,
444 struct hlist_node *next)
445 {
446 next->next = n->next;
447 *(next->pprev) = n;
448 n->next = next;
449 }
451 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
453 /* Cannot easily do prefetch unfortunately */
454 #define hlist_for_each(pos, head) \
455 for (pos = (head)->first; pos; pos = pos->next)
457 #define hlist_for_each_safe(pos, n, head) \
458 for (pos = (head)->first; n = pos ? pos->next : 0, pos; \
459 pos = n)
461 /**
462 * hlist_for_each_entry - iterate over list of given type
463 * @tpos: the type * to use as a loop counter.
464 * @pos: the &struct hlist_node to use as a loop counter.
465 * @head: the head for your list.
466 * @member: the name of the hlist_node within the struct.
467 */
468 #define hlist_for_each_entry(tpos, pos, head, member) \
469 for (pos = (head)->first; \
470 pos && ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
471 pos = pos->next)
473 /**
474 * hlist_for_each_entry_continue - iterate over a hlist continuing after existing point
475 * @tpos: the type * to use as a loop counter.
476 * @pos: the &struct hlist_node to use as a loop counter.
477 * @member: the name of the hlist_node within the struct.
478 */
479 #define hlist_for_each_entry_continue(tpos, pos, member) \
480 for (pos = (pos)->next; \
481 pos && ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
482 pos = pos->next)
484 /**
485 * hlist_for_each_entry_from - iterate over a hlist continuing from existing point
486 * @tpos: the type * to use as a loop counter.
487 * @pos: the &struct hlist_node to use as a loop counter.
488 * @member: the name of the hlist_node within the struct.
489 */
490 #define hlist_for_each_entry_from(tpos, pos, member) \
491 for (; pos && ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
492 pos = pos->next)
494 /**
495 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
496 * @tpos: the type * to use as a loop counter.
497 * @pos: the &struct hlist_node to use as a loop counter.
498 * @n: another &struct hlist_node to use as temporary storage
499 * @head: the head for your list.
500 * @member: the name of the hlist_node within the struct.
501 */
502 #define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
503 for (pos = (head)->first; \
504 pos && ({ n = pos->next; 1; }) && \
505 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
506 pos = n)
508 #endif