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

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

Set up log2 Makefile, Macro, derived class...

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