92 #define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)  argument
97 struct node {  struct
127 	struct node *child[0];
152 	struct node *trie;
158 static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n);
159 static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n,
161 static struct node *resize(struct trie *t, struct tnode *tn);
168 static inline struct tnode *node_parent(struct node *node)  in node_parent()  argument
170 	return (struct tnode *)(node->parent & ~NODE_TYPE_MASK);  in node_parent()
173 static inline struct tnode *node_parent_rcu(struct node *node)  in node_parent_rcu()  argument
175 	struct tnode *ret = node_parent(node);  in node_parent_rcu()
183 static inline void node_set_parent(struct node *node, struct tnode *ptr)  in node_set_parent()  argument
186 	node->parent = (unsigned long)ptr | NODE_TYPE(node);  in node_set_parent()
189 static inline struct node *tnode_get_child(struct tnode *tn, unsigned int i)  in tnode_get_child()
196 static inline struct node *tnode_get_child_rcu(struct tnode *tn, unsigned int i)  in tnode_get_child_rcu()
198 	struct node *ret = tnode_get_child(tn, i);  in tnode_get_child_rcu()
370 		      (sizeof(struct node *) << tn->bits);  in __tnode_free_rcu()
410 	size_t sz = sizeof(struct tnode) + (sizeof(struct node *) << bits);  in tnode_new()
423 		 (unsigned long) (sizeof(struct node) << bits));  in tnode_new()
432 static inline int tnode_full(const struct tnode *tn, const struct node *n)  in tnode_full()
441 			     struct node *n)  in put_child()
451 static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n,  in tnode_put_child_reorg()
454 	struct node *chi = tn->child[i];  in tnode_put_child_reorg()
481 static struct node *resize(struct trie *t, struct tnode *tn)  in resize()
504 			struct node *n;  in resize()
664 			struct node *n;  in resize()
677 	return (struct node *) tn;  in resize()
724 			put_child(t, tn, 2*i, (struct node *) left);  in inflate()
725 			put_child(t, tn, 2*i+1, (struct node *) right);  in inflate()
731 		struct node *node = tnode_get_child(oldtnode, i);  in inflate()  local
736 		if (node == NULL)  in inflate()
741 		if (IS_LEAF(node) || ((struct tnode *) node)->pos >  in inflate()
743 			if (tkey_extract_bits(node->key,  in inflate()
746 				put_child(t, tn, 2*i, node);  in inflate()
748 				put_child(t, tn, 2*i+1, node);  in inflate()
753 		inode = (struct tnode *) node;  in inflate()
826 	struct node *left, *right;  in halve()
857 			put_child(t, tn, i/2, (struct node *)newn);  in halve()
911 	struct hlist_node *node;  in find_leaf_info()  local
914 	hlist_for_each_entry_rcu(li, node, head, hlist)  in find_leaf_info()
934 	struct hlist_node *node;  in insert_leaf_info()  local
939 		hlist_for_each_entry(li, node, head, hlist) {  in insert_leaf_info()
959 	struct node *n;  in fib_find_node()
986 static struct node *trie_rebalance(struct trie *t, struct tnode *tn)  in trie_rebalance()
992 	while (tn != NULL && (tp = node_parent((struct node *)tn)) != NULL) {  in trie_rebalance()
998 				      (struct node *)tn, wasfull);  in trie_rebalance()
1000 		tp = node_parent((struct node *) tn);  in trie_rebalance()
1010 	return (struct node *)tn;  in trie_rebalance()
1019 	struct node *n;  in fib_insert_node()
1105 		node_set_parent((struct node *)l, tp);  in fib_insert_node()
1108 		put_child(t, (struct tnode *)tp, cindex, (struct node *)l);  in fib_insert_node()
1135 		node_set_parent((struct node *)tn, tp);  in fib_insert_node()
1138 		put_child(t, tn, missbit, (struct node *)l);  in fib_insert_node()
1144 				  (struct node *)tn);  in fib_insert_node()
1146 			rcu_assign_pointer(t->trie, (struct node *)tn);  in fib_insert_node()
1340 	struct hlist_node *node;  in check_leaf()  local
1342 	hlist_for_each_entry_rcu(li, node, hhead, hlist) {  in check_leaf()
1371 	struct node *n;  in fn_trie_lookup()
1544 			struct tnode *parent = node_parent((struct node *) pn);  in fn_trie_lookup()
1571 	struct tnode *tp = node_parent((struct node *) l);  in trie_leaf_remove()
1691 	struct hlist_node *node, *tmp;  in trie_flush_leaf()  local
1694 	hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {  in trie_flush_leaf()
1709 static struct leaf *leaf_walk_rcu(struct tnode *p, struct node *c)  in leaf_walk_rcu()
1735 		c = (struct node *) p;  in leaf_walk_rcu()
1756 	struct node *c = (struct node *) l;  in trie_nextleaf()
1915 	struct hlist_node *node;  in fn_trie_dump_leaf()  local
1922 	hlist_for_each_entry_rcu(li, node, &l->list, hlist) {  in fn_trie_dump_leaf()
2039 static struct node *fib_trie_get_next(struct fib_trie_iter *iter)  in fib_trie_get_next()
2053 		struct node *n = tnode_get_child_rcu(tn, cindex);  in fib_trie_get_next()
2072 	p = node_parent_rcu((struct node *)tn);  in fib_trie_get_next()
2084 static struct node *fib_trie_get_first(struct fib_trie_iter *iter,  in fib_trie_get_first()
2087 	struct node *n;  in fib_trie_get_first()
2111 	struct node *n;  in trie_collect_stats()
2184 	bytes += sizeof(struct node *) * pointers;  in trie_show_stats()
2229 		struct hlist_node *node;  in fib_triestat_seq_show()  local
2232 		hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {  in fib_triestat_seq_show()
2265 static struct node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)  in fib_trie_get_idx()
2274 		struct hlist_node *node;  in fib_trie_get_idx()  local
2277 		hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {  in fib_trie_get_idx()
2278 			struct node *n;  in fib_trie_get_idx()
2307 	struct node *n;  in fib_trie_seq_next()
2392 	struct node *n = v;  in fib_trie_seq_show()
2409 		struct hlist_node *node;  in fib_trie_seq_show()  local
2415 		hlist_for_each_entry_rcu(li, node, &l->list, hlist) {  in fib_trie_seq_show()
2561 	struct hlist_node *node;  in fib_route_seq_show()  local
2570 	hlist_for_each_entry_rcu(li, node, &l->list, hlist) {  in fib_route_seq_show()