Lines Matching refs:tn
172 static struct key_vector *resize(struct trie *t, struct key_vector *tn);
193 #define node_parent(tn) rtnl_dereference(tn_info(tn)->parent)
194 #define get_child(tn, i) rtnl_dereference((tn)->tnode[i])
197 #define node_parent_rcu(tn) rcu_dereference_rtnl(tn_info(tn)->parent)
198 #define get_child_rcu(tn, i) rcu_dereference_rtnl((tn)->tnode[i])
212 static inline unsigned long child_length(const struct key_vector *tn)
214 return (1ul << tn->bits) & ~(1ul);
378 struct key_vector *tn;
396 tn = tnode->kv;
397 tn->key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0;
398 tn->pos = pos;
399 tn->bits = bits;
400 tn->slen = pos;
402 return tn;
408 static inline int tnode_full(struct key_vector *tn, struct key_vector *n)
410 return n && ((n->pos + n->bits) == tn->pos) && IS_TNODE(n);
416 static void put_child(struct key_vector *tn, unsigned long i,
419 struct key_vector *chi = get_child(tn, i);
422 BUG_ON(i >= child_length(tn));
426 empty_child_inc(tn);
428 empty_child_dec(tn);
431 wasfull = tnode_full(tn, chi);
432 isfull = tnode_full(tn, n);
435 tn_info(tn)->full_children--;
437 tn_info(tn)->full_children++;
439 if (n && (tn->slen < n->slen))
440 tn->slen = n->slen;
442 rcu_assign_pointer(tn->tnode[i], n);
445 static void update_children(struct key_vector *tn)
450 for (i = child_length(tn); i;) {
451 struct key_vector *inode = get_child(tn, --i);
460 if (node_parent(inode) == tn)
463 node_set_parent(inode, tn);
476 static inline void tnode_free_init(struct key_vector *tn)
478 tn_info(tn)->rcu.next = NULL;
481 static inline void tnode_free_append(struct key_vector *tn,
484 tn_info(n)->rcu.next = tn_info(tn)->rcu.next;
485 tn_info(tn)->rcu.next = &tn_info(n)->rcu;
488 static void tnode_free(struct key_vector *tn)
490 struct callback_head *head = &tn_info(tn)->rcu;
494 tnode_free_size += TNODE_SIZE(1ul << tn->bits);
495 node_free(tn);
497 tn = container_of(head, struct tnode, rcu)->kv;
508 struct key_vector *tn)
514 NODE_INIT_PARENT(tn, tp);
515 put_child_root(tp, tn->key, tn);
518 update_children(tn);
524 for (i = child_length(tn); i;) {
525 struct key_vector *inode = get_child(tn, --i);
528 if (tnode_full(tn, inode))
529 tn = resize(t, inode);
538 struct key_vector *tn;
544 tn = tnode_new(oldtnode->key, oldtnode->pos - 1, oldtnode->bits + 1);
545 if (!tn)
556 for (i = child_length(oldtnode), m = 1u << tn->pos; i;) {
567 put_child(tn, get_index(inode->key, tn), inode);
576 put_child(tn, 2 * i + 1, get_child(inode, 1));
577 put_child(tn, 2 * i, get_child(inode, 0));
591 * (tn->pos) - is the one that will differ between
600 tnode_free_append(tn, node1);
603 tnode_free_append(tn, node0);
614 NODE_INIT_PARENT(node1, tn);
615 NODE_INIT_PARENT(node0, tn);
618 put_child(tn, 2 * i + 1, node1);
619 put_child(tn, 2 * i, node0);
623 return replace(t, oldtnode, tn);
626 tnode_free(tn);
634 struct key_vector *tn;
639 tn = tnode_new(oldtnode->key, oldtnode->pos + 1, oldtnode->bits - 1);
640 if (!tn)
658 put_child(tn, i / 2, node1 ? : node0);
666 tnode_free_append(tn, inode);
671 NODE_INIT_PARENT(inode, tn);
674 put_child(tn, i / 2, inode);
678 return replace(t, oldtnode, tn);
681 tnode_free(tn);
707 static unsigned char update_suffix(struct key_vector *tn)
709 unsigned char slen = tn->pos;
714 * tn->pos + tn->bits, the second highest node will have a suffix
715 * length at most of tn->pos + tn->bits - 1
717 slen_max = min_t(unsigned char, tn->pos + tn->bits - 1, tn->slen);
722 * represent the nodes with suffix length equal to tn->pos
724 for (i = 0, stride = 0x2ul ; i < child_length(tn); i += stride) {
725 struct key_vector *n = get_child(tn, i);
740 tn->slen = slen;
758 * The left-hand side may look a bit weird: child_length(tn)
759 * - tn->empty_children is of course the number of non-null children
760 * in the current node. tn->full_children is the number of "full"
767 * to_be_doubled = tn->full_children;
768 * not_to_be_doubled = child_length(tn) - tn->empty_children -
769 * tn->full_children;
771 * new_child_length = child_length(tn) * 2;
788 * 100 * (child_length(tn) - tn->empty_children +
789 * tn->full_children) >= inflate_threshold * new_child_length
792 * 100 * (child_length(tn) - tn->empty_children +
793 * tn->full_children) >=
794 * inflate_threshold * child_length(tn) * 2
797 * 50 * (tn->full_children + child_length(tn) -
798 * tn->empty_children) >= inflate_threshold *
799 * child_length(tn)
802 static inline bool should_inflate(struct key_vector *tp, struct key_vector *tn)
804 unsigned long used = child_length(tn);
809 used -= tn_info(tn)->empty_children;
810 used += tn_info(tn)->full_children;
814 return (used > 1) && tn->pos && ((50 * used) >= threshold);
817 static inline bool should_halve(struct key_vector *tp, struct key_vector *tn)
819 unsigned long used = child_length(tn);
824 used -= tn_info(tn)->empty_children;
828 return (used > 1) && (tn->bits > 1) && ((100 * used) < threshold);
831 static inline bool should_collapse(struct key_vector *tn)
833 unsigned long used = child_length(tn);
835 used -= tn_info(tn)->empty_children;
838 if ((tn->bits == KEYLENGTH) && tn_info(tn)->full_children)
846 static struct key_vector *resize(struct trie *t, struct key_vector *tn)
851 struct key_vector *tp = node_parent(tn);
852 unsigned long cindex = get_index(tn->key, tp);
856 tn, inflate_threshold, halve_threshold);
862 BUG_ON(tn != get_child(tp, cindex));
867 while (should_inflate(tp, tn) && max_work) {
868 tp = inflate(t, tn);
877 tn = get_child(tp, cindex);
881 tp = node_parent(tn);
890 while (should_halve(tp, tn) && max_work) {
891 tp = halve(t, tn);
900 tn = get_child(tp, cindex);
904 if (should_collapse(tn))
905 return collapse(t, tn);
908 return node_parent(tn);
911 static void node_pull_suffix(struct key_vector *tn, unsigned char slen)
913 unsigned char node_slen = tn->slen;
915 while ((node_slen > tn->pos) && (node_slen > slen)) {
916 slen = update_suffix(tn);
920 tn = node_parent(tn);
921 node_slen = tn->slen;
925 static void node_push_suffix(struct key_vector *tn, unsigned char slen)
927 while (tn->slen < slen) {
928 tn->slen = slen;
929 tn = node_parent(tn);
1056 static void trie_rebalance(struct trie *t, struct key_vector *tn)
1058 while (!IS_TRIE(tn))
1059 tn = resize(t, tn);
1081 struct key_vector *tn;
1083 tn = tnode_new(key, __fls(key ^ n->key), 1);
1084 if (!tn)
1088 NODE_INIT_PARENT(tn, tp);
1089 put_child(tn, get_index(key, tn) ^ 1, n);
1092 put_child_root(tp, key, tn);
1093 node_set_parent(n, tn);
1096 tp = tn;
1734 static struct key_vector *leaf_walk_rcu(struct key_vector **tn, t_key key)
1736 struct key_vector *pn, *n = *tn;
1783 *tn = pn;
1787 *tn = pn;