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

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

Specialized on LGTH.

File size: 7.8 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
23#include "../lib/bitblock.hpp"
24#include "../lib/byte_compare.hpp"
25#include "../lib/allocator.hpp"
26#include "../lib/s2p.hpp"
27#include "../lib/byte_pool.hpp"
28#include "../lib/hash.hpp"
29#include "gid.hpp"
30#include "compare_strategy.hpp"
31#include "hash_strategy.hpp"
32#include <cmath>
33#include <stdint.h>
34#include <string>
35#include <sstream>
36#include <iostream>
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    gid_type gid;
45    node * next;
46} node;
47
48template<uint32_t LGTH, 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) {
68                        #ifdef HASH_TABLE_HPP_DEBUG
69                                        lookups++;
70                        #endif
71                        return hash_strategy.hash(h0,h1,idx,this->hash_strategy.max_hashsize(),this->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, 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->gid = gid;
87
88        next->next = table[bucket];
89        table[bucket] = next;
90    }
91
92//    IDISA_ALWAYS_INLINE gid_type lookup_or_insert(uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
93//                                                uint8_t * h0, uint8_t * h1, const uint32_t hash_bit_lgth,
94//                                                      GIDFactory & gid_factory, GIDData & gid_data);
95
96    void print_table() const {
97
98        for(int i=0;i<table_size;i++) {
99
100            node * head = table[i];
101            node * crt = head;
102
103            if(head != NULL) { cout << "table[" << i << "]"; }
104
105            while(crt != NULL) {
106                cout << "->";
107                print_node(crt);
108                crt = crt->next;
109            }
110
111            if(head != NULL) { cout << endl; }
112        }
113    }
114
115    void print_node(node * crt) const {
116        cout    << "(GID:"      << crt->gid
117                << ",Lgth:"     << crt->raw_bytes_lgth
118                << ",Value:'"   << string((char *)&crt->raw_bytes[0], crt->raw_bytes_lgth)
119                << "')";
120    }
121
122
123    void print_diagnostics() const {
124        #ifdef HASH_TABLE_HPP_DEBUG
125            cout << "Table Size:"                       << table_size << endl;
126            cout << "Total Elements:"                   << elements << endl;
127            cout << "Total Lookups (with resizes):"     << lookups << endl;
128            cout << "Collisions(with resizes):"         << collisions << endl;
129            cout << "Table Expansions:"                 << table_expansions << endl;
130            cout << "Resize Chain Length:"              << resize_chain_lgth << endl;
131            cout << endl;
132        #else
133            cout << "#define HASH_TABLE_HPP_DEBUG for diagnostics." << endl;
134        #endif
135    }
136
137
138    void print_table_distribution() const {
139
140        for(int i=0;i<table_size;i++) {
141
142            node * head = table[i];
143            node * crt = head;
144
145            if(head != NULL) { cout << "table[" << i << "]"; }
146
147            while(crt != NULL) {
148                cout << "X";
149                crt = crt->next;
150            }
151
152            if(head != NULL) { cout << endl; }
153        }
154    }
155
156protected:
157    // ----- Members -----
158    uint32_t table_size;            // power of 2
159    uint32_t hash_size;             // maximum number of bits hashed on
160    uint32_t resize_chain_lgth;     // maximum chain length
161
162    node ** table;
163    // uint32_t elements;
164    byte_pool<ALLOCATOR> raw_data_pool;
165    compare_strategy_t<LGTH> compare_strategy;
166    hash_strategy_t<LGTH> hash_strategy;
167
168    // ----- Diagnostics -----
169    #ifdef HASH_TABLE_HPP_DEBUG
170        uint32_t lookups;
171        uint32_t elements;
172        uint32_t collisions;
173        uint32_t table_expansions;
174    #endif
175
176    // ----- Helpers -----
177    uint32_t log2msb(uint32_t v) {
178        uint32_t r = 0;
179        while (v >>= 1) {r++;}
180        return r;
181    }
182
183    void init(const uint32_t size, const uint32_t chain_lgth) {
184
185        hash_size = MIN((log2msb(size)), hash_strategy.max_hashsize());
186        table_size = pow(2.0, (double)hash_size);
187        table = (node**) calloc(table_size, sizeof(node*));
188
189        if ((table) == NULL) {
190                cerr << "Out of Memory" << endl;
191                abort();
192        }
193        resize_chain_lgth = chain_lgth;
194    }
195
196    void destroy_table(node ** table, const uint32_t table_size) {
197        node * crt = NULL;
198        node * next = NULL;
199
200        for(int i=0;i<table_size;i++) {
201            crt = table[i];
202            while(crt != NULL) {
203                next = crt->next;
204                free((node  *)crt);
205                crt = next;
206            }
207        }
208
209        free((node **) table);
210        table = NULL;
211    }
212
213    uint32_t chain_lgth(const node * chain) {
214        uint32_t lgth = 0;
215        node * crt = (node *)chain;
216        while(NULL != crt) {
217            lgth++;
218            crt = crt->next;
219        }
220
221        return lgth;
222    }
223
224    bool expansion_test(const node * chain) {
225
226        if ((chain_lgth(chain) > resize_chain_lgth)
227                &&  (hash_size < hash_strategy.max_hashsize())
228                &&  (table_size < MAX_TABLE_SIZE))
229        {
230            return true;
231        }
232
233        return false;
234    }
235
236    void expand() { // naive expansion
237
238        node ** prev_table = this->table;
239        uint32_t prev_size = this->table_size;
240
241        init(table_size*2, resize_chain_lgth);
242
243        uint64_t bucket;
244        node * crt;
245
246        for(int i=0;i<prev_size;i++) {
247            crt = prev_table[i];
248
249            while(crt != NULL) {
250
251
252                bucket = this->get_bucket(crt->h0,
253                                          crt->h1,
254                                          0);
255                this->insert(bucket,
256                             crt->raw_bytes,
257                             crt->raw_bytes_lgth,
258                             crt->h0,
259                             crt->h1,
260                             crt->gid);
261
262                crt = crt->next;
263            }
264        }
265
266        destroy_table(prev_table,prev_size);
267        crt = NULL;
268
269        for(int i=0;i<table_size;i++) {
270            if(expansion_test(table[i])) {
271                expand();
272            }
273        }
274    }
275};
276
277template<uint32_t LGTH, class ALLOCATOR>
278class id_hash_table : public hash_table<LGTH, ALLOCATOR> {
279
280public:
281
282    IDISA_ALWAYS_INLINE gid_type lookup_or_insert(uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
283                                                  uint8_t * h0, uint8_t * h1,
284                                                  GIDFactory & gid_factory, GIDData & gid_data) {
285
286        /* lookup */ // returns gid
287        uint64_t bucket = this->get_bucket(h0,h1,idx);
288
289        node * crt = this->table[bucket];
290        node * prev = crt;
291
292        while(NULL != crt) {
293            if(this->compare_strategy.compare(&raw_bytes[idx], crt->raw_bytes, raw_byte_lgth)) {
294                                return crt->gid;
295            }
296            prev = crt;
297            crt = crt->next;
298            #ifdef HASH_TABLE_HPP_DEBUG
299                                collisions++;
300            #endif
301        }
302
303        gid_type gid = gid_factory.next();
304        uint64_t x0 = bit_slice(h0, idx, 1); // get pointer to bit position, TODO opt for bit/byte variants
305        uint64_t x1 = bit_slice(h1, idx, 1);
306        uint8_t * data_pool_raw_bytes = this->raw_data_pool.insert(&raw_bytes[idx],raw_byte_lgth); // persist
307
308        /* insert */
309        insert( bucket,
310                data_pool_raw_bytes,
311                raw_byte_lgth,
312                this->raw_data_pool.insert((uint8_t *)&x0, bits2bytes(this->hash_strategy.max_hashsize())), // TODO opt for bit/byte variants
313                this->raw_data_pool.insert((uint8_t *)&x1, bits2bytes(this->hash_strategy.max_hashsize())),
314                gid);
315
316        if(this->expansion_test(this->table[bucket])) {
317
318            #ifdef HASH_TABLE_HPP_DEBUG
319                this->table_expansions++;
320            #endif
321
322            this->expand();
323        }
324
325        #ifdef HASH_TABLE_HPP_DEBUG
326            elements++;
327        #endif
328
329        gid_data.add_data(data_pool_raw_bytes,raw_byte_lgth);
330
331        return gid;
332    }
333
334};
335
336template<uint32_t LGTH, class ALLOCATOR>
337class div2_hash_table : public hash_table<LGTH, ALLOCATOR> {
338
339public:
340
341
342
343
344};
345
346template<uint32_t LGTH, class ALLOCATOR>
347class log2_hash_table : public hash_table<LGTH, ALLOCATOR> {
348
349public:
350
351
352};
353
354
355#endif // HASH_TABLE_HPP
Note: See TracBrowser for help on using the repository browser.