/* 
/* 
static struct node *resize(struct trie *t, struct tnode *tn) {	int i;	int err = 0; 	if (!tn)		return NULL;	if(trie_debug) 		printk("In tnode_resize %p inflate_threshold=%d threshold=%d\n", 		      tn, inflate_threshold, halve_threshold);	/* No children */	if (tn->empty_children == tnode_child_length(tn)) {		tnode_free(tn);		return NULL;	}	/* One child */	if (tn->empty_children == tnode_child_length(tn) - 1)		for (i = 0; i < tnode_child_length(tn); i++) {			write_lock_bh(&fib_lock);			if (tn->child[i] != NULL) {				/* compress one level */				struct node *n = tn->child[i];				if(n)					NODE_INIT_PARENT(n, NODE_TYPE(n));				write_unlock_bh(&fib_lock);				tnode_free(tn);				return n;			}			write_unlock_bh(&fib_lock);		}	/* 	 * Double as long as the resulting node has a number of	 * nonempty nodes that are above the threshold.	 */	/*	 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of 	 * the Helsinki University of Technology and Matti Tikkanen of Nokia 	 * Telecommunications, page 6:	 * "A node is doubled if the ratio of non-empty children to all 	 * children in the *doubled* node is at least 'high'."	 *	 * 'high' in this instance is the variable 'inflate_threshold'. It 	 * is expressed as a percentage, so we multiply it with 	 * tnode_child_length() and instead of multiplying by 2 (since the 	 * child array will be doubled by inflate()) and multiplying 	 * the left-hand side by 100 (to handle the percentage thing) we 	 * multiply the left-hand side by 50.	 * 	 * The left-hand side may look a bit weird: tnode_child_length(tn) 	 * - tn->empty_children is of course the number of non-null children 	 * in the current node. tn->full_children is the number of "full" 	 * children, that is non-null tnodes with a skip value of 0.	 * All of those will be doubled in the resulting inflated tnode, so 	 * we just count them one extra time here.	 * 	 * A clearer way to write this would be:	 * 	 * to_be_doubled = tn->full_children;	 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children - 	 *     tn->full_children;	 *	 * new_child_length = tnode_child_length(tn) * 2;	 *	 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) / 	 *      new_child_length;	 * if (new_fill_factor >= inflate_threshold)	 * 	 * ...and so on, tho it would mess up the while() loop.	 * 	 * anyway,	 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=	 *      inflate_threshold	 * 	 * avoid a division:	 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=	 *      inflate_threshold * new_child_length	 * 	 * expand not_to_be_doubled and to_be_doubled, and shorten:	 * 100 * (tnode_child_length(tn) - tn->empty_children + 	 *    tn->full_children ) >= inflate_threshold * new_child_length	 * 	 * expand new_child_length:	 * 100 * (tnode_child_length(tn) - tn->empty_children + 	 *    tn->full_children ) >=	 *      inflate_threshold * tnode_child_length(tn) * 2	 * 	 * shorten again:	 * 50 * (tn->full_children + tnode_child_length(tn) - 	 *    tn->empty_children ) >= inflate_threshold * 	 *    tnode_child_length(tn)	 * 	 */	check_tnode(tn);		err = 0;	while ((tn->full_children > 0 &&	       50 * (tn->full_children + tnode_child_length(tn) - tn->empty_children) >=				inflate_threshold * tnode_child_length(tn))) {		tn = inflate(t, tn, &err);		if(err) {#ifdef CONFIG_IP_FIB_TRIE_STATS			t->stats.resize_node_skipped++;#endif			break;		}	}	check_tnode(tn);	/*	 * Halve as long as the number of empty children in this	 * node is above threshold.	 */	err = 0;	while (tn->bits > 1 &&	       100 * (tnode_child_length(tn) - tn->empty_children) <	       halve_threshold * tnode_child_length(tn)) {		tn = halve(t, tn, &err);		if(err) {#ifdef CONFIG_IP_FIB_TRIE_STATS			t->stats.resize_node_skipped++;#endif			break;		}	}  	/* Only one child remains */	if (tn->empty_children == tnode_child_length(tn) - 1)		for (i = 0; i < tnode_child_length(tn); i++) {						write_lock_bh(&fib_lock);			if (tn->child[i] != NULL) {				/* compress one level */				struct node *n = tn->child[i];				if(n)					NODE_INIT_PARENT(n, NODE_TYPE(n));				write_unlock_bh(&fib_lock);				tnode_free(tn);				return n;			}			write_unlock_bh(&fib_lock);		}	return (struct node *) tn;}
10457	/local/tlutelli/issta_data/temp/c/2005_temp/2005/10457/c877efb207bf4629cfa97ac13412f7392a873485/fib_trie.c/clean/net/ipv4/fib_trie.c