47 {0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, -1};
50 #define rn_masktop (mask_rnhead->rnh_treetop) 63 #define SUBTREE_OPEN "[ " 64 #define SUBTREE_CLOSE " ]" 70 #define MIN(x,y) (((x)<(y))?(x):(y)) 77 memset(rm, 0,
sizeof(*rm));
88 #define R_Malloc(p, t, n) \ 90 p = (t) clib_mem_alloc((unsigned int)(n)); \ 93 #define Free(p) clib_mem_free((p)) 94 #define log(a,b, c...) 136 const u8 *
const v = v_arg;
139 for (x = head; x->
rn_b >= 0;) {
155 const u8 *
const v = v_arg;
156 const u8 *
const m = m_arg;
158 for (x = head; x->
rn_b >= 0;) {
173 const char *m = m_arg;
174 const char *n = n_arg;
175 const char *lim = n + *(
const u8 *)n;
176 const char *lim2 = lim;
177 int longer = (*(
const u8 *)n++) - (int)(*(
const u8 *)m++);
178 int masks_are_equal = 1;
191 if (masks_are_equal && (longer < 0))
192 for (lim2 = m - longer; m < lim2; )
195 return !masks_are_equal;
205 const char *netmask =
NULL;
214 while (x !=
NULL && x->rn_mask != netmask)
226 const char *cp = trial;
227 const char *cp2 = leaf->rn_key;
228 const char *cp3 = leaf->rn_mask;
230 int length =
MIN(*(
const u8 *)cp, *(
const u8 *)cp2);
235 length =
MIN(length, *(
const u8 *)cp3);
236 cplim = cp + length; cp3 += skip; cp2 += skip;
237 for (cp += skip; cp < cplim; cp++, cp2++, cp3++)
238 if ((*cp ^ *cp2) & *cp3)
248 const char *
const v = v_arg;
257 int vlen = *(
const u8 *)cp;
265 for (; t->
rn_b >= 0; ) {
283 vlen = *(
const u8 *)t->rn_mask;
284 cp += off; cp2 = t->rn_key + off; cplim = v + vlen;
285 for (; cp < cplim; cp++, cp2++)
296 test = (*cp ^ *cp2) & 0xff;
297 for (b = 7; (test >>= 1) > 0;)
299 matched_off = cp -
v;
300 b += matched_off << 3;
305 if ((saved_t = t)->rn_mask == 0)
307 for (; t; t = t->rn_dupedkey)
336 off =
MIN(t->rn_off, matched_off);
338 while (x && x->rn_mask != m->rm_mask)
354 (*printer)(arg,
"%s(%s%p: p<%p> l<%p> r<%p>)",
355 delim, ((
void *)rn == arg) ?
"*" :
"", rn, rn->
rn_p,
363 rn_dbg_print(
void *arg,
const char *fmt, ...)
368 vlog(LOG_DEBUG, fmt, ap);
385 for (dup = rn; dup !=
NULL; dup = dup->rn_dupedkey) {
398 #define traverse(__head, __rn) rn_treeprint((__head), rn_dbg_print, (__rn)) 410 t->rn_l = tt; t->rn_off = b >> 3;
411 tt->
rn_b = -1; tt->rn_key =
v; tt->
rn_p = t;
426 const char *
v = v_arg;
427 int head_off = top->rn_off;
428 int vlen = *((
const u8 *)v);
429 const char *cp = v + head_off;
435 const char *cp2 = t->rn_key + head_off;
436 const char *cplim = v + vlen;
446 cmp_res = (cp[-1] ^ cp2[-1]) & 0xff;
447 for (b = (cp - v) << 3; cmp_res; b--)
458 }
while (b > (
unsigned) x->
rn_b);
461 log(LOG_DEBUG,
"%s: Going In:\n", __func__), traverse(head, p);
463 t =
rn_newpair(v_arg, b, nodes); tt = t->rn_l;
464 if ((cp[p->rn_off] & p->
rn_bmask) == 0)
469 if ((cp[t->rn_off] & t->
rn_bmask) == 0) {
472 t->rn_r = tt; t->rn_l = x;
476 log(LOG_DEBUG,
"%s: Coming Out:\n", __func__),
490 const char *netmask = n_arg;
496 int maskduplicated, m0, isnormal;
497 static int last_zeroed = 0;
499 if ((mlen = *(
const u8 *)netmask) > max_keylen)
506 memmove(addmask_key + 1, rn_ones + 1, skip - 1);
507 if ((m0 = mlen) > skip)
508 memmove(addmask_key + skip, netmask + skip, mlen - skip);
512 for (cp = addmask_key + mlen; (cp >
addmask_key) && cp[-1] == 0;)
516 if (m0 >= last_zeroed)
520 if (m0 < last_zeroed)
521 memset(addmask_key + m0, 0, last_zeroed - m0);
522 *addmask_key = last_zeroed = mlen;
524 if (memcmp(addmask_key, x->rn_key, mlen) != 0)
529 if ((saved_x = x) ==
NULL)
531 memset(x, 0, max_keylen + 2 *
sizeof (*x));
532 cp = netmask = (
void *)(x + 2);
533 memmove(x + 2, addmask_key, mlen);
534 x =
rn_insert(cp, mask_rnhead, &maskduplicated, x);
535 if (maskduplicated) {
536 log(LOG_ERR,
"rn_addmask: mask impossibly already in tree\n");
543 cplim = netmask + mlen; isnormal = 1;
544 for (cp = netmask + skip; (cp < cplim) && *(
const u8 *)cp == 0xff;)
547 for (j = 0x80; (j & *cp) != 0; j >>= 1)
549 if (*cp != normal_chars[b] || cp != (cplim - 1))
552 b += (cp - netmask) << 3;
564 const u8 *mp = m_arg;
565 const u8 *np = n_arg;
571 for (lim = mp + *mp; mp < lim;)
586 log(LOG_ERR,
"Mask for route not entered\n");
589 memset(m, 0,
sizeof(*m));
595 m->rm_mask = tt->rn_mask;
608 const char *
v = v_arg, *netmask = n_arg;
611 short b = 0, b_leaf = 0;
623 if (netmask !=
NULL) {
633 saved_tt = tt =
rn_insert(v, head, &keyduplicated, treenodes);
635 for (t = tt; tt !=
NULL; t = tt, tt = tt->rn_dupedkey) {
636 if (tt->rn_mask == netmask)
638 if (netmask ==
NULL ||
639 (tt->rn_mask !=
NULL &&
640 (b_leaf < tt->rn_b ||
658 if (tt == saved_tt) {
663 tt->rn_p = x = t->
rn_p;
676 tt->rn_dupedkey->
rn_p = tt;
685 if (netmask !=
NULL) {
686 tt->rn_mask = netmask;
693 b_leaf = -1 - t->
rn_b;
694 if (t->rn_r == saved_tt)
701 if (x->rn_mask !=
NULL && x->
rn_b >= b_leaf &&
713 if (m->
rm_b >= b_leaf)
726 }
while (b <= t->
rn_b && x != top);
734 if (m->
rm_b < b_leaf)
736 if (m->
rm_b > b_leaf)
739 mmask = m->rm_leaf->rn_mask;
741 log(LOG_ERR,
"Non-unique normal route," 742 " mask not entered\n");
747 if (mmask == netmask) {
762 const void *netmask_arg,
769 const char *
v, *netmask;
770 int b, head_off, vlen;
773 netmask = netmask_arg;
776 head_off = x->rn_off;
777 vlen = *(
const u8 *)v;
781 memcmp(v + head_off, tt->rn_key + head_off, vlen - head_off) != 0)
786 if (netmask !=
NULL) {
790 while (tt->rn_mask != netmask)
791 if ((tt = tt->rn_dupedkey) ==
NULL)
797 if (m->rm_leaf != tt || m->
rm_refs > 0) {
798 log(LOG_ERR,
"rn_delete: inconsistent annotation\n");
802 if (m->rm_mask != tt->rn_mask) {
803 log(LOG_ERR,
"rn_delete: inconsistent annotation\n");
816 }
while (b <= t->
rn_b && x != top);
825 log(LOG_ERR,
"rn_delete: couldn't find our annotation\n");
837 log(LOG_DEBUG,
"%s: Going In:\n", __func__), traverse(head, tt);
840 dupedkey = saved_tt->rn_dupedkey;
841 if (dupedkey !=
NULL) {
846 if (tt == saved_tt) {
855 for (x = p = saved_tt;
856 p !=
NULL && p->rn_dupedkey != tt;)
859 p->rn_dupedkey = tt->rn_dupedkey;
860 if (tt->rn_dupedkey !=
NULL)
861 tt->rn_dupedkey->
rn_p = p;
863 log(LOG_ERR,
"rn_delete: couldn't find us\n");
893 else if (x->
rn_b >= 0) {
903 x = x->rn_dupedkey) {
913 log(LOG_ERR,
"rn_delete: Orphaned Mask %p at %p\n",
934 log(LOG_DEBUG,
"%s: Coming Out:\n", __func__),
946 const void *netmask_arg,
964 for (rn = rn->
rn_p->rn_r; rn->
rn_b >= 0;) {
976 while (rn->
rn_b >= 0) {
1002 while ((rn = base) !=
NULL) {
1003 base = rn->rn_dupedkey;
1016 int (*matcher)(
struct radix_node *,
void *),
void *w)
1030 while ((rn = base) !=
NULL) {
1031 base = rn->rn_dupedkey;
1033 matched = (*matcher)(rn, w);
1066 memset(rnh, 0,
sizeof(*rnh));
1073 tt->
rn_b = -1 - off;
1089 R_Malloc(rn_zeros,
char *, 3 * max_keylen);
1090 if (rn_zeros ==
NULL)
1093 memset(rn_zeros, 0, 3 * max_keylen);
static clib_error_t * rn_module_init(vlib_main_t *vm)
struct radix_node * rnh_addaddr(const void *v, const void *mask, struct radix_node_head *head, struct radix_node nodes[])
static const char normal_chars[]
struct radix_node * rn_newpair(const void *v, int b, struct radix_node nodes[2])
struct radix_node * rnh_matchaddr(const void *v, struct radix_node_head *head)
struct radix_node rnh_nodes[3]
static struct radix_mask * rm_alloc(void)
struct radix_node * rn_search_m(const void *v_arg, struct radix_node *head, const void *m_arg)
struct radix_node * rn_insert(const void *v_arg, struct radix_node_head *head, int *dupentry, struct radix_node nodes[2])
#define VLIB_INIT_FUNCTION(x)
#define clib_error_return(e, args...)
int rn_refines(const void *m_arg, const void *n_arg)
struct radix_node * rnh_deladdr(const void *v, const void *mask, struct radix_node_head *head)
struct radix_mask * rm_mklist
struct radix_node * rn_lookup(const void *v_arg, const void *m_arg, struct radix_node_head *head)
struct radix_node * rnh_treetop
static void rm_free(struct radix_mask *rm)
static struct radix_node * rn_walkfirst(struct radix_node *, rn_printer_t, void *)
struct radix_node * rn_search(const void *v_arg, struct radix_node *head)
int rn_walktree(struct radix_node_head *h, int(*f)(struct radix_node *, void *), void *w)
struct radix_node * rn_delete1(const void *v_arg, const void *netmask_arg, struct radix_node_head *head, struct radix_node *rn)
struct radix_mask * rn_mklist
struct radix_node_head * mask_rnhead
struct radix_node * rn_addmask(const void *n_arg, int search, int skip)
static void clib_mem_free(void *p)
int rn_inithead(void **head, int off)
static struct radix_mask * rn_new_radix_mask(struct radix_node *, struct radix_mask *)
struct radix_node * rnh_lookup(const void *v, const void *mask, struct radix_node_head *head)
struct radix_node * rn_delete(const void *v_arg, const void *netmask_arg, struct radix_node_head *head)
static void * clib_mem_alloc(uword size)
static int rn_satisfies_leaf(const char *, struct radix_node *, int)
static char * addmask_key
int rn_inithead0(struct radix_node_head *rnh, int off)
#define R_Malloc(p, t, n)
void(* rn_printer_t)(void *, const char *fmt,...)
static void rn_nodeprint(struct radix_node *, rn_printer_t, void *, const char *)
struct radix_node * rn_addroute(const void *v_arg, const void *n_arg, struct radix_node_head *head, struct radix_node treenodes[2])
struct radix_mask * rn_mkfreelist
struct radix_node * rn_match(const void *v_arg, struct radix_node_head *head)
struct radix_node * rn_search_matched(struct radix_node_head *h, int(*matcher)(struct radix_node *, void *), void *w)
static struct radix_node * rn_walknext(struct radix_node *, rn_printer_t, void *)
static int rn_lexobetter(const void *, const void *)