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         node->usercount = 0;
 325         patricia->head = node;
 326         patricia->num_active_node++;
 327         return (node);
 328     }
 329
 330     addr = prefix_touchar (prefix);
 331     bitlen = prefix->bitlen;
 332     node = patricia->head;
 333
 334     /* while ( bitlength of tree node < bitlength of node we're searching for || the node has no prefix */
 335     while (node->bit < bitlen || node->prefix == NULL) {
 336         /* check that we're not at the lowest leaf i.e. node->bit is less than max bits */
 337         if (node->bit < patricia->maxbits &&
 338             (addr[node->bit >> 3]) & (0x80 >> (node->bit & 0x07))) {
 339             if (node->r == NULL)
 340                 break;
 341             node = node->r;
 342         }
 343         else {
 344             if (node->l == NULL)
 345                 break;
 346             node = node->l;
 347         }
 348
 349         assert (node);
 350     }
 351
 352     assert (node->prefix);
 353
 354     test_addr = prefix_touchar (node->prefix);
 355     /* find the first bit different */
 356     check_bit = (node->bit < bitlen)? node->bit: bitlen;
 357     differ_bit = 0;
 358     for (i = 0; i*8 < check_bit; i++) {
 359         if ((r = (addr[i] ^ test_addr[i])) == 0) {
 360             differ_bit = (i + 1) * 8;
 361             continue;
 362         }
 363         /* I know the better way, but for now */
 364         for (j = 0; j < 8; j++) {
 365             if ((r) & ((0x80 >> j)))
 366                 break;
 367         }
 368         /* must be found */
 369         assert (j < 8);
 370         differ_bit = i * 8 + j;
 371         break;
 372     }
 373     if (differ_bit > check_bit)
 374         differ_bit = check_bit;
 375
 376
 377     parent = node->parent;
 378     while (parent && parent->bit >= differ_bit) {
 379         node = parent;
 380         parent = node->parent;
 381     }
 382
 383     if (differ_bit == bitlen && node->bit == bitlen) {
 384         if (node->prefix) {
 385             return (node);
 386         }
 387         node->prefix = patricia_ref_prefix (prefix);
 388         return (node);
 389     }
 390
 391     new_node = malloc(sizeof *new_node);
 392     new_node->bit = prefix->bitlen;
 393     new_node->prefix = patricia_ref_prefix (prefix);
 394     new_node->parent = NULL;
 395     new_node->l = new_node->r = NULL;
 396     new_node->usercount = 0;
 397     patricia->num_active_node++;
 398
 399     if (node->bit == differ_bit) {
 400         new_node->parent = node;
 401         if (node->bit < patricia->maxbits &&
 402             (addr[node->bit >> 3]) & (0x80 >> (node->bit & 0x07))) {
 403             assert (node->r == NULL);
 404             node->r = new_node;
 405         }
 406         else {
 407             assert (node->l == NULL);
 408             node->l = new_node;
 409         }
 410         return (new_node);
 411     }
 412
 413     if (bitlen == differ_bit) {
 414         if (bitlen < patricia->maxbits &&
 415             (test_addr[bitlen >> 3]) & (0x80 >> (bitlen & 0x07))) {
 416             new_node->r = node;
 417         }
 418         else {
 419             new_node->l = node;
 420         }
 421         new_node->parent = node->parent;
 422         if (node->parent == NULL) {
 423             assert (patricia->head == node);
 424             patricia->head = new_node;
 425         }
 426         else if (node->parent->r == node) {
 427             node->parent->r = new_node;
 428         }
 429         else {
 430             node->parent->l = new_node;
 431         }
 432         node->parent = new_node;
 433     }
 434     else {
 435         glue = malloc(sizeof *glue);
 436         glue->bit = differ_bit;
 437         glue->prefix = NULL;
 438         glue->parent = node->parent;
 439         glue->usercount = 0;
 440         patricia->num_active_node++;
 441         if (differ_bit < patricia->maxbits &&
 442             (addr[differ_bit >> 3]) & (0x80 >> (differ_bit & 0x07))) {
 443             glue->r = new_node;
 444             glue->l = node;
 445         }
 446         else {
 447             glue->r = node;
 448             glue->l = new_node;
 449         }
 450         new_node->parent = glue;
 451
 452         if (node->parent == NULL) {
 453             assert (patricia->head == node);
 454             patricia->head = glue;
 455         }
 456         else if (node->parent->r == node) {
 457             node->parent->r = glue;
 458         }
 459         else {
 460             node->parent->l = glue;
 461         }
 462         node->parent = glue;
 463     }
 464     return (new_node);
 465 }
 466
 467 void
 468 patricia_remove (patricia_tree_t *patricia, patricia_node_t *node)
 469 {
 470     patricia_node_t *parent, *child;
 471
 472     assert (patricia);
 473     assert (node);
 474
 475     if (node->r && node->l) {
 476         /* this might be a placeholder node -- have to check and make sure
 477          * there is a prefix aossciated with it ! */
 478         if (node->prefix != NULL)
 479           patricia_deref_prefix (node->prefix);
 480         node->prefix = NULL;
 481         return;
 482     }
 483
 484     if (node->r == NULL && node->l == NULL) {
 485         parent = node->parent;
 486         patricia_deref_prefix (node->prefix);
 487         free(node);
 488         patricia->num_active_node--;
 489
 490         if (parent == NULL) {
 491             assert (patricia->head == node);
 492             patricia->head = NULL;
 493             return;
 494         }
 495
 496         if (parent->r == node) {
 497             parent->r = NULL;
 498             child = parent->l;
 499         }
 500         else {
 501             assert (parent->l == node);
 502             parent->l = NULL;
 503             child = parent->r;
 504         }
 505
 506         if (parent->prefix)
 507             return;
 508
 509         /* we need to remove parent too */
 510
 511         if (parent->parent == NULL) {
 512             assert (patricia->head == parent);
 513             patricia->head = child;
 514         }
 515         else if (parent->parent->r == parent) {
 516             parent->parent->r = child;
 517         }
 518         else {
 519             assert (parent->parent->l == parent);
 520             parent->parent->l = child;
 521         }
 522         child->parent = parent->parent;
 523         free(parent);
 524         patricia->num_active_node--;
 525         return;
 526     }
 527
 528     if (node->r) {
 529         child = node->r;
 530     }
 531     else {
 532         assert (node->l);
 533         child = node->l;
 534     }
 535     parent = node->parent;
 536     child->parent = parent;
 537
 538     patricia_deref_prefix (node->prefix);
 539     free(node);
 540     patricia->num_active_node--;
 541
 542     if (parent == NULL) {
 543         assert (patricia->head == node);
 544         patricia->head = child;
 545         return;
 546     }
 547
 548     if (parent->r == node) {
 549         parent->r = child;
 550     }
 551     else {
 552         assert (parent->l == node);
 553         parent->l = child;
 554     }
 555 }
 556
 557 /* } */
 558
 559 patricia_node_t *
 560 refnode(patricia_tree_t *tree, struct irc_in_addr *sin, int bitlen) {
 561   patricia_node_t *node;
 562   prefix_t *prefix;
 563
 564   node = patricia_search_exact(tree, sin, bitlen);
 565
 566   if (node == NULL) {
 567     prefix = patricia_new_prefix(sin, bitlen);
 568     node = patricia_lookup(tree, prefix);
 569     node->slots = (void **)malloc(PATRICIA_MAXSLOTS * sizeof(void *));
 570     memset(node->slots, 0, PATRICIA_MAXSLOTS * sizeof(void *));
 571     patricia_deref_prefix(prefix);
 572   } else if (node->prefix) {
 573     patricia_ref_prefix(node->prefix);
 574   }
 575
 576   return node;
 577 }
 578
 579 void
 580 derefnode(patricia_tree_t *tree, patricia_node_t *node) {
 581   if (!node || !node->prefix)
 582     return;
 583
 584   if (node->prefix->ref_count == 1) {
 585     free(node->slots);
 586     patricia_remove(tree, node);
 587   } else
 588     patricia_deref_prefix(node->prefix);
 589 }