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

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

Added static is_delimeter routines.

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