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 945976 : fib_node_list_elt_get_index (fib_node_list_elt_t *elt)
73 : {
74 945976 : return (elt - fib_node_list_elt_pool);
75 : }
76 :
77 : static fib_node_list_elt_t *
78 930023 : fib_node_list_elt_get (index_t fi)
79 : {
80 930023 : return (pool_elt_at_index(fib_node_list_elt_pool, fi));
81 : }
82 :
83 : static index_t
84 393787 : fib_node_list_head_get_index (fib_node_list_head_t *head)
85 : {
86 393787 : return (head - fib_node_list_head_pool);
87 : }
88 : static fib_node_list_head_t *
89 1005150 : fib_node_list_head_get (fib_node_list_t fi)
90 : {
91 1005150 : return (pool_elt_at_index(fib_node_list_head_pool, fi));
92 : }
93 :
94 : static fib_node_list_elt_t *
95 254169 : 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 254169 : pool_get(fib_node_list_elt_pool, elt);
103 :
104 254169 : elt->fnle_list = fib_node_list_head_get_index(head);
105 254169 : elt->fnle_owner.fnp_type = type;
106 254169 : elt->fnle_owner.fnp_index = index;
107 :
108 254169 : elt->fnle_next = FIB_NODE_INDEX_INVALID;
109 254169 : elt->fnle_prev = FIB_NODE_INDEX_INVALID;
110 :
111 254169 : return (elt);
112 : }
113 :
114 : static void
115 139618 : fib_node_list_head_init (fib_node_list_head_t *head)
116 : {
117 139618 : head->fnlh_n_elts = 0;
118 139618 : head->fnlh_head = FIB_NODE_INDEX_INVALID;
119 139618 : }
120 :
121 : /**
122 : * @brief Create a new node list.
123 : */
124 : fib_node_list_t
125 139618 : fib_node_list_create (void)
126 : {
127 : fib_node_list_head_t *head;
128 :
129 139618 : pool_get(fib_node_list_head_pool, head);
130 :
131 139618 : fib_node_list_head_init(head);
132 :
133 139618 : return (fib_node_list_head_get_index(head));
134 : }
135 :
136 : void
137 378375 : fib_node_list_destroy (fib_node_list_t *list)
138 : {
139 : fib_node_list_head_t *head;
140 :
141 378375 : if (FIB_NODE_INDEX_INVALID == *list)
142 258690 : return;
143 :
144 119685 : head = fib_node_list_head_get(*list);
145 119685 : ASSERT(0 == head->fnlh_n_elts);
146 :
147 119685 : pool_put(fib_node_list_head_pool, head);
148 119685 : *list = FIB_NODE_INDEX_INVALID;
149 : }
150 :
151 :
152 : /**
153 : * @brief Insert an element at the from of the list.
154 : */
155 : u32
156 254169 : 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 254169 : head = fib_node_list_head_get(list);
165 254169 : elt = fib_node_list_elt_create(head, owner_id, type, index);
166 :
167 254169 : elt->fnle_prev = FIB_NODE_INDEX_INVALID;
168 254169 : elt->fnle_next = head->fnlh_head;
169 :
170 254169 : if (FIB_NODE_INDEX_INVALID != head->fnlh_head)
171 : {
172 115576 : next = fib_node_list_elt_get(head->fnlh_head);
173 115576 : next->fnle_prev = fib_node_list_elt_get_index(elt);
174 : }
175 254169 : head->fnlh_head = fib_node_list_elt_get_index(elt);
176 :
177 254169 : head->fnlh_n_elts++;
178 :
179 254169 : 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 294634 : 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 294634 : if (FIB_NODE_INDEX_INVALID != elt->fnle_next)
199 : {
200 79073 : next = fib_node_list_elt_get(elt->fnle_next);
201 79073 : next->fnle_prev = elt->fnle_prev;
202 : }
203 :
204 294634 : if (FIB_NODE_INDEX_INVALID != elt->fnle_prev)
205 : {
206 127125 : prev = fib_node_list_elt_get(elt->fnle_prev);
207 127125 : prev->fnle_next = elt->fnle_next;
208 : }
209 : else
210 : {
211 167509 : ASSERT (fib_node_list_elt_get_index(elt) == head->fnlh_head);
212 167509 : head->fnlh_head = elt->fnle_next;
213 : }
214 294634 : }
215 :
216 : static void
217 64290 : 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 64290 : elt->fnle_next = prev->fnle_next;
224 64290 : if (FIB_NODE_INDEX_INVALID != prev->fnle_next)
225 : {
226 25973 : next = fib_node_list_elt_get(prev->fnle_next);
227 25973 : next->fnle_prev = fib_node_list_elt_get_index(elt);
228 : }
229 64290 : prev->fnle_next = fib_node_list_elt_get_index(elt);
230 64290 : elt->fnle_prev = fib_node_list_elt_get_index(prev);
231 64290 : }
232 :
233 : void
234 230344 : 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 230344 : head = fib_node_list_head_get(list);
241 230344 : elt = fib_node_list_elt_get(sibling);
242 :
243 230344 : fib_node_list_extract(head, elt);
244 :
245 230344 : head->fnlh_n_elts--;
246 230344 : pool_put(fib_node_list_elt_pool, elt);
247 230344 : }
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 80979 : fib_node_list_advance (u32 sibling)
265 : {
266 : fib_node_list_elt_t *elt, *next;
267 : fib_node_list_head_t *head;
268 :
269 80979 : elt = fib_node_list_elt_get(sibling);
270 80979 : head = fib_node_list_head_get(elt->fnle_list);
271 :
272 80979 : if (FIB_NODE_INDEX_INVALID != elt->fnle_next)
273 : {
274 : /*
275 : * not at the end of the list
276 : */
277 64290 : next = fib_node_list_elt_get(elt->fnle_next);
278 :
279 64290 : fib_node_list_extract(head, elt);
280 64290 : fib_node_list_insert_after(head, next, elt);
281 :
282 64290 : return (1);
283 : }
284 : else
285 : {
286 16689 : return (0);
287 : }
288 : }
289 :
290 : int
291 119366 : 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 119366 : elt = fib_node_list_elt_get(sibling);
297 :
298 119366 : if (FIB_NODE_INDEX_INVALID != elt->fnle_next)
299 : {
300 81047 : next = fib_node_list_elt_get(elt->fnle_next);
301 :
302 81047 : *ptr = next->fnle_owner;
303 81047 : return (1);
304 : }
305 : else
306 : {
307 38319 : ptr->fnp_index = FIB_NODE_INDEX_INVALID;
308 38319 : return (0);
309 : }
310 : }
311 :
312 : u32
313 581707 : fib_node_list_get_size (fib_node_list_t list)
314 : {
315 : fib_node_list_head_t *head;
316 :
317 581707 : if (FIB_NODE_INDEX_INVALID == list)
318 : {
319 266231 : return (0);
320 : }
321 :
322 315476 : head = fib_node_list_head_get(list);
323 :
324 315476 : return (head->fnlh_n_elts);
325 : }
326 :
327 : int
328 480 : 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 480 : 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 478 : head = fib_node_list_head_get(list);
342 478 : elt = fib_node_list_elt_get(head->fnlh_head);
343 :
344 478 : *ptr = elt->fnle_owner;
345 :
346 478 : 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 4022 : 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 4022 : if (FIB_NODE_INDEX_INVALID == list)
363 : {
364 2 : return;
365 : }
366 :
367 4020 : head = fib_node_list_head_get(list);
368 4020 : sibling = head->fnlh_head;
369 :
370 9603 : while (FIB_NODE_INDEX_INVALID != sibling)
371 : {
372 5583 : elt = fib_node_list_elt_get(sibling);
373 5583 : sibling = elt->fnle_next;
374 :
375 5583 : 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 : }
|
