source: trunk/symbol_table/src/id_symbol_table.hpp @ 2045

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

Revered TYPE and LGTH template parameters.

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