src/hash.c

   1
   2 #include "hash.h"
   3 #include "common.h"
   4 #include <stdlib.h>
   5 #include <stdint.h>
   6 #include <string.h>
   7
   8
   9 static const size_t INITIAL_TABLE_SIZE = 128;
  10 static const double MAX_LOAD = 0.75;
  11
  12
  13 /*
  14  * Paul Hsieh's SuperFastHash
  15  * http://www.azillionmonkeys.com/qed/hash.html
  16  */
  17
  18
  19 #undef get16bits
  20 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
  21     || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
  22 #define get16bits(d) (*((const uint16_t *) (d)))
  23 #endif
  24
  25 #if !defined (get16bits)
  26 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
  27         +(uint32_t)(((const uint8_t *)(d))[0]) )
  28 #endif
  29
  30 static uint32_t hash(const char * data, size_t len) {
  31     uint32_t hash = len, tmp;
  32     int rem;
  33
  34     if (len <= 0 || data == NULL) return 0;
  35
  36     rem = len & 3;
  37     len >>= 2;
  38
  39     /* Main loop */
  40     for (;len > 0; len--) {
  41         hash  += get16bits (data);
  42         tmp    = (get16bits (data+2) << 11) ^ hash;
  43         hash   = (hash << 16) ^ tmp;
  44         data  += 2*sizeof (uint16_t);
  45         hash  += hash >> 11;
  46     }
  47
  48     /* Handle end cases */
  49     switch (rem) {
  50         case 3: hash += get16bits (data);
  51                 hash ^= hash << 16;
  52                 hash ^= data[sizeof (uint16_t)] << 18;
  53                 hash += hash >> 11;
  54                 break;
  55         case 2: hash += get16bits (data);
  56                 hash ^= hash << 11;
  57                 hash += hash >> 17;
  58                 break;
  59         case 1: hash += *data;
  60                 hash ^= hash << 10;
  61                 hash += hash >> 1;
  62     }
  63
  64     /* Force "avalanching" of final 127 bits */
  65     hash ^= hash << 3;
  66     hash += hash >> 5;
  67     hash ^= hash << 4;
  68     hash += hash >> 17;
  69     hash ^= hash << 25;
  70     hash += hash >> 6;
  71
  72     return hash;
  73 }
  74
  75
  76
  77 static void rehash(hash_table* T, size_t new_n);
  78 static void clear_hash_table(hash_table*);
  79
  80
  81
  82 hash_table* create_hash_table()
  83 {
  84     hash_table* T = malloc_or_die(sizeof(hash_table));
  85     T->A = malloc_or_die(INITIAL_TABLE_SIZE * sizeof(hashed_value*));
  86     memset(T->A, 0, INITIAL_TABLE_SIZE * sizeof(hashed_value*));
  87     T->n = INITIAL_TABLE_SIZE;
  88     T->m = 0;
  89     T->max_m = T->n * MAX_LOAD;
  90
  91     return T;
  92 }
  93
  94
  95 void destroy_hash_table(hash_table* T)
  96 {
  97     if (T != NULL) {
  98         clear_hash_table(T);
  99         free(T->A);
 100         free(T);
 101     }
 102 }
 103
 104
 105
 106 void clear_hash_table(hash_table* T)
 107 {
 108     hashed_value* u;
 109     size_t i;
 110     for (i = 0; i < T->n; i++) {
 111         while (T->A[i]) {
 112             u = T->A[i]->next;
 113             free(T->A[i]->value);
 114             free(T->A[i]);
 115             T->A[i] = u;
 116         }
 117     }
 118
 119     T->m = 0;
 120 }
 121
 122
 123 static void insert_without_copy(hash_table* T, hashed_value* V)
 124 {
 125     uint32_t h = hash(V->value, V->len) % T->n;
 126     V->next = T->A[h];
 127     T->A[h] = V;
 128     T->m++;
 129 }
 130
 131
 132
 133 static void rehash(hash_table* T, size_t new_n)
 134 {
 135     hash_table U;
 136     U.n = new_n;
 137     U.m = 0;
 138     U.max_m = U.n * MAX_LOAD;
 139     U.A = malloc_or_die(U.n * sizeof(hashed_value*));
 140     memset(U.A, 0, U.n * sizeof(hashed_value*));
 141
 142     hashed_value *j, *k;
 143     size_t i;
 144     for (i = 0; i < T->n; i++) {
 145         j = T->A[i];
 146         while (j) {
 147             k = j->next;
 148             insert_without_copy(&U, j);
 149             j = k;
 150         }
 151         T->A[i] = NULL;
 152     }
 153
 154     free(T->A);
 155     T->A = U.A;
 156     T->n = U.n;
 157     T->max_m = U.max_m;
 158 }
 159
 160
 161 void inc_hash_table(hash_table* T, const char* value, size_t len)
 162 {
 163     if (T->m >= T->max_m) rehash(T, T->n * 2);
 164
 165     uint32_t h = hash(value, len) % T->n;
 166
 167     hashed_value* u = T->A[h];
 168
 169     while (u) {
 170         if (u->len == len && memcmp(u->value, value, len) == 0) {
 171             u->count++;
 172             return;
 173         }
 174
 175         u = u->next;
 176     }
 177
 178     u = malloc_or_die(sizeof(hashed_value));
 179     u->value = malloc_or_die(len);
 180     memcpy(u->value, value, len);
 181     u->len = len;
 182     u->count = 1;
 183
 184     u->next = T->A[h];
 185     T->A[h] = u;
 186
 187     T->m++;
 188 }
 189
 190
 191
 192 hashed_value** dump_hash_table(hash_table* T)
 193 {
 194     hashed_value** D = malloc_or_die(T->m * sizeof(hashed_value*));
 195
 196     hashed_value* u;
 197     size_t i, j;
 198     for (i = 0, j = 0; i < T->n; i++) {
 199         u = T->A[i];
 200         while (u) {
 201             D[j++] = u;
 202             u = u->next;
 203         }
 204     }
 205
 206     return D;
 207 }
 208
 209
 210