librb/src/patricia.c

   1 /*
   2  * Yanked out of Net::Patricia by Aaron Sethman <androsyn@ratbox.org>
   3  *
   4  * This was then yanked out of the ratbox/devel/src tree and stuffed into
   5  * librb and had function names changed, but otherwise not really altered.
   6  *
   7  * Dave Plonka <plonka@doit.wisc.edu>
   8  *
   9  * This product includes software developed by the University of Michigan,
  10  * Merit Network, Inc., and their contributors.
  11  *
  12  * This file had been called "radix.c" in the MRT sources.
  13  *
  14  * I renamed it to "patricia.c" since it's not an implementation of a general
  15  * radix trie.  Also I pulled in various requirements from "prefix.c" and
  16  * "demo.c" so that it could be used as a standalone API.
  17  *
  18  * This product includes software developed by the University of Michigan, Merit
  19  * Network, Inc., and their contributors.
  20  *
  21  */
  22 #include <librb_config.h>
  23 #include <rb_lib.h>
  24
  25 /* Enable both of these to debug patricia.c
  26  * #define NOTYET 1
  27  * #define PATRICIA_DEBUG 1
  28  */
  29
  30 void
  31 rb_init_patricia(void)
  32 {
  33         return;
  34 }
  35
  36 /* prefix_tochar
  37  * convert prefix information to bytes
  38  */
  39 static uint8_t *
  40 prefix_tochar(rb_prefix_t *prefix)
  41 {
  42         if(prefix == NULL)
  43                 return (NULL);
  44
  45         return ((uint8_t *)&prefix->add.sin);
  46 }
  47
  48 static int
  49 comp_with_mask(void *addr, void *dest, unsigned int mask)
  50 {
  51
  52         if( /* mask/8 == 0 || */ memcmp(addr, dest, mask / 8) == 0)
  53         {
  54                 int n = mask / 8;
  55                 int m = ((-1) << (8 - (mask % 8)));
  56
  57                 if(mask % 8 == 0 || (((uint8_t *)addr)[n] & m) == (((uint8_t *)dest)[n] & m))
  58                         return (1);
  59         }
  60         return (0);
  61 }
  62
  63 #ifdef NOTYET
  64 static char *
  65 prefix_toa2x(rb_prefix_t *prefix, char *buf, int buf_len, int with_len)
  66 {
  67         static char tmp[6];
  68         if(prefix == NULL)
  69         {
  70                 rb_strlcpy(buf, "(NULL)", buf_len);
  71                 return (buf);
  72         }
  73         inet_ntop(prefix->family, &prefix->add.sin, buf, buf_len);
  74         if(with_len)
  75         {
  76                 snprintf(tmp, sizeof(tmp), "/%d", prefix->bitlen);
  77                 strcat(buf, tmp);
  78         }
  79         return (buf);
  80 }
  81
  82 /* prefix_toa2
  83  * convert prefix information to ascii string
  84  */
  85
  86 static char *
  87 prefix_toa2(rb_prefix_t *prefix, char *buff, int buf_len)
  88 {
  89         return (prefix_toa2x(prefix, buff, buf_len, 0));
  90 }
  91
  92 static char *
  93 prefix_toa(rb_prefix_t *prefix)
  94 {
  95 #ifdef RB_IPV6
  96         static char buf[INET6_ADDRSTRLEN + 6];
  97 #else
  98         static char buf[16 + 6];
  99 #endif
 100         return (prefix_toa2(prefix, buf, sizeof(buf)));
 101 }
 102 #endif
 103 static rb_prefix_t *
 104 New_Prefix2(int family, void *dest, int bitlen, rb_prefix_t *prefix)
 105 {
 106         int dynamic_allocated = 0;
 107 #ifdef RB_IPV6
 108         int default_bitlen = 128;
 109 #else
 110         int default_bitlen = 32;
 111 #endif
 112
 113 #ifdef RB_IPV6
 114         if(family == AF_INET6)
 115         {
 116                 default_bitlen = 128;
 117                 if(prefix == NULL)
 118                 {
 119                         prefix = rb_malloc(sizeof(rb_prefix_t));
 120                         dynamic_allocated++;
 121                 }
 122                 memcpy(&prefix->add.sin6, dest, 16);
 123         }
 124         else
 125 #endif /* RB_IPV6 */
 126         if(family == AF_INET)
 127         {
 128                 if(prefix == NULL)
 129                 {
 130                         prefix = rb_malloc(sizeof(rb_prefix_t));
 131                         dynamic_allocated++;
 132                 }
 133                 memcpy(&prefix->add.sin, dest, 4);
 134         }
 135         else
 136         {
 137                 return (NULL);
 138         }
 139
 140         prefix->bitlen = (bitlen >= 0) ? bitlen : default_bitlen;
 141         prefix->family = family;
 142         prefix->ref_count = 0;
 143         if(dynamic_allocated)
 144         {
 145                 prefix->ref_count++;
 146         }
 147         return (prefix);
 148 }
 149
 150 static rb_prefix_t *
 151 New_Prefix(int family, void *dest, int bitlen)
 152 {
 153         return (New_Prefix2(family, dest, bitlen, NULL));
 154 }
 155
 156 /* ascii2prefix
 157  */
 158 static rb_prefix_t *
 159 ascii2prefix(int family, const char *string)
 160 {
 161         long bitlen, maxbitlen = 0;
 162         char *cp;
 163         struct in_addr sinaddr;
 164 #ifdef RB_IPV6
 165         struct in6_addr sinaddr6;
 166 #endif /* RB_IPV6 */
 167         int result;
 168         char save[MAXLINE];
 169
 170         if(string == NULL)
 171                 return (NULL);
 172
 173         /* easy way to handle both families */
 174         if(family == 0)
 175         {
 176                 family = AF_INET;
 177 #ifdef RB_IPV6
 178                 if(strchr(string, ':'))
 179                         family = AF_INET6;
 180 #endif /* RB_IPV6 */
 181         }
 182         if(family == AF_INET)
 183         {
 184                 maxbitlen = 32;
 185         }
 186 #ifdef RB_IPV6
 187         else if(family == AF_INET6)
 188         {
 189                 maxbitlen = 128;
 190         }
 191 #endif /* RB_IPV6 */
 192
 193         if((cp = strchr(string, '/')) != NULL)
 194         {
 195                 bitlen = atol(cp + 1);
 196                 /* *cp = '\0'; */
 197                 /* copy the string to save. Avoid destroying the string */
 198                 assert(cp - string < MAXLINE);
 199                 memcpy(save, string, cp - string);
 200                 save[cp - string] = '\0';
 201                 string = save;
 202                 if(bitlen <= 0 || bitlen > maxbitlen)
 203                         bitlen = maxbitlen;
 204         }
 205         else
 206         {
 207                 bitlen = maxbitlen;
 208         }
 209
 210         if(family == AF_INET)
 211         {
 212                 if((result = rb_inet_pton(AF_INET, string, &sinaddr)) <= 0)
 213                         return (NULL);
 214                 return (New_Prefix(AF_INET, &sinaddr, bitlen));
 215         }
 216 #ifdef RB_IPV6
 217         else if(family == AF_INET6)
 218         {
 219                 if((result = rb_inet_pton(AF_INET6, string, &sinaddr6)) <= 0)
 220                         return (NULL);
 221                 return (New_Prefix(AF_INET6, &sinaddr6, bitlen));
 222         }
 223 #endif /* RB_IPV6 */
 224         else
 225                 return (NULL);
 226 }
 227
 228 static rb_prefix_t *
 229 Ref_Prefix(rb_prefix_t *prefix)
 230 {
 231         if(prefix == NULL)
 232                 return (NULL);
 233         if(prefix->ref_count == 0)
 234         {
 235                 /* make a copy in case of a static prefix */
 236                 return (New_Prefix2(prefix->family, &prefix->add, prefix->bitlen, NULL));
 237         }
 238         prefix->ref_count++;
 239         return (prefix);
 240 }
 241
 242 static void
 243 Deref_Prefix(rb_prefix_t *prefix)
 244 {
 245         if(prefix == NULL)
 246                 return;
 247         /* for secure programming, raise an assert. no static prefix can call this */
 248         assert(prefix->ref_count > 0);
 249
 250         prefix->ref_count--;
 251         assert(prefix->ref_count >= 0);
 252         if(prefix->ref_count <= 0)
 253         {
 254                 rb_free(prefix);
 255                 return;
 256         }
 257 }
 258
 259 /* } */
 260
 261 // #define PATRICIA_DEBUG 1
 262
 263 static int num_active_patricia = 0;
 264
 265 /* these routines support continuous mask only */
 266
 267 rb_patricia_tree_t *
 268 rb_new_patricia(int maxbits)
 269 {
 270         rb_patricia_tree_t *patricia = rb_malloc(sizeof(rb_patricia_tree_t));
 271
 272         patricia->maxbits = maxbits;
 273         patricia->head = NULL;
 274         patricia->num_active_node = 0;
 275         assert(maxbits <= RB_PATRICIA_MAXBITS); /* XXX */
 276         num_active_patricia++;
 277         return (patricia);
 278 }
 279
 280
 281 /*
 282  * if func is supplied, it will be called as func(node->data)
 283  * before deleting the node
 284  */
 285
 286 void
 287 rb_clear_patricia(rb_patricia_tree_t *patricia, void (*func) (void *))
 288 {
 289         assert(patricia);
 290         if(patricia->head)
 291         {
 292
 293                 rb_patricia_node_t *Xstack[RB_PATRICIA_MAXBITS + 1];
 294                 rb_patricia_node_t **Xsp = Xstack;
 295                 rb_patricia_node_t *Xrn = patricia->head;
 296
 297                 while(Xrn)
 298                 {
 299                         rb_patricia_node_t *l = Xrn->l;
 300                         rb_patricia_node_t *r = Xrn->r;
 301
 302                         if(Xrn->prefix)
 303                         {
 304                                 Deref_Prefix(Xrn->prefix);
 305                                 if(Xrn->data && func)
 306                                         func(Xrn->data);
 307                         }
 308                         else
 309                         {
 310                                 assert(Xrn->data == NULL);
 311                         }
 312                         rb_free(Xrn);
 313                         patricia->num_active_node--;
 314
 315                         if(l)
 316                         {
 317                                 if(r)
 318                                 {
 319                                         *Xsp++ = r;
 320                                 }
 321                                 Xrn = l;
 322                         }
 323                         else if(r)
 324                         {
 325                                 Xrn = r;
 326                         }
 327                         else if(Xsp != Xstack)
 328                         {
 329                                 Xrn = *(--Xsp);
 330                         }
 331                         else
 332                         {
 333                                 Xrn = (rb_patricia_node_t *)0;
 334                         }
 335                 }
 336         }
 337         assert(patricia->num_active_node == 0);
 338         rb_free(patricia);
 339 }
 340
 341
 342 void
 343 rb_destroy_patricia(rb_patricia_tree_t *patricia, void (*func) (void *))
 344 {
 345         rb_clear_patricia(patricia, func);
 346         num_active_patricia--;
 347 }
 348
 349
 350 /*
 351  * if func is supplied, it will be called as func(node->prefix, node->data)
 352  */
 353
 354 void
 355 rb_patricia_process(rb_patricia_tree_t *patricia, void (*func) (rb_prefix_t *, void *))
 356 {
 357         rb_patricia_node_t *node;
 358         assert(func);
 359
 360         RB_PATRICIA_WALK(patricia->head, node)
 361         {
 362                 func(node->prefix, node->data);
 363         }
 364         RB_PATRICIA_WALK_END;
 365 }
 366
 367 rb_patricia_node_t *
 368 rb_patricia_search_exact(rb_patricia_tree_t *patricia, rb_prefix_t *prefix)
 369 {
 370         rb_patricia_node_t *node;
 371         uint8_t *addr;
 372         unsigned int bitlen;
 373
 374         assert(patricia);
 375         assert(prefix);
 376         assert(prefix->bitlen <= patricia->maxbits);
 377
 378         if(patricia->head == NULL)
 379                 return (NULL);
 380
 381         node = patricia->head;
 382         addr = rb_prefix_touchar(prefix);
 383         bitlen = prefix->bitlen;
 384
 385         while(node->bit < bitlen)
 386         {
 387
 388                 if(BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
 389                 {
 390 #ifdef PATRICIA_DEBUG
 391                         if(node->prefix)
 392                                 fprintf(stderr,
 393                                         "patricia_search_exact: take right %s/%d\n",
 394                                         prefix_toa(node->prefix), node->prefix->bitlen);
 395                         else
 396                                 fprintf(stderr,
 397                                         "patricia_search_exact: take right at %u\n", node->bit);
 398 #endif /* PATRICIA_DEBUG */
 399                         node = node->r;
 400                 }
 401                 else
 402                 {
 403 #ifdef PATRICIA_DEBUG
 404                         if(node->prefix)
 405                                 fprintf(stderr,
 406                                         "patricia_search_exact: take left %s/%d\n",
 407                                         prefix_toa(node->prefix), node->prefix->bitlen);
 408                         else
 409                                 fprintf(stderr,
 410                                         "patricia_search_exact: take left at %u\n", node->bit);
 411 #endif /* PATRICIA_DEBUG */
 412                         node = node->l;
 413                 }
 414
 415                 if(node == NULL)
 416                         return (NULL);
 417         }
 418
 419 #ifdef PATRICIA_DEBUG
 420         if(node->prefix)
 421                 fprintf(stderr, "patricia_search_exact: stop at %s/%d %u\n",
 422                         prefix_toa(node->prefix), node->prefix->bitlen, node->bit);
 423         else
 424                 fprintf(stderr, "patricia_search_exact: stop at %u\n", node->bit);
 425 #endif /* PATRICIA_DEBUG */
 426         if(node->bit > bitlen || node->prefix == NULL)
 427                 return (NULL);
 428         assert(node->bit == bitlen);
 429         assert(node->bit == node->prefix->bitlen);
 430         if(comp_with_mask(prefix_tochar(node->prefix), prefix_tochar(prefix), bitlen))
 431         {
 432 #ifdef PATRICIA_DEBUG
 433                 fprintf(stderr, "patricia_search_exact: found %s/%d\n",
 434                         prefix_toa(node->prefix), node->prefix->bitlen);
 435 #endif /* PATRICIA_DEBUG */
 436                 return (node);
 437         }
 438         return (NULL);
 439 }
 440
 441 /* if inclusive != 0, "best" may be the given prefix itself */
 442 rb_patricia_node_t *
 443 rb_patricia_search_best2(rb_patricia_tree_t *patricia, rb_prefix_t *prefix, int inclusive)
 444 {
 445         rb_patricia_node_t *node;
 446         rb_patricia_node_t *stack[RB_PATRICIA_MAXBITS + 1];
 447         uint8_t *addr;
 448         unsigned int bitlen;
 449         int cnt = 0;
 450
 451         assert(patricia);
 452         assert(prefix);
 453         assert(prefix->bitlen <= patricia->maxbits);
 454
 455         if(patricia->head == NULL)
 456                 return (NULL);
 457
 458         node = patricia->head;
 459         addr = rb_prefix_touchar(prefix);
 460         bitlen = prefix->bitlen;
 461
 462         while(node->bit < bitlen)
 463         {
 464
 465                 if(node->prefix)
 466                 {
 467 #ifdef PATRICIA_DEBUG
 468                         fprintf(stderr,
 469                                 "patricia_search_best: push %s/%d\n",
 470                                 prefix_toa(node->prefix), node->prefix->bitlen);
 471 #endif /* PATRICIA_DEBUG */
 472                         stack[cnt++] = node;
 473                 }
 474
 475                 if(BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
 476                 {
 477 #ifdef PATRICIA_DEBUG
 478                         if(node->prefix)
 479                                 fprintf(stderr,
 480                                         "patricia_search_best: take right %s/%d\n",
 481                                         prefix_toa(node->prefix), node->prefix->bitlen);
 482                         else
 483                                 fprintf(stderr,
 484                                         "patricia_search_best: take right at %u\n", node->bit);
 485 #endif /* PATRICIA_DEBUG */
 486                         node = node->r;
 487                 }
 488                 else
 489                 {
 490 #ifdef PATRICIA_DEBUG
 491                         if(node->prefix)
 492                                 fprintf(stderr,
 493                                         "patricia_search_best: take left %s/%d\n",
 494                                         prefix_toa(node->prefix), node->prefix->bitlen);
 495                         else
 496                                 fprintf(stderr,
 497                                         "patricia_search_best: take left at %u\n", node->bit);
 498 #endif /* PATRICIA_DEBUG */
 499                         node = node->l;
 500                 }
 501
 502                 if(node == NULL)
 503                         break;
 504         }
 505
 506         if(inclusive && node && node->prefix)
 507                 stack[cnt++] = node;
 508
 509 #ifdef PATRICIA_DEBUG
 510         if(node == NULL)
 511                 fprintf(stderr, "patricia_search_best: stop at null\n");
 512         else if(node->prefix)
 513                 fprintf(stderr, "patricia_search_best: stop at %s/%d\n",
 514                         prefix_toa(node->prefix), node->prefix->bitlen);
 515         else
 516                 fprintf(stderr, "patricia_search_best: stop at %u\n", node->bit);
 517 #endif /* PATRICIA_DEBUG */
 518
 519         if(cnt <= 0)
 520                 return (NULL);
 521
 522         while(--cnt >= 0)
 523         {
 524                 node = stack[cnt];
 525 #ifdef PATRICIA_DEBUG
 526                 fprintf(stderr, "patricia_search_best: pop %s/%d\n",
 527                         prefix_toa(node->prefix), node->prefix->bitlen);
 528 #endif /* PATRICIA_DEBUG */
 529                 if(comp_with_mask(prefix_tochar(node->prefix),
 530                                   prefix_tochar(prefix), node->prefix->bitlen))
 531                 {
 532 #ifdef PATRICIA_DEBUG
 533                         fprintf(stderr,
 534                                 "patricia_search_best: found %s/%d\n",
 535                                 prefix_toa(node->prefix), node->prefix->bitlen);
 536 #endif /* PATRICIA_DEBUG */
 537                         return (node);
 538                 }
 539         }
 540         return (NULL);
 541 }
 542
 543
 544 rb_patricia_node_t *
 545 rb_patricia_search_best(rb_patricia_tree_t *patricia, rb_prefix_t *prefix)
 546 {
 547         return (rb_patricia_search_best2(patricia, prefix, 1));
 548 }
 549
 550
 551 rb_patricia_node_t *
 552 rb_patricia_lookup(rb_patricia_tree_t *patricia, rb_prefix_t *prefix)
 553 {
 554         rb_patricia_node_t *node, *new_node, *parent, *glue;
 555         uint8_t *addr, *test_addr;
 556         unsigned int bitlen, check_bit, differ_bit;
 557         unsigned int i, j, r;
 558
 559         assert(patricia);
 560         assert(prefix);
 561         assert(prefix->bitlen <= patricia->maxbits);
 562
 563         if(patricia->head == NULL)
 564         {
 565                 node = rb_malloc(sizeof(rb_patricia_node_t));
 566                 node->bit = prefix->bitlen;
 567                 node->prefix = Ref_Prefix(prefix);
 568                 node->parent = NULL;
 569                 node->l = node->r = NULL;
 570                 node->data = NULL;
 571                 patricia->head = node;
 572 #ifdef PATRICIA_DEBUG
 573                 fprintf(stderr,
 574                         "patricia_lookup: new_node #0 %s/%d (head)\n",
 575                         prefix_toa(prefix), prefix->bitlen);
 576 #endif /* PATRICIA_DEBUG */
 577                 patricia->num_active_node++;
 578                 return (node);
 579         }
 580
 581         addr = rb_prefix_touchar(prefix);
 582         bitlen = prefix->bitlen;
 583         node = patricia->head;
 584
 585         while(node->bit < bitlen || node->prefix == NULL)
 586         {
 587
 588                 if(node->bit < patricia->maxbits &&
 589                    BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
 590                 {
 591                         if(node->r == NULL)
 592                                 break;
 593 #ifdef PATRICIA_DEBUG
 594                         if(node->prefix)
 595                                 fprintf(stderr,
 596                                         "patricia_lookup: take right %s/%d\n",
 597                                         prefix_toa(node->prefix), node->prefix->bitlen);
 598                         else
 599                                 fprintf(stderr, "patricia_lookup: take right at %u\n", node->bit);
 600 #endif /* PATRICIA_DEBUG */
 601                         node = node->r;
 602                 }
 603                 else
 604                 {
 605                         if(node->l == NULL)
 606                                 break;
 607 #ifdef PATRICIA_DEBUG
 608                         if(node->prefix)
 609                                 fprintf(stderr,
 610                                         "patricia_lookup: take left %s/%d\n",
 611                                         prefix_toa(node->prefix), node->prefix->bitlen);
 612                         else
 613                                 fprintf(stderr, "patricia_lookup: take left at %u\n", node->bit);
 614 #endif /* PATRICIA_DEBUG */
 615                         node = node->l;
 616                 }
 617
 618                 assert(node);
 619         }
 620
 621         assert(node->prefix);
 622 #ifdef PATRICIA_DEBUG
 623         fprintf(stderr, "patricia_lookup: stop at %s/%d\n",
 624                 prefix_toa(node->prefix), node->prefix->bitlen);
 625 #endif /* PATRICIA_DEBUG */
 626
 627         test_addr = rb_prefix_touchar(node->prefix);
 628         /* find the first bit different */
 629         check_bit = (node->bit < bitlen) ? node->bit : bitlen;
 630         differ_bit = 0;
 631         for(i = 0; i * 8 < check_bit; i++)
 632         {
 633                 if((r = (addr[i] ^ test_addr[i])) == 0)
 634                 {
 635                         differ_bit = (i + 1) * 8;
 636                         continue;
 637                 }
 638                 /* I know the better way, but for now */
 639                 for(j = 0; j < 8; j++)
 640                 {
 641                         if(BIT_TEST(r, (0x80 >> j)))
 642                                 break;
 643                 }
 644                 /* must be found */
 645                 assert(j < 8);
 646                 differ_bit = i * 8 + j;
 647                 break;
 648         }
 649         if(differ_bit > check_bit)
 650                 differ_bit = check_bit;
 651 #ifdef PATRICIA_DEBUG
 652         fprintf(stderr, "patricia_lookup: differ_bit %u\n", differ_bit);
 653 #endif /* PATRICIA_DEBUG */
 654
 655         parent = node->parent;
 656         while(parent && parent->bit >= differ_bit)
 657         {
 658                 node = parent;
 659                 parent = node->parent;
 660 #ifdef PATRICIA_DEBUG
 661                 if(node->prefix)
 662                         fprintf(stderr, "patricia_lookup: up to %s/%d\n",
 663                                 prefix_toa(node->prefix), node->prefix->bitlen);
 664                 else
 665                         fprintf(stderr, "patricia_lookup: up to %u\n", node->bit);
 666 #endif /* PATRICIA_DEBUG */
 667         }
 668
 669         if(differ_bit == bitlen && node->bit == bitlen)
 670         {
 671                 if(node->prefix)
 672                 {
 673 #ifdef PATRICIA_DEBUG
 674                         fprintf(stderr, "patricia_lookup: found %s/%d\n",
 675                                 prefix_toa(node->prefix), node->prefix->bitlen);
 676 #endif /* PATRICIA_DEBUG */
 677                         return (node);
 678                 }
 679                 node->prefix = Ref_Prefix(prefix);
 680 #ifdef PATRICIA_DEBUG
 681                 fprintf(stderr,
 682                         "patricia_lookup: new node #1 %s/%d (glue mod)\n",
 683                         prefix_toa(prefix), prefix->bitlen);
 684 #endif /* PATRICIA_DEBUG */
 685                 assert(node->data == NULL);
 686                 return (node);
 687         }
 688
 689         new_node = rb_malloc(sizeof(rb_patricia_node_t));
 690         new_node->bit = prefix->bitlen;
 691         new_node->prefix = Ref_Prefix(prefix);
 692         new_node->parent = NULL;
 693         new_node->l = new_node->r = NULL;
 694         new_node->data = NULL;
 695         patricia->num_active_node++;
 696
 697         if(node->bit == differ_bit)
 698         {
 699                 new_node->parent = node;
 700                 if(node->bit < patricia->maxbits &&
 701                    BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
 702                 {
 703                         assert(node->r == NULL);
 704                         node->r = new_node;
 705                 }
 706                 else
 707                 {
 708                         assert(node->l == NULL);
 709                         node->l = new_node;
 710                 }
 711 #ifdef PATRICIA_DEBUG
 712                 fprintf(stderr,
 713                         "patricia_lookup: new_node #2 %s/%d (child)\n",
 714                         prefix_toa(prefix), prefix->bitlen);
 715 #endif /* PATRICIA_DEBUG */
 716                 return (new_node);
 717         }
 718
 719         if(bitlen == differ_bit)
 720         {
 721                 if(bitlen < patricia->maxbits &&
 722                    BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07)))
 723                 {
 724                         new_node->r = node;
 725                 }
 726                 else
 727                 {
 728                         new_node->l = node;
 729                 }
 730                 new_node->parent = node->parent;
 731                 if(node->parent == NULL)
 732                 {
 733                         assert(patricia->head == node);
 734                         patricia->head = new_node;
 735                 }
 736                 else if(node->parent->r == node)
 737                 {
 738                         node->parent->r = new_node;
 739                 }
 740                 else
 741                 {
 742                         node->parent->l = new_node;
 743                 }
 744                 node->parent = new_node;
 745 #ifdef PATRICIA_DEBUG
 746                 fprintf(stderr,
 747                         "patricia_lookup: new_node #3 %s/%d (parent)\n",
 748                         prefix_toa(prefix), prefix->bitlen);
 749 #endif /* PATRICIA_DEBUG */
 750         }
 751         else
 752         {
 753                 glue = rb_malloc(sizeof(rb_patricia_node_t));
 754                 glue->bit = differ_bit;
 755                 glue->prefix = NULL;
 756                 glue->parent = node->parent;
 757                 glue->data = NULL;
 758                 patricia->num_active_node++;
 759                 if(differ_bit < patricia->maxbits &&
 760                    BIT_TEST(addr[differ_bit >> 3], 0x80 >> (differ_bit & 0x07)))
 761                 {
 762                         glue->r = new_node;
 763                         glue->l = node;
 764                 }
 765                 else
 766                 {
 767                         glue->r = node;
 768                         glue->l = new_node;
 769                 }
 770                 new_node->parent = glue;
 771
 772                 if(node->parent == NULL)
 773                 {
 774                         assert(patricia->head == node);
 775                         patricia->head = glue;
 776                 }
 777                 else if(node->parent->r == node)
 778                 {
 779                         node->parent->r = glue;
 780                 }
 781                 else
 782                 {
 783                         node->parent->l = glue;
 784                 }
 785                 node->parent = glue;
 786 #ifdef PATRICIA_DEBUG
 787                 fprintf(stderr,
 788                         "patricia_lookup: new_node #4 %s/%d (glue+node)\n",
 789                         prefix_toa(prefix), prefix->bitlen);
 790 #endif /* PATRICIA_DEBUG */
 791         }
 792         return (new_node);
 793 }
 794
 795
 796 void
 797 rb_patricia_remove(rb_patricia_tree_t *patricia, rb_patricia_node_t *node)
 798 {
 799         rb_patricia_node_t *parent, *child;
 800
 801         assert(patricia);
 802         assert(node);
 803
 804         if(node->r && node->l)
 805         {
 806 #ifdef PATRICIA_DEBUG
 807                 fprintf(stderr, "patricia_remove: #0 %s/%d (r & l)\n",
 808                         prefix_toa(node->prefix), node->prefix->bitlen);
 809 #endif /* PATRICIA_DEBUG */
 810
 811                 /* this might be a placeholder node -- have to check and make sure
 812                  * there is a prefix aossciated with it ! */
 813                 if(node->prefix != NULL)
 814                         Deref_Prefix(node->prefix);
 815                 node->prefix = NULL;
 816                 /* Also I needed to clear data pointer -- masaki */
 817                 node->data = NULL;
 818                 return;
 819         }
 820
 821         if(node->r == NULL && node->l == NULL)
 822         {
 823 #ifdef PATRICIA_DEBUG
 824                 fprintf(stderr, "patricia_remove: #1 %s/%d (!r & !l)\n",
 825                         prefix_toa(node->prefix), node->prefix->bitlen);
 826 #endif /* PATRICIA_DEBUG */
 827                 parent = node->parent;
 828                 Deref_Prefix(node->prefix);
 829                 rb_free(node);
 830                 patricia->num_active_node--;
 831
 832                 if(parent == NULL)
 833                 {
 834                         assert(patricia->head == node);
 835                         patricia->head = NULL;
 836                         return;
 837                 }
 838
 839                 if(parent->r == node)
 840                 {
 841                         parent->r = NULL;
 842                         child = parent->l;
 843                 }
 844                 else
 845                 {
 846                         assert(parent->l == node);
 847                         parent->l = NULL;
 848                         child = parent->r;
 849                 }
 850
 851                 if(parent->prefix)
 852                         return;
 853
 854                 /* we need to remove parent too */
 855
 856                 if(parent->parent == NULL)
 857                 {
 858                         assert(patricia->head == parent);
 859                         patricia->head = child;
 860                 }
 861                 else if(parent->parent->r == parent)
 862                 {
 863                         parent->parent->r = child;
 864                 }
 865                 else
 866                 {
 867                         assert(parent->parent->l == parent);
 868                         parent->parent->l = child;
 869                 }
 870                 child->parent = parent->parent;
 871                 rb_free(parent);
 872                 patricia->num_active_node--;
 873                 return;
 874         }
 875 #ifdef PATRICIA_DEBUG
 876         fprintf(stderr, "patricia_remove: #2 %s/%d (r ^ l)\n",
 877                 prefix_toa(node->prefix), node->prefix->bitlen);
 878 #endif /* PATRICIA_DEBUG */
 879         if(node->r)
 880         {
 881                 child = node->r;
 882         }
 883         else
 884         {
 885                 assert(node->l);
 886                 child = node->l;
 887         }
 888         parent = node->parent;
 889         child->parent = parent;
 890
 891         Deref_Prefix(node->prefix);
 892         rb_free(node);
 893         patricia->num_active_node--;
 894
 895         if(parent == NULL)
 896         {
 897                 assert(patricia->head == node);
 898                 patricia->head = child;
 899                 return;
 900         }
 901
 902         if(parent->r == node)
 903         {
 904                 parent->r = child;
 905         }
 906         else
 907         {
 908                 assert(parent->l == node);
 909                 parent->l = child;
 910         }
 911 }
 912
 913 rb_patricia_node_t *
 914 make_and_lookup_ip(rb_patricia_tree_t *tree, struct sockaddr *in, int bitlen)
 915 {
 916         rb_prefix_t *prefix;
 917         rb_patricia_node_t *node;
 918         void *ipptr = NULL;
 919 #ifdef RB_IPV6
 920         if(in->sa_family == AF_INET6)
 921                 ipptr = &((struct sockaddr_in6 *)in)->sin6_addr;
 922         else
 923 #endif
 924                 ipptr = &((struct sockaddr_in *)in)->sin_addr;
 925
 926         prefix = New_Prefix(in->sa_family, ipptr, bitlen);
 927
 928         if(prefix == NULL)
 929                 return NULL;
 930
 931         node = rb_patricia_lookup(tree, prefix);
 932
 933
 934
 935         Deref_Prefix(prefix);
 936         return (node);
 937 }
 938
 939
 940 rb_patricia_node_t *
 941 make_and_lookup(rb_patricia_tree_t *tree, const char *string)
 942 {
 943         rb_prefix_t *prefix;
 944         rb_patricia_node_t *node;
 945
 946         if((prefix = ascii2prefix(AF_INET, string)) != NULL)
 947         {
 948                 node = rb_patricia_lookup(tree, prefix);
 949         }
 950         else
 951 #ifdef RB_IPV6
 952         if((prefix = ascii2prefix(AF_INET6, string)) != NULL)
 953         {
 954                 node = rb_patricia_lookup(tree, prefix);
 955         }
 956         else
 957 #endif
 958                 return NULL;
 959 #ifdef PATRICIA_DEBUG
 960         printf("make_and_lookup: %s/%d\n", prefix_toa(prefix), prefix->bitlen);
 961 #endif
 962         Deref_Prefix(prefix);
 963         return (node);
 964 }
 965
 966 #ifdef NOTYET
 967 static rb_patricia_node_t *
 968 try_search_exact(rb_patricia_tree_t *tree, char *string)
 969 {
 970         rb_prefix_t *prefix;
 971         rb_patricia_node_t *node;
 972         if((prefix = ascii2prefix(AF_INET, string)) != NULL)
 973         {
 974                 node = rb_patricia_search_exact(tree, prefix);
 975                 Deref_Prefix(prefix);
 976                 return (node);
 977         }
 978 #ifdef RB_IPV6
 979         else if((prefix = ascii2prefix(AF_INET6, string)) != NULL)
 980         {
 981                 node = rb_patricia_search_exact(tree, prefix);
 982                 Deref_Prefix(prefix);
 983                 return (node);
 984         }
 985 #endif
 986         else
 987                 return NULL;
 988 }
 989
 990 void
 991 lookup_then_remove(rb_patricia_tree_t *tree, char *string)
 992 {
 993         rb_patricia_node_t *node;
 994
 995         if((node = try_search_exact(tree, string)))
 996                 patricia_remove(tree, node);
 997 }
 998 #endif
 999
1000 rb_patricia_node_t *
1001 rb_match_ip(rb_patricia_tree_t *tree, struct sockaddr *ip)
1002 {
1003         rb_prefix_t *prefix;
1004         rb_patricia_node_t *node;
1005         void *ipptr;
1006         unsigned int len;
1007         int family;
1008 #ifndef RB_IPV6
1009         len = 32;
1010         family = AF_INET;
1011         ipptr = &((struct sockaddr_in *)ip)->sin_addr;
1012 #else
1013         if(ip->sa_family == AF_INET6)
1014         {
1015                 len = 128;
1016                 family = AF_INET6;
1017                 ipptr = &((struct sockaddr_in6 *)ip)->sin6_addr;
1018         }
1019         else
1020         {
1021                 len = 32;
1022                 family = AF_INET;
1023                 ipptr = &((struct sockaddr_in *)ip)->sin_addr;
1024         }
1025 #endif
1026
1027         if((prefix = New_Prefix(family, ipptr, len)) != NULL)
1028         {
1029                 node = rb_patricia_search_best(tree, prefix);
1030                 Deref_Prefix(prefix);
1031                 return (node);
1032         }
1033         return NULL;
1034 }
1035
1036 rb_patricia_node_t *
1037 rb_match_ip_exact(rb_patricia_tree_t *tree, struct sockaddr *ip, unsigned int len)
1038 {
1039         rb_prefix_t *prefix;
1040         rb_patricia_node_t *node;
1041         void *ipptr;
1042         int family;
1043 #ifndef RB_IPV6
1044         if(len > 128)
1045                 len = 128;
1046
1047         family = AF_INET;
1048         ipptr = &((struct sockaddr_in *)ip)->sin_addr;
1049 #else
1050         if(ip->sa_family == AF_INET6)
1051         {
1052                 if(len > 128)
1053                         len = 128;
1054                 family = AF_INET6;
1055                 ipptr = &((struct sockaddr_in6 *)ip)->sin6_addr;
1056         }
1057         else
1058         {
1059                 if(len > 32)
1060                         len = 32;
1061                 family = AF_INET;
1062                 ipptr = &((struct sockaddr_in *)ip)->sin_addr;
1063         }
1064 #endif
1065
1066         if((prefix = New_Prefix(family, ipptr, len)) != NULL)
1067         {
1068                 node = rb_patricia_search_exact(tree, prefix);
1069                 Deref_Prefix(prefix);
1070                 return (node);
1071         }
1072         return NULL;
1073 }
1074
1075
1076
1077 rb_patricia_node_t *
1078 rb_match_string(rb_patricia_tree_t *tree, const char *string)
1079 {
1080         rb_patricia_node_t *node;
1081         rb_prefix_t *prefix;
1082
1083         if((prefix = ascii2prefix(AF_INET, string)) != NULL)
1084         {
1085                 node = rb_patricia_search_best(tree, prefix);
1086                 Deref_Prefix(prefix);
1087         }
1088         else
1089 #ifdef RB_IPV6
1090         if((prefix = ascii2prefix(AF_INET6, string)) != NULL)
1091         {
1092                 node = rb_patricia_search_best(tree, prefix);
1093                 Deref_Prefix(prefix);
1094         }
1095         else
1096 #endif
1097                 return NULL;
1098         return node;
1099 }
1100
1101 rb_patricia_node_t *
1102 rb_match_exact_string(rb_patricia_tree_t *tree, const char *string)
1103 {
1104         rb_prefix_t *prefix;
1105         rb_patricia_node_t *node;
1106         if((prefix = ascii2prefix(AF_INET, string)) != NULL)
1107         {
1108                 node = rb_patricia_search_exact(tree, prefix);
1109                 Deref_Prefix(prefix);
1110         }
1111         else
1112 #ifdef RB_IPV6
1113         if((prefix = ascii2prefix(AF_INET6, string)) != NULL)
1114         {
1115                 node = rb_patricia_search_exact(tree, prefix);
1116                 Deref_Prefix(prefix);
1117         }
1118         else
1119 #endif
1120                 return NULL;
1121         return node;
1122 }