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