include/osmocom/core/linuxlist.h

   1 #ifndef _LINUX_LLIST_H
   2 #define _LINUX_LLIST_H
   3
   4 #include <stddef.h>
   5
   6 #ifndef inline
   7 #define inline __inline__
   8 #endif
   9
  10 static inline void prefetch(const void *x) {;}
  11
  12 /**
  13  * container_of - cast a member of a structure out to the containing structure
  14  *
  15  * @ptr:        the pointer to the member.
  16  * @type:       the type of the container struct this is embedded in.
  17  * @member:     the name of the member within the struct.
  18  *
  19  */
  20 #define container_of(ptr, type, member) ({                      \
  21         const typeof( ((type *)0)->member ) *__mptr = (typeof( ((type *)0)->member ) *)(ptr);   \
  22         (type *)( (char *)__mptr - offsetof(type, member) );})
  23
  24
  25 /*
  26  * These are non-NULL pointers that will result in page faults
  27  * under normal circumstances, used to verify that nobody uses
  28  * non-initialized llist entries.
  29  */
  30 #define LLIST_POISON1  ((void *) 0x00100100)
  31 #define LLIST_POISON2  ((void *) 0x00200200)
  32
  33 /*
  34  * Simple doubly linked llist implementation.
  35  *
  36  * Some of the internal functions ("__xxx") are useful when
  37  * manipulating whole llists rather than single entries, as
  38  * sometimes we already know the next/prev entries and we can
  39  * generate better code by using them directly rather than
  40  * using the generic single-entry routines.
  41  */
  42
  43 struct llist_head {
  44         struct llist_head *next, *prev;
  45 };
  46
  47 #define LLIST_HEAD_INIT(name) { &(name), &(name) }
  48
  49 #define LLIST_HEAD(name) \
  50         struct llist_head name = LLIST_HEAD_INIT(name)
  51
  52 #define INIT_LLIST_HEAD(ptr) do { \
  53         (ptr)->next = (ptr); (ptr)->prev = (ptr); \
  54 } while (0)
  55
  56 /*
  57  * Insert a new entry between two known consecutive entries.
  58  *
  59  * This is only for internal llist manipulation where we know
  60  * the prev/next entries already!
  61  */
  62 static inline void __llist_add(struct llist_head *_new,
  63                               struct llist_head *prev,
  64                               struct llist_head *next)
  65 {
  66         next->prev = _new;
  67         _new->next = next;
  68         _new->prev = prev;
  69         prev->next = _new;
  70 }
  71
  72 /**
  73  * llist_add - add a new entry
  74  * @new: new entry to be added
  75  * @head: llist head to add it after
  76  *
  77  * Insert a new entry after the specified head.
  78  * This is good for implementing stacks.
  79  */
  80 static inline void llist_add(struct llist_head *_new, struct llist_head *head)
  81 {
  82         __llist_add(_new, head, head->next);
  83 }
  84
  85 /**
  86  * llist_add_tail - add a new entry
  87  * @new: new entry to be added
  88  * @head: llist head to add it before
  89  *
  90  * Insert a new entry before the specified head.
  91  * This is useful for implementing queues.
  92  */
  93 static inline void llist_add_tail(struct llist_head *_new, struct llist_head *head)
  94 {
  95         __llist_add(_new, head->prev, head);
  96 }
  97
  98 /*
  99  * Delete a llist entry by making the prev/next entries
 100  * point to each other.
 101  *
 102  * This is only for internal llist manipulation where we know
 103  * the prev/next entries already!
 104  */
 105 static inline void __llist_del(struct llist_head * prev, struct llist_head * next)
 106 {
 107         next->prev = prev;
 108         prev->next = next;
 109 }
 110
 111 /**
 112  * llist_del - deletes entry from llist.
 113  * @entry: the element to delete from the llist.
 114  * Note: llist_empty on entry does not return true after this, the entry is
 115  * in an undefined state.
 116  */
 117 static inline void llist_del(struct llist_head *entry)
 118 {
 119         __llist_del(entry->prev, entry->next);
 120         entry->next = (struct llist_head *)LLIST_POISON1;
 121         entry->prev = (struct llist_head *)LLIST_POISON2;
 122 }
 123
 124 /**
 125  * llist_del_init - deletes entry from llist and reinitialize it.
 126  * @entry: the element to delete from the llist.
 127  */
 128 static inline void llist_del_init(struct llist_head *entry)
 129 {
 130         __llist_del(entry->prev, entry->next);
 131         INIT_LLIST_HEAD(entry);
 132 }
 133
 134 /**
 135  * llist_move - delete from one llist and add as another's head
 136  * @llist: the entry to move
 137  * @head: the head that will precede our entry
 138  */
 139 static inline void llist_move(struct llist_head *llist, struct llist_head *head)
 140 {
 141         __llist_del(llist->prev, llist->next);
 142         llist_add(llist, head);
 143 }
 144
 145 /**
 146  * llist_move_tail - delete from one llist and add as another's tail
 147  * @llist: the entry to move
 148  * @head: the head that will follow our entry
 149  */
 150 static inline void llist_move_tail(struct llist_head *llist,
 151                                   struct llist_head *head)
 152 {
 153         __llist_del(llist->prev, llist->next);
 154         llist_add_tail(llist, head);
 155 }
 156
 157 /**
 158  * llist_empty - tests whether a llist is empty
 159  * @head: the llist to test.
 160  */
 161 static inline int llist_empty(const struct llist_head *head)
 162 {
 163         return head->next == head;
 164 }
 165
 166 static inline void __llist_splice(struct llist_head *llist,
 167                                  struct llist_head *head)
 168 {
 169         struct llist_head *first = llist->next;
 170         struct llist_head *last = llist->prev;
 171         struct llist_head *at = head->next;
 172
 173         first->prev = head;
 174         head->next = first;
 175
 176         last->next = at;
 177         at->prev = last;
 178 }
 179
 180 /**
 181  * llist_splice - join two llists
 182  * @llist: the new llist to add.
 183  * @head: the place to add it in the first llist.
 184  */
 185 static inline void llist_splice(struct llist_head *llist, struct llist_head *head)
 186 {
 187         if (!llist_empty(llist))
 188                 __llist_splice(llist, head);
 189 }
 190
 191 /**
 192  * llist_splice_init - join two llists and reinitialise the emptied llist.
 193  * @llist: the new llist to add.
 194  * @head: the place to add it in the first llist.
 195  *
 196  * The llist at @llist is reinitialised
 197  */
 198 static inline void llist_splice_init(struct llist_head *llist,
 199                                     struct llist_head *head)
 200 {
 201         if (!llist_empty(llist)) {
 202                 __llist_splice(llist, head);
 203                 INIT_LLIST_HEAD(llist);
 204         }
 205 }
 206
 207 /**
 208  * llist_entry - get the struct for this entry
 209  * @ptr:        the &struct llist_head pointer.
 210  * @type:       the type of the struct this is embedded in.
 211  * @member:     the name of the llist_struct within the struct.
 212  */
 213 #define llist_entry(ptr, type, member) \
 214         container_of(ptr, type, member)
 215
 216 /**
 217  * llist_for_each       -       iterate over a llist
 218  * @pos:        the &struct llist_head to use as a loop counter.
 219  * @head:       the head for your llist.
 220  */
 221 #define llist_for_each(pos, head) \
 222         for (pos = (head)->next, prefetch(pos->next); pos != (head); \
 223                 pos = pos->next, prefetch(pos->next))
 224
 225 /**
 226  * __llist_for_each     -       iterate over a llist
 227  * @pos:        the &struct llist_head to use as a loop counter.
 228  * @head:       the head for your llist.
 229  *
 230  * This variant differs from llist_for_each() in that it's the
 231  * simplest possible llist iteration code, no prefetching is done.
 232  * Use this for code that knows the llist to be very short (empty
 233  * or 1 entry) most of the time.
 234  */
 235 #define __llist_for_each(pos, head) \
 236         for (pos = (head)->next; pos != (head); pos = pos->next)
 237
 238 /**
 239  * llist_for_each_prev  -       iterate over a llist backwards
 240  * @pos:        the &struct llist_head to use as a loop counter.
 241  * @head:       the head for your llist.
 242  */
 243 #define llist_for_each_prev(pos, head) \
 244         for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \
 245                 pos = pos->prev, prefetch(pos->prev))
 246
 247 /**
 248  * llist_for_each_safe  -       iterate over a llist safe against removal of llist entry
 249  * @pos:        the &struct llist_head to use as a loop counter.
 250  * @n:          another &struct llist_head to use as temporary storage
 251  * @head:       the head for your llist.
 252  */
 253 #define llist_for_each_safe(pos, n, head) \
 254         for (pos = (head)->next, n = pos->next; pos != (head); \
 255                 pos = n, n = pos->next)
 256
 257 /**
 258  * llist_for_each_entry -       iterate over llist of given type
 259  * @pos:        the type * to use as a loop counter.
 260  * @head:       the head for your llist.
 261  * @member:     the name of the llist_struct within the struct.
 262  */
 263 #define llist_for_each_entry(pos, head, member)                         \
 264         for (pos = llist_entry((head)->next, typeof(*pos), member),     \
 265                      prefetch(pos->member.next);                        \
 266              &pos->member != (head);                                    \
 267              pos = llist_entry(pos->member.next, typeof(*pos), member), \
 268                      prefetch(pos->member.next))
 269
 270 /**
 271  * llist_for_each_entry_reverse - iterate backwards over llist of given type.
 272  * @pos:        the type * to use as a loop counter.
 273  * @head:       the head for your llist.
 274  * @member:     the name of the llist_struct within the struct.
 275  */
 276 #define llist_for_each_entry_reverse(pos, head, member)                 \
 277         for (pos = llist_entry((head)->prev, typeof(*pos), member),     \
 278                      prefetch(pos->member.prev);                        \
 279              &pos->member != (head);                                    \
 280              pos = llist_entry(pos->member.prev, typeof(*pos), member), \
 281                      prefetch(pos->member.prev))
 282
 283 /**
 284  * llist_for_each_entry_continue -      iterate over llist of given type
 285  *                      continuing after existing point
 286  * @pos:        the type * to use as a loop counter.
 287  * @head:       the head for your llist.
 288  * @member:     the name of the llist_struct within the struct.
 289  */
 290 #define llist_for_each_entry_continue(pos, head, member)                \
 291         for (pos = llist_entry(pos->member.next, typeof(*pos), member), \
 292                      prefetch(pos->member.next);                        \
 293              &pos->member != (head);                                    \
 294              pos = llist_entry(pos->member.next, typeof(*pos), member), \
 295                      prefetch(pos->member.next))
 296
 297 /**
 298  * llist_for_each_entry_safe - iterate over llist of given type safe against removal of llist entry
 299  * @pos:        the type * to use as a loop counter.
 300  * @n:          another type * to use as temporary storage
 301  * @head:       the head for your llist.
 302  * @member:     the name of the llist_struct within the struct.
 303  */
 304 #define llist_for_each_entry_safe(pos, n, head, member)                 \
 305         for (pos = llist_entry((head)->next, typeof(*pos), member),     \
 306                 n = llist_entry(pos->member.next, typeof(*pos), member);        \
 307              &pos->member != (head);                                    \
 308              pos = n, n = llist_entry(n->member.next, typeof(*n), member))
 309
 310 /**
 311  * llist_for_each_rcu   -       iterate over an rcu-protected llist
 312  * @pos:        the &struct llist_head to use as a loop counter.
 313  * @head:       the head for your llist.
 314  */
 315 #define llist_for_each_rcu(pos, head) \
 316         for (pos = (head)->next, prefetch(pos->next); pos != (head); \
 317                 pos = pos->next, ({ smp_read_barrier_depends(); 0;}), prefetch(pos->next))
 318
 319 #define __llist_for_each_rcu(pos, head) \
 320         for (pos = (head)->next; pos != (head); \
 321                 pos = pos->next, ({ smp_read_barrier_depends(); 0;}))
 322
 323 /**
 324  * llist_for_each_safe_rcu      -       iterate over an rcu-protected llist safe
 325  *                                      against removal of llist entry
 326  * @pos:        the &struct llist_head to use as a loop counter.
 327  * @n:          another &struct llist_head to use as temporary storage
 328  * @head:       the head for your llist.
 329  */
 330 #define llist_for_each_safe_rcu(pos, n, head) \
 331         for (pos = (head)->next, n = pos->next; pos != (head); \
 332                 pos = n, ({ smp_read_barrier_depends(); 0;}), n = pos->next)
 333
 334 /**
 335  * llist_for_each_entry_rcu     -       iterate over rcu llist of given type
 336  * @pos:        the type * to use as a loop counter.
 337  * @head:       the head for your llist.
 338  * @member:     the name of the llist_struct within the struct.
 339  */
 340 #define llist_for_each_entry_rcu(pos, head, member)                     \
 341         for (pos = llist_entry((head)->next, typeof(*pos), member),     \
 342                      prefetch(pos->member.next);                        \
 343              &pos->member != (head);                                    \
 344              pos = llist_entry(pos->member.next, typeof(*pos), member), \
 345                      ({ smp_read_barrier_depends(); 0;}),               \
 346                      prefetch(pos->member.next))
 347
 348
 349 /**
 350  * llist_for_each_continue_rcu  -       iterate over an rcu-protected llist
 351  *                      continuing after existing point.
 352  * @pos:        the &struct llist_head to use as a loop counter.
 353  * @head:       the head for your llist.
 354  */
 355 #define llist_for_each_continue_rcu(pos, head) \
 356         for ((pos) = (pos)->next, prefetch((pos)->next); (pos) != (head); \
 357                 (pos) = (pos)->next, ({ smp_read_barrier_depends(); 0;}), prefetch((pos)->next))
 358
 359
 360 #endif