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

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

Updated symbol table to represent group 0 as the arbitrary length group.

File size: 12.3 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, int GROUP_STRATEGY, int SCALE_FACTOR, class ALLOCATOR>
49class hash_table {
50
51public:
52    hash_table(const uint32_t table_size=4096, const uint32_t resize_chain_lgth=2) {
53        #ifdef HASH_TABLE_HPP_DEBUG
54            lookups = 0;
55            elements = 0;
56            collisions = 0;
57            table_expansions = 0;
58        #endif
59        init(table_size,resize_chain_lgth);
60    }
61
62    virtual ~hash_table() {
63        destroy_table(this->table, this->table_size);
64    }
65
66    IDISA_ALWAYS_INLINE uint64_t get_bucket(const uint8_t * h0, const uint8_t * h1, const uint32_t idx) {
67        #ifdef HASH_TABLE_HPP_DEBUG
68            lookups++;
69        #endif
70
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 void pool_and_insert(uint64_t bucket, uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
93                                                  uint8_t * h0, uint8_t * h1,
94                                                  GIDFactory & gid_factory, GIDData & gid_data, gid_type & gid) {
95
96        /* persistant data */
97        gid = gid_factory.next();
98
99        uint64_t x0 = *((uint64_t *)(h0 + (idx/8))) >> (idx & (8-1));
100        uint8_t * data_pool_x0 = this->raw_data_pool.insert((uint8_t *)&x0, bits2bytes(this->hash_strategy.max_hashsize()));
101
102        uint64_t x1 = *((uint64_t *)(h1 + (idx/8))) >> (idx & (8-1));
103        uint8_t * data_pool_x1 = this->raw_data_pool.insert((uint8_t *)&x1, bits2bytes(this->hash_strategy.max_hashsize()));
104
105        uint8_t * data_pool_raw_bytes = this->raw_data_pool.insert(&raw_bytes[idx],raw_byte_lgth);
106
107        /* insert */
108        insert( bucket,
109                data_pool_raw_bytes,
110                raw_byte_lgth,
111                data_pool_x0,
112                data_pool_x1,
113                gid);
114
115        if(this->expansion_test(this->table[bucket])) {
116            #ifdef HASH_TABLE_HPP_DEBUG
117                this->table_expansions++;
118            #endif
119            this->expand();
120        }
121
122        #ifdef HASH_TABLE_HPP_DEBUG
123            elements++;
124        #endif
125        gid_data.add_data(data_pool_raw_bytes,raw_byte_lgth);
126    }
127
128    IDISA_ALWAYS_INLINE gid_type lookup(uint64_t bucket, uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
129                                        uint8_t * h0, uint8_t * h1, gid_type & gid) {
130
131        node * crt = this->table[bucket];
132        node * prev = crt;
133
134        while(NULL != crt) {
135            if(this->compare_strategy.compare(&raw_bytes[idx], crt->raw_bytes, raw_byte_lgth)) {
136                                gid = crt->gid;
137                                return true;
138            }
139            prev = crt;
140            crt = crt->next;
141            #ifdef HASH_TABLE_HPP_DEBUG
142                this->collisions++;
143            #endif
144        }
145
146        return false;
147    }
148
149    IDISA_ALWAYS_INLINE gid_type lookup_or_insert(uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
150                                                  uint8_t * h0, uint8_t * h1,
151                                                  GIDFactory & gid_factory, GIDData & gid_data) {
152
153        gid_type gid;
154        uint64_t bucket = this->get_bucket(h0,h1,idx);
155
156        if(lookup(bucket, raw_bytes, idx, raw_byte_lgth, h0, h1, gid)) {
157            return gid;
158        }
159
160        this->pool_and_insert(bucket, raw_bytes, idx, raw_byte_lgth, h0, h1, gid_factory, gid_data, gid);
161        return gid;
162
163    }
164
165    ///////////////////////////////////////////////////////////////////////////
166    // Helpers
167    ///////////////////////////////////////////////////////////////////////////
168    protected:
169
170    uint32_t log2msb(uint32_t v) {
171        uint32_t r = 0;
172        while (v >>= 1) {r++;}
173        return r;
174    }
175
176    void init(const uint32_t size, const uint32_t chain_lgth) {
177
178        hash_size = MIN((log2msb(size)), hash_strategy.max_hashsize());
179        table_size = pow(2.0, (double)hash_size);
180        table = (node**) calloc(table_size, sizeof(node*));
181
182        if ((table) == NULL) {
183                cerr << "Out of Memory" << endl;
184                abort();
185        }
186        resize_chain_lgth = chain_lgth;
187    }
188
189    void destroy_table(node ** table, const uint32_t table_size) {
190        node * crt = NULL;
191        node * next = NULL;
192
193        for(int i=0;i<table_size;i++) {
194            crt = table[i];
195            while(crt != NULL) {
196                next = crt->next;
197                free((node  *)crt);
198                crt = next;
199            }
200        }
201
202        free((node **) table);
203        table = NULL;
204    }
205
206    uint32_t chain_lgth(const node * chain) {
207        uint32_t lgth = 0;
208        node * crt = (node *)chain;
209        while(NULL != crt) {
210            lgth++;
211            crt = crt->next;
212        }
213
214        return lgth;
215    }
216
217    bool expansion_test(const node * chain) {
218
219        if ((chain_lgth(chain) > resize_chain_lgth)
220                &&  (hash_size < hash_strategy.max_hashsize())
221                &&  (table_size < MAX_TABLE_SIZE))
222        {
223            return true;
224        }
225
226        return false;
227    }
228
229    void expand() { // naive expansion
230
231        node ** prev_table = this->table;
232        uint32_t prev_size = this->table_size;
233
234        init(table_size*2, resize_chain_lgth);
235
236        uint64_t bucket;
237        node * crt;
238
239        for(int i=0;i<prev_size;i++) {
240            crt = prev_table[i];
241
242            while(crt != NULL) {
243
244
245                bucket = this->get_bucket(crt->h0,
246                                          crt->h1,
247                                          0);
248                this->insert(bucket,
249                             crt->raw_bytes,
250                             crt->raw_bytes_lgth,
251                             crt->h0,
252                             crt->h1,
253                             crt->gid);
254
255                crt = crt->next;
256            }
257        }
258
259        destroy_table(prev_table,prev_size);
260        crt = NULL;
261
262        for(int i=0;i<table_size;i++) {
263            if(expansion_test(table[i])) {
264                expand();
265            }
266        }
267    }
268
269    ///////////////////////////////////////////////////////////////////////////
270    // Members
271    ///////////////////////////////////////////////////////////////////////////
272    uint32_t table_size;            // power of 2
273    uint32_t hash_size;             // maximum number of bits hashed on
274    uint32_t resize_chain_lgth;     // maximum chain length
275
276    node ** table;
277    byte_pool<ALLOCATOR> raw_data_pool;
278    compare_strategy_t<LGTH,GROUP_STRATEGY> compare_strategy;
279    hash_strategy_t<LGTH,GROUP_STRATEGY,SCALE_FACTOR> hash_strategy;
280
281    ///////////////////////////////////////////////////////////////////////////
282    // Debug / Diagnostics
283    ///////////////////////////////////////////////////////////////////////////
284    void print_table() const {
285
286        for(int i=0;i<table_size;i++) {
287
288            node * head = table[i];
289            node * crt = head;
290
291            if(head != NULL) { cout << "table[" << i << "]"; }
292
293            while(crt != NULL) {
294                cout << "->";
295                print_node(crt);
296                crt = crt->next;
297            }
298
299            if(head != NULL) { cout << endl; }
300        }
301    }
302
303    void print_node(node * crt) const {
304        cout    << "(GID:"      << crt->gid
305                << ",Lgth:"     << crt->raw_bytes_lgth
306                << ",Value:'"   << string((char *)&crt->raw_bytes[0], crt->raw_bytes_lgth)
307                << "')";
308    }
309
310    void print_table_distribution() const {
311
312        for(int i=0;i<table_size;i++) {
313
314            node * head = table[i];
315            node * crt = head;
316
317            if(head != NULL) { cout << "table[" << i << "]"; }
318
319            while(crt != NULL) {
320                cout << "X";
321                crt = crt->next;
322            }
323
324            if(head != NULL) { cout << endl; }
325        }
326    }
327
328    ///////////////////////////////////////////////////////////////////////////
329    // Debug Members
330    ///////////////////////////////////////////////////////////////////////////
331    #ifdef HASH_TABLE_HPP_DEBUG
332        uint32_t lookups;
333        uint32_t elements;
334        uint32_t collisions;
335        uint32_t table_expansions;
336    #endif
337
338    void print_diagnostics() const {
339        #ifdef HASH_TABLE_HPP_DEBUG
340            cout << "Table Size:"                       << table_size << endl;
341            cout << "Total Elements:"                   << elements << endl;
342            cout << "Total Lookups (with resizes):"     << lookups << endl;
343            cout << "Collisions(with resizes):"         << collisions << endl;
344            cout << "Table Expansions:"                 << table_expansions << endl;
345            cout << "Resize Chain Length:"              << resize_chain_lgth << endl;
346            cout << endl;
347        #else
348            cout << "#define HASH_TABLE_HPP_DEBUG for diagnostics." << endl;
349        #endif
350    }
351};
352
353///////////////////////////////////////////////////////////////////////////
354// id - Identity Strategy
355///////////////////////////////////////////////////////////////////////////
356template<uint32_t LGTH, int GROUP_STRATEGY, int SCALE_FACTOR, class ALLOCATOR>
357class id_hash_table : public hash_table<LGTH, GROUP_STRATEGY, SCALE_FACTOR, ALLOCATOR> {};
358
359///////////////////////////////////////////////////////////////////////////
360// div2 - Div2 Strategy
361///////////////////////////////////////////////////////////////////////////
362
363// TODO - delimeters at compile time
364static char XMLdelimiters[] = {' ', '\0', '\0', ';', '\0', '=', '>', '/'};
365static IDISA_ALWAYS_INLINE bool isXMLDelimiter(const char c) {
366    return c == XMLdelimiters[(unsigned int) c & 0x7];
367}
368
369static IDISA_ALWAYS_INLINE bool isGeneralDelimiter(const char c) {
370    return !(('A' <= c && c <= 'Z') || ('a' <= c && c <= 'z'));
371}
372
373static IDISA_ALWAYS_INLINE bool isTestDelimiter(const char c) {
374    return c == ',';
375}
376
377template<uint32_t LGTH, int GROUP_STRATEGY, int SCALE_FACTOR, class ALLOCATOR>
378class div2_hash_table : public hash_table<LGTH, GROUP_STRATEGY, SCALE_FACTOR, ALLOCATOR> {
379
380public:
381
382    IDISA_ALWAYS_INLINE gid_type lookup(uint64_t bucket, uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
383                                        uint8_t * h0, uint8_t * h1, gid_type & gid) {
384
385        node * crt = this->table[bucket];
386        node * prev = crt;
387
388        while(NULL != crt) {
389            if(this->compare_strategy.compare(&raw_bytes[idx], crt->raw_bytes, raw_byte_lgth)) {
390                                gid = crt->gid;
391                                return true;
392            }
393            prev = crt;
394            crt = crt->next;
395            #ifdef HASH_TABLE_HPP_DEBUG
396                this->collisions++;
397            #endif
398        }
399
400        return false;
401    }
402
403    IDISA_ALWAYS_INLINE gid_type lookup_or_insert(uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
404                                                  uint8_t * h0, uint8_t * h1,
405                                                  GIDFactory & gid_factory, GIDData & gid_data) {
406
407        gid_type gid;
408        uint64_t bucket = this->get_bucket(h0,h1,idx);
409        uint32_t lgth = raw_byte_lgth;
410
411        ///////////////////////////////////////////////////////////////////////////
412        // Even
413        ///////////////////////////////////////////////////////////////////////////
414        if(lookup(bucket, raw_bytes, idx, lgth, h0, h1, gid)) {
415            return gid;
416        } else {
417
418            if (!div2_hash_table::is_delimeter((char) *(raw_bytes + (idx)))) {
419                this->pool_and_insert(bucket, raw_bytes, idx, lgth, h0, h1, gid_factory, gid_data, gid);
420                return gid;
421            } else {
422                ///////////////////////////////////////////////////////////////////////////
423                // Odd
424                ///////////////////////////////////////////////////////////////////////////
425                bucket = this->hash_table_odd.get_bucket(h0,h1,idx+1);
426
427                if(this->hash_table_odd.lookup(bucket, raw_bytes, idx+1, lgth-1, h0, h1, gid)) {
428                    return gid;
429                }
430
431                hash_table_odd.pool_and_insert(bucket, raw_bytes, idx+1, lgth-1, h0, h1, gid_factory, gid_data, gid);
432                return gid;
433            }
434        }
435    }
436
437protected:
438
439    static IDISA_ALWAYS_INLINE bool is_delimeter(const char delim) {
440        return ::isTestDelimiter(delim);
441    }
442
443    id_hash_table<LGTH-1, div2, SCALE_FACTOR, ALLOCATOR> hash_table_odd;
444};
445
446///////////////////////////////////////////////////////////////////////////
447// log2 - Log base 2 Strategy
448///////////////////////////////////////////////////////////////////////////
449template<uint32_t LGTH, int GROUP_STRATEGY, int SCALE_FACTOR, class ALLOCATOR>
450class logbase2_hash_table : public hash_table<LGTH, GROUP_STRATEGY, SCALE_FACTOR, ALLOCATOR> {};
451
452///////////////////////////////////////////////////////////////////////////
453// single - Single Strategy
454///////////////////////////////////////////////////////////////////////////
455template<uint32_t LGTH, int GROUP_STRATEGY, int SCALE_FACTOR, class ALLOCATOR>
456class single_hash_table : public hash_table<LGTH, GROUP_STRATEGY, SCALE_FACTOR, ALLOCATOR> {};
457
458
459#endif // HASH_TABLE_HPP
Note: See TracBrowser for help on using the repository browser.