source: trunk/symbol_table/src/symbol_table.hpp @ 2052

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

Refactored symbol table design to support div2, log2.

File size: 13.9 KB
Line 
1/*
2 * id_symbol_table.hpp
3 * Created on: 18-December-2011
4 * Author: Ken Herdy
5 *
6 * BitBlock type arguments must adhere to the 'full-block invariant'
7 * and mask partial block with null bytes.
8 *
9 * Number of length groups must coincide with the
10 * number compiler generated length groups.
11 *
12 */
13#ifndef ID_SYMBOL_TABLE_TEMPLATE_HPP
14#define ID_SYMBOL_TABLE_TEMPLATE_HPP
15
16#include "buffer.hpp"
17#include "gid.hpp"
18#include "hash_table.hpp"
19#include "../lib/carryQ.hpp"
20#include "../lib/bitblock_iterator.hpp"
21#include "../lib/bitblock_scan.hpp"
22#include <cstdlib>
23#include <vector>
24using namespace std;
25
26#ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
27static void print_symbol_debug(gid_type gid, const uint8_t buffer [], const int32_t spos, const uint32_t epos, const uint32_t lgth) {
28        cout << "{Symbol:{";
29        cout << "GID:" << gid;
30        cout << ",Length:" << lgth;
31        cout << ",Value:'" << string((char *)&(buffer[spos]), lgth) << "'";
32        cout << ",Start:" << spos;
33        cout << ",End:" << epos;
34        cout << "}}" << endl;
35}
36#endif
37
38///////////////////////////////////////////////////////////////////////////
39// Symbol Type - do_block()
40///////////////////////////////////////////////////////////////////////////
41template<class SYMBOL, class HASH_TABLE>
42void do_block(uint32_t blk_offset,
43              HASH_TABLE & h_table,
44              BitBlock ends,
45              uint8_t buffer [], const uint32_t lgth,
46              uint8_t h0 [], uint8_t h1 [], const uint32_t h_lgth, const uint32_t h_block_size,
47              SYMBOL & symbols, GIDFactory & gid_factory, GIDData & gid_data);
48
49template<class SYMBOL, class HASH_TABLE>
50void do_block(uint32_t blk_offset,
51              HASH_TABLE & h_table,
52              BitBlock starts [], BitBlock ends [],
53              uint8_t buffer [],
54              uint8_t h0 [], uint8_t h1 [], const uint32_t h_lgth, const uint32_t h_block_size,
55              SYMBOL & symbols, GIDFactory & gid_factory, GIDData & gid_data);
56
57///////////////////////////////////////////////////////////////////////////
58// Symbol Type - Array gids.
59///////////////////////////////////////////////////////////////////////////
60
61class Symbol {
62public:
63    Symbol (uint32_t n) {
64                        init(n);
65    }
66
67    void init(uint32_t n) {
68                        gids.reserve(n);
69                        //gids_idx.reserve((n/BLOCK_SIZE) + 1);
70    }
71
72    vector<gid_type> gids;
73    //vector<BitBlock> gids_idx;   // gids index
74};
75
76
77// TODO - Refactor as a single mixed symbol table class composed of Id, Div2, Log2 hash tables.
78template<class SYMBOL, class ALLOCATOR>
79class symbol_table {
80public:
81        symbol_table()/*:hash_table_1(256)*/{}
82        ~symbol_table() {
83//      hash_table_1.print_table();
84//      hash_table_2.print_table();
85//      hash_table_3.print_table();
86//      hash_table_4.print_table();
87//      hash_table_5.print_table();
88//      hash_table_6.print_table();
89//      hash_table_7.print_table();
90//      hash_table_8.print_table();
91//      hash_table_9.print_table();
92//      hash_table_10.print_table();
93//      hash_table_11.print_table();
94//      hash_table_12.print_table();
95//      hash_table_13.print_table();
96//      hash_table_14.print_table();
97//      hash_table_15.print_table();
98//      hash_table_16.print_table();
99//      hash_table_gte_17.print_table();
100#ifdef HASH_TABLE_HPP_DEBUG
101        hash_table_1.print_diagnostics();
102        hash_table_2.print_diagnostics();
103        hash_table_3.print_diagnostics();
104        hash_table_4.print_diagnostics();
105        hash_table_5.print_diagnostics();
106        hash_table_6.print_diagnostics();
107        hash_table_7.print_diagnostics();
108        hash_table_8.print_diagnostics();
109        hash_table_9.print_diagnostics();
110        hash_table_10.print_diagnostics();
111        hash_table_11.print_diagnostics();
112        hash_table_12.print_diagnostics();
113        hash_table_13.print_diagnostics();
114        hash_table_14.print_diagnostics();
115        hash_table_15.print_diagnostics();
116        hash_table_16.print_diagnostics();
117        hash_table_gte_17.print_diagnostics();
118#endif
119        }
120
121        // Groups & groups
122        void resolve(uint8_t buffer [], Groups groups [],  BitBlock starts [], BitBlock ends_gte_17 [],
123                                 BitBlock h0 [], BitBlock h1 [], uint32_t blocks, SYMBOL & symbols) {
124
125                        for(uint32_t blk = 0; blk < blocks; blk++) {
126                                const uint32_t blk_offset = blk * BLOCKSIZE;
127                                resolve(blk_offset, &buffer[blk_offset], groups[blk], &starts[blk], &h0[blk], &h1[blk], symbols);
128                        }
129        }
130
131        // Groups & groups
132        IDISA_ALWAYS_INLINE
133        void resolve(uint32_t blk_offset, uint8_t buffer [], Groups & groups,  BitBlock starts[],
134                                 BitBlock * h0, BitBlock * h1, SYMBOL & symbols) {
135
136                        ///////////////////////////////////////////////////////////////////////////////
137                        // Byte Space Hash
138                        ///////////////////////////////////////////////////////////////////////////////
139                        #define BYTE_HASH(LGTH, TYPE) \
140                                if(bitblock::any(groups.ends_##LGTH)) { \
141                                        do_block<SYMBOL, id_hash_table <identity_strategy_t<LGTH,TYPE>, hash_strategy_t<LGTH>, ALLOCATOR> > \
142                                                (blk_offset, \
143                                                 hash_table_##LGTH, \
144                                                 groups.ends_##LGTH, \
145                                                 buffer, LGTH, /* buffer, symbol length */ \
146                                                 buffer, buffer, bytes2bits(LGTH), BLOCK_SIZE, /* h0, h1, hash lgth (bits), hash block size (bits) */ \
147                                                 symbols, this->gid_factory, this->gid_data); \
148                                }
149
150                        BYTE_HASH(1, uint8_t);
151                        BYTE_HASH(2, uint16_t);
152                        BYTE_HASH(3, uint16_t);
153                        BYTE_HASH(4, uint32_t);
154                        BYTE_HASH(5, uint32_t);
155                        BYTE_HASH(6, uint32_t);
156                        BYTE_HASH(7, uint32_t);
157
158                        #undef BYTE_HASH
159
160                        ///////////////////////////////////////////////////////////////////////////////
161                        // Bit Space Hash
162                        ///////////////////////////////////////////////////////////////////////////////
163                        #define BIT_HASH(LGTH, TYPE) \
164                                if(bitblock::any(groups.ends_##LGTH)) { \
165                                        do_block<SYMBOL, id_hash_table <identity_strategy_t<LGTH,TYPE>, hash_strategy_t<LGTH>, ALLOCATOR> > \
166                                                (blk_offset, \
167                                                 hash_table_##LGTH, \
168                                                 groups.ends_##LGTH, \
169                                                 buffer, LGTH, \
170                                                 (uint8_t *)h0, (uint8_t *)h1, LGTH, (BLOCK_SIZE / 8), \
171                                                 symbols, this->gid_factory, this->gid_data); \
172                                }
173
174                        BIT_HASH(8, uint64_t);
175                        BIT_HASH(9, uint64_t);
176                        BIT_HASH(10, uint64_t);
177                        BIT_HASH(11, uint64_t);
178                        BIT_HASH(12, uint64_t);
179                        BIT_HASH(13, uint64_t);
180                        BIT_HASH(14, uint64_t);
181                        BIT_HASH(15, uint64_t);
182                        BIT_HASH(16, BitBlock);
183
184                        #undef BIT_HASH
185
186                        if(bitblock::any(groups.ends_gte_17)) {
187                                do_block<SYMBOL, id_hash_table<identity_strategy_d, hash_strategy_d, ALLOCATOR> >
188                                                (blk_offset,
189                                                 hash_table_gte_17,
190                                                 starts, &groups.ends_gte_17,
191                                                 buffer,
192                                                 (uint8_t *)h0, (uint8_t *)h1, 17, BLOCK_SIZE/8,
193                                                 symbols, this->gid_factory, this->gid_data);
194                        }
195        }
196
197        IDISA_ALWAYS_INLINE uint8_t * get_raw_data(uint32_t idx) const { return gid_data.get_raw_bytes(idx); }
198        IDISA_ALWAYS_INLINE uint32_t get_lgth(uint32_t idx) const { return gid_data.get_bytes_lgth(idx); }
199
200private:
201
202        GIDFactory gid_factory;
203        GIDData gid_data;
204
205        ///////////////////////////////////////////////////////////////////////////////
206        // Byte Space Hash
207        ///////////////////////////////////////////////////////////////////////////////
208        id_hash_table<identity_strategy_t<1, uint8_t>, hash_strategy_t<1>, ALLOCATOR> hash_table_1;
209        id_hash_table<identity_strategy_t<2, uint16_t>, hash_strategy_t<2>, ALLOCATOR> hash_table_2;
210        id_hash_table<identity_strategy_t<3, uint16_t>, hash_strategy_t<3>, ALLOCATOR> hash_table_3;
211        id_hash_table<identity_strategy_t<4, uint32_t>, hash_strategy_t<4>, ALLOCATOR> hash_table_4;
212        id_hash_table<identity_strategy_t<5, uint32_t>, hash_strategy_t<5>, ALLOCATOR> hash_table_5;
213        id_hash_table<identity_strategy_t<6, uint32_t>, hash_strategy_t<6>, ALLOCATOR> hash_table_6;
214        id_hash_table<identity_strategy_t<7, uint32_t>, hash_strategy_t<7>, ALLOCATOR> hash_table_7;
215//      ///////////////////////////////////////////////////////////////////////////////
216//      // Bit Space Hash
217//      ///////////////////////////////////////////////////////////////////////////////
218        id_hash_table<identity_strategy_t<8, uint64_t>, hash_strategy_t<8>, ALLOCATOR> hash_table_8;
219        id_hash_table<identity_strategy_t<9, uint64_t>, hash_strategy_t<9>, ALLOCATOR> hash_table_9;
220        id_hash_table<identity_strategy_t<10, uint64_t>, hash_strategy_t<10>, ALLOCATOR> hash_table_10;
221        id_hash_table<identity_strategy_t<11, uint64_t>, hash_strategy_t<11>, ALLOCATOR> hash_table_11;
222        id_hash_table<identity_strategy_t<12, uint64_t>, hash_strategy_t<12>, ALLOCATOR> hash_table_12;
223        id_hash_table<identity_strategy_t<13, uint64_t>, hash_strategy_t<13>, ALLOCATOR> hash_table_13;
224        id_hash_table<identity_strategy_t<14, uint64_t>, hash_strategy_t<14>, ALLOCATOR> hash_table_14;
225        id_hash_table<identity_strategy_t<15, uint64_t>, hash_strategy_t<15>, ALLOCATOR> hash_table_15;
226        id_hash_table<identity_strategy_t<16, BitBlock>, hash_strategy_t<16>, ALLOCATOR> hash_table_16;
227        id_hash_table<identity_strategy_d, hash_strategy_d, ALLOCATOR> hash_table_gte_17;
228};
229
230/* NOTE: C++ template code and Pablo generated length groups must coincide. */
231
232// Fixed Lengths - REVERSE SCAN LOGIC - Scan each BLOCK MSB to LSB
233template<class SYMBOL, class HASH_TABLE>
234void do_block(uint32_t blk_offset,
235                  HASH_TABLE & h_table,
236                  BitBlock ends,
237                  uint8_t buffer [], const uint32_t lgth,
238                  uint8_t h0 [], uint8_t h1 [], const uint32_t h_lgth, const uint32_t h_block_size,
239                  SYMBOL & symbols, GIDFactory & gid_factory, GIDData & gid_data) {
240
241                uint8_t * buffer_base = buffer;
242                uint8_t * h0_base = h0;
243                uint8_t * h1_base = h1;
244
245                gid_type gid;
246                int32_t epos;
247                int32_t spos;
248                uint32_t blk_count;
249
250        ReverseScanner<BitBlock, scanword_t> rscanner(&ends);
251
252        rscanner.scan_to_next();
253        epos = rscanner.get_pos();
254
255                while(!rscanner.is_done()) {
256
257                spos = epos - lgth;
258
259                        if(spos < 0) { // boundary case
260                                        spos = (BLOCK_SIZE - (-1 * spos)) & (BLOCK_SIZE - 1);
261                                        blk_count = (lgth/BLOCK_SIZE)+1;
262                                        buffer_base -= (BLOCK_SIZE * blk_count);
263                                        h0_base -= (h_block_size * blk_count);
264                                        h1_base -= (h_block_size * blk_count);
265                        }
266
267                        assert (spos >= 0);
268
269                        gid = h_table.lookup_or_insert(buffer_base, spos, lgth, h0_base, h1_base, h_lgth, gid_factory, gid_data); // WARNING: spos must be >= 0
270
271                        #ifdef ID_SYMBOL_STORE_SYMBOL_GIDS_AT_END_POSITION
272                        symbols.gids[blk_offset + epos] = gid;
273                        #else
274                        symbols.gids[blk_offset + epos - lgth] = gid;
275                        #endif
276
277                        #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
278                                print_symbol_debug(gid, buffer_base, spos, epos, lgth);
279                        #endif
280
281                        rscanner.scan_to_next();
282                epos = rscanner.get_pos();
283                }
284        }
285
286
287// Variable Lengths, reverse scanner logic
288// Precondition: A symbol end is marked iff a symbol start is marked within a buffer segment.
289template<class SYMBOL, class HASH_TABLE>
290void do_block(uint32_t blk_offset,
291                          HASH_TABLE & h_table,
292                          BitBlock starts [], BitBlock ends [],
293                          uint8_t buffer [],
294                          uint8_t h0 [], uint8_t h1 [], const uint32_t h_lgth, const uint32_t h_block_size,
295                          SYMBOL & symbols, GIDFactory & gid_factory, GIDData & gid_data) {
296
297        BitBlock * starts_base = starts;
298        uint8_t * buffer_base = buffer;
299        uint8_t * h0_base = h0;
300        uint8_t * h1_base = h1;
301
302        gid_type gid;
303        int32_t epos;
304        int32_t spos;
305        uint32_t lgth;
306        uint32_t blk_count = 0;
307
308        ReverseScanner<BitBlock, scanword_t> ends_rscanner(ends);
309        ReverseScanner<BitBlock, scanword_t> starts_rscanner(starts);
310
311        ends_rscanner.scan_to_next();
312        epos = ends_rscanner.get_pos();
313
314        while(!ends_rscanner.is_done()) {
315
316                starts_rscanner.move_to(epos);
317                starts_rscanner.scan_to_next();
318                spos = starts_rscanner.get_pos();
319                lgth = epos - spos;
320
321                while(starts_rscanner.is_done()) { // boundary case
322                          starts_base--;
323
324                        blk_count++;
325
326                        starts_rscanner.init(starts_base);
327                        starts_rscanner.scan_to_next();
328
329                        if(!starts_rscanner.is_done()) { // found start
330                                        lgth = epos + (BLOCK_SIZE - starts_rscanner.get_pos()) + (BLOCK_SIZE * (blk_count-1));
331                                        // spos = (BLOCK_SIZE - (-1 * spos)) & (BLOCK_SIZE - 1);
332
333                                        // buffer_base -= (BLOCK_SIZE * blk_count);
334                                        //spos = epos - lgth;
335                                        spos = starts_rscanner.get_pos();
336
337                                        buffer_base -= (BLOCK_SIZE * blk_count);
338                                        h0_base -= (h_block_size * blk_count);
339                                        h1_base -= (h_block_size * blk_count);
340                                        break;
341                        }
342
343                }
344
345                gid = h_table.lookup_or_insert(buffer_base, spos, lgth, h0_base, h1_base, h_lgth, gid_factory, gid_data); // WARNING: spos must be >= 0
346
347                #ifdef ID_SYMBOL_STORE_SYMBOL_GIDS_AT_END_POSITION
348                symbols.gids[blk_offset + epos] = gid;
349                #else
350                symbols.gids[blk_offset + epos - lgth] = gid;
351                #endif
352
353                #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
354                        //print_symbol_debug(gid, buffer, spos, epos, lgth);
355                        print_symbol_debug(gid, buffer_base, spos, epos, lgth);
356                #endif
357
358                ends_rscanner.scan_to_next();
359                epos = ends_rscanner.get_pos();
360        }
361}
362
363#endif // ID_SYMBOL_TABLE_TEMPLATE_HPP
364
365//
366/*
367void do_block(uint32_t blk_offset,
368                  HASH_TABLE & h_table,
369                  BitBlock ends,
370                  uint8_t buffer [], const uint32_t lgth,
371                  uint8_t h0 [], uint8_t h1 [], const uint32_t h_lgth, const uint32_t h_block_size,
372                  SYMBOL & symbols, GIDFactory & gid_factory, GIDData & gid_data) {
373
374        gid_type gid;
375        int32_t spos;
376        int32_t epos;
377        ForwardScanner<BitBlock, scanword_t> fscanner(&ends);
378
379        fscanner.scan_to_next();
380        epos = fscanner.get_pos();
381        spos = (epos - lgth);
382
383        if(!fscanner.is_done() && (spos < 0) ) { // block boundary case
384
385        ////////////////////////////////////////////////////////////////////
386        // Start - Review boundary logic
387        ////////////////////////////////////////////////////////////////////
388        uint8_t * lb_buffer = buffer - ((lgth / BLOCK_SIZE) + 1)*BLOCK_SIZE;
389        int32_t lb_spos = (BLOCK_SIZE - (-1*spos)) & (BLOCK_SIZE-1);
390
391        uint8_t * lb_h0 = h0 - ((lgth / BLOCK_SIZE) + 1)*h_block_size;
392        uint8_t * lb_h1 = h1 - ((lgth / BLOCK_SIZE) + 1)*h_block_size;
393
394        gid = h_table.lookup_or_insert(lb_buffer, lb_spos, lgth, lb_h0, lb_h1, h_lgth, gid_factory, gid_data);
395
396        symbols.gids[blk_offset + spos] = gid;
397        ////////////////////////////////////////////////////////////////////
398        // End
399        ////////////////////////////////////////////////////////////////////
400
401        #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
402                        print_symbol_debug(gid, lb_buffer, lb_spos, epos, lgth);
403        #endif
404
405        fscanner.scan_to_next();
406        epos = fscanner.get_pos();
407        spos = (epos - lgth);
408
409        }
410
411        while(!fscanner.is_done()) {
412
413                gid = h_table.lookup_or_insert(buffer, spos, lgth, h0, h1, h_lgth, gid_factory, gid_data);
414                symbols.gids[blk_offset + spos] = gid;
415
416        #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
417                print_symbol_debug(gid, buffer, spos, epos, lgth);
418        #endif
419
420                fscanner.scan_to_next();
421                epos = fscanner.get_pos();
422                spos = (epos - lgth);
423        }
424
425}
426*/
427
Note: See TracBrowser for help on using the repository browser.