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