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  * Internal implementation to add a new member.
  42  *     list_node_t *node -> node to add.
  43  *     list_node_t *prev -> prev node.
  44  *     list_node_t *next -> next node.
  45  */
  46 static inline void __list_add(list_node_t *node, list_node_t *prev, list_node_t *next)
  47 {
  48     prev->next = node;
  49     node->prev = prev;
  50     node->next = next;
  51     next->prev = node;
  52 }
  53
  54 // Macros over add.
  55 #define list_add_head(list, node) __list_add((node), (list), (list)->next)
  56 #define list_add_tail(list, node) __list_add((node), (list)->prev, (list))
  57 #define list_add_after(cur, node) list_add_head((cur), (node))
  58 #define list_add_before(cur, node) list_add_tail((cur), (node))
  59
  60 /*
  61  * Internal implementation to remove a member.
  62  *     list_node_t *prev -> prev node.
  63  *     list_node_t *next -> next node.
  64  */
  65 static inline void __list_rem(list_node_t *prev, list_node_t *next)
  66 {
  67     prev->next = next;
  68     next->prev = prev;
  69 }
  70
  71 /*
  72  * Delete a member.
  73  *     list_node_t *node -> node to delete.
  74  */
  75 static inline void list_delete(list_node_t *node)
  76 {
  77     __list_rem(node->prev, node->next);
  78     node->prev = node->next = 0;
  79 }
  80
  81 /*
  82  * Delete the head of a list.
  83  *     list_node_t *list -> the list.
  84  *
  85  * Returns:
  86  *     list_node_t* -> the node deleted.
  87  */
  88 static inline list_node_t* list_delete_head(list_node_t *list)
  89 {
  90     list_node_t *node;
  91     if ((node = list->next) != list) {
  92         list_delete(node);
  93         return node;
  94     } else {
  95         return 0;
  96     }
  97 }
  98
  99 /*
 100  * Delete the tail of a list.
 101  *     list_node_t *list -> the list.
 102  *
 103  * Returns:
 104  *     list_node_t* -> the node deleted.
 105  */
 106 static inline list_node_t* list_delete_tail(list_node_t *list)
 107 {
 108     list_node_t *node;
 109     if ((node = list->prev) != list) {
 110         list_delete(node);
 111         return node;
 112     } else {
 113         return 0;
 114     }
 115 }
 116
 117 /*
 118  * Check if list is empty, or not.
 119  *     const list_node_t *list -> the list.
 120  *
 121  * Returns:
 122  *     bool -> true if empty.
 123  */
 124 static inline bool list_is_emtpy(const list_node_t *list)
 125 {
 126     return (list->next == list);
 127 }
 128
 129 /*
 130  * Check if node is the last element in the list.
 131  *     const list_node_t *list -> the list.
 132  *     const list_node_t *node -> the node to check.
 133  *
 134  * Returns:
 135  *     bool -> true if last.
 136  */
 137 static inline bool list_is_last(const list_node_t *list, const list_node_t *node)
 138 {
 139     return (list->prev == node);
 140 }
 141
 142 // Iterator.
 143 #define list_foreach(list, type, member, iterator) for (\
 144                         (iterator) = get_container((list)->next, type, member); \
 145                         &(iterator)->member != (list); \
 146                         (iterator) = get_container((iterator)->member.next, type, member))
 147
 148 // Safe iterator.
 149 #define list_foreach_safe(list, type, member, iterator, temp_iter) for (\
 150                         (iterator) = get_container((list)->next, type, member), \
 151                         (temp_iter) = get_container((iterator)->member.next, type, member); \
 152                         &(iterator)->member != (list); \
 153                         (iterator) = (temp_iter), \
 154                         (temp_iter) = get_container((iterator)->member.next, type, member))
 155
 156 #endif /* _LIST_H */