From c9e5fb091d8dcda3dd02ebafd60c77f7e86fa831 Mon Sep 17 00:00:00 2001 From: Keith Sklower Date: Fri, 2 Dec 1994 22:55:12 -0800 Subject: [PATCH] this doesn't include annotation bugfixes, but documents work sent to mitre for a tunnel driver SCCS-vsn: sys/net/radix.c 8.2.3.1 --- usr/src/sys/net/radix.c | 185 ++++++++++++++-------------------------- 1 file changed, 64 insertions(+), 121 deletions(-) diff --git a/usr/src/sys/net/radix.c b/usr/src/sys/net/radix.c index ff9e35518b..0eb1281372 100644 --- a/usr/src/sys/net/radix.c +++ b/usr/src/sys/net/radix.c @@ -1,34 +1,32 @@ /* - * Copyright (c) 1988, 1989, 1993 + * Copyright (c) 1988, 1991, 1993 * The Regents of the University of California. All rights reserved. * * %sccs.include.redist.c% * - * @(#)radix.c 8.4 (Berkeley) %G% + * @(#)radix.c 8.2.3.1 (Berkeley) %G% */ /* * Routines to build and maintain radix trees for routing lookups. */ -#ifndef _RADIX_H_ +#ifndef RNF_NORMAL #include #ifdef KERNEL -#ifdef KERNEL #include #include #define M_DONTWAIT M_NOWAIT +#ifdef KERNEL #include #else #include -#else -#include #endif #include #include -#include -#include #endif +#include + int max_keylen; struct radix_node_head *mask_rnhead; static char *rn_zeros, *rn_ones; @@ -125,6 +123,7 @@ rn_refines(m_arg, n_arg) return 0; if (*n++ != *m++) masks_are_equal = 0; + } while (n < lim2) if (*n++) @@ -139,13 +138,6 @@ rn_refines(m_arg, n_arg) static int low_bits[] = {1, 3, 7, 15, 31, 63, 127, 255}; static int mask_bits[] = {1, 2, 4, 8, 16, 32, 64, 128}; -struct radix_node * -rn_lookup(v_arg, m_arg, head) - void *v_arg, *m_arg; - struct radix_node_head *head; -{ - register struct radix_node *x; - caddr_t netmask = 0; struct radix_node * rn_lookup(v_arg, m_arg, head) void *v_arg, *m_arg; @@ -172,40 +164,6 @@ rn_lookup(v_arg, m_arg, head) return x; } -static -rn_satsifies_leaf(trial, leaf, skip) - char *trial; - register struct radix_node *leaf; - int skip; -{ - register char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; - char *cplim; - int length = min(*(u_char *)cp, *(u_char *)cp2); - - if (cp3 == 0) - cp3 = rn_ones; - else - length = min(length, *(u_char *)cp3); - cplim = cp + length; cp3 += skip; cp2 += skip; - for (cp += skip; cp < cplim; cp++, cp2++, cp3++) - if ((*cp ^ *cp2) & *cp3) - return 0; - return 1; -} - - if (m_arg) { - if ((x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_off)) == 0) - return (0); - netmask = x->rn_key; - } - x = rn_match(v_arg, head); - if (x && netmask) { - while (x && x->rn_mask != netmask) - x = x->rn_dupedkey; - } - return x; -} - static rn_satsifies_leaf(trial, leaf, skip) char *trial; @@ -385,8 +343,6 @@ rn_match(v_arg, head) */ if (t->rn_mask) vlen = *(u_char *)t->rn_mask; - if (t->rn_mask) - vlen = *(u_char *)t->rn_mask; for (saved_t = t; t; t = t->rn_dupedkey) /* if (bits_matched >= mask_index) */ if (rn_b <= t->rn_b) { @@ -394,6 +350,8 @@ rn_match(v_arg, head) * This extra grot is in case we are explicitly asked * to look up the default. Ugh! */ + off = min(t->rn_off, matched_off); + mstart = maskedKey + off; if ((t->rn_flags & RNF_ROOT) && t->rn_dupedkey) t = t->rn_dupedkey; return (t); @@ -471,7 +429,7 @@ rn_insert(v_arg, head, dupentry, nodes) #ifdef RN_DEBUG if (rn_debug) - log(LOG_DEBUG, "rn_insert: Going In:\n"), traverse(p); + printf("Going In:\n"), traverse(p); #endif t = rn_newpair1(v, b, nodes, head); /* @@ -494,7 +452,7 @@ rn_insert(v_arg, head, dupentry, nodes) x->rn_p = t; #ifdef RN_DEBUG if (rn_debug) - log(LOG_DEBUG, "rn_insert: Coming Out:\n"), traverse(p); + printf("Coming out:\n"), traverse(p); #endif return (nodes); } @@ -512,10 +470,8 @@ rn_masksubr(n_arg, v_arg, skip, head, len_p) caddr_t netmask = (caddr_t)n_arg, v = v_arg; register struct radix_node *x = rn_masktop; register caddr_t cp, cplim; - register int b = 0, mlen, j; - int maskduplicated, m0, isnormal; - struct radix_node *saved_x; - static int last_zeroed = 0; + register int b, mlen, j; + int maskduplicated; struct radix_node *saved_x; if (head == 0) @@ -529,14 +485,6 @@ rn_masksubr(n_arg, v_arg, skip, head, len_p) Bzero(addmask_key + m0, last_zeroed - m0); *addmask_key = last_zeroed = mlen; x = rn_search(addmask_key, rn_masktop); - if (Bcmp(addmask_key, x->rn_key, mlen) != 0) - x = 0; - if (x || search) - return (x); - if (m0 < last_zeroed) - Bzero(addmask_key + m0, last_zeroed - m0); - *addmask_key = last_zeroed = mlen; - x = rn_search(addmask_key, rn_masktop); if (Bcmp(addmask_key, x->rn_key, mlen) != 0) x = 0; if (x || search) @@ -550,7 +498,7 @@ rn_masksubr(n_arg, v_arg, skip, head, len_p) Bcmp(netmask + skip, x->rn_key + skip, mlen - skip) == 0) goto found; R_Malloc(x, struct radix_node *, max_keylen + 2 * sizeof (*x)); - if ((saved_x = x) == 0) + if (x == 0) return (0); saved_x = x; Bzero(x, max_keylen + 2 * sizeof (*x)); @@ -566,7 +514,6 @@ rn_masksubr(n_arg, v_arg, skip, head, len_p) x->rn_b = -1 - mlen; } b += (cp - netmask) << 3; - b += (cp - netmask) << 3; found: if (len_p) *len_p = (-1 - x->rn_b) - head->rnh_offset; @@ -612,45 +559,6 @@ rn_new_radix_mask(tt, next) return m; } -static int /* XXX: arbitrary ordering for non-contiguous masks */ -rn_lexobetter(m_arg, n_arg) - void *m_arg, *n_arg; -{ - register u_char *mp = m_arg, *np = n_arg, *lim; - - if (*mp > *np) - return 1; /* not really, but need to check longer one first */ - if (*mp == *np) - for (lim = mp + *mp; mp < lim;) - if (*mp++ > *np++) - return 1; - return 0; -} - -static struct radix_mask * -rn_new_radix_mask(tt, next) - register struct radix_node *tt; - register struct radix_mask *next; -{ - register struct radix_mask *m; - - MKGet(m); - if (m == 0) { - log(LOG_ERR, "Mask for route not entered\n"); - return (0); - } - Bzero(m, sizeof *m); - m->rm_b = tt->rn_b; - m->rm_flags = tt->rn_flags; - if (tt->rn_flags & RNF_NORMAL) - m->rm_leaf = tt; - else - m->rm_mask = tt->rn_mask; - m->rm_mklist = next; - tt->rn_mklist = m; - return m; -} - struct radix_node * rn_addroute(v_arg, n_arg, head, treenodes) void *v_arg, *n_arg; @@ -702,6 +610,7 @@ rn_addroute(v_arg, n_arg, head, treenodes) t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; #endif + t = saved_tt; us->rn_key = (caddr_t) v; us->rn_flags = RNF_ACTIVE; } @@ -710,8 +619,13 @@ rn_addroute(v_arg, n_arg, head, treenodes) /* * Annotate tree about masks. */ - if (*mp = m = rn_new_radix_mask(x, 0)) - mp = &m->rm_mklist; + MKGet(m); + if (m) { + Bzero(m, sizeof *m); + m->rm_b = x->rn_b; + m->rm_mask = x->rn_mask; + x->rn_mklist = t->rn_mklist = m; + } } } @@ -724,7 +638,6 @@ rn_addroute(v_arg, n_arg, head, treenodes) break; p->rn_mklist = m; *mp = 0; } -on2: on2: /* Add new route to highest possible ancestor's list */ if ((netmask == 0) || (masklen > p->rn_b )) @@ -736,9 +649,10 @@ on2: /* * Search through routes associated with node to * insert new route according to index. - * Need same criteria as when sorting dupedkeys to avoid - * double loop on deletion. + * For nodes of equal index, place more specific + * masks first. */ + cplim = netmask + mlen; for (mp = &x->rn_mklist; m = *mp; mp = &m->rn_mklist) { if (m->rn_b > masklen_leaf) continue; @@ -758,6 +672,39 @@ struct radix_node * rn_delete(v_arg, n_arg, head) void *v_arg, *n_arg; struct radix_node_head *head; +{ + register struct radix_node *t, *x, *tt; + struct radix_node *dupedkey; + caddr_t v, netmask; + int b, head_off, vlen; + + v = v_arg; + x = head->rnh_treetop; + tt = rn_search(v, x); + head_off = x->rn_off; + vlen = *(u_char *)v; + if (tt == 0 || + Bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off)) + return (0); + /* + * Check for possiblity of key being duped in tree. + */ + if (dupedkey = tt->rn_dupedkey) { + if (netmask_arg) + netmask = rn_search(netmask_arg, rn_masktop)->rn_key; + else + netmask = 0; + while (tt->rn_mask != netmask) + if ((tt = tt->rn_dupedkey) == 0) + return (0); + } + return (rn_delete1(tt, head)); +} + +struct radix_node * +rn_delete1(rn, head) + struct radix_node *rn; + struct radix_node_head *head; { register struct radix_node *t, *p, *x, *tt; struct radix_node *m, *saved_m, **mp; @@ -769,6 +716,7 @@ rn_delete(v_arg, n_arg, head) base = tt = rn_search_unmapped(v_arg, head); if (tt == 0 || Bcmp(v + head_off, tt->rn_key + head_off, vlen)) return (0); + p = t = tt->rn_p; (void) rn_masksubr(v_arg, n_arg, head_off, head, &masklen); masklen_leaf = -1 - masklen; @@ -790,11 +738,8 @@ rn_delete(v_arg, n_arg, head) *mp = tt->rn_mklist; break; } - if (m == 0) { - log(LOG_ERR, "rn_delete: couldn't find our annotation\n"); - if (tt->rn_flags & RNF_NORMAL) - return (0); /* Dangling ref to us */ - } + if (m == 0) + printf("rn_delete: couldn't find our annotation\n"); on1: /* * Eliminate us from tree @@ -806,7 +751,7 @@ on1: for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {} if (t) t->rn_ybro = tt->rn_ybro; #endif - if (dupedkey = saved_tt->rn_dupedkey) { + if (dupedkey) { if (tt == base) { x = dupedkey; x->rn_p = t; if (t->rn_l == tt) t->rn_l = x; else t->rn_r = x; @@ -814,7 +759,7 @@ on1: for (x = base; x && x->rn_dupedkey != tt;) x = x->rn_dupedkey; if (x) x->rn_dupedkey = tt->rn_dupedkey; - else log(LOG_ERR, "rn_delete: couldn't find us\n"); + else printf("rn_delete: couldn't find us\n"); } x = tt + 1; if (x->rn_flags & RNF_ACTIVE) { @@ -934,7 +879,6 @@ rn_inithead(head, off) rnh->rnh_deladdr = rn_delete; rnh->rnh_matchaddr = rn_match; rnh->rnh_lookup = rn_lookup; - rnh->rnh_lookup = rn_lookup; rnh->rnh_walktree = rn_walktree; rnh->rnh_bits_matched = rn_unmapped_bits_matched; rnh->rnh_set_mask = rn_unmapped_set_mask; @@ -953,8 +897,7 @@ rn_init() max_keylen = dom->dom_maxrtkey; #endif if (max_keylen == 0) { - log(LOG_ERR, - "rn_init: radix functions require max_keylen be set\n"); + printf("rn_init: radix functions require max_keylen be set\n"); return; } R_Malloc(rn_zeros, char *, 3 * max_keylen); -- 2.20.1