source: trunk/symbol_table/src/hash_table.hpp @ 2045

Last change on this file since 2045 was 2045, checked in by ksherdy, 7 years ago

Revered TYPE and LGTH template parameters.

File size: 15.0 KB
Line 
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/*=============================================================================
12  hash_table.hpp - Hashing with chaining
13  Created on: 18-December-2011
14  Author: Ken Herdy
15=============================================================================*/
16
17//#define HASH_TABLE_HPP_DEBUG
18
19#define MIN(a, b) ((a < b) ? a : b)
20#define MAX(a, b) ((a > b) ? a : b)
21#define MAX_TABLE_SIZE 65536
22#define MAX_HASH_BITS 17   
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"
30#include "gid.hpp"
31#include <cmath>
32#include <stdint.h>
33#include <string>
34#include <sstream>
35#include <iostream>
36using namespace std;
37
38typedef 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
48template<class COMPARE_STRATEGY, class HASH_STRATEGY, class ALLOCATOR>
49class hash_table {
50
51public:
52
53    hash_table(const uint32_t table_size=1024, const uint32_t resize_chain_lgth=2) {
54        #ifdef HASH_TABLE_HPP_DEBUG
55            lookups = 0;
56            elements = 0;
57            collisions = 0;
58            table_expansions = 0;
59        #endif
60        init(table_size,resize_chain_lgth);
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) {
68                        #ifdef HASH_TABLE_HPP_DEBUG
69                                        lookups++;
70                        #endif
71                        return hash_strategy.hash(h0,h1,idx,slice_bits,hash_size);
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
93    IDISA_ALWAYS_INLINE gid_type lookup_or_insert(uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
94                                                  uint8_t * h0, uint8_t * h1, const uint32_t hash_bit_lgth, 
95                                                        GIDFactory & gid_factory, GIDData & gid_data) {
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)) {
105                                return crt->gid;
106            }
107            prev = crt;
108            crt = crt->next;
109            #ifdef HASH_TABLE_HPP_DEBUG
110                                collisions++;
111            #endif
112        }
113
114        /* insert */
115        gid_type gid = gid_factory.next();
116
117        uint64_t x0 = bit_slice(h0, idx, hash_bit_lgth);
118        uint64_t x1 = bit_slice(h1, idx, hash_bit_lgth);
119
120        uint8_t * data_pool_raw_bytes = raw_data_pool.insert(&raw_bytes[idx],raw_byte_lgth); // persist
121
122        insert( bucket,
123                data_pool_raw_bytes,
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])) {
131
132            #ifdef HASH_TABLE_HPP_DEBUG
133                this->table_expansions++;
134            #endif
135
136             expand();
137        }
138
139        #ifdef HASH_TABLE_HPP_DEBUG
140            elements++;
141        #endif
142
143        gid_data.add_data(data_pool_raw_bytes,raw_byte_lgth);
144
145        return gid;
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) {
158                cout << "->";
159                print_node(crt);
160                crt = crt->next;
161            }
162
163            if(head != NULL) { cout << endl; }
164        }
165    }
166
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
185            cout << "#define HASH_TABLE_HPP_DEBUG for diagnostics." << endl;
186        #endif
187    }
188
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
208private:
209    // ----- Members -----
210    uint32_t table_size;            // power of 2
211    uint32_t hash_size;             // maximum number of bits hashed on
212    uint32_t resize_chain_lgth; // maximum chain length
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
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
228    // ----- Helpers -----
229    uint32_t log2msb(uint32_t v) {
230        uint32_t r = 0;
231        while (v >>= 1) {r++;}
232        return r;
233    }
234
235    void init(const uint32_t size, const uint32_t chain_lgth) {
236
237        hash_size = MIN((log2msb(size)), hash_strategy.max_hashsize());
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        }
245        resize_chain_lgth = chain_lgth;
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++;
270            crt = crt->next;
271        }
272
273        return lgth;
274    }
275
276    bool expansion_test(const node * chain) {
277
278        if ((chain_lgth(chain) > resize_chain_lgth)
279                &&  (hash_size < hash_strategy.max_hashsize())
280                &&  (table_size < MAX_TABLE_SIZE))
281        {
282            return true;
283        }
284
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
293        init(table_size*2, resize_chain_lgth);
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) {
302
303
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,
313                                 crt->hash_bit_lgth,
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        }
328
329    }
330
331};
332
333/* Length specialized strategy classes. Hash, Compare */
334
335/* Templated approach: (i) avoids duplicate code, (ii) avoids vtable overhead, (iii) introduces coding complexity.*/
336
337/* Hash Strategy */
338class hash_strategy {
339public:
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();
342protected:
343    hash_strategy() {}
344};
345
346/* Hash functions specialized on symbol length. */
347template<uint32_t LGTH>
348class hash_strategy_t: public hash_strategy {
349public:
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
354template<> class hash_strategy_t<1> {
355public:
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
362template<> class hash_strategy_t<2> {
363public:
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) {
365        return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
366    }
367    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(2); }
368};
369
370template<> class hash_strategy_t<3> {
371public:
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
378template<> class hash_strategy_t<4>: public hash_strategy {
379public:
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
386template<> class hash_strategy_t<5>: public hash_strategy {
387public:
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
394template<> class hash_strategy_t<6>: public hash_strategy {
395public:
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
402template<> class hash_strategy_t<7>: public hash_strategy {
403public:
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
410template<> class hash_strategy_t<8>: public hash_strategy {
411public:
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
418template<> class hash_strategy_t<9>: public hash_strategy {
419public:
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
426template<> class hash_strategy_t<10>: public hash_strategy {
427public:
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
434template<> class hash_strategy_t<11>: public hash_strategy {
435public:
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
442template<> class hash_strategy_t<12>: public hash_strategy {
443public:
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
450template<> class hash_strategy_t<13>: public hash_strategy {
451public:
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
458template<> class hash_strategy_t<14>: public hash_strategy {
459public:
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
466template<> class hash_strategy_t<15>: public hash_strategy {
467public:
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
474template<> class hash_strategy_t<16>: public hash_strategy {
475public:
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
482/* Default */
483class hash_strategy_d: public hash_strategy {
484public:
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    }
488    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return MAX_HASH_BITS; }
489};
490
491/* Compare Strategy */
492class compare_strategy {
493public:
494    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0);
495protected:
496    compare_strategy() {}
497};
498
499/* Length specific comparison */
500template<uint32_t LGTH, class TYPE>
501class identity_strategy_t: public compare_strategy {
502public:
503    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
504        return overlap_compare<LGTH, TYPE>(x,y);
505    }
506};
507
508/* Default */
509class identity_strategy_d: public compare_strategy {
510public:
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
Note: See TracBrowser for help on using the repository browser.