src/hash_table.c

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