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 * An opaque indentifier set by the FIB node owning this element
30 * that will allow the owner to identify which element it is.
35 * The index of the list this element is in
37 fib_node_list_t fnle_list;
40 * The owner of this element
42 fib_node_ptr_t fnle_owner;
45 * The next element in the list
50 * The previous element in the list
53 } fib_node_list_elt_t;
56 * @brief A list of FIB nodes
58 typedef struct fib_node_list_head_t_
66 * Number of elements in the list
69 } fib_node_list_head_t;
72 * Pools of list elements and heads
74 static fib_node_list_elt_t *fib_node_list_elt_pool;
75 static fib_node_list_head_t *fib_node_list_head_pool;
78 fib_node_list_elt_get_index (fib_node_list_elt_t *elt)
80 return (elt - fib_node_list_elt_pool);
83 static fib_node_list_elt_t *
84 fib_node_list_elt_get (index_t fi)
86 return (pool_elt_at_index(fib_node_list_elt_pool, fi));
90 fib_node_list_head_get_index (fib_node_list_head_t *head)
92 return (head - fib_node_list_head_pool);
94 static fib_node_list_head_t *
95 fib_node_list_head_get (fib_node_list_t fi)
97 return (pool_elt_at_index(fib_node_list_head_pool, fi));
100 static fib_node_list_elt_t *
101 fib_node_list_elt_create (fib_node_list_head_t *head,
103 fib_node_type_t type,
104 fib_node_index_t index)
106 fib_node_list_elt_t *elt;
108 pool_get(fib_node_list_elt_pool, elt);
110 elt->fnle_list = fib_node_list_head_get_index(head);
111 elt->fnle_owner_id = id;
112 elt->fnle_owner.fnp_type = type;
113 elt->fnle_owner.fnp_index = index;
115 elt->fnle_next = FIB_NODE_INDEX_INVALID;
116 elt->fnle_prev = FIB_NODE_INDEX_INVALID;
122 fib_node_list_head_init (fib_node_list_head_t *head)
124 head->fnlh_n_elts = 0;
125 head->fnlh_head = FIB_NODE_INDEX_INVALID;
129 * @brief Create a new node list. The expectation is that these are few in number
130 * so straight from the memory subsystem
133 fib_node_list_create (void)
135 fib_node_list_head_t *head;
137 pool_get(fib_node_list_head_pool, head);
139 fib_node_list_head_init(head);
141 return (fib_node_list_head_get_index(head));
145 fib_node_list_destroy (fib_node_list_t *list)
147 fib_node_list_head_t *head;
149 if (FIB_NODE_INDEX_INVALID == *list)
152 head = fib_node_list_head_get(*list);
153 ASSERT(0 == head->fnlh_n_elts);
155 pool_put(fib_node_list_head_pool, head);
156 *list = FIB_NODE_INDEX_INVALID;
161 * @brief Insert an element at the from of the list.
164 fib_node_list_push_front (fib_node_list_t list,
166 fib_node_type_t type,
167 fib_node_index_t index)
169 fib_node_list_elt_t *elt, *next;
170 fib_node_list_head_t *head;
172 head = fib_node_list_head_get(list);
173 elt = fib_node_list_elt_create(head, owner_id, type, index);
175 elt->fnle_prev = FIB_NODE_INDEX_INVALID;
176 elt->fnle_next = head->fnlh_head;
178 if (FIB_NODE_INDEX_INVALID != head->fnlh_head)
180 next = fib_node_list_elt_get(head->fnlh_head);
181 next->fnle_prev = fib_node_list_elt_get_index(elt);
183 head->fnlh_head = fib_node_list_elt_get_index(elt);
187 return (fib_node_list_elt_get_index(elt));
191 fib_node_list_push_back (fib_node_list_t list,
193 fib_node_type_t type,
194 fib_node_index_t index)
197 return (FIB_NODE_INDEX_INVALID);
201 fib_node_list_extract (fib_node_list_head_t *head,
202 fib_node_list_elt_t *elt)
204 fib_node_list_elt_t *next, *prev;
206 if (FIB_NODE_INDEX_INVALID != elt->fnle_next)
208 next = fib_node_list_elt_get(elt->fnle_next);
209 next->fnle_prev = elt->fnle_prev;
212 if (FIB_NODE_INDEX_INVALID != elt->fnle_prev)
214 prev = fib_node_list_elt_get(elt->fnle_prev);
215 prev->fnle_next = elt->fnle_next;
219 ASSERT (fib_node_list_elt_get_index(elt) == head->fnlh_head);
220 head->fnlh_head = elt->fnle_next;
225 fib_node_list_insert_after (fib_node_list_head_t *head,
226 fib_node_list_elt_t *prev,
227 fib_node_list_elt_t *elt)
229 fib_node_list_elt_t *next;
231 elt->fnle_next = prev->fnle_next;
232 if (FIB_NODE_INDEX_INVALID != prev->fnle_next)
234 next = fib_node_list_elt_get(prev->fnle_next);
235 next->fnle_prev = fib_node_list_elt_get_index(elt);
237 prev->fnle_next = fib_node_list_elt_get_index(elt);
238 elt->fnle_prev = fib_node_list_elt_get_index(prev);
242 fib_node_list_remove (fib_node_list_t list,
245 fib_node_list_head_t *head;
246 fib_node_list_elt_t *elt;
248 head = fib_node_list_head_get(list);
249 elt = fib_node_list_elt_get(sibling);
251 fib_node_list_extract(head, elt);
254 pool_put(fib_node_list_elt_pool, elt);
258 fib_node_list_elt_remove (u32 sibling)
260 fib_node_list_elt_t *elt;
262 elt = fib_node_list_elt_get(sibling);
264 fib_node_list_remove(elt->fnle_list, sibling);
268 * @brief Advance the sibling one step (toward the tail) in the list.
269 * return 0 if at the end of the list, 1 otherwise.
272 fib_node_list_advance (u32 sibling)
274 fib_node_list_elt_t *elt, *next;
275 fib_node_list_head_t *head;
277 elt = fib_node_list_elt_get(sibling);
278 head = fib_node_list_head_get(elt->fnle_list);
280 if (FIB_NODE_INDEX_INVALID != elt->fnle_next)
283 * not at the end of the list
285 next = fib_node_list_elt_get(elt->fnle_next);
287 fib_node_list_extract(head, elt);
288 fib_node_list_insert_after(head, next, elt);
299 fib_node_list_elt_get_next (u32 sibling,
302 fib_node_list_elt_t *elt, *next;
304 elt = fib_node_list_elt_get(sibling);
306 if (FIB_NODE_INDEX_INVALID != elt->fnle_next)
308 next = fib_node_list_elt_get(elt->fnle_next);
310 *ptr = next->fnle_owner;
315 ptr->fnp_index = FIB_NODE_INDEX_INVALID;
321 fib_node_list_get_size (fib_node_list_t list)
323 fib_node_list_head_t *head;
325 if (FIB_NODE_INDEX_INVALID == list)
330 head = fib_node_list_head_get(list);
332 return (head->fnlh_n_elts);
336 fib_node_list_get_front (fib_node_list_t list,
339 fib_node_list_head_t *head;
340 fib_node_list_elt_t *elt;
343 if (0 == fib_node_list_get_size(list))
345 ptr->fnp_index = FIB_NODE_INDEX_INVALID;
349 head = fib_node_list_head_get(list);
350 elt = fib_node_list_elt_get(head->fnlh_head);
352 *ptr = elt->fnle_owner;
358 * @brief Walk the list of node. This must be safe w.r.t. the removal
359 * of nodes during the walk.
362 fib_node_list_walk (fib_node_list_t list,
363 fib_node_list_walk_cb_t fn,
366 fib_node_list_elt_t *elt;
367 fib_node_list_head_t *head;
370 if (FIB_NODE_INDEX_INVALID == list)
375 head = fib_node_list_head_get(list);
376 sibling = head->fnlh_head;
378 while (FIB_NODE_INDEX_INVALID != sibling)
380 elt = fib_node_list_elt_get(sibling);
381 sibling = elt->fnle_next;
383 fn(&elt->fnle_owner, args);