diff options
| -rw-r--r-- | sys/net/radix.c | 75 | ||||
| -rw-r--r-- | sys/net/radix.h | 5 |
2 files changed, 54 insertions, 26 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"); } diff --git a/sys/net/radix.h b/sys/net/radix.h index 2802a583f50..1ebe63d3978 100644 --- a/sys/net/radix.h +++ b/sys/net/radix.h @@ -1,4 +1,4 @@ -/* $OpenBSD: radix.h,v 1.10 2003/08/27 00:33:34 henric Exp $ */ +/* $OpenBSD: radix.h,v 1.11 2004/04/25 01:38:10 brad Exp $ */ /* $NetBSD: radix.h,v 1.8 1996/02/13 22:00:37 christos Exp $ */ /* @@ -59,7 +59,7 @@ struct radix_node { struct radix_node *rn_L;/* progeny */ struct radix_node *rn_R;/* progeny */ } rn_node; - } rn_u; + } rn_u; #ifdef RN_DEBUG int rn_info; struct radix_node *rn_twin; @@ -151,6 +151,7 @@ struct radix_node_head { #if defined(_KERNEL) || defined(_ROUTED) void rn_init(void); int rn_inithead(void **, int); +int rn_inithead0(struct radix_node_head *, int); int rn_refines(void *, void *); int rn_walktree(struct radix_node_head *, int (*)(struct radix_node *, void *), void *); |