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

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

Simplified/refactored block boundary case.

File size: 14.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 "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 load_factor=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,load_factor);
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
283            return true;
284        }
285
286        return false;
287    }
288
289    void expand() { // naive expansion
290
291        node ** prev_table = this->table;
292        uint32_t prev_size = this->table_size;
293
294        init(table_size*2, resize_chain_lgth);
295
296        uint64_t bucket;
297        node * crt;
298
299        for(int i=0;i<prev_size;i++) {
300            crt = prev_table[i];
301
302            while(crt != NULL) {
303                bucket = this->get_bucket(crt->h0,
304                                          crt->h1,
305                                          0,
306                                          crt->hash_bit_lgth);
307                this->insert(bucket,
308                             crt->raw_bytes,
309                             crt->raw_bytes_lgth,
310                             crt->h0,
311                             crt->h1,
312                             crt->hash_bit_lgth,
313                             crt->gid);
314
315                crt = crt->next;
316            }
317        }
318
319        destroy_table(prev_table,prev_size);
320        crt = NULL;
321
322        for(int i=0;i<table_size;i++) {
323            if(expansion_test(table[i])) {
324                expand();
325            }
326        }
327    }
328
329};
330
331/* Length specialized strategy classes. Hash, Compare */
332
333/* Templated approach: (i) avoids duplicate code, (ii) avoids vtable overhead, (iii) introduces coding complexity.*/
334
335/* Hash Strategy */
336class hash_strategy {
337public:
338    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);
339    static IDISA_ALWAYS_INLINE uint32_t max_hashsize();
340protected:
341    hash_strategy() {}
342};
343
344/* Hash functions specialized on symbol length. */
345template<uint32_t LGTH>
346class hash_strategy_t: public hash_strategy {
347public:
348    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);
349    static IDISA_ALWAYS_INLINE uint32_t max_hashsize();
350};
351
352template<> class hash_strategy_t<1> {
353public:
354    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) {
355        return h0[idx];
356    }
357    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(1); }
358};
359
360template<> class hash_strategy_t<2> {
361public:
362    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) {
363        return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
364    }
365    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(2); }
366};
367
368template<> class hash_strategy_t<3> {
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        return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
372    }
373    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(3); }
374};
375
376template<> class hash_strategy_t<4>: public hash_strategy {
377public:
378    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) {
379        return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
380    };
381    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(4); }
382};
383
384template<> class hash_strategy_t<5>: public hash_strategy {
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 bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
388    };
389    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(5); }
390};
391
392template<> class hash_strategy_t<6>: public hash_strategy {
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(6); }
398};
399
400template<> class hash_strategy_t<7>: public hash_strategy {
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(7); }
406};
407
408template<> class hash_strategy_t<8>: 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, idx, slice_bits, hash_bits);
412    };
413    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 8; }
414};
415
416template<> class hash_strategy_t<9>: 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, idx, slice_bits, hash_bits);
420    };
421    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 9; }
422};
423
424template<> class hash_strategy_t<10>: 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, idx, slice_bits, hash_bits);
428    };
429    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 10; }
430};
431
432template<> class hash_strategy_t<11>: 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, idx, slice_bits, hash_bits);
436    };
437    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 11; }
438};
439
440template<> class hash_strategy_t<12>: 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 12; }
446};
447
448template<> class hash_strategy_t<13>: 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 13; }
454};
455
456template<> class hash_strategy_t<14>: 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 14; }
462};
463
464template<> class hash_strategy_t<15>: 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 15; }
470};
471
472template<> class hash_strategy_t<16>: 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 16; }
478};
479
480/* Default */
481class hash_strategy_d: public hash_strategy {
482public:
483    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) {
484        return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits); // expect h0 as hash bit stream
485    }
486    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return MAX_HASH_BITS; }
487};
488
489/* Compare Strategy */
490class compare_strategy {
491public:
492    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0);
493protected:
494    compare_strategy() {}
495};
496
497/* Length specific comparison */
498template<class T, uint32_t LGTH>
499class identity_strategy_t: public compare_strategy {
500public:
501    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
502        return overlap_compare<T,LGTH>(x,y);
503    }
504};
505
506/* Default */
507class identity_strategy_d: public compare_strategy {
508public:
509    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
510        return mem_compare(x,y,lgth);
511    }
512};
513
514#endif // HASH_TABLE_HPP
Note: See TracBrowser for help on using the repository browser.