* Copyright (c) 1988, 1989, 1993
* The Regents of the University of California. All rights reserved.
* 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 8.2 (Berkeley) 1/4/94
* Routines to build and maintain radix trees for routing lookups.
#define M_DONTWAIT M_NOWAIT
struct radix_mask
*rn_mkfreelist
;
struct radix_node_head
*mask_rnhead
;
static char *rn_zeros
, *rn_ones
;
#define rn_masktop (mask_rnhead->rnh_treetop)
#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
, v
= v_arg
; x
->rn_b
>= 0;) {
if (x
->rn_bmask
& v
[x
->rn_off
])
rn_search_m(v_arg
, head
, m_arg
)
register struct radix_node
*x
;
register caddr_t v
= v_arg
, m
= m_arg
;
for (x
= head
; x
->rn_b
>= 0;) {
if ((x
->rn_bmask
& m
[x
->rn_off
]) &&
(x
->rn_bmask
& v
[x
->rn_off
]))
register caddr_t m
= m_arg
, n
= n_arg
;
register caddr_t lim
, lim2
= lim
= n
+ *(u_char
*)n
;
int longer
= (*(u_char
*)n
++) - (int)(*(u_char
*)m
++);
if (masks_are_equal
&& (longer
< 0))
for (lim2
= m
- longer
; m
< lim2
; )
return (!masks_are_equal
);
struct radix_node_head
*head
;
register struct radix_node
*t
= head
->rnh_treetop
, *x
;
register caddr_t cp
= v
, cp2
, cp3
;
struct radix_node
*saved_t
, *top
= t
;
int off
= t
->rn_off
, vlen
= *(u_char
*)cp
, matched_off
;
* Open code rn_search(v, top) 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
= (caddr_t
)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_arg
, head
, dupentry
, nodes
)
struct radix_node_head
*head
;
struct radix_node nodes
[2];
struct radix_node
*top
= head
->rnh_treetop
;
int head_off
= top
->rn_off
, vlen
= (int)*((u_char
*)v
);
register struct radix_node
*t
= rn_search(v_arg
, top
);
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
= top
;
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_arg
, 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(n_arg
, search
, skip
)
caddr_t netmask
= (caddr_t
)n_arg
;
register struct radix_node
*x
;
register caddr_t cp
, cplim
;
mlen
= *(u_char
*)netmask
;
x
= rn_search(netmask
, rn_masktop
);
mlen
= *(u_char
*)netmask
;
if (Bcmp(netmask
, x
->rn_key
, mlen
) == 0)
R_Malloc(x
, struct radix_node
*, max_keylen
+ 2 * sizeof (*x
));
Bzero(x
, max_keylen
+ 2 * sizeof (*x
));
Bcopy(netmask
, cp
, mlen
);
x
= rn_insert(netmask
, mask_rnhead
, &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_arg
, n_arg
, head
, treenodes
)
struct radix_node_head
*head
;
struct radix_node treenodes
[2];
caddr_t v
= (caddr_t
)v_arg
, netmask
= (caddr_t
)n_arg
;
register struct radix_node
*t
, *x
, *tt
;
struct radix_node
*saved_tt
, *top
= head
->rnh_treetop
;
struct radix_mask
*m
, **mp
;
* 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_masktop
);
mlen
= *(u_char
*)netmask
;
if (Bcmp(netmask
, x
->rn_key
, mlen
) != 0) {
x
= rn_addmask(netmask
, 0, top
->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
)
(tt
->rn_mask
&& rn_refines(netmask
, tt
->rn_mask
)))
} 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.
* We sort the masks for a duplicated key the same way as
* in a masklist -- most specific to least specific.
* This may require the unfortunate nuisance of relocating
if (tt
&& t
== saved_tt
) {
struct radix_node
*xx
= x
;
/* link in at head of list */
(tt
= treenodes
)->rn_dupedkey
= t
;
tt
->rn_flags
= t
->rn_flags
;
if (x
->rn_l
== t
) x
->rn_l
= tt
; else x
->rn_r
= tt
;
(tt
= treenodes
)->rn_dupedkey
= t
->rn_dupedkey
;
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
!= top
);
* 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
) {
if (rn_refines(netmask
, m
->rm_mask
))
printf("Mask for route not entered\n");
rn_delete(v_arg
, netmask_arg
, head
)
void *v_arg
, *netmask_arg
;
struct radix_node_head
*head
;
register struct radix_node
*t
, *p
, *x
, *tt
;
struct radix_mask
*m
, *saved_m
, **mp
;
struct radix_node
*dupedkey
, *saved_tt
, *top
;
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_masktop
)->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
!= top
);
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
;
for (x
= 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_flags
& RNF_ACTIVE
) {
b
= t
->rn_info
; *++x
= *t
; t
->rn_info
= b
; 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
;
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
;
struct radix_node_head
*h
;
struct radix_node
*base
, *next
;
register struct radix_node
*rn
= h
->rnh_treetop
;
* This gets complicated because we may delete the node
* while applying the function f to it, so we need to calculate
* the successor node in advance.
/* First time through node, go left */
/* If at right child go back up, otherwise, go right */
while (rn
->rn_p
->rn_r
== rn
&& (rn
->rn_flags
& RNF_ROOT
) == 0)
/* Find the next *leaf* since next node might vanish, too */
for (rn
= rn
->rn_p
->rn_r
; rn
->rn_b
>= 0;)
if (!(rn
->rn_flags
& RNF_ROOT
) && (error
= (*f
)(rn
, w
)))
if (rn
->rn_flags
& RNF_ROOT
)
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
;
rnh
->rnh_addaddr
= rn_addroute
;
rnh
->rnh_deladdr
= rn_delete
;
rnh
->rnh_matchaddr
= rn_match
;
rnh
->rnh_walktree
= rn_walktree
;
for (dom
= domains
; dom
; dom
= dom
->dom_next
)
if (dom
->dom_maxrtkey
> max_keylen
)
max_keylen
= dom
->dom_maxrtkey
;
printf("rn_init: radix functions require max_keylen be set\n");
R_Malloc(rn_zeros
, char *, 3 * max_keylen
);
Bzero(rn_zeros
, 3 * max_keylen
);
rn_ones
= cp
= rn_zeros
+ max_keylen
;
maskedKey
= cplim
= rn_ones
+ max_keylen
;
if (rn_inithead((void **)&mask_rnhead
, 0) == 0)