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., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA
  29  *
  30  *  Copyright 2005  The FreeRADIUS server project
  31  */
  32
  33 static const char rcsid[] = "$Id$";
  34
  35 #include "autoconf.h"
  36
  37 #include <stdlib.h>
  38 #include <string.h>
  39
  40 #include "missing.h"
  41 #include "libradius.h"
  42
  43 typedef struct lrad_hash_entry_t {
  44         struct lrad_hash_entry_t *next;
  45         uint32_t        key; /* reversed image of the key */
  46         void            *data;
  47 } lrad_hash_entry_t;
  48
  49 struct lrad_hash_table_t {
  50         int                     num_elements;
  51         int                     num_buckets; /* power of 2 */
  52         int                     replace_flag;
  53         size_t                  data_size;
  54         void                    (*free)(void *);
  55         lrad_hash_entry_t       **buckets;
  56 };
  57
  58 #ifdef TESTING
  59 static int grow = 0;
  60 #endif
  61
  62
  63 /*
  64  * 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";}}'
  65  */
  66 static const uint8_t reversed_byte[256] = {
  67         0,  128, 64, 192, 32, 160, 96,  224,
  68         16, 144, 80, 208, 48, 176, 112, 240,
  69         8,  136, 72, 200, 40, 168, 104, 232,
  70         24, 152, 88, 216, 56, 184, 120, 248,
  71         4,  132, 68, 196, 36, 164, 100, 228,
  72         20, 148, 84, 212, 52, 180, 116, 244,
  73         12, 140, 76, 204, 44, 172, 108, 236,
  74         28, 156, 92, 220, 60, 188, 124, 252,
  75         2,  130, 66, 194, 34, 162, 98,  226,
  76         18, 146, 82, 210, 50, 178, 114, 242,
  77         10, 138, 74, 202, 42, 170, 106, 234,
  78         26, 154, 90, 218, 58, 186, 122, 250,
  79         6,  134, 70, 198, 38, 166, 102, 230,
  80         22, 150, 86, 214, 54, 182, 118, 246,
  81         14, 142, 78, 206, 46, 174, 110, 238,
  82         30, 158, 94, 222, 62, 190, 126, 254,
  83         1,  129, 65, 193, 33, 161, 97,  225,
  84         17, 145, 81, 209, 49, 177, 113, 241,
  85         9,  137, 73, 201, 41, 169, 105, 233,
  86         25, 153, 89, 217, 57, 185, 121, 249,
  87         5,  133, 69, 197, 37, 165, 101, 229,
  88         21, 149, 85, 213, 53, 181, 117, 245,
  89         13, 141, 77, 205, 45, 173, 109, 237,
  90         29, 157, 93, 221, 61, 189, 125, 253,
  91         3,  131, 67, 195, 35, 163, 99,  227,
  92         19, 147, 83, 211, 51, 179, 115, 243,
  93         11, 139, 75, 203, 43, 171, 107, 235,
  94         27, 155, 91, 219, 59, 187, 123, 251,
  95         7,  135, 71, 199, 39, 167, 103, 231,
  96         23, 151, 87, 215, 55, 183, 119, 247,
  97         15, 143, 79, 207, 47, 175, 111, 239,
  98         31, 159, 95, 223, 63, 191, 127, 255
  99 };
 100
 101
 102 /*
 103  *      Reverse a key.
 104  */
 105 static uint32_t reverse(uint32_t key)
 106 {
 107         return ((reversed_byte[key & 0xff] << 24) |
 108                 (reversed_byte[(key >> 8) & 0xff] << 16) |
 109                 (reversed_byte[(key >> 16) & 0xff] << 8) |
 110                 (reversed_byte[(key >> 24) & 0xff]));
 111 }
 112
 113 static lrad_hash_entry_t *list_find(lrad_hash_entry_t *head, uint32_t key)
 114 {
 115         lrad_hash_entry_t *cur;
 116
 117         for (cur = head; cur != NULL; cur = cur->next) {
 118                 if (cur->key > key) return NULL;
 119                 if (cur->key == key) return cur;
 120         }
 121
 122         return NULL;
 123 }
 124
 125 /*
 126  *      Inserts a new entry into the list, in order.
 127  */
 128 static int list_insert(lrad_hash_entry_t **head, lrad_hash_entry_t *node)
 129 {
 130         lrad_hash_entry_t **last, *cur;
 131
 132         last = head;
 133
 134         for (cur = *head; cur != NULL; cur = cur->next) {
 135                 if (cur->key > node->key) break;
 136                 last = &(cur->next);
 137         }
 138
 139         node->next = *last;
 140         *last = node;
 141
 142         return 1;
 143 }
 144
 145
 146 /*
 147  *      Delete an entry from the list.
 148  */
 149 static int list_delete(lrad_hash_entry_t **head, lrad_hash_entry_t *node)
 150 {
 151         lrad_hash_entry_t **last, *cur;
 152
 153         last = head;
 154
 155         for (cur = *head; cur != NULL; cur = cur->next) {
 156                 if (cur == node) break;
 157                 last = &(cur->next);
 158         }
 159
 160         *last = node->next;
 161         return 1;
 162 }
 163
 164
 165 /*
 166  *      Split a list.  Everything >= key is returned, and the returned
 167  *      list is removed from the input list.
 168  */
 169 static lrad_hash_entry_t *list_split(lrad_hash_entry_t **head, uint32_t key)
 170 {
 171         lrad_hash_entry_t **last, *cur;
 172
 173         last = head;
 174
 175         for (cur = *head; cur != NULL; cur = cur->next) {
 176                 if (cur->key >= key) break;
 177                 last = &(cur->next);
 178         }
 179
 180         *last = NULL;
 181
 182         return cur;
 183 }
 184
 185
 186 /*
 187  *      Create the table.  Size is a power of two (i.e. 1..31)
 188  */
 189 lrad_hash_table_t *lrad_hash_table_create(int size, void (*freeNode)(void *),
 190                                           int replace_flag)
 191 {
 192         lrad_hash_table_t *ht;
 193
 194         if ((size <= 1) || (size > 31)) return NULL;
 195
 196         /*
 197          *      Get the nearest power of two.
 198          */
 199         size = 1 << size;
 200
 201         ht = malloc(sizeof(*ht));
 202         if (!ht) return NULL;
 203
 204         memset(ht, 0, sizeof(*ht));
 205         ht->free = freeNode;
 206         ht->num_buckets = size;
 207         ht->replace_flag = replace_flag;
 208
 209         ht->buckets = malloc(sizeof(*ht->buckets) * ht->num_buckets);
 210         if (!ht->buckets) {
 211                 free(ht);
 212                 return NULL;
 213         }
 214         memset(ht->buckets, 0, sizeof(*ht->buckets) * ht->num_buckets);
 215
 216         return ht;
 217 }
 218
 219 /*
 220  *      Insert data, OR copy it, if ht->data_size != 0
 221  */
 222 int lrad_hash_table_insert(lrad_hash_table_t *ht, uint32_t key, void *data)
 223 {
 224         uint32_t entry;
 225         uint32_t reversed;
 226         lrad_hash_entry_t *node;
 227
 228         if (!ht || !data) return 0;
 229
 230         entry = key & (ht->num_buckets - 1);
 231         reversed = reverse(key);
 232
 233         /*
 234          *      Already in the table.
 235          */
 236         node = list_find(ht->buckets[entry], reversed);
 237         if (node) {
 238                 if (!ht->replace_flag) return 0;
 239
 240                 list_delete(&ht->buckets[entry], node);
 241
 242                 if (ht->free && node->data) ht->free(node->data);
 243
 244                 /*
 245                  *      Fall through to re-using the node.
 246                  */
 247         } else {
 248                 node = malloc(sizeof(*node) + ht->data_size);
 249                 if (!node) return 0;
 250         }
 251         memset(node, 0, sizeof(*node) + ht->data_size);
 252
 253         node->next = NULL;
 254         node->key = reversed;
 255         if (ht->data_size) {
 256                 node->data = &node[1]; /* point to the end of the node */
 257                 memcpy(node->data, data, ht->data_size);
 258         } else {
 259                 node->data = data;
 260         }
 261
 262         list_insert(&(ht->buckets[entry]), node);
 263         ht->num_elements++;
 264
 265         /*
 266          *      Check the load factor, and grow the table if
 267          *      necessary.
 268          */
 269         if (ht->num_elements >= (3 * ht->num_buckets)) {
 270                 int i;
 271                 lrad_hash_entry_t **buckets;
 272
 273                 buckets = malloc(sizeof(*buckets) * 2 * ht->num_buckets);
 274                 if (!buckets) return 1;
 275
 276                 memcpy(buckets, ht->buckets,
 277                        sizeof(*buckets) * ht->num_buckets);
 278
 279                 /*
 280                  *      Split the hash entries.
 281                  *
 282                  *      When we double the size of the hash array, we
 283                  *      do O(N/2) work.  Since this only happens after
 284                  *      we've inserted N elements,  we're still amortized
 285                  *      at O(1) inserts, deletes, and updates.
 286                  */
 287                 for (i = 0; i < ht->num_buckets; i++) {
 288                         buckets[ht->num_buckets + i] = list_split(&buckets[i],
 289                                                                   reverse((uint32_t) i + ht->num_buckets));
 290                 }
 291                 free(ht->buckets);
 292                 ht->buckets = buckets;
 293                 ht->num_buckets *= 2;
 294 #ifdef TESTING
 295                 grow = 1;
 296                 fprintf(stderr, "GROW TO %d\n", ht->num_buckets);
 297 #endif
 298         }
 299
 300         return 1;
 301 }
 302
 303
 304 /*
 305  *      Find data from a key.
 306  */
 307 void *lrad_hash_table_finddata(lrad_hash_table_t *ht, uint32_t key)
 308 {
 309         uint32_t entry;
 310         uint32_t reversed;
 311         lrad_hash_entry_t *node;
 312
 313         entry = key & (ht->num_buckets - 1);
 314         reversed = reverse(key);
 315
 316         if (!ht) return NULL;
 317
 318         node = list_find(ht->buckets[entry], reversed);
 319         if (!node) return NULL;
 320
 321         return node->data;      /* may be NULL */
 322 }
 323
 324
 325 /*
 326  *      Delete a piece of data from the hash table.
 327  */
 328 int lrad_hash_table_delete(lrad_hash_table_t *ht, uint32_t key)
 329 {
 330         uint32_t entry;
 331         uint32_t reversed;
 332         lrad_hash_entry_t *node;
 333
 334         if (!ht) return 0;
 335
 336         entry = key & (ht->num_buckets - 1);
 337         reversed = reverse(key);
 338
 339         node = list_find(ht->buckets[entry], reversed);
 340         if (!node) return 0;
 341
 342         if (ht->free) ht->free(node->data);
 343         list_delete(&ht->buckets[entry], node);
 344         ht->num_elements--;
 345
 346         free(node);
 347         return 1;
 348 }
 349
 350
 351 /*
 352  *      Free a hash table
 353  */
 354 void lrad_hash_table_free(lrad_hash_table_t *ht)
 355 {
 356         lrad_hash_entry_t *node, *next;
 357
 358         if (!ht) return;
 359
 360         /*
 361          *      The entries MUST be all in one linked list.
 362          */
 363         for (node = ht->buckets[0]; node != NULL; node = next) {
 364                 next = node->next;
 365
 366                 if (!node->data) continue; /* dummy entry */
 367
 368                 if (ht->free) ht->free(node->data);
 369                 free(node);
 370         }
 371
 372         free(ht->buckets);
 373         free(ht);
 374 }
 375
 376
 377 /*
 378  *      Count number of elements
 379  */
 380 int lrad_hash_table_num_elements(lrad_hash_table_t *ht)
 381 {
 382         if (!ht) return 0;
 383
 384         return ht->num_elements;
 385 }
 386
 387
 388 /*
 389  *      Walk over the nodes, allowing deletes & inserts to happen.
 390  */
 391 int lrad_hash_table_walk(lrad_hash_table_t *ht,
 392                          int (*callback)(void * /* ctx */,
 393                                          void * /* data */),
 394                          void *context)
 395 {
 396         int i, rcode;;
 397
 398         if (!ht || !callback) return 0;
 399
 400         for (i = 0; i < ht->num_buckets; i++) {
 401                 lrad_hash_entry_t *node, *next;
 402
 403                 if (!ht->buckets[i]) continue;
 404
 405                 for (node = ht->buckets[i]; node != NULL; node = next) {
 406                         next = node->next;
 407
 408                         rcode = callback(context, node->data);
 409                         if (rcode != 0) return rcode;
 410                 }
 411         }
 412
 413         return 0;
 414 }
 415
 416
 417 /*
 418  *      For users that have a small amount of data, and wish to associate
 419  *      it directly with the hash entry, this saves a bit of memory &
 420  *      malloc/free stuff.
 421  */
 422 int lrad_hash_table_set_data_size(lrad_hash_table_t *ht, size_t data_size)
 423 {
 424       if (!ht || ht->free) return 0;
 425
 426       if (ht->num_elements != 0) return 0;
 427
 428       ht->data_size = data_size;
 429
 430       return 1;
 431 }
 432
 433
 434 #define FNV_MAGIC_INIT (0x811c9dc5)
 435 #define FNV_MAGIC_PRIME (0x01000193)
 436
 437 /*
 438  *      A fast hash function.  For details, see:
 439  *
 440  *      http://www.isthe.com/chongo/tech/comp/fnv/
 441  *
 442  *      Which also includes public domain source.  We've re-written
 443  *      it here for our purposes.
 444  */
 445 uint32_t lrad_hash(const void *data, size_t size)
 446 {
 447         const uint8_t *p = data;
 448         const uint8_t *q = p + size;
 449         uint32_t      hash = FNV_MAGIC_INIT;
 450
 451         /*
 452          *      FNV-1 hash each octet in the buffer
 453          */
 454         while (p != q) {
 455                 /*
 456                  *      Multiple by 32-bit magic FNV prime, mod 2^32
 457                  */
 458                 hash *= FNV_MAGIC_PRIME;
 459 #if 0
 460                 /*
 461                  *      Potential optimization.
 462                  */
 463                 hash += (hash<<1) + (hash<<4) + (hash<<7) + (hash<<8) + (hash<<24);
 464 #endif
 465                 /*
 466                  *      XOR the 8-bit quantity into the bottom of
 467                  *      the hash.
 468                  */
 469                 hash ^= (uint32_t) (*p++);
 470     }
 471
 472     return hash;
 473 }
 474
 475 /*
 476  *      Continue hashing data.
 477  */
 478 uint32_t lrad_hash_update(const void *data, size_t size, uint32_t hash)
 479 {
 480         const uint8_t *p = data;
 481         const uint8_t *q = p + size;
 482
 483         while (p != q) {
 484                 hash *= FNV_MAGIC_PRIME;
 485                 hash ^= (uint32_t) (*p++);
 486     }
 487
 488     return hash;
 489
 490 }
 491
 492 /*
 493  *      Return a "folded" hash, where the lower "bits" are the
 494  *      hash, and the upper bits are zero.
 495  *
 496  *      If you need a non-power-of-two hash, cope.
 497  */
 498 uint32_t lrad_hash_fold(uint32_t hash, int bits)
 499 {
 500         int count;
 501         uint32_t result;
 502
 503         if ((bits <= 0) || (bits >= 32)) return hash;
 504
 505         result = hash;
 506
 507         /*
 508          *      Never use the same bits twice in an xor.
 509          */
 510         for (count = 0; count < 32; count += bits) {
 511                 hash >>= bits;
 512                 result ^= hash;
 513         }
 514
 515         return result & (((uint32_t) (1 << bits)) - 1);
 516 }
 517
 518
 519 #ifdef TESTING
 520 /*
 521  *  cc -DTESTING -I ../include/ hash.c -o hash
 522  *
 523  *  ./hash
 524  */
 525
 526 #include <stdio.h>
 527 #include <stdlib.h>
 528
 529 #define MAX 8000
 530 int main(int argc, char **argv)
 531 {
 532         uint32_t i, *p, *q;
 533         lrad_hash_table_t *ht;
 534
 535         ht = lrad_hash_table_create(10, free, 0);
 536         if (!ht) {
 537                 fprintf(stderr, "Hash create failed\n");
 538                 exit(1);
 539         }
 540
 541         for (i = 0; i < MAX; i++) {
 542                 p = malloc(sizeof(i));
 543                 *p = i;
 544                 if (!lrad_hash_table_insert(ht, i, p)) {
 545                         fprintf(stderr, "Failed insert %08x\n", i);
 546                         exit(1);
 547                 }
 548
 549                 if (grow) {
 550                         uint32_t j;
 551
 552                         for (j = 0; j < i; j++) {
 553                                 q = lrad_hash_table_finddata(ht, j);
 554                                 if (!q || (*q != j)) {
 555                                         fprintf(stderr, "BAD DATA %d %p\n",
 556                                                 j, q);
 557                                         exit(1);
 558                                 }
 559                         }
 560                         grow = 0;
 561                 }
 562
 563                 q = lrad_hash_table_finddata(ht, i);
 564                 if (q != p) {
 565                         fprintf(stderr, "Bad data %d\n", i);
 566                         exit(1);
 567                 }
 568         }
 569
 570         for (i = 0; i < MAX; i++) {
 571                 lrad_hash_table_delete(ht, i);
 572                 q = lrad_hash_table_finddata(ht, i);
 573                 if (q) {
 574                         fprintf(stderr, "Failed to delete %08x\n", i);
 575                         exit(1);
 576                 }
 577         }
 578
 579         lrad_hash_table_free(ht);
 580
 581         exit(0);
 582 }
 583 #endif