libosmocore  1.4.0
Osmocom core library
linuxlist.h
Go to the documentation of this file.
1 
12 #pragma once
13 
18 #include <stddef.h>
19 
20 #ifndef inline
21 #define inline __inline__
22 #endif
23 
24 static inline void prefetch(const void *x) {;}
25 
31 #define container_of(ptr, type, member) ({ \
32  const typeof( ((type *)0)->member ) *__mptr = (ptr); \
33  (type *)( (char *)__mptr - offsetof(type, member) );})
34 
35 
41 #define LLIST_POISON1 ((void *) 0x00100100)
42 #define LLIST_POISON2 ((void *) 0x00200200)
43 
45 struct llist_head {
47  struct llist_head *next, *prev;
48 };
49 
53 #define LLIST_HEAD_INIT(name) { &(name), &(name) }
54 
58 #define LLIST_HEAD(name) \
59  struct llist_head name = LLIST_HEAD_INIT(name)
60 
64 #define INIT_LLIST_HEAD(ptr) do { \
65  (ptr)->next = (ptr); (ptr)->prev = (ptr); \
66 } while (0)
67 
68 /*
69  * Insert a new entry between two known consecutive entries.
70  *
71  * This is only for internal llist manipulation where we know
72  * the prev/next entries already!
73  */
74 static inline void __llist_add(struct llist_head *_new,
75  struct llist_head *prev,
76  struct llist_head *next)
77 {
78  next->prev = _new;
79  _new->next = next;
80  _new->prev = prev;
81  prev->next = _new;
82 }
83 
91 static inline void llist_add(struct llist_head *_new, struct llist_head *head)
92 {
93  __llist_add(_new, head, head->next);
94 }
95 
103 static inline void llist_add_tail(struct llist_head *_new, struct llist_head *head)
104 {
105  __llist_add(_new, head->prev, head);
106 }
107 
108 /*
109  * Delete a llist entry by making the prev/next entries
110  * point to each other.
111  *
112  * This is only for internal llist manipulation where we know
113  * the prev/next entries already!
114  */
115 static inline void __llist_del(struct llist_head * prev, struct llist_head * next)
116 {
117  next->prev = prev;
118  prev->next = next;
119 }
120 
127 static inline void llist_del(struct llist_head *entry)
128 {
129  __llist_del(entry->prev, entry->next);
130  entry->next = (struct llist_head *)LLIST_POISON1;
131  entry->prev = (struct llist_head *)LLIST_POISON2;
132 }
133 
137 static inline void llist_del_init(struct llist_head *entry)
138 {
139  __llist_del(entry->prev, entry->next);
140  INIT_LLIST_HEAD(entry);
141 }
142 
147 static inline void llist_move(struct llist_head *llist, struct llist_head *head)
148 {
149  __llist_del(llist->prev, llist->next);
150  llist_add(llist, head);
151 }
152 
157 static inline void llist_move_tail(struct llist_head *llist,
158  struct llist_head *head)
159 {
160  __llist_del(llist->prev, llist->next);
161  llist_add_tail(llist, head);
162 }
163 
168 static inline int llist_empty(const struct llist_head *head)
169 {
170  return head->next == head;
171 }
172 
173 static inline void __llist_splice(struct llist_head *llist,
174  struct llist_head *head)
175 {
176  struct llist_head *first = llist->next;
177  struct llist_head *last = llist->prev;
178  struct llist_head *at = head->next;
179 
180  first->prev = head;
181  head->next = first;
182 
183  last->next = at;
184  at->prev = last;
185 }
186 
191 static inline void llist_splice(struct llist_head *llist, struct llist_head *head)
192 {
193  if (!llist_empty(llist))
194  __llist_splice(llist, head);
195 }
196 
203 static inline void llist_splice_init(struct llist_head *llist,
204  struct llist_head *head)
205 {
206  if (!llist_empty(llist)) {
207  __llist_splice(llist, head);
208  INIT_LLIST_HEAD(llist);
209  }
210 }
211 
217 #define llist_entry(ptr, type, member) \
218  container_of(ptr, type, member)
219 
227 #define llist_first_entry(ptr, type, member) \
228  llist_entry((ptr)->next, type, member)
229 
237 #define llist_last_entry(ptr, type, member) \
238  llist_entry((ptr)->prev, type, member)
239 
247 #define llist_first_entry_or_null(ptr, type, member) \
248  (!llist_empty(ptr) ? llist_first_entry(ptr, type, member) : NULL)
249 
254 #define llist_for_each(pos, head) \
255  for (pos = (head)->next, prefetch(pos->next); pos != (head); \
256  pos = pos->next, prefetch(pos->next))
257 
267 #define __llist_for_each(pos, head) \
268  for (pos = (head)->next; pos != (head); pos = pos->next)
269 
274 #define llist_for_each_prev(pos, head) \
275  for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \
276  pos = pos->prev, prefetch(pos->prev))
277 
283 #define llist_for_each_safe(pos, n, head) \
284  for (pos = (head)->next, n = pos->next; pos != (head); \
285  pos = n, n = pos->next)
286 
292 #define llist_for_each_entry(pos, head, member) \
293  for (pos = llist_entry((head)->next, typeof(*pos), member), \
294  prefetch(pos->member.next); \
295  &pos->member != (head); \
296  pos = llist_entry(pos->member.next, typeof(*pos), member), \
297  prefetch(pos->member.next))
298 
304 #define llist_for_each_entry_reverse(pos, head, member) \
305  for (pos = llist_entry((head)->prev, typeof(*pos), member), \
306  prefetch(pos->member.prev); \
307  &pos->member != (head); \
308  pos = llist_entry(pos->member.prev, typeof(*pos), member), \
309  prefetch(pos->member.prev))
310 
317 #define llist_for_each_entry_continue(pos, head, member) \
318  for (pos = llist_entry(pos->member.next, typeof(*pos), member), \
319  prefetch(pos->member.next); \
320  &pos->member != (head); \
321  pos = llist_entry(pos->member.next, typeof(*pos), member), \
322  prefetch(pos->member.next))
323 
331 #define llist_for_each_entry_safe(pos, n, head, member) \
332  for (pos = llist_entry((head)->next, typeof(*pos), member), \
333  n = llist_entry(pos->member.next, typeof(*pos), member); \
334  &pos->member != (head); \
335  pos = n, n = llist_entry(n->member.next, typeof(*n), member))
336 
341 #define llist_for_each_rcu(pos, head) \
342  for (pos = (head)->next, prefetch(pos->next); pos != (head); \
343  pos = pos->next, ({ smp_read_barrier_depends(); 0;}), prefetch(pos->next))
344 
345 #define __llist_for_each_rcu(pos, head) \
346  for (pos = (head)->next; pos != (head); \
347  pos = pos->next, ({ smp_read_barrier_depends(); 0;}))
348 
354 #define llist_for_each_safe_rcu(pos, n, head) \
355  for (pos = (head)->next, n = pos->next; pos != (head); \
356  pos = n, ({ smp_read_barrier_depends(); 0;}), n = pos->next)
357 
363 #define llist_for_each_entry_rcu(pos, head, member) \
364  for (pos = llist_entry((head)->next, typeof(*pos), member), \
365  prefetch(pos->member.next); \
366  &pos->member != (head); \
367  pos = llist_entry(pos->member.next, typeof(*pos), member), \
368  ({ smp_read_barrier_depends(); 0;}), \
369  prefetch(pos->member.next))
370 
371 
376 #define llist_for_each_continue_rcu(pos, head) \
377  for ((pos) = (pos)->next, prefetch((pos)->next); (pos) != (head); \
378  (pos) = (pos)->next, ({ smp_read_barrier_depends(); 0;}), prefetch((pos)->next))
379 
387 static inline unsigned int llist_count(const struct llist_head *head)
388 {
389  struct llist_head *entry;
390  unsigned int i = 0;
391  llist_for_each(entry, head)
392  i++;
393  return i;
394 }
395 
LLIST_POISON1
#define LLIST_POISON1
These are non-NULL pointers that will result in page faults under normal circumstances,...
Definition: linuxlist.h:41
llist_splice
static void llist_splice(struct llist_head *llist, struct llist_head *head)
Join two linked lists.
Definition: linuxlist.h:191
llist_for_each
#define llist_for_each(pos, head)
Iterate over a linked list.
Definition: linuxlist.h:254
llist_head::next
struct llist_head * next
Pointer to next and previous item.
Definition: linuxlist.h:47
llist_del_init
static void llist_del_init(struct llist_head *entry)
Delete a single entry from a linked list and reinitialize it.
Definition: linuxlist.h:137
INIT_LLIST_HEAD
#define INIT_LLIST_HEAD(ptr)
Initialize a llist_head to point back to itself.
Definition: linuxlist.h:64
llist_del
static void llist_del(struct llist_head *entry)
Delete a single entry from a linked list.
Definition: linuxlist.h:127
llist_move
static void llist_move(struct llist_head *llist, struct llist_head *head)
Delete from one llist and add as another's head.
Definition: linuxlist.h:147
__llist_del
static void __llist_del(struct llist_head *prev, struct llist_head *next)
Definition: linuxlist.h:115
__llist_add
static void __llist_add(struct llist_head *_new, struct llist_head *prev, struct llist_head *next)
Definition: linuxlist.h:74
llist_move_tail
static void llist_move_tail(struct llist_head *llist, struct llist_head *head)
Delete from one llist and add as another's tail.
Definition: linuxlist.h:157
LLIST_POISON2
#define LLIST_POISON2
Definition: linuxlist.h:42
llist_head
(double) linked list header structure
Definition: linuxlist.h:45
llist_count
static unsigned int llist_count(const struct llist_head *head)
Count number of llist items by iterating.
Definition: linuxlist.h:387
llist_add
static void llist_add(struct llist_head *_new, struct llist_head *head)
Add a new entry into a linked list (at head).
Definition: linuxlist.h:91
llist_add_tail
static void llist_add_tail(struct llist_head *_new, struct llist_head *head)
Add a new entry into a linked list (at tail).
Definition: linuxlist.h:103
__llist_splice
static void __llist_splice(struct llist_head *llist, struct llist_head *head)
Definition: linuxlist.h:173
llist_empty
static int llist_empty(const struct llist_head *head)
Test whether a linked list is empty.
Definition: linuxlist.h:168
llist_head::prev
struct llist_head * prev
Definition: linuxlist.h:47
prefetch
static void prefetch(const void *x)
Definition: linuxlist.h:24
llist_splice_init
static void llist_splice_init(struct llist_head *llist, struct llist_head *head)
Join two llists and reinitialise the emptied llist.
Definition: linuxlist.h:203