libosmocore  0.9.3
Osmocom core library
include/osmocom/core/linuxlist.h
00001 #pragma once
00002 
00003 #include <stddef.h>
00004 
00005 #ifndef inline
00006 #define inline __inline__
00007 #endif
00008 
00009 static inline void prefetch(const void *x) {;}
00010 
00019 #define container_of(ptr, type, member) ({                      \
00020         const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
00021         (type *)( (char *)__mptr - offsetof(type, member) );})
00022 
00023 
00024 /*
00025  * These are non-NULL pointers that will result in page faults
00026  * under normal circumstances, used to verify that nobody uses
00027  * non-initialized llist entries.
00028  */
00029 #define LLIST_POISON1  ((void *) 0x00100100)
00030 #define LLIST_POISON2  ((void *) 0x00200200)
00031 
00032 /*
00033  * Simple doubly linked llist implementation.
00034  *
00035  * Some of the internal functions ("__xxx") are useful when
00036  * manipulating whole llists rather than single entries, as
00037  * sometimes we already know the next/prev entries and we can
00038  * generate better code by using them directly rather than
00039  * using the generic single-entry routines.
00040  */
00041 
00042 struct llist_head {
00043         struct llist_head *next, *prev;
00044 };
00045 
00046 #define LLIST_HEAD_INIT(name) { &(name), &(name) }
00047 
00048 #define LLIST_HEAD(name) \
00049         struct llist_head name = LLIST_HEAD_INIT(name)
00050 
00051 #define INIT_LLIST_HEAD(ptr) do { \
00052         (ptr)->next = (ptr); (ptr)->prev = (ptr); \
00053 } while (0)
00054 
00055 /*
00056  * Insert a new entry between two known consecutive entries. 
00057  *
00058  * This is only for internal llist manipulation where we know
00059  * the prev/next entries already!
00060  */
00061 static inline void __llist_add(struct llist_head *_new,
00062                               struct llist_head *prev,
00063                               struct llist_head *next)
00064 {
00065         next->prev = _new;
00066         _new->next = next;
00067         _new->prev = prev;
00068         prev->next = _new;
00069 }
00070 
00079 static inline void llist_add(struct llist_head *_new, struct llist_head *head)
00080 {
00081         __llist_add(_new, head, head->next);
00082 }
00083 
00092 static inline void llist_add_tail(struct llist_head *_new, struct llist_head *head)
00093 {
00094         __llist_add(_new, head->prev, head);
00095 }
00096 
00097 /*
00098  * Delete a llist entry by making the prev/next entries
00099  * point to each other.
00100  *
00101  * This is only for internal llist manipulation where we know
00102  * the prev/next entries already!
00103  */
00104 static inline void __llist_del(struct llist_head * prev, struct llist_head * next)
00105 {
00106         next->prev = prev;
00107         prev->next = next;
00108 }
00109 
00116 static inline void llist_del(struct llist_head *entry)
00117 {
00118         __llist_del(entry->prev, entry->next);
00119         entry->next = (struct llist_head *)LLIST_POISON1;
00120         entry->prev = (struct llist_head *)LLIST_POISON2;
00121 }
00122 
00127 static inline void llist_del_init(struct llist_head *entry)
00128 {
00129         __llist_del(entry->prev, entry->next);
00130         INIT_LLIST_HEAD(entry); 
00131 }
00132 
00138 static inline void llist_move(struct llist_head *llist, struct llist_head *head)
00139 {
00140         __llist_del(llist->prev, llist->next);
00141         llist_add(llist, head);
00142 }
00143 
00149 static inline void llist_move_tail(struct llist_head *llist,
00150                                   struct llist_head *head)
00151 {
00152         __llist_del(llist->prev, llist->next);
00153         llist_add_tail(llist, head);
00154 }
00155 
00160 static inline int llist_empty(const struct llist_head *head)
00161 {
00162         return head->next == head;
00163 }
00164 
00165 static inline void __llist_splice(struct llist_head *llist,
00166                                  struct llist_head *head)
00167 {
00168         struct llist_head *first = llist->next;
00169         struct llist_head *last = llist->prev;
00170         struct llist_head *at = head->next;
00171 
00172         first->prev = head;
00173         head->next = first;
00174 
00175         last->next = at;
00176         at->prev = last;
00177 }
00178 
00184 static inline void llist_splice(struct llist_head *llist, struct llist_head *head)
00185 {
00186         if (!llist_empty(llist))
00187                 __llist_splice(llist, head);
00188 }
00189 
00197 static inline void llist_splice_init(struct llist_head *llist,
00198                                     struct llist_head *head)
00199 {
00200         if (!llist_empty(llist)) {
00201                 __llist_splice(llist, head);
00202                 INIT_LLIST_HEAD(llist);
00203         }
00204 }
00205 
00212 #define llist_entry(ptr, type, member) \
00213         container_of(ptr, type, member)
00214 
00220 #define llist_for_each(pos, head) \
00221         for (pos = (head)->next, prefetch(pos->next); pos != (head); \
00222                 pos = pos->next, prefetch(pos->next))
00223 
00234 #define __llist_for_each(pos, head) \
00235         for (pos = (head)->next; pos != (head); pos = pos->next)
00236 
00242 #define llist_for_each_prev(pos, head) \
00243         for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \
00244                 pos = pos->prev, prefetch(pos->prev))
00245                 
00252 #define llist_for_each_safe(pos, n, head) \
00253         for (pos = (head)->next, n = pos->next; pos != (head); \
00254                 pos = n, n = pos->next)
00255 
00262 #define llist_for_each_entry(pos, head, member)                         \
00263         for (pos = llist_entry((head)->next, typeof(*pos), member),     \
00264                      prefetch(pos->member.next);                        \
00265              &pos->member != (head);                                    \
00266              pos = llist_entry(pos->member.next, typeof(*pos), member), \
00267                      prefetch(pos->member.next))
00268 
00275 #define llist_for_each_entry_reverse(pos, head, member)                 \
00276         for (pos = llist_entry((head)->prev, typeof(*pos), member),     \
00277                      prefetch(pos->member.prev);                        \
00278              &pos->member != (head);                                    \
00279              pos = llist_entry(pos->member.prev, typeof(*pos), member), \
00280                      prefetch(pos->member.prev))
00281 
00289 #define llist_for_each_entry_continue(pos, head, member)                \
00290         for (pos = llist_entry(pos->member.next, typeof(*pos), member), \
00291                      prefetch(pos->member.next);                        \
00292              &pos->member != (head);                                    \
00293              pos = llist_entry(pos->member.next, typeof(*pos), member), \
00294                      prefetch(pos->member.next))
00295 
00304 #define llist_for_each_entry_safe(pos, n, head, member)                 \
00305         for (pos = llist_entry((head)->next, typeof(*pos), member),     \
00306                 n = llist_entry(pos->member.next, typeof(*pos), member);        \
00307              &pos->member != (head);                                    \
00308              pos = n, n = llist_entry(n->member.next, typeof(*n), member))
00309 
00315 #define llist_for_each_rcu(pos, head) \
00316         for (pos = (head)->next, prefetch(pos->next); pos != (head); \
00317                 pos = pos->next, ({ smp_read_barrier_depends(); 0;}), prefetch(pos->next))
00318                 
00319 #define __llist_for_each_rcu(pos, head) \
00320         for (pos = (head)->next; pos != (head); \
00321                 pos = pos->next, ({ smp_read_barrier_depends(); 0;}))
00322                 
00330 #define llist_for_each_safe_rcu(pos, n, head) \
00331         for (pos = (head)->next, n = pos->next; pos != (head); \
00332                 pos = n, ({ smp_read_barrier_depends(); 0;}), n = pos->next)
00333 
00340 #define llist_for_each_entry_rcu(pos, head, member)                     \
00341         for (pos = llist_entry((head)->next, typeof(*pos), member),     \
00342                      prefetch(pos->member.next);                        \
00343              &pos->member != (head);                                    \
00344              pos = llist_entry(pos->member.next, typeof(*pos), member), \
00345                      ({ smp_read_barrier_depends(); 0;}),               \
00346                      prefetch(pos->member.next))
00347 
00348 
00355 #define llist_for_each_continue_rcu(pos, head) \
00356         for ((pos) = (pos)->next, prefetch((pos)->next); (pos) != (head); \
00357                 (pos) = (pos)->next, ({ smp_read_barrier_depends(); 0;}), prefetch((pos)->next))