nhrpd/list.h

   1 /* Linux kernel style list handling function
   2  *
   3  * Written from scratch by Timo Teräs <timo.teras@iki.fi>, but modeled
   4  * after the linux kernel code.
   5  *
   6  * This file is free software: you may copy, redistribute and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation, either version 2 of the License, or
   9  * (at your option) any later version.
  10  */
  11
  12 #ifndef LIST_H
  13 #define LIST_H
  14
  15 #ifndef NULL
  16 #define NULL 0L
  17 #endif
  18
  19 #ifndef offsetof
  20 #ifdef __compiler_offsetof
  21 #define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
  22 #else
  23 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
  24 #endif
  25 #endif
  26
  27 #ifndef container_of
  28 #define container_of(ptr, type, member)                                        \
  29         ({                                                                     \
  30                 const typeof(((type *)0)->member) *__mptr = (ptr);             \
  31                 (type *)((char *)__mptr - offsetof(type, member));             \
  32         })
  33 #endif
  34
  35 struct hlist_head {
  36         struct hlist_node *first;
  37 };
  38
  39 struct hlist_node {
  40         struct hlist_node *next;
  41         struct hlist_node **pprev;
  42 };
  43
  44 static inline int hlist_empty(const struct hlist_head *h)
  45 {
  46         return !h->first;
  47 }
  48
  49 static inline int hlist_hashed(const struct hlist_node *n)
  50 {
  51         return n->pprev != NULL;
  52 }
  53
  54 static inline void hlist_del(struct hlist_node *n)
  55 {
  56         struct hlist_node *next = n->next;
  57         struct hlist_node **pprev = n->pprev;
  58
  59         *pprev = next;
  60         if (next)
  61                 next->pprev = pprev;
  62
  63         n->next = NULL;
  64         n->pprev = NULL;
  65 }
  66
  67 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
  68 {
  69         struct hlist_node *first = h->first;
  70
  71         n->next = first;
  72         if (first)
  73                 first->pprev = &n->next;
  74         n->pprev = &h->first;
  75         h->first = n;
  76 }
  77
  78 static inline void hlist_add_after(struct hlist_node *n,
  79                                    struct hlist_node *prev)
  80 {
  81         n->next = prev->next;
  82         n->pprev = &prev->next;
  83         prev->next = n;
  84 }
  85
  86 static inline struct hlist_node **hlist_tail_ptr(struct hlist_head *h)
  87 {
  88         struct hlist_node *n = h->first;
  89         if (n == NULL)
  90                 return &h->first;
  91         while (n->next != NULL)
  92                 n = n->next;
  93         return &n->next;
  94 }
  95
  96 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
  97
  98 #define hlist_for_each(pos, head)                                              \
  99         for (pos = (head)->first; pos; pos = pos->next)
 100
 101 #define hlist_for_each_safe(pos, n, head)                                      \
 102         for (pos = (head)->first; pos && ({                                    \
 103                                           n = pos->next;                       \
 104                                           1;                                   \
 105                                   });                                          \
 106              pos = n)
 107
 108 #define hlist_for_each_entry(tpos, pos, head, member)                          \
 109         for (pos = (head)->first;                                              \
 110              pos && ({                                                         \
 111                      tpos = hlist_entry(pos, typeof(*tpos), member);           \
 112                      1;                                                        \
 113              });                                                               \
 114              pos = pos->next)
 115
 116 #define hlist_for_each_entry_safe(tpos, pos, n, head, member)                  \
 117         for (pos = (head)->first;                                              \
 118              pos && ({                                                         \
 119                      n = pos->next;                                            \
 120                      1;                                                        \
 121              })                                                                \
 122              && ({                                                             \
 123                         tpos = hlist_entry(pos, typeof(*tpos), member);        \
 124                         1;                                                     \
 125                 });                                                            \
 126              pos = n)
 127
 128
 129 struct list_head {
 130         struct list_head *next, *prev;
 131 };
 132
 133 #define LIST_INITIALIZER(l) { .next = &l, .prev = &l }
 134
 135 static inline void list_init(struct list_head *list)
 136 {
 137         list->next = list;
 138         list->prev = list;
 139 }
 140
 141 static inline void __list_add(struct list_head *new, struct list_head *prev,
 142                               struct list_head *next)
 143 {
 144         next->prev = new;
 145         new->next = next;
 146         new->prev = prev;
 147         prev->next = new;
 148 }
 149
 150 static inline void list_add(struct list_head *new, struct list_head *head)
 151 {
 152         __list_add(new, head, head->next);
 153 }
 154
 155 static inline void list_add_tail(struct list_head *new, struct list_head *head)
 156 {
 157         __list_add(new, head->prev, head);
 158 }
 159
 160 static inline void __list_del(struct list_head *prev, struct list_head *next)
 161 {
 162         next->prev = prev;
 163         prev->next = next;
 164 }
 165
 166 static inline void list_del(struct list_head *entry)
 167 {
 168         __list_del(entry->prev, entry->next);
 169         entry->next = NULL;
 170         entry->prev = NULL;
 171 }
 172
 173 static inline int list_hashed(const struct list_head *n)
 174 {
 175         return n->next != n && n->next != NULL;
 176 }
 177
 178 static inline int list_empty(const struct list_head *n)
 179 {
 180         return !list_hashed(n);
 181 }
 182
 183 #define list_next(ptr, type, member)                                           \
 184         (list_hashed(ptr) ? container_of((ptr)->next, type, member) : NULL)
 185
 186 #define list_entry(ptr, type, member) container_of(ptr,type,member)
 187
 188 #define list_for_each(pos, head)                                               \
 189         for (pos = (head)->next; pos != (head); pos = pos->next)
 190
 191 #define list_for_each_safe(pos, n, head)                                       \
 192         for (pos = (head)->next, n = pos->next; pos != (head);                 \
 193              pos = n, n = pos->next)
 194
 195 #define list_for_each_entry(pos, head, member)                                 \
 196         for (pos = list_entry((head)->next, typeof(*pos), member);             \
 197              &pos->member != (head);                                           \
 198              pos = list_entry(pos->member.next, typeof(*pos), member))
 199
 200 #define list_for_each_entry_safe(pos, n, head, member)                         \
 201         for (pos = list_entry((head)->next, typeof(*pos), member),             \
 202             n = list_entry(pos->member.next, typeof(*pos), member);            \
 203              &pos->member != (head);                                           \
 204              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 205
 206 #endif