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:
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 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}.
21 #include <vnet/fib/fib_node_list.h>
24 * @brief An element in the list
26 typedef struct fib_node_list_elt_t_
29 * The index of the list this element is in
31 fib_node_list_t fnle_list;
34 * The owner of this element
36 fib_node_ptr_t fnle_owner;
39 * The next element in the list
44 * The previous element in the list
47 } fib_node_list_elt_t;
50 * @brief A list of FIB nodes
52 typedef struct fib_node_list_head_t_
60 * Number of elements in the list
63 } fib_node_list_head_t;
66 * Pools of list elements and heads
68 static fib_node_list_elt_t *fib_node_list_elt_pool;
69 static fib_node_list_head_t *fib_node_list_head_pool;
72 fib_node_list_elt_get_index (fib_node_list_elt_t *elt)
74 return (elt - fib_node_list_elt_pool);
77 static fib_node_list_elt_t *
78 fib_node_list_elt_get (index_t fi)
80 return (pool_elt_at_index(fib_node_list_elt_pool, fi));
84 fib_node_list_head_get_index (fib_node_list_head_t *head)
86 return (head - fib_node_list_head_pool);
88 static fib_node_list_head_t *
89 fib_node_list_head_get (fib_node_list_t fi)
91 return (pool_elt_at_index(fib_node_list_head_pool, fi));
94 static fib_node_list_elt_t *
95 fib_node_list_elt_create (fib_node_list_head_t *head,
98 fib_node_index_t index)
100 fib_node_list_elt_t *elt;
102 pool_get(fib_node_list_elt_pool, elt);
104 elt->fnle_list = fib_node_list_head_get_index(head);
105 elt->fnle_owner.fnp_type = type;
106 elt->fnle_owner.fnp_index = index;
108 elt->fnle_next = FIB_NODE_INDEX_INVALID;
109 elt->fnle_prev = FIB_NODE_INDEX_INVALID;
115 fib_node_list_head_init (fib_node_list_head_t *head)
117 head->fnlh_n_elts = 0;
118 head->fnlh_head = FIB_NODE_INDEX_INVALID;
122 * @brief Create a new node list.
125 fib_node_list_create (void)
127 fib_node_list_head_t *head;
129 pool_get(fib_node_list_head_pool, head);
131 fib_node_list_head_init(head);
133 return (fib_node_list_head_get_index(head));
137 fib_node_list_destroy (fib_node_list_t *list)
139 fib_node_list_head_t *head;
141 if (FIB_NODE_INDEX_INVALID == *list)
144 head = fib_node_list_head_get(*list);
145 ASSERT(0 == head->fnlh_n_elts);
147 pool_put(fib_node_list_head_pool, head);
148 *list = FIB_NODE_INDEX_INVALID;
153 * @brief Insert an element at the from of the list.
156 fib_node_list_push_front (fib_node_list_t list,
158 fib_node_type_t type,
159 fib_node_index_t index)
161 fib_node_list_elt_t *elt, *next;
162 fib_node_list_head_t *head;
164 head = fib_node_list_head_get(list);
165 elt = fib_node_list_elt_create(head, owner_id, type, index);
167 elt->fnle_prev = FIB_NODE_INDEX_INVALID;
168 elt->fnle_next = head->fnlh_head;
170 if (FIB_NODE_INDEX_INVALID != head->fnlh_head)
172 next = fib_node_list_elt_get(head->fnlh_head);
173 next->fnle_prev = fib_node_list_elt_get_index(elt);
175 head->fnlh_head = fib_node_list_elt_get_index(elt);
179 return (fib_node_list_elt_get_index(elt));
183 fib_node_list_push_back (fib_node_list_t list,
185 fib_node_type_t type,
186 fib_node_index_t index)
189 return (FIB_NODE_INDEX_INVALID);
193 fib_node_list_extract (fib_node_list_head_t *head,
194 fib_node_list_elt_t *elt)
196 fib_node_list_elt_t *next, *prev;
198 if (FIB_NODE_INDEX_INVALID != elt->fnle_next)
200 next = fib_node_list_elt_get(elt->fnle_next);
201 next->fnle_prev = elt->fnle_prev;
204 if (FIB_NODE_INDEX_INVALID != elt->fnle_prev)
206 prev = fib_node_list_elt_get(elt->fnle_prev);
207 prev->fnle_next = elt->fnle_next;
211 ASSERT (fib_node_list_elt_get_index(elt) == head->fnlh_head);
212 head->fnlh_head = elt->fnle_next;
217 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)
221 fib_node_list_elt_t *next;
223 elt->fnle_next = prev->fnle_next;
224 if (FIB_NODE_INDEX_INVALID != prev->fnle_next)
226 next = fib_node_list_elt_get(prev->fnle_next);
227 next->fnle_prev = fib_node_list_elt_get_index(elt);
229 prev->fnle_next = fib_node_list_elt_get_index(elt);
230 elt->fnle_prev = fib_node_list_elt_get_index(prev);
234 fib_node_list_remove (fib_node_list_t list,
237 fib_node_list_head_t *head;
238 fib_node_list_elt_t *elt;
240 head = fib_node_list_head_get(list);
241 elt = fib_node_list_elt_get(sibling);
243 fib_node_list_extract(head, elt);
246 pool_put(fib_node_list_elt_pool, elt);
250 fib_node_list_elt_remove (u32 sibling)
252 fib_node_list_elt_t *elt;
254 elt = fib_node_list_elt_get(sibling);
256 fib_node_list_remove(elt->fnle_list, sibling);
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.
264 fib_node_list_advance (u32 sibling)
266 fib_node_list_elt_t *elt, *next;
267 fib_node_list_head_t *head;
269 elt = fib_node_list_elt_get(sibling);
270 head = fib_node_list_head_get(elt->fnle_list);
272 if (FIB_NODE_INDEX_INVALID != elt->fnle_next)
275 * not at the end of the list
277 next = fib_node_list_elt_get(elt->fnle_next);
279 fib_node_list_extract(head, elt);
280 fib_node_list_insert_after(head, next, elt);
291 fib_node_list_elt_get_next (u32 sibling,
294 fib_node_list_elt_t *elt, *next;
296 elt = fib_node_list_elt_get(sibling);
298 if (FIB_NODE_INDEX_INVALID != elt->fnle_next)
300 next = fib_node_list_elt_get(elt->fnle_next);
302 *ptr = next->fnle_owner;
307 ptr->fnp_index = FIB_NODE_INDEX_INVALID;
313 fib_node_list_get_size (fib_node_list_t list)
315 fib_node_list_head_t *head;
317 if (FIB_NODE_INDEX_INVALID == list)
322 head = fib_node_list_head_get(list);
324 return (head->fnlh_n_elts);
328 fib_node_list_get_front (fib_node_list_t list,
331 fib_node_list_head_t *head;
332 fib_node_list_elt_t *elt;
335 if (0 == fib_node_list_get_size(list))
337 ptr->fnp_index = FIB_NODE_INDEX_INVALID;
341 head = fib_node_list_head_get(list);
342 elt = fib_node_list_elt_get(head->fnlh_head);
344 *ptr = elt->fnle_owner;
350 * @brief Walk the list of node. This must be safe w.r.t. the removal
351 * of nodes during the walk.
354 fib_node_list_walk (fib_node_list_t list,
355 fib_node_list_walk_cb_t fn,
358 fib_node_list_elt_t *elt;
359 fib_node_list_head_t *head;
362 if (FIB_NODE_INDEX_INVALID == list)
367 head = fib_node_list_head_get(list);
368 sibling = head->fnlh_head;
370 while (FIB_NODE_INDEX_INVALID != sibling)
372 elt = fib_node_list_elt_get(sibling);
373 sibling = elt->fnle_next;
375 fn(&elt->fnle_owner, args);
380 fib_node_list_memory_show (void)
382 fib_show_memory_usage("Node-list elements",
383 pool_elts(fib_node_list_elt_pool),
384 pool_len(fib_node_list_elt_pool),
385 sizeof(fib_node_list_elt_t));
386 fib_show_memory_usage("Node-list heads",
387 pool_elts(fib_node_list_head_pool),
388 pool_len(fib_node_list_head_pool),
389 sizeof(fib_node_list_head_t));