Lines Matching defs:key

120 	t_key key;
217 #define get_cindex(key, kv) (((key) ^ (kv)->key) >> (kv)->pos)
219 static inline unsigned long get_index(t_key key, struct key_vector *kv)
221 unsigned long index = key ^ kv->key;
230 * necessary. Every node in the trie has a key associated with it, but not
231 * all of the bits in that key are significant.
235 * If n is a leaf, every bit in its key is significant. Its presence is
240 * correct key path.
242 * Note that we can never "miss" the correct key in the tree if present by
243 * following the wrong path. Path compression ensures that segments of the key
248 * if n is an internal node - a 'tnode' here, the various parts of its key
279 * of the bits are really not needed or indeed known in n->key.
352 static struct key_vector *leaf_new(t_key key, struct fib_alias *fa)
361 /* initialize key vector */
363 l->key = key;
375 static struct key_vector *tnode_new(t_key key, int pos, int bits)
397 tn->key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0;
467 static inline void put_child_root(struct key_vector *tp, t_key key,
473 put_child(tp, get_index(key, tp), n);
515 put_child_root(tp, tn->key, tn);
544 tn = tnode_new(oldtnode->key, oldtnode->pos - 1, oldtnode->bits + 1);
567 put_child(tn, get_index(inode->key, tn), inode);
584 * a position one bit further down the key and this
588 * node0's key and "1" in node1's key. Since we are
589 * moving the key position by one step, the bit that
595 node1 = tnode_new(inode->key | m, inode->pos, inode->bits - 1);
598 node0 = tnode_new(inode->key, inode->pos, inode->bits - 1);
639 tn = tnode_new(oldtnode->key, oldtnode->pos + 1, oldtnode->bits - 1);
663 inode = tnode_new(node0->key, oldtnode->pos, 1);
698 put_child_root(tp, oldtnode->key, n);
852 unsigned long cindex = get_index(tn->key, tp);
935 struct key_vector **tp, u32 key)
947 index = get_cindex(key, n);
952 * is the difference between the key and this value. From
1063 struct fib_alias *new, t_key key)
1067 l = leaf_new(key, new);
1072 n = get_child(tp, get_index(key, tp));
1074 /* Case 2: n is a LEAF or a TNODE and the key doesn't match.
1083 tn = tnode_new(key, __fls(key ^ n->key), 1);
1089 put_child(tn, get_index(key, tn) ^ 1, n);
1092 put_child_root(tp, key, tn);
1102 put_child_root(tp, key, l);
1114 struct fib_alias *fa, t_key key)
1117 return fib_insert_node(t, tp, new, key);
1148 static bool fib_valid_key_len(u32 key, u8 plen, struct netlink_ext_ack *extack)
1155 if ((plen < KEYLENGTH) && (key << plen)) {
1179 u32 key;
1182 key = ntohl(cfg->fc_dst);
1184 if (!fib_valid_key_len(key, plen, extack))
1187 pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
1195 l = fib_find_node(t, &tp, key);
1200 * with the same keys [prefix,tos,priority], if such key already
1275 key, plen,
1284 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1328 err = fib_insert_alias(t, tp, l, new_fa, fa, key);
1333 l = l ? l : fib_find_node(t, &tp, key);
1344 err = call_fib_entry_notifiers(net, fib_event, key, plen,
1354 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, new_fa->tb_id,
1369 static inline t_key prefix_mismatch(t_key key, struct key_vector *n)
1371 t_key prefix = n->key;
1373 return (key ^ prefix) & (prefix | -prefix);
1404 const t_key key = ntohl(flp->daddr);
1425 index = get_cindex(key, n);
1430 * is the difference between the key and this value. From
1467 * between the key and the prefix exist in the region of
1470 if (unlikely(prefix_mismatch(key, n)) || (n->slen == n->pos))
1494 t_key pkey = pn->key;
1523 index = key ^ n->key;
1577 res->prefix = htonl(n->key);
1618 put_child_root(tp, l->key, NULL);
1633 static void fib_notify_alias_delete(struct net *net, u32 key,
1659 call_fib_entry_notifiers(net, fib_event, key, KEYLENGTH - slen,
1673 u32 key;
1675 key = ntohl(cfg->fc_dst);
1677 if (!fib_valid_key_len(key, plen, extack))
1680 l = fib_find_node(t, &tp, key);
1688 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1716 fib_notify_alias_delete(net, key, &l->leaf, fa_to_delete, extack);
1717 rtmsg_fib(RTM_DELROUTE, htonl(key), fa_to_delete, plen, tb->tb_id,
1733 /* Scan for the next leaf starting at the provided key value */
1734 static struct key_vector *leaf_walk_rcu(struct key_vector **tn, t_key key)
1739 /* this loop is meant to try and find the key in the trie */
1743 cindex = (key > pn->key) ? get_index(key, pn) : 0;
1754 if (IS_LEAF(n) && (n->key >= key))
1758 /* this loop will search for the next leaf with a greater key */
1762 t_key pkey = pn->key;
1804 t_key pkey = pn->key;
1813 put_child_root(pn, n->key, NULL);
1839 put_child_root(pn, n->key, NULL);
1856 t_key key = 0;
1867 while ((l = leaf_walk_rcu(&tp, key)) != NULL) {
1885 local_l = fib_find_node(lt, &local_tp, l->key);
1888 NULL, l->key)) {
1894 /* stop loop if key wrapped back to 0 */
1895 key = l->key + 1;
1896 if (key < l->key)
1922 t_key pkey = pn->key;
1970 put_child_root(pn, n->key, NULL);
1993 t_key pkey = pn->key;
2041 fib_notify_alias_delete(net, n->key, &n->leaf, fa,
2044 rtmsg_fib(RTM_DELROUTE, htonl(n->key), fa,
2056 put_child_root(pn, n->key, NULL);
2078 t_key pkey = pn->key;
2107 rtmsg_fib(RTM_NEWROUTE, htonl(n->key), fa,
2116 n->key,
2162 l->key, KEYLENGTH - fa->fa_slen,
2175 t_key key = 0;
2178 while ((l = leaf_walk_rcu(&tp, key)) != NULL) {
2183 key = l->key + 1;
2185 if (key < l->key)
2232 __be32 xkey = htonl(l->key);
2318 /* Dump starting at last key.
2319 * Note: 0.0.0.0/0 (ie default) is first key.
2322 t_key key = cb->args[3];
2324 /* First time here, count and key are both always 0. Count > 0
2325 * and key == 0 means the dump has wrapped around and we are done.
2327 if (count && !key)
2330 while ((l = leaf_walk_rcu(&tp, key)) != NULL) {
2335 cb->args[3] = key;
2341 key = l->key + 1;
2346 /* stop loop if key wrapped back to 0 */
2347 if (key < l->key)
2351 cb->args[3] = key;
2442 pkey = pn->key;
2764 __be32 prf = htonl(n->key);
2772 __be32 val = htonl(n->key);
2809 t_key key;
2816 t_key key;
2818 /* use cached location of previously found key */
2820 key = iter->key;
2823 key = 0;
2828 while ((l = leaf_walk_rcu(tp, key)) && (pos-- > 0)) {
2829 key = l->key + 1;
2833 /* handle unlikely case of a key wrap */
2834 if (!key)
2839 iter->key = l->key; /* remember it */
2867 iter->key = KEY_MAX;
2876 t_key key = iter->key + 1;
2880 /* only allow key of 0 for start of sequence */
2881 if ((v == SEQ_START_TOKEN) || key)
2882 l = leaf_walk_rcu(&iter->tnode, key);
2885 iter->key = l->key;
2939 prefix = htonl(l->key);