*~
*.sw[op]
/build-root/.ccache
/build-root/build-*/
/build-root/install-*/
/build-root/tools
/build-root/dpdk-includes/
/build-root/packages-vpp/
/build-root/path_setup
/build-root/deb/debian/vpp-plugins/
/build-root/deb/.pybuild/
/build-root/*.deb
/build-root/*.rpm
/build-root/*.tar.xz
/build-root/*.changes
/build-root/rpmbuild/
/build-root/test-doc/
/build-root/test-cov/
/test/run/
/test/build/
/test/coverage/
/build-config.mk
/build/external/*.tar.gz
/build/external/*.tar.xz
/build/external/vpp-*.deb
/build/external/vpp-*.changes
/build/external/downloads/
/path_setup
/tools/
# start autotools ignore
autom4te.cache/
config/
Makefile.in
aclocal.m4
app.info
compile
config.log
config.guess
config.sub
config.status
configure
configure.scan
coverage_report
depcomp
install-sh
libtool
m4
missing
stamp-h1
ltmain.sh
ylwrap
test-driver
*.iml
.deps.ok
.settings
.autotools
# stop autotools ignore
# OSX and some IDE
.DS_Store
.idea/
.project
.cproject
.pydevproject
.vscode/
cmake-build*/
# cscope and ctags
/cscope.*
/tags
ID
TAGS
# ggtags
GPATH
GRTAGS
GTAGS
# Generated documentation
/build-root/docs
/build-roo/*
* Copyright (c) 2016 Cisco and/or its affiliates.
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at:
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/**
* @brief a hetrogeneous w.r.t. FIB node type, of FIB nodes.
* Since we cannot use C pointers, due to memeory reallocs, the next/prev
* are described as key:{type,index}.
*/
#include <vnet/fib/fib_node_list.h>
/**
* @brief An element in the list
*/
typedef struct fib_node_list_elt_t_
{
/**
* The index of the list this element is in
*/
fib_node_list_t fnle_list;
/**
* The owner of this element
*/
fib_node_ptr_t fnle_owner;
/**
* The next element in the list
*/
u32 fnle_next;
/**
* The previous element in the list
*/
u32 fnle_prev;
} fib_node_list_elt_t;
/**
* @brief A list of FIB nodes
*/
typedef struct fib_node_list_head_t_
{
/**
* The head element
*/
u32 fnlh_head;
/**
* Number of elements in the list
*/
u32 fnlh_n_elts;
} fib_node_list_head_t;
/**
* Pools of list elements and heads
*/
static fib_node_list_elt_t *fib_node_list_elt_pool;
static fib_node_list_head_t *fib_node_list_head_pool;
static index_t
fib_node_list_elt_get_index (fib_node_list_elt_t *elt)
{
return (elt - fib_node_list_elt_pool);
}
static fib_node_list_elt_t *
fib_node_list_elt_get (index_t fi)
{
return (pool_elt_at_index(fib_node_list_elt_pool, fi));
}
static index_t
fib_node_list_head_get_index (fib_node_list_head_t *head)
{
return (head - fib_node_list_head_pool);
}
static fib_node_list_head_t *
fib_node_list_head_get (fib_node_list_t fi)
{
return (pool_elt_at_index(fib_node_list_head_pool, fi));
}
static fib_node_list_elt_t *
fib_node_list_elt_create (fib_node_list_head_t *head,
int id,
fib_node_type_t type,
fib_node_index_t index)
{
fib_node_list_elt_t *elt;
pool_get(fib_node_list_elt_pool, elt);
elt->fnle_list = fib_node_list_head_get_index(head);
elt->fnle_owner.fnp_type = type;
elt->fnle_owner.fnp_index = index;
elt->fnle_next = FIB_NODE_INDEX_INVALID;
elt->fnle_prev = FIB_NODE_INDEX_INVALID;
return (elt);
}
static void
fib_node_list_head_init (fib_node_list_head_t *head)
{
head->fnlh_n_elts = 0;
head->fnlh_head = FIB_NODE_INDEX_INVALID;
}
/**
* @brief Create a new node list.
*/
fib_node_list_t
fib_node_list_create (void)
{
fib_node_list_head_t *head;
pool_get(fib_node_list_head_pool, head);
fib_node_list_head_init(head);
return (fib_node_list_head_get_index(head));
}
void
fib_node_list_destroy (fib_node_list_t *list)
{
fib_node_list_head_t *head;
if (FIB_NODE_INDEX_INVALID == *list)
return;
head = fib_node_list_head_get(*list);
ASSERT(0 == head->fnlh_n_elts);
pool_put(fib_node_list_head_pool, head);
*list = FIB_NODE_INDEX_INVALID;
}
/**
* @brief Insert an element at the from of the list.
*/
u32
fib_node_list_push_front (fib_node_list_t list,
int owner_id,
fib_node_type_t type,
fib_node_index_t index)
{
fib_node_list_elt_t *elt, *next;
fib_node_list_head_t *head;
head = fib_node_list_head_get(list);
elt = fib_node_list_elt_create(head, owner_id, type, index);
elt->fnle_prev = FIB_NODE_INDEX_INVALID;
elt->fnle_next = head->fnlh_head;
if (FIB_NODE_INDEX_INVALID != head->fnlh_head)
{
next = fib_node_list_elt_get(head->fnlh_head);
next->fnle_prev = fib_node_list_elt_get_index(elt);
}
head->fnlh_head = fib_node_list_elt_get_index(elt);
head->fnlh_n_elts++;
return (fib_node_list_elt_get_index(elt));
}
u32
fib_node_list_push_back (fib_node_list_t list,
int owner_id,
fib_node_type_t type,
fib_node_index_t index)
{
ASSERT(0);
return (FIB_NODE_INDEX_INVALID);
}
static void
fib_node_list_extract (fib_node_list_head_t *head,
fib_node_list_elt_t *elt)
{
fib_node_list_elt_t *next, *prev;
if (FIB_NODE_INDEX_INVALID != elt->fnle_next)
{
next = fib_node_list_elt_get(elt->fnle_next);
next->fnle_prev = elt->fnle_prev;
}
if (FIB_NODE_INDEX_INVALID != elt->fnle_prev)
{
prev = fib_node_list_elt_get(elt->fnle_prev);
prev->fnle_next = elt->fnle_next;
}
else
{
ASSERT (fib_node_list_elt_get_index(elt) == head->fnlh_head);
head->fnlh_head = elt->fnle_next;
}
}
static void
fib_node_list_insert_after (fib_node_list_head_t *head,
fib_node_list_elt_t *prev,
fib_node_list_elt_t *elt)
{
fib_node_list_elt_t *next;
elt->fnle_next = prev->fnle_next;
if (FIB_NODE_INDEX_INVALID != prev->fnle_next)
{
next = fib_node_list_elt_get(prev->fnle_next);
next->fnle_prev = fib_node_list_elt_get_index(elt);
}
prev->fnle_next = fib_node_list_elt_get_index(elt);
elt->fnle_prev = fib_node_list_elt_get_index(prev);
}
void
fib_node_list_remove (fib_node_list_t list,
u32 sibling)
{
fib_node_list_head_t *head;
fib_node_list_elt_t *elt;
head = fib_node_list_head_get(list);
elt = fib_node_list_elt_get(sibling);
fib_node_list_extract(head, elt);
head->fnlh_n_elts--;
pool_put(fib_node_list_elt_pool, elt);
}
void
fib_node_list_elt_remove (u32 sibling)
{
fib_node_list_elt_t *elt;
elt = fib_node_list_elt_get(sibling);
fib_node_list_remove(elt->fnle_list, sibling);
}
/**
* @brief Advance the sibling one step (toward the tail) in the list.
* return 0 if at the end of the list, 1 otherwise.
*/
int
fib_node_list_advance (u32 sibling)
{
fib_node_list_elt_t *elt, *next;
fib_node_list_head_t *head;
elt = fib_node_list_elt_get(sibling);
head = fib_node_list_head_get(elt->fnle_list);
if (FIB_NODE_INDEX_INVALID != elt->fnle_next)
{
/*
* not at the end of the list
*/
next = fib_node_list_elt_get(elt->fnle_next);
fib_node_list_extract(head, elt);
fib_node_list_insert_after(head, next, elt);
return (1);
}
else
{
return (0);
}
}
int
fib_node_list_elt_get_next (u32 sibling,
fib_node_ptr_t *ptr)
{
fib_node_list_elt_t *elt, *next;
elt = fib_node_list_elt_get(sibling);
if (FIB_NODE_INDEX_INVALID != elt->fnle_next)
{
next = fib_node_list_elt_get(elt->fnle_next);
*ptr = next->fnle_owner;
return (1);
}
else
{
ptr->fnp_index = FIB_NODE_INDEX_INVALID;
return (0);
}
}
u32
fib_node_list_get_size (fib_node_list_t list)
{
fib_node_list_head_t *head;
if (FIB_NODE_INDEX_INVALID == list)
{
return (0);
}
head = fib_node_list_head_get(list);
return (head->fnlh_n_elts);
}
int
fib_node_list_get_front (fib_node_list_t list,
fib_node_ptr_t *ptr)
{
fib_node_list_head_t *head;
fib_node_list_elt_t *elt;
if (0 == fib_node_list_get_size(list))
{
ptr->fnp_index = FIB_NODE_INDEX_INVALID;
return (0);
}
head = fib_node_list_head_get(list);
elt = fib_node_list_elt_get(head->fnlh_head);
*ptr = elt->fnle_owner;
return (1);
}
/**
* @brief Walk the list of node. This must be safe w.r.t. the removal
* of nodes during the walk.
*/
void
fib_node_list_walk (fib_node_list_t list,
fib_node_list_walk_cb_t fn,
void *args)
{
fib_node_list_elt_t *elt;
fib_node_list_head_t *head;
u32 sibling;
if (FIB_NODE_INDEX_INVALID == list)
{
return;
}
head = fib_node_list_head_get(list);
sibling = head->fnlh_head;
while (FIB_NODE_INDEX_INVALID != sibling)
{
elt = fib_node_list_elt_get(sibling);
sibling = elt->fnle_next;
fn(&elt->fnle_owner, args);
}
}
void
fib_node_list_memory_show (void)
{
fib_show_memory_usage("Node-list elements",
pool_elts(fib_node_list_elt_pool),
pool_len(fib_node_list_elt_pool),
sizeof(fib_node_list_elt_t));
fib_show_memory_usage("Node-list heads",
pool_elts(fib_node_list_head_pool),
pool_len(fib_node_list_head_pool),
sizeof(fib_node_list_head_t));
}
