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