FD.io VPP  v21.10.1-2-g0a485f517
Vector Packet Processing
llist.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2019 Cisco and/or its affiliates.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at:
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  *
15  * @file
16  * @brief Circular doubly linked list with head sentinel.
17  * List entries are allocated out of a "supporting" pool and all pool entries
18  * must contain a list anchor struct for each list they pertain to.
19  */
20 
21 #ifndef SRC_VPPINFRA_CLIB_LLIST_H_
22 #define SRC_VPPINFRA_CLIB_LLIST_H_
23 
24 #include <vppinfra/types.h>
25 #include <vppinfra/pool.h>
26 
27 typedef u32 clib_llist_index_t;
28 
29 typedef struct clib_llist_anchor
30 {
31  clib_llist_index_t prev;
32  clib_llist_index_t next;
33 } clib_llist_anchor_t;
34 
35 #define CLIB_LLIST_INVALID_INDEX ((u32)~0)
36 
37 /**
38  * Local variable naming macro.
39  */
40 #define _ll_var(v) _llist_##v
41 /**
42  * Local macros to grab llist anchor next and prev from pool entry
43  */
44 #define _lnext(E,name) ((E)->name).next
45 #define _lprev(E,name) ((E)->name).prev
46 /**
47  * Get list entry index
48  *
49  * @param LP linked list pool
50  * @param E pool entry
51  * @return pool entry index
52  */
53 #define clib_llist_entry_index(LP,E) ((E) - (LP))
54 /**
55  * Alloc new element
56  *
57  * @param LP linked list pool
58  * @param E element to be returned
59  */
60 #define clib_llist_get(LP, E) pool_get (LP, E)
61 /**
62  * Free element
63  *
64  * @param LP linked list pool
65  * @param E element to be freed
66  */
67 #define clib_llist_put(LP, E) pool_put (LP, E)
68 /**
69  * Free list supporting container
70  *
71  * @param LP linked list pool
72  */
73 #define clib_llist_free(LP) pool_free (LP)
74 /**
75  * Get list elt at index
76  *
77  * @param LP linked list pool
78  * @param EI element index
79  * @return element
80  */
81 #define clib_llist_elt(LP, EI) pool_elt_at_index (LP, EI)
82 /**
83  * Get number of elements in supporting container
84  *
85  * This is NOT the elements linked in the list but the number of
86  * elements consumed out of the supporting pool
87  *
88  * @param LP linked list pool
89  * @return number of elements
90  */
91 #define clib_llist_elts(LP) pool_elts (LP)
92 /**
93  * Get prev list entry index
94  *
95  * @param E pool entry
96  * @name list anchor name
97  * @return previous index
98  */
99 #define clib_llist_prev_index(E,name) _lprev(E,name)
100 /**
101  * Get next list entry index
102  *
103  * @param E pool entry
104  * @name list anchor name
105  * @return next index
106  */
107 #define clib_llist_next_index(E,name) _lnext(E,name)
108 /**
109  * Get next pool entry
110  *
111  * @param LP linked list pool
112  * @param name list anchor name
113  * @param E pool entry
114  * @return next pool entry
115  */
116 #define clib_llist_next(LP,name,E) pool_elt_at_index((LP),_lnext((E),name))
117 /**
118  * Get previous pool entry
119  *
120  * @param LP linked list pool
121  * @param name list anchor name
122  * @param E pool entry
123  * @return previous pool entry
124  */
125 #define clib_llist_prev(LP,name,E) pool_elt_at_index((LP),_lprev((E),name))
126 /**
127  * Initialize element in llist for entry
128  *
129  * @param LP linked list pool
130  * @param name list anchor name
131  * @param E entry whose ll anchor is to be initialized
132  */
133 #define clib_llist_anchor_init(LP,name,E) \
134 do { \
135  _lprev ((E),name) = clib_llist_entry_index ((LP), (E)); \
136  _lnext ((E),name) = _lprev ((E),name); \
137 } while (0)
138 /**
139  * Initialize llist head
140  *
141  * @param LP linked list pool
142  * @param name list anchor name
143  */
144 #define clib_llist_make_head(LP,name) \
145 ({ \
146  typeof (LP) _ll_var (head); \
147  pool_get_zero ((LP), _ll_var (head)); \
148  clib_llist_anchor_init ((LP),name,_ll_var (head)); \
149  clib_llist_entry_index ((LP), _ll_var (head)); \
150 })
151 /**
152  * Check is list is empty
153  *
154  * @param LP linked list pool
155  * @param name list anchor name
156  * @param H list head
157  * @return 1 if sentinel is the only node part of the list, 0 otherwise
158  */
159 #define clib_llist_is_empty(LP,name,H) \
160  (clib_llist_entry_index (LP,H) == (H)->name.next)
161 /**
162  * Check if element is linked in a list
163  *
164  * @param E list element
165  * @param name list anchor name
166  */
167 #define clib_llist_elt_is_linked(E,name) \
168  ((E)->name.next != CLIB_LLIST_INVALID_INDEX \
169  && (E)->name.prev != CLIB_LLIST_INVALID_INDEX)
170 /**
171  * Insert entry between previous and next
172  *
173  * Internal use.
174  *
175  * @param LP linked list pool
176  * @param name list anchor name
177  * @param E new entry
178  * @param P previous in list
179  * @param N next in list
180  */
181 #define _llist_insert(LP,name,E,P,N) \
182 do { \
183  _lprev (E,name) = _lprev(N,name); \
184  _lnext (E,name) = _lnext(P,name); \
185  _lprev ((N),name) = clib_llist_entry_index ((LP),(E)); \
186  _lnext ((P),name) = clib_llist_entry_index ((LP),(E)); \
187 } while (0)
188 /**
189  * Insert entry after previous
190  *
191  * @param LP linked list pool
192  * @param name list anchor name
193  * @param E new entry
194  * @param P previous in list
195  */
196 #define clib_llist_insert(LP,name,E,P) \
197 do { \
198  typeof (LP) _ll_var (N) = clib_llist_next (LP,name,P); \
199  _llist_insert ((LP),name,(E),(P), _ll_var (N)); \
200 } while (0)
201 
202 /**
203  * Add entry after head
204  *
205  * @param LP linked list pool
206  * @param name list anchor name
207  * @param E new entry
208  * @param H list head
209  */
210 #define clib_llist_add(LP,name,E,H) clib_llist_insert ((LP),name,(E),(H))
211 /**
212  * Add entry after tail
213  *
214  * @param LP linked list pool
215  * @param name list anchor name
216  * @param E new entry
217  * @param H list head
218  */
219 #define clib_llist_add_tail(LP,name,E,H) \
220 do { \
221  typeof (LP) _ll_var (P) = clib_llist_prev ((LP),name,(H)); \
222  _llist_insert ((LP),name,(E),_ll_var (P),(H)); \
223 } while (0)
224 /**
225  * Remove entry from list
226  *
227  * @param LP linked list pool
228  * @param name list anchor name
229  * @param E entry to be removed
230  */
231 #define clib_llist_remove(LP,name,E) \
232 do { \
233  ASSERT ((E) != clib_llist_next (LP,name,E));/* don't remove sentinel */\
234  ASSERT (_lnext (E,name) != CLIB_LLIST_INVALID_INDEX); \
235  ASSERT (_lprev (E,name) != CLIB_LLIST_INVALID_INDEX); \
236  typeof (LP) _ll_var (P) = clib_llist_prev ((LP),name,E); \
237  typeof (LP) _ll_var (N) = clib_llist_next ((LP),name,E); \
238  _lnext (_ll_var (P),name) = _lnext (E,name); \
239  _lprev (_ll_var (N),name) = _lprev (E,name); \
240  _lnext (E,name) = _lprev (E,name) = CLIB_LLIST_INVALID_INDEX; \
241 }while (0)
242 /**
243  * Removes and returns the first element in the list.
244  *
245  * The element is not freed. It's the responsability of the caller to
246  * free it.
247  *
248  * @param LP linked list pool
249  * @param name list anchor name
250  * @param E storage the first entry
251  * @param H list head entry
252  */
253 #define clib_llist_pop_first(LP,name,E,H) \
254 do { \
255  E = clib_llist_next (LP,name,H); \
256  clib_llist_remove (LP,name,E); \
257 } while (0)
258 /**
259  * Splice two lists at a given position
260  *
261  * List spliced into destination list is left with 0 entries, i.e., head
262  * is made to point to itself.
263  *
264  * @param LP linked list pool
265  * @param name list anchor name
266  * @param P position in destination where source list is spliced
267  * @param H head of source list that will be spliced into destination
268  */
269 #define clib_llist_splice(LP,name,P,H) \
270 do { \
271  typeof (LP) _ll_var (fe) = clib_llist_next (LP,name,H); \
272  if (_ll_var (fe) != (H)) \
273  { \
274  typeof (LP) _ll_var (le) = clib_llist_prev (LP,name,H); \
275  typeof (LP) _ll_var (ne) = clib_llist_next (LP,name,P); \
276  _lprev (_ll_var (fe),name) = clib_llist_entry_index(LP,P); \
277  _lnext (_ll_var (le),name) = clib_llist_entry_index(LP,_ll_var (ne));\
278  _lnext (P,name) = clib_llist_entry_index (LP,_ll_var (fe)); \
279  _lprev (_ll_var (ne),name) = clib_llist_entry_index(LP,_ll_var (le));\
280  _lnext (H,name) = clib_llist_entry_index(LP,H); \
281  _lprev (H,name) = _lnext (H,name); \
282  } \
283 } while (0)
284 /**
285  * Walk list starting at head
286  *
287  * @param LP linked list pool
288  * @param name list anchor name
289  * @param H head entry
290  * @param E entry iterator
291  * @param body code to be executed
292  */
293 #define clib_llist_foreach(LP,name,H,E,body) \
294 do { \
295  typeof (LP) _ll_var (n); \
296  (E) = clib_llist_next (LP,name,H); \
297  while (E != H) \
298  { \
299  _ll_var (n) = clib_llist_next (LP,name,E); \
300  do { body; } while (0); \
301  (E) = _ll_var (n); \
302  } \
303 } while (0)
304 /**
305  * Walk list starting at head safe
306  *
307  * @param LP linked list pool
308  * @param name list anchor name
309  * @param HI head index
310  * @param EI entry index iterator
311  * @param body code to be executed
312  */
313 #define clib_llist_foreach_safe(LP,name,H,E,body) \
314 do { \
315  clib_llist_index_t _ll_var (HI) = clib_llist_entry_index (LP, H); \
316  clib_llist_index_t _ll_var (EI), _ll_var (NI); \
317  _ll_var (EI) = _lnext ((H),name); \
318  while (_ll_var (EI) != _ll_var (HI)) \
319  { \
320  (E) = pool_elt_at_index (LP, _ll_var (EI)); \
321  _ll_var (NI) = _lnext ((E),name); \
322  do { body; } while (0); \
323  _ll_var (EI) = _ll_var (NI); \
324  } \
325 } while (0)
326 /**
327  * Walk list starting at head in reverse order
328  *
329  * @param LP linked list pool
330  * @param name list anchor name
331  * @param H head entry
332  * @param E entry iterator
333  * @param body code to be executed
334  */
335 #define clib_llist_foreach_reverse(LP,name,H,E,body) \
336 do { \
337  typeof (LP) _ll_var (p); \
338  (E) = clib_llist_prev (LP,name,H); \
339  while (E != H) \
340  { \
341  _ll_var (p) = clib_llist_prev (LP,name,E); \
342  do { body; } while (0); \
343  (E) = _ll_var (p); \
344  } \
345 } while (0)
346 
347 #endif /* SRC_VPPINFRA_CLIB_LLIST_H_ */
348 
349 /*
350  * fd.io coding-style-patch-verification: ON
351  *
352  * Local Variables:
353  * eval: (c-set-style "gnu")
354  * End:
355  */
types.h
clib_llist_anchor
Definition: llist.h:29
clib_llist_index_t
u32 clib_llist_index_t
Definition: llist.h:27
clib_llist_anchor::next
clib_llist_index_t next
Definition: llist.h:32
pool.h
Fixed length block allocator. Pools are built from clib vectors and bitmaps. Use pools when repeatedl...
clib_llist_anchor_t
struct clib_llist_anchor clib_llist_anchor_t
u32
unsigned int u32
Definition: types.h:88
clib_llist_anchor::prev
clib_llist_index_t prev
Definition: llist.h:31