route

IPv4 route fib find node

###summary
遍历路由树，查找是否存在key这条路由。
如果有则返回对应的节点 struct leaf *，
否则返回NULL。

中间节点 和 叶子节点

路由树（fib lc tree)是个多叉树,树的每个节点是struct rt_trie_node。
每个节点的分叉个数(X)是可变的， 由 struct rt_trie_node里的bits决定。
X = 2 的bits次幂次方。

叶子节点的首个子类型也是struct rt_trie_node，所以可以看成是其派生。

树的遍历

  1. 如果当前节点为空， 结束循环。

  2. 如果当前节点不是T_TNODE，结束循环。
    即:当前节点为 叶子节点T_LEAF.

  3. 比较当前节点tn和参数key的未比较过的前缀是否匹配。
    tkey_sub_equals(tn->key, x, y, key))

    未比较过的前缀指[x-y)这个区间的位，包括x,不包括y。
    x = 父节点的pos + 父节点的bits （父节点为空时，x取0）
    y = 当前节点的pos + 父节点的pos
    这里，具体取哪些位石油父节点和当前节点刚提决定的。

  4. 如果相等，则结束循环，判断当前节点是否真正匹配。

  5. 如果不相等，则跳到第N个一个孩子节点。
    N = tkey_extract_bits(key, tn->pos, tn->bits)
    N是取从参数key的第tn->pos位开始, 共tn->bits位转化出来的值。
    注意，此处是取key的某一位或者几位的值，而具体怎么取值是有当前节点的(pos,bits)决定的。

完整判断

当前节点n是叶子节点，并且key完全相同
n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
954 static struct leaf *
955 fib_find_node(struct trie *t, u32 key)
956 {
957         int pos;
958         struct tnode *tn;
959         struct rt_trie_node *n;
960 
961         pos = 0;
962         n = rcu_dereference_rtnl(t->trie);
963 
964         while (n != NULL &&  NODE_TYPE(n) == T_TNODE) {
965                 tn = (struct tnode *) n;
966 
967                 check_tnode(tn);
968 
969                 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
970                         pos = tn->pos + tn->bits;
971                         n = tnode_get_child_rcu(tn,
972                                                 tkey_extract_bits(key,
973                                                                   tn->pos,
974                                                                   tn->bits));
975                 } else
976                         break;
977         }
978         /* Case we have found a leaf. Compare prefixes */
979 
980         if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
981                 return (struct leaf *)n;
982 
983         return NULL;
984 }