sync with NetBSD, mostly a Lite2 merge.

ok itojun@

1 files changed, 51 insertions, 24 deletions

diff --git a/sys/net/radix.c b/sys/net/radix.c
index 92d7022a845..97a85d7c49f 100644
--- a/sys/net/radix.c
+++ b/sys/net/radix.c
@@ -1,5 +1,5 @@
-/*	$OpenBSD: radix.c,v 1.15 2004/04/25 00:31:40 itojun Exp $	*/
-/*	$NetBSD: radix.c,v 1.11 1996/03/16 23:55:36 christos Exp $	*/
+/*	$OpenBSD: radix.c,v 1.16 2004/04/25 01:38:10 brad Exp $	*/
+/*	$NetBSD: radix.c,v 1.20 2003/08/07 16:32:56 agc Exp $	*/
 
 /*
  * Copyright (c) 1988, 1989, 1993
@@ -29,12 +29,14 @@
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  *
- *	@(#)radix.c	8.4 (Berkeley) 11/2/94
+ *	@(#)radix.c	8.6 (Berkeley) 10/17/95
  */
 
 /*
  * Routines to build and maintain radix trees for routing lookups.
  */
+
+#ifndef _NET_RADIX_H_
 #include <sys/param.h>
 #ifdef _KERNEL
 #include <sys/systm.h>
@@ -43,11 +45,10 @@
 #include <sys/domain.h>
 #else
 #include <stdlib.h>
-#include <stdlib.h>
-#include <string.h>
 #endif
 #include <sys/syslog.h>
 #include <net/radix.h>
+#endif
 
 int	max_keylen;
 struct radix_mask *rn_mkfreelist;
@@ -60,11 +61,11 @@ static char *rn_zeros, *rn_ones;
 #undef Bcmp
 #define Bcmp(a, b, l) (l == 0 ? 0 : bcmp((caddr_t)(a), (caddr_t)(b), (u_long)l))
 
-
 static int rn_satisfies_leaf(char *, struct radix_node *, int);
 static int rn_lexobetter(void *, void *);
 static struct radix_mask *rn_new_radix_mask(struct radix_node *,
-						 struct radix_mask *);
+    struct radix_mask *);
+
 /*
  * The data structure for the keys is a radix tree with one way
  * branching removed.  The index rn_b at an internal node n represents a bit
@@ -278,7 +279,8 @@ on1:
 	do {
 		struct radix_mask *m;
 		t = t->rn_p;
-		if ((m = t->rn_mklist) != NULL) {
+		m = t->rn_mklist;
+		if (m) {
 			/*
 			 * If non-contiguous masks ever become important
 			 * we can restore the masking and open coding of
@@ -297,7 +299,8 @@ on1:
 					if (x && rn_satisfies_leaf(v, x, off))
 						return x;
 				}
-			} while ((m = m->rm_mklist) != NULL);
+				m = m->rm_mklist;
+			} while (m);
 		}
 	} while (t != top);
 	return 0;
@@ -454,7 +457,7 @@ rn_addmask(n_arg, search, skip)
 	Bcopy(addmask_key, cp, mlen);
 	x = rn_insert(cp, mask_rnhead, &maskduplicated, x);
 	if (maskduplicated) {
-		log(LOG_ERR, "rn_addmask: mask impossibly already in tree");
+		log(LOG_ERR, "rn_addmask: mask impossibly already in tree\n");
 		Free(saved_x);
 		return (x);
 	}
@@ -569,6 +572,9 @@ rn_addroute(v_arg, n_arg, head, treenodes)
 		 * in a masklist -- most specific to least specific.
 		 * This may require the unfortunate nuisance of relocating
 		 * the head of the list.
+		 *
+		 * We also reverse, or doubly link the list through the
+		 * parent pointer.
 		 */
 		if (tt == saved_tt) {
 			struct	radix_node *xx = x;
@@ -576,6 +582,7 @@ rn_addroute(v_arg, n_arg, head, treenodes)
 			(tt = treenodes)->rn_dupedkey = t;
 			tt->rn_flags = t->rn_flags;
 			tt->rn_p = x = t->rn_p;
+			t->rn_p = tt;
 			if (x->rn_l == t)
 				x->rn_l = tt;
 			else
@@ -585,6 +592,9 @@ rn_addroute(v_arg, n_arg, head, treenodes)
 		} else {
 			(tt = treenodes)->rn_dupedkey = t->rn_dupedkey;
 			t->rn_dupedkey = tt;
+			tt->rn_p = t;
+			if (tt->rn_dupedkey)
+				tt->rn_dupedkey->rn_p = tt;
 		}
 #ifdef RN_DEBUG
 		t=tt+1;
@@ -626,7 +636,7 @@ rn_addroute(v_arg, n_arg, head, treenodes)
 		/*
 		 * Skip over masks whose index is > that of new node
 		 */
-		for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist)
+		for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist)
 			if (m->rm_b >= b_leaf)
 				break;
 		t->rn_mklist = m;
@@ -647,7 +657,7 @@ on2:
 	 * Need same criteria as when sorting dupedkeys to avoid
 	 * double loop on deletion.
 	 */
-	for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist) {
+	for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) {
 		if (m->rm_b < b_leaf)
 			continue;
 		if (m->rm_b > b_leaf)
@@ -655,8 +665,8 @@ on2:
 		if (m->rm_flags & RNF_NORMAL) {
 			mmask = m->rm_leaf->rn_mask;
 			if (tt->rn_flags & RNF_NORMAL) {
-				log(LOG_ERR, "Non-unique normal route, "
-				    "mask not entered\n");
+				log(LOG_ERR, "Non-unique normal route,"
+				    " mask not entered\n");
 				return tt;
 			}
 		} else
@@ -729,7 +739,7 @@ rn_delete(v_arg, netmask_arg, head)
 		x = t;
 		t = t->rn_p;
 	} while (b <= t->rn_b && x != top);
-	for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist)
+	for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist)
 		if (m == saved_m) {
 			*mp = m->rm_mklist;
 			MKFree(m);
@@ -753,7 +763,12 @@ on1:
 	if (t) t->rn_ybro = tt->rn_ybro;
 #endif
 	t = tt->rn_p;
-	if ((dupedkey = saved_tt->rn_dupedkey) != 0) {
+	dupedkey = saved_tt->rn_dupedkey;
+	if (dupedkey) {
+		/*
+		 * Here, tt is the deletion target, and
+		 * saved_tt is the head of the dupedkey chain.
+		 */
 		if (tt == saved_tt) {
 			x = dupedkey;
 			x->rn_p = t;
@@ -762,12 +777,14 @@ on1:
 			else
 				t->rn_r = x;
 		} else {
+			/* find node in front of tt on the chain */
 			for (x = p = saved_tt; p && p->rn_dupedkey != tt;)
 				p = p->rn_dupedkey;
-			if (p)
+			if (p) {
 				p->rn_dupedkey = tt->rn_dupedkey;
-			else
-				log(LOG_ERR, "rn_delete: couldn't find us\n");
+				if (tt->rn_dupedkey)
+					tt->rn_dupedkey->rn_p = p;
+			} else log(LOG_ERR, "rn_delete: couldn't find us\n");
 		}
 		t = tt + 1;
 		if  (t->rn_flags & RNF_ACTIVE) {
@@ -804,7 +821,7 @@ on1:
 	 */
 	if (t->rn_mklist) {
 		if (x->rn_b >= 0) {
-			for (mp = &x->rn_mklist; (m = *mp) != NULL;)
+			for (mp = &x->rn_mklist; (m = *mp);)
 				mp = &m->rm_mklist;
 			*mp = t->rn_mklist;
 		} else {
@@ -821,7 +838,7 @@ on1:
 				}
 			if (m)
 				log(LOG_ERR, "%s %p at %p\n",
-					    "rn_delete: Orphaned Mask", m, x);
+				    "rn_delete: Orphaned Mask", m, x);
 		}
 	}
 	/*
@@ -895,14 +912,24 @@ rn_inithead(head, off)
 	int off;
 {
 	struct radix_node_head *rnh;
-	struct radix_node *t, *tt, *ttt;
+
 	if (*head)
 		return (1);
 	R_Malloc(rnh, struct radix_node_head *, sizeof (*rnh));
 	if (rnh == 0)
 		return (0);
-	Bzero(rnh, sizeof (*rnh));
 	*head = rnh;
+	return rn_inithead0(rnh, off);
+}
+
+int
+rn_inithead0(rnh, off)
+	struct radix_node_head *rnh;
+	int off;
+{
+	struct radix_node *t, *tt, *ttt;
+
+	Bzero(rnh, sizeof (*rnh));
 	t = rn_newpair(rn_zeros, off, rnh->rnh_nodes);
 	ttt = rnh->rnh_nodes + 2;
 	t->rn_r = ttt;
@@ -945,6 +972,6 @@ rn_init()
 	addmask_key = cplim = rn_ones + max_keylen;
 	while (cp < cplim)
 		*cp++ = -1;
-	if (rn_inithead((void **)&mask_rnhead, 0) == 0)
+	if (rn_inithead((void *)&mask_rnhead, 0) == 0)
 		panic("rn_init 2");
 }