Changeset View
Changeset View
Standalone View
Standalone View
sys/net/radix.c
Show First 20 Lines • Show All 121 Lines • ▼ Show 20 Lines | |||||
* | * | ||||
* To make the assumption more explicit, we use the LEN() macro to access | * To make the assumption more explicit, we use the LEN() macro to access | ||||
* this field. It is safe to pass an expression with side effects | * this field. It is safe to pass an expression with side effects | ||||
* to LEN() as the argument is evaluated only once. | * to LEN() as the argument is evaluated only once. | ||||
* We cast the result to int as this is the dominant usage. | * We cast the result to int as this is the dominant usage. | ||||
*/ | */ | ||||
#define LEN(x) ( (int) (*(const u_char *)(x)) ) | #define LEN(x) ( (int) (*(const u_char *)(x)) ) | ||||
#define RN_IS_ROOT(_rn) (((_rn)->rn_flags & RNF_ROOT) != 0) | |||||
#define RN_IS_LEAF(_rn) ((_rn)->rn_bit < 0) | |||||
/* | /* | ||||
* XXX THIS NEEDS TO BE FIXED | * XXX THIS NEEDS TO BE FIXED | ||||
* In the code, pointers to keys and masks are passed as either | * In the code, pointers to keys and masks are passed as either | ||||
* 'void *' (because callers use to pass pointers of various kinds), or | * 'void *' (because callers use to pass pointers of various kinds), or | ||||
* 'caddr_t' (which is fine for pointer arithmetics, but not very | * 'caddr_t' (which is fine for pointer arithmetics, but not very | ||||
* clean when you dereference it to access data). Furthermore, caddr_t | * clean when you dereference it to access data). Furthermore, caddr_t | ||||
* is really 'char *', while the natural type to operate on keys and | * is really 'char *', while the natural type to operate on keys and | ||||
* masks would be 'u_char'. This mismatch require a lot of casts and | * masks would be 'u_char'. This mismatch require a lot of casts and | ||||
▲ Show 20 Lines • Show All 226 Lines • ▼ Show 20 Lines | while (m) { | ||||
x = x->rn_dupedkey; | x = x->rn_dupedkey; | ||||
if (x && rn_satisfies_leaf(v, x, off)) | if (x && rn_satisfies_leaf(v, x, off)) | ||||
return (x); | return (x); | ||||
} | } | ||||
m = m->rm_mklist; | m = m->rm_mklist; | ||||
} | } | ||||
} while (t != top); | } while (t != top); | ||||
return (0); | return (0); | ||||
} | |||||
static int | |||||
get_mlen_bits(const struct radix_node *rn) | |||||
{ | |||||
if (rn->rn_mask == NULL) { | |||||
return ((LEN(rn->rn_key) * 8)); | |||||
} | |||||
return (-(1 + rn->rn_bit)); | |||||
} | |||||
struct radix_node * | |||||
rn_get_parent(const struct radix_head *head, struct radix_node *rn) | |||||
{ | |||||
struct radix_node *rn_parent; | |||||
const char *rn_prefix = rn->rn_key; | |||||
int mlen = get_mlen_bits(rn); | |||||
int tree_off = head->rnh_treetop->rn_offset; | |||||
rn_parent = rn_nextprefix(rn); | |||||
if (rn_parent != NULL) | |||||
return (rn_parent); | |||||
while (!RN_IS_ROOT(rn)) { | |||||
/* | |||||
* Go up the tree to consider key candidates one-by-one. | |||||
* For each parent, go down to the leftmost leaf node & | |||||
* check if the masks are wide enough to match the original node. | |||||
*/ | |||||
rn = rn->rn_parent; | |||||
/* Now dive left to find the leaf node */ | |||||
struct radix_node *rn_l = rn->rn_left; | |||||
while (rn_l != NULL && !RN_IS_LEAF(rn_l)) | |||||
rn_l = rn_l->rn_left; | |||||
/* now rn_left is either NULL or a leaf */ | |||||
for (; rn_l != NULL; rn_l = rn_nextprefix(rn_l)) { | |||||
if (RN_IS_ROOT(rn_l) || get_mlen_bits(rn_l) >= mlen) | |||||
continue; | |||||
if (rn_satisfies_leaf(rn_prefix, rn_l, tree_off)) | |||||
return (rn_l); | |||||
} | |||||
} | |||||
return (NULL); | |||||
} | } | ||||
/* | /* | ||||
* Returns the next (wider) prefix for the key defined by @rn | * Returns the next (wider) prefix for the key defined by @rn | ||||
* if exists. | * if exists. | ||||
*/ | */ | ||||
struct radix_node * | struct radix_node * | ||||
rn_nextprefix(struct radix_node *rn) | rn_nextprefix(struct radix_node *rn) | ||||
▲ Show 20 Lines • Show All 826 Lines • Show Last 20 Lines |