src/patricia.c

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