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) argument
195 #define get_child(tn, i) rtnl_dereference((tn)->tnode[i]) argument
198 #define node_parent_rcu(tn) rcu_dereference_rtnl(tn_info(tn)->parent) argument
199 #define get_child_rcu(tn, i) rcu_dereference_rtnl((tn)->tnode[i]) argument
213 static inline unsigned long child_length(const struct key_vector *tn) in child_length() argument
215 return (1ul << tn->bits) & ~(1ul); in child_length()
381 struct key_vector *tn; in tnode_new() local
399 tn = tnode->kv; in tnode_new()
400 tn->key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0; in tnode_new()
401 tn->pos = pos; in tnode_new()
402 tn->bits = bits; in tnode_new()
403 tn->slen = pos; in tnode_new()
405 return tn; in tnode_new()
411 static inline int tnode_full(struct key_vector *tn, struct key_vector *n) in tnode_full() argument
413 return n && ((n->pos + n->bits) == tn->pos) && IS_TNODE(n); in tnode_full()
419 static void put_child(struct key_vector *tn, unsigned long i, in put_child() argument
422 struct key_vector *chi = get_child(tn, i); in put_child()
425 BUG_ON(i >= child_length(tn)); in put_child()
429 empty_child_inc(tn); in put_child()
431 empty_child_dec(tn); in put_child()
434 wasfull = tnode_full(tn, chi); in put_child()
435 isfull = tnode_full(tn, n); in put_child()
438 tn_info(tn)->full_children--; in put_child()
440 tn_info(tn)->full_children++; in put_child()
442 if (n && (tn->slen < n->slen)) in put_child()
443 tn->slen = n->slen; in put_child()
445 rcu_assign_pointer(tn->tnode[i], n); in put_child()
448 static void update_children(struct key_vector *tn) in update_children() argument
453 for (i = child_length(tn); i;) { in update_children()
454 struct key_vector *inode = get_child(tn, --i); in update_children()
463 if (node_parent(inode) == tn) in update_children()
466 node_set_parent(inode, tn); in update_children()
479 static inline void tnode_free_init(struct key_vector *tn) in tnode_free_init() argument
481 tn_info(tn)->rcu.next = NULL; in tnode_free_init()
484 static inline void tnode_free_append(struct key_vector *tn, in tnode_free_append() argument
487 tn_info(n)->rcu.next = tn_info(tn)->rcu.next; in tnode_free_append()
488 tn_info(tn)->rcu.next = &tn_info(n)->rcu; in tnode_free_append()
491 static void tnode_free(struct key_vector *tn) in tnode_free() argument
493 struct callback_head *head = &tn_info(tn)->rcu; in tnode_free()
497 tnode_free_size += TNODE_SIZE(1ul << tn->bits); in tnode_free()
498 node_free(tn); in tnode_free()
500 tn = container_of(head, struct tnode, rcu)->kv; in tnode_free()
511 struct key_vector *tn) in replace() argument
517 NODE_INIT_PARENT(tn, tp); in replace()
518 put_child_root(tp, tn->key, tn); in replace()
521 update_children(tn); in replace()
527 for (i = child_length(tn); i;) { in replace()
528 struct key_vector *inode = get_child(tn, --i); in replace()
531 if (tnode_full(tn, inode)) in replace()
532 tn = resize(t, inode); in replace()
541 struct key_vector *tn; in inflate() local
547 tn = tnode_new(oldtnode->key, oldtnode->pos - 1, oldtnode->bits + 1); in inflate()
548 if (!tn) in inflate()
559 for (i = child_length(oldtnode), m = 1u << tn->pos; i;) { in inflate()
570 put_child(tn, get_index(inode->key, tn), inode); in inflate()
579 put_child(tn, 2 * i + 1, get_child(inode, 1)); in inflate()
580 put_child(tn, 2 * i, get_child(inode, 0)); in inflate()
603 tnode_free_append(tn, node1); in inflate()
606 tnode_free_append(tn, node0); in inflate()
617 NODE_INIT_PARENT(node1, tn); in inflate()
618 NODE_INIT_PARENT(node0, tn); in inflate()
621 put_child(tn, 2 * i + 1, node1); in inflate()
622 put_child(tn, 2 * i, node0); in inflate()
626 return replace(t, oldtnode, tn); in inflate()
629 tnode_free(tn); in inflate()
637 struct key_vector *tn; in halve() local
642 tn = tnode_new(oldtnode->key, oldtnode->pos + 1, oldtnode->bits - 1); in halve()
643 if (!tn) in halve()
661 put_child(tn, i / 2, node1 ? : node0); in halve()
669 tnode_free_append(tn, inode); in halve()
674 NODE_INIT_PARENT(inode, tn); in halve()
677 put_child(tn, i / 2, inode); in halve()
681 return replace(t, oldtnode, tn); in halve()
684 tnode_free(tn); in halve()
710 static unsigned char update_suffix(struct key_vector *tn) in update_suffix() argument
712 unsigned char slen = tn->pos; in update_suffix()
720 slen_max = min_t(unsigned char, tn->pos + tn->bits - 1, tn->slen); in update_suffix()
727 for (i = 0, stride = 0x2ul ; i < child_length(tn); i += stride) { in update_suffix()
728 struct key_vector *n = get_child(tn, i); in update_suffix()
743 tn->slen = slen; in update_suffix()
805 static inline bool should_inflate(struct key_vector *tp, struct key_vector *tn) in should_inflate() argument
807 unsigned long used = child_length(tn); in should_inflate()
812 used -= tn_info(tn)->empty_children; in should_inflate()
813 used += tn_info(tn)->full_children; in should_inflate()
817 return (used > 1) && tn->pos && ((50 * used) >= threshold); in should_inflate()
820 static inline bool should_halve(struct key_vector *tp, struct key_vector *tn) in should_halve() argument
822 unsigned long used = child_length(tn); in should_halve()
827 used -= tn_info(tn)->empty_children; in should_halve()
831 return (used > 1) && (tn->bits > 1) && ((100 * used) < threshold); in should_halve()
834 static inline bool should_collapse(struct key_vector *tn) in should_collapse() argument
836 unsigned long used = child_length(tn); in should_collapse()
838 used -= tn_info(tn)->empty_children; in should_collapse()
841 if ((tn->bits == KEYLENGTH) && tn_info(tn)->full_children) in should_collapse()
849 static struct key_vector *resize(struct trie *t, struct key_vector *tn) in resize() argument
854 struct key_vector *tp = node_parent(tn); in resize()
855 unsigned long cindex = get_index(tn->key, tp); in resize()
859 tn, inflate_threshold, halve_threshold); in resize()
865 BUG_ON(tn != get_child(tp, cindex)); in resize()
870 while (should_inflate(tp, tn) && max_work) { in resize()
871 tp = inflate(t, tn); in resize()
880 tn = get_child(tp, cindex); in resize()
884 tp = node_parent(tn); in resize()
893 while (should_halve(tp, tn) && max_work) { in resize()
894 tp = halve(t, tn); in resize()
903 tn = get_child(tp, cindex); in resize()
907 if (should_collapse(tn)) in resize()
908 return collapse(t, tn); in resize()
911 return node_parent(tn); in resize()
914 static void node_pull_suffix(struct key_vector *tn, unsigned char slen) in node_pull_suffix() argument
916 unsigned char node_slen = tn->slen; in node_pull_suffix()
918 while ((node_slen > tn->pos) && (node_slen > slen)) { in node_pull_suffix()
919 slen = update_suffix(tn); in node_pull_suffix()
923 tn = node_parent(tn); in node_pull_suffix()
924 node_slen = tn->slen; in node_pull_suffix()
928 static void node_push_suffix(struct key_vector *tn, unsigned char slen) in node_push_suffix() argument
930 while (tn->slen < slen) { in node_push_suffix()
931 tn->slen = slen; in node_push_suffix()
932 tn = node_parent(tn); in node_push_suffix()
1008 static void trie_rebalance(struct trie *t, struct key_vector *tn) in trie_rebalance() argument
1010 while (!IS_TRIE(tn)) in trie_rebalance()
1011 tn = resize(t, tn); in trie_rebalance()
1033 struct key_vector *tn; in fib_insert_node() local
1035 tn = tnode_new(key, __fls(key ^ n->key), 1); in fib_insert_node()
1036 if (!tn) in fib_insert_node()
1040 NODE_INIT_PARENT(tn, tp); in fib_insert_node()
1041 put_child(tn, get_index(key, tn) ^ 1, n); in fib_insert_node()
1044 put_child_root(tp, key, tn); in fib_insert_node()
1045 node_set_parent(n, tn); in fib_insert_node()
1048 tp = tn; in fib_insert_node()
1619 static struct key_vector *leaf_walk_rcu(struct key_vector **tn, t_key key) in leaf_walk_rcu() argument
1621 struct key_vector *pn, *n = *tn; in leaf_walk_rcu()
1668 *tn = pn; in leaf_walk_rcu()
1672 *tn = pn; in leaf_walk_rcu()