bsd/net/radix.c

121  * branching removed.  The index rn_bit at an internal node n represents a bit
123  * of a node n have keys whose bits all agree up to position rn_bit - 1.
124  * (We say the index of n is rn_bit.)
126  * There is at least one descendant which has a one bit at position rn_bit,
136  * If a node n has a descendant (k, m) with index(m) == index(n) == rn_bit,
138  * If the index(m) < rn_bit, this implies the trailing last few bits of k
159 	for (x = head, v = v_arg; x->rn_bit >= 0;) {
174 	for (x = head; x->rn_bit >= 0;) {
280 	int test, b, rn_bit;
286 	for (; t->rn_bit >= 0; ) {
340 	rn_bit = -1 - b;
353 			if ((rn_bit <= t->rn_bit) && RN_MATCHF(t, f, w))
373 				if ((rn_bit <= m->rm_bit) &&
401 	t->rn_bit = b;
405 	tt->rn_bit = -1;
458 	} while (b > (unsigned) x->rn_bit);
459 				/* x->rn_bit < b && x->rn_bit >= 0 */
552 	x->rn_bit = -1 - b;
583 	m->rm_bit = tt->rn_bit;
616 		b_leaf = x->rn_bit;
617 		b = -1 - x->rn_bit;
630 			     ((b_leaf < tt->rn_bit) /* index(netmask) > node */
669 		tt->rn_bit = -1;
678 		tt->rn_bit = x->rn_bit;
684 	b_leaf = -1 - t->rn_bit;
690 	if (x->rn_bit < 0) {
692 		if (x->rn_mask && (x->rn_bit >= b_leaf) && x->rn_mklist == 0) {
708 	if ((netmask == 0) || (b > t->rn_bit ))
710 	b_leaf = tt->rn_bit;
714 	} while (b <= t->rn_bit && x != top);
794 	b = -1 - tt->rn_bit;
796 	if (b > t->rn_bit)
801 	} while (b <= t->rn_bit && x != top);
884 		if (x->rn_bit >= 0) {
968 	for (rn = h->rnh_treetop; rn->rn_bit >= 0; ) {
986 	lastb = rn->rn_bit;
989 	while (rn->rn_bit >= 0)
1000 			if (rn->rn_bit <= lastb) {
1041 		for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;)
1085 	while (rn->rn_bit >= 0)
1094 		for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;)
1132 	tt->rn_bit = -1 - off;