net/patricia/radix.c

128  * branching removed.  The index rn_bit at an internal node n represents a bit
130  * of a node n have keys whose bits all agree up to position rn_bit - 1.
131  * (We say the index of n is rn_bit.)
133  * There is at least one descendant which has a one bit at position rn_bit,
143  * If a node n has a descendant (k, m) with index(m) == index(n) == rn_bit,
145  * If the index(m) < rn_bit, this implies the trailing last few bits of k
183 	for (x = head, v = v_arg; x->rn_bit >= 0; ) {
203 	for (x = head; x->rn_bit >= 0; ) {
324 	int test, b, rn_bit;
330 	for (; t->rn_bit >= 0; ) {
386 	rn_bit = -1 - b;
401 			if ((rn_bit <= t->rn_bit) &&
425 				if ((rn_bit <= m->rm_bit) &&
464 	t->rn_bit = b;
473 	tt->rn_bit = -1;
530 	} while (b > (unsigned)x->rn_bit);
531 			/* x->rn_bit < b && x->rn_bit >= 0 */
534 	 * x->rn_bit.
536 	 * We will add a new branch at p.  b cannot equal x->rn_bit
638 	x->rn_bit = -1 - b;
676 	m->rm_bit = tt->rn_bit;
711 		b_leaf = x->rn_bit;
712 		b = -1 - x->rn_bit;
726 			    ((b_leaf < tt->rn_bit) ||
767 		tt->rn_bit = -1;
775 		tt->rn_bit = x->rn_bit;
795 	b_leaf = -1 - t->rn_bit;
797 	 * b_leaf is now normalized to be in the leaf rn_bit format
798 	 * (it is the rn_bit value of a leaf corresponding to netmask
799 	 * of t->rn_bit).
809 	if (x->rn_bit < 0) {
812 			if (x->rn_mask && (x->rn_bit >= b_leaf) &&
837 	if ((netmask == 0) || (b > t->rn_bit))
839 	b_leaf = tt->rn_bit;
844 	} while (b <= t->rn_bit && x != top);
942 	b = -1 - tt->rn_bit;
944 	if (b > t->rn_bit)
949 	} while (b <= t->rn_bit && x != top);
1030 		if (x->rn_bit >= 0) {
1120 	while (rn->rn_bit >= 0) {
1135 		for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0; ) {
1209 	tt->rn_bit = -1 - off;