nsz Git - libfirm/blob - include/libfirm/adt/list.h

   1 /**
   2  * @file
   3  * @brief   Doubly linked lists.
   4  *
   5  * Simple doubly linked list implementation.
   6  *
   7  * Some of the internal functions ("__xxx") are useful when
   8  * manipulating whole lists rather than single entries, as
   9  * sometimes we already know the next/prev entries and we can
  10  * generate better code by using them directly rather than
  11  * using the generic single-entry routines.
  12   */
  13 #ifndef FIRM_ADT_LIST_H
  14 #define FIRM_ADT_LIST_H
  15
  16 #include <stdlib.h>
  17
  18 #include "../begin.h"
  19
  20 typedef struct list_head list_head;
  21 struct list_head {
  22         struct list_head *next, *prev;
  23 };
  24
  25 #define LIST_HEAD_INIT(name) { &(name), &(name) }
  26
  27 #define LIST_HEAD(name) \
  28         struct list_head name = LIST_HEAD_INIT(name)
  29
  30 #define INIT_LIST_HEAD(ptr) do { \
  31         (ptr)->next = (ptr); (ptr)->prev = (ptr); \
  32 } while (0)
  33
  34 #define _list_offsetof(type,member) \
  35   ((char *) &(((type *) 0)->member) - (char *) 0)
  36
  37 #define _list_container_of(ptr, type, member) \
  38         ((type *) ((char *) (ptr) - _list_offsetof(type, member)))
  39
  40 /*
  41  * Insert a new entry between two known consecutive entries.
  42  *
  43  * This is only for internal list manipulation where we know
  44  * the prev/next entries already!
  45  */
  46 static inline void __list_add(struct list_head *new_node,
  47                               struct list_head *prev,
  48                               struct list_head *next)
  49 {
  50         next->prev = new_node;
  51         new_node->next = next;
  52         new_node->prev = prev;
  53         prev->next = new_node;
  54 }
  55
  56 /**
  57  * list_add - add a new entry
  58  * @param new_node   new entry to be added
  59  * @param head       list head to add it after
  60  *
  61  * Insert a new entry after the specified head.
  62  * This is good for implementing stacks.
  63  */
  64 static inline void list_add(struct list_head *new_node, struct list_head *head)
  65 {
  66         __list_add(new_node, head, head->next);
  67 }
  68
  69 /**
  70  * list_add_tail - add a new entry
  71  * @param new_node   new entry to be added
  72  * @param head       list head to add it before
  73  *
  74  * Insert a new entry before the specified head.
  75  * This is useful for implementing queues.
  76  */
  77 static inline void list_add_tail(struct list_head *new_node, struct list_head *head)
  78 {
  79         __list_add(new_node, head->prev, head);
  80 }
  81
  82 /*
  83  * Delete a list entry by making the prev/next entries
  84  * point to each other.
  85  *
  86  * This is only for internal list manipulation where we know
  87  * the prev/next entries already!
  88  */
  89 static inline void __list_del(struct list_head * prev, struct list_head * next)
  90 {
  91         next->prev = prev;
  92         prev->next = next;
  93 }
  94
  95 /**
  96  * list_del - deletes entry from list.
  97  * @param entry  the element to delete from the list.
  98  *
  99  * @note
 100  *   list_empty on entry does not return true after this, the entry is
 101  *   in an undefined state.
 102  */
 103 static inline void list_del(struct list_head *entry)
 104 {
 105         __list_del(entry->prev, entry->next);
 106         entry->next = NULL;
 107         entry->prev = NULL;
 108 }
 109
 110
 111 /**
 112  * list_del_init - deletes entry from list and reinitialize it.
 113  * @param entry   the element to delete from the list.
 114  */
 115 static inline void list_del_init(struct list_head *entry)
 116 {
 117         __list_del(entry->prev, entry->next);
 118         INIT_LIST_HEAD(entry);
 119 }
 120
 121 /**
 122  * list_move - delete from one list and add as another's head
 123  * @param list   the entry to move
 124  * @param head   the head that will precede our entry
 125  */
 126 static inline void list_move(struct list_head *list, struct list_head *head)
 127 {
 128         __list_del(list->prev, list->next);
 129         list_add(list, head);
 130 }
 131
 132 /**
 133  * list_move_tail - delete from one list and add as another's tail
 134  * @param list   the entry to move
 135  * @param head   the head that will follow our entry
 136  */
 137 static inline void list_move_tail(struct list_head *list,
 138                                   struct list_head *head)
 139 {
 140         __list_del(list->prev, list->next);
 141         list_add_tail(list, head);
 142 }
 143
 144 /**
 145  * list_empty - tests whether a list is empty
 146  * @param head   the list to test.
 147  */
 148 static inline int list_empty(const struct list_head *head)
 149 {
 150         return head->next == head;
 151 }
 152
 153 static inline void __list_splice(struct list_head *list,
 154                                  struct list_head *head)
 155 {
 156         struct list_head *first = list->next;
 157         struct list_head *last = list->prev;
 158         struct list_head *at = head->next;
 159
 160         first->prev = head;
 161         head->next = first;
 162
 163         last->next = at;
 164         at->prev = last;
 165 }
 166
 167 /**
 168  * list_splice - join two lists
 169  * @param list   the new list to add.
 170  * @param head   the place to add it in the first list.
 171  */
 172 static inline void list_splice(struct list_head *list, struct list_head *head)
 173 {
 174         if (!list_empty(list))
 175                 __list_splice(list, head);
 176 }
 177
 178 /**
 179  * list_splice_init - join two lists and reinitialize the emptied list.
 180  * @param list   the new list to add.
 181  * @param head   the place to add it in the first list.
 182  *
 183  * The list at list is reinitialized
 184  */
 185 static inline void list_splice_init(struct list_head *list,
 186                                     struct list_head *head)
 187 {
 188         if (!list_empty(list)) {
 189                 __list_splice(list, head);
 190                 INIT_LIST_HEAD(list);
 191         }
 192 }
 193
 194 /**
 195  * list_entry - get the struct for this entry
 196  * @param ptr     the &struct list_head pointer.
 197  * @param type    the type of the struct this is embedded in.
 198  * @param member  the name of the list_struct within the struct.
 199  */
 200 #define list_entry(ptr, type, member) \
 201         _list_container_of(ptr, type, member)
 202
 203 /**
 204  * list_for_each - iterate over a list
 205  * @param pos   the &struct list_head to use as a loop counter.
 206  * @param head  the head for your list.
 207  */
 208 #define list_for_each(pos, head) \
 209         for (pos = (head)->next; pos != (head); pos = pos->next)
 210
 211 /**
 212  * __list_for_each - iterate over a list
 213  * @param pos   the &struct list_head to use as a loop counter.
 214  * @param head  the head for your list.
 215  *
 216  * This variant differs from list_for_each() in that it's the
 217  * simplest possible list iteration code, no ing is done.
 218  * Use this for code that knows the list to be very short (empty
 219  * or 1 entry) most of the time.
 220  */
 221 #define __list_for_each(pos, head) \
 222         for (pos = (head)->next; pos != (head); pos = pos->next)
 223
 224 /**
 225  * list_for_each_prev - iterate over a list backwards
 226  * @param pos   the &struct list_head to use as a loop counter.
 227  * @param head  the head for your list.
 228  */
 229 #define list_for_each_prev(pos, head) \
 230         for (pos = (head)->prev; pos != (head); pos = pos->prev)
 231
 232 /**
 233  * list_for_each_safe - iterate over a list safe against removal of list entry
 234  * @param pos   the &struct list_head to use as a loop counter.
 235  * @param n     another &struct list_head to use as temporary storage
 236  * @param head  the head for your list.
 237  */
 238 #define list_for_each_safe(pos, n, head) \
 239         for (pos = (head)->next, n = pos->next; pos != (head); \
 240                 pos = n, n = pos->next)
 241
 242 /**
 243  * list_for_each_entry - iterate over list of given type
 244  * @param type    the type of the struct where the listhead is embedded in
 245  * @param pos     the type * to use as a loop counter.
 246  * @param head    the head for your list.
 247  * @param member  the name of the list_struct within the struct.
 248  */
 249 #define list_for_each_entry(type, pos, head, member)    \
 250         for (pos = list_entry((head)->next, type, member);  \
 251              &pos->member != (head);                        \
 252              pos = list_entry(pos->member.next, type, member))
 253
 254 /**
 255  * list_for_each_entry_reverse - iterate backwards over list of given type.
 256  * @param type    the type of the struct where the listhead is embedded in
 257  * @param pos     the type * to use as a loop counter.
 258  * @param head    the head for your list.
 259  * @param member  the name of the list_struct within the struct.
 260  */
 261 #define list_for_each_entry_reverse(type, pos, head, member) \
 262         for (pos = list_entry((head)->prev, type, member);       \
 263              &pos->member != (head);                             \
 264              pos = list_entry(pos->member.prev, type, member))
 265
 266
 267 /**
 268  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 269  * @param type    the type of the struct where the listhead is embedded in
 270  * @param pos     the type * to use as a loop counter.
 271  * @param n       another type * to use as temporary storage
 272  * @param head    the head for your list.
 273  * @param member  the name of the list_struct within the struct.
 274  */
 275 #define list_for_each_entry_safe(type, pos, n, head, member) \
 276         for (pos = list_entry((head)->next, type, member),       \
 277                 n = list_entry(pos->member.next, type, member);      \
 278              &pos->member != (head);                             \
 279              pos = n, n = list_entry(n->member.next, type, member))
 280
 281 #include "../end.h"
 282
 283 #endif