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) argument
194 #define get_child(tn, i) rtnl_dereference((tn)->tnode[i]) argument
197 #define node_parent_rcu(tn) rcu_dereference_rtnl(tn_info(tn)->parent) argument
198 #define get_child_rcu(tn, i) rcu_dereference_rtnl((tn)->tnode[i]) argument
212 static inline unsigned long child_length(const struct key_vector *tn) in child_length() argument
214 return (1ul << tn->bits) & ~(1ul); in child_length()
378 struct key_vector *tn; in tnode_new() local
396 tn = tnode->kv; in tnode_new()
397 tn->key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0; in tnode_new()
398 tn->pos = pos; in tnode_new()
399 tn->bits = bits; in tnode_new()
400 tn->slen = pos; in tnode_new()
402 return tn; in tnode_new()
408 static inline int tnode_full(struct key_vector *tn, struct key_vector *n) in tnode_full() argument
410 return n && ((n->pos + n->bits) == tn->pos) && IS_TNODE(n); in tnode_full()
416 static void put_child(struct key_vector *tn, unsigned long i, in put_child() argument
419 struct key_vector *chi = get_child(tn, i); in put_child()
422 BUG_ON(i >= child_length(tn)); in put_child()
426 empty_child_inc(tn); in put_child()
428 empty_child_dec(tn); in put_child()
431 wasfull = tnode_full(tn, chi); in put_child()
432 isfull = tnode_full(tn, n); in put_child()
435 tn_info(tn)->full_children--; in put_child()
437 tn_info(tn)->full_children++; in put_child()
439 if (n && (tn->slen < n->slen)) in put_child()
440 tn->slen = n->slen; in put_child()
442 rcu_assign_pointer(tn->tnode[i], n); in put_child()
445 static void update_children(struct key_vector *tn) in update_children() argument
450 for (i = child_length(tn); i;) { in update_children()
451 struct key_vector *inode = get_child(tn, --i); in update_children()
460 if (node_parent(inode) == tn) in update_children()
463 node_set_parent(inode, tn); in update_children()
476 static inline void tnode_free_init(struct key_vector *tn) in tnode_free_init() argument
478 tn_info(tn)->rcu.next = NULL; in tnode_free_init()
481 static inline void tnode_free_append(struct key_vector *tn, in tnode_free_append() argument
484 tn_info(n)->rcu.next = tn_info(tn)->rcu.next; in tnode_free_append()
485 tn_info(tn)->rcu.next = &tn_info(n)->rcu; in tnode_free_append()
488 static void tnode_free(struct key_vector *tn) in tnode_free() argument
490 struct callback_head *head = &tn_info(tn)->rcu; in tnode_free()
494 tnode_free_size += TNODE_SIZE(1ul << tn->bits); in tnode_free()
495 node_free(tn); in tnode_free()
497 tn = container_of(head, struct tnode, rcu)->kv; in tnode_free()
508 struct key_vector *tn) in replace() argument
514 NODE_INIT_PARENT(tn, tp); in replace()
515 put_child_root(tp, tn->key, tn); in replace()
518 update_children(tn); in replace()
524 for (i = child_length(tn); i;) { in replace()
525 struct key_vector *inode = get_child(tn, --i); in replace()
528 if (tnode_full(tn, inode)) in replace()
529 tn = resize(t, inode); in replace()
538 struct key_vector *tn; in inflate() local
544 tn = tnode_new(oldtnode->key, oldtnode->pos - 1, oldtnode->bits + 1); in inflate()
545 if (!tn) in inflate()
556 for (i = child_length(oldtnode), m = 1u << tn->pos; i;) { in inflate()
567 put_child(tn, get_index(inode->key, tn), inode); in inflate()
576 put_child(tn, 2 * i + 1, get_child(inode, 1)); in inflate()
577 put_child(tn, 2 * i, get_child(inode, 0)); in inflate()
600 tnode_free_append(tn, node1); in inflate()
603 tnode_free_append(tn, node0); in inflate()
614 NODE_INIT_PARENT(node1, tn); in inflate()
615 NODE_INIT_PARENT(node0, tn); in inflate()
618 put_child(tn, 2 * i + 1, node1); in inflate()
619 put_child(tn, 2 * i, node0); in inflate()
623 return replace(t, oldtnode, tn); in inflate()
626 tnode_free(tn); in inflate()
634 struct key_vector *tn; in halve() local
639 tn = tnode_new(oldtnode->key, oldtnode->pos + 1, oldtnode->bits - 1); in halve()
640 if (!tn) in halve()
658 put_child(tn, i / 2, node1 ? : node0); in halve()
666 tnode_free_append(tn, inode); in halve()
671 NODE_INIT_PARENT(inode, tn); in halve()
674 put_child(tn, i / 2, inode); in halve()
678 return replace(t, oldtnode, tn); in halve()
681 tnode_free(tn); in halve()
707 static unsigned char update_suffix(struct key_vector *tn) in update_suffix() argument
709 unsigned char slen = tn->pos; in update_suffix()
717 slen_max = min_t(unsigned char, tn->pos + tn->bits - 1, tn->slen); in update_suffix()
724 for (i = 0, stride = 0x2ul ; i < child_length(tn); i += stride) { in update_suffix()
725 struct key_vector *n = get_child(tn, i); in update_suffix()
740 tn->slen = slen; in update_suffix()
802 static inline bool should_inflate(struct key_vector *tp, struct key_vector *tn) in should_inflate() argument
804 unsigned long used = child_length(tn); in should_inflate()
809 used -= tn_info(tn)->empty_children; in should_inflate()
810 used += tn_info(tn)->full_children; in should_inflate()
814 return (used > 1) && tn->pos && ((50 * used) >= threshold); in should_inflate()
817 static inline bool should_halve(struct key_vector *tp, struct key_vector *tn) in should_halve() argument
819 unsigned long used = child_length(tn); in should_halve()
824 used -= tn_info(tn)->empty_children; in should_halve()
828 return (used > 1) && (tn->bits > 1) && ((100 * used) < threshold); in should_halve()
831 static inline bool should_collapse(struct key_vector *tn) in should_collapse() argument
833 unsigned long used = child_length(tn); in should_collapse()
835 used -= tn_info(tn)->empty_children; in should_collapse()
838 if ((tn->bits == KEYLENGTH) && tn_info(tn)->full_children) in should_collapse()
846 static struct key_vector *resize(struct trie *t, struct key_vector *tn) in resize() argument
851 struct key_vector *tp = node_parent(tn); in resize()
852 unsigned long cindex = get_index(tn->key, tp); in resize()
856 tn, inflate_threshold, halve_threshold); in resize()
862 BUG_ON(tn != get_child(tp, cindex)); in resize()
867 while (should_inflate(tp, tn) && max_work) { in resize()
868 tp = inflate(t, tn); in resize()
877 tn = get_child(tp, cindex); in resize()
881 tp = node_parent(tn); in resize()
890 while (should_halve(tp, tn) && max_work) { in resize()
891 tp = halve(t, tn); in resize()
900 tn = get_child(tp, cindex); in resize()
904 if (should_collapse(tn)) in resize()
905 return collapse(t, tn); in resize()
908 return node_parent(tn); in resize()
911 static void node_pull_suffix(struct key_vector *tn, unsigned char slen) in node_pull_suffix() argument
913 unsigned char node_slen = tn->slen; in node_pull_suffix()
915 while ((node_slen > tn->pos) && (node_slen > slen)) { in node_pull_suffix()
916 slen = update_suffix(tn); in node_pull_suffix()
920 tn = node_parent(tn); in node_pull_suffix()
921 node_slen = tn->slen; in node_pull_suffix()
925 static void node_push_suffix(struct key_vector *tn, unsigned char slen) in node_push_suffix() argument
927 while (tn->slen < slen) { in node_push_suffix()
928 tn->slen = slen; in node_push_suffix()
929 tn = node_parent(tn); in node_push_suffix()
1056 static void trie_rebalance(struct trie *t, struct key_vector *tn) in trie_rebalance() argument
1058 while (!IS_TRIE(tn)) in trie_rebalance()
1059 tn = resize(t, tn); in trie_rebalance()
1081 struct key_vector *tn; in fib_insert_node() local
1083 tn = tnode_new(key, __fls(key ^ n->key), 1); in fib_insert_node()
1084 if (!tn) in fib_insert_node()
1088 NODE_INIT_PARENT(tn, tp); in fib_insert_node()
1089 put_child(tn, get_index(key, tn) ^ 1, n); in fib_insert_node()
1092 put_child_root(tp, key, tn); in fib_insert_node()
1093 node_set_parent(n, tn); in fib_insert_node()
1096 tp = tn; in fib_insert_node()
1733 static struct key_vector *leaf_walk_rcu(struct key_vector **tn, t_key key) in leaf_walk_rcu() argument
1735 struct key_vector *pn, *n = *tn; in leaf_walk_rcu()
1782 *tn = pn; in leaf_walk_rcu()
1786 *tn = pn; in leaf_walk_rcu()