btt/list.h

   1 #ifndef _LINUX_LIST_H
   2 #define _LINUX_LIST_H
   3
   4 #include <stdio.h>
   5
   6 #ifndef offsetof
   7 /**
   8  * Get offset of a member
   9  */
  10 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
  11 #endif
  12
  13 #ifndef container_of
  14 /**
  15  * Casts a member of a structure out to the containing structure
  16  * @param ptr        the pointer to the member.
  17  * @param type       the type of the container struct this is embedded in.
  18  * @param member     the name of the member within the struct.
  19  *
  20  */
  21 #define container_of(ptr, type, member) ({                      \
  22         const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
  23                 (type *)( (char *)__mptr - offsetof(type,member) );})
  24 #endif
  25
  26 /*
  27  * These are non-NULL pointers that will result in page faults
  28  * under normal circumstances, used to verify that nobody uses
  29  * non-initialized list entries.
  30  */
  31 #define LIST_POISON1  ((void *) 0x00100100)
  32 #define LIST_POISON2  ((void *) 0x00200200)
  33
  34 struct list_head {
  35         struct list_head *next, *prev;
  36 };
  37
  38 #define LIST_HEAD_INIT(name) { &(name), &(name) }
  39
  40 #define LIST_HEAD(name) \
  41         struct list_head name = LIST_HEAD_INIT(name)
  42
  43 static inline void INIT_LIST_HEAD(struct list_head *list)
  44 {
  45         list->next = list;
  46         list->prev = list;
  47 }
  48
  49 /*
  50  * Insert a new entry between two known consecutive entries.
  51  *
  52  * This is only for internal list manipulation where we know
  53  * the prev/next entries already!
  54  */
  55 static inline void __list_add(struct list_head *new,
  56                               struct list_head *prev,
  57                               struct list_head *next)
  58 {
  59         next->prev = new;
  60         new->next = next;
  61         new->prev = prev;
  62         prev->next = new;
  63 }
  64
  65 /**
  66  * list_add - add a new entry
  67  * @new: new entry to be added
  68  * @head: list head to add it after
  69  *
  70  * Insert a new entry after the specified head.
  71  * This is good for implementing stacks.
  72  */
  73 static inline void list_add(struct list_head *new, struct list_head *head)
  74 {
  75         __list_add(new, head, head->next);
  76 }
  77
  78 /**
  79  * list_add_tail - add a new entry
  80  * @new: new entry to be added
  81  * @head: list head to add it before
  82  *
  83  * Insert a new entry before the specified head.
  84  * This is useful for implementing queues.
  85  */
  86 static inline void list_add_tail(struct list_head *new, struct list_head *head)
  87 {
  88         __list_add(new, head->prev, head);
  89 }
  90
  91 /*
  92  * Delete a list entry by making the prev/next entries
  93  * point to each other.
  94  *
  95  * This is only for internal list manipulation where we know
  96  * the prev/next entries already!
  97  */
  98 static inline void __list_del(struct list_head * prev, struct list_head * next)
  99 {
 100         next->prev = prev;
 101         prev->next = next;
 102 }
 103
 104 /**
 105  * list_del - deletes entry from list.
 106  * @entry: the element to delete from the list.
 107  * Note: list_empty on entry does not return true after this, the entry is
 108  * in an undefined state.
 109  */
 110 static inline void list_del(struct list_head *entry)
 111 {
 112         __list_del(entry->prev, entry->next);
 113         entry->next = LIST_POISON1;
 114         entry->prev = LIST_POISON2;
 115 }
 116
 117 /**
 118  * __list_for_each      -       iterate over a list
 119  * @pos:        the &struct list_head to use as a loop counter.
 120  * @head:       the head for your list.
 121  *
 122  * This variant differs from list_for_each() in that it's the
 123  * simplest possible list iteration code, no prefetching is done.
 124  * Use this for code that knows the list to be very short (empty
 125  * or 1 entry) most of the time.
 126  */
 127 #define __list_for_each(pos, head) \
 128         for (pos = (head)->next; pos != (head); pos = pos->next)
 129
 130 /**
 131  * list_for_each_safe   -       iterate over a list safe against removal of list entry
 132  * @pos:        the &struct list_head to use as a loop counter.
 133  * @n:          another &struct list_head to use as temporary storage
 134  * @head:       the head for your list.
 135  */
 136 #define list_for_each_safe(pos, n, head) \
 137         for (pos = (head)->next, n = pos->next; pos != (head); \
 138                 pos = n, n = pos->next)
 139
 140 /**
 141  * list_entry - get the struct for this entry
 142  * @ptr:        the &struct list_head pointer.
 143  * @type:       the type of the struct this is embedded in.
 144  * @member:     the name of the list_struct within the struct.
 145  */
 146 #define list_entry(ptr, type, member) \
 147         container_of(ptr, type, member)
 148
 149 static inline int list_len(struct list_head *head_p)
 150 {
 151         struct list_head *p;
 152         int n = 0;
 153
 154         __list_for_each(p, head_p) {
 155                 n++;
 156         }
 157
 158         return n;
 159 }
 160
 161 /**
 162  * list_empty - tests whether a list is empty
 163  * @head: the list to test.
 164  */
 165 static inline int list_empty(const struct list_head *head)
 166 {
 167         return head->next == head;
 168 }
 169
 170 /**
 171  * list_first - Returns first entry on list, or NULL if empty
 172  * @head: the list
 173  */
 174 static inline struct list_head *list_first(const struct list_head *head)
 175 {
 176         return list_empty(head) ? NULL : head->next;
 177 }
 178
 179 /**
 180  * list_move_tail - delete from one list and add as another's tail
 181  * @list: the entry to move
 182  * @head: the head that will follow our entry
 183  */
 184 static inline void list_move_tail(struct list_head *list,
 185                                   struct list_head *head)
 186 {
 187         __list_del(list->prev, list->next);
 188         list_add_tail(list, head);
 189 }
 190
 191 static inline void __list_splice(struct list_head *list,
 192                                  struct list_head *head)
 193 {
 194         struct list_head *first = list->next;
 195         struct list_head *last = list->prev;
 196         struct list_head *at = head->next;
 197
 198         first->prev = head;
 199         head->next = first;
 200
 201         last->next = at;
 202         at->prev = last;
 203 }
 204
 205 /**
 206  *  * list_splice - join two lists
 207  *   * @list: the new list to add.
 208  *    * @head: the place to add it in the first list.
 209  *     */
 210 static inline void list_splice(struct list_head *list, struct list_head *head)
 211 {
 212         if (!list_empty(list))
 213                 __list_splice(list, head);
 214 }
 215
 216 #endif