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))
55 * Get prev list entry index
58 * @name list anchor name
59 * @return previous index
61 #define clib_llist_prev_index(E,name) _lprev(E,name)
63 * Get next list entry index
66 * @name list anchor name
69 #define clib_llist_next_index(E,name) _lnext(E,name)
73 * @param LP linked list pool
74 * @param name list anchor name
76 * @return next pool entry
78 #define clib_llist_next(LP,name,E) pool_elt_at_index((LP),_lnext((E),name))
80 * Get previous pool entry
82 * @param LP linked list pool
83 * @param name list anchor name
85 * @return previous pool entry
87 #define clib_llist_prev(LP,name,E) pool_elt_at_index((LP),_lprev((E),name))
89 * Initialize element in llist for entry
91 * @param LP linked list pool
92 * @param name list anchor name
93 * @param E entry whose ll anchor is to be initialized
95 #define clib_llist_anchor_init(LP,name,E) \
97 _lprev ((E),name) = clib_llist_entry_index ((LP), (E)); \
98 _lnext ((E),name) = _lprev ((E),name); \
101 * Initialize llist head
103 * @param LP linked list pool
104 * @param name list anchor name
106 #define clib_llist_make_head(LP,name) \
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)); \
114 * Check is list is empty
116 * @param LP linked list pool
117 * @param name list anchor name
119 * @return 1 if sentinel is the only node part of the list, 0 otherwise
121 #define clib_llist_is_empty(LP,name,H) \
122 (clib_llist_entry_index (LP,H) == (H)->name.next)
124 * Check if element is linked in a list
126 * @param E list element
127 * @param name list anchor name
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)
133 * Insert entry between previous and next
137 * @param LP linked list pool
138 * @param name list anchor name
140 * @param P previous in list
141 * @param N next in list
143 #define _llist_insert(LP,name,E,P,N) \
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)); \
151 * Insert entry after previous
153 * @param LP linked list pool
154 * @param name list anchor name
156 * @param P previous in list
158 #define clib_llist_insert(LP,name,E,P) \
160 typeof (LP) _ll_var (N) = clib_llist_next (LP,name,P); \
161 _llist_insert ((LP),name,(E),(P), _ll_var (N)); \
165 * Add entry after head
167 * @param LP linked list pool
168 * @param name list anchor name
172 #define clib_llist_add(LP,name,E,H) clib_llist_insert ((LP),name,(E),(H))
174 * Add entry after tail
176 * @param LP linked list pool
177 * @param name list anchor name
181 #define clib_llist_add_tail(LP,name,E,H) \
183 typeof (LP) _ll_var (P) = clib_llist_prev ((LP),name,(H)); \
184 _llist_insert ((LP),name,(E),_ll_var (P),(H)); \
187 * Remove entry from list
189 * @param LP linked list pool
190 * @param name list anchor name
191 * @param E entry to be removed
193 #define clib_llist_remove(LP,name,E) \
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; \
205 * Removes and returns the first element in the list.
207 * The element is not freed. It's the responsability of the caller to
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
215 #define clib_llist_pop_first(LP,name,E,H) \
217 E = clib_llist_next (LP,name,H); \
218 clib_llist_remove (LP,name,E); \
221 * Splice two lists at a given position
223 * List spliced into destination list is left with 0 entries, i.e., head
224 * is made to point to itself.
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
231 #define clib_llist_splice(LP,name,P,H) \
233 typeof (LP) _ll_var (fe) = clib_llist_next (LP,name,H); \
234 if (_ll_var (fe) != (H)) \
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); \
247 * Walk list starting at head
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
255 #define clib_llist_foreach(LP,name,H,E,body) \
257 typeof (LP) _ll_var (n); \
258 (E) = clib_llist_next (LP,name,H); \
261 _ll_var (n) = clib_llist_next (LP,name,E); \
262 do { body; } while (0); \
267 * Walk list starting at head safe
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
275 #define clib_llist_foreach_safe(LP,name,H,E,body) \
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)) \
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); \
289 * Walk list starting at head in reverse order
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
297 #define clib_llist_foreach_reverse(LP,name,H,E,body) \
299 typeof (LP) _ll_var (p); \
300 (E) = clib_llist_prev (LP,name,H); \
303 _ll_var (p) = clib_llist_prev (LP,name,E); \
304 do { body; } while (0); \
309 #endif /* SRC_VPPINFRA_CLIB_LLIST_H_ */
312 * fd.io coding-style-patch-verification: ON
315 * eval: (c-set-style "gnu")