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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
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.
21 #ifndef SRC_VPPINFRA_CLIB_LLIST_H_
22 #define SRC_VPPINFRA_CLIB_LLIST_H_
24 #include <vppinfra/types.h>
25 #include <vppinfra/pool.h>
27 typedef u32 clib_llist_index_t;
29 typedef struct clib_llist_anchor
31 clib_llist_index_t prev;
32 clib_llist_index_t next;
33 } clib_llist_anchor_t;
35 #define CLIB_LLIST_INVALID_INDEX ((u32)~0)
38 * Local variable naming macro.
40 #define _ll_var(v) _llist_##v
42 * Local macros to grab llist anchor next and prev from pool entry
44 #define _lnext(E,name) ((E)->name).next
45 #define _lprev(E,name) ((E)->name).prev
47 * Get list entry index
49 * @param LP linked list pool
51 * @return pool entry index
53 #define clib_llist_entry_index(LP,E) ((E) - (LP))
57 * @param LP linked list pool
58 * @param E element to be returned
60 #define clib_llist_get(LP, E) pool_get (LP, E)
64 * @param LP linked list pool
65 * @param E element to be freed
67 #define clib_llist_put(LP, E) pool_put (LP, E)
69 * Free list supporting container
71 * @param LP linked list pool
73 #define clib_llist_free(LP) pool_free (LP)
75 * Get list elt at index
77 * @param LP linked list pool
78 * @param EI element index
81 #define clib_llist_elt(LP, EI) pool_elt_at_index (LP, EI)
83 * Get number of elements in supporting container
85 * This is NOT the elements linked in the list but the number of
86 * elements consumed out of the supporting pool
88 * @param LP linked list pool
89 * @return number of elements
91 #define clib_llist_elts(LP) pool_elts (LP)
93 * Get prev list entry index
96 * @name list anchor name
97 * @return previous index
99 #define clib_llist_prev_index(E,name) _lprev(E,name)
101 * Get next list entry index
103 * @param E pool entry
104 * @name list anchor name
107 #define clib_llist_next_index(E,name) _lnext(E,name)
109 * Get next pool entry
111 * @param LP linked list pool
112 * @param name list anchor name
113 * @param E pool entry
114 * @return next pool entry
116 #define clib_llist_next(LP,name,E) pool_elt_at_index((LP),_lnext((E),name))
118 * Get previous pool entry
120 * @param LP linked list pool
121 * @param name list anchor name
122 * @param E pool entry
123 * @return previous pool entry
125 #define clib_llist_prev(LP,name,E) pool_elt_at_index((LP),_lprev((E),name))
127 * Initialize element in llist for entry
129 * @param LP linked list pool
130 * @param name list anchor name
131 * @param E entry whose ll anchor is to be initialized
133 #define clib_llist_anchor_init(LP,name,E) \
135 _lprev ((E),name) = clib_llist_entry_index ((LP), (E)); \
136 _lnext ((E),name) = _lprev ((E),name); \
139 * Initialize llist head
141 * @param LP linked list pool
142 * @param name list anchor name
144 #define clib_llist_make_head(LP,name) \
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)); \
152 * Check is list is empty
154 * @param LP linked list pool
155 * @param name list anchor name
157 * @return 1 if sentinel is the only node part of the list, 0 otherwise
159 #define clib_llist_is_empty(LP,name,H) \
160 (clib_llist_entry_index (LP,H) == (H)->name.next)
162 * Check if element is linked in a list
164 * @param E list element
165 * @param name list anchor name
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)
171 * Insert entry between previous and next
175 * @param LP linked list pool
176 * @param name list anchor name
178 * @param P previous in list
179 * @param N next in list
181 #define _llist_insert(LP,name,E,P,N) \
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)); \
189 * Insert entry after previous
191 * @param LP linked list pool
192 * @param name list anchor name
194 * @param P previous in list
196 #define clib_llist_insert(LP,name,E,P) \
198 typeof (LP) _ll_var (N) = clib_llist_next (LP,name,P); \
199 _llist_insert ((LP),name,(E),(P), _ll_var (N)); \
203 * Add entry after head
205 * @param LP linked list pool
206 * @param name list anchor name
210 #define clib_llist_add(LP,name,E,H) clib_llist_insert ((LP),name,(E),(H))
212 * Add entry after tail
214 * @param LP linked list pool
215 * @param name list anchor name
219 #define clib_llist_add_tail(LP,name,E,H) \
221 typeof (LP) _ll_var (P) = clib_llist_prev ((LP),name,(H)); \
222 _llist_insert ((LP),name,(E),_ll_var (P),(H)); \
225 * Remove entry from list
227 * @param LP linked list pool
228 * @param name list anchor name
229 * @param E entry to be removed
231 #define clib_llist_remove(LP,name,E) \
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; \
243 * Removes and returns the first element in the list.
245 * The element is not freed. It's the responsability of the caller to
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
253 #define clib_llist_pop_first(LP,name,E,H) \
255 E = clib_llist_next (LP,name,H); \
256 clib_llist_remove (LP,name,E); \
259 * Splice two lists at a given position
261 * List spliced into destination list is left with 0 entries, i.e., head
262 * is made to point to itself.
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
269 #define clib_llist_splice(LP,name,P,H) \
271 typeof (LP) _ll_var (fe) = clib_llist_next (LP,name,H); \
272 if (_ll_var (fe) != (H)) \
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); \
285 * Walk list starting at head
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
293 #define clib_llist_foreach(LP,name,H,E,body) \
295 typeof (LP) _ll_var (n); \
296 (E) = clib_llist_next (LP,name,H); \
299 _ll_var (n) = clib_llist_next (LP,name,E); \
300 do { body; } while (0); \
305 * Walk list starting at head safe
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
313 #define clib_llist_foreach_safe(LP,name,H,E,body) \
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)) \
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); \
327 * Walk list starting at head in reverse order
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
335 #define clib_llist_foreach_reverse(LP,name,H,E,body) \
337 typeof (LP) _ll_var (p); \
338 (E) = clib_llist_prev (LP,name,H); \
341 _ll_var (p) = clib_llist_prev (LP,name,E); \
342 do { body; } while (0); \
347 #endif /* SRC_VPPINFRA_CLIB_LLIST_H_ */
350 * fd.io coding-style-patch-verification: ON
353 * eval: (c-set-style "gnu")