Lines Matching +full:x +full:- +full:mask +full:-
1 /*-
2 * SPDX-License-Identifier: BSD-3-Clause
37 #define log(x, msg) syslog(x, msg) argument
49 #define rn_masktop (mask_rnhead->rnh_treetop)
63 * of a node n have keys whose bits all agree up to position rn_b - 1.
69 * A route is determined by a pair of key and mask. We require that the
70 * bit-wise logical and of the key and mask to be the key.
71 * We define the index of a route to associated with the mask to be
72 * the first bit number in the mask where 0 occurs (with bit number 0
75 * We say a mask is normal if every bit is 0, past the index of the mask.
77 * and m is a normal mask, then the route applies to every descendant of n.
82 * Similar logic shows that a non-normal mask m such that
84 * Thus, for each non-host route, we attach its mask to a list at an internal
87 * The present version of the code makes use of normal routes in short-
88 * circuiting an explicit mask and compare operation when testing whether
97 struct radix_node *x; in rn_search() local
100 for (x = head, v = v_arg; x->rn_b >= 0;) { in rn_search()
101 if (x->rn_bmask & v[x->rn_off]) in rn_search()
102 x = x->rn_r; in rn_search()
104 x = x->rn_l; in rn_search()
106 return (x); in rn_search()
114 struct radix_node *x; in rn_search_m() local
117 for (x = head; x->rn_b >= 0;) { in rn_search_m()
118 if ((x->rn_bmask & m[x->rn_off]) && in rn_search_m()
119 (x->rn_bmask & v[x->rn_off])) in rn_search_m()
120 x = x->rn_r; in rn_search_m()
122 x = x->rn_l; in rn_search_m()
124 return x; in rn_search_m()
132 int longer = (*(u_char *)n++) - (int)(*(u_char *)m++); in rn_refines()
136 lim -= longer; in rn_refines()
147 for (lim2 = m - longer; m < lim2; ) in rn_refines()
156 struct radix_node *x; in rn_lookup() local
160 if ((x = rn_addmask(m_arg, 1, in rn_lookup()
161 head->rnh_treetop->rn_off)) == NULL) in rn_lookup()
163 netmask = x->rn_key; in rn_lookup()
165 x = rn_match(v_arg, head); in rn_lookup()
166 if (x && netmask) { in rn_lookup()
167 while (x && x->rn_mask != netmask) in rn_lookup()
168 x = x->rn_dupedkey; in rn_lookup()
170 return x; in rn_lookup()
178 char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; in rn_satisfies_leaf()
198 struct radix_node *t = head->rnh_treetop, *x; in rn_match() local
202 int off = t->rn_off, vlen = *(u_char *)cp, matched_off; in rn_match()
209 for (; t->rn_b >= 0; ) { in rn_match()
210 if (t->rn_bmask & cp[t->rn_off]) in rn_match()
211 t = t->rn_r; in rn_match()
213 t = t->rn_l; in rn_match()
217 * or at least learn how many bits match, for normal mask finesse. in rn_match()
220 * to the length of the mask, since if it matches we had a genuine in rn_match()
226 if (t->rn_mask) in rn_match()
227 vlen = *(u_char *)t->rn_mask; in rn_match()
228 cp += off; cp2 = t->rn_key + off; cplim = v + vlen; in rn_match()
244 if (!(t->rn_flags & RNF_ROOT)) in rn_match()
246 if (t->rn_dupedkey) { in rn_match()
247 t = t->rn_dupedkey; in rn_match()
250 if (*(cp-1) == 0) in rn_match()
257 b--; in rn_match()
259 matched_off = cp - v; in rn_match()
261 rn_b = -1 - b; in rn_match()
263 * If there is a host route in a duped-key chain, it will be first. in rn_match()
265 if ((saved_t = t)->rn_mask == 0) in rn_match()
266 t = t->rn_dupedkey; in rn_match()
267 for (; t; t = t->rn_dupedkey) { in rn_match()
273 if (t->rn_flags & RNF_NORMAL) { in rn_match()
274 if (rn_b <= t->rn_b) in rn_match()
284 t = t->rn_p; in rn_match()
285 if ((m = t->rn_mklist)) { in rn_match()
287 * If non-contiguous masks ever become important in rn_match()
293 if (m->rm_flags & RNF_NORMAL) { in rn_match()
294 if (rn_b <= m->rm_b) in rn_match()
295 return (m->rm_leaf); in rn_match()
297 off = min(t->rn_off, matched_off); in rn_match()
298 x = rn_search_m(v, t, m->rm_mask); in rn_match()
299 while (x && x->rn_mask != m->rm_mask) in rn_match()
300 x = x->rn_dupedkey; in rn_match()
301 if (x && rn_satisfies_leaf(v, x, off)) in rn_match()
302 return x; in rn_match()
304 } while ((m = m->rm_mklist)); in rn_match()
321 t->rn_b = b; t->rn_bmask = 0x80 >> (b & 7); in rn_newpair()
322 t->rn_l = tt; t->rn_off = b >> 3; in rn_newpair()
323 tt->rn_b = -1; tt->rn_key = (caddr_t)v; tt->rn_p = t; in rn_newpair()
324 tt->rn_flags = t->rn_flags = RNF_ACTIVE; in rn_newpair()
326 tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; in rn_newpair()
327 tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; in rn_newpair()
339 struct radix_node *top = head->rnh_treetop; in rn_insert()
340 int head_off = top->rn_off, vlen = (int)*((u_char *)v); in rn_insert()
347 * Find first bit at which v and t->rn_key differ in rn_insert()
350 caddr_t cp2 = t->rn_key + head_off; in rn_insert()
358 if (!(t->rn_flags & RNF_ROOT) || *(cp2-1) == 0) { in rn_insert()
364 cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; in rn_insert()
365 for (b = (cp - v) << 3; cmp_res; b--) in rn_insert()
369 struct radix_node *p, *x = top; in rn_insert() local
372 p = x; in rn_insert()
373 if (cp[x->rn_off] & x->rn_bmask) in rn_insert()
374 x = x->rn_r; in rn_insert()
375 else x = x->rn_l; in rn_insert()
376 } while ((unsigned)b > (unsigned)x->rn_b); in rn_insert()
381 t = rn_newpair(v_arg, b, nodes); tt = t->rn_l; in rn_insert()
382 if ((cp[p->rn_off] & p->rn_bmask) == 0) in rn_insert()
383 p->rn_l = t; in rn_insert()
385 p->rn_r = t; in rn_insert()
386 x->rn_p = t; t->rn_p = p; /* frees x, p as temp vars below */ in rn_insert()
387 if ((cp[t->rn_off] & t->rn_bmask) == 0) { in rn_insert()
388 t->rn_r = x; in rn_insert()
390 t->rn_r = tt; t->rn_l = x; in rn_insert()
404 struct radix_node *x; in rn_addmask() local
416 return (mask_rnhead->rnh_nodes); in rn_addmask()
418 Bcopy(rn_ones + 1, addmask_key + 1, skip - 1); in rn_addmask()
420 Bcopy(netmask + skip, addmask_key + skip, mlen - skip); in rn_addmask()
424 for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0;) in rn_addmask()
425 cp--; in rn_addmask()
426 mlen = cp - addmask_key; in rn_addmask()
430 return (mask_rnhead->rnh_nodes); in rn_addmask()
433 Bzero(addmask_key + m0, last_zeroed - m0); in rn_addmask()
435 x = rn_search(addmask_key, rn_masktop); in rn_addmask()
436 if (Bcmp(addmask_key, x->rn_key, mlen) != 0) in rn_addmask()
437 x = NULL; in rn_addmask()
438 if (x || search) in rn_addmask()
439 return (x); in rn_addmask()
440 x = (struct radix_node *)rtmalloc(max_keylen + 2*sizeof(*x), in rn_addmask()
442 saved_x = x; in rn_addmask()
443 Bzero(x, max_keylen + 2 * sizeof (*x)); in rn_addmask()
444 netmask = cp = (caddr_t)(x + 2); in rn_addmask()
446 x = rn_insert(cp, mask_rnhead, &maskduplicated, x); in rn_addmask()
448 log(LOG_ERR, "rn_addmask: mask impossibly already in tree"); in rn_addmask()
450 return (x); in rn_addmask()
453 * Calculate index of mask, and check for normalcy. in rn_addmask()
461 if (*cp != normal_chars[b] || cp != (cplim - 1)) in rn_addmask()
464 b += (cp - netmask) << 3; in rn_addmask()
465 x->rn_b = -1 - b; in rn_addmask()
467 x->rn_flags |= RNF_NORMAL; in rn_addmask()
468 return (x); in rn_addmask()
471 static int /* XXX: arbitrary ordering for non-contiguous masks */
493 log(LOG_ERR, "Mask for route not entered\n"); in rn_new_radix_mask()
497 m->rm_b = tt->rn_b; in rn_new_radix_mask()
498 m->rm_flags = tt->rn_flags; in rn_new_radix_mask()
499 if (tt->rn_flags & RNF_NORMAL) in rn_new_radix_mask()
500 m->rm_leaf = tt; in rn_new_radix_mask()
502 m->rm_mask = tt->rn_mask; in rn_new_radix_mask()
503 m->rm_mklist = next; in rn_new_radix_mask()
504 tt->rn_mklist = m; in rn_new_radix_mask()
515 struct radix_node *t, *x = NULL, *tt; in rn_addroute() local
516 struct radix_node *saved_tt, *top = head->rnh_treetop; in rn_addroute()
523 * In dealing with non-contiguous masks, there may be in rn_addroute()
524 * many different routes which have the same mask. in rn_addroute()
526 * the mask to speed avoiding duplicate references at in rn_addroute()
530 if ((x = rn_addmask(netmask, 0, top->rn_off)) == NULL) in rn_addroute()
532 b_leaf = x->rn_b; in rn_addroute()
533 b = -1 - x->rn_b; in rn_addroute()
534 netmask = x->rn_key; in rn_addroute()
541 for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) { in rn_addroute()
542 if (tt->rn_mask == netmask) in rn_addroute()
545 (tt->rn_mask && in rn_addroute()
546 ((b_leaf < tt->rn_b) || /* index(netmask) > node */ in rn_addroute()
547 rn_refines(netmask, tt->rn_mask) || in rn_addroute()
548 rn_lexobetter(netmask, tt->rn_mask)))) in rn_addroute()
552 * If the mask is not duplicated, we wouldn't in rn_addroute()
557 * in a masklist -- most specific to least specific. in rn_addroute()
562 struct radix_node *xx = x; in rn_addroute()
564 (tt = treenodes)->rn_dupedkey = t; in rn_addroute()
565 tt->rn_flags = t->rn_flags; in rn_addroute()
566 tt->rn_p = x = t->rn_p; in rn_addroute()
567 if (x->rn_l == t) x->rn_l = tt; else x->rn_r = tt; in rn_addroute()
568 saved_tt = tt; x = xx; in rn_addroute()
570 (tt = treenodes)->rn_dupedkey = t->rn_dupedkey; in rn_addroute()
571 t->rn_dupedkey = tt; in rn_addroute()
574 t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; in rn_addroute()
575 tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; in rn_addroute()
577 tt->rn_key = (caddr_t) v; in rn_addroute()
578 tt->rn_b = -1; in rn_addroute()
579 tt->rn_flags = RNF_ACTIVE; in rn_addroute()
582 * Put mask in tree. in rn_addroute()
585 tt->rn_mask = netmask; in rn_addroute()
586 tt->rn_b = x->rn_b; in rn_addroute()
587 tt->rn_flags |= x->rn_flags & RNF_NORMAL; in rn_addroute()
589 t = saved_tt->rn_p; in rn_addroute()
592 b_leaf = -1 - t->rn_b; in rn_addroute()
593 if (t->rn_r == saved_tt) x = t->rn_l; else x = t->rn_r; in rn_addroute()
595 if (x->rn_b < 0) { in rn_addroute()
596 for (mp = &t->rn_mklist; x; x = x->rn_dupedkey) in rn_addroute()
597 if (x->rn_mask && (x->rn_b >= b_leaf) && x->rn_mklist == 0) { in rn_addroute()
598 if ((*mp = m = rn_new_radix_mask(x, 0))) in rn_addroute()
599 mp = &m->rm_mklist; in rn_addroute()
601 } else if (x->rn_mklist) { in rn_addroute()
605 for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) in rn_addroute()
606 if (m->rm_b >= b_leaf) in rn_addroute()
608 t->rn_mklist = m; *mp = NULL; in rn_addroute()
612 if ((netmask == 0) || (b > t->rn_b )) in rn_addroute()
614 b_leaf = tt->rn_b; in rn_addroute()
616 x = t; in rn_addroute()
617 t = t->rn_p; in rn_addroute()
618 } while (b <= t->rn_b && x != top); in rn_addroute()
625 for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) { in rn_addroute()
626 if (m->rm_b < b_leaf) in rn_addroute()
628 if (m->rm_b > b_leaf) in rn_addroute()
630 if (m->rm_flags & RNF_NORMAL) { in rn_addroute()
631 mmask = m->rm_leaf->rn_mask; in rn_addroute()
632 if (tt->rn_flags & RNF_NORMAL) { in rn_addroute()
634 "Non-unique normal route, mask not entered"); in rn_addroute()
638 mmask = m->rm_mask; in rn_addroute()
640 m->rm_refs++; in rn_addroute()
641 tt->rn_mklist = m; in rn_addroute()
656 struct radix_node *t, *p, *x, *tt; in rn_delete() local
664 x = head->rnh_treetop; in rn_delete()
665 tt = rn_search(v, x); in rn_delete()
666 head_off = x->rn_off; in rn_delete()
669 top = x; in rn_delete()
671 Bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off)) in rn_delete()
674 * Delete our route from mask lists. in rn_delete()
677 if ((x = rn_addmask(netmask, 1, head_off)) == NULL) in rn_delete()
679 netmask = x->rn_key; in rn_delete()
680 while (tt->rn_mask != netmask) in rn_delete()
681 if ((tt = tt->rn_dupedkey) == NULL) in rn_delete()
684 if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == NULL) in rn_delete()
686 if (tt->rn_flags & RNF_NORMAL) { in rn_delete()
687 if (m->rm_leaf != tt || m->rm_refs > 0) { in rn_delete()
692 if (m->rm_mask != tt->rn_mask) { in rn_delete()
696 if (--m->rm_refs >= 0) in rn_delete()
699 b = -1 - tt->rn_b; in rn_delete()
700 t = saved_tt->rn_p; in rn_delete()
701 if (b > t->rn_b) in rn_delete()
704 x = t; in rn_delete()
705 t = t->rn_p; in rn_delete()
706 } while (b <= t->rn_b && x != top); in rn_delete()
707 for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) in rn_delete()
709 *mp = m->rm_mklist; in rn_delete()
715 if (tt->rn_flags & RNF_NORMAL) in rn_delete()
722 if (tt->rn_flags & RNF_ROOT) in rn_delete()
726 for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {} in rn_delete()
727 if (t) t->rn_ybro = tt->rn_ybro; in rn_delete()
729 t = tt->rn_p; in rn_delete()
730 if ((dupedkey = saved_tt->rn_dupedkey)) { in rn_delete()
732 x = dupedkey; x->rn_p = t; in rn_delete()
733 if (t->rn_l == tt) t->rn_l = x; else t->rn_r = x; in rn_delete()
735 for (x = p = saved_tt; p && p->rn_dupedkey != tt;) in rn_delete()
736 p = p->rn_dupedkey; in rn_delete()
737 if (p) p->rn_dupedkey = tt->rn_dupedkey; in rn_delete()
741 if (t->rn_flags & RNF_ACTIVE) { in rn_delete()
743 *++x = *t; p = t->rn_p; in rn_delete()
745 b = t->rn_info; *++x = *t; t->rn_info = b; p = t->rn_p; in rn_delete()
747 if (p->rn_l == t) p->rn_l = x; else p->rn_r = x; in rn_delete()
748 x->rn_l->rn_p = x; x->rn_r->rn_p = x; in rn_delete()
752 if (t->rn_l == tt) x = t->rn_r; else x = t->rn_l; in rn_delete()
753 p = t->rn_p; in rn_delete()
754 if (p->rn_r == t) p->rn_r = x; else p->rn_l = x; in rn_delete()
755 x->rn_p = p; in rn_delete()
759 if (t->rn_mklist) { in rn_delete()
760 if (x->rn_b >= 0) { in rn_delete()
761 for (mp = &x->rn_mklist; (m = *mp);) in rn_delete()
762 mp = &m->rm_mklist; in rn_delete()
763 *mp = t->rn_mklist; in rn_delete()
765 /* If there are any key,mask pairs in a sibling in rn_delete()
766 duped-key chain, some subset will appear sorted in rn_delete()
768 for (m = t->rn_mklist; m && x; x = x->rn_dupedkey) in rn_delete()
769 if (m == x->rn_mklist) { in rn_delete()
770 struct radix_mask *mm = m->rm_mklist; in rn_delete()
771 x->rn_mklist = 0; in rn_delete()
772 if (--(m->rm_refs) < 0) in rn_delete()
777 syslog(LOG_ERR, "%s 0x%lx at 0x%lx\n", in rn_delete()
778 "rn_delete: Orphaned Mask", in rn_delete()
780 (unsigned long)x); in rn_delete()
786 x = tt + 1; in rn_delete()
787 if (t != x) { in rn_delete()
789 *t = *x; in rn_delete()
791 b = t->rn_info; *t = *x; t->rn_info = b; in rn_delete()
793 t->rn_l->rn_p = t; t->rn_r->rn_p = t; in rn_delete()
794 p = x->rn_p; in rn_delete()
795 if (p->rn_l == x) p->rn_l = t; else p->rn_r = t; in rn_delete()
798 tt->rn_flags &= ~RNF_ACTIVE; in rn_delete()
810 struct radix_node *rn = h->rnh_treetop; in rn_walktree()
817 while (rn->rn_b >= 0) in rn_walktree()
818 rn = rn->rn_l; in rn_walktree()
822 while (rn->rn_p->rn_r == rn && (rn->rn_flags & RNF_ROOT) == 0) in rn_walktree()
823 rn = rn->rn_p; in rn_walktree()
825 for (rn = rn->rn_p->rn_r; rn->rn_b >= 0;) in rn_walktree()
826 rn = rn->rn_l; in rn_walktree()
830 base = rn->rn_dupedkey; in rn_walktree()
831 if (!(rn->rn_flags & RNF_ROOT) && (error = (*f)(rn, w))) in rn_walktree()
835 if (rn->rn_flags & RNF_ROOT) in rn_walktree()
851 t = rn_newpair(rn_zeros, off, rnh->rnh_nodes); in rn_inithead()
852 ttt = rnh->rnh_nodes + 2; in rn_inithead()
853 t->rn_r = ttt; in rn_inithead()
854 t->rn_p = t; in rn_inithead()
855 tt = t->rn_l; in rn_inithead()
856 tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; in rn_inithead()
857 tt->rn_b = -1 - off; in rn_inithead()
859 ttt->rn_key = rn_ones; in rn_inithead()
860 rnh->rnh_addaddr = rn_addroute; in rn_inithead()
861 rnh->rnh_deladdr = rn_delete; in rn_inithead()
862 rnh->rnh_matchaddr = rn_match; in rn_inithead()
863 rnh->rnh_lookup = rn_lookup; in rn_inithead()
864 rnh->rnh_walktree = rn_walktree; in rn_inithead()
865 rnh->rnh_treetop = t; in rn_inithead()
882 *cp++ = -1; in rn_init()