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