* Copyright (c) 1988, 1989 Regents of the University of California.
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. All advertising materials mentioning features or use of this software
* must display the following acknowledgement:
* This product includes software developed by the University of
* California, Berkeley and its contributors.
* 4. Neither the name of the University nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* @(#)radix.c 7.9 (Berkeley) 2/4/91
* Routines to build and maintain radix trees for routing lookups.
#define M_DONTWAIT M_NOWAIT
struct radix_node_head
*mask_rnhead
;
#define rn_maskhead mask_rnhead->rnh_treetop
struct radix_mask
*rn_mkfreelist
;
struct radix_node_head
*radix_node_head
;
#define Bcmp(a, b, l) (l == 0 ? 0 : bcmp((caddr_t)(a), (caddr_t)(b), (u_long)l))
* 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
* position to be tested. The tree is arranged so that all descendants
* of a node n have keys whose bits all agree up to position rn_b - 1.
* (We say the index of n is rn_b.)
* There is at least one descendant which has a one bit at position rn_b,
* and at least one with a zero there.
* A route is determined by a pair of key and mask. We require that the
* bit-wise logical and of the key and mask to be the key.
* We define the index of a route to associated with the mask to be
* the first bit number in the mask where 0 occurs (with bit number 0
* representing the highest order bit).
* We say a mask is normal if every bit is 0, past the index of the mask.
* If a node n has a descendant (k, m) with index(m) == index(n) == rn_b,
* and m is a normal mask, then the route applies to every descendant of n.
* If the index(m) < rn_b, this implies the trailing last few bits of k
* before bit b are all 0, (and hence consequently true of every descendant
* of n), so the route applies to all descendants of the node as well.
* The present version of the code makes no use of normal routes,
* but similar logic shows that a non-normal mask m such that
* index(m) <= index(n) could potentially apply to many children of n.
* Thus, for each non-host route, we attach its mask to a list at an internal
* node as high in the tree as we can go.
register struct radix_node
*x
;
for (x
= head
; x
->rn_b
>= 0;) {
if (x
->rn_bmask
& v
[x
->rn_off
])
register struct radix_node
*x
;
for (x
= head
; x
->rn_b
>= 0;) {
if ((x
->rn_bmask
& m
[x
->rn_off
]) &&
(x
->rn_bmask
& v
[x
->rn_off
]))
static char maskedKey
[MAXKEYLEN
];
register struct radix_node
*t
= head
, *x
;
register caddr_t cp
= v
, cp2
, cp3
;
struct radix_node
*saved_t
;
int off
= t
->rn_off
, vlen
= *(u_char
*)cp
, matched_off
;
* Open code rn_search(v, head) to avoid overhead of extra
if (t
->rn_bmask
& cp
[t
->rn_off
])
* See if we match exactly as a host destination
cp
+= off
; cp2
= t
->rn_key
+ off
; cplim
= v
+ vlen
;
for (; cp
< cplim
; cp
++, cp2
++)
* This extra grot is in case we are explicitly asked
* to look up the default. Ugh!
if ((t
->rn_flags
& RNF_ROOT
) && t
->rn_dupedkey
)
* Even if we don't match exactly as a hosts;
* we may match if the leaf we wound up at is
cp3
= matched_off
+ t
->rn_mask
;
cp2
= matched_off
+ t
->rn_key
;
if ((*cp2
++ ^ *cp
) & *cp3
++)
} while (t
= t
->rn_dupedkey
);
/* start searching up the tree */
register struct radix_mask
*m
;
* After doing measurements here, it may
* turn out to be faster to open code
* rn_search_m here instead of always
off
= min(t
->rn_off
, matched_off
);
mstart
= maskedKey
+ off
;
for (cp
= v
+ off
; cp
< cplim
;)
x
= rn_search(maskedKey
, t
);
while (x
&& x
->rn_mask
!= m
->rm_mask
)
(Bcmp(mstart
, x
->rn_key
+ off
,
} while (m
= m
->rm_mklist
);
struct radix_node
*rn_clist
;
struct radix_node nodes
[2];
register struct radix_node
*tt
= nodes
, *t
= tt
+ 1;
t
->rn_b
= b
; t
->rn_bmask
= 0x80 >> (b
& 7);
t
->rn_l
= tt
; t
->rn_off
= b
>> 3;
tt
->rn_b
= -1; tt
->rn_key
= v
; tt
->rn_p
= t
;
tt
->rn_flags
= t
->rn_flags
= RNF_ACTIVE
;
tt
->rn_info
= rn_nodenum
++; t
->rn_info
= rn_nodenum
++;
tt
->rn_twin
= t
; tt
->rn_ybro
= rn_clist
; rn_clist
= tt
;
rn_insert(v
, head
, dupentry
, nodes
)
struct radix_node nodes
[2];
int head_off
= head
->rn_off
, vlen
= (int)*((u_char
*)v
);
register struct radix_node
*t
= rn_search(v
, head
);
register caddr_t cp
= v
+ head_off
;
*find first bit at which v and t->rn_key differ
register caddr_t cp2
= t
->rn_key
+ head_off
;
caddr_t cplim
= v
+ vlen
;
cmp_res
= (cp
[-1] ^ cp2
[-1]) & 0xff;
for (b
= (cp
- v
) << 3; cmp_res
; b
--)
register struct radix_node
*p
, *x
= head
;
if (cp
[x
->rn_off
] & x
->rn_bmask
)
} while (b
> (unsigned) x
->rn_b
); /* x->rn_b < b && x->rn_b >= 0 */
printf("Going In:\n"), traverse(p
);
t
= rn_newpair(v
, b
, nodes
); tt
= t
->rn_l
;
if ((cp
[p
->rn_off
] & p
->rn_bmask
) == 0)
x
->rn_p
= t
; t
->rn_p
= p
; /* frees x, p as temp vars below */
if ((cp
[t
->rn_off
] & t
->rn_bmask
) == 0) {
t
->rn_r
= tt
; t
->rn_l
= x
;
printf("Coming out:\n"), traverse(p
);
rn_addmask(netmask
, search
, skip
)
register struct radix_node
*x
;
register caddr_t cp
, cplim
;
mlen
= *(u_char
*)netmask
;
x
= rn_search(netmask
, rn_maskhead
);
mlen
= *(u_char
*)netmask
;
if (Bcmp(netmask
, x
->rn_key
, mlen
) == 0)
R_Malloc(x
, struct radix_node
*, MAXKEYLEN
+ 2 * sizeof (*x
));
Bzero(x
, MAXKEYLEN
+ 2 * sizeof (*x
));
Bcopy(netmask
, cp
, mlen
);
x
= rn_insert(netmask
, rn_maskhead
, &maskduplicated
, x
);
* Calculate index of mask.
for (cp
= netmask
+ skip
; cp
< cplim
; cp
++)
if (*(u_char
*)cp
!= 0xff)
for (j
= 0x80; j
; b
++, j
>>= 1)
rn_addroute(v
, netmask
, head
, treenodes
)
struct radix_node treenodes
[2];
register struct radix_node
*t
, *x
, *tt
;
int vlen
= *(u_char
*)v
, mlen
, keyduplicated
;
caddr_t cplim
; unsigned char *maskp
;
struct radix_mask
*m
, **mp
;
struct radix_node
*saved_tt
;
* In dealing with non-contiguous masks, there may be
* many different routes which have the same mask.
* We will find it useful to have a unique pointer to
* the mask to speed avoiding duplicate references at
* nodes and possibly save time in calculating indices.
x
= rn_search(netmask
, rn_maskhead
);
mlen
= *(u_char
*)netmask
;
if (Bcmp(netmask
, x
->rn_key
, mlen
) != 0) {
x
= rn_addmask(netmask
, 0, head
->rn_off
);
* Deal with duplicated keys: attach node to previous instance
saved_tt
= tt
= rn_insert(v
, head
, &keyduplicated
, treenodes
);
if (tt
->rn_mask
== netmask
)
} while (tt
= tt
->rn_dupedkey
);
* If the mask is not duplicated, we wouldn't
* find it among possible duplicate key entries
* anyway, so the above test doesn't hurt.
* XXX: we really ought to sort the masks
* for a duplicated key the same way as in a masklist.
* It is an unfortunate pain having to relocate
t
->rn_dupedkey
= tt
= 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
;
tt
->rn_key
= (caddr_t
) v
;
tt
->rn_flags
= t
->rn_flags
& ~RNF_ROOT
;
if (t
->rn_r
== saved_tt
) x
= t
->rn_l
; else x
= t
->rn_r
;
/* Promote general routes from below */
if (x
->rn_mask
&& (x
->rn_b
>= b_leaf
) && x
->rn_mklist
== 0) {
x
->rn_mklist
= t
->rn_mklist
= m
;
} else if (x
->rn_mklist
) {
* Skip over masks whose index is > that of new node
for (mp
= &x
->rn_mklist
; m
= *mp
; mp
= &m
->rm_mklist
)
t
->rn_mklist
= m
; *mp
= 0;
/* Add new route to highest possible ancestor's list */
if ((netmask
== 0) || (b
> t
->rn_b
))
return tt
; /* can't lift at all */
} while (b
<= t
->rn_b
&& x
!= head
);
* Search through routes associated with node to
* insert new route according to index.
* For nodes of equal index, place more specific
for (mp
= &x
->rn_mklist
; m
= *mp
; mp
= &m
->rm_mklist
) {
if (m
->rm_mask
== netmask
) {
maskp
= (u_char
*)m
->rm_mask
;
for (cp
= netmask
; cp
< cplim
; cp
++)
if (*(u_char
*)cp
> *maskp
++)
printf("Mask for route not entered\n");
rn_delete(v
, netmask
, head
)
register struct radix_node
*t
, *p
, *x
= head
;
register struct radix_node
*tt
= rn_search(v
, x
);
int b
, head_off
= x
->rn_off
, vlen
= * (u_char
*) v
;
struct radix_mask
*m
, *saved_m
, **mp
;
struct radix_node
*dupedkey
, *saved_tt
= tt
;
Bcmp(v
+ head_off
, tt
->rn_key
+ head_off
, vlen
- head_off
))
* Delete our route from mask lists.
if (dupedkey
= tt
->rn_dupedkey
) {
netmask
= rn_search(netmask
, rn_maskhead
)->rn_key
;
while (tt
->rn_mask
!= netmask
)
if ((tt
= tt
->rn_dupedkey
) == 0)
if (tt
->rn_mask
== 0 || (saved_m
= m
= tt
->rn_mklist
) == 0)
if (m
->rm_mask
!= tt
->rn_mask
) {
printf("rn_delete: inconsistent annotation\n");
goto on1
; /* Wasn't lifted at all */
} while (b
<= t
->rn_b
&& x
!= head
);
for (mp
= &x
->rn_mklist
; m
= *mp
; mp
= &m
->rm_mklist
)
printf("rn_delete: couldn't find our annotation\n");
if (tt
->rn_flags
& RNF_ROOT
)
/* Get us out of the creation list */
for (t
= rn_clist
; t
&& t
->rn_ybro
!= tt
; t
= t
->rn_ybro
) {}
if (t
) t
->rn_ybro
= tt
->rn_ybro
;
x
= dupedkey
; x
->rn_p
= t
;
if (t
->rn_l
== tt
) t
->rn_l
= x
; else t
->rn_r
= x
;
x
++; t
= tt
+ 1; *x
= *t
; p
= t
->rn_p
;
x
++; b
= x
->rn_info
; t
= tt
+ 1; *x
= *t
; p
= t
->rn_p
;
if (p
->rn_l
== t
) p
->rn_l
= x
; else p
->rn_r
= x
;
x
->rn_l
->rn_p
= x
; x
->rn_r
->rn_p
= x
;
for (p
= saved_tt
; p
&& p
->rn_dupedkey
!= tt
;)
if (p
) p
->rn_dupedkey
= tt
->rn_dupedkey
;
else printf("rn_delete: couldn't find us\n");
if (t
->rn_l
== tt
) x
= t
->rn_r
; else x
= t
->rn_l
;
if (p
->rn_r
== t
) p
->rn_r
= x
; else p
->rn_l
= x
;
* Demote routes attached to us.
for (mp
= &x
->rn_mklist
; m
= *mp
;)
for (m
= t
->rn_mklist
; m
;) {
struct radix_mask
*mm
= m
->rm_mklist
;
if (m
== x
->rn_mklist
&& (--(m
->rm_refs
) < 0)) {
"rn_delete: Orphaned Mask", m
, x
);
* We may be holding an active internal node in the tree.
b
= t
->rn_info
; *t
= *x
; t
->rn_info
= b
;
t
->rn_l
->rn_p
= t
; t
->rn_r
->rn_p
= t
;
if (p
->rn_l
== x
) p
->rn_l
= t
; else p
->rn_r
= t
;
tt
->rn_flags
&= ~RNF_ACTIVE
;
tt
[1].rn_flags
&= ~RNF_ACTIVE
;
char rn_zeros
[MAXKEYLEN
], rn_ones
[MAXKEYLEN
];
rn_inithead(head
, off
, af
)
struct radix_node_head
**head
;
register struct radix_node_head
*rnh
;
register struct radix_node
*t
, *tt
, *ttt
;
R_Malloc(rnh
, struct radix_node_head
*, sizeof (*rnh
));
Bzero(rnh
, sizeof (*rnh
));
t
= rn_newpair(rn_zeros
, off
, rnh
->rnh_nodes
);
ttt
= rnh
->rnh_nodes
+ 2;
tt
->rn_flags
= t
->rn_flags
= RNF_ROOT
| RNF_ACTIVE
;
if (radix_node_head
== 0) {
caddr_t cp
= rn_ones
, cplim
= rn_ones
+ MAXKEYLEN
;
if (rn_inithead(&radix_node_head
, 0, 0) == 0) {
mask_rnhead
= radix_node_head
;
rnh
->rnh_next
= radix_node_head
->rnh_next
;
if (radix_node_head
!= rnh
)
radix_node_head
->rnh_next
= rnh
;