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