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