bsd/net/radix.c

112 		rn_new_radix_mask(struct radix_node *tt,
400 	struct radix_node *tt = nodes, *t = tt + 1;
403 	t->rn_left = tt;
405 	tt->rn_bit = -1;
406 	tt->rn_key = (caddr_t)v;
407 	tt->rn_parent = t;
408 	tt->rn_flags = t->rn_flags = RNF_ACTIVE;
409 	tt->rn_mklist = t->rn_mklist = NULL;
411 	tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++;
412 	tt->rn_twin = t;
413 	tt->rn_ybro = rn_clist;
414 	rn_clist = tt;
429 	struct radix_node *tt;
465 	tt = t->rn_left;
475 		t->rn_right = tt;
483 	return (tt);
573 rn_new_radix_mask(struct radix_node *tt, struct radix_mask *next)
583 	m->rm_bit = tt->rn_bit;
584 	m->rm_flags = tt->rn_flags;
585 	if (tt->rn_flags & RNF_NORMAL)
586 		m->rm_leaf = tt;
588 		m->rm_mask = tt->rn_mask;
590 	tt->rn_mklist = m;
599 	struct radix_node *t, *x = NULL, *tt;
623 	saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes);
625 		for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) {
626 			if (tt->rn_mask == netmask)
629 			    (tt->rn_mask &&
630 			     ((b_leaf < tt->rn_bit) /* index(netmask) > node */
631 			      || rn_refines(netmask, tt->rn_mask)
632 			      || rn_lexobetter(netmask, tt->rn_mask))))
645 		if (tt == saved_tt) {
648 			(tt = treenodes)->rn_dupedkey = t;
649 			tt->rn_flags = t->rn_flags;
650 			tt->rn_parent = x = t->rn_parent;
651 			t->rn_parent = tt;	 		/* parent */
653 				x->rn_left = tt;
655 				x->rn_right = tt;
656 			saved_tt = tt; x = xx;
658 			(tt = treenodes)->rn_dupedkey = t->rn_dupedkey;
659 			t->rn_dupedkey = tt;
660 			tt->rn_parent = t;			/* parent */
661 			if (tt->rn_dupedkey)			/* parent */
662 				tt->rn_dupedkey->rn_parent = tt; /* parent */
665 		t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++;
666 		tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt;
668 		tt->rn_key = (caddr_t) v;
669 		tt->rn_bit = -1;
670 		tt->rn_flags = RNF_ACTIVE;
677 		tt->rn_mask = netmask;
678 		tt->rn_bit = x->rn_bit;
679 		tt->rn_flags |= x->rn_flags & RNF_NORMAL;
709 		return tt; /* can't lift at all */
710 	b_leaf = tt->rn_bit;
728 			if (tt->rn_flags & RNF_NORMAL) {
731 				return tt;
737 			tt->rn_mklist = m;
738 			return tt;
744 	*mp = rn_new_radix_mask(tt, *mp);
745 	return tt;
751 	struct radix_node *t, *p, *x, *tt;
760 	tt = rn_search(v, x);
763 	saved_tt = tt;
765 	if (tt == 0 ||
766 	    Bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off))
775 		while (tt->rn_mask != netmask)
776 			if ((tt = tt->rn_dupedkey) == 0)
779 	if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0)
781 	if (tt->rn_flags & RNF_NORMAL) {
782 		if (m->rm_leaf != tt || m->rm_refs > 0) {
787 		if (m->rm_mask != tt->rn_mask) {
794 	b = -1 - tt->rn_bit;
810 		if (tt->rn_flags & RNF_NORMAL)
817 	if (tt->rn_flags & RNF_ROOT)
822 	for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {}
823 	if (t) t->rn_ybro = tt->rn_ybro;
825 	t = tt->rn_parent;
829 		 * at this point, tt is the deletion target and saved_tt
832 		if (tt == saved_tt) {
835 			if (t->rn_left == tt)
840 			/* find node in front of tt on the chain */
841 			for (x = p = saved_tt; p && p->rn_dupedkey != tt;)
844 				p->rn_dupedkey = tt->rn_dupedkey;
845 				if (tt->rn_dupedkey)		/* parent */
846 					tt->rn_dupedkey->rn_parent = p;
850 		t = tt + 1;
870 	if (t->rn_left == tt)
909 	x = tt + 1;
927 	tt->rn_flags &= ~RNF_ACTIVE;
928 	tt[1].rn_flags &= ~RNF_ACTIVE;
929 	return (tt);
1118 	struct radix_node *t, *tt, *ttt;
1130 	tt = t->rn_left;
1131 	tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE;
1132 	tt->rn_bit = -1 - off;
1133 	*ttt = *tt;