Lines Matching full:tn
174 static struct key_vector *resize(struct trie *t, struct key_vector *tn);
195 #define node_parent(tn) rtnl_dereference(tn_info(tn)->parent) argument
196 #define get_child(tn, i) rtnl_dereference((tn)->tnode[i]) argument
199 #define node_parent_rcu(tn) rcu_dereference_rtnl(tn_info(tn)->parent) argument
200 #define get_child_rcu(tn, i) rcu_dereference_rtnl((tn)->tnode[i]) argument
214 static inline unsigned long child_length(const struct key_vector *tn) in child_length() argument
216 return (1ul << tn->bits) & ~(1ul); in child_length()
374 struct key_vector *tn; in tnode_new() local
392 tn = tnode->kv; in tnode_new()
393 tn->key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0; in tnode_new()
394 tn->pos = pos; in tnode_new()
395 tn->bits = bits; in tnode_new()
396 tn->slen = pos; in tnode_new()
398 return tn; in tnode_new()
404 static inline int tnode_full(struct key_vector *tn, struct key_vector *n) in tnode_full() argument
406 return n && ((n->pos + n->bits) == tn->pos) && IS_TNODE(n); in tnode_full()
412 static void put_child(struct key_vector *tn, unsigned long i, in put_child() argument
415 struct key_vector *chi = get_child(tn, i); in put_child()
418 BUG_ON(i >= child_length(tn)); in put_child()
422 empty_child_inc(tn); in put_child()
424 empty_child_dec(tn); in put_child()
427 wasfull = tnode_full(tn, chi); in put_child()
428 isfull = tnode_full(tn, n); in put_child()
431 tn_info(tn)->full_children--; in put_child()
433 tn_info(tn)->full_children++; in put_child()
435 if (n && (tn->slen < n->slen)) in put_child()
436 tn->slen = n->slen; in put_child()
438 rcu_assign_pointer(tn->tnode[i], n); in put_child()
441 static void update_children(struct key_vector *tn) in update_children() argument
446 for (i = child_length(tn); i;) { in update_children()
447 struct key_vector *inode = get_child(tn, --i); in update_children()
456 if (node_parent(inode) == tn) in update_children()
459 node_set_parent(inode, tn); in update_children()
472 static inline void tnode_free_init(struct key_vector *tn) in tnode_free_init() argument
474 tn_info(tn)->rcu.next = NULL; in tnode_free_init()
477 static inline void tnode_free_append(struct key_vector *tn, in tnode_free_append() argument
480 tn_info(n)->rcu.next = tn_info(tn)->rcu.next; in tnode_free_append()
481 tn_info(tn)->rcu.next = &tn_info(n)->rcu; in tnode_free_append()
484 static void tnode_free(struct key_vector *tn) in tnode_free() argument
486 struct callback_head *head = &tn_info(tn)->rcu; in tnode_free()
490 tnode_free_size += TNODE_SIZE(1ul << tn->bits); in tnode_free()
491 node_free(tn); in tnode_free()
493 tn = container_of(head, struct tnode, rcu)->kv; in tnode_free()
504 struct key_vector *tn) in replace() argument
510 NODE_INIT_PARENT(tn, tp); in replace()
511 put_child_root(tp, tn->key, tn); in replace()
514 update_children(tn); in replace()
520 for (i = child_length(tn); i;) { in replace()
521 struct key_vector *inode = get_child(tn, --i); in replace()
524 if (tnode_full(tn, inode)) in replace()
525 tn = resize(t, inode); in replace()
534 struct key_vector *tn; in inflate() local
540 tn = tnode_new(oldtnode->key, oldtnode->pos - 1, oldtnode->bits + 1); in inflate()
541 if (!tn) in inflate()
552 for (i = child_length(oldtnode), m = 1u << tn->pos; i;) { in inflate()
563 put_child(tn, get_index(inode->key, tn), inode); in inflate()
572 put_child(tn, 2 * i + 1, get_child(inode, 1)); in inflate()
573 put_child(tn, 2 * i, get_child(inode, 0)); in inflate()
587 * (tn->pos) - is the one that will differ between in inflate()
596 tnode_free_append(tn, node1); in inflate()
599 tnode_free_append(tn, node0); in inflate()
610 NODE_INIT_PARENT(node1, tn); in inflate()
611 NODE_INIT_PARENT(node0, tn); in inflate()
614 put_child(tn, 2 * i + 1, node1); in inflate()
615 put_child(tn, 2 * i, node0); in inflate()
619 return replace(t, oldtnode, tn); in inflate()
622 tnode_free(tn); in inflate()
630 struct key_vector *tn; in halve() local
635 tn = tnode_new(oldtnode->key, oldtnode->pos + 1, oldtnode->bits - 1); in halve()
636 if (!tn) in halve()
654 put_child(tn, i / 2, node1 ? : node0); in halve()
662 tnode_free_append(tn, inode); in halve()
667 NODE_INIT_PARENT(inode, tn); in halve()
670 put_child(tn, i / 2, inode); in halve()
674 return replace(t, oldtnode, tn); in halve()
677 tnode_free(tn); in halve()
703 static unsigned char update_suffix(struct key_vector *tn) in update_suffix() argument
705 unsigned char slen = tn->pos; in update_suffix()
710 * tn->pos + tn->bits, the second highest node will have a suffix in update_suffix()
711 * length at most of tn->pos + tn->bits - 1 in update_suffix()
713 slen_max = min_t(unsigned char, tn->pos + tn->bits - 1, tn->slen); in update_suffix()
718 * represent the nodes with suffix length equal to tn->pos in update_suffix()
720 for (i = 0, stride = 0x2ul ; i < child_length(tn); i += stride) { in update_suffix()
721 struct key_vector *n = get_child(tn, i); in update_suffix()
736 tn->slen = slen; in update_suffix()
754 * The left-hand side may look a bit weird: child_length(tn)
755 * - tn->empty_children is of course the number of non-null children
756 * in the current node. tn->full_children is the number of "full"
763 * to_be_doubled = tn->full_children;
764 * not_to_be_doubled = child_length(tn) - tn->empty_children -
765 * tn->full_children;
767 * new_child_length = child_length(tn) * 2;
784 * 100 * (child_length(tn) - tn->empty_children +
785 * tn->full_children) >= inflate_threshold * new_child_length
788 * 100 * (child_length(tn) - tn->empty_children +
789 * tn->full_children) >=
790 * inflate_threshold * child_length(tn) * 2
793 * 50 * (tn->full_children + child_length(tn) -
794 * tn->empty_children) >= inflate_threshold *
795 * child_length(tn)
798 static inline bool should_inflate(struct key_vector *tp, struct key_vector *tn) in should_inflate() argument
800 unsigned long used = child_length(tn); in should_inflate()
805 used -= tn_info(tn)->empty_children; in should_inflate()
806 used += tn_info(tn)->full_children; in should_inflate()
810 return (used > 1) && tn->pos && ((50 * used) >= threshold); in should_inflate()
813 static inline bool should_halve(struct key_vector *tp, struct key_vector *tn) in should_halve() argument
815 unsigned long used = child_length(tn); in should_halve()
820 used -= tn_info(tn)->empty_children; in should_halve()
824 return (used > 1) && (tn->bits > 1) && ((100 * used) < threshold); in should_halve()
827 static inline bool should_collapse(struct key_vector *tn) in should_collapse() argument
829 unsigned long used = child_length(tn); in should_collapse()
831 used -= tn_info(tn)->empty_children; in should_collapse()
834 if ((tn->bits == KEYLENGTH) && tn_info(tn)->full_children) in should_collapse()
842 static struct key_vector *resize(struct trie *t, struct key_vector *tn) in resize() argument
847 struct key_vector *tp = node_parent(tn); in resize()
848 unsigned long cindex = get_index(tn->key, tp); in resize()
852 tn, inflate_threshold, halve_threshold); in resize()
858 BUG_ON(tn != get_child(tp, cindex)); in resize()
863 while (should_inflate(tp, tn) && max_work) { in resize()
864 tp = inflate(t, tn); in resize()
873 tn = get_child(tp, cindex); in resize()
877 tp = node_parent(tn); in resize()
886 while (should_halve(tp, tn) && max_work) { in resize()
887 tp = halve(t, tn); in resize()
896 tn = get_child(tp, cindex); in resize()
900 if (should_collapse(tn)) in resize()
901 return collapse(t, tn); in resize()
904 return node_parent(tn); in resize()
907 static void node_pull_suffix(struct key_vector *tn, unsigned char slen) in node_pull_suffix() argument
909 unsigned char node_slen = tn->slen; in node_pull_suffix()
911 while ((node_slen > tn->pos) && (node_slen > slen)) { in node_pull_suffix()
912 slen = update_suffix(tn); in node_pull_suffix()
916 tn = node_parent(tn); in node_pull_suffix()
917 node_slen = tn->slen; in node_pull_suffix()
921 static void node_push_suffix(struct key_vector *tn, unsigned char slen) in node_push_suffix() argument
923 while (tn->slen < slen) { in node_push_suffix()
924 tn->slen = slen; in node_push_suffix()
925 tn = node_parent(tn); in node_push_suffix()
1098 static void trie_rebalance(struct trie *t, struct key_vector *tn) in trie_rebalance() argument
1100 while (!IS_TRIE(tn)) in trie_rebalance()
1101 tn = resize(t, tn); in trie_rebalance()
1123 struct key_vector *tn; in fib_insert_node() local
1125 tn = tnode_new(key, __fls(key ^ n->key), 1); in fib_insert_node()
1126 if (!tn) in fib_insert_node()
1130 NODE_INIT_PARENT(tn, tp); in fib_insert_node()
1131 put_child(tn, get_index(key, tn) ^ 1, n); in fib_insert_node()
1134 put_child_root(tp, key, tn); in fib_insert_node()
1135 node_set_parent(n, tn); in fib_insert_node()
1138 tp = tn; in fib_insert_node()
1757 static struct key_vector *leaf_walk_rcu(struct key_vector **tn, t_key key) in leaf_walk_rcu() argument
1759 struct key_vector *pn, *n = *tn; in leaf_walk_rcu()
1806 *tn = pn; in leaf_walk_rcu()
1810 *tn = pn; in leaf_walk_rcu()