1 /* $OpenBSD: radish.c,v 1.4 2015/12/17 08:01:55 tb Exp $ */ 2 #ifndef GENERIC_USE 3 #define GENERIC_USE 4 #endif 5 /* 6 * Copyright (C) 1995, 1996, 1997, and 1998 WIDE Project. 7 * All rights reserved. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 3. Neither the name of the project nor the names of its contributors 18 * may be used to endorse or promote products derived from this software 19 * without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND 22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 * ARE DISCLAIMED. IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE 25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 * 33 */ 34 35 /* 36 * radish.c 37 * 38 * Version: 0.9 39 * Created: May 27, 1995 40 * Modified: January 28, 1997 41 * Author: Kazu YAMAMOTO 42 * Email: kazu@is.aist-nara.ac.jp 43 */ 44 45 #ifdef RADISH 46 #include <sys/types.h> 47 #include <sys/socket.h> 48 #include <sys/socketvar.h> 49 #include <string.h> 50 #include <stdlib.h> 51 #include <errno.h> 52 53 #if !defined(GENERIC_USE) && !defined(_ROUTE_H_) 54 #include <net/route.h> 55 #endif 56 57 #ifdef KERNEL 58 #include <net/radish.h> 59 #else /* KERNEL */ 60 #include "radish.h" 61 #endif /* KERNEL */ 62 63 #if defined(NO_SA_LEN) && !defined(SA_LEN) 64 #error requires sockaddr.sa_len or SA_LEN macro 65 #endif 66 67 68 #include <netinet/in.h> 69 #ifdef GENERIC_USE 70 #include <string.h> 71 #include <strings.h> 72 #include <stdlib.h> 73 #endif 74 75 #define M_DONTWAIT M_NOWAIT 76 #ifndef NULL 77 #define NULL 0 78 #endif 79 80 #ifdef KERNEL 81 #define FATAL(x) panic(x) 82 #elif defined(GENERIC_USE) 83 #define FATAL(x) return(-1); 84 #else 85 #define FATAL(x) exit(1) 86 #endif 87 88 static u_char rd_bmask [] = { 89 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 90 }; 91 92 static u_char rd_btest [] = { 93 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01, 94 }; 95 96 u_char rd_deleted_km[1024]; 97 98 /* 99 * return 1 if success 100 * return 0 if error 101 */ 102 int 103 rd_inithead(headp, family, slen, off, alen, match) 104 void **headp; 105 int family, slen, off, alen; 106 int (*match)(void *, void *); 107 { 108 struct radish_head *head; 109 struct radish *new; 110 struct sockaddr *masks; 111 u_char *m; 112 int num = alen * 8 + 1, i, j, q, r; 113 int len = sizeof(*head) + sizeof(*new) + slen * num; 114 115 if (*headp) return (1); 116 R_Malloc(head, struct radish_head *, len); 117 if (head == NULL) 118 return 0; 119 Bzero(head, len); 120 new = (struct radish *)(head + 1); 121 masks = (struct sockaddr *)(new +1); 122 *headp = head; 123 124 /* 125 * prepare all continuous masks 126 */ 127 m = (u_char *)masks; 128 for (i = 0; i < num; i++, m += slen) { 129 *m = slen; 130 *(m + 1) = family; 131 q = i >> 3; 132 r = i & 7; 133 for(j = 0; j < q; j++) 134 *(m + off + j) = 0xff; 135 *(m + off + j) = rd_bmask[r]; 136 } 137 138 head->rdh_slen = slen; 139 head->rdh_offset = off; 140 head->rdh_alen = alen; 141 head->rdh_masks = masks; 142 head->rdh_match = match; 143 head->rdh_top = new; 144 145 new->rd_route = masks; 146 new->rd_mask = masks; 147 new->rd_btest = rd_btest[0]; 148 /* other nembers are 0 */ 149 150 return(1); 151 } 152 153 struct sockaddr * 154 rd_mask(m_arg, head, maskp) 155 struct sockaddr *m_arg; 156 struct radish_head *head; 157 int *maskp; /* return value */ 158 { 159 u_char *mp, *masks = (u_char *)head->rdh_masks; 160 int off = head->rdh_offset; 161 int slen = head->rdh_slen; 162 int alen = head->rdh_alen; 163 int i = 0, masklen = 0; 164 165 if (m_arg == NULL) { 166 masklen = alen * 8; 167 *maskp = masklen; 168 return((struct sockaddr *)(masks + slen * masklen)); 169 } 170 mp = (u_char *)m_arg + off; 171 while ((i < alen) && (mp[i] == 0xff)) { 172 masklen += 8; 173 i++; 174 } 175 if (i < alen) 176 switch (mp[i]) { 177 case 0xfe: masklen += 7; break; 178 case 0xfc: masklen += 6; break; 179 case 0xf8: masklen += 5; break; 180 case 0xf0: masklen += 4; break; 181 case 0xe0: masklen += 3; break; 182 case 0xc0: masklen += 2; break; 183 case 0x80: masklen += 1; break; 184 case 0x00: break; 185 } 186 *maskp = masklen; 187 return((struct sockaddr *)(masks + slen * masklen)); 188 } 189 190 int 191 rd_insert(d_arg, m_arg, head, rt) 192 struct sockaddr *d_arg; 193 struct sockaddr *m_arg; 194 struct radish_head *head; 195 #ifdef GENERIC_USE 196 void *rt; 197 #else /* GENERIC_USE */ 198 struct rtentry *rt; 199 #endif /* GENERIC_USE */ 200 { 201 struct radish *cur = head->rdh_top, *parent, *new; 202 int off = head->rdh_offset; 203 int slen = head->rdh_slen; 204 int alen = head->rdh_alen; 205 int i, lim, q, r, masklen; 206 u_char *dp, *np, *rp; 207 struct sockaddr *mask; 208 209 mask = rd_mask(m_arg, head, &masklen); 210 q = masklen >> 3; 211 r = masklen & 7; 212 213 /* Allocate a new radish. 214 * This may be overhead in the case that 215 * masklen == cur->rd_masklen 216 * and 217 * route == dest. 218 */ 219 R_Malloc(new, struct radish *, sizeof(*new) + slen); 220 if (new == NULL) 221 return ENOBUFS; 222 Bzero(new, sizeof(*new) + slen); 223 new->rd_route = (struct sockaddr *)(new + 1); 224 new->rd_mask = mask; 225 new->rd_masklen = masklen; 226 new->rd_masklim = q; 227 new->rd_bmask = rd_bmask[r]; 228 new->rd_btest = rd_btest[r]; 229 new->rd_rtent = rt; 230 231 #ifndef GENERIC_USE 232 rt->rt_radish = new; 233 #endif /* GENERIC_USE */ 234 235 /* masked copy from dest to route */ 236 np = (u_char *)new->rd_route; 237 dp = (u_char *)d_arg; 238 *np = *dp; /* sa_len */ 239 np[1] = dp[1]; /* sa_family */ 240 dp += off; 241 np += off; 242 i = 0; 243 while (i < q) { 244 np[i] = dp[i]; 245 i++; 246 } 247 np[i] = dp[i] & rd_bmask[r]; /* just in case */ 248 249 while (cur) { 250 if (masklen == cur->rd_masklen) { 251 rp = (u_char *)cur->rd_route + off; 252 for (i = 0; i < alen; i++) 253 if (np[i] != rp[i]) { 254 /* 255 * masklen == cur->rd_masklen 256 * dest != route 257 */ 258 return rd_glue(cur, new, i, head); 259 } 260 /* 261 * masklen == cur->rd_masklen 262 * dest == route 263 */ 264 Free(new); 265 if (cur->rd_rtent != NULL) 266 return EEXIST; 267 cur->rd_rtent = rt; 268 #ifndef GENERIC_USE 269 rt->rt_radish = cur; 270 #endif /* GENERIC_USE */ 271 return 0; 272 } 273 /* 274 * masklen != cur->rd_masklen 275 */ 276 if (masklen > cur->rd_masklen) { 277 /* 278 * See if dest matches with cur node. 279 * (dest & mask) == route 280 */ 281 rp = (u_char *)cur->rd_route + off; 282 lim = cur->rd_masklim; 283 284 /* mask is continuous, thus mask is 0xff here. */ 285 for (i = 0; i < lim; i++) 286 if(np[i] != rp[i]) { 287 /* 288 * masklen > cur->rd_masklen 289 * (dest & mask) != route 290 */ 291 return rd_glue(cur, new, i, head); 292 } 293 if (cur->rd_bmask) 294 if ((np[lim] & cur->rd_bmask) != rp[lim]) { 295 /* 296 * masklen > cur->rd_masklen 297 * (dest & mask) != route 298 */ 299 return rd_glue(cur, new, lim, head); 300 } 301 /* 302 * masklen > cur->rd_masklen 303 * (dest & mask) == route 304 */ 305 if (cur->rd_btest & np[cur->rd_masklim]) { 306 if (cur->rd_r != NULL) { 307 cur = cur->rd_r; 308 continue; 309 } 310 cur->rd_r = new; 311 new->rd_p = cur; 312 return 0; 313 } else { 314 if (cur->rd_l != NULL) { 315 cur = cur->rd_l; 316 continue; 317 } 318 cur->rd_l = new; 319 new->rd_p = cur; 320 return 0; 321 } 322 } 323 /* 324 * masklen < cur->rd_masklen 325 */ 326 327 /* See if route matches with dest, be carefull! 328 * dest == (route & dest_mask) 329 */ 330 rp = (u_char *)cur->rd_route + off; 331 lim = new->rd_masklim; 332 333 /* mask is continuous, thus mask is 0xff here. */ 334 for (i = 0; i < lim; i++) 335 if(np[i] != rp[i]) { 336 /* 337 * masklen < cur->rd_masklen 338 * dest != (route & dest_mask) 339 */ 340 return rd_glue(cur, new, i, head); 341 } 342 if (new->rd_bmask) 343 if (np[lim] != (rp[lim] & new->rd_bmask)) { 344 /* 345 * masklen < cur->rd_masklen 346 * dest != (route & dest_mask) 347 */ 348 return rd_glue(cur, new, lim, head); 349 } 350 /* 351 * masklen < cur->rd_masklen 352 * dest == (route & dest_mask) 353 */ 354 355 /* put the new radish between cur and its parent */ 356 parent = cur->rd_p; 357 new->rd_p = parent; 358 if (parent->rd_l == cur) 359 parent->rd_l = new; 360 else if (parent->rd_r == cur) 361 parent->rd_r = new; 362 else 363 FATAL("rd_insert"); 364 if (new->rd_btest & rp[new->rd_masklim]) 365 new->rd_r = cur; 366 else 367 new->rd_l = cur; 368 369 cur->rd_p = new; 370 return 0; 371 } 372 return 1; 373 } 374 375 /* 376 * Insert a glue radish between the current and its parent. 377 * Let the current radish one child of glue radish. 378 * Let the new radish the other child of glue radish. 379 */ 380 int 381 rd_glue(cur, new, misbyte, head) 382 struct radish *cur, *new; 383 int misbyte; 384 struct radish_head *head; 385 { 386 struct radish *parent = cur->rd_p, *glue; 387 u_char *cp = (u_char *)cur->rd_route; 388 u_char *np = (u_char *)new->rd_route; 389 u_char *gp; 390 int off = head->rdh_offset, slen = head->rdh_slen; 391 int maskb, xor, i; 392 393 /* 394 * Glue radish 395 */ 396 R_Malloc(glue, struct radish *, sizeof(*glue) + slen); 397 if (glue == NULL) { 398 Free (new); 399 return ENOBUFS; 400 } 401 Bzero(glue, sizeof(*glue) + slen); 402 403 /* calculate a bit to test */ 404 xor = (*(cp + off + misbyte) ^ *(np + off + misbyte)) & 0xff; 405 maskb = 8; 406 while(xor) { 407 xor >>= 1; 408 maskb--; 409 } 410 411 glue->rd_route = (struct sockaddr *)(glue + 1); 412 glue->rd_masklen = 8 * misbyte + maskb; 413 glue->rd_masklim = misbyte; 414 glue->rd_bmask = rd_bmask[maskb]; 415 glue->rd_btest = rd_btest[maskb]; 416 glue->rd_rtent = NULL; 417 glue->rd_p = parent; 418 glue->rd_mask = (struct sockaddr *) 419 ((u_char *)head->rdh_masks + slen * glue->rd_masklen); 420 421 /* masked copy of route */ 422 gp = (u_char *)glue->rd_route; 423 *gp = *cp; /* sa_len */ 424 *(gp + 1) = *(cp + 1); /* sa_family */ 425 cp += off; 426 gp += off; 427 for(i = 0; i < misbyte; i++) 428 gp[i] = cp[i]; 429 gp[misbyte] = cp[misbyte] & glue->rd_bmask; 430 431 if (glue->rd_btest & cp[misbyte]) { 432 glue->rd_r = cur; 433 glue->rd_l = new; 434 } else { 435 glue->rd_r = new; 436 glue->rd_l = cur; 437 } 438 439 /* 440 * Children 441 */ 442 new->rd_p = cur->rd_p = glue; 443 444 /* 445 * Parent 446 */ 447 if (parent->rd_l == cur) 448 parent->rd_l = glue; 449 else if (parent->rd_r == cur) 450 parent->rd_r = glue; 451 else 452 FATAL("rd_insert"); 453 return 0; 454 } 455 456 /* 457 * Find the longest-match radish with the destination. 458 * Return 1 if success, otherwise return 0. 459 */ 460 461 int 462 rd_match(d_arg, head, rdp) 463 struct sockaddr *d_arg; 464 struct radish_head *head; 465 struct radish **rdp; /* return value */ 466 { 467 return rd_match_next(d_arg, head, rdp, NULL); 468 } 469 470 int 471 rd_match_next(d_arg, head, rdp, cur) 472 struct sockaddr *d_arg; 473 struct radish_head *head; 474 struct radish **rdp; /* return value */ 475 struct radish *cur; /* return value */ 476 { 477 struct radish *target = NULL; 478 int off = head->rdh_offset, i, lim; 479 u_char *dp = (u_char *)d_arg + off, *cp; 480 481 if (cur == NULL) { 482 cur = head->rdh_top; 483 while (cur) { 484 target = cur; 485 if (cur->rd_btest & *(dp + cur->rd_masklim)) 486 cur = cur->rd_r; 487 else 488 cur = cur->rd_l; 489 } 490 } else { 491 target = cur->rd_p; 492 if (target == NULL) { 493 *rdp = NULL; 494 return 0; 495 } 496 } 497 498 /* We are now on the leaf radish. Backtrace to find the radish 499 which contains route to match. */ 500 do { 501 /* If this radish doesn't have route, 502 we skip it and chase the next parent. */ 503 if (target->rd_rtent != NULL) { 504 cp = (u_char *)target->rd_route + off; 505 lim = target->rd_masklim; 506 507 /* Check the edge for slight speed up */ 508 if (target->rd_bmask) 509 if ((*(dp + lim) & target->rd_bmask) 510 != *(cp + lim)){ 511 nextparent: 512 continue; 513 } 514 515 /* mask is always 0xff */ 516 for (i = 0; i < lim; i++) 517 if(dp[i] != cp[i]) 518 /* to break the for loop */ 519 goto nextparent; 520 /* Matched to this radish! */ 521 *rdp = target; 522 return 1; 523 } 524 } while ((target = target->rd_p)); 525 *rdp = NULL; 526 return 0; 527 } 528 529 /* 530 * Lookup the same radish according to a pair of destination and mask. 531 * Return a pointer to rtentry if exists. Otherwise, return NULL. 532 */ 533 534 #ifndef GENERIC_USE 535 struct rtentry * 536 #else /* GENERIC_USE */ 537 void * 538 #endif /* GENERIC_USE */ 539 rd_lookup(d_arg, m_arg, head) 540 struct sockaddr *d_arg, *m_arg; 541 struct radish_head *head; 542 { 543 struct radish *cur = head->rdh_top; 544 int off = head->rdh_offset, i, lim, olim = 0, masklen; 545 u_char *dp = (u_char *)d_arg + off, *cp; 546 547 rd_mask(m_arg, head, &masklen); 548 549 /* Skipping forward search */ 550 while (cur) { 551 /* Skip a radish if it doesn't have a route */ 552 if (cur->rd_rtent != NULL) { 553 cp = (u_char *)(cur->rd_route) + off; 554 lim = cur->rd_masklim; 555 /* check the edge to speed up a bit */ 556 if (cur->rd_bmask) 557 if ((*(dp + lim) & cur->rd_bmask) 558 != *(cp + lim)) 559 return NULL; 560 /* mask is always 0xff */ 561 for (i = olim; i < lim; i++) 562 if(dp[i] != cp[i]) 563 return NULL; 564 if (masklen == cur->rd_masklen) 565 return cur->rd_rtent; 566 olim = lim; 567 } 568 if (cur->rd_btest & *(dp + cur->rd_masklim)) 569 cur = cur->rd_r; 570 else 571 cur = cur->rd_l; 572 } 573 return NULL; 574 } 575 576 /* 577 * Delete the radish for dest and mask. 578 * Return 0 if success. 579 * Return ENOENT if no such radish exists. 580 * Return EFAULT if try to delete intermediate radish which doesn't have route. 581 */ 582 583 int 584 #ifndef GENERIC_USE 585 rd_delete(d_arg, m_arg, head, rt) 586 #else /* GENERIC_USE */ 587 rd_delete(d_arg, m_arg, head, item) 588 #endif /* GENERIC_USE */ 589 struct sockaddr *d_arg; 590 struct sockaddr *m_arg; 591 struct radish_head *head; 592 #ifndef GENERIC_USE 593 struct rtentry **rt; 594 #else /* GENERIC_USE */ 595 void **item; 596 #endif /* GENERIC_USE */ 597 { 598 struct radish *cur = head->rdh_top; 599 int off = head->rdh_offset, i, lim, masklen; 600 u_char *dp = (u_char *)d_arg + off, *cp; 601 602 rd_mask(m_arg, head, &masklen); 603 #ifndef GENERIC_USE 604 *rt = NULL; /* just in case */ 605 #else /* GENERIC_USE */ 606 *item = NULL; /* just in case */ 607 #endif /* GENERIC_USE */ 608 609 while (cur) { 610 /* exit loop if dest does not match with the current node 611 * (dest & mask) != route 612 */ 613 cp = (u_char *)cur->rd_route + off; 614 /* check the edge to speed up */ 615 if (cur->rd_bmask) 616 if ((*(dp + cur->rd_masklim) & cur->rd_bmask) 617 != *(cp + cur->rd_masklim)) 618 return ENOENT; 619 /* mask is always 0xff */ 620 lim = cur->rd_masklim; 621 for (i = 0; i < lim; i++) 622 if(dp[i] != cp[i]) 623 return ENOENT; 624 625 /* See if cur is exactly what we delete */ 626 627 /* Check mask to speed up */ 628 if (cur->rd_masklen != masklen) 629 goto next; 630 631 cp = (u_char *)cur->rd_route + off; 632 lim = head->rdh_alen; 633 for (i = 0; i < lim; i++) 634 if (dp[i] != cp[i]) 635 goto next; 636 /* 637 * Both route and mask are the same. 638 */ 639 if (cur->rd_rtent == NULL) { 640 /* Leaf always has route, so this radish 641 * must be intermediate. 642 * Can't delete intermediate radish which 643 * doesn't have route. 644 */ 645 return EFAULT; 646 } 647 #ifndef GENERIC_USE 648 *rt = cur->rd_rtent; 649 #else /* GENERIC_USE */ 650 *item = cur->rd_rtent; 651 #endif /* GENERIC_USE */ 652 { 653 #ifndef SA_LEN 654 /* used to report the deleted entry back */ 655 u_char rl = cur->rd_route->sa_len; 656 u_char ml = cur->rd_mask->sa_len; 657 #else 658 u_char rl = SA_LEN(cur->rd_route); 659 u_char ml = SA_LEN(cur->rd_mask); 660 #endif 661 662 bcopy(cur->rd_route, rd_deleted_km, rl); 663 bcopy(cur->rd_mask, rd_deleted_km + rl, ml); 664 } 665 if (cur->rd_l && cur->rd_r) { 666 /* This radish has two children */ 667 cur->rd_rtent = NULL; 668 return 0; 669 } 670 /* Unlink the radish that has 0 or 1 child 671 * and surely has a route. 672 */ 673 rd_unlink(cur, head->rdh_top); 674 return 0; 675 676 next: 677 /* seach corresponding subtree */ 678 if (cur->rd_btest & *(dp + cur->rd_masklim)) { 679 if (cur->rd_r) { 680 cur = cur->rd_r; 681 continue; 682 } else 683 break; 684 } else { 685 if (cur->rd_l) { 686 cur = cur->rd_l; 687 continue; 688 } else 689 break; 690 } 691 } 692 return ENOENT; 693 } 694 695 /* 696 * Free radish and refine radish tree. 697 * rd_unlink is called with radish which have 0 or 1 child and route. 698 * Error causes panic, so return only when success. 699 */ 700 701 void 702 rd_unlink(cur, top) 703 struct radish *cur, *top; 704 { 705 struct radish *parent, *child; 706 707 if (cur == top) { 708 cur->rd_rtent = NULL; 709 return; 710 } 711 712 if ((cur->rd_l == 0) && (cur->rd_r == 0)) { 713 /* No child, just delete it. */ 714 parent = cur->rd_p; 715 if (parent->rd_l == cur) { 716 parent->rd_l = NULL; 717 Free(cur); 718 } else if (parent->rd_r == cur) { 719 parent->rd_r = NULL; 720 Free(cur); 721 } else 722 #ifndef GENERIC_USE 723 FATAL("rd_unlink"); 724 #else 725 return; 726 #endif 727 if (parent->rd_rtent == NULL && parent != top) 728 /* Parent is not necessary, refine radish. */ 729 rd_unlink(parent, top); 730 } else { 731 /* 732 * There is one child, never two. 733 * Make its child its parent's child. 734 */ 735 if (cur->rd_l) 736 child = cur->rd_l; 737 else 738 child = cur->rd_r; 739 parent = cur->rd_p; 740 child->rd_p = parent; 741 if (parent->rd_l == cur) { 742 parent->rd_l = child; 743 Free(cur); 744 } else if (parent->rd_r == cur) { 745 parent->rd_r = child; 746 Free(cur); 747 } else 748 #ifndef GENERIC_USE 749 FATAL("rd_unlink"); 750 #else 751 return; 752 #endif 753 } 754 } 755 756 int 757 rd_walktree(h, f, w) 758 struct radish_head *h; 759 register int (*f)(struct radish *, void *); 760 void *w; 761 { 762 int error = 0; 763 struct radish *par = NULL, *cur, *top = h->rdh_top; 764 765 cur = top; 766 for (;;) { 767 while (cur) { 768 if (cur->rd_rtent != NULL) 769 if ((error = (*f)(cur, w))) 770 return error; 771 par = cur; 772 cur = cur->rd_l; 773 } 774 cur = par; 775 while (cur->rd_r == NULL || par == cur->rd_r) { 776 par = cur; 777 cur = cur->rd_p; 778 if (cur == NULL) return 0; 779 } 780 par = cur; 781 cur = cur->rd_r; 782 } 783 } 784 785 /* This function can be mush easier in the context of radish. 786 * For instance, using rd_mask. But we stay the original because 787 * it works. 788 */ 789 int 790 rd_refines(m_arg, n_arg) 791 void *m_arg, *n_arg; 792 { 793 register caddr_t m = m_arg, n = n_arg; 794 register caddr_t lim, lim2 = lim = n + *(u_char *)n; 795 int longer = (*(u_char *)n++) - (int)(*(u_char *)m++); 796 int masks_are_equal = 1; 797 798 if (longer > 0) 799 lim -= longer; 800 while (n < lim) { 801 if (*n & ~(*m)) 802 return 0; 803 if (*n++ != *m++) 804 masks_are_equal = 0; 805 806 } 807 while (n < lim2) 808 if (*n++) 809 return 0; 810 if (masks_are_equal && (longer < 0)) 811 for (lim2 = m - longer; m < lim2; ) 812 if (*m++) 813 return 1; 814 return (!masks_are_equal); 815 } 816 #endif /* RADISH */ 817