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 name list anchor name
60 * @return next pool entry
62 #define clib_llist_next(LP,name,E) pool_elt_at_index((LP),_lnext((E),name))
64 * Get previous pool entry
66 * @param LP linked list pool
67 * @param name list anchor name
69 * @return previous pool entry
71 #define clib_llist_prev(LP,name,E) pool_elt_at_index((LP),_lprev((E),name))
73 * Initialize element in llist for entry
75 * @param LP linked list pool
76 * @param name list anchor name
77 * @param E entry whose ll anchor is to be initialized
79 #define clib_llist_anchor_init(LP,name,E) \
81 _lprev ((E),name) = clib_llist_entry_index ((LP), (E)); \
82 _lnext ((E),name) = _lprev ((E),name); \
85 * Initialize llist head
87 * @param LP linked list pool
88 * @param name list anchor name
90 #define clib_llist_make_head(LP,name) \
92 typeof (LP) _ll_var (head); \
93 pool_get_zero ((LP), _ll_var (head)); \
94 clib_llist_anchor_init ((LP),name,_ll_var (head)); \
95 clib_llist_entry_index ((LP), _ll_var (head)); \
98 * Check is list is empty
100 * @param LP linked list pool
101 * @param name list anchor name
103 * @return 1 if sentinel is the only node part of the list, 0 otherwise
105 #define clib_llist_is_empty(LP,name,H) \
106 (clib_llist_entry_index (LP,H) == (H)->name.next)
108 * Check if element is linked in a list
110 * @param E list element
111 * @param name list anchor name
113 #define clib_llist_elt_is_linked(E,name) \
114 ((E)->name.next != CLIB_LLIST_INVALID_INDEX \
115 && (E)->name.prev != CLIB_LLIST_INVALID_INDEX)
117 * Insert entry between previous and next
121 * @param LP linked list pool
122 * @param name list anchor name
124 * @param P previous in list
125 * @param N next in list
127 #define _llist_insert(LP,name,E,P,N) \
129 _lprev (E,name) = _lprev(N,name); \
130 _lnext (E,name) = _lnext(P,name); \
131 _lprev ((N),name) = clib_llist_entry_index ((LP),(E)); \
132 _lnext ((P),name) = clib_llist_entry_index ((LP),(E)); \
135 * Insert entry after previous
137 * @param LP linked list pool
138 * @param name list anchor name
140 * @param P previous in list
142 #define clib_llist_insert(LP,name,E,P) \
144 typeof (LP) _ll_var (N) = clib_llist_next (LP,name,P); \
145 _llist_insert ((LP),name,(E),(P), _ll_var (N)); \
149 * Add entry after head
151 * @param LP linked list pool
152 * @param name list anchor name
156 #define clib_llist_add(LP,name,E,H) clib_llist_insert ((LP),name,(E),(H))
158 * Add entry after tail
160 * @param LP linked list pool
161 * @param name list anchor name
165 #define clib_llist_add_tail(LP,name,E,H) \
167 typeof (LP) _ll_var (P) = clib_llist_prev ((LP),name,(H)); \
168 _llist_insert ((LP),name,(E),_ll_var (P),(H)); \
171 * Remove entry from list
173 * @param LP linked list pool
174 * @param name list anchor name
175 * @param E entry to be removed
177 #define clib_llist_remove(LP,name,E) \
179 ASSERT ((E) != clib_llist_next (LP,name,E));/* don't remove sentinel */\
180 ASSERT (_lnext (E,name) != CLIB_LLIST_INVALID_INDEX); \
181 ASSERT (_lprev (E,name) != CLIB_LLIST_INVALID_INDEX); \
182 typeof (LP) _ll_var (P) = clib_llist_prev ((LP),name,E); \
183 typeof (LP) _ll_var (N) = clib_llist_next ((LP),name,E); \
184 _lnext (_ll_var (P),name) = _lnext (E,name); \
185 _lprev (_ll_var (N),name) = _lprev (E,name); \
186 _lnext (E,name) = _lprev (E,name) = CLIB_LLIST_INVALID_INDEX; \
189 * Removes and returns the first element in the list.
191 * The element is not freed. It's the responsability of the caller to
194 * @param LP linked list pool
195 * @param name list anchor name
196 * @param E storage the first entry
197 * @param H list head entry
199 #define clib_llist_pop_first(LP,name,E,H) \
201 E = clib_llist_next (LP,name,H); \
202 clib_llist_remove (LP,name,E); \
205 * Splice two lists at a given position
207 * List spliced into destination list is left with 0 entries, i.e., head
208 * is made to point to itself.
210 * @param LP linked list pool
211 * @param name list anchor name
212 * @param P position in destination where source list is spliced
213 * @param H head of source list that will be spliced into destination
215 #define clib_llist_splice(LP,name,P,H) \
217 typeof (LP) _ll_var (fe) = clib_llist_next (LP,name,H); \
218 if (_ll_var (fe) != (H)) \
220 typeof (LP) _ll_var (le) = clib_llist_prev (LP,name,H); \
221 typeof (LP) _ll_var (ne) = clib_llist_next (LP,name,P); \
222 _lprev (_ll_var (fe),name) = clib_llist_entry_index(LP,P); \
223 _lnext (_ll_var (le),name) = clib_llist_entry_index(LP,_ll_var (ne));\
224 _lnext (P,name) = clib_llist_entry_index (LP,_ll_var (fe)); \
225 _lprev (_ll_var (ne),name) = clib_llist_entry_index(LP,_ll_var (le));\
226 _lnext (H,name) = clib_llist_entry_index(LP,H); \
227 _lprev (H,name) = _lnext (H,name); \
231 * Walk list starting at head
233 * @param LP linked list pool
234 * @param name list anchor name
235 * @param H head entry
236 * @param E entry iterator
237 * @param body code to be executed
239 #define clib_llist_foreach(LP,name,H,E,body) \
241 typeof (LP) _ll_var (n); \
242 (E) = clib_llist_next (LP,name,H); \
245 _ll_var (n) = clib_llist_next (LP,name,E); \
246 do { body; } while (0); \
251 * Walk list starting at head in reverse order
253 * @param LP linked list pool
254 * @param name list anchor name
255 * @param H head entry
256 * @param E entry iterator
257 * @param body code to be executed
259 #define clib_llist_foreach_reverse(LP,name,H,E,body) \
261 typeof (LP) _ll_var (p); \
262 (E) = clib_llist_prev (LP,name,H); \
265 _ll_var (p) = clib_llist_prev (LP,name,E); \
266 do { body; } while (0); \
271 #endif /* SRC_VPPINFRA_CLIB_LLIST_H_ */
274 * fd.io coding-style-patch-verification: ON
277 * eval: (c-set-style "gnu")