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

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

Added bit / byte strategy. Added length test to hash table.

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