LC-Trie树插入

参考文本链接：https://blog.csdn.net/dog250/article/details/6596046
下面一个例子，依次插入3条路由项：
1:192.168.10.0/24
2:192.168.20.0/24
3:2.232.20.0/24

然后我们看图说话，首先看一下比特图：


static struct tnode *tnode_new(t_key key, int pos, int bits)
{
size_t sz = sizeof(struct tnode) + (sizeof(struct rt_trie_node *) << bits);
struct tnode *tn = tnode_alloc(sz);


if (tn) {
tn->parent = T_TNODE;
tn->pos = pos;
tn->bits = bits;
tn->key = key;
tn->full_children = 0;
tn->empty_children = 1 << bits ;
}


pr_debug("AT %p s=%zu %zu\n", tn, sizeof(struct tnode),
sizeof(struct rt_trie_node *) << bits);
return tn;
}


static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
{
int pos, newpos;
struct tnode *tp = NULL, *tn = NULL;
struct rt_trie_node *n;
struct leaf *l;
int missbit;
struct list_head *fa_head = NULL;
struct leaf_info *li;
t_key cindex;


pos = 0;
n = rtnl_dereference(t->trie);
......
/* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
/*
*  Add a new tnode here
*  first tnode need some special handling
*/


if (n) {
pos = tp ? tp->pos+tp->bits : 0;
newpos = tkey_mismatch(key, pos, n->key);
tn = tnode_new(n->key, newpos, 1);
} else { //static struct tnode *tnode_new(t_key key, int pos, int bits)
newpos = 0;
tn = tnode_new(key, newpos, 1); /* First tnode */
}
......
/* Rebalance the trie */

/*
trie_rebalance()
The key function for the dynamic trie after any change in the trie
it is run to optimize and reorganize. Tt will walk the trie upwards 
towards the root from a given tnode, doing a resize() at each step 
to implement level compression.

而动态多路trie所要维护的就是让这棵树不这么极端。
我们首先看一眼普通多路trie树的插入情形，注意，所谓多路trie树插入是假的，在Linux的实现中，只有平衡操作才能让trie成为多路的，这里给出的实例在Linux中是不会出现的，只有经过平衡操作的trie树才会是这个样子，也就是说，不可能一插入就是这样的，具体的CheckNode的bits在这里是事先确定好的，而在Linux的实现中却是动态调整的。多路trie的本质在于其“多路”，而多路的本质在于CheckNode的bits字段。
*/
trie_rebalance(t, tp);
done:
return fa_head;
}
接下来看一下插入trie的情形：