[1967] | 1 | /* |
---|
| 2 | * Created on: 18-December-2011 |
---|
| 3 | * Author: Ken Herdy |
---|
| 4 | * |
---|
| 5 | * Length partitioned parallel bit stream hashing with chaining. |
---|
| 6 | * |
---|
| 7 | */ |
---|
| 8 | #ifndef HASH_TABLE_HPP |
---|
| 9 | #define HASH_TABLE_HPP |
---|
| 10 | |
---|
| 11 | /*============================================================================= |
---|
[1986] | 12 | hash_table.hpp - Hashing with chaining |
---|
[1967] | 13 | Created on: 18-December-2011 |
---|
| 14 | Author: Ken Herdy |
---|
| 15 | =============================================================================*/ |
---|
| 16 | |
---|
[1988] | 17 | //#define HASH_TABLE_HPP_DEBUG |
---|
[1967] | 18 | |
---|
| 19 | #define MIN(a, b) ((a < b) ? a : b) |
---|
| 20 | #define MAX(a, b) ((a > b) ? a : b) |
---|
[1991] | 21 | #define MAX_TABLE_SIZE 65536 |
---|
[1989] | 22 | #define MAX_HASH_BITS 17 |
---|
[1967] | 23 | |
---|
| 24 | #include "../lib/bitblock.hpp" |
---|
| 25 | #include "../lib/byte_compare.hpp" |
---|
| 26 | #include "../lib/allocator.hpp" |
---|
| 27 | #include "../lib/s2p.hpp" |
---|
| 28 | #include "../lib/byte_pool.hpp" |
---|
| 29 | #include "../lib/hash.hpp" |
---|
[2028] | 30 | #include "gid.hpp" |
---|
[1967] | 31 | #include <cmath> |
---|
| 32 | #include <stdint.h> |
---|
| 33 | #include <string> |
---|
| 34 | #include <sstream> |
---|
| 35 | #include <iostream> |
---|
| 36 | using namespace std; |
---|
| 37 | |
---|
| 38 | typedef struct node { |
---|
| 39 | uint8_t * raw_bytes; |
---|
| 40 | uint32_t raw_bytes_lgth; |
---|
| 41 | uint8_t * h0; |
---|
| 42 | uint8_t * h1; |
---|
| 43 | uint32_t hash_bit_lgth; |
---|
| 44 | gid_type gid; |
---|
| 45 | node * next; |
---|
| 46 | } node; |
---|
| 47 | |
---|
| 48 | template<class COMPARE_STRATEGY, class HASH_STRATEGY, class ALLOCATOR> |
---|
| 49 | class hash_table { |
---|
[2001] | 50 | |
---|
[1967] | 51 | public: |
---|
| 52 | |
---|
[2040] | 53 | hash_table(const uint32_t table_size=1024, const uint32_t resize_chain_lgth=2) { |
---|
[1986] | 54 | #ifdef HASH_TABLE_HPP_DEBUG |
---|
| 55 | lookups = 0; |
---|
| 56 | elements = 0; |
---|
| 57 | collisions = 0; |
---|
| 58 | table_expansions = 0; |
---|
| 59 | #endif |
---|
[2040] | 60 | init(table_size,resize_chain_lgth); |
---|
[1967] | 61 | } |
---|
| 62 | |
---|
| 63 | virtual ~hash_table() { |
---|
| 64 | destroy_table(this->table, this->table_size); |
---|
| 65 | } |
---|
| 66 | |
---|
| 67 | IDISA_ALWAYS_INLINE uint64_t get_bucket(const uint8_t * h0, const uint8_t * h1, const uint32_t idx, const uint32_t slice_bits) { |
---|
[2031] | 68 | #ifdef HASH_TABLE_HPP_DEBUG |
---|
| 69 | lookups++; |
---|
| 70 | #endif |
---|
| 71 | return hash_strategy.hash(h0,h1,idx,slice_bits,hash_size); |
---|
[1967] | 72 | } |
---|
| 73 | |
---|
| 74 | IDISA_ALWAYS_INLINE void insert(const uint64_t bucket, uint8_t * raw_bytes, uint32_t raw_byte_lgth, uint8_t * h0, uint8_t * h1, uint32_t hash_bit_lgth, gid_type gid) { |
---|
| 75 | |
---|
| 76 | node * next = (node *) malloc(sizeof(node)); |
---|
| 77 | if (next == NULL) { |
---|
| 78 | cerr << "Out of Memory" << endl; |
---|
| 79 | abort(); |
---|
| 80 | } |
---|
| 81 | |
---|
| 82 | next->raw_bytes = raw_bytes; |
---|
| 83 | next->raw_bytes_lgth = raw_byte_lgth; |
---|
| 84 | next->h0 = h0; |
---|
| 85 | next->h1 = h1; |
---|
| 86 | next->hash_bit_lgth = hash_bit_lgth; |
---|
| 87 | next->gid = gid; |
---|
| 88 | |
---|
| 89 | next->next = table[bucket]; |
---|
| 90 | table[bucket] = next; |
---|
| 91 | } |
---|
| 92 | |
---|
[1992] | 93 | IDISA_ALWAYS_INLINE gid_type lookup_or_insert(uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth, |
---|
[2028] | 94 | uint8_t * h0, uint8_t * h1, const uint32_t hash_bit_lgth, |
---|
| 95 | GIDFactory & gid_factory, GIDData & gid_data) { |
---|
[1967] | 96 | |
---|
| 97 | uint64_t bucket = get_bucket(h0,h1,idx,hash_bit_lgth); |
---|
| 98 | |
---|
| 99 | node * crt = table[bucket]; |
---|
| 100 | node * prev = crt; |
---|
| 101 | |
---|
| 102 | /* lookup */ |
---|
| 103 | while(NULL != crt) { |
---|
| 104 | if(compare_strategy.compare(&raw_bytes[idx], crt->raw_bytes, raw_byte_lgth)) { |
---|
[2031] | 105 | return crt->gid; |
---|
[1967] | 106 | } |
---|
| 107 | prev = crt; |
---|
| 108 | crt = crt->next; |
---|
[1986] | 109 | #ifdef HASH_TABLE_HPP_DEBUG |
---|
[2031] | 110 | collisions++; |
---|
[1986] | 111 | #endif |
---|
[1967] | 112 | } |
---|
| 113 | |
---|
[1992] | 114 | /* insert */ |
---|
[2027] | 115 | gid_type gid = gid_factory.next(); |
---|
[1967] | 116 | |
---|
| 117 | uint64_t x0 = bit_slice(h0, idx, hash_bit_lgth); |
---|
| 118 | uint64_t x1 = bit_slice(h1, idx, hash_bit_lgth); |
---|
| 119 | |
---|
[2001] | 120 | uint8_t * data_pool_raw_bytes = raw_data_pool.insert(&raw_bytes[idx],raw_byte_lgth); // persist |
---|
| 121 | |
---|
[1967] | 122 | insert( bucket, |
---|
[2001] | 123 | data_pool_raw_bytes, |
---|
[1967] | 124 | raw_byte_lgth, |
---|
| 125 | raw_data_pool.insert((uint8_t *)&x0, bits2bytes(hash_bit_lgth)), |
---|
| 126 | raw_data_pool.insert((uint8_t *)&x1, bits2bytes(hash_bit_lgth)), |
---|
| 127 | hash_bit_lgth, |
---|
| 128 | gid); |
---|
| 129 | |
---|
| 130 | if(expansion_test(table[bucket])) { |
---|
[1986] | 131 | |
---|
| 132 | #ifdef HASH_TABLE_HPP_DEBUG |
---|
| 133 | this->table_expansions++; |
---|
| 134 | #endif |
---|
| 135 | |
---|
[2040] | 136 | expand(); |
---|
[1967] | 137 | } |
---|
[1986] | 138 | |
---|
| 139 | #ifdef HASH_TABLE_HPP_DEBUG |
---|
| 140 | elements++; |
---|
| 141 | #endif |
---|
| 142 | |
---|
[2028] | 143 | gid_data.add_data(data_pool_raw_bytes,raw_byte_lgth); |
---|
[2001] | 144 | |
---|
[1992] | 145 | return gid; |
---|
[1967] | 146 | } |
---|
| 147 | |
---|
| 148 | void print_table() const { |
---|
| 149 | |
---|
| 150 | for(int i=0;i<table_size;i++) { |
---|
| 151 | |
---|
| 152 | node * head = table[i]; |
---|
| 153 | node * crt = head; |
---|
| 154 | |
---|
| 155 | if(head != NULL) { cout << "table[" << i << "]"; } |
---|
| 156 | |
---|
| 157 | while(crt != NULL) { |
---|
[1986] | 158 | cout << "->"; |
---|
| 159 | print_node(crt); |
---|
[1967] | 160 | crt = crt->next; |
---|
| 161 | } |
---|
| 162 | |
---|
| 163 | if(head != NULL) { cout << endl; } |
---|
| 164 | } |
---|
| 165 | } |
---|
| 166 | |
---|
[1986] | 167 | void print_node(node * crt) const { |
---|
| 168 | cout << "(GID:" << crt->gid |
---|
| 169 | << ",Lgth:" << crt->raw_bytes_lgth |
---|
| 170 | << ",Value:'" << string((char *)&crt->raw_bytes[0], crt->raw_bytes_lgth) |
---|
| 171 | << "')"; |
---|
| 172 | } |
---|
| 173 | |
---|
| 174 | |
---|
| 175 | void print_diagnostics() const { |
---|
| 176 | #ifdef HASH_TABLE_HPP_DEBUG |
---|
| 177 | cout << "Table Size:" << table_size << endl; |
---|
| 178 | cout << "Total Elements:" << elements << endl; |
---|
| 179 | cout << "Total Lookups (with resizes):" << lookups << endl; |
---|
| 180 | cout << "Collisions(with resizes):" << collisions << endl; |
---|
| 181 | cout << "Table Expansions:" << table_expansions << endl; |
---|
| 182 | cout << "Resize Chain Length:" << resize_chain_lgth << endl; |
---|
| 183 | cout << endl; |
---|
| 184 | #else |
---|
[1988] | 185 | cout << "#define HASH_TABLE_HPP_DEBUG for diagnostics." << endl; |
---|
[1986] | 186 | #endif |
---|
| 187 | } |
---|
| 188 | |
---|
[1988] | 189 | |
---|
| 190 | void print_table_distribution() const { |
---|
| 191 | |
---|
| 192 | for(int i=0;i<table_size;i++) { |
---|
| 193 | |
---|
| 194 | node * head = table[i]; |
---|
| 195 | node * crt = head; |
---|
| 196 | |
---|
| 197 | if(head != NULL) { cout << "table[" << i << "]"; } |
---|
| 198 | |
---|
| 199 | while(crt != NULL) { |
---|
| 200 | cout << "X"; |
---|
| 201 | crt = crt->next; |
---|
| 202 | } |
---|
| 203 | |
---|
| 204 | if(head != NULL) { cout << endl; } |
---|
| 205 | } |
---|
| 206 | } |
---|
| 207 | |
---|
[1967] | 208 | private: |
---|
| 209 | // ----- Members ----- |
---|
[1986] | 210 | uint32_t table_size; // power of 2 |
---|
| 211 | uint32_t hash_size; // maximum number of bits hashed on |
---|
[2040] | 212 | uint32_t resize_chain_lgth; // maximum chain length |
---|
[1967] | 213 | |
---|
| 214 | node ** table; |
---|
| 215 | // uint32_t elements; |
---|
| 216 | byte_pool<ALLOCATOR> raw_data_pool; |
---|
| 217 | COMPARE_STRATEGY compare_strategy; |
---|
| 218 | HASH_STRATEGY hash_strategy; |
---|
| 219 | |
---|
[1986] | 220 | // ----- Diagnostics ----- |
---|
| 221 | #ifdef HASH_TABLE_HPP_DEBUG |
---|
| 222 | uint32_t lookups; |
---|
| 223 | uint32_t elements; |
---|
| 224 | uint32_t collisions; |
---|
| 225 | uint32_t table_expansions; |
---|
| 226 | #endif |
---|
| 227 | |
---|
[1967] | 228 | // ----- Helpers ----- |
---|
| 229 | uint32_t log2msb(uint32_t v) { |
---|
| 230 | uint32_t r = 0; |
---|
| 231 | while (v >>= 1) {r++;} |
---|
| 232 | return r; |
---|
| 233 | } |
---|
| 234 | |
---|
[1988] | 235 | void init(const uint32_t size, const uint32_t chain_lgth) { |
---|
[1967] | 236 | |
---|
[2040] | 237 | hash_size = MIN((log2msb(size)), hash_strategy.max_hashsize()); |
---|
[1967] | 238 | table_size = pow(2.0, (double)hash_size); |
---|
| 239 | table = (node**) calloc(table_size, sizeof(node*)); |
---|
| 240 | |
---|
| 241 | if ((table) == NULL) { |
---|
| 242 | cerr << "Out of Memory" << endl; |
---|
| 243 | abort(); |
---|
| 244 | } |
---|
[1988] | 245 | resize_chain_lgth = chain_lgth; |
---|
[1967] | 246 | } |
---|
| 247 | |
---|
| 248 | void destroy_table(node ** table, const uint32_t table_size) { |
---|
| 249 | node * crt = NULL; |
---|
| 250 | node * next = NULL; |
---|
| 251 | |
---|
| 252 | for(int i=0;i<table_size;i++) { |
---|
| 253 | crt = table[i]; |
---|
| 254 | while(crt != NULL) { |
---|
| 255 | next = crt->next; |
---|
| 256 | free((node *)crt); |
---|
| 257 | crt = next; |
---|
| 258 | } |
---|
| 259 | } |
---|
| 260 | |
---|
| 261 | free((node **) table); |
---|
| 262 | table = NULL; |
---|
| 263 | } |
---|
| 264 | |
---|
| 265 | uint32_t chain_lgth(const node * chain) { |
---|
| 266 | uint32_t lgth = 0; |
---|
| 267 | node * crt = (node *)chain; |
---|
| 268 | while(NULL != crt) { |
---|
| 269 | lgth++; |
---|
[1986] | 270 | crt = crt->next; |
---|
[1967] | 271 | } |
---|
[1988] | 272 | |
---|
[1967] | 273 | return lgth; |
---|
| 274 | } |
---|
| 275 | |
---|
| 276 | bool expansion_test(const node * chain) { |
---|
| 277 | |
---|
[1986] | 278 | if ((chain_lgth(chain) > resize_chain_lgth) |
---|
| 279 | && (hash_size < hash_strategy.max_hashsize()) |
---|
| 280 | && (table_size < MAX_TABLE_SIZE)) |
---|
| 281 | { |
---|
[1967] | 282 | return true; |
---|
| 283 | } |
---|
[1988] | 284 | |
---|
[1967] | 285 | return false; |
---|
| 286 | } |
---|
| 287 | |
---|
| 288 | void expand() { // naive expansion |
---|
| 289 | |
---|
| 290 | node ** prev_table = this->table; |
---|
| 291 | uint32_t prev_size = this->table_size; |
---|
| 292 | |
---|
[1986] | 293 | init(table_size*2, resize_chain_lgth); |
---|
[1967] | 294 | |
---|
| 295 | uint64_t bucket; |
---|
| 296 | node * crt; |
---|
| 297 | |
---|
| 298 | for(int i=0;i<prev_size;i++) { |
---|
| 299 | crt = prev_table[i]; |
---|
| 300 | |
---|
| 301 | while(crt != NULL) { |
---|
[2040] | 302 | |
---|
| 303 | |
---|
[1967] | 304 | bucket = this->get_bucket(crt->h0, |
---|
| 305 | crt->h1, |
---|
| 306 | 0, |
---|
| 307 | crt->hash_bit_lgth); |
---|
| 308 | this->insert(bucket, |
---|
| 309 | crt->raw_bytes, |
---|
| 310 | crt->raw_bytes_lgth, |
---|
| 311 | crt->h0, |
---|
| 312 | crt->h1, |
---|
[2040] | 313 | crt->hash_bit_lgth, |
---|
[1967] | 314 | crt->gid); |
---|
| 315 | |
---|
| 316 | crt = crt->next; |
---|
| 317 | } |
---|
| 318 | } |
---|
| 319 | |
---|
| 320 | destroy_table(prev_table,prev_size); |
---|
| 321 | crt = NULL; |
---|
| 322 | |
---|
| 323 | for(int i=0;i<table_size;i++) { |
---|
| 324 | if(expansion_test(table[i])) { |
---|
| 325 | expand(); |
---|
| 326 | } |
---|
| 327 | } |
---|
[2040] | 328 | |
---|
[1967] | 329 | } |
---|
| 330 | |
---|
| 331 | }; |
---|
| 332 | |
---|
| 333 | /* Length specialized strategy classes. Hash, Compare */ |
---|
| 334 | |
---|
[1986] | 335 | /* Templated approach: (i) avoids duplicate code, (ii) avoids vtable overhead, (iii) introduces coding complexity.*/ |
---|
[1967] | 336 | |
---|
| 337 | /* Hash Strategy */ |
---|
| 338 | class hash_strategy { |
---|
| 339 | public: |
---|
| 340 | static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits); |
---|
| 341 | static IDISA_ALWAYS_INLINE uint32_t max_hashsize(); |
---|
| 342 | protected: |
---|
| 343 | hash_strategy() {} |
---|
| 344 | }; |
---|
| 345 | |
---|
[1986] | 346 | /* Hash functions specialized on symbol length. */ |
---|
[1967] | 347 | template<uint32_t LGTH> |
---|
| 348 | class hash_strategy_t: public hash_strategy { |
---|
| 349 | public: |
---|
| 350 | static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits); |
---|
| 351 | static IDISA_ALWAYS_INLINE uint32_t max_hashsize(); |
---|
| 352 | }; |
---|
| 353 | |
---|
| 354 | template<> class hash_strategy_t<1> { |
---|
| 355 | public: |
---|
| 356 | static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) { |
---|
| 357 | return h0[idx]; |
---|
| 358 | } |
---|
| 359 | static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(1); } |
---|
| 360 | }; |
---|
| 361 | |
---|
| 362 | template<> class hash_strategy_t<2> { |
---|
| 363 | public: |
---|
| 364 | static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) { |
---|
[1986] | 365 | return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits); |
---|
[1967] | 366 | } |
---|
| 367 | static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(2); } |
---|
| 368 | }; |
---|
| 369 | |
---|
| 370 | template<> class hash_strategy_t<3> { |
---|
| 371 | public: |
---|
| 372 | static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) { |
---|
| 373 | return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits); |
---|
| 374 | } |
---|
| 375 | static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(3); } |
---|
| 376 | }; |
---|
| 377 | |
---|
| 378 | template<> class hash_strategy_t<4>: public hash_strategy { |
---|
| 379 | public: |
---|
| 380 | static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) { |
---|
| 381 | return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits); |
---|
| 382 | }; |
---|
| 383 | static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(4); } |
---|
| 384 | }; |
---|
| 385 | |
---|
| 386 | template<> class hash_strategy_t<5>: public hash_strategy { |
---|
| 387 | public: |
---|
| 388 | static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) { |
---|
| 389 | return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits); |
---|
| 390 | }; |
---|
| 391 | static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(5); } |
---|
| 392 | }; |
---|
| 393 | |
---|
| 394 | template<> class hash_strategy_t<6>: public hash_strategy { |
---|
| 395 | public: |
---|
| 396 | static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) { |
---|
| 397 | return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits); |
---|
| 398 | }; |
---|
| 399 | static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(6); } |
---|
| 400 | }; |
---|
| 401 | |
---|
| 402 | template<> class hash_strategy_t<7>: public hash_strategy { |
---|
| 403 | public: |
---|
| 404 | static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) { |
---|
| 405 | return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits); |
---|
| 406 | }; |
---|
| 407 | static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(7); } |
---|
| 408 | }; |
---|
| 409 | |
---|
| 410 | template<> class hash_strategy_t<8>: public hash_strategy { |
---|
| 411 | public: |
---|
| 412 | static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) { |
---|
| 413 | return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits); |
---|
| 414 | }; |
---|
| 415 | static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 8; } |
---|
| 416 | }; |
---|
| 417 | |
---|
[1988] | 418 | template<> class hash_strategy_t<9>: public hash_strategy { |
---|
| 419 | public: |
---|
| 420 | static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) { |
---|
| 421 | return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits); |
---|
| 422 | }; |
---|
| 423 | static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 9; } |
---|
| 424 | }; |
---|
| 425 | |
---|
| 426 | template<> class hash_strategy_t<10>: public hash_strategy { |
---|
| 427 | public: |
---|
| 428 | static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) { |
---|
| 429 | return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits); |
---|
| 430 | }; |
---|
| 431 | static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 10; } |
---|
| 432 | }; |
---|
| 433 | |
---|
| 434 | template<> class hash_strategy_t<11>: public hash_strategy { |
---|
| 435 | public: |
---|
| 436 | static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) { |
---|
| 437 | return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits); |
---|
| 438 | }; |
---|
| 439 | static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 11; } |
---|
| 440 | }; |
---|
| 441 | |
---|
| 442 | template<> class hash_strategy_t<12>: public hash_strategy { |
---|
| 443 | public: |
---|
| 444 | static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) { |
---|
| 445 | return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits); |
---|
| 446 | }; |
---|
| 447 | static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 12; } |
---|
| 448 | }; |
---|
| 449 | |
---|
| 450 | template<> class hash_strategy_t<13>: public hash_strategy { |
---|
| 451 | public: |
---|
| 452 | static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) { |
---|
| 453 | return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits); |
---|
| 454 | }; |
---|
| 455 | static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 13; } |
---|
| 456 | }; |
---|
| 457 | |
---|
| 458 | template<> class hash_strategy_t<14>: public hash_strategy { |
---|
| 459 | public: |
---|
| 460 | static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) { |
---|
| 461 | return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits); |
---|
| 462 | }; |
---|
| 463 | static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 14; } |
---|
| 464 | }; |
---|
| 465 | |
---|
| 466 | template<> class hash_strategy_t<15>: public hash_strategy { |
---|
| 467 | public: |
---|
| 468 | static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) { |
---|
| 469 | return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits); |
---|
| 470 | }; |
---|
| 471 | static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 15; } |
---|
| 472 | }; |
---|
| 473 | |
---|
| 474 | template<> class hash_strategy_t<16>: public hash_strategy { |
---|
| 475 | public: |
---|
| 476 | static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) { |
---|
| 477 | return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits); |
---|
| 478 | }; |
---|
| 479 | static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 16; } |
---|
| 480 | }; |
---|
| 481 | |
---|
[1967] | 482 | /* Default */ |
---|
| 483 | class hash_strategy_d: public hash_strategy { |
---|
| 484 | public: |
---|
| 485 | static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) { |
---|
| 486 | return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits); // expect h0 as hash bit stream |
---|
| 487 | } |
---|
[1988] | 488 | static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return MAX_HASH_BITS; } |
---|
[1967] | 489 | }; |
---|
| 490 | |
---|
| 491 | /* Compare Strategy */ |
---|
| 492 | class compare_strategy { |
---|
| 493 | public: |
---|
| 494 | static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0); |
---|
| 495 | protected: |
---|
| 496 | compare_strategy() {} |
---|
| 497 | }; |
---|
| 498 | |
---|
| 499 | /* Length specific comparison */ |
---|
[2045] | 500 | template<uint32_t LGTH, class TYPE> |
---|
[1967] | 501 | class identity_strategy_t: public compare_strategy { |
---|
| 502 | public: |
---|
| 503 | static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) { |
---|
[2045] | 504 | return overlap_compare<LGTH, TYPE>(x,y); |
---|
[1967] | 505 | } |
---|
| 506 | }; |
---|
| 507 | |
---|
| 508 | /* Default */ |
---|
| 509 | class identity_strategy_d: public compare_strategy { |
---|
| 510 | public: |
---|
| 511 | static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) { |
---|
| 512 | return mem_compare(x,y,lgth); |
---|
| 513 | } |
---|
| 514 | }; |
---|
| 515 | |
---|
| 516 | #endif // HASH_TABLE_HPP |
---|