Line data Source code
1 : /*
2 : * Copyright (c) 2016 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 : /**
16 : * @brief a hetrogeneous w.r.t. FIB node type, of FIB nodes.
17 : * Since we cannot use C pointers, due to memeory reallocs, the next/prev
18 : * are described as key:{type,index}.
19 : */
20 :
21 : #include <vnet/fib/fib_node_list.h>
22 :
23 : /**
24 : * @brief An element in the list
25 : */
26 : typedef struct fib_node_list_elt_t_
27 : {
28 : /**
29 : * The index of the list this element is in
30 : */
31 : fib_node_list_t fnle_list;
32 :
33 : /**
34 : * The owner of this element
35 : */
36 : fib_node_ptr_t fnle_owner;
37 :
38 : /**
39 : * The next element in the list
40 : */
41 : u32 fnle_next;
42 :
43 : /**
44 : * The previous element in the list
45 : */
46 : u32 fnle_prev;
47 : } fib_node_list_elt_t;
48 :
49 : /**
50 : * @brief A list of FIB nodes
51 : */
52 : typedef struct fib_node_list_head_t_
53 : {
54 : /**
55 : * The head element
56 : */
57 : u32 fnlh_head;
58 :
59 : /**
60 : * Number of elements in the list
61 : */
62 : u32 fnlh_n_elts;
63 : } fib_node_list_head_t;
64 :
65 : /**
66 : * Pools of list elements and heads
67 : */
68 : static fib_node_list_elt_t *fib_node_list_elt_pool;
69 : static fib_node_list_head_t *fib_node_list_head_pool;
70 :
71 : static index_t
72 927796 : fib_node_list_elt_get_index (fib_node_list_elt_t *elt)
73 : {
74 927796 : return (elt - fib_node_list_elt_pool);
75 : }
76 :
77 : static fib_node_list_elt_t *
78 906165 : fib_node_list_elt_get (index_t fi)
79 : {
80 906165 : return (pool_elt_at_index(fib_node_list_elt_pool, fi));
81 : }
82 :
83 : static index_t
84 387945 : fib_node_list_head_get_index (fib_node_list_head_t *head)
85 : {
86 387945 : return (head - fib_node_list_head_pool);
87 : }
88 : static fib_node_list_head_t *
89 988640 : fib_node_list_head_get (fib_node_list_t fi)
90 : {
91 988640 : return (pool_elt_at_index(fib_node_list_head_pool, fi));
92 : }
93 :
94 : static fib_node_list_elt_t *
95 249934 : fib_node_list_elt_create (fib_node_list_head_t *head,
96 : int id,
97 : fib_node_type_t type,
98 : fib_node_index_t index)
99 : {
100 : fib_node_list_elt_t *elt;
101 :
102 249934 : pool_get(fib_node_list_elt_pool, elt);
103 :
104 249934 : elt->fnle_list = fib_node_list_head_get_index(head);
105 249934 : elt->fnle_owner.fnp_type = type;
106 249934 : elt->fnle_owner.fnp_index = index;
107 :
108 249934 : elt->fnle_next = FIB_NODE_INDEX_INVALID;
109 249934 : elt->fnle_prev = FIB_NODE_INDEX_INVALID;
110 :
111 249934 : return (elt);
112 : }
113 :
114 : static void
115 138011 : fib_node_list_head_init (fib_node_list_head_t *head)
116 : {
117 138011 : head->fnlh_n_elts = 0;
118 138011 : head->fnlh_head = FIB_NODE_INDEX_INVALID;
119 138011 : }
120 :
121 : /**
122 : * @brief Create a new node list.
123 : */
124 : fib_node_list_t
125 138011 : fib_node_list_create (void)
126 : {
127 : fib_node_list_head_t *head;
128 :
129 138011 : pool_get(fib_node_list_head_pool, head);
130 :
131 138011 : fib_node_list_head_init(head);
132 :
133 138011 : return (fib_node_list_head_get_index(head));
134 : }
135 :
136 : void
137 374224 : fib_node_list_destroy (fib_node_list_t *list)
138 : {
139 : fib_node_list_head_t *head;
140 :
141 374224 : if (FIB_NODE_INDEX_INVALID == *list)
142 256168 : return;
143 :
144 118056 : head = fib_node_list_head_get(*list);
145 118056 : ASSERT(0 == head->fnlh_n_elts);
146 :
147 118056 : pool_put(fib_node_list_head_pool, head);
148 118056 : *list = FIB_NODE_INDEX_INVALID;
149 : }
150 :
151 :
152 : /**
153 : * @brief Insert an element at the from of the list.
154 : */
155 : u32
156 249934 : fib_node_list_push_front (fib_node_list_t list,
157 : int owner_id,
158 : fib_node_type_t type,
159 : fib_node_index_t index)
160 : {
161 : fib_node_list_elt_t *elt, *next;
162 : fib_node_list_head_t *head;
163 :
164 249934 : head = fib_node_list_head_get(list);
165 249934 : elt = fib_node_list_elt_create(head, owner_id, type, index);
166 :
167 249934 : elt->fnle_prev = FIB_NODE_INDEX_INVALID;
168 249934 : elt->fnle_next = head->fnlh_head;
169 :
170 249934 : if (FIB_NODE_INDEX_INVALID != head->fnlh_head)
171 : {
172 112916 : next = fib_node_list_elt_get(head->fnlh_head);
173 112916 : next->fnle_prev = fib_node_list_elt_get_index(elt);
174 : }
175 249934 : head->fnlh_head = fib_node_list_elt_get_index(elt);
176 :
177 249934 : head->fnlh_n_elts++;
178 :
179 249934 : return (fib_node_list_elt_get_index(elt));
180 : }
181 :
182 : u32
183 0 : fib_node_list_push_back (fib_node_list_t list,
184 : int owner_id,
185 : fib_node_type_t type,
186 : fib_node_index_t index)
187 : {
188 0 : ASSERT(0);
189 0 : return (FIB_NODE_INDEX_INVALID);
190 : }
191 :
192 : static void
193 288781 : fib_node_list_extract (fib_node_list_head_t *head,
194 : fib_node_list_elt_t *elt)
195 : {
196 : fib_node_list_elt_t *next, *prev;
197 :
198 288781 : if (FIB_NODE_INDEX_INVALID != elt->fnle_next)
199 : {
200 77060 : next = fib_node_list_elt_get(elt->fnle_next);
201 77060 : next->fnle_prev = elt->fnle_prev;
202 : }
203 :
204 288781 : if (FIB_NODE_INDEX_INVALID != elt->fnle_prev)
205 : {
206 121852 : prev = fib_node_list_elt_get(elt->fnle_prev);
207 121852 : prev->fnle_next = elt->fnle_next;
208 : }
209 : else
210 : {
211 166929 : ASSERT (fib_node_list_elt_get_index(elt) == head->fnlh_head);
212 166929 : head->fnlh_head = elt->fnle_next;
213 : }
214 288781 : }
215 :
216 : static void
217 62568 : fib_node_list_insert_after (fib_node_list_head_t *head,
218 : fib_node_list_elt_t *prev,
219 : fib_node_list_elt_t *elt)
220 : {
221 : fib_node_list_elt_t *next;
222 :
223 62568 : elt->fnle_next = prev->fnle_next;
224 62568 : if (FIB_NODE_INDEX_INVALID != prev->fnle_next)
225 : {
226 22947 : next = fib_node_list_elt_get(prev->fnle_next);
227 22947 : next->fnle_prev = fib_node_list_elt_get_index(elt);
228 : }
229 62568 : prev->fnle_next = fib_node_list_elt_get_index(elt);
230 62568 : elt->fnle_prev = fib_node_list_elt_get_index(prev);
231 62568 : }
232 :
233 : void
234 226213 : fib_node_list_remove (fib_node_list_t list,
235 : u32 sibling)
236 : {
237 : fib_node_list_head_t *head;
238 : fib_node_list_elt_t *elt;
239 :
240 226213 : head = fib_node_list_head_get(list);
241 226213 : elt = fib_node_list_elt_get(sibling);
242 :
243 226213 : fib_node_list_extract(head, elt);
244 :
245 226213 : head->fnlh_n_elts--;
246 226213 : pool_put(fib_node_list_elt_pool, elt);
247 226213 : }
248 :
249 : void
250 189 : fib_node_list_elt_remove (u32 sibling)
251 : {
252 : fib_node_list_elt_t *elt;
253 :
254 189 : elt = fib_node_list_elt_get(sibling);
255 :
256 189 : fib_node_list_remove(elt->fnle_list, sibling);
257 189 : }
258 :
259 : /**
260 : * @brief Advance the sibling one step (toward the tail) in the list.
261 : * return 0 if at the end of the list, 1 otherwise.
262 : */
263 : int
264 78524 : fib_node_list_advance (u32 sibling)
265 : {
266 : fib_node_list_elt_t *elt, *next;
267 : fib_node_list_head_t *head;
268 :
269 78524 : elt = fib_node_list_elt_get(sibling);
270 78524 : head = fib_node_list_head_get(elt->fnle_list);
271 :
272 78524 : if (FIB_NODE_INDEX_INVALID != elt->fnle_next)
273 : {
274 : /*
275 : * not at the end of the list
276 : */
277 62568 : next = fib_node_list_elt_get(elt->fnle_next);
278 :
279 62568 : fib_node_list_extract(head, elt);
280 62568 : fib_node_list_insert_after(head, next, elt);
281 :
282 62568 : return (1);
283 : }
284 : else
285 : {
286 15956 : return (0);
287 : }
288 : }
289 :
290 : int
291 118215 : fib_node_list_elt_get_next (u32 sibling,
292 : fib_node_ptr_t *ptr)
293 : {
294 : fib_node_list_elt_t *elt, *next;
295 :
296 118215 : elt = fib_node_list_elt_get(sibling);
297 :
298 118215 : if (FIB_NODE_INDEX_INVALID != elt->fnle_next)
299 : {
300 78592 : next = fib_node_list_elt_get(elt->fnle_next);
301 :
302 78592 : *ptr = next->fnle_owner;
303 78592 : return (1);
304 : }
305 : else
306 : {
307 39623 : ptr->fnp_index = FIB_NODE_INDEX_INVALID;
308 39623 : return (0);
309 : }
310 : }
311 :
312 : u32
313 572439 : fib_node_list_get_size (fib_node_list_t list)
314 : {
315 : fib_node_list_head_t *head;
316 :
317 572439 : if (FIB_NODE_INDEX_INVALID == list)
318 : {
319 261616 : return (0);
320 : }
321 :
322 310823 : head = fib_node_list_head_get(list);
323 :
324 310823 : return (head->fnlh_n_elts);
325 : }
326 :
327 : int
328 544 : fib_node_list_get_front (fib_node_list_t list,
329 : fib_node_ptr_t *ptr)
330 : {
331 : fib_node_list_head_t *head;
332 : fib_node_list_elt_t *elt;
333 :
334 :
335 544 : if (0 == fib_node_list_get_size(list))
336 : {
337 2 : ptr->fnp_index = FIB_NODE_INDEX_INVALID;
338 2 : return (0);
339 : }
340 :
341 542 : head = fib_node_list_head_get(list);
342 542 : elt = fib_node_list_elt_get(head->fnlh_head);
343 :
344 542 : *ptr = elt->fnle_owner;
345 :
346 542 : return (1);
347 : }
348 :
349 : /**
350 : * @brief Walk the list of node. This must be safe w.r.t. the removal
351 : * of nodes during the walk.
352 : */
353 : void
354 4550 : fib_node_list_walk (fib_node_list_t list,
355 : fib_node_list_walk_cb_t fn,
356 : void *args)
357 : {
358 : fib_node_list_elt_t *elt;
359 : fib_node_list_head_t *head;
360 : u32 sibling;
361 :
362 4550 : if (FIB_NODE_INDEX_INVALID == list)
363 : {
364 2 : return;
365 : }
366 :
367 4548 : head = fib_node_list_head_get(list);
368 4548 : sibling = head->fnlh_head;
369 :
370 11095 : while (FIB_NODE_INDEX_INVALID != sibling)
371 : {
372 6547 : elt = fib_node_list_elt_get(sibling);
373 6547 : sibling = elt->fnle_next;
374 :
375 6547 : if (WALK_STOP == fn(&elt->fnle_owner, args))
376 0 : break;
377 : }
378 : }
379 :
380 : void
381 1 : fib_node_list_memory_show (void)
382 : {
383 1 : fib_show_memory_usage("Node-list elements",
384 1 : pool_elts(fib_node_list_elt_pool),
385 1 : pool_len(fib_node_list_elt_pool),
386 : sizeof(fib_node_list_elt_t));
387 1 : fib_show_memory_usage("Node-list heads",
388 1 : pool_elts(fib_node_list_head_pool),
389 1 : pool_len(fib_node_list_head_pool),
390 : sizeof(fib_node_list_head_t));
391 1 : }
|
