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

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

Significant refactor to sync with current ICXML buffer model. Report GID on start positions and scan forward support file diffs for QA

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