/*
- * 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 <sys/param.h>
#ifdef KERNEL
-#ifdef KERNEL
#include <sys/systm.h>
#include <sys/malloc.h>
#define M_DONTWAIT M_NOWAIT
+#ifdef KERNEL
#include <sys/domain.h>
#else
#include <stdlib.h>
-#else
-#include <stdlib.h>
#endif
#include <sys/syslog.h>
#include <net/radix.h>
-#include <sys/syslog.h>
-#include <net/radix.h>
#endif
+#include <net/radix.h>
+
int max_keylen;
struct radix_node_head *mask_rnhead;
static char *rn_zeros, *rn_ones;
return 0;
if (*n++ != *m++)
masks_are_equal = 0;
+
}
while (n < lim2)
if (*n++)
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;
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;
*/
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) {
* 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);
#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);
/*
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);
}
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)
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)
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));
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;
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;
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;
}
/*
* 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;
+ }
}
}
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 ))
/*
* 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;
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;
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;
*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
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;
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) {
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;
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);