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

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

Fixed table resize.

File size: 12.5 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 "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
23#ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
24static void print_symbol_debug(gid_type gid, const uint8_t buffer [], const int32_t spos, const uint32_t epos, const uint32_t lgth) {
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;
32}
33#endif
34
35// TODO - Refactor as a single mixed symbol table class composed of Id, Div2, Log2 hash tables.
36template<class SYMBOL, class ALLOCATOR>
37class id_symbol_table: public symbol_table<SYMBOL> {
38public:
39        id_symbol_table()/*:hash_table_1(256)*/{}
40        ~id_symbol_table() {
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();
57//      hash_table_gte_17.print_table();
58#ifdef HASH_TABLE_HPP_DEBUG
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();
76#endif
77        }
78
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) {
82
83                        for(uint32_t blk = 0; blk < blocks; blk++) {
84                                const uint32_t blk_offset = blk * BLOCKSIZE;
85                                resolve(blk_offset, &buffer[blk_offset], groups[blk], &starts[blk], &h0[blk], &h1[blk], symbols);
86                        }
87        }
88
89        // Groups & groups
90        IDISA_ALWAYS_INLINE
91        void resolve(uint32_t blk_offset, uint8_t buffer [], Groups & groups,  BitBlock starts[],
92                                 BitBlock * h0, BitBlock * h1, SYMBOL & symbols) {
93
94                        ///////////////////////////////////////////////////////////////////////////////
95                        // Byte Space Hash
96                        ///////////////////////////////////////////////////////////////////////////////
97                        #define BYTE_HASH(LENGTH_GROUP, COMPARISON_TYPE) \
98                                if(bitblock::any(groups.ends_##LENGTH_GROUP)) { \
99                                        do_block<SYMBOL, hash_table <identity_strategy_t<COMPARISON_TYPE,LENGTH_GROUP>, hash_strategy_t<LENGTH_GROUP>, ALLOCATOR> > \
100                                                (blk_offset, \
101                                                 hash_table_##LENGTH_GROUP, \
102                                                 groups.ends_##LENGTH_GROUP, \
103                                                 buffer, LENGTH_GROUP, /* buffer, symbol length */ \
104                                                 buffer, buffer, bytes2bits(LENGTH_GROUP), BLOCK_SIZE, /* h0, h1, hash lgth (bits), hash block size (bits) */ \
105                                                 symbols, this->gid_factory, this->gid_data); \
106                                }
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                        ///////////////////////////////////////////////////////////////////////////////
121                        #define BIT_HASH(LENGTH_GROUP, COMPARISON_TYPE) \
122                                if(bitblock::any(groups.ends_##LENGTH_GROUP)) { \
123                                        do_block<SYMBOL, hash_table <identity_strategy_t<COMPARISON_TYPE, LENGTH_GROUP>, hash_strategy_t<LENGTH_GROUP>, ALLOCATOR> > \
124                                                (blk_offset, \
125                                                 hash_table_##LENGTH_GROUP, \
126                                                 groups.ends_##LENGTH_GROUP, \
127                                                 buffer, LENGTH_GROUP, \
128                                                 (uint8_t *)h0, (uint8_t *)h1, LENGTH_GROUP, (BLOCK_SIZE / 8), \
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
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,
148                                                 starts, &groups.ends_gte_17,
149                                                 buffer,
150                                                 (uint8_t *)h0, (uint8_t *)h1, 17, BLOCK_SIZE/8,
151                                                 symbols, this->gid_factory, this->gid_data);
152                        }
153        }
154
155private:
156        ///////////////////////////////////////////////////////////////////////////////
157        // Byte Space Hash
158        ///////////////////////////////////////////////////////////////////////////////
159        hash_table<identity_strategy_t<uint8_t,1>, hash_strategy_t<1>, ALLOCATOR> hash_table_1;
160        hash_table<identity_strategy_t<uint16_t,2>, hash_strategy_t<2>, ALLOCATOR> hash_table_2;
161        hash_table<identity_strategy_t<uint16_t,3>, hash_strategy_t<3>, ALLOCATOR> hash_table_3;
162        hash_table<identity_strategy_t<uint32_t,4>, hash_strategy_t<4>, ALLOCATOR> hash_table_4;
163        hash_table<identity_strategy_t<uint32_t,5>, hash_strategy_t<5>, ALLOCATOR> hash_table_5;
164        hash_table<identity_strategy_t<uint32_t,6>, hash_strategy_t<6>, ALLOCATOR> hash_table_6;
165        hash_table<identity_strategy_t<uint32_t,7>, hash_strategy_t<7>, ALLOCATOR> hash_table_7;
166        ///////////////////////////////////////////////////////////////////////////////
167        // Bit Space Hash
168        ///////////////////////////////////////////////////////////////////////////////
169        hash_table<identity_strategy_t<uint64_t,8>, hash_strategy_t<8>, ALLOCATOR> hash_table_8;
170        hash_table<identity_strategy_t<uint64_t,9>, hash_strategy_t<9>, ALLOCATOR> hash_table_9;
171        hash_table<identity_strategy_t<uint64_t,10>, hash_strategy_t<10>, ALLOCATOR> hash_table_10;
172        hash_table<identity_strategy_t<uint64_t,11>, hash_strategy_t<11>, ALLOCATOR> hash_table_11;
173        hash_table<identity_strategy_t<uint64_t,12>, hash_strategy_t<12>, ALLOCATOR> hash_table_12;
174        hash_table<identity_strategy_t<uint64_t,13>, hash_strategy_t<13>, ALLOCATOR> hash_table_13;
175        hash_table<identity_strategy_t<uint64_t,14>, hash_strategy_t<14>, ALLOCATOR> hash_table_14;
176        hash_table<identity_strategy_t<uint64_t,15>, hash_strategy_t<15>, ALLOCATOR> hash_table_15;
177        hash_table<identity_strategy_t<BitBlock,16>, hash_strategy_t<16>, ALLOCATOR> hash_table_16;
178        hash_table<identity_strategy_d, hash_strategy_d, ALLOCATOR> hash_table_gte_17;
179};
180
181/* NOTE: C++ template code and Pablo generated length groups must coincide. */
182
183// Fixed Lengths - REVERSE SCAN LOGIC - Scan each BLOCK MSB to LSB
184template<class SYMBOL, class HASH_TABLE>
185void do_block(uint32_t blk_offset,
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) {
191
192                uint8_t * buffer_base = buffer;
193                uint8_t * h0_base = h0;
194                uint8_t * h1_base = h1;
195
196                gid_type gid;
197                int32_t epos;
198                int32_t spos;
199                uint32_t blk_count;
200
201        ReverseScanner<BitBlock, scanword_t> rscanner(&ends);
202
203        rscanner.scan_to_next();
204        epos = rscanner.get_pos();
205
206                while(!rscanner.is_done()) {
207
208                spos = epos - lgth;
209
210                        if(spos < 0) { // boundary case
211                                        spos = (BLOCK_SIZE - (-1 * spos)) & (BLOCK_SIZE - 1);
212                                        blk_count = (lgth/BLOCK_SIZE)+1;
213                                        buffer_base -= (BLOCK_SIZE * blk_count);
214                                        h0_base -= (h_block_size * blk_count);
215                                        h1_base -= (h_block_size * blk_count);
216                        }
217
218                        assert (spos >= 0);
219
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
221
222                        #ifdef ID_SYMBOL_STORE_SYMBOL_GIDS_AT_END_POSITION
223                        symbols.gids[blk_offset + epos] = gid;
224                        #else
225                        symbols.gids[blk_offset + epos - lgth] = gid;
226                        #endif
227
228                        #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
229                                print_symbol_debug(gid, buffer_base, spos, epos, lgth);
230                        #endif
231
232                        rscanner.scan_to_next();
233                epos = rscanner.get_pos();
234                }
235        }
236
237
238// Variable Lengths, reverse scanner logic
239// Precondition: A symbol end is marked iff a symbol start is marked within a buffer segment.
240template<class SYMBOL, class HASH_TABLE>
241void do_block(uint32_t blk_offset,
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,
246                          SYMBOL & symbols, GIDFactory & gid_factory, GIDData & gid_data) {
247
248        BitBlock * starts_base = starts;
249        uint8_t * buffer_base = buffer;
250        uint8_t * h0_base = h0;
251        uint8_t * h1_base = h1;
252
253        gid_type gid;
254        int32_t epos;
255        int32_t spos;
256        uint32_t lgth;
257        uint32_t blk_count = 0;
258
259        ReverseScanner<BitBlock, scanword_t> ends_rscanner(ends);
260        ReverseScanner<BitBlock, scanword_t> starts_rscanner(starts);
261
262        ends_rscanner.scan_to_next();
263        epos = ends_rscanner.get_pos();
264
265        while(!ends_rscanner.is_done()) {
266
267                starts_rscanner.move_to(epos);
268                starts_rscanner.scan_to_next();
269                spos = starts_rscanner.get_pos();
270                lgth = epos - spos;
271
272                while(starts_rscanner.is_done()) { // boundary case
273                          starts_base--;
274
275                        blk_count++;
276
277                        starts_rscanner.init(starts_base);
278                        starts_rscanner.scan_to_next();
279
280                        if(!starts_rscanner.is_done()) { // found start
281                                        lgth = epos + (BLOCK_SIZE - starts_rscanner.get_pos()) + (BLOCK_SIZE * (blk_count-1));
282                                        // spos = (BLOCK_SIZE - (-1 * spos)) & (BLOCK_SIZE - 1);
283
284                                        // buffer_base -= (BLOCK_SIZE * blk_count);
285                                        //spos = epos - lgth;
286                                        spos = starts_rscanner.get_pos();
287
288                                        buffer_base -= (BLOCK_SIZE * blk_count);
289                                        h0_base -= (h_block_size * blk_count);
290                                        h1_base -= (h_block_size * blk_count);
291                                        break;
292                        }
293
294                }
295
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
297
298                #ifdef ID_SYMBOL_STORE_SYMBOL_GIDS_AT_END_POSITION
299                symbols.gids[blk_offset + epos] = gid;
300                #else
301                symbols.gids[blk_offset + epos - lgth] = gid;
302                #endif
303
304                #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
305                        //print_symbol_debug(gid, buffer, spos, epos, lgth);
306                        print_symbol_debug(gid, buffer_base, spos, epos, lgth);
307                #endif
308
309                ends_rscanner.scan_to_next();
310                epos = ends_rscanner.get_pos();
311        }
312}
313
314#endif // ID_SYMBOL_TABLE_TEMPLATE_HPP
315
316//
317/*
318void do_block(uint32_t blk_offset,
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) {
324
325        gid_type gid;
326        int32_t spos;
327        int32_t epos;
328        ForwardScanner<BitBlock, scanword_t> fscanner(&ends);
329
330        fscanner.scan_to_next();
331        epos = fscanner.get_pos();
332        spos = (epos - lgth);
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
360        }
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);
374        }
375
376}
377*/
378
Note: See TracBrowser for help on using the repository browser.