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