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

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

Code clean up.

File size: 15.0 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
68        hash_table_9.print_diagnostics();
69        hash_table_10.print_diagnostics();
70        hash_table_11.print_diagnostics();
71        hash_table_12.print_diagnostics();
72        hash_table_13.print_diagnostics();
73        hash_table_14.print_diagnostics();
74        hash_table_15.print_diagnostics();
75        hash_table_16.print_diagnostics();
76        hash_table_gte_17.print_diagnostics();
77#endif
78    }
79
80                  // Groups & groups
81                  void resolve(uint8_t buffer [], Groups groups [],  BitBlock starts [], BitBlock ends_gte_17 [],
82                                                                                BitBlock h0 [], BitBlock h1 [], uint32_t blocks, SYMBOL & symbols) {
83
84                        uint32_t blk_offset;
85
86                        for(uint32_t blk=0;blk<blocks;blk++) {
87
88                                blk_offset = blk * BLOCKSIZE;
89                                ///////////////////////////////////////////////////////////////////////////////
90                                // Byte Space Hash
91                                ///////////////////////////////////////////////////////////////////////////////
92                                if(bitblock::any(groups[blk].ends_1)) {
93                                        do_block<SYMBOL, hash_table <identity_strategy_t<uint8_t,1>, hash_strategy_t<1>, ALLOCATOR> >
94                                                (blk_offset,
95                                                 hash_table_1,
96                                                 groups[blk].ends_1,
97                                                 &buffer[blk_offset], 1,                                                  /* buffer, symbol length */
98                                                 &buffer[blk_offset], &buffer[blk_offset], bytes2bits(1), BLOCK_SIZE, /* h0, h1, hash lgth (bits), hash block size (bits) */
99                                                 symbols, this->gid_factory, this->gid_data);
100                                }
101                                if(bitblock::any(groups[blk].ends_2)) {
102                                                do_block<SYMBOL, hash_table <identity_strategy_t<uint16_t,2>, hash_strategy_t<2>, ALLOCATOR> >
103                                                        (blk_offset,
104                                                         hash_table_2,
105                                                         groups[blk].ends_2,
106                                                         &buffer[blk_offset], 2,
107                                                         &buffer[blk_offset], &buffer[blk_offset], bytes2bits(2), BLOCK_SIZE,
108                                                         symbols, this->gid_factory, this->gid_data);
109                                }
110                                if(bitblock::any(groups[blk].ends_3)) {
111                                                do_block<SYMBOL, hash_table <identity_strategy_t<uint16_t,3>, hash_strategy_t<3>, ALLOCATOR> >
112                                                        (blk_offset,
113                                                         hash_table_3,
114                                                         groups[blk].ends_3,
115                                                         &buffer[blk_offset], 3,
116                                                         &buffer[blk_offset], &buffer[blk_offset], bytes2bits(3), BLOCK_SIZE,
117                                                         symbols, this->gid_factory, this->gid_data);
118                                }
119                                if(bitblock::any(groups[blk].ends_4)) {
120                                                do_block<SYMBOL, hash_table <identity_strategy_t<uint32_t,4>, hash_strategy_t<4>, ALLOCATOR> >
121                                                        (blk_offset,
122                                                         hash_table_4,
123                                                         groups[blk].ends_4,
124                                                         &buffer[blk_offset], 4,
125                                                         &buffer[blk_offset], &buffer[blk_offset], bytes2bits(4), BLOCK_SIZE,
126                                                         symbols, this->gid_factory, this->gid_data);
127                                }
128                                if(bitblock::any(groups[blk].ends_5)) {
129                                                do_block<SYMBOL, hash_table <identity_strategy_t<uint32_t,5>, hash_strategy_t<5>, ALLOCATOR> >
130                                                        (blk_offset,
131                                                         hash_table_5,
132                                                         groups[blk].ends_5,
133                                                         &buffer[blk_offset], 5,
134                                                         &buffer[blk_offset], &buffer[blk_offset], bytes2bits(5), BLOCK_SIZE,
135                                                         symbols, this->gid_factory, this->gid_data);
136                                }
137                                if(bitblock::any(groups[blk].ends_6)) {
138                                                do_block<SYMBOL, hash_table <identity_strategy_t<uint32_t,6>, hash_strategy_t<6>, ALLOCATOR> >
139                                                        (blk_offset,
140                                                         hash_table_6,
141                                                         groups[blk].ends_6,
142                                                         &buffer[blk_offset], 6,
143                                                         &buffer[blk_offset], &buffer[blk_offset], bytes2bits(6), BLOCK_SIZE,
144                                                         symbols, this->gid_factory, this->gid_data);
145                                }
146                                if(bitblock::any(groups[blk].ends_7)) {
147                                                do_block<SYMBOL, hash_table <identity_strategy_t<uint32_t,7>, hash_strategy_t<7>, ALLOCATOR> >
148                                                        (blk_offset,
149                                                         hash_table_7,
150                                                         groups[blk].ends_7,
151                                                         &buffer[blk_offset], 7,
152                                                         &buffer[blk_offset], &buffer[blk_offset], bytes2bits(7), BLOCK_SIZE,
153                                                         symbols, this->gid_factory, this->gid_data);
154                                }
155                                ///////////////////////////////////////////////////////////////////////////////
156                                // Bit Space Hash
157                                ///////////////////////////////////////////////////////////////////////////////
158                                if(bitblock::any(groups[blk].ends_8)) {
159                                                do_block<SYMBOL, hash_table <identity_strategy_t<uint64_t,8>, hash_strategy_d, ALLOCATOR> >
160                                                        (blk_offset,
161                                                         hash_table_8,
162                                                         groups[blk].ends_8, &buffer[blk_offset], 8,
163                                                         (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 8, BLOCK_SIZE/8,
164                                                         symbols, this->gid_factory, this->gid_data);
165                                }
166                                if(bitblock::any(groups[blk].ends_9)) {
167                                        do_block<SYMBOL, hash_table<identity_strategy_t<uint64_t,9>, hash_strategy_d, ALLOCATOR> >
168                                                (blk_offset,
169                                                hash_table_9,
170                                                groups[blk].ends_9, &buffer[blk_offset], 9,
171                                                (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 9, BLOCK_SIZE/8,
172                                                symbols, this->gid_factory, this->gid_data);
173                                }
174                                if(bitblock::any(groups[blk].ends_10)) {
175                                        do_block<SYMBOL, hash_table<identity_strategy_t<uint64_t,10>, hash_strategy_d, ALLOCATOR> >
176                                                (blk_offset,
177                                                hash_table_10,
178                                                groups[blk].ends_10, &buffer[blk_offset], 10,
179                                                (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 10, BLOCK_SIZE/8,
180                                                symbols, this->gid_factory, this->gid_data);
181                                }
182                                if(bitblock::any(groups[blk].ends_11)) {
183                                        do_block<SYMBOL, hash_table<identity_strategy_t<uint64_t,11>, hash_strategy_d, ALLOCATOR> >
184                                                        (blk_offset,
185                                                        hash_table_11,
186                                                        groups[blk].ends_11, &buffer[blk_offset], 11,
187                                                        (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 11, BLOCK_SIZE/8,
188                                                        symbols, this->gid_factory, this->gid_data);
189                                }
190                                if(bitblock::any(groups[blk].ends_12)) {
191                                        do_block<SYMBOL, hash_table<identity_strategy_t<uint64_t,12>, hash_strategy_d, ALLOCATOR> >
192                                                        (blk_offset,
193                                                        hash_table_12,
194                                                        groups[blk].ends_12, &buffer[blk_offset], 12,
195                                                        (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 12, BLOCK_SIZE/8,
196                                                        symbols, this->gid_factory, this->gid_data);
197                                }
198                                if(bitblock::any(groups[blk].ends_13)) {
199                                        do_block<SYMBOL, hash_table<identity_strategy_t<uint64_t,13>, hash_strategy_d, ALLOCATOR> >
200                                                        (blk_offset,
201                                                        hash_table_13,
202                                                        groups[blk].ends_13, &buffer[blk_offset], 13,
203                                                        (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 13, BLOCK_SIZE/8,
204                                                        symbols, this->gid_factory, this->gid_data);
205                                }
206                                if(bitblock::any(groups[blk].ends_14)) {
207                                        do_block<SYMBOL, hash_table<identity_strategy_t<uint64_t,14>, hash_strategy_d, ALLOCATOR> >
208                                                        (blk_offset,
209                                                        hash_table_14,
210                                                        groups[blk].ends_14, &buffer[blk_offset], 14,
211                                                        (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 14, BLOCK_SIZE/8,
212                                                        symbols, this->gid_factory, this->gid_data);
213                                }
214                                if(bitblock::any(groups[blk].ends_15)) {
215                                        do_block<SYMBOL, hash_table<identity_strategy_t<uint64_t,15>, hash_strategy_d, ALLOCATOR> >
216                                                        (blk_offset,
217                                                        hash_table_15,
218                                                        groups[blk].ends_15, &buffer[blk_offset], 15,
219                                                        (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 15, BLOCK_SIZE/8,
220                                                        symbols, this->gid_factory, this->gid_data);
221                                }
222                                if(bitblock::any(groups[blk].ends_16)) {
223                                        do_block<SYMBOL, hash_table<identity_strategy_t<BitBlock,16>, hash_strategy_d, ALLOCATOR> >
224                                                        (blk_offset,
225                                                        hash_table_16,
226                                                        groups[blk].ends_16, &buffer[blk_offset], 16,
227                                                        (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 16, BLOCK_SIZE/8,
228                                                        symbols, this->gid_factory, this->gid_data);
229                                }
230                                if(bitblock::any(groups[blk].ends_gte_17)) {
231                                        do_block<SYMBOL, hash_table<identity_strategy_d, hash_strategy_d, ALLOCATOR> >
232                                                        (blk_offset,
233                                                         hash_table_gte_17,
234                                                         &starts[blk], &ends_gte_17[blk],
235                                                         &buffer[blk_offset],
236                                                         (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 17, BLOCK_SIZE/8,
237                                                         symbols, this->gid_factory, this->gid_data);
238                                }
239                        }
240    }
241
242private:
243    ///////////////////////////////////////////////////////////////////////////////
244    // Byte Space Hash
245    ///////////////////////////////////////////////////////////////////////////////
246    hash_table<identity_strategy_t<uint8_t,1>, hash_strategy_t<1>, ALLOCATOR> hash_table_1;
247    hash_table<identity_strategy_t<uint16_t,2>, hash_strategy_t<2>, ALLOCATOR> hash_table_2;
248    hash_table<identity_strategy_t<uint16_t,3>, hash_strategy_t<3>, ALLOCATOR> hash_table_3;
249    hash_table<identity_strategy_t<uint32_t,4>, hash_strategy_t<4>, ALLOCATOR> hash_table_4;
250    hash_table<identity_strategy_t<uint32_t,5>, hash_strategy_t<5>, ALLOCATOR> hash_table_5;
251    hash_table<identity_strategy_t<uint32_t,6>, hash_strategy_t<6>, ALLOCATOR> hash_table_6;
252    hash_table<identity_strategy_t<uint32_t,7>, hash_strategy_t<7>, ALLOCATOR> hash_table_7;
253    ///////////////////////////////////////////////////////////////////////////////
254    // Bit Space Hash
255    ///////////////////////////////////////////////////////////////////////////////
256    hash_table<identity_strategy_t<uint64_t,8>, hash_strategy_d, ALLOCATOR> hash_table_8;
257    hash_table<identity_strategy_t<uint64_t,9>, hash_strategy_d, ALLOCATOR> hash_table_9;
258    hash_table<identity_strategy_t<uint64_t,10>, hash_strategy_d, ALLOCATOR> hash_table_10;
259    hash_table<identity_strategy_t<uint64_t,11>, hash_strategy_d, ALLOCATOR> hash_table_11;
260    hash_table<identity_strategy_t<uint64_t,12>, hash_strategy_d, ALLOCATOR> hash_table_12;
261    hash_table<identity_strategy_t<uint64_t,13>, hash_strategy_d, ALLOCATOR> hash_table_13;
262    hash_table<identity_strategy_t<uint64_t,14>, hash_strategy_d, ALLOCATOR> hash_table_14;
263    hash_table<identity_strategy_t<uint64_t,15>, hash_strategy_d, ALLOCATOR> hash_table_15;
264    hash_table<identity_strategy_t<BitBlock,16>, hash_strategy_d, ALLOCATOR> hash_table_16;
265    hash_table<identity_strategy_d, hash_strategy_d, ALLOCATOR> hash_table_gte_17;
266};
267
268/* NOTE: C++ template code and Pablo generated length groups must coincide. */
269
270// Fixed Lengths - REVERSE SCAN LOGIC - Scan each BLOCK MSB to LSB
271template<class SYMBOL, class HASH_TABLE>
272void do_block(uint32_t blk_offset,
273              HASH_TABLE & h_table,
274              BitBlock ends,
275              uint8_t buffer [], const uint32_t lgth,
276              uint8_t h0 [], uint8_t h1 [], const uint32_t h_lgth, const uint32_t h_block_size,
277              SYMBOL & symbols, GIDFactory & gid_factory, GIDData & gid_data) {
278
279    gid_type gid;
280    int32_t spos;
281    int32_t epos;
282    ForwardScanner<BitBlock, scanword_t> fscanner(&ends);
283
284    fscanner.scan_to_next();
285    epos = fscanner.get_pos();
286    spos = (epos - lgth);
287
288        if(!fscanner.is_done() && (spos < 0) ) { // block boundary case
289
290        ////////////////////////////////////////////////////////////////////
291        // Start - Review boundary logic
292        ////////////////////////////////////////////////////////////////////
293        uint8_t * lb_buffer = buffer - ((lgth / BLOCK_SIZE) + 1)*BLOCK_SIZE;
294        int32_t lb_spos = (BLOCK_SIZE - (-1*spos)) & (BLOCK_SIZE-1);
295
296        uint8_t * lb_h0 = h0 - ((lgth / BLOCK_SIZE) + 1)*h_block_size;
297        uint8_t * lb_h1 = h1 - ((lgth / BLOCK_SIZE) + 1)*h_block_size;
298
299        gid = h_table.lookup_or_insert(lb_buffer, lb_spos, lgth, lb_h0, lb_h1, h_lgth, gid_factory, gid_data);
300
301        symbols.gids[blk_offset + spos] = gid;
302        ////////////////////////////////////////////////////////////////////
303        // End
304        ////////////////////////////////////////////////////////////////////
305
306        #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
307                        print_symbol_debug(gid, lb_buffer, lb_spos, epos, lgth);
308        #endif
309
310        fscanner.scan_to_next();
311        epos = fscanner.get_pos();
312        spos = (epos - lgth);
313
314    }
315
316        while(!fscanner.is_done()) {
317
318                gid = h_table.lookup_or_insert(buffer, spos, lgth, h0, h1, h_lgth, gid_factory, gid_data);
319                symbols.gids[blk_offset + spos] = gid;
320
321        #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
322                print_symbol_debug(gid, buffer, spos, epos, lgth);
323        #endif
324
325                fscanner.scan_to_next();
326                epos = fscanner.get_pos();
327                spos = (epos - lgth);
328    }
329
330}
331
332// Variable Lengths, reverse scanner logic
333// Precondition: A symbol end is marked iff a symbol start is marked within a buffer segment.
334template<class SYMBOL, class HASH_TABLE>
335void do_block(uint32_t blk_offset,
336                          HASH_TABLE & h_table,
337                          BitBlock starts [], BitBlock ends [],
338                          uint8_t buffer [],
339                          uint8_t h0 [], uint8_t h1 [], const uint32_t h_lgth, const uint32_t h_block_size,
340                          SYMBOL & symbols, GIDFactory & gid_factory, GIDData & gid_data) {
341
342        BitBlock * starts_base = starts;
343        uint8_t * h0_base = h0;
344        uint8_t * h1_base = h1;
345
346        gid_type gid;
347        int32_t epos;
348        int32_t spos;
349        uint32_t lgth;
350        uint32_t blk_count = 0;
351
352        ReverseScanner<BitBlock, scanword_t> ends_rscanner(ends);
353        ReverseScanner<BitBlock, scanword_t> starts_rscanner(starts);
354
355        ends_rscanner.scan_to_next();
356        epos = ends_rscanner.get_pos();
357
358        while(!ends_rscanner.is_done()) {
359               
360                starts_rscanner.move_to(epos);
361                starts_rscanner.scan_to_next();
362                spos = starts_rscanner.get_pos();
363                lgth = epos - spos;
364
365                while(starts_rscanner.is_done()) { // boundary case
366                    starts_base--;
367                    h0_base--;
368                    h1_base--;
369
370                    starts_rscanner.init(starts_base);
371                    starts_rscanner.scan_to_next();
372
373                    if(!starts_rscanner.is_done()) { // found start
374
375                        lgth = epos + (BLOCK_SIZE - starts_rscanner.get_pos()) + (BLOCK_SIZE * blk_count);
376                        spos = epos - lgth;
377                        h0_base -= (h_block_size * blk_count);
378                        h1_base -= (h_block_size * blk_count);
379                        break;
380                    }
381                    blk_count++;
382
383                }
384
385                gid = h_table.lookup_or_insert(buffer, spos, lgth, h0_base, h1_base, h_lgth, gid_factory, gid_data);
386                symbols.gids[blk_offset + spos] = gid;
387
388                #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
389                        print_symbol_debug(gid, buffer, spos, epos, lgth);
390                #endif
391
392                ends_rscanner.scan_to_next();
393                epos = ends_rscanner.get_pos();
394        }
395}
396
397#endif // ID_SYMBOL_TABLE_TEMPLATE_HPP
398
399
Note: See TracBrowser for help on using the repository browser.