patricia/patricialib.c

   1 /*
   2  * $Id: patricia.c,v 1.7 2005/12/07 20:46:41 dplonka Exp $
   3  * Dave Plonka <plonka@doit.wisc.edu>
   4  *
   5  * This product includes software developed by the University of Michigan,
   6  * Merit Network, Inc., and their contributors.
   7  *
   8  * This file had been called "radix.c" in the MRT sources.
   9  *
  10  * I renamed it to "patricia.c" since it's not an implementation of a general
  11  * radix trie.  Also I pulled in various requirements from "prefix.c" and
  12  * "demo.c" so that it could be used as a standalone API.
  13  */
  14
  15 char patricia_copyright[] =
  16 "This product includes software developed by the University of Michigan, Merit"
  17 "Network, Inc., and their contributors.";
  18
  19 #include <assert.h> /* assert */
  20 #include <ctype.h> /* isdigit */
  21 #include <errno.h> /* errno */
  22 #include <math.h> /* sin */
  23 #include <stddef.h> /* NULL */
  24 #include <stdio.h> /* sprintf, fprintf, stderr */
  25 #include <stdlib.h> /* free, atol, calloc */
  26 #include <string.h> /* memcpy, strchr, strlen */
  27
  28 #include "patricia.h"
  29
  30 /* prefix_tochar
  31  * convert prefix information to bytes
  32  */
  33 u_char *
  34 prefix_tochar (prefix_t * prefix)
  35 {
  36     if (prefix == NULL)
  37         return (NULL);
  38
  39     return ((u_char *) & prefix->sin);
  40 }
  41
  42 int
  43 comp_with_mask (void *addr, void *dest, u_int mask)
  44 {
  45
  46     if ( /* mask/8 == 0 || */ memcmp (addr, dest, mask / 8) == 0) {
  47         int n = mask / 8;
  48         int m = ((-1) << (8 - (mask % 8)));
  49
  50         if (mask % 8 == 0 || (((u_char *)addr)[n] & m) == (((u_char *)dest)[n] & m))
  51             return (1);
  52     }
  53     return (0);
  54 }
  55
  56
  57 prefix_t *
  58 patricia_new_prefix (struct irc_in_addr *dest, int bitlen)
  59 {
  60     prefix_t *prefix = newprefix();
  61     assert (0 != prefix);
  62
  63     memcpy (&prefix->sin, dest, 16);
  64     prefix->bitlen = (bitlen >= 0)? bitlen: 128;
  65     prefix->ref_count = 1;
  66
  67     return prefix;
  68 }
  69
  70 prefix_t *
  71 patricia_ref_prefix (prefix_t * prefix)
  72 {
  73     if (prefix == NULL)
  74         return (NULL);
  75     if (prefix->ref_count == 0) {
  76         /* make a copy in case of a static prefix */
  77         return (patricia_new_prefix (&prefix->sin, prefix->bitlen));
  78     }
  79     prefix->ref_count++;
  80     return (prefix);
  81 }
  82
  83 void
  84 patricia_deref_prefix (prefix_t * prefix)
  85 {
  86     if (prefix == NULL)
  87         return;
  88     /* for secure programming, raise an assert. no static prefix can call this */
  89     assert (prefix->ref_count > 0);
  90
  91     prefix->ref_count--;
  92     if (prefix->ref_count <= 0) {
  93         freeprefix(prefix);
  94         return;
  95     }
  96 }
  97
  98 /* these routines support continuous mask only */
  99
 100 patricia_tree_t *
 101 patricia_new_tree (int maxbits)
 102 {
 103     patricia_tree_t *patricia = calloc(1, sizeof *patricia);
 104
 105     patricia->maxbits = maxbits;
 106     patricia->head = NULL;
 107     patricia->num_active_node = 0;
 108     assert (maxbits <= PATRICIA_MAXBITS); /* XXX */
 109     return (patricia);
 110 }
 111
 112
 113 void
 114 patricia_clear_tree (patricia_tree_t *patricia, void_fn_t func)
 115 {
 116     assert (patricia);
 117     if (patricia->head) {
 118
 119         patricia_node_t *Xstack[PATRICIA_MAXBITS+1];
 120         patricia_node_t **Xsp = Xstack;
 121         patricia_node_t *Xrn = patricia->head;
 122
 123         while (Xrn) {
 124             patricia_node_t *l = Xrn->l;
 125             patricia_node_t *r = Xrn->r;
 126
 127             if (Xrn->prefix) {
 128                 if (Xrn->exts && func)
 129                         func(Xrn->exts);
 130                 patricia_deref_prefix (Xrn->prefix);
 131             }
 132             freenode(Xrn);
 133             patricia->num_active_node--;
 134
 135             if (l) {
 136                 if (r) {
 137                     *Xsp++ = r;
 138                 }
 139                 Xrn = l;
 140             } else if (r) {
 141                 Xrn = r;
 142             } else if (Xsp != Xstack) {
 143                 Xrn = *(--Xsp);
 144             } else {
 145                 Xrn = (patricia_node_t *) 0;
 146             }
 147         }
 148     }
 149     assert (patricia->num_active_node == 0);
 150 }
 151
 152 void
 153 patricia_destroy_tree (patricia_tree_t *patricia, void_fn_t func)
 154 {
 155     patricia_clear_tree (patricia, func);
 156     free(patricia);
 157     /*TODO: EXTENSIONS!*/
 158 }
 159
 160
 161 /*
 162  * if func is supplied, it will be called as func(node->prefix)
 163  */
 164
 165 void
 166 patricia_process (patricia_tree_t *patricia, void_fn_t func)
 167 {
 168     patricia_node_t *node;
 169     assert (func);
 170
 171     PATRICIA_WALK (patricia->head, node) {
 172         func (node->prefix);
 173     } PATRICIA_WALK_END;
 174 }
 175
 176 size_t
 177 patricia_walk_inorder(patricia_node_t *node, void_fn_t func)
 178 {
 179     size_t n = 0;
 180     assert(func);
 181
 182     if (node->l) {
 183          n += patricia_walk_inorder(node->l, func);
 184     }
 185
 186     if (node->prefix) {
 187         func(node->prefix);
 188         n++;
 189     }
 190
 191     if (node->r) {
 192          n += patricia_walk_inorder(node->r, func);
 193     }
 194
 195     return n;
 196 }
 197
 198
 199 patricia_node_t *
 200 patricia_search_exact (patricia_tree_t *patricia, struct irc_in_addr *sin, unsigned char bitlen)
 201 {
 202     patricia_node_t *node;
 203     u_char *addr;
 204
 205     assert (patricia);
 206     assert (sin);
 207     assert (bitlen <= patricia->maxbits);
 208
 209     if (patricia->head == NULL)
 210         return (NULL);
 211
 212     node = patricia->head;
 213     addr = (u_char *)sin;
 214
 215     while (node->bit < bitlen) {
 216         if (is_bit_set(addr,node->bit))
 217             node = node->r;
 218         else
 219             node = node->l;
 220
 221         if (node == NULL)
 222             return (NULL);
 223     }
 224
 225     if (node->bit > bitlen || node->prefix == NULL)
 226         return (NULL);
 227     assert (node->bit == bitlen);
 228     assert (node->bit == node->prefix->bitlen);
 229     if (comp_with_mask (prefix_tochar (node->prefix), addr, bitlen)) {
 230         return (node);
 231     }
 232     return (NULL);
 233 }
 234
 235
 236 /* if inclusive != 0, "best" may be the given prefix itself */
 237 patricia_node_t *
 238 patricia_search_best2 (patricia_tree_t *patricia, struct irc_in_addr *sin, unsigned char bitlen, int inclusive)
 239 {
 240     patricia_node_t *node;
 241     patricia_node_t *stack[PATRICIA_MAXBITS + 1];
 242     u_char *addr;
 243     int cnt = 0;
 244
 245     assert (patricia);
 246     assert (sin);
 247     assert (bitlen <= patricia->maxbits);
 248
 249     if (patricia->head == NULL)
 250         return (NULL);
 251
 252     node = patricia->head;
 253     addr = (u_char *)sin;
 254
 255     while (node->bit < bitlen) {
 256
 257         if (node->prefix) {
 258             stack[cnt++] = node;
 259         }
 260
 261         if (is_bit_set(addr,node->bit)) {
 262             node = node->r;
 263         }
 264         else {
 265             node = node->l;
 266         }
 267
 268         if (node == NULL)
 269             break;
 270     }
 271
 272     if (inclusive && node && node->prefix)
 273         stack[cnt++] = node;
 274
 275     if (cnt <= 0)
 276         return (NULL);
 277
 278     while (--cnt >= 0) {
 279         node = stack[cnt];
 280         if (comp_with_mask (prefix_tochar (node->prefix),
 281                             addr,
 282                             node->prefix->bitlen)) {
 283             return (node);
 284         }
 285     }
 286     return (NULL);
 287 }
 288
 289
 290 patricia_node_t *
 291 patricia_search_best (patricia_tree_t *patricia, struct irc_in_addr *sin, unsigned char bitlen)
 292 {
 293     return (patricia_search_best2 (patricia, sin, bitlen, 1));
 294 }
 295
 296
 297 patricia_node_t *
 298 patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix)
 299 {
 300     patricia_node_t *node, *new_node, *parent, *glue;
 301     u_char *addr, *test_addr;
 302     u_int bitlen, check_bit, differ_bit;
 303     int i, j, r;
 304
 305     assert (patricia);
 306     assert (prefix);
 307     assert (prefix->bitlen <= patricia->maxbits);
 308
 309     /* if new trie, create the first node */
 310     if (patricia->head == NULL) {
 311         node = patricia_new_node(patricia, prefix->bitlen, patricia_ref_prefix (prefix));
 312         patricia->head = node;
 313         return (node);
 314     }
 315
 316     addr = prefix_touchar (prefix);
 317     bitlen = prefix->bitlen;
 318     node = patricia->head;
 319
 320     /* while ( bitlength of tree node < bitlength of node we're searching for || the node has no prefix */
 321     while (node->bit < bitlen || node->prefix == NULL) {
 322         /* check that we're not at the lowest leaf i.e. node->bit is less than max bits */
 323         if (node->bit < patricia->maxbits &&
 324             (is_bit_set(addr,node->bit))) {
 325             if (node->r == NULL)
 326                 break;
 327             node = node->r;
 328         }
 329         else {
 330             if (node->l == NULL)
 331                 break;
 332             node = node->l;
 333         }
 334
 335         assert (node);
 336     }
 337
 338     assert (node->prefix);
 339
 340     test_addr = prefix_touchar (node->prefix);
 341     /* find the first bit different */
 342     check_bit = (node->bit < bitlen)? node->bit: bitlen;
 343     differ_bit = 0;
 344     for (i = 0; i*8 < check_bit; i++) {
 345         if ((r = (addr[i] ^ test_addr[i])) == 0) {
 346             differ_bit = (i + 1) * 8;
 347             continue;
 348         }
 349         /* I know the better way, but for now */
 350         for (j = 0; j < 8; j++) {
 351             if ((r) & ((0x80 >> j)))
 352                 break;
 353         }
 354         /* must be found */
 355         assert (j < 8);
 356         differ_bit = i * 8 + j;
 357         break;
 358     }
 359     if (differ_bit > check_bit)
 360         differ_bit = check_bit;
 361
 362
 363     parent = node->parent;
 364     while (parent && parent->bit >= differ_bit) {
 365         node = parent;
 366         parent = node->parent;
 367     }
 368
 369     if (differ_bit == bitlen && node->bit == bitlen) {
 370         if (!node->prefix) {
 371             node->prefix = patricia_ref_prefix (prefix);
 372         }
 373         return (node);
 374     }
 375
 376     new_node = patricia_new_node(patricia, prefix->bitlen, patricia_ref_prefix (prefix));
 377     if (node->bit == differ_bit) {
 378         new_node->parent = node;
 379         if (node->bit < patricia->maxbits &&
 380             (is_bit_set(addr, node->bit))) {
 381             assert (node->r == NULL);
 382             node->r = new_node;
 383         }
 384         else {
 385             assert (node->l == NULL);
 386             node->l = new_node;
 387         }
 388         return (new_node);
 389     }
 390
 391     if (bitlen == differ_bit) {
 392         if (bitlen < patricia->maxbits &&
 393             (is_bit_set(test_addr,bitlen))) {
 394             new_node->r = node;
 395         }
 396         else {
 397             new_node->l = node;
 398         }
 399         new_node->parent = node->parent;
 400         if (node->parent == NULL) {
 401             assert (patricia->head == node);
 402             patricia->head = new_node;
 403         }
 404         else if (node->parent->r == node) {
 405             node->parent->r = new_node;
 406         }
 407         else {
 408             node->parent->l = new_node;
 409         }
 410         node->parent = new_node;
 411         new_node->usercount = node->usercount;
 412     }
 413     else {
 414         glue = patricia_new_node(patricia, differ_bit, NULL);
 415         glue->parent = node->parent;
 416         if (differ_bit < patricia->maxbits &&
 417             (is_bit_set(addr, differ_bit))) {
 418             glue->r = new_node;
 419             glue->l = node;
 420         }
 421         else {
 422             glue->r = node;
 423             glue->l = new_node;
 424         }
 425         new_node->parent = glue;
 426
 427         if (node->parent == NULL) {
 428             assert (patricia->head == node);
 429             patricia->head = glue;
 430         }
 431         else if (node->parent->r == node) {
 432             node->parent->r = glue;
 433         }
 434         else {
 435             node->parent->l = glue;
 436         }
 437         node->parent = glue;
 438         glue->usercount = node->usercount;
 439     }
 440
 441     return (new_node);
 442 }
 443
 444 void
 445 patricia_remove (patricia_tree_t *patricia, patricia_node_t *node)
 446 {
 447     patricia_node_t *parent, *child;
 448
 449     assert (patricia);
 450     assert (node);
 451
 452     if (node->r && node->l) {
 453         /* this might be a placeholder node -- have to check and make sure
 454          * there is a prefix aossciated with it ! */
 455         if (node->prefix != NULL)
 456           patricia_deref_prefix (node->prefix);
 457         node->prefix = NULL;
 458         return;
 459     }
 460
 461     if (node->r == NULL && node->l == NULL) {
 462         parent = node->parent;
 463         patricia_deref_prefix (node->prefix);
 464         freenode(node);
 465         patricia->num_active_node--;
 466
 467         if (parent == NULL) {
 468             assert (patricia->head == node);
 469             patricia->head = NULL;
 470             return;
 471         }
 472
 473         if (parent->r == node) {
 474             parent->r = NULL;
 475             child = parent->l;
 476         }
 477         else {
 478             assert (parent->l == node);
 479             parent->l = NULL;
 480             child = parent->r;
 481         }
 482
 483         if (parent->prefix)
 484             return;
 485
 486         /* we need to remove parent too */
 487
 488         if (parent->parent == NULL) {
 489             assert (patricia->head == parent);
 490             patricia->head = child;
 491         }
 492         else if (parent->parent->r == parent) {
 493             parent->parent->r = child;
 494         }
 495         else {
 496             assert (parent->parent->l == parent);
 497             parent->parent->l = child;
 498         }
 499         child->parent = parent->parent;
 500         freenode(parent);
 501         patricia->num_active_node--;
 502         return;
 503     }
 504
 505     if (node->r) {
 506         child = node->r;
 507     }
 508     else {
 509         assert (node->l);
 510         child = node->l;
 511     }
 512     parent = node->parent;
 513     child->parent = parent;
 514
 515     patricia_deref_prefix (node->prefix);
 516     freenode(node);
 517     patricia->num_active_node--;
 518
 519     if (parent == NULL) {
 520         assert (patricia->head == node);
 521         patricia->head = child;
 522         return;
 523     }
 524
 525     if (parent->r == node) {
 526         parent->r = child;
 527     }
 528     else {
 529         assert (parent->l == node);
 530         parent->l = child;
 531     }
 532 }
 533
 534
 535 patricia_node_t *
 536 refnode(patricia_tree_t *tree, struct irc_in_addr *sin, int bitlen) {
 537   patricia_node_t *node;
 538   prefix_t *prefix;
 539
 540   node = patricia_search_exact(tree, sin, bitlen);
 541
 542   if (node == NULL) {
 543     prefix = patricia_new_prefix(sin, bitlen);
 544     node = patricia_lookup(tree, prefix);
 545     patricia_deref_prefix(prefix);
 546   } else if (node->prefix) {
 547     patricia_ref_prefix(node->prefix);
 548   }
 549
 550   return node;
 551 }
 552
 553 void
 554 derefnode(patricia_tree_t *tree, patricia_node_t *node) {
 555   if (!node || !node->prefix)
 556     return;
 557
 558   if (node->prefix->ref_count == 1) {
 559     patricia_remove(tree, node);
 560   } else
 561     patricia_deref_prefix(node->prefix);
 562 }
 563
 564 patricia_node_t *patricia_new_node(patricia_tree_t *patricia, unsigned char bit,prefix_t *prefix ) {
 565   patricia_node_t *new_node = newnode();
 566   memset(new_node->exts, 0, PATRICIA_MAXSLOTS * sizeof(void *));
 567   new_node->bit = bit;
 568   new_node->prefix = prefix;
 569   new_node->usercount = 0;
 570   new_node->parent = NULL;
 571   new_node->l = new_node->r = NULL;
 572   patricia->num_active_node++;
 573   return new_node;
 574 }
 575
 576 void node_increment_usercount( patricia_node_t *node) {
 577   while(node) {
 578     node->usercount++;
 579     node=node->parent;
 580   }
 581 }
 582
 583 void node_decrement_usercount( patricia_node_t *node) {
 584   while(node) {
 585     node->usercount--;
 586     node=node->parent;
 587   }
 588 }