Changeset View
Changeset View
Standalone View
Standalone View
sys/net/radix.c
Show First 20 Lines • Show All 57 Lines • ▼ Show 20 Lines | |||||
#include <net/radix.h> | #include <net/radix.h> | ||||
#endif /* !_KERNEL */ | #endif /* !_KERNEL */ | ||||
static struct radix_node | static struct radix_node | ||||
*rn_insert(void *, struct radix_head *, int *, | *rn_insert(void *, struct radix_head *, int *, | ||||
struct radix_node [2]), | struct radix_node [2]), | ||||
*rn_newpair(void *, int, struct radix_node[2]), | *rn_newpair(void *, int, struct radix_node[2]), | ||||
*rn_search(void *, struct radix_node *), | *rn_search(void *, struct radix_node *), | ||||
*rn_search_m(void *, struct radix_node *, void *); | *rn_search_m(const void *, struct radix_node *, void *); | ||||
static struct radix_node *rn_addmask(void *, struct radix_mask_head *, int,int); | static struct radix_node *rn_addmask(void *, struct radix_mask_head *, int,int); | ||||
static void rn_detachhead_internal(struct radix_head *); | static void rn_detachhead_internal(struct radix_head *); | ||||
#define RADIX_MAX_KEY_LEN 32 | #define RADIX_MAX_KEY_LEN 32 | ||||
static char rn_zeros[RADIX_MAX_KEY_LEN]; | static char rn_zeros[RADIX_MAX_KEY_LEN]; | ||||
static char rn_ones[RADIX_MAX_KEY_LEN] = { | static char rn_ones[RADIX_MAX_KEY_LEN] = { | ||||
-1, -1, -1, -1, -1, -1, -1, -1, | -1, -1, -1, -1, -1, -1, -1, -1, | ||||
-1, -1, -1, -1, -1, -1, -1, -1, | -1, -1, -1, -1, -1, -1, -1, -1, | ||||
-1, -1, -1, -1, -1, -1, -1, -1, | -1, -1, -1, -1, -1, -1, -1, -1, | ||||
-1, -1, -1, -1, -1, -1, -1, -1, | -1, -1, -1, -1, -1, -1, -1, -1, | ||||
}; | }; | ||||
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(const 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 65 Lines • ▼ Show 20 Lines | rn_search(void *v_arg, struct radix_node *head) | ||||
return (x); | return (x); | ||||
} | } | ||||
/* | /* | ||||
* Same as above, but with an additional mask. | * Same as above, but with an additional mask. | ||||
* XXX note this function is used only once. | * XXX note this function is used only once. | ||||
*/ | */ | ||||
static struct radix_node * | static struct radix_node * | ||||
rn_search_m(void *v_arg, struct radix_node *head, void *m_arg) | rn_search_m(const void *v_arg, struct radix_node *head, void *m_arg) | ||||
{ | { | ||||
struct radix_node *x; | struct radix_node *x; | ||||
caddr_t v = v_arg, m = m_arg; | c_caddr_t v = v_arg, m = m_arg; | ||||
for (x = head; x->rn_bit >= 0;) { | for (x = head; x->rn_bit >= 0;) { | ||||
if ((x->rn_bmask & m[x->rn_offset]) && | if ((x->rn_bmask & m[x->rn_offset]) && | ||||
(x->rn_bmask & v[x->rn_offset])) | (x->rn_bmask & v[x->rn_offset])) | ||||
x = x->rn_right; | x = x->rn_right; | ||||
else | else | ||||
x = x->rn_left; | x = x->rn_left; | ||||
} | } | ||||
▲ Show 20 Lines • Show All 69 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(const char *trial, struct radix_node *leaf, int skip, | ||||
int salen) | |||||
{ | { | ||||
char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; | const char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; | ||||
char *cplim; | const 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 * | static inline struct radix_node * | ||||
rn_match(void *v_arg, struct radix_head *head) | rn_match_internal(const void *v_arg, struct radix_head *head, int salen) | ||||
{ | { | ||||
caddr_t v = v_arg; | c_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; | c_caddr_t cp = v, cp2; | ||||
caddr_t cplim; | c_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; | 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); | ||||
} | } | ||||
struct radix_node * | |||||
rn_match(const void *v_arg, struct radix_head *head) | |||||
{ | |||||
return (rn_match_internal(v_arg, head, LEN(v_arg))); | |||||
} | |||||
struct radix_node * | |||||
rn_match_fixed(const void *v_arg, struct radix_head *head) | |||||
{ | |||||
return (rn_match_internal(v_arg, head, head->rnh_treetop->rn_salen)); | |||||
} | |||||
#ifdef RN_DEBUG | #ifdef RN_DEBUG | ||||
int rn_nodenum; | int rn_nodenum; | ||||
struct radix_node *rn_clist; | struct radix_node *rn_clist; | ||||
int rn_saveinfo; | int rn_saveinfo; | ||||
int rn_debug = 1; | int rn_debug = 1; | ||||
#endif | #endif | ||||
/* | /* | ||||
▲ Show 20 Lines • Show All 719 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) | |||||
{ | { | ||||
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; | ||||
tt = t->rn_left; /* ... which in turn is base_nodes */ | tt = t->rn_left; /* ... which in turn is base_nodes */ | ||||
▲ Show 20 Lines • Show All 51 Lines • ▼ Show 20 Lines | rn_inithead(void **head, int off) | ||||
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; | ||||
rnh->rnh_walktree = rn_walktree; | rnh->rnh_walktree = rn_walktree; | ||||
rnh->rnh_walktree_from = rn_walktree_from; | rnh->rnh_walktree_from = rn_walktree_from; | ||||
return (1); | return (1); | ||||
} | } | ||||
/* Sets lookup _key_ length for the constant-length keys */ | |||||
void | |||||
rn_setkeylen(struct radix_head *rh, int keylen) | |||||
{ | |||||
struct radix_node *t; | |||||
t = rh->rnh_treetop; | |||||
t->rn_salen = t->rn_offset + keylen; | |||||
} | |||||
static int | static int | ||||
rn_freeentry(struct radix_node *rn, void *arg) | rn_freeentry(struct radix_node *rn, void *arg) | ||||
{ | { | ||||
struct radix_head * const rnh = arg; | struct radix_head * const rnh = arg; | ||||
struct radix_node *x; | struct radix_node *x; | ||||
x = (struct radix_node *)rn_delete(rn + 2, NULL, rnh); | x = (struct radix_node *)rn_delete(rn + 2, NULL, rnh); | ||||
Show All 24 Lines |