source: trunk/symbol_table/src/hash_table.hpp

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

Removed problematic 'using namespace std;'

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