source: trunk/symtab/hash_table.hpp @ 3925

Last change on this file since 3925 was 1929, checked in by ksherdy, 8 years ago

Updated identity symbol table.

File size: 6.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_H
9#define HASH_TABLE_H
10
11#include "../lib/bitblock.hpp"
12#include "../lib/byte_compare.hpp"
13#include "../lib/allocator.hpp"
14#include "../lib/s2p.hpp"
15#include "../lib/byte_pool.hpp"
16#include "../lib/hash.hpp"
17#include <cmath>
18#include <stdint.h>
19#include <string>
20#include <sstream>
21#include <iostream>
22using namespace std;
23
24typedef uint32_t gid_type;
25
26typedef struct node {
27    uint8_t * raw_bytes;
28    uint32_t lgth;
29    gid_type gid;
30    node * next;
31} node;
32
33class gid {
34public:
35    static uint64_t next() { return value++; }
36private:
37    static uint64_t value;
38};
39
40/* Global GID for all hash_tables */
41uint64_t gid::value = 1;
42
43
44// TODO - Move raw_data_pool to a base class so all hash table share the same memory pool.
45
46template<class COMPARE_STRATEGY, class HASH_STRATEGY, class ALLOCATOR>
47class hash_table {
48public:
49
50    hash_table(const uint32_t pow2=1024) {
51        init(pow2);
52    }
53
54    ~hash_table() {
55        destroy();
56    }
57
58    IDISA_ALWAYS_INLINE uint64_t get_bucket(const uint8_t * h0, const uint8_t * h1, const uint32_t offset, const uint32_t lgth) {
59        return  hash_strategy.hash(h0,h1,offset,hash_size,lgth);
60    }
61
62    /* Specify a length for the default case */
63    IDISA_ALWAYS_INLINE gid_type lookup_or_insert(const uint64_t bucket, uint8_t * raw_bytes, const uint32_t lgth=0) {
64
65        node * crt = table[bucket];
66        node * prev = crt;
67
68        /* lookup */
69        while(NULL != crt) {
70
71            if(compare_strategy.compare(raw_bytes, crt->raw_bytes, lgth)) {
72                cout << "Collision" << endl;
73                return crt->gid;
74            }
75            prev = crt;
76            crt = crt->next;
77        }
78
79        /* allocate */
80        node * next = (node *) malloc(sizeof(node));
81        if (next == NULL) {
82            cerr << "Out of Memory" << endl;
83            abort();
84        }
85
86        /* set */
87        next->raw_bytes = raw_data_pool.insert(raw_bytes,lgth);
88        next->lgth = lgth;
89        next->gid = gid::next();
90        next->next = NULL;
91
92        /* tail */
93        if(prev != NULL ) {
94            prev->next = next;
95        } else {
96            table[bucket] = next;
97        }
98
99        return next->gid;
100    }
101
102    void print_table() const {
103
104        for(int i=0;i<table_size;i++) {
105
106            node * crt = table[i];
107
108            if(crt != NULL) { cout << "table[" << i << "]"; }
109
110            while(crt != NULL) {
111                cout << "->" << "(" << crt->gid << "," << string((char *)crt->raw_bytes, crt->lgth) << ")";
112                crt = crt->next;
113            }
114
115            if(crt != NULL) { cout << endl; }
116        }
117    }
118
119private:
120
121    uint32_t log2msb(uint32_t v) {
122        uint32_t r = 0;
123        while (v >>= 1) {r++;}
124        return r;
125    }
126
127    void init(const uint32_t size) {
128
129        hash_size = log2msb(size);
130
131        table_size = pow(2.0, (double)hash_size);
132
133
134        cout << "hash_size: "  << hash_size << endl;
135        cout << "table_size: " << table_size << endl;
136
137        this->table = (node**) calloc(table_size, sizeof(node*));
138        if ((this->table) == NULL) {
139                cerr << "Out of Memory" << endl;
140                abort();
141        }
142    }
143
144    void destroy() {
145/*
146        node * next = NULL;
147
148        for(int i=0;i<table_size;i++) {
149            node * crt = table[i];
150            while(crt != NULL) {
151                next = crt->next;
152                free((node *)crt);
153                crt = next;
154                next = NULL;
155            }
156        }
157        table = NULL;
158*/
159    }
160
161    node ** table;
162    uint32_t table_size;
163    uint32_t hash_size;
164
165    // hash_mask
166
167    byte_pool<ALLOCATOR> raw_data_pool;
168
169    // MAX_EXP_SIZE // (bits) // TODO
170
171    COMPARE_STRATEGY compare_strategy;
172    HASH_STRATEGY hash_strategy;
173};
174
175/* Length specialized strategy classes. Hash, Compare */
176
177/* Templated approach:
178(1) Avoids duplicate code,
179(2) Avoid vtable overhead,
180(3) Introduces coding complexity.
181*/
182
183/* Hash Strategy */
184class hash_strategy {
185public:
186    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * b0, const uint8_t * b1, const uint32_t pos, const uint32_t hash_size, const uint32_t lgth=0);
187protected:
188    hash_strategy() {}
189};
190
191template<uint32_t LGTH>
192class hash_strategy_t: public hash_strategy {
193public:
194    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * b0, const uint8_t * b1, const uint32_t pos, const uint32_t hash_size, const uint32_t lgth=0);
195};
196
197/* Specialized 'Byte' hash functions. */
198/* 1-4 */
199template<>
200class hash_strategy_t<1> {
201public:
202    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * b0, const uint8_t * b1, const uint32_t pos, const uint32_t hash_size, const uint32_t lgth=0) {
203        return b0[pos];
204    }
205};
206
207template<>
208class hash_strategy_t<2> {
209public:
210    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * b0, const uint8_t * b1, const uint32_t pos, const uint32_t hash_size, const uint32_t lgth=0) {
211        return compress_hash(b0, bytes2bits(pos), bytes2bits(2), hash_size); // expect b0 as byte stream
212    }
213};
214
215template<>
216class hash_strategy_t<3> {
217public:
218    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * b0, const uint8_t * b1, const uint32_t pos, const uint32_t hash_size, const uint32_t lgth=0) {
219        return compress_hash(b0, bytes2bits(pos), bytes2bits(3), hash_size); // expect b0 as byte stream
220    }
221};
222
223template<>
224class hash_strategy_t<4>: public hash_strategy {
225public:
226    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * b0, const uint8_t * b1, const uint32_t pos, const uint32_t hash_size, const uint32_t lgth=0) {
227        return compress_hash(b0, bytes2bits(pos), bytes2bits(4), hash_size); // expect b0 as byte stream
228    };
229};
230
231/* Specialized 'Bit' hash functions. */
232/* 5-12 */
233/*
234template<>
235class hash_strategy_t<?>: public hash_strategy {
236public:
237    static IDISA_ALWAYS_INLINE uint64_t do_hash(const uint8_t * b0, const uint8_t * b1, const uint32_t pos, const uint32_t hash_size, const uint32_t lgth=0) {
238        return ;
239    };
240};
241*/
242
243/* Default case - Hash on bits. */
244class hash_strategy_d: public hash_strategy {
245public:
246    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * b0, const uint8_t * b1, const uint32_t pos, const uint32_t hash_size, const uint32_t lgth=0) {
247        //return bit_expand_hash((uint8_t *) &b0, (uint8_t *) &b1, pos, lgth, hash_size);
248
249    return compress_hash(b0, bytes2bits(pos), bytes2bits(lgth), hash_size); // expect b0 as byte stream
250    }
251};
252
253// Compare
254class compare_strategy {
255public:
256    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0);
257protected:
258    compare_strategy() {}
259};
260
261/* Length specific comparison */
262template<class T, uint32_t LGTH>
263class identity_strategy_t: public compare_strategy {
264public:
265    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
266        return overlap_compare<T,LGTH>(x,y);
267    }
268};
269
270/* Default case */
271class identity_strategy_d: public compare_strategy {
272public:
273    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
274        return overlap_compare<BitBlock>(x,y,lgth);
275    }
276};
277
278#endif // HASH_TABLE_H
Note: See TracBrowser for help on using the repository browser.