aura  0.1
 All Data Structures Functions Variables Modules Pages
list.h
1 
17 #ifndef _LINUX_LIST_H
18 #define _LINUX_LIST_H
19 
20 
25 
29 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
30 
38 #define container_of(ptr, type, member) ({ \
39  const typeof( ((type *)0)->member ) *__mptr = (ptr); \
40  (type *)( (char *)__mptr - offsetof(type,member) );})
41 
44 /*
45  * These are non-NULL pointers that will result in page faults
46  * under normal circumstances, used to verify that nobody uses
47  * non-initialized list entries.
48  */
49 #define LIST_POISON1 ((void *) 0x00100100)
50 #define LIST_POISON2 ((void *) 0x00200200)
51 
61 struct list_head {
62  struct list_head *next, *prev;
63 };
64 
65 #define LIST_HEAD_INIT(name) { &(name), &(name) }
66 
67 #define LIST_HEAD(name) \
68  struct list_head name = LIST_HEAD_INIT(name)
69 
70 #define INIT_LIST_HEAD(ptr) do { \
71  (ptr)->next = (ptr); (ptr)->prev = (ptr); \
72 } while (0)
73 
74 /*
75  * Insert a new entry between two known consecutive entries.
76  *
77  * This is only for internal list manipulation where we know
78  * the prev/next entries already!
79  */
80 static inline void __list_add(struct list_head *neu,
81  struct list_head *prev,
82  struct list_head *next)
83 {
84  next->prev = neu;
85  neu->next = next;
86  neu->prev = prev;
87  prev->next = neu;
88 }
89 
98 static inline void list_add(struct list_head *neu, struct list_head *head)
99 {
100  __list_add(neu, head, head->next);
101 }
102 
111 static inline void list_add_tail(struct list_head *neu, struct list_head *head)
112 {
113  __list_add(neu, head->prev, head);
114 }
115 
116 
117 /*
118  * Delete a list entry by making the prev/next entries
119  * point to each other.
120  *
121  * This is only for internal list manipulation where we know
122  * the prev/next entries already!
123  */
124 static inline void __list_del(struct list_head * prev, struct list_head * next)
125 {
126  next->prev = prev;
127  prev->next = next;
128 }
129 
136 static inline void list_del(struct list_head *entry)
137 {
138  __list_del(entry->prev, entry->next);
139  entry->next = (struct list_head *)LIST_POISON1;
140  entry->prev = (struct list_head *)LIST_POISON2;
141 }
142 
143 
144 
149 static inline void list_del_init(struct list_head *entry)
150 {
151  __list_del(entry->prev, entry->next);
152  INIT_LIST_HEAD(entry);
153 }
154 
160 static inline void list_move(struct list_head *list, struct list_head *head)
161 {
162  __list_del(list->prev, list->next);
163  list_add(list, head);
164 }
165 
171 static inline void list_move_tail(struct list_head *list,
172  struct list_head *head)
173 {
174  __list_del(list->prev, list->next);
175  list_add_tail(list, head);
176 }
177 
182 static inline int list_empty(const struct list_head *head)
183 {
184  return head->next == head;
185 }
186 
187 static inline void __list_splice(struct list_head *list,
188  struct list_head *head)
189 {
190  struct list_head *first = list->next;
191  struct list_head *last = list->prev;
192  struct list_head *at = head->next;
193 
194  first->prev = head;
195  head->next = first;
196 
197  last->next = at;
198  at->prev = last;
199 }
200 
206 static inline void list_splice(struct list_head *list, struct list_head *head)
207 {
208  if (!list_empty(list))
209  __list_splice(list, head);
210 }
211 
219 static inline void list_splice_init(struct list_head *list,
220  struct list_head *head)
221 {
222  if (!list_empty(list)) {
223  __list_splice(list, head);
224  INIT_LIST_HEAD(list);
225  }
226 }
227 
234 #define list_entry(ptr, type, member) \
235  container_of(ptr, type, member)
236 
243 #define list_for_each(pos, head) \
244  for (pos = (head)->next; pos != (head); \
245  pos = pos->next)
246 
257 #define __list_for_each(pos, head) \
258  for (pos = (head)->next; pos != (head); pos = pos->next)
259 
265 #define list_for_each_prev(pos, head) \
266  for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
267  pos = pos->prev)
268 
275 #define list_for_each_safe(pos, n, head) \
276  for (pos = (head)->next, n = pos->next; pos != (head); \
277  pos = n, n = pos->next)
278 
285 #define list_for_each_entry(pos, head, member) \
286  for (pos = list_entry((head)->next, typeof(*pos), member); \
287  &pos->member != (head); \
288  pos = list_entry(pos->member.next, typeof(*pos), member))
289 
296 #define list_for_each_entry_reverse(pos, head, member) \
297  for (pos = list_entry((head)->prev, typeof(*pos), member); \
298  &pos->member != (head); \
299  pos = list_entry(pos->member.prev, typeof(*pos), member))
300 
308 #define list_prepare_entry(pos, head, member) \
309  ((pos) ? : list_entry(head, typeof(*pos), member))
310 
318 #define list_for_each_entry_continue(pos, head, member) \
319  for (pos = list_entry(pos->member.next, typeof(*pos), member); \
320  &pos->member != (head); \
321  pos = list_entry(pos->member.next, typeof(*pos), member))
322 
330 #define list_for_each_entry_safe(pos, n, head, member) \
331  for (pos = list_entry((head)->next, typeof(*pos), member), \
332  n = list_entry(pos->member.next, typeof(*pos), member); \
333  &pos->member != (head); \
334  pos = n, n = list_entry(n->member.next, typeof(*n), member))
335 
344 #define list_for_each_entry_safe_continue(pos, n, head, member) \
345  for (pos = list_entry(pos->member.next, typeof(*pos), member), \
346  n = list_entry(pos->member.next, typeof(*pos), member); \
347  &pos->member != (head); \
348  pos = n, n = list_entry(n->member.next, typeof(*n), member))
349 
358 #define list_for_each_entry_safe_reverse(pos, n, head, member) \
359  for (pos = list_entry((head)->prev, typeof(*pos), member), \
360  n = list_entry(pos->member.prev, typeof(*pos), member); \
361  &pos->member != (head); \
362  pos = n, n = list_entry(n->member.prev, typeof(*n), member))
363 
364 
365 
366 
367 /*
368  * Double linked lists with a single pointer list head.
369  * Mostly useful for hash tables where the two pointer list head is
370  * too wasteful.
371  * You lose the ability to access the tail in O(1).
372  */
373 
374 struct hlist_head {
375  struct hlist_node *first;
376 };
377 
378 struct hlist_node {
379  struct hlist_node *next, **pprev;
380 };
381 
382 #define HLIST_HEAD_INIT { .first = NULL }
383 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
384 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
385 #define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)
386 
387 static inline int hlist_unhashed(const struct hlist_node *h)
388 {
389  return !h->pprev;
390 }
391 
392 static inline int hlist_empty(const struct hlist_head *h)
393 {
394  return !h->first;
395 }
396 
397 static inline void __hlist_del(struct hlist_node *n)
398 {
399  struct hlist_node *next = n->next;
400  struct hlist_node **pprev = n->pprev;
401  *pprev = next;
402  if (next)
403  next->pprev = pprev;
404 }
405 
406 static inline void hlist_del(struct hlist_node *n)
407 {
408  __hlist_del(n);
409  n->next = (struct hlist_node *) LIST_POISON1;
410  n->pprev = (struct hlist_node **)LIST_POISON2;
411 }
412 
413 
414 static inline void hlist_del_init(struct hlist_node *n)
415 {
416  if (n->pprev) {
417  __hlist_del(n);
418  INIT_HLIST_NODE(n);
419  }
420 }
421 
422 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
423 {
424  struct hlist_node *first = h->first;
425  n->next = first;
426  if (first)
427  first->pprev = &n->next;
428  h->first = n;
429  n->pprev = &h->first;
430 }
431 
432 
433 
434 /* next must be != NULL */
435 static inline void hlist_add_before(struct hlist_node *n,
436  struct hlist_node *next)
437 {
438  n->pprev = next->pprev;
439  n->next = next;
440  next->pprev = &n->next;
441  *(n->pprev) = n;
442 }
443 
444 static inline void hlist_add_after(struct hlist_node *n,
445  struct hlist_node *next)
446 {
447  next->next = n->next;
448  n->next = next;
449  next->pprev = &n->next;
450 
451  if(next->next)
452  next->next->pprev = &next->next;
453 }
454 
455 
456 
457 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
458 
459 #define hlist_for_each(pos, head) \
460  for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
461  pos = pos->next)
462 
463 #define hlist_for_each_safe(pos, n, head) \
464  for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
465  pos = n)
466 
474 #define hlist_for_each_entry(tpos, pos, head, member) \
475  for (pos = (head)->first; \
476  pos && ({ prefetch(pos->next); 1;}) && \
477  ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
478  pos = pos->next)
479 
486 #define hlist_for_each_entry_continue(tpos, pos, member) \
487  for (pos = (pos)->next; \
488  pos && ({ prefetch(pos->next); 1;}) && \
489  ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
490  pos = pos->next)
491 
498 #define hlist_for_each_entry_from(tpos, pos, member) \
499  for (; pos && ({ prefetch(pos->next); 1;}) && \
500  ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
501  pos = pos->next)
502 
511 #define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
512  for (pos = (head)->first; \
513  pos && ({ n = pos->next; 1; }) && \
514  ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
515  pos = n)
516 
517 
518 #endif
Definition: list.h:61