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