ia64/xen-unstable

view tools/xenstore/list.h @ 6946:e703abaf6e3d

Add behaviour to the remove methods to remove the transaction's path itself. This allows us to write Remove(path) to remove the specified path rather than having to slice the path ourselves.
author emellor@ewan
date Sun Sep 18 14:42:13 2005 +0100 (2005-09-18)
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