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

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

Refactored symbol table design to support div2, log2.

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