include/list.h

   1 #ifndef _LIST_H
   2 #define _LIST_H
   3
   4 /* Linux inspired doubly linked-list implementation. */
   5
   6 #include <stdint.h>
   7 #include <stdbool.h>
   8
   9 typedef struct list_node
  10 {
  11     struct list_node *prev, *next;
  12 } list_node_t;
  13
  14 #define get_offset(type, member)            (uintptr_t)&(((type*)0)->member)
  15 #define get_container(entry, type, member)  (type*)((uintptr_t)(entry) - get_offset(type, member))
  16
  17 #define EMPTY_LIST(name) { &name, &name }
  18
  19 /*
  20  * Initialize a list.
  21  *     list_node_t *list -> list to initialize.
  22  */
  23 static inline void list_init(list_node_t *list)
  24 {
  25     list->prev = list->next = list;
  26 }
  27
  28 /*
  29  * Check whether a node is in a list.
  30  *     const list_node_t *node.
  31  *
  32  * Returns:
  33  *     bool.
  34  */
  35 static inline bool list_in_list(const list_node_t *node)
  36 {
  37     return !((node->prev == 0) || (node->next == 0));
  38 }
  39
  40 /*
  41  * Get list head.
  42  *     const list_node_t *list -> list.
  43  *
  44  * Returns:
  45  *     list_node_t*.
  46  */
  47 static inline list_node_t* list_get_head(const list_node_t *list)
  48 {
  49     if (list->next != list) {
  50         return list->next;
  51     } else {
  52         return 0;
  53     }
  54 }
  55
  56 #define list_get_head_type(list, type, element) ({ \
  57             list_node_t *__node = list_get_head(list); \
  58             type *__instance; \
  59             if (__node) \
  60                 __instance = get_container(__node, type, element); \
  61             else \
  62                 __instance = (type *)0; \
  63             __instance; \
  64         })
  65
  66 /*
  67  * Get list tail.
  68  *     const list_node_t *list -> list.
  69  *
  70  * Returns:
  71  *     list_node_t*.
  72  */
  73 static inline list_node_t* list_get_tail(const list_node_t *list)
  74 {
  75     if (list->prev != list) {
  76         return list->prev;
  77     } else {
  78         return 0;
  79     }
  80 }
  81
  82 #define list_get_tail_type(list, type, element) ({ \
  83             list_node_t *__node = list_get_tail(list); \
  84             type *__instance; \
  85             if (__node) \
  86                 __instance = get_container(__node, type, element); \
  87             else \
  88                 __instance = (type *)0; \
  89             __instance; \
  90         })
  91
  92 /*
  93  * Internal implementation to add a new member.
  94  *     list_node_t *node -> node to add.
  95  *     list_node_t *prev -> prev node.
  96  *     list_node_t *next -> next node.
  97  */
  98 static inline void __list_add(list_node_t *node, list_node_t *prev, list_node_t *next)
  99 {
 100     prev->next = node;
 101     node->prev = prev;
 102     node->next = next;
 103     next->prev = node;
 104 }
 105
 106 // Macros over add.
 107 #define list_add_head(list, node) __list_add((node), (list), (list)->next)
 108 #define list_add_tail(list, node) __list_add((node), (list)->prev, (list))
 109 #define list_add_after(cur, node) list_add_head((cur), (node))
 110 #define list_add_before(cur, node) list_add_tail((cur), (node))
 111
 112 /*
 113  * Internal implementation to remove a member.
 114  *     list_node_t *prev -> prev node.
 115  *     list_node_t *next -> next node.
 116  */
 117 static inline void __list_rem(list_node_t *prev, list_node_t *next)
 118 {
 119     prev->next = next;
 120     next->prev = prev;
 121 }
 122
 123 /*
 124  * Delete a member.
 125  *     list_node_t *node -> node to delete.
 126  */
 127 static inline void list_delete(list_node_t *node)
 128 {
 129     __list_rem(node->prev, node->next);
 130     node->prev = node->next = 0;
 131 }
 132
 133 /*
 134  * Delete the head of a list.
 135  *     list_node_t *list -> the list.
 136  *
 137  * Returns:
 138  *     list_node_t* -> the node deleted.
 139  */
 140 static inline list_node_t* list_delete_head(list_node_t *list)
 141 {
 142     list_node_t *node;
 143     if ((node = list->next) != list) {
 144         list_delete(node);
 145         return node;
 146     } else {
 147         return 0;
 148     }
 149 }
 150
 151 /*
 152  * Delete the tail of a list.
 153  *     list_node_t *list -> the list.
 154  *
 155  * Returns:
 156  *     list_node_t* -> the node deleted.
 157  */
 158 static inline list_node_t* list_delete_tail(list_node_t *list)
 159 {
 160     list_node_t *node;
 161     if ((node = list->prev) != list) {
 162         list_delete(node);
 163         return node;
 164     } else {
 165         return 0;
 166     }
 167 }
 168
 169 /*
 170  * Check if list is empty, or not.
 171  *     const list_node_t *list -> the list.
 172  *
 173  * Returns:
 174  *     bool -> true if empty.
 175  */
 176 static inline bool list_is_emtpy(const list_node_t *list)
 177 {
 178     return (list->next == list);
 179 }
 180
 181 /*
 182  * Check if node is the last element in the list.
 183  *     const list_node_t *list -> the list.
 184  *     const list_node_t *node -> the node to check.
 185  *
 186  * Returns:
 187  *     bool -> true if last.
 188  */
 189 static inline bool list_is_last(const list_node_t *list, const list_node_t *node)
 190 {
 191     return (list->prev == node);
 192 }
 193
 194 // Iterator.
 195 #define list_foreach(list, type, member, iterator) for (\
 196                         (iterator) = get_container((list)->next, type, member); \
 197                         &(iterator)->member != (list); \
 198                         (iterator) = get_container((iterator)->member.next, type, member))
 199
 200 // Safe iterator.
 201 #define list_foreach_safe(list, type, member, iterator, temp_iter) for (\
 202                         (iterator) = get_container((list)->next, type, member), \
 203                         (temp_iter) = get_container((iterator)->member.next, type, member); \
 204                         &(iterator)->member != (list); \
 205                         (iterator) = (temp_iter), \
 206                         (temp_iter) = get_container((iterator)->member.next, type, member))
 207
 208 #endif /* _LIST_H */