Lines Matching refs:tn
173 static struct key_vector *resize(struct trie *t, struct key_vector *tn);
194 #define node_parent(tn) rtnl_dereference(tn_info(tn)->parent)
195 #define get_child(tn, i) rtnl_dereference((tn)->tnode[i])
198 #define node_parent_rcu(tn) rcu_dereference_rtnl(tn_info(tn)->parent)
199 #define get_child_rcu(tn, i) rcu_dereference_rtnl((tn)->tnode[i])
213 static inline unsigned long child_length(const struct key_vector *tn)
215 return (1ul << tn->bits) & ~(1ul);
379 struct key_vector *tn;
397 tn = tnode->kv;
398 tn->key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0;
399 tn->pos = pos;
400 tn->bits = bits;
401 tn->slen = pos;
403 return tn;
409 static inline int tnode_full(struct key_vector *tn, struct key_vector *n)
411 return n && ((n->pos + n->bits) == tn->pos) && IS_TNODE(n);
417 static void put_child(struct key_vector *tn, unsigned long i,
420 struct key_vector *chi = get_child(tn, i);
423 BUG_ON(i >= child_length(tn));
427 empty_child_inc(tn);
429 empty_child_dec(tn);
432 wasfull = tnode_full(tn, chi);
433 isfull = tnode_full(tn, n);
436 tn_info(tn)->full_children--;
438 tn_info(tn)->full_children++;
440 if (n && (tn->slen < n->slen))
441 tn->slen = n->slen;
443 rcu_assign_pointer(tn->tnode[i], n);
446 static void update_children(struct key_vector *tn)
451 for (i = child_length(tn); i;) {
452 struct key_vector *inode = get_child(tn, --i);
461 if (node_parent(inode) == tn)
464 node_set_parent(inode, tn);
477 static inline void tnode_free_init(struct key_vector *tn)
479 tn_info(tn)->rcu.next = NULL;
482 static inline void tnode_free_append(struct key_vector *tn,
485 tn_info(n)->rcu.next = tn_info(tn)->rcu.next;
486 tn_info(tn)->rcu.next = &tn_info(n)->rcu;
489 static void tnode_free(struct key_vector *tn)
491 struct callback_head *head = &tn_info(tn)->rcu;
495 tnode_free_size += TNODE_SIZE(1ul << tn->bits);
496 node_free(tn);
498 tn = container_of(head, struct tnode, rcu)->kv;
509 struct key_vector *tn)
515 NODE_INIT_PARENT(tn, tp);
516 put_child_root(tp, tn->key, tn);
519 update_children(tn);
525 for (i = child_length(tn); i;) {
526 struct key_vector *inode = get_child(tn, --i);
529 if (tnode_full(tn, inode))
530 tn = resize(t, inode);
539 struct key_vector *tn;
545 tn = tnode_new(oldtnode->key, oldtnode->pos - 1, oldtnode->bits + 1);
546 if (!tn)
557 for (i = child_length(oldtnode), m = 1u << tn->pos; i;) {
568 put_child(tn, get_index(inode->key, tn), inode);
577 put_child(tn, 2 * i + 1, get_child(inode, 1));
578 put_child(tn, 2 * i, get_child(inode, 0));
592 * (tn->pos) - is the one that will differ between
601 tnode_free_append(tn, node1);
604 tnode_free_append(tn, node0);
615 NODE_INIT_PARENT(node1, tn);
616 NODE_INIT_PARENT(node0, tn);
619 put_child(tn, 2 * i + 1, node1);
620 put_child(tn, 2 * i, node0);
624 return replace(t, oldtnode, tn);
627 tnode_free(tn);
635 struct key_vector *tn;
640 tn = tnode_new(oldtnode->key, oldtnode->pos + 1, oldtnode->bits - 1);
641 if (!tn)
659 put_child(tn, i / 2, node1 ? : node0);
667 tnode_free_append(tn, inode);
672 NODE_INIT_PARENT(inode, tn);
675 put_child(tn, i / 2, inode);
679 return replace(t, oldtnode, tn);
682 tnode_free(tn);
708 static unsigned char update_suffix(struct key_vector *tn)
710 unsigned char slen = tn->pos;
715 * tn->pos + tn->bits, the second highest node will have a suffix
716 * length at most of tn->pos + tn->bits - 1
718 slen_max = min_t(unsigned char, tn->pos + tn->bits - 1, tn->slen);
723 * represent the nodes with suffix length equal to tn->pos
725 for (i = 0, stride = 0x2ul ; i < child_length(tn); i += stride) {
726 struct key_vector *n = get_child(tn, i);
741 tn->slen = slen;
759 * The left-hand side may look a bit weird: child_length(tn)
760 * - tn->empty_children is of course the number of non-null children
761 * in the current node. tn->full_children is the number of "full"
768 * to_be_doubled = tn->full_children;
769 * not_to_be_doubled = child_length(tn) - tn->empty_children -
770 * tn->full_children;
772 * new_child_length = child_length(tn) * 2;
789 * 100 * (child_length(tn) - tn->empty_children +
790 * tn->full_children) >= inflate_threshold * new_child_length
793 * 100 * (child_length(tn) - tn->empty_children +
794 * tn->full_children) >=
795 * inflate_threshold * child_length(tn) * 2
798 * 50 * (tn->full_children + child_length(tn) -
799 * tn->empty_children) >= inflate_threshold *
800 * child_length(tn)
803 static inline bool should_inflate(struct key_vector *tp, struct key_vector *tn)
805 unsigned long used = child_length(tn);
810 used -= tn_info(tn)->empty_children;
811 used += tn_info(tn)->full_children;
815 return (used > 1) && tn->pos && ((50 * used) >= threshold);
818 static inline bool should_halve(struct key_vector *tp, struct key_vector *tn)
820 unsigned long used = child_length(tn);
825 used -= tn_info(tn)->empty_children;
829 return (used > 1) && (tn->bits > 1) && ((100 * used) < threshold);
832 static inline bool should_collapse(struct key_vector *tn)
834 unsigned long used = child_length(tn);
836 used -= tn_info(tn)->empty_children;
839 if ((tn->bits == KEYLENGTH) && tn_info(tn)->full_children)
847 static struct key_vector *resize(struct trie *t, struct key_vector *tn)
852 struct key_vector *tp = node_parent(tn);
853 unsigned long cindex = get_index(tn->key, tp);
857 tn, inflate_threshold, halve_threshold);
863 BUG_ON(tn != get_child(tp, cindex));
868 while (should_inflate(tp, tn) && max_work) {
869 tp = inflate(t, tn);
878 tn = get_child(tp, cindex);
882 tp = node_parent(tn);
891 while (should_halve(tp, tn) && max_work) {
892 tp = halve(t, tn);
901 tn = get_child(tp, cindex);
905 if (should_collapse(tn))
906 return collapse(t, tn);
909 return node_parent(tn);
912 static void node_pull_suffix(struct key_vector *tn, unsigned char slen)
914 unsigned char node_slen = tn->slen;
916 while ((node_slen > tn->pos) && (node_slen > slen)) {
917 slen = update_suffix(tn);
921 tn = node_parent(tn);
922 node_slen = tn->slen;
926 static void node_push_suffix(struct key_vector *tn, unsigned char slen)
928 while (tn->slen < slen) {
929 tn->slen = slen;
930 tn = node_parent(tn);
1103 static void trie_rebalance(struct trie *t, struct key_vector *tn)
1105 while (!IS_TRIE(tn))
1106 tn = resize(t, tn);
1128 struct key_vector *tn;
1130 tn = tnode_new(key, __fls(key ^ n->key), 1);
1131 if (!tn)
1135 NODE_INIT_PARENT(tn, tp);
1136 put_child(tn, get_index(key, tn) ^ 1, n);
1139 put_child_root(tp, key, tn);
1140 node_set_parent(n, tn);
1143 tp = tn;
1784 static struct key_vector *leaf_walk_rcu(struct key_vector **tn, t_key key)
1786 struct key_vector *pn, *n = *tn;
1833 *tn = pn;
1837 *tn = pn;