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

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

Added GIDFactory class member. Each symbol table maintains a set of GIDs.

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