Changeset View
Changeset View
Standalone View
Standalone View
sys/net/radix.c
Show First 20 Lines • Show All 78 Lines • ▼ Show 20 Lines | |||||
}; | }; | ||||
static int rn_lexobetter(void *m_arg, void *n_arg); | static int rn_lexobetter(void *m_arg, void *n_arg); | ||||
static struct radix_mask * | static struct radix_mask * | ||||
rn_new_radix_mask(struct radix_node *tt, | rn_new_radix_mask(struct radix_node *tt, | ||||
struct radix_mask *next); | struct radix_mask *next); | ||||
static int rn_satisfies_leaf(char *trial, struct radix_node *leaf, | static int rn_satisfies_leaf(char *trial, struct radix_node *leaf, | ||||
int skip); | int skip, int salen); | ||||
/* | /* | ||||
* The data structure for the keys is a radix tree with one way | * The data structure for the keys is a radix tree with one way | ||||
* branching removed. The index rn_bit at an internal node n represents a bit | * branching removed. The index rn_bit at an internal node n represents a bit | ||||
* position to be tested. The tree is arranged so that all descendants | * 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_bit - 1. | * of a node n have keys whose bits all agree up to position rn_bit - 1. | ||||
* (We say the index of n is rn_bit.) | * (We say the index of n is rn_bit.) | ||||
* | * | ||||
▲ Show 20 Lines • Show All 154 Lines • ▼ Show 20 Lines | rn_lookup(void *v_arg, void *m_arg, struct radix_head *head) | ||||
/* Check if this is not host route */ | /* Check if this is not host route */ | ||||
if (x->rn_mask != NULL) | if (x->rn_mask != NULL) | ||||
return (NULL); | return (NULL); | ||||
return (x); | return (x); | ||||
} | } | ||||
static int | static int | ||||
rn_satisfies_leaf(char *trial, struct radix_node *leaf, int skip) | rn_satisfies_leaf(char *trial, struct radix_node *leaf, int skip, int salen) | ||||
{ | { | ||||
char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; | char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; | ||||
char *cplim; | char *cplim; | ||||
int length = min(LEN(cp), LEN(cp2)); | int length = min(salen, LEN(cp2) - skip); | ||||
if (cp3 == NULL) | if (cp3 == NULL) | ||||
cp3 = rn_ones; | cp3 = rn_ones; | ||||
else | else | ||||
length = min(length, LEN(cp3)); | length = min(length, LEN(cp3)); | ||||
cplim = cp + length; cp3 += skip; cp2 += skip; | cplim = cp + length; cp3 += skip; cp2 += skip; | ||||
for (cp += skip; cp < cplim; cp++, cp2++, cp3++) | for (cp += skip; cp < cplim; cp++, cp2++, cp3++) | ||||
if ((*cp ^ *cp2) & *cp3) | if ((*cp ^ *cp2) & *cp3) | ||||
return (0); | return (0); | ||||
return (1); | return (1); | ||||
} | } | ||||
/* | /* | ||||
* Search for longest-prefix match in given @head | * Search for longest-prefix match in given @head | ||||
*/ | */ | ||||
struct radix_node * | struct radix_node * | ||||
rn_match(void *v_arg, struct radix_head *head) | rn_match(void *v_arg, struct radix_head *head) | ||||
{ | { | ||||
caddr_t v = v_arg; | caddr_t v = v_arg; | ||||
struct radix_node *t = head->rnh_treetop, *x; | struct radix_node *t = head->rnh_treetop, *x; | ||||
caddr_t cp = v, cp2; | caddr_t cp = v, cp2; | ||||
caddr_t cplim; | caddr_t cplim; | ||||
struct radix_node *saved_t, *top = t; | struct radix_node *saved_t, *top = t; | ||||
int off = t->rn_offset, vlen = LEN(cp), matched_off; | #ifndef RADIX_ALLOW_VARIABLE_KEY_LENGTH | ||||
int salen = t->rn_salen; | |||||
#else | |||||
int salen = LEN(cp); | |||||
#endif | |||||
int off = t->rn_offset, vlen = salen, matched_off; | |||||
int test, b, rn_bit; | int test, b, rn_bit; | ||||
/* | /* | ||||
* Open code rn_search(v, top) to avoid overhead of extra | * Open code rn_search(v, top) to avoid overhead of extra | ||||
* subroutine call. | * subroutine call. | ||||
*/ | */ | ||||
for (; t->rn_bit >= 0; ) { | for (; t->rn_bit >= 0; ) { | ||||
if (t->rn_bmask & cp[t->rn_offset]) | if (t->rn_bmask & cp[t->rn_offset]) | ||||
▲ Show 20 Lines • Show All 44 Lines • ▼ Show 20 Lines | for (; t; t = t->rn_dupedkey) | ||||
/* | /* | ||||
* Even if we don't match exactly as a host, | * Even if we don't match exactly as a host, | ||||
* we may match if the leaf we wound up at is | * we may match if the leaf we wound up at is | ||||
* a route to a net. | * a route to a net. | ||||
*/ | */ | ||||
if (t->rn_flags & RNF_NORMAL) { | if (t->rn_flags & RNF_NORMAL) { | ||||
if (rn_bit <= t->rn_bit) | if (rn_bit <= t->rn_bit) | ||||
return (t); | return (t); | ||||
} else if (rn_satisfies_leaf(v, t, matched_off)) | } else if (rn_satisfies_leaf(v, t, matched_off, salen)) | ||||
return (t); | return (t); | ||||
t = saved_t; | t = saved_t; | ||||
/* start searching up the tree */ | /* start searching up the tree */ | ||||
do { | do { | ||||
struct radix_mask *m; | struct radix_mask *m; | ||||
t = t->rn_parent; | t = t->rn_parent; | ||||
m = t->rn_mklist; | m = t->rn_mklist; | ||||
/* | /* | ||||
* If non-contiguous masks ever become important | * If non-contiguous masks ever become important | ||||
* we can restore the masking and open coding of | * we can restore the masking and open coding of | ||||
* the search and satisfaction test and put the | * the search and satisfaction test and put the | ||||
* calculation of "off" back before the "do". | * calculation of "off" back before the "do". | ||||
*/ | */ | ||||
while (m) { | while (m) { | ||||
if (m->rm_flags & RNF_NORMAL) { | if (m->rm_flags & RNF_NORMAL) { | ||||
if (rn_bit <= m->rm_bit) | if (rn_bit <= m->rm_bit) | ||||
return (m->rm_leaf); | return (m->rm_leaf); | ||||
} else { | } else { | ||||
off = min(t->rn_offset, matched_off); | off = min(t->rn_offset, matched_off); | ||||
x = rn_search_m(v, t, m->rm_mask); | x = rn_search_m(v, t, m->rm_mask); | ||||
while (x && x->rn_mask != m->rm_mask) | while (x && x->rn_mask != m->rm_mask) | ||||
x = x->rn_dupedkey; | x = x->rn_dupedkey; | ||||
if (x && rn_satisfies_leaf(v, x, off)) | if (x && rn_satisfies_leaf(v, x, off, salen)) | ||||
return (x); | return (x); | ||||
} | } | ||||
m = m->rm_mklist; | m = m->rm_mklist; | ||||
} | } | ||||
} while (t != top); | } while (t != top); | ||||
return (0); | return (0); | ||||
} | } | ||||
▲ Show 20 Lines • Show All 727 Lines • ▼ Show 20 Lines | |||||
/* | /* | ||||
* Initialize an empty tree. This has 3 nodes, which are passed | * Initialize an empty tree. This has 3 nodes, which are passed | ||||
* via base_nodes (in the order <left,root,right>) and are | * via base_nodes (in the order <left,root,right>) and are | ||||
* marked RNF_ROOT so they cannot be freed. | * marked RNF_ROOT so they cannot be freed. | ||||
* The leaves have all-zero and all-one keys, with significant | * The leaves have all-zero and all-one keys, with significant | ||||
* bits starting at 'off'. | * bits starting at 'off'. | ||||
*/ | */ | ||||
void | void | ||||
rn_inithead_internal(struct radix_head *rh, struct radix_node *base_nodes, int off) | rn_inithead_internal(struct radix_head *rh, struct radix_node *base_nodes, | ||||
int off, int salen) | |||||
{ | { | ||||
struct radix_node *t, *tt, *ttt; | struct radix_node *t, *tt, *ttt; | ||||
t = rn_newpair(rn_zeros, off, base_nodes); | t = rn_newpair(rn_zeros, off, base_nodes); | ||||
ttt = base_nodes + 2; | ttt = base_nodes + 2; | ||||
t->rn_right = ttt; | t->rn_right = ttt; | ||||
t->rn_parent = t; | t->rn_parent = t; | ||||
t->rn_salen = salen; | |||||
tt = t->rn_left; /* ... which in turn is base_nodes */ | tt = t->rn_left; /* ... which in turn is base_nodes */ | ||||
tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; | tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; | ||||
tt->rn_bit = -1 - off; | tt->rn_bit = -1 - off; | ||||
*ttt = *tt; | *ttt = *tt; | ||||
ttt->rn_key = rn_ones; | ttt->rn_key = rn_ones; | ||||
rh->rnh_treetop = t; | rh->rnh_treetop = t; | ||||
} | } | ||||
static void | static void | ||||
rn_detachhead_internal(struct radix_head *head) | rn_detachhead_internal(struct radix_head *head) | ||||
{ | { | ||||
KASSERT((head != NULL), | KASSERT((head != NULL), | ||||
("%s: head already freed", __func__)); | ("%s: head already freed", __func__)); | ||||
/* Free <left,root,right> nodes. */ | /* Free <left,root,right> nodes. */ | ||||
R_Free(head); | R_Free(head); | ||||
} | } | ||||
/* Functions used by 'struct radix_node_head' users */ | /* Functions used by 'struct radix_node_head' users */ | ||||
int | int | ||||
rn_inithead(void **head, int off) | rn_inithead(void **head, int off, int salen) | ||||
{ | { | ||||
struct radix_node_head *rnh; | struct radix_node_head *rnh; | ||||
struct radix_mask_head *rmh; | struct radix_mask_head *rmh; | ||||
rnh = *head; | rnh = *head; | ||||
rmh = NULL; | rmh = NULL; | ||||
if (*head != NULL) | if (*head != NULL) | ||||
return (1); | return (1); | ||||
R_Zalloc(rnh, struct radix_node_head *, sizeof (*rnh)); | R_Zalloc(rnh, struct radix_node_head *, sizeof (*rnh)); | ||||
R_Zalloc(rmh, struct radix_mask_head *, sizeof (*rmh)); | R_Zalloc(rmh, struct radix_mask_head *, sizeof (*rmh)); | ||||
if (rnh == NULL || rmh == NULL) { | if (rnh == NULL || rmh == NULL) { | ||||
if (rnh != NULL) | if (rnh != NULL) | ||||
R_Free(rnh); | R_Free(rnh); | ||||
if (rmh != NULL) | if (rmh != NULL) | ||||
R_Free(rmh); | R_Free(rmh); | ||||
return (0); | return (0); | ||||
} | } | ||||
/* Init trees */ | /* Init trees */ | ||||
rn_inithead_internal(&rnh->rh, rnh->rnh_nodes, off); | rn_inithead_internal(&rnh->rh, rnh->rnh_nodes, off, salen); | ||||
rn_inithead_internal(&rmh->head, rmh->mask_nodes, 0); | rn_inithead_internal(&rmh->head, rmh->mask_nodes, 0, 0); | ||||
*head = rnh; | *head = rnh; | ||||
rnh->rh.rnh_masks = rmh; | rnh->rh.rnh_masks = rmh; | ||||
/* Finally, set base callbacks */ | /* Finally, set base callbacks */ | ||||
rnh->rnh_addaddr = rn_addroute; | rnh->rnh_addaddr = rn_addroute; | ||||
rnh->rnh_deladdr = rn_delete; | rnh->rnh_deladdr = rn_delete; | ||||
rnh->rnh_matchaddr = rn_match; | rnh->rnh_matchaddr = rn_match; | ||||
rnh->rnh_lookup = rn_lookup; | rnh->rnh_lookup = rn_lookup; | ||||
Show All 37 Lines |