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

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

Added div2 support wte length greater than or equal to 17.

File size: 10.8 KB
RevLine 
[1967]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/*=============================================================================
[1986]12  hash_table.hpp - Hashing with chaining
[1967]13  Created on: 18-December-2011
14  Author: Ken Herdy
15=============================================================================*/
16
[1988]17//#define HASH_TABLE_HPP_DEBUG
[1967]18
19#define MIN(a, b) ((a < b) ? a : b)
20#define MAX(a, b) ((a > b) ? a : b)
[1991]21#define MAX_TABLE_SIZE 65536
[1967]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"
[2028]29#include "gid.hpp"
[2053]30#include "compare_strategy.hpp"
31#include "hash_strategy.hpp"
[1967]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
[2053]48template<uint32_t LGTH, class ALLOCATOR>
[1967]49class hash_table {
[2001]50
[1967]51public:
52
[2053]53    IDISA_ALWAYS_INLINE uint64_t get_bucket(const uint8_t * h0, const uint8_t * h1, const uint32_t idx) {
[2031]54                        #ifdef HASH_TABLE_HPP_DEBUG
55                                        lookups++;
56                        #endif
[2053]57                        return hash_strategy.hash(h0,h1,idx,this->hash_strategy.max_hashsize(),this->hash_size);
[1967]58    }
59
[2053]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) {
[1967]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
[2054]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) {
[1967]81
[2054]82        /* persistant data */
83        gid = gid_factory.next();
[1967]84
[2054]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()));
[1967]87
[2054]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()));
[1967]90
[2054]91        uint8_t * data_pool_raw_bytes = this->raw_data_pool.insert(&raw_bytes[idx],raw_byte_lgth);
[1967]92
[2054]93        /* insert */
94        insert( bucket,
95                data_pool_raw_bytes,
96                raw_byte_lgth,
97                data_pool_x0,
98                data_pool_x1,
99                gid);
[1967]100
[2054]101        if(this->expansion_test(this->table[bucket])) {
102            #ifdef HASH_TABLE_HPP_DEBUG
103                this->table_expansions++;
104            #endif
105            this->expand();
[1967]106        }
107
[2054]108        #ifdef HASH_TABLE_HPP_DEBUG
109            elements++;
110        #endif
111        gid_data.add_data(data_pool_raw_bytes,raw_byte_lgth);
[1986]112    }
113
[2054]114    protected:
[1986]115
[2054]116    hash_table(const uint32_t table_size=1024, const uint32_t resize_chain_lgth=2) {
[1986]117        #ifdef HASH_TABLE_HPP_DEBUG
[2054]118            lookups = 0;
119            elements = 0;
120            collisions = 0;
121            table_expansions = 0;
[1986]122        #endif
[2054]123        init(table_size,resize_chain_lgth);
[1986]124    }
125
[2054]126    virtual ~hash_table() {
127        destroy_table(this->table, this->table_size);
[1988]128    }
129
[2054]130    ///////////////////////////////////////////////////////////////////////////
131    // Helpers
132    ///////////////////////////////////////////////////////////////////////////
[1967]133    uint32_t log2msb(uint32_t v) {
134        uint32_t r = 0;
135        while (v >>= 1) {r++;}
136        return r;
137    }
138
[1988]139    void init(const uint32_t size, const uint32_t chain_lgth) {
[1967]140
[2040]141        hash_size = MIN((log2msb(size)), hash_strategy.max_hashsize());
[1967]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        }
[1988]149        resize_chain_lgth = chain_lgth;
[1967]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++;
[1986]174            crt = crt->next;
[1967]175        }
[1988]176
[1967]177        return lgth;
178    }
179
180    bool expansion_test(const node * chain) {
181
[1986]182        if ((chain_lgth(chain) > resize_chain_lgth)
183                &&  (hash_size < hash_strategy.max_hashsize())
184                &&  (table_size < MAX_TABLE_SIZE))
185        {
[1967]186            return true;
187        }
[1988]188
[1967]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
[1986]197        init(table_size*2, resize_chain_lgth);
[1967]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) {
[2040]206
207
[1967]208                bucket = this->get_bucket(crt->h0,
209                                          crt->h1,
[2053]210                                          0);
[1967]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        }
[2052]230    }
[2054]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    }
[2052]314};
[2040]315
[2053]316template<uint32_t LGTH, class ALLOCATOR>
317class id_hash_table : public hash_table<LGTH, ALLOCATOR> {
[2052]318
319public:
320
[2054]321    IDISA_ALWAYS_INLINE gid_type lookup(uint64_t bucket, uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
322                                        uint8_t * h0, uint8_t * h1, gid_type & gid) {
323
324        node * crt = this->table[bucket];
325        node * prev = crt;
326
327        while(NULL != crt) {
328            if(this->compare_strategy.compare(&raw_bytes[idx], crt->raw_bytes, raw_byte_lgth)) {
329                                gid = crt->gid;
330                                return true;
331            }
332            prev = crt;
333            crt = crt->next;
334            #ifdef HASH_TABLE_HPP_DEBUG
335                collisions++;
336            #endif
337        }
338
339        return false;
340    }
341
[2052]342    IDISA_ALWAYS_INLINE gid_type lookup_or_insert(uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
[2053]343                                                  uint8_t * h0, uint8_t * h1,
344                                                  GIDFactory & gid_factory, GIDData & gid_data) {
[2052]345
[2054]346        gid_type gid;
[2053]347        uint64_t bucket = this->get_bucket(h0,h1,idx);
[2052]348
[2054]349        if(lookup(bucket, raw_bytes, idx, raw_byte_lgth, h0, h1, gid)) {
350            return gid;
351        }
352
353        this->pool_and_insert(bucket, raw_bytes, idx, raw_byte_lgth, h0, h1, gid_factory, gid_data, gid);
354        return gid;
355
356    }
357
358};
359
360template<uint32_t LGTH, class ALLOCATOR>
361class div2_hash_table : public hash_table<LGTH, ALLOCATOR> {
362
363public:
364
365    IDISA_ALWAYS_INLINE gid_type lookup(uint64_t bucket, uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
366                                        uint8_t * h0, uint8_t * h1, gid_type & gid) {
367
[2052]368        node * crt = this->table[bucket];
369        node * prev = crt;
370
371        while(NULL != crt) {
372            if(this->compare_strategy.compare(&raw_bytes[idx], crt->raw_bytes, raw_byte_lgth)) {
[2054]373                                gid = crt->gid;
374                                return true;
[2052]375            }
376            prev = crt;
377            crt = crt->next;
378            #ifdef HASH_TABLE_HPP_DEBUG
[2054]379                collisions++;
[2052]380            #endif
381        }
382
[2054]383        return false;
384    }
[2052]385
[2054]386    IDISA_ALWAYS_INLINE gid_type lookup_or_insert(uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
387                                                  uint8_t * h0, uint8_t * h1,
388                                                  GIDFactory & gid_factory, GIDData & gid_data) {
[2052]389
[2054]390        gid_type gid;
391        uint64_t bucket = this->get_bucket(h0,h1,idx);
392        uint32_t lgth = raw_byte_lgth;
[2052]393
[2054]394        uint32_t index_of_last = idx + lgth - 1;
[2052]395
[2054]396        ///////////////////////////////////////////////////////////////////////////
397        // Even
398        ///////////////////////////////////////////////////////////////////////////
399/*      if (!div2_hash_table::is_delimeter(raw_bytes, index_of_last)) {
[2052]400
[2054]401            if(lookup(bucket, raw_bytes, idx, lgth, h0, h1, gid)) {
402                return gid;
403            }
[2052]404
[2054]405            this->pool_and_insert(bucket, raw_bytes, idx, lgth, h0, h1, gid_factory, gid_data, gid);
406            return gid;
[2052]407
[2054]408        } else*/ {
[1967]409
[2054]410        ///////////////////////////////////////////////////////////////////////////
411        // Odd
412        ///////////////////////////////////////////////////////////////////////////
413            ///lgth--;
[1967]414
[2054]415            if(this->hash_table_odd.lookup(bucket, raw_bytes, idx, lgth-1, h0, h1, gid)) {
416                return gid;
417            }
[1967]418
[2054]419            hash_table_odd.pool_and_insert(bucket, raw_bytes, idx, lgth-1, h0, h1, gid_factory, gid_data, gid);
420            return gid;
421        }
[1967]422
[2054]423    }
[1967]424
[2054]425protected:
[1967]426
[2054]427    // TODO - Compile in delimeter set.
428    static IDISA_ALWAYS_INLINE bool is_delimeter(uint8_t * raw_bytes, const uint32_t idx) {
429        bool has_delim = *(raw_bytes + idx) == ',';
430        return has_delim;
431    }
[1967]432
[2054]433    id_hash_table<LGTH-1, ALLOCATOR> hash_table_odd;
[1967]434};
435
[2053]436template<uint32_t LGTH, class ALLOCATOR>
437class log2_hash_table : public hash_table<LGTH, ALLOCATOR> {
[1967]438
439public:
440
441
442};
443
444
445#endif // HASH_TABLE_HPP
Note: See TracBrowser for help on using the repository browser.