src/lib/hash.c

   1 /*
   2  * hash.c       Non-thread-safe split-ordered hash table.
   3  *
   4  *  The weird "reverse" function is based on an idea from
   5  *  "Split-Ordered Lists - Lock-free Resizable Hash Tables", with
   6  *  modifications so that they're not lock-free. :(
   7  *
   8  *  However, the split-order idea allows a fast & easy splitting of the
   9  *  hash bucket chain when the hash table is resized.  Without it, we'd
  10  *  have to check & update the pointers for every node in the buck chain,
  11  *  rather than being able to move 1/2 of the entries in the chain with
  12  *  one update.
  13  *
  14  * Version:     $Id$
  15  *
  16  *   This library is free software; you can redistribute it and/or
  17  *   modify it under the terms of the GNU Lesser General Public
  18  *   License as published by the Free Software Foundation; either
  19  *   version 2.1 of the License, or (at your option) any later version.
  20  *
  21  *   This library is distributed in the hope that it will be useful,
  22  *   but WITHOUT ANY WARRANTY; without even the implied warranty of
  23  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  24  *   Lesser General Public License for more details.
  25  *
  26  *   You should have received a copy of the GNU Lesser General Public
  27  *   License along with this library; if not, write to the Free Software
  28  *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  29  *
  30  *  Copyright 2005,2006  The FreeRADIUS server project
  31  */
  32
  33 #include <freeradius-devel/ident.h>
  34 RCSID("$Id$")
  35
  36 #include <freeradius-devel/autoconf.h>
  37
  38 #include <stdlib.h>
  39 #include <string.h>
  40
  41 #include <freeradius-devel/missing.h>
  42 #include <freeradius-devel/hash.h>
  43
  44 /*
  45  *      A reasonable number of buckets to start off with.
  46  *      Should be a power of two.
  47  */
  48 #define LRAD_HASH_NUM_BUCKETS (64)
  49
  50 typedef struct lrad_hash_entry_t {
  51         struct lrad_hash_entry_t *next;
  52         uint32_t        reversed;
  53         uint32_t        key;
  54         void            *data;
  55 } lrad_hash_entry_t;
  56
  57
  58 struct lrad_hash_table_t {
  59         int                     num_elements;
  60         int                     num_buckets; /* power of 2 */
  61         int                     next_grow;
  62         int                     mask;
  63
  64         lrad_hash_table_free_t  free;
  65         lrad_hash_table_hash_t  hash;
  66         lrad_hash_table_cmp_t   cmp;
  67
  68         lrad_hash_entry_t       null;
  69
  70         lrad_hash_entry_t       **buckets;
  71 };
  72
  73 #ifdef TESTING
  74 #include <stdio.h>
  75
  76 static int grow = 0;
  77 #endif
  78
  79 /*
  80  * perl -e 'foreach $i (0..255) {$r = 0; foreach $j (0 .. 7 ) { if (($i & ( 1<< $j)) != 0) { $r |= (1 << (7 - $j));}} print $r, ", ";if (($i & 7) == 7) {print "\n";}}'
  81  */
  82 static const uint8_t reversed_byte[256] = {
  83         0,  128, 64, 192, 32, 160, 96,  224,
  84         16, 144, 80, 208, 48, 176, 112, 240,
  85         8,  136, 72, 200, 40, 168, 104, 232,
  86         24, 152, 88, 216, 56, 184, 120, 248,
  87         4,  132, 68, 196, 36, 164, 100, 228,
  88         20, 148, 84, 212, 52, 180, 116, 244,
  89         12, 140, 76, 204, 44, 172, 108, 236,
  90         28, 156, 92, 220, 60, 188, 124, 252,
  91         2,  130, 66, 194, 34, 162, 98,  226,
  92         18, 146, 82, 210, 50, 178, 114, 242,
  93         10, 138, 74, 202, 42, 170, 106, 234,
  94         26, 154, 90, 218, 58, 186, 122, 250,
  95         6,  134, 70, 198, 38, 166, 102, 230,
  96         22, 150, 86, 214, 54, 182, 118, 246,
  97         14, 142, 78, 206, 46, 174, 110, 238,
  98         30, 158, 94, 222, 62, 190, 126, 254,
  99         1,  129, 65, 193, 33, 161, 97,  225,
 100         17, 145, 81, 209, 49, 177, 113, 241,
 101         9,  137, 73, 201, 41, 169, 105, 233,
 102         25, 153, 89, 217, 57, 185, 121, 249,
 103         5,  133, 69, 197, 37, 165, 101, 229,
 104         21, 149, 85, 213, 53, 181, 117, 245,
 105         13, 141, 77, 205, 45, 173, 109, 237,
 106         29, 157, 93, 221, 61, 189, 125, 253,
 107         3,  131, 67, 195, 35, 163, 99,  227,
 108         19, 147, 83, 211, 51, 179, 115, 243,
 109         11, 139, 75, 203, 43, 171, 107, 235,
 110         27, 155, 91, 219, 59, 187, 123, 251,
 111         7,  135, 71, 199, 39, 167, 103, 231,
 112         23, 151, 87, 215, 55, 183, 119, 247,
 113         15, 143, 79, 207, 47, 175, 111, 239,
 114         31, 159, 95, 223, 63, 191, 127, 255
 115 };
 116
 117
 118 /*
 119  * perl -e 'foreach $i (0..255) {$r = 0;foreach $j (0 .. 7) { $r = $i & (1 << (7 - $j)); last if ($r)} print $i & ~($r), ", ";if (($i & 7) == 7) {print "\n";}}'
 120  */
 121 static uint8_t parent_byte[256] = {
 122         0, 0, 0, 1, 0, 1, 2, 3,
 123         0, 1, 2, 3, 4, 5, 6, 7,
 124         0, 1, 2, 3, 4, 5, 6, 7,
 125         8, 9, 10, 11, 12, 13, 14, 15,
 126         0, 1, 2, 3, 4, 5, 6, 7,
 127         8, 9, 10, 11, 12, 13, 14, 15,
 128         16, 17, 18, 19, 20, 21, 22, 23,
 129         24, 25, 26, 27, 28, 29, 30, 31,
 130         0, 1, 2, 3, 4, 5, 6, 7,
 131         8, 9, 10, 11, 12, 13, 14, 15,
 132         16, 17, 18, 19, 20, 21, 22, 23,
 133         24, 25, 26, 27, 28, 29, 30, 31,
 134         32, 33, 34, 35, 36, 37, 38, 39,
 135         40, 41, 42, 43, 44, 45, 46, 47,
 136         48, 49, 50, 51, 52, 53, 54, 55,
 137         56, 57, 58, 59, 60, 61, 62, 63,
 138         0, 1, 2, 3, 4, 5, 6, 7,
 139         8, 9, 10, 11, 12, 13, 14, 15,
 140         16, 17, 18, 19, 20, 21, 22, 23,
 141         24, 25, 26, 27, 28, 29, 30, 31,
 142         32, 33, 34, 35, 36, 37, 38, 39,
 143         40, 41, 42, 43, 44, 45, 46, 47,
 144         48, 49, 50, 51, 52, 53, 54, 55,
 145         56, 57, 58, 59, 60, 61, 62, 63,
 146         64, 65, 66, 67, 68, 69, 70, 71,
 147         72, 73, 74, 75, 76, 77, 78, 79,
 148         80, 81, 82, 83, 84, 85, 86, 87,
 149         88, 89, 90, 91, 92, 93, 94, 95,
 150         96, 97, 98, 99, 100, 101, 102, 103,
 151         104, 105, 106, 107, 108, 109, 110, 111,
 152         112, 113, 114, 115, 116, 117, 118, 119,
 153         120, 121, 122, 123, 124, 125, 126, 127
 154 };
 155
 156
 157 /*
 158  *      Reverse a key.
 159  */
 160 static uint32_t reverse(uint32_t key)
 161 {
 162         return ((reversed_byte[key & 0xff] << 24) |
 163                 (reversed_byte[(key >> 8) & 0xff] << 16) |
 164                 (reversed_byte[(key >> 16) & 0xff] << 8) |
 165                 (reversed_byte[(key >> 24) & 0xff]));
 166 }
 167
 168 /*
 169  *      Take the parent by discarding the highest bit that is set.
 170  */
 171 static uint32_t parent_of(uint32_t key)
 172 {
 173         if (key > 0x00ffffff)
 174                 return (key & 0x00ffffff) | (parent_byte[key >> 24] << 24);
 175
 176         if (key > 0x0000ffff)
 177                 return (key & 0x0000ffff) | (parent_byte[key >> 16] << 16);
 178
 179         if (key > 0x000000ff)
 180                 return (key & 0x000000ff) | (parent_byte[key >> 8] << 8);
 181
 182         return parent_byte[key];
 183 }
 184
 185
 186 static lrad_hash_entry_t *list_find(lrad_hash_table_t *ht,
 187                                     lrad_hash_entry_t *head,
 188                                     uint32_t reversed,
 189                                     const void *data)
 190 {
 191         lrad_hash_entry_t *cur;
 192
 193         for (cur = head; cur != &ht->null; cur = cur->next) {
 194                 if (cur->reversed == reversed) {
 195                         if (ht->cmp) {
 196                                 int cmp = ht->cmp(data, cur->data);
 197                                 if (cmp > 0) break;
 198                                 if (cmp < 0) continue;
 199                         }
 200                         return cur;
 201                 }
 202                 if (cur->reversed > reversed) break;
 203         }
 204
 205         return NULL;
 206 }
 207
 208
 209 /*
 210  *      Inserts a new entry into the list, in order.
 211  */
 212 static int list_insert(lrad_hash_table_t *ht,
 213                        lrad_hash_entry_t **head, lrad_hash_entry_t *node)
 214 {
 215         lrad_hash_entry_t **last, *cur;
 216
 217         last = head;
 218
 219         for (cur = *head; cur != &ht->null; cur = cur->next) {
 220                 if (cur->reversed > node->reversed) break;
 221                 last = &(cur->next);
 222
 223                 if (cur->reversed == node->reversed) {
 224                         if (ht->cmp) {
 225                                 int cmp = ht->cmp(node->data, cur->data);
 226                                 if (cmp > 0) break;
 227                                 if (cmp < 0) continue;
 228                         }
 229                         return 0;
 230                 }
 231         }
 232
 233         node->next = *last;
 234         *last = node;
 235
 236         return 1;
 237 }
 238
 239
 240 /*
 241  *      Delete an entry from the list.
 242  */
 243 static int list_delete(lrad_hash_table_t *ht,
 244                        lrad_hash_entry_t **head, lrad_hash_entry_t *node)
 245 {
 246         lrad_hash_entry_t **last, *cur;
 247
 248         last = head;
 249
 250         for (cur = *head; cur != &ht->null; cur = cur->next) {
 251                 if (cur == node) {
 252                         if (ht->cmp) {
 253                                 int cmp = ht->cmp(node->data, cur->data);
 254                                 if (cmp > 0) break;
 255                                 if (cmp < 0) continue;
 256                         }
 257                         break;
 258                 }
 259                 last = &(cur->next);
 260         }
 261
 262         *last = node->next;
 263         return 1;
 264 }
 265
 266
 267 /*
 268  *      Create the table.
 269  *
 270  *      Memory usage in bytes is (20/3) * number of entries.
 271  */
 272 lrad_hash_table_t *lrad_hash_table_create(lrad_hash_table_hash_t hashNode,
 273                                           lrad_hash_table_cmp_t cmpNode,
 274                                           lrad_hash_table_free_t freeNode)
 275 {
 276         lrad_hash_table_t *ht;
 277
 278         if (!hashNode) return NULL;
 279
 280         ht = malloc(sizeof(*ht));
 281         if (!ht) return NULL;
 282
 283         memset(ht, 0, sizeof(*ht));
 284         ht->free = freeNode;
 285         ht->hash = hashNode;
 286         ht->cmp = cmpNode;
 287         ht->num_buckets = LRAD_HASH_NUM_BUCKETS;
 288         ht->mask = ht->num_buckets - 1;
 289
 290         /*
 291          *      Have a default load factor of 2.5.  In practice this
 292          *      means that the average load will hit 3 before the
 293          *      table grows.
 294          */
 295         ht->next_grow = (ht->num_buckets << 1) + (ht->num_buckets >> 1);
 296
 297         ht->buckets = malloc(sizeof(*ht->buckets) * ht->num_buckets);
 298         if (!ht->buckets) {
 299                 free(ht);
 300                 return NULL;
 301         }
 302         memset(ht->buckets, 0, sizeof(*ht->buckets) * ht->num_buckets);
 303
 304         ht->null.reversed = ~0;
 305         ht->null.key = ~0;
 306         ht->null.next = &ht->null;
 307
 308         ht->buckets[0] = &ht->null;
 309
 310         return ht;
 311 }
 312
 313
 314 /*
 315  *      If the current bucket is uninitialized, initialize it
 316  *      by recursively copying information from the parent.
 317  *
 318  *      We may have a situation where entry E is a parent to 2 other
 319  *      entries E' and E".  If we split E into E and E', then the
 320  *      nodes meant for E" end up in E or E', either of which is
 321  *      wrong.  To solve that problem, we walk down the whole chain,
 322  *      inserting the elements into the correct place.
 323  */
 324 static void lrad_hash_table_fixup(lrad_hash_table_t *ht, uint32_t entry)
 325 {
 326         uint32_t parent_entry = parent_of(entry);
 327         lrad_hash_entry_t **last, *cur;
 328         uint32_t this;
 329
 330         parent_entry = parent_of(entry);
 331
 332         /* parent_entry == entry if and only if entry == 0 */
 333
 334         if (!ht->buckets[parent_entry]) {
 335                 lrad_hash_table_fixup(ht, parent_entry);
 336         }
 337
 338         /*
 339          *      Keep walking down cur, trying to find entries that
 340          *      don't belong here any more.  There may be multiple
 341          *      ones, so we can't have a naive algorithm...
 342          */
 343         last = &ht->buckets[parent_entry];
 344         this = parent_entry;
 345
 346         for (cur = *last; cur != &ht->null; cur = cur->next) {
 347                 uint32_t real_entry;
 348
 349                 real_entry = cur->key & ht->mask;
 350                 if (real_entry != this) { /* ht->buckets[real_entry] == NULL */
 351                         *last = &ht->null;
 352                         ht->buckets[real_entry] = cur;
 353                         this = real_entry;
 354                 }
 355
 356                 last = &(cur->next);
 357         }
 358
 359         /*
 360          *      We may NOT have initialized this bucket, so do it now.
 361          */
 362         if (!ht->buckets[entry]) ht->buckets[entry] = &ht->null;
 363 }
 364
 365 /*
 366  *      This should be a power of two.  Changing it to 4 doesn't seem
 367  *      to make any difference.
 368  */
 369 #define GROW_FACTOR (2)
 370
 371 /*
 372  *      Grow the hash table.
 373  */
 374 static void lrad_hash_table_grow(lrad_hash_table_t *ht)
 375 {
 376         lrad_hash_entry_t **buckets;
 377
 378         buckets = malloc(sizeof(*buckets) * GROW_FACTOR * ht->num_buckets);
 379         if (!buckets) return;
 380
 381         memcpy(buckets, ht->buckets,
 382                sizeof(*buckets) * ht->num_buckets);
 383         memset(&buckets[ht->num_buckets], 0,
 384                sizeof(*buckets) * ht->num_buckets);
 385
 386         free(ht->buckets);
 387         ht->buckets = buckets;
 388         ht->num_buckets *= GROW_FACTOR;
 389         ht->next_grow *= GROW_FACTOR;
 390         ht->mask = ht->num_buckets - 1;
 391 #ifdef TESTING
 392         grow = 1;
 393         fprintf(stderr, "GROW TO %d\n", ht->num_buckets);
 394 #endif
 395 }
 396
 397
 398 /*
 399  *      Insert data.
 400  */
 401 int lrad_hash_table_insert(lrad_hash_table_t *ht, void *data)
 402 {
 403         uint32_t key;
 404         uint32_t entry;
 405         uint32_t reversed;
 406         lrad_hash_entry_t *node;
 407
 408         if (!ht || !data) return 0;
 409
 410         key = ht->hash(data);
 411         entry = key & ht->mask;
 412         reversed = reverse(key);
 413
 414         if (!ht->buckets[entry]) lrad_hash_table_fixup(ht, entry);
 415
 416         /*
 417          *      If we try to do our own memory allocation here, the
 418          *      speedup is only ~15% or so, which isn't worth it.
 419          */
 420         node = malloc(sizeof(*node));
 421         if (!node) return 0;
 422         memset(node, 0, sizeof(*node));
 423
 424         node->next = &ht->null;
 425         node->reversed = reversed;
 426         node->key = key;
 427         node->data = data;
 428
 429         /* already in the table, can't insert it */
 430         if (!list_insert(ht, &ht->buckets[entry], node)) {
 431                 free(node);
 432                 return 0;
 433         }
 434
 435         /*
 436          *      Check the load factor, and grow the table if
 437          *      necessary.
 438          */
 439         ht->num_elements++;
 440         if (ht->num_elements >= ht->next_grow) {
 441                 lrad_hash_table_grow(ht);
 442         }
 443
 444         return 1;
 445 }
 446
 447
 448 /*
 449  *      Internal find a node routine.
 450  */
 451 static lrad_hash_entry_t *lrad_hash_table_find(lrad_hash_table_t *ht,
 452                                                const void *data)
 453 {
 454         uint32_t key;
 455         uint32_t entry;
 456         uint32_t reversed;
 457
 458         if (!ht) return NULL;
 459
 460         key = ht->hash(data);
 461         entry = key & ht->mask;
 462         reversed = reverse(key);
 463
 464         if (!ht->buckets[entry]) lrad_hash_table_fixup(ht, entry);
 465
 466         return list_find(ht, ht->buckets[entry], reversed, data);
 467 }
 468
 469
 470 /*
 471  *      Replace old data with new data, OR insert if there is no old.
 472  */
 473 int lrad_hash_table_replace(lrad_hash_table_t *ht, void *data)
 474 {
 475         lrad_hash_entry_t *node;
 476
 477         if (!ht || !data) return 0;
 478
 479         node = lrad_hash_table_find(ht, data);
 480         if (!node) return lrad_hash_table_insert(ht, data);
 481
 482         if (ht->free) ht->free(node->data);
 483         node->data = data;
 484
 485         return 1;
 486 }
 487
 488
 489 /*
 490  *      Find data from a template
 491  */
 492 void *lrad_hash_table_finddata(lrad_hash_table_t *ht, const void *data)
 493 {
 494         lrad_hash_entry_t *node;
 495
 496         node = lrad_hash_table_find(ht, data);
 497         if (!node) return NULL;
 498
 499         return node->data;
 500 }
 501
 502
 503
 504 /*
 505  *      Yank an entry from the hash table, without freeing the data.
 506  */
 507 void *lrad_hash_table_yank(lrad_hash_table_t *ht, const void *data)
 508 {
 509         uint32_t key;
 510         uint32_t entry;
 511         uint32_t reversed;
 512         void *old;
 513         lrad_hash_entry_t *node;
 514
 515         if (!ht) return NULL;
 516
 517         key = ht->hash(data);
 518         entry = key & ht->mask;
 519         reversed = reverse(key);
 520
 521         if (!ht->buckets[entry]) lrad_hash_table_fixup(ht, entry);
 522
 523         node = list_find(ht, ht->buckets[entry], reversed, data);
 524         if (!node) return NULL;
 525
 526         list_delete(ht, &ht->buckets[entry], node);
 527         ht->num_elements--;
 528
 529         old = node->data;
 530         free(node);
 531
 532         return old;
 533 }
 534
 535
 536 /*
 537  *      Delete a piece of data from the hash table.
 538  */
 539 int lrad_hash_table_delete(lrad_hash_table_t *ht, const void *data)
 540 {
 541         void *old;
 542
 543         old = lrad_hash_table_yank(ht, data);
 544         if (!old) return 0;
 545
 546         if (ht->free) ht->free(old);
 547
 548         return 1;
 549 }
 550
 551
 552 /*
 553  *      Free a hash table
 554  */
 555 void lrad_hash_table_free(lrad_hash_table_t *ht)
 556 {
 557         int i;
 558         lrad_hash_entry_t *node, *next;
 559
 560         if (!ht) return;
 561
 562         /*
 563          *      Walk over the buckets, freeing them all.
 564          */
 565         for (i = 0; i < ht->num_buckets; i++) {
 566                 if (ht->buckets[i]) for (node = ht->buckets[i];
 567                                          node != &ht->null;
 568                                          node = next) {
 569                         next = node->next;
 570
 571                         if (!node->data) continue; /* dummy entry */
 572
 573                         if (ht->free) ht->free(node->data);
 574                         free(node);
 575                 }
 576         }
 577
 578         free(ht->buckets);
 579         free(ht);
 580 }
 581
 582
 583 /*
 584  *      Count number of elements
 585  */
 586 int lrad_hash_table_num_elements(lrad_hash_table_t *ht)
 587 {
 588         if (!ht) return 0;
 589
 590         return ht->num_elements;
 591 }
 592
 593
 594 /*
 595  *      Walk over the nodes, allowing deletes & inserts to happen.
 596  */
 597 int lrad_hash_table_walk(lrad_hash_table_t *ht,
 598                          lrad_hash_table_walk_t callback,
 599                          void *context)
 600 {
 601         int i, rcode;;
 602
 603         if (!ht || !callback) return 0;
 604
 605         for (i = ht->num_buckets - 1; i >= 0; i--) {
 606                 lrad_hash_entry_t *node, *next;
 607
 608                 /*
 609                  *      Ensure that the current bucket is filled.
 610                  */
 611                 if (!ht->buckets[i]) lrad_hash_table_fixup(ht, i);
 612
 613                 for (node = ht->buckets[i]; node != &ht->null; node = next) {
 614                         next = node->next;
 615
 616                         rcode = callback(context, node->data);
 617                         if (rcode != 0) return rcode;
 618                 }
 619         }
 620
 621         return 0;
 622 }
 623
 624
 625 #ifdef TESTING
 626 /*
 627  *      Show what the hash table is doing.
 628  */
 629 int lrad_hash_table_info(lrad_hash_table_t *ht)
 630 {
 631         int i, a, collisions, uninitialized;
 632         int array[256];
 633
 634         if (!ht) return 0;
 635
 636         uninitialized = collisions = 0;
 637         memset(array, 0, sizeof(array));
 638
 639         for (i = 0; i < ht->num_buckets; i++) {
 640                 uint32_t key;
 641                 int load;
 642                 lrad_hash_entry_t *node, *next;
 643
 644                 /*
 645                  *      If we haven't inserted or looked up an entry
 646                  *      in a bucket, it's uninitialized.
 647                  */
 648                 if (!ht->buckets[i]) {
 649                         uninitialized++;
 650                         continue;
 651                 }
 652
 653                 load = 0;
 654                 key = ~0;
 655                 for (node = ht->buckets[i]; node != &ht->null; node = next) {
 656                         if (node->reversed == key) {
 657                                 collisions++;
 658                         } else {
 659                                 key = node->reversed;
 660                         }
 661                         next = node->next;
 662                         load++;
 663                 }
 664
 665                 if (load > 255) load = 255;
 666                 array[load]++;
 667         }
 668
 669         printf("HASH TABLE %p\tbuckets: %d\t(%d uninitialized)\n", ht,
 670                 ht->num_buckets, uninitialized);
 671         printf("\tnum entries %d\thash collisions %d\n",
 672                 ht->num_elements, collisions);
 673
 674         a = 0;
 675         for (i = 1; i < 256; i++) {
 676                 if (!array[i]) continue;
 677                 printf("%d\t%d\n", i, array[i]);
 678
 679                 /*
 680                  *      Since the entries are ordered, the lookup cost
 681                  *      for any one element in a chain is (on average)
 682                  *      the cost of walking half of the chain.
 683                  */
 684                 if (i > 1) {
 685                         a += array[i] * i;
 686                 }
 687         }
 688         a /= 2;
 689         a += array[1];
 690
 691         printf("\texpected lookup cost = %d/%d or %f\n\n",
 692                ht->num_elements, a,
 693                (float) ht->num_elements / (float) a);
 694
 695         return 0;
 696 }
 697 #endif
 698
 699
 700 #define FNV_MAGIC_INIT (0x811c9dc5)
 701 #define FNV_MAGIC_PRIME (0x01000193)
 702
 703 /*
 704  *      A fast hash function.  For details, see:
 705  *
 706  *      http://www.isthe.com/chongo/tech/comp/fnv/
 707  *
 708  *      Which also includes public domain source.  We've re-written
 709  *      it here for our purposes.
 710  */
 711 uint32_t lrad_hash(const void *data, size_t size)
 712 {
 713         const uint8_t *p = data;
 714         const uint8_t *q = p + size;
 715         uint32_t      hash = FNV_MAGIC_INIT;
 716
 717         /*
 718          *      FNV-1 hash each octet in the buffer
 719          */
 720         while (p != q) {
 721                 /*
 722                  *      Multiple by 32-bit magic FNV prime, mod 2^32
 723                  */
 724                 hash *= FNV_MAGIC_PRIME;
 725 #if 0
 726                 /*
 727                  *      Potential optimization.
 728                  */
 729                 hash += (hash<<1) + (hash<<4) + (hash<<7) + (hash<<8) + (hash<<24);
 730 #endif
 731                 /*
 732                  *      XOR the 8-bit quantity into the bottom of
 733                  *      the hash.
 734                  */
 735                 hash ^= (uint32_t) (*p++);
 736     }
 737
 738     return hash;
 739 }
 740
 741 /*
 742  *      Continue hashing data.
 743  */
 744 uint32_t lrad_hash_update(const void *data, size_t size, uint32_t hash)
 745 {
 746         const uint8_t *p = data;
 747         const uint8_t *q = p + size;
 748
 749         while (p != q) {
 750                 hash *= FNV_MAGIC_PRIME;
 751                 hash ^= (uint32_t) (*p++);
 752     }
 753
 754     return hash;
 755
 756 }
 757
 758 /*
 759  *      Return a "folded" hash, where the lower "bits" are the
 760  *      hash, and the upper bits are zero.
 761  *
 762  *      If you need a non-power-of-two hash, cope.
 763  */
 764 uint32_t lrad_hash_fold(uint32_t hash, int bits)
 765 {
 766         int count;
 767         uint32_t result;
 768
 769         if ((bits <= 0) || (bits >= 32)) return hash;
 770
 771         result = hash;
 772
 773         /*
 774          *      Never use the same bits twice in an xor.
 775          */
 776         for (count = 0; count < 32; count += bits) {
 777                 hash >>= bits;
 778                 result ^= hash;
 779         }
 780
 781         return result & (((uint32_t) (1 << bits)) - 1);
 782 }
 783
 784
 785 /*
 786  *      Hash a C string, so we loop over it once.
 787  */
 788 uint32_t lrad_hash_string(const char *p)
 789 {
 790         uint32_t      hash = FNV_MAGIC_INIT;
 791
 792         while (*p) {
 793                 hash *= FNV_MAGIC_PRIME;
 794                 hash ^= (uint32_t) (*p++);
 795         }
 796
 797         return hash;
 798 }
 799
 800
 801 #ifdef TESTING
 802 /*
 803  *  cc -g -DTESTING -I ../include hash.c -o hash
 804  *
 805  *  ./hash
 806  */
 807
 808 #include <stdio.h>
 809 #include <stdlib.h>
 810
 811 static uint32_t hash_int(const void *data)
 812 {
 813         return lrad_hash((int *) data, sizeof(int));
 814 }
 815
 816 #define MAX 1024*1024
 817 int main(int argc, char **argv)
 818 {
 819         int i, *p, *q, k;
 820         lrad_hash_table_t *ht;
 821         int *array;
 822
 823         ht = lrad_hash_table_create(hash_int, NULL, NULL);
 824         if (!ht) {
 825                 fprintf(stderr, "Hash create failed\n");
 826                 exit(1);
 827         }
 828
 829         array = malloc(sizeof(int) * MAX);
 830         if (!array) exit(1);
 831
 832         for (i = 0; i < MAX; i++) {
 833                 p = array + i;
 834                 *p = i;
 835
 836                 if (!lrad_hash_table_insert(ht, p)) {
 837                         fprintf(stderr, "Failed insert %08x\n", i);
 838                         exit(1);
 839                 }
 840 #ifdef TEST_INSERT
 841                 q = lrad_hash_table_finddata(ht, p);
 842                 if (q != p) {
 843                         fprintf(stderr, "Bad data %d\n", i);
 844                         exit(1);
 845                 }
 846 #endif
 847         }
 848
 849         lrad_hash_table_info(ht);
 850
 851         /*
 852          *      Build this to see how lookups result in shortening
 853          *      of the hash chains.
 854          */
 855         if (1) {
 856                 for (i = 0; i < MAX ; i++) {
 857                         q = lrad_hash_table_finddata(ht, &i);
 858                         if (!q || *q != i) {
 859                                 fprintf(stderr, "Failed finding %d\n", i);
 860                                 exit(1);
 861                         }
 862
 863 #if 0
 864                         if (!lrad_hash_table_delete(ht, &i)) {
 865                                 fprintf(stderr, "Failed deleting %d\n", i);
 866                                 exit(1);
 867                         }
 868                         q = lrad_hash_table_finddata(ht, &i);
 869                         if (q) {
 870                                 fprintf(stderr, "Failed to delete %08x\n", i);
 871                                 exit(1);
 872                         }
 873 #endif
 874                 }
 875
 876                 lrad_hash_table_info(ht);
 877         }
 878
 879         lrad_hash_table_free(ht);
 880         free(array);
 881
 882         exit(0);
 883 }
 884 #endif