FD.io VPP  v20.09-64-g4f7b92f0a
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 
28 
29 typedef struct clib_llist_anchor
30 {
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  * Get prev list entry index
56  *
57  * @param E pool entry
58  * @name list anchor name
59  * @return previous index
60  */
61 #define clib_llist_prev_index(E,name) _lprev(E,name)
62 /**
63  * Get next list entry index
64  *
65  * @param E pool entry
66  * @name list anchor name
67  * @return next index
68  */
69 #define clib_llist_next_index(E,name) _lnext(E,name)
70 /**
71  * Get next pool entry
72  *
73  * @param LP linked list pool
74  * @param name list anchor name
75  * @param E pool entry
76  * @return next pool entry
77  */
78 #define clib_llist_next(LP,name,E) pool_elt_at_index((LP),_lnext((E),name))
79 /**
80  * Get previous pool entry
81  *
82  * @param LP linked list pool
83  * @param name list anchor name
84  * @param E pool entry
85  * @return previous pool entry
86  */
87 #define clib_llist_prev(LP,name,E) pool_elt_at_index((LP),_lprev((E),name))
88 /**
89  * Initialize element in llist for entry
90  *
91  * @param LP linked list pool
92  * @param name list anchor name
93  * @param E entry whose ll anchor is to be initialized
94  */
95 #define clib_llist_anchor_init(LP,name,E) \
96 do { \
97  _lprev ((E),name) = clib_llist_entry_index ((LP), (E)); \
98  _lnext ((E),name) = _lprev ((E),name); \
99 } while (0)
100 /**
101  * Initialize llist head
102  *
103  * @param LP linked list pool
104  * @param name list anchor name
105  */
106 #define clib_llist_make_head(LP,name) \
107 ({ \
108  typeof (LP) _ll_var (head); \
109  pool_get_zero ((LP), _ll_var (head)); \
110  clib_llist_anchor_init ((LP),name,_ll_var (head)); \
111  clib_llist_entry_index ((LP), _ll_var (head)); \
112 })
113 /**
114  * Check is list is empty
115  *
116  * @param LP linked list pool
117  * @param name list anchor name
118  * @param H list head
119  * @return 1 if sentinel is the only node part of the list, 0 otherwise
120  */
121 #define clib_llist_is_empty(LP,name,H) \
122  (clib_llist_entry_index (LP,H) == (H)->name.next)
123 /**
124  * Check if element is linked in a list
125  *
126  * @param E list element
127  * @param name list anchor name
128  */
129 #define clib_llist_elt_is_linked(E,name) \
130  ((E)->name.next != CLIB_LLIST_INVALID_INDEX \
131  && (E)->name.prev != CLIB_LLIST_INVALID_INDEX)
132 /**
133  * Insert entry between previous and next
134  *
135  * Internal use.
136  *
137  * @param LP linked list pool
138  * @param name list anchor name
139  * @param E new entry
140  * @param P previous in list
141  * @param N next in list
142  */
143 #define _llist_insert(LP,name,E,P,N) \
144 do { \
145  _lprev (E,name) = _lprev(N,name); \
146  _lnext (E,name) = _lnext(P,name); \
147  _lprev ((N),name) = clib_llist_entry_index ((LP),(E)); \
148  _lnext ((P),name) = clib_llist_entry_index ((LP),(E)); \
149 } while (0)
150 /**
151  * Insert entry after previous
152  *
153  * @param LP linked list pool
154  * @param name list anchor name
155  * @param E new entry
156  * @param P previous in list
157  */
158 #define clib_llist_insert(LP,name,E,P) \
159 do { \
160  typeof (LP) _ll_var (N) = clib_llist_next (LP,name,P); \
161  _llist_insert ((LP),name,(E),(P), _ll_var (N)); \
162 } while (0)
163 
164 /**
165  * Add entry after head
166  *
167  * @param LP linked list pool
168  * @param name list anchor name
169  * @param E new entry
170  * @param H list head
171  */
172 #define clib_llist_add(LP,name,E,H) clib_llist_insert ((LP),name,(E),(H))
173 /**
174  * Add entry after tail
175  *
176  * @param LP linked list pool
177  * @param name list anchor name
178  * @param E new entry
179  * @param H list head
180  */
181 #define clib_llist_add_tail(LP,name,E,H) \
182 do { \
183  typeof (LP) _ll_var (P) = clib_llist_prev ((LP),name,(H)); \
184  _llist_insert ((LP),name,(E),_ll_var (P),(H)); \
185 } while (0)
186 /**
187  * Remove entry from list
188  *
189  * @param LP linked list pool
190  * @param name list anchor name
191  * @param E entry to be removed
192  */
193 #define clib_llist_remove(LP,name,E) \
194 do { \
195  ASSERT ((E) != clib_llist_next (LP,name,E));/* don't remove sentinel */\
196  ASSERT (_lnext (E,name) != CLIB_LLIST_INVALID_INDEX); \
197  ASSERT (_lprev (E,name) != CLIB_LLIST_INVALID_INDEX); \
198  typeof (LP) _ll_var (P) = clib_llist_prev ((LP),name,E); \
199  typeof (LP) _ll_var (N) = clib_llist_next ((LP),name,E); \
200  _lnext (_ll_var (P),name) = _lnext (E,name); \
201  _lprev (_ll_var (N),name) = _lprev (E,name); \
202  _lnext (E,name) = _lprev (E,name) = CLIB_LLIST_INVALID_INDEX; \
203 }while (0)
204 /**
205  * Removes and returns the first element in the list.
206  *
207  * The element is not freed. It's the responsability of the caller to
208  * free it.
209  *
210  * @param LP linked list pool
211  * @param name list anchor name
212  * @param E storage the first entry
213  * @param H list head entry
214  */
215 #define clib_llist_pop_first(LP,name,E,H) \
216 do { \
217  E = clib_llist_next (LP,name,H); \
218  clib_llist_remove (LP,name,E); \
219 } while (0)
220 /**
221  * Splice two lists at a given position
222  *
223  * List spliced into destination list is left with 0 entries, i.e., head
224  * is made to point to itself.
225  *
226  * @param LP linked list pool
227  * @param name list anchor name
228  * @param P position in destination where source list is spliced
229  * @param H head of source list that will be spliced into destination
230  */
231 #define clib_llist_splice(LP,name,P,H) \
232 do { \
233  typeof (LP) _ll_var (fe) = clib_llist_next (LP,name,H); \
234  if (_ll_var (fe) != (H)) \
235  { \
236  typeof (LP) _ll_var (le) = clib_llist_prev (LP,name,H); \
237  typeof (LP) _ll_var (ne) = clib_llist_next (LP,name,P); \
238  _lprev (_ll_var (fe),name) = clib_llist_entry_index(LP,P); \
239  _lnext (_ll_var (le),name) = clib_llist_entry_index(LP,_ll_var (ne));\
240  _lnext (P,name) = clib_llist_entry_index (LP,_ll_var (fe)); \
241  _lprev (_ll_var (ne),name) = clib_llist_entry_index(LP,_ll_var (le));\
242  _lnext (H,name) = clib_llist_entry_index(LP,H); \
243  _lprev (H,name) = _lnext (H,name); \
244  } \
245 } while (0)
246 /**
247  * Walk list starting at head
248  *
249  * @param LP linked list pool
250  * @param name list anchor name
251  * @param H head entry
252  * @param E entry iterator
253  * @param body code to be executed
254  */
255 #define clib_llist_foreach(LP,name,H,E,body) \
256 do { \
257  typeof (LP) _ll_var (n); \
258  (E) = clib_llist_next (LP,name,H); \
259  while (E != H) \
260  { \
261  _ll_var (n) = clib_llist_next (LP,name,E); \
262  do { body; } while (0); \
263  (E) = _ll_var (n); \
264  } \
265 } while (0)
266 /**
267  * Walk list starting at head safe
268  *
269  * @param LP linked list pool
270  * @param name list anchor name
271  * @param HI head index
272  * @param EI entry index iterator
273  * @param body code to be executed
274  */
275 #define clib_llist_foreach_safe(LP,name,H,E,body) \
276 do { \
277  clib_llist_index_t _ll_var (HI) = clib_llist_entry_index (LP, H); \
278  clib_llist_index_t _ll_var (EI), _ll_var (NI); \
279  _ll_var (EI) = _lnext ((H),name); \
280  while (_ll_var (EI) != _ll_var (HI)) \
281  { \
282  (E) = pool_elt_at_index (LP, _ll_var (EI)); \
283  _ll_var (NI) = _lnext ((E),name); \
284  do { body; } while (0); \
285  _ll_var (EI) = _ll_var (NI); \
286  } \
287 } while (0)
288 /**
289  * Walk list starting at head in reverse order
290  *
291  * @param LP linked list pool
292  * @param name list anchor name
293  * @param H head entry
294  * @param E entry iterator
295  * @param body code to be executed
296  */
297 #define clib_llist_foreach_reverse(LP,name,H,E,body) \
298 do { \
299  typeof (LP) _ll_var (p); \
300  (E) = clib_llist_prev (LP,name,H); \
301  while (E != H) \
302  { \
303  _ll_var (p) = clib_llist_prev (LP,name,E); \
304  do { body; } while (0); \
305  (E) = _ll_var (p); \
306  } \
307 } while (0)
308 
309 #endif /* SRC_VPPINFRA_CLIB_LLIST_H_ */
310 
311 /*
312  * fd.io coding-style-patch-verification: ON
313  *
314  * Local Variables:
315  * eval: (c-set-style "gnu")
316  * End:
317  */
clib_llist_index_t prev
Definition: llist.h:31
Fixed length block allocator.
clib_llist_index_t next
Definition: llist.h:32
unsigned int u32
Definition: types.h:88
u32 clib_llist_index_t
Definition: llist.h:27
struct clib_llist_anchor clib_llist_anchor_t