mega-sena/mod_cuckoo.c

   1 #include <stdio.h>
   2 #include <string.h>
   3 #include <stdlib.h>
   4
   5 #include "module.h"
   6 #include "mod_cuckoo.h"
   7
   8 struct cuckoo_array {
   9         void **array;
  10         unsigned int size;
  11 };
  12
  13 struct cuckoo_tbl {
  14         int size;
  15         unsigned int positions;
  16         struct cuckoo_array first, second;
  17 };
  18
  19 static struct cuckoo_tbl cuckoo_tbl;
  20
  21 #define HASH_TABLE_SIZE  3072          /* 3k */
  22 #define LOTTERY_MAX         6          /* bytes */
  23 #define NAME_LENGTH        17          /* bytes */
  24
  25 static inline unsigned int tdb_hash(char *name)
  26 {
  27         unsigned value; /* Used to compute the hash value.  */
  28         unsigned   i;   /* Used to cycle through random values. */
  29
  30         /* Set the initial value from the key size. */
  31         for (value = 0x238F13AF * strlen(name), i=0; name[i]; i++)
  32                 value = (value + (((unsigned char *)name)[i] << (i*5 % 24)));
  33
  34         return (1103515243 * value + 12345);
  35 }
  36
  37 static inline unsigned int joaat_hash(char *name)
  38 {
  39         int i;
  40         unsigned int hash = 0;
  41
  42         for (i = 0; i < (int) strlen(name); i++) {
  43                 hash += name[i];
  44                 hash += (hash << 10);
  45                 hash ^= (hash >> 6);
  46         }
  47
  48         hash += (hash << 3);
  49         hash ^= (hash >> 11);
  50         hash += (hash << 15);
  51
  52         return hash;
  53 }
  54
  55 static void cuckoo_print_stats(void)
  56 {
  57         struct cuckoo_tbl *tbl = &cuckoo_tbl;
  58
  59         printf("\n-> Hash table statistics\n");
  60         printf("First table size:  %4d\n", tbl->positions);
  61         printf(" o in use:         %4d\n", tbl->first.size);
  62         printf(" o free:           %4d\n", tbl->positions - tbl->first.size);
  63         printf("Second table size: %4d\n", tbl->positions);
  64         printf(" o in use:         %4d\n", tbl->second.size);
  65         printf(" o free:           %4d\n", tbl->positions - tbl->second.size);
  66         printf("\n");
  67 }
  68
  69 static int cuckoo_lookup(char *name, unsigned int *h)
  70 {
  71         unsigned int hash;
  72
  73         hash = tdb_hash(name) % cuckoo_tbl.positions;
  74         if (cuckoo_tbl.first.array[hash] == NULL)
  75                 return 0;
  76
  77         if (!memcmp(cuckoo_tbl.first.array[hash], name, NAME_LENGTH))
  78                 goto found;
  79
  80         hash = joaat_hash(name) % cuckoo_tbl.positions;
  81         if (cuckoo_tbl.second.array[hash] == NULL)
  82                 return 0;
  83
  84         if (!memcmp(cuckoo_tbl.second.array[hash], name, NAME_LENGTH))
  85                 goto found;
  86
  87         return 0;
  88
  89 found:
  90         if (h)
  91                 *h = hash;
  92         return 1;
  93 }
  94
  95 static int cuckoo_insert(char *name)
  96 {
  97         int ret;
  98         void *el, *tmp;
  99         unsigned int i, hash;
 100
 101         ret = cuckoo_lookup(name, NULL);
 102         if (ret) {
 103                 /* key already exists */
 104                 return 1;
 105         }
 106
 107         el = (void *) name;
 108
 109         for (i = 0; i < cuckoo_tbl.positions; i++) {
 110
 111                 hash = tdb_hash(el) % cuckoo_tbl.positions;
 112                 if (cuckoo_tbl.first.array[hash] == NULL) {
 113                         cuckoo_tbl.first.array[hash] = el;
 114                         cuckoo_tbl.first.size++;
 115                         goto out;
 116                 }
 117
 118                 tmp = cuckoo_tbl.first.array[hash];
 119                 cuckoo_tbl.first.array[hash] = el;
 120                 el = tmp;
 121
 122                 hash = joaat_hash(el) % cuckoo_tbl.positions;
 123                 if (cuckoo_tbl.second.array[hash] == NULL) {
 124                         cuckoo_tbl.second.array[hash] = el;
 125                         cuckoo_tbl.second.size++;
 126                         goto out;
 127                 }
 128
 129                 tmp = cuckoo_tbl.second.array[hash];
 130                 cuckoo_tbl.second.array[hash] = el;
 131                 el = tmp;
 132         }
 133
 134         fprintf(stderr, "Out of Max loop, aborting\n");
 135         abort();
 136
 137 out:
 138         cuckoo_tbl.size++;
 139         return 0;
 140 }
 141
 142 #if 0
 143 static struct cuckoo_tbl *rehash(struct cuckoo_tbl *tbl)
 144 {
 145         int err;
 146         unsigned int i;
 147         struct cuckoo_tbl *new_table;
 148
 149         new_table = malloc(sizeof(struct cuckoo_tbl));
 150         if (!new_table)
 151                 return NULL;
 152
 153         err = cuckoo_init(new_table, tbl->positions * 2);
 154         if (err)
 155                 goto out_err;
 156
 157         for (i = 0; i < tbl->positions; i++) {
 158                 if (tbl->first.array[i]) {
 159                         err = cuckoo_insert(new_table,
 160                                             tbl->first.array[i]);
 161                         if (err)
 162                                 goto out_err;
 163                 }
 164
 165                 if (tbl->second.array[i]) {
 166                         err = cuckoo_insert(new_table,
 167                                             tbl->second.array[i]);
 168                         if (err)
 169                                 goto out_err;
 170                 }
 171         }
 172
 173         cuckoo_destroy(tbl);
 174         free(tbl);
 175
 176         return new_table;
 177
 178 out_err:
 179         free(new_table);
 180         return NULL;
 181 }
 182 #endif
 183
 184 static int cuckoo_init(void)
 185 {
 186         int i;
 187         const int positions = HASH_TABLE_SIZE;
 188
 189         cuckoo_tbl.first.array = malloc(sizeof(void *) * positions);
 190         if (!cuckoo_tbl.first.array)
 191                 return -1;
 192
 193         cuckoo_tbl.second.array = malloc(sizeof(void *) * positions);
 194         if (!cuckoo_tbl.second.array) {
 195                 free(cuckoo_tbl.first.array);
 196                 return -1;
 197         }
 198
 199         for (i = 0; i < positions; i++)
 200                 cuckoo_tbl.first.array[i] = cuckoo_tbl.second.array[i] = NULL;
 201
 202         cuckoo_tbl.positions = positions;
 203         cuckoo_tbl.size = cuckoo_tbl.first.size = cuckoo_tbl.second.size = 0;
 204
 205         return 0;
 206 }
 207
 208 static void cuckoo_destroy(void)
 209 {
 210         unsigned int i;
 211
 212         for (i = 0; i < cuckoo_tbl.positions; i++) {
 213                 if (cuckoo_tbl.first.array[i])
 214                         free(cuckoo_tbl.first.array[i]);
 215
 216                 if (cuckoo_tbl.second.array[i])
 217                         free(cuckoo_tbl.second.array[i]);
 218         }
 219
 220         free(cuckoo_tbl.first.array);
 221         free(cuckoo_tbl.second.array);
 222 }
 223
 224 struct module cuckoo_module = {
 225         .mod_name    = "Cuckoo hashing",
 226         .mod_init    = cuckoo_init,
 227         .mod_insert  = cuckoo_insert,
 228         .mod_lookup  = cuckoo_lookup,
 229         .mod_destroy = cuckoo_destroy,
 230         .mod_stats   = cuckoo_print_stats,
 231 };