Palacios Public Git Repository

To checkout Palacios execute

  git clone http://v3vee.org/palacios/palacios.web/palacios.git
This will give you the master branch. You probably want the devel branch or one of the release branches. To switch to the devel branch, simply execute
  cd palacios
  git checkout --track -b devel origin/devel
The other branches are similar.


Merge branch 'devel'
[palacios-OLD.git] / geekos / include / geekos / list2.h
1 /* (c) 2008, Jack Lange <jarusl@cs.northwestern.edu> */
2 /* (c) 2008, The V3VEE Project <http://www.v3vee.org> */
3
4 #ifndef _LIST2_H
5 #define _LIST2_H
6
7 // JRL FIXME
8 // #ifdef __V3VEE__
9
10 #include <geekos/string.h>
11
12 #undef offsetof
13 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
14
15
16 #define container_of(ptr, type, member) ({                      \
17         const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
18         (type *)( (char *)__mptr - offsetof(type,member) );})
19
20
21 static inline void prefetch(const void *x) {;}
22
23 /*
24  * These are non-NULL pointers that will result in page faults
25  * under normal circumstances, used to verify that nobody uses
26  * non-initialized list entries.
27  */
28 #define LIST_POISON1  ((void *) 0x00100100)
29 #define LIST_POISON2  ((void *) 0x00200200)
30
31 /*
32  * Simple doubly linked list implementation.
33  *
34  * Some of the internal functions ("__xxx") are useful when
35  * manipulating whole lists rather than single entries, as
36  * sometimes we already know the next/prev entries and we can
37  * generate better code by using them directly rather than
38  * using the generic single-entry routines.
39  */
40
41 struct list_head {
42         struct list_head *next, *prev;
43 };
44
45 #define LIST_HEAD_INIT(name) { &(name), &(name) }
46
47 #define LIST_HEAD(name) \
48         struct list_head name = LIST_HEAD_INIT(name)
49
50 static inline void INIT_LIST_HEAD(struct list_head *list)
51 {
52         list->next = list;
53         list->prev = list;
54 }
55
56 /*
57  * Insert a new entry between two known consecutive entries.
58  *
59  * This is only for internal list manipulation where we know
60  * the prev/next entries already!
61  */
62 static inline void __list_add(struct list_head *new,
63                               struct list_head *prev,
64                               struct list_head *next)
65 {
66         next->prev = new;
67         new->next = next;
68         new->prev = prev;
69         prev->next = new;
70 }
71
72 /**
73  * list_add - add a new entry
74  * @new: new entry to be added
75  * @head: list head to add it after
76  *
77  * Insert a new entry after the specified head.
78  * This is good for implementing stacks.
79  */
80 static inline void list_add(struct list_head *new, struct list_head *head)
81 {
82         __list_add(new, head, head->next);
83 }
84
85 /**
86  * list_add_tail - add a new entry
87  * @new: new entry to be added
88  * @head: list head to add it before
89  *
90  * Insert a new entry before the specified head.
91  * This is useful for implementing queues.
92  */
93 static inline void list_add_tail(struct list_head *new, struct list_head *head)
94 {
95         __list_add(new, head->prev, head);
96 }
97
98 /*
99  * Delete a list entry by making the prev/next entries
100  * point to each other.
101  *
102  * This is only for internal list manipulation where we know
103  * the prev/next entries already!
104  */
105 static inline void __list_del(struct list_head * prev, struct list_head * next)
106 {
107         next->prev = prev;
108         prev->next = next;
109 }
110
111 /**
112  * list_del - deletes entry from list.
113  * @entry: the element to delete from the list.
114  * Note: list_empty on entry does not return true after this, the entry is
115  * in an undefined state.
116  */
117 static inline void list_del(struct list_head *entry)
118 {
119         __list_del(entry->prev, entry->next);
120         entry->next = LIST_POISON1;
121         entry->prev = LIST_POISON2;
122 }
123
124 /**
125  * list_del_init - deletes entry from list and reinitialize it.
126  * @entry: the element to delete from the list.
127  */
128 static inline void list_del_init(struct list_head *entry)
129 {
130         __list_del(entry->prev, entry->next);
131         INIT_LIST_HEAD(entry);
132 }
133
134 /**
135  * list_move - delete from one list and add as another's head
136  * @list: the entry to move
137  * @head: the head that will precede our entry
138  */
139 static inline void list_move(struct list_head *list, struct list_head *head)
140 {
141         __list_del(list->prev, list->next);
142         list_add(list, head);
143 }
144
145 /**
146  * list_move_tail - delete from one list and add as another's tail
147  * @list: the entry to move
148  * @head: the head that will follow our entry
149  */
150 static inline void list_move_tail(struct list_head *list,
151                                   struct list_head *head)
152 {
153         __list_del(list->prev, list->next);
154         list_add_tail(list, head);
155 }
156
157 /**
158  * list_empty - tests whether a list is empty
159  * @head: the list to test.
160  */
161 static inline int list_empty(const struct list_head *head)
162 {
163         return head->next == head;
164 }
165
166 /**
167  * list_empty_careful - tests whether a list is
168  * empty _and_ checks that no other CPU might be
169  * in the process of still modifying either member
170  *
171  * NOTE: using list_empty_careful() without synchronization
172  * can only be safe if the only activity that can happen
173  * to the list entry is list_del_init(). Eg. it cannot be used
174  * if another CPU could re-list_add() it.
175  *
176  * @head: the list to test.
177  */
178 static inline int list_empty_careful(const struct list_head *head)
179 {
180         struct list_head *next = head->next;
181         return (next == head) && (next == head->prev);
182 }
183
184 static inline void __list_splice(struct list_head *list,
185                                  struct list_head *head)
186 {
187         struct list_head *first = list->next;
188         struct list_head *last = list->prev;
189         struct list_head *at = head->next;
190
191         first->prev = head;
192         head->next = first;
193
194         last->next = at;
195         at->prev = last;
196 }
197
198 /**
199  * list_splice - join two lists
200  * @list: the new list to add.
201  * @head: the place to add it in the first list.
202  */
203 static inline void list_splice(struct list_head *list, struct list_head *head)
204 {
205         if (!list_empty(list))
206                 __list_splice(list, head);
207 }
208
209 /**
210  * list_splice_init - join two lists and reinitialise the emptied list.
211  * @list: the new list to add.
212  * @head: the place to add it in the first list.
213  *
214  * The list at @list is reinitialised
215  */
216 static inline void list_splice_init(struct list_head *list,
217                                     struct list_head *head)
218 {
219         if (!list_empty(list)) {
220                 __list_splice(list, head);
221                 INIT_LIST_HEAD(list);
222         }
223 }
224
225 /**
226  * list_entry - get the struct for this entry
227  * @ptr:        the &struct list_head pointer.
228  * @type:       the type of the struct this is embedded in.
229  * @member:     the name of the list_struct within the struct.
230  */
231 #define list_entry(ptr, type, member) \
232         container_of(ptr, type, member)
233
234 /**
235  * list_for_each        -       iterate over a list
236  * @pos:        the &struct list_head to use as a loop counter.
237  * @head:       the head for your list.
238  */
239 #define list_for_each(pos, head) \
240         for (pos = (head)->next; prefetch(pos->next), pos != (head); \
241                 pos = pos->next)
242
243 /**
244  * __list_for_each      -       iterate over a list
245  * @pos:        the &struct list_head to use as a loop counter.
246  * @head:       the head for your list.
247  *
248  * This variant differs from list_for_each() in that it's the
249  * simplest possible list iteration code, no prefetching is done.
250  * Use this for code that knows the list to be very short (empty
251  * or 1 entry) most of the time.
252  */
253 #define __list_for_each(pos, head) \
254         for (pos = (head)->next; pos != (head); pos = pos->next)
255
256 /**
257  * list_for_each_prev   -       iterate over a list backwards
258  * @pos:        the &struct list_head to use as a loop counter.
259  * @head:       the head for your list.
260  */
261 #define list_for_each_prev(pos, head) \
262         for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
263                 pos = pos->prev)
264
265 /**
266  * list_for_each_safe   -       iterate over a list safe against removal of list entry
267  * @pos:        the &struct list_head to use as a loop counter.
268  * @n:          another &struct list_head to use as temporary storage
269  * @head:       the head for your list.
270  */
271 #define list_for_each_safe(pos, n, head) \
272         for (pos = (head)->next, n = pos->next; pos != (head); \
273                 pos = n, n = pos->next)
274
275 /**
276  * list_for_each_entry  -       iterate over list of given type
277  * @pos:        the type * to use as a loop counter.
278  * @head:       the head for your list.
279  * @member:     the name of the list_struct within the struct.
280  */
281 #define list_for_each_entry(pos, head, member)                          \
282         for (pos = list_entry((head)->next, typeof(*pos), member);      \
283              prefetch(pos->member.next), &pos->member != (head);        \
284              pos = list_entry(pos->member.next, typeof(*pos), member))
285
286 /**
287  * list_for_each_entry_reverse - iterate backwards over list of given type.
288  * @pos:        the type * to use as a loop counter.
289  * @head:       the head for your list.
290  * @member:     the name of the list_struct within the struct.
291  */
292 #define list_for_each_entry_reverse(pos, head, member)                  \
293         for (pos = list_entry((head)->prev, typeof(*pos), member);      \
294              prefetch(pos->member.prev), &pos->member != (head);        \
295              pos = list_entry(pos->member.prev, typeof(*pos), member))
296
297 /**
298  * list_prepare_entry - prepare a pos entry for use as a start point in
299  *                      list_for_each_entry_continue
300  * @pos:        the type * to use as a start point
301  * @head:       the head of the list
302  * @member:     the name of the list_struct within the struct.
303  */
304 #define list_prepare_entry(pos, head, member) \
305         ((pos) ? : list_entry(head, typeof(*pos), member))
306
307 /**
308  * list_for_each_entry_continue -       iterate over list of given type
309  *                      continuing after existing point
310  * @pos:        the type * to use as a loop counter.
311  * @head:       the head for your list.
312  * @member:     the name of the list_struct within the struct.
313  */
314 #define list_for_each_entry_continue(pos, head, member)                 \
315         for (pos = list_entry(pos->member.next, typeof(*pos), member);  \
316              prefetch(pos->member.next), &pos->member != (head);        \
317              pos = list_entry(pos->member.next, typeof(*pos), member))
318
319 /**
320  * list_for_each_entry_from -   iterate over list of given type
321  *                      continuing from existing point
322  * @pos:        the type * to use as a loop counter.
323  * @head:       the head for your list.
324  * @member:     the name of the list_struct within the struct.
325  */
326 #define list_for_each_entry_from(pos, head, member)                     \
327         for (; prefetch(pos->member.next), &pos->member != (head);      \
328              pos = list_entry(pos->member.next, typeof(*pos), member))
329
330 /**
331  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
332  * @pos:        the type * to use as a loop counter.
333  * @n:          another type * to use as temporary storage
334  * @head:       the head for your list.
335  * @member:     the name of the list_struct within the struct.
336  */
337 #define list_for_each_entry_safe(pos, n, head, member)                  \
338         for (pos = list_entry((head)->next, typeof(*pos), member),      \
339                 n = list_entry(pos->member.next, typeof(*pos), member); \
340              &pos->member != (head);                                    \
341              pos = n, n = list_entry(n->member.next, typeof(*n), member))
342
343 /**
344  * list_for_each_entry_safe_continue -  iterate over list of given type
345  *                      continuing after existing point safe against removal of list entry
346  * @pos:        the type * to use as a loop counter.
347  * @n:          another type * to use as temporary storage
348  * @head:       the head for your list.
349  * @member:     the name of the list_struct within the struct.
350  */
351 #define list_for_each_entry_safe_continue(pos, n, head, member)                 \
352         for (pos = list_entry(pos->member.next, typeof(*pos), member),          \
353                 n = list_entry(pos->member.next, typeof(*pos), member);         \
354              &pos->member != (head);                                            \
355              pos = n, n = list_entry(n->member.next, typeof(*n), member))
356
357 /**
358  * list_for_each_entry_safe_from - iterate over list of given type
359  *                      from existing point safe against removal of list entry
360  * @pos:        the type * to use as a loop counter.
361  * @n:          another type * to use as temporary storage
362  * @head:       the head for your list.
363  * @member:     the name of the list_struct within the struct.
364  */
365 #define list_for_each_entry_safe_from(pos, n, head, member)                     \
366         for (n = list_entry(pos->member.next, typeof(*pos), member);            \
367              &pos->member != (head);                                            \
368              pos = n, n = list_entry(n->member.next, typeof(*n), member))
369
370 /**
371  * list_for_each_entry_safe_reverse - iterate backwards over list of given type safe against
372  *                                    removal of list entry
373  * @pos:        the type * to use as a loop counter.
374  * @n:          another type * to use as temporary storage
375  * @head:       the head for your list.
376  * @member:     the name of the list_struct within the struct.
377  */
378 #define list_for_each_entry_safe_reverse(pos, n, head, member)          \
379         for (pos = list_entry((head)->prev, typeof(*pos), member),      \
380                 n = list_entry(pos->member.prev, typeof(*pos), member); \
381              &pos->member != (head);                                    \
382              pos = n, n = list_entry(n->member.prev, typeof(*n), member))
383
384 /*
385  * Double linked lists with a single pointer list head.
386  * Mostly useful for hash tables where the two pointer list head is
387  * too wasteful.
388  * You lose the ability to access the tail in O(1).
389  */
390
391 struct hlist_head {
392         struct hlist_node *first;
393 };
394
395 struct hlist_node {
396         struct hlist_node *next, **pprev;
397 };
398
399 #define HLIST_HEAD_INIT { .first = NULL }
400 #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
401 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
402 static inline void INIT_HLIST_NODE(struct hlist_node *h)
403 {
404         h->next = NULL;
405         h->pprev = NULL;
406 }
407
408 static inline int hlist_unhashed(const struct hlist_node *h)
409 {
410         return !h->pprev;
411 }
412
413 static inline int hlist_empty(const struct hlist_head *h)
414 {
415         return !h->first;
416 }
417
418 static inline void __hlist_del(struct hlist_node *n)
419 {
420         struct hlist_node *next = n->next;
421         struct hlist_node **pprev = n->pprev;
422         *pprev = next;
423         if (next)
424                 next->pprev = pprev;
425 }
426
427 static inline void hlist_del(struct hlist_node *n)
428 {
429         __hlist_del(n);
430         n->next = LIST_POISON1;
431         n->pprev = LIST_POISON2;
432 }
433
434 static inline void hlist_del_init(struct hlist_node *n)
435 {
436         if (!hlist_unhashed(n)) {
437                 __hlist_del(n);
438                 INIT_HLIST_NODE(n);
439         }
440 }
441
442 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
443 {
444         struct hlist_node *first = h->first;
445         n->next = first;
446         if (first)
447                 first->pprev = &n->next;
448         h->first = n;
449         n->pprev = &h->first;
450 }
451
452 /* next must be != NULL */
453 static inline void hlist_add_before(struct hlist_node *n,
454                                         struct hlist_node *next)
455 {
456         n->pprev = next->pprev;
457         n->next = next;
458         next->pprev = &n->next;
459         *(n->pprev) = n;
460 }
461
462 static inline void hlist_add_after(struct hlist_node *n,
463                                         struct hlist_node *next)
464 {
465         next->next = n->next;
466         n->next = next;
467         next->pprev = &n->next;
468
469         if(next->next)
470                 next->next->pprev  = &next->next;
471 }
472
473 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
474
475 #define hlist_for_each(pos, head) \
476         for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
477              pos = pos->next)
478
479 #define hlist_for_each_safe(pos, n, head) \
480         for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
481              pos = n)
482
483 /**
484  * hlist_for_each_entry - iterate over list of given type
485  * @tpos:       the type * to use as a loop counter.
486  * @pos:        the &struct hlist_node to use as a loop counter.
487  * @head:       the head for your list.
488  * @member:     the name of the hlist_node within the struct.
489  */
490 #define hlist_for_each_entry(tpos, pos, head, member)                    \
491         for (pos = (head)->first;                                        \
492              pos && ({ prefetch(pos->next); 1;}) &&                      \
493                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
494              pos = pos->next)
495
496 /**
497  * hlist_for_each_entry_continue - iterate over a hlist continuing after existing point
498  * @tpos:       the type * to use as a loop counter.
499  * @pos:        the &struct hlist_node to use as a loop counter.
500  * @member:     the name of the hlist_node within the struct.
501  */
502 #define hlist_for_each_entry_continue(tpos, pos, member)                 \
503         for (pos = (pos)->next;                                          \
504              pos && ({ prefetch(pos->next); 1;}) &&                      \
505                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
506              pos = pos->next)
507
508 /**
509  * hlist_for_each_entry_from - iterate over a hlist continuing from existing point
510  * @tpos:       the type * to use as a loop counter.
511  * @pos:        the &struct hlist_node to use as a loop counter.
512  * @member:     the name of the hlist_node within the struct.
513  */
514 #define hlist_for_each_entry_from(tpos, pos, member)                     \
515         for (; pos && ({ prefetch(pos->next); 1;}) &&                    \
516                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
517              pos = pos->next)
518
519 /**
520  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
521  * @tpos:       the type * to use as a loop counter.
522  * @pos:        the &struct hlist_node to use as a loop counter.
523  * @n:          another &struct hlist_node to use as temporary storage
524  * @head:       the head for your list.
525  * @member:     the name of the hlist_node within the struct.
526  */
527 #define hlist_for_each_entry_safe(tpos, pos, n, head, member)            \
528         for (pos = (head)->first;                                        \
529              pos && ({ n = pos->next; 1; }) &&                           \
530                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
531              pos = n)
532
533
534 // JRL FIXME
535 //#endif // ! __V3VEE__
536
537 #endif