source: trunk/symbol_table/id_symbol_table.hpp @ 1986

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

Standalone symbol table - initial check in.

File size: 10.6 KB
Line 
1/*
2 * id_symbol_table.hpp - Identity Symbol Table Pablo Template
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//#define ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
17
18#include "symbol_table.hpp"
19#include "hash_table.hpp"
20#include "../lib/carryQ.hpp"
21#include "../lib/bitblock_iterator.hpp"
22#include "../lib/bitblock_scan.hpp"
23
24/* NOTE: C++ template code and Pablo generated length groups must coincide. */
25//static const uint32_t LGTH_GROUPS = 17;
26
27template<class HASH_TABLE>
28IDISA_ALWAYS_INLINE void do_block(HASH_TABLE & h_table, BitBlock ends, uint8_t buffer [], const uint32_t lgth,
29                                  uint8_t h0 [], uint8_t h1 [], const uint32_t h_lgth, const uint32_t h_block_size) {
30
31    int32_t spos;
32    int32_t epos;
33    ForwardScanner<BitBlock, scanword_t> scanner(&ends);
34    scanner.scan_to_next();
35    epos = scanner.get_pos();
36    spos = (epos - lgth);
37
38    if((epos != -1) && (spos < 0)) { // block boundary case
39
40        assert(lgth<=BLOCK_SIZE); // segment boundary
41
42        uint8_t * lb_buffer = buffer - ((lgth / BLOCK_SIZE) + 1)*BLOCK_SIZE;
43        int32_t lb_spos = BLOCK_SIZE - ((-1*spos) & (BLOCK_SIZE-1));
44
45        uint8_t * lb_h0 = h0 - ((lgth / BLOCK_SIZE) + 1)*h_block_size;
46        uint8_t * lb_h1 = h1 - ((lgth / BLOCK_SIZE) + 1)*h_block_size;
47
48        h_table.lookup_or_insert(lb_buffer, lb_spos, lgth,
49                                 lb_h0, lb_h1, h_lgth);
50
51#ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
52        cout << "Symbol(";
53        cout << "End:" << epos;
54        cout << ",Start:" << lb_spos;
55        cout << ",Text:'" << string((char *)&(lb_buffer[lb_spos]), lgth);
56        cout << "')" << endl;
57#endif
58        epos = scanner.scan_to_next();
59        spos = (epos - lgth);
60
61    }
62
63    while(epos != -1) {
64
65        h_table.lookup_or_insert(buffer, spos, lgth,
66                                 h0, h1, h_lgth);
67
68#ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
69        cout << "Symbol(";
70        cout << "End:" << epos;
71        cout << ",Start:" << spos;
72        cout << ",Text:'" << string((char *)&(buffer[spos]), lgth);
73        cout << "')" << endl;
74#endif
75        epos = scanner.scan_to_next();
76        spos = (epos - lgth);
77
78    }
79}
80
81template<class ALLOCATOR>
82class id_symbol_table : public symbol_table {
83public:
84    id_symbol_table()/*:hash_table_1(256)*/{}
85    ~id_symbol_table() {
86#ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
87        hash_table_1.print_table();
88        hash_table_2.print_table();
89        hash_table_3.print_table();
90        hash_table_4.print_table();
91        hash_table_5.print_table();
92        hash_table_6.print_table();
93        hash_table_7.print_table();
94        hash_table_8.print_table();
95        hash_table_9.print_table();
96        hash_table_10.print_table();
97        hash_table_11.print_table();
98        hash_table_12.print_table();
99        hash_table_13.print_table();
100        hash_table_14.print_table();
101        hash_table_15.print_table();
102        hash_table_16.print_table();
103#endif
104    }
105
106    // Groups & groups
107    void resolve(uint8_t buffer [], Groups groups [], BitBlock h0 [], BitBlock h1 [], uint32_t blocks, AoS_symbol symbol_ary [], const uint32_t symbols) {
108
109        for(uint32_t blk=0;blk<blocks;blk++) {
110        ///////////////////////////////////////////////////////////////////////////////
111        // Byte Space Hash
112        ///////////////////////////////////////////////////////////////////////////////
113        if(bitblock::any(groups[blk].ends_1)) {
114        do_block<hash_table <identity_strategy_t<uint8_t,1>, hash_strategy_t<1>, ALLOCATOR> >(hash_table_1, groups[blk].ends_1, &buffer[blk*BLOCK_SIZE], 1, &buffer[blk*BLOCK_SIZE], &buffer[blk*BLOCK_SIZE], bytes2bits(1), BLOCK_SIZE);
115        }
116        if(bitblock::any(groups[blk].ends_2)) {
117        do_block<hash_table <identity_strategy_t<uint16_t,2>, hash_strategy_t<2>, ALLOCATOR> >(hash_table_2, groups[blk].ends_2, &buffer[blk*BLOCK_SIZE], 2, &buffer[blk*BLOCK_SIZE], &buffer[blk*BLOCK_SIZE], bytes2bits(2), BLOCK_SIZE);
118        }
119        if(bitblock::any(groups[blk].ends_3)) {
120        do_block<hash_table <identity_strategy_t<uint16_t,3>, hash_strategy_t<3>, ALLOCATOR> >(hash_table_3, groups[blk].ends_3, &buffer[blk*BLOCK_SIZE], 3, &buffer[blk*BLOCK_SIZE], &buffer[blk*BLOCK_SIZE], bytes2bits(3), BLOCK_SIZE);
121        }
122        if(bitblock::any(groups[blk].ends_4)) {
123        do_block<hash_table <identity_strategy_t<uint32_t,4>, hash_strategy_t<4>, ALLOCATOR> >(hash_table_4, groups[blk].ends_4, &buffer[blk*BLOCK_SIZE], 4, &buffer[blk*BLOCK_SIZE], &buffer[blk*BLOCK_SIZE], bytes2bits(4), BLOCK_SIZE);
124        }
125        if(bitblock::any(groups[blk].ends_5)) {
126        do_block<hash_table <identity_strategy_t<uint32_t,5>, hash_strategy_t<5>, ALLOCATOR> >(hash_table_5, groups[blk].ends_5, &buffer[blk*BLOCK_SIZE], 5, &buffer[blk*BLOCK_SIZE], &buffer[blk*BLOCK_SIZE], bytes2bits(5), BLOCK_SIZE);
127        }
128        if(bitblock::any(groups[blk].ends_6)) {
129        do_block<hash_table <identity_strategy_t<uint32_t,6>, hash_strategy_t<6>, ALLOCATOR> >(hash_table_6, groups[blk].ends_6, &buffer[blk*BLOCK_SIZE], 6, &buffer[blk*BLOCK_SIZE], &buffer[blk*BLOCK_SIZE], bytes2bits(6), BLOCK_SIZE);
130        }
131        if(bitblock::any(groups[blk].ends_7)) {
132        do_block<hash_table <identity_strategy_t<uint32_t,7>, hash_strategy_t<7>, ALLOCATOR> >(hash_table_7, groups[blk].ends_7, &buffer[blk*BLOCK_SIZE], 7, &buffer[blk*BLOCK_SIZE], &buffer[blk*BLOCK_SIZE], bytes2bits(7), BLOCK_SIZE);
133        }
134        ///////////////////////////////////////////////////////////////////////////////
135        // Bit Space Hash
136        ///////////////////////////////////////////////////////////////////////////////
137        if(bitblock::any(groups[blk].ends_8)) {
138        do_block<hash_table <identity_strategy_t<uint64_t,8>, hash_strategy_t<8>, ALLOCATOR> >(hash_table_8, groups[blk].ends_8, &buffer[blk*BLOCK_SIZE], 8, (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 8, BLOCK_SIZE/8);
139        }
140        if(bitblock::any(groups[blk].ends_9)) {
141        do_block<hash_table<identity_strategy_t<uint64_t,9>, hash_strategy_d, ALLOCATOR> >(hash_table_9, groups[blk].ends_9, &buffer[blk*BLOCK_SIZE], 9, (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 9, BLOCK_SIZE/8);
142        }
143        if(bitblock::any(groups[blk].ends_10)) {
144        do_block<hash_table<identity_strategy_t<uint64_t,10>, hash_strategy_d, ALLOCATOR> >(hash_table_10, groups[blk].ends_10, &buffer[blk*BLOCK_SIZE], 10, (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 10, BLOCK_SIZE/8);
145        }
146        if(bitblock::any(groups[blk].ends_11)) {
147        do_block<hash_table<identity_strategy_t<uint64_t,11>, hash_strategy_d, ALLOCATOR> >(hash_table_11, groups[blk].ends_11, &buffer[blk*BLOCK_SIZE], 11, (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 11, BLOCK_SIZE/8);
148        }
149        if(bitblock::any(groups[blk].ends_12)) {
150        do_block<hash_table<identity_strategy_t<uint64_t,12>, hash_strategy_d, ALLOCATOR> >(hash_table_12, groups[blk].ends_12, &buffer[blk*BLOCK_SIZE], 12, (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 12, BLOCK_SIZE/8);
151        }
152        if(bitblock::any(groups[blk].ends_13)) {
153        do_block<hash_table<identity_strategy_t<uint64_t,13>, hash_strategy_d, ALLOCATOR> >(hash_table_13, groups[blk].ends_13, &buffer[blk*BLOCK_SIZE], 13, (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 13, BLOCK_SIZE/8);
154        }
155        if(bitblock::any(groups[blk].ends_14)) {
156        do_block<hash_table<identity_strategy_t<uint64_t,14>, hash_strategy_d, ALLOCATOR> >(hash_table_14, groups[blk].ends_14, &buffer[blk*BLOCK_SIZE], 14, (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 14, BLOCK_SIZE/8);
157        }
158        if(bitblock::any(groups[blk].ends_15)) {
159        do_block<hash_table<identity_strategy_t<uint64_t,15>, hash_strategy_d, ALLOCATOR> >(hash_table_15, groups[blk].ends_15, &buffer[blk*BLOCK_SIZE], 15, (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 15, BLOCK_SIZE/8);
160        }
161        if(bitblock::any(groups[blk].ends_16)) {
162        do_block<hash_table<identity_strategy_t<BitBlock,16>, hash_strategy_d, ALLOCATOR> >(hash_table_16, groups[blk].ends_16, &buffer[blk*BLOCK_SIZE], 16, (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 16, BLOCK_SIZE/8);
163        }
164        if(bitblock::any(groups[blk].ends_gte_17)) {
165        do_block<hash_table<identity_strategy_d, hash_strategy_d, ALLOCATOR> >(hash_table_gte_17, groups[blk].ends_gte_17, &buffer[blk*BLOCK_SIZE], 16, (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 16, BLOCK_SIZE/8);
166        }
167
168
169
170//      do_segment<hash_table<identity_strategy_d, hash_strategy_d, ALLOCATOR> >(hgte_17, starts, groups.ends_gte_17, segment_size);
171
172        }
173    }
174
175    // void resolve(uint8_t * segment, uint32_t segment_blocks, BitBlock * starts, BitBlock * ends, BitBlock * hash_values, SoA_symbol & symbols) {}
176private:
177
178    hash_table<identity_strategy_t<uint8_t,1>, hash_strategy_t<1>, ALLOCATOR> hash_table_1;
179    hash_table<identity_strategy_t<uint16_t,2>, hash_strategy_t<2>, ALLOCATOR> hash_table_2;
180    hash_table<identity_strategy_t<uint16_t,3>, hash_strategy_t<3>, ALLOCATOR> hash_table_3;
181    hash_table<identity_strategy_t<uint32_t,4>, hash_strategy_t<4>, ALLOCATOR> hash_table_4;
182    hash_table<identity_strategy_t<uint32_t,5>, hash_strategy_t<5>, ALLOCATOR> hash_table_5;
183    hash_table<identity_strategy_t<uint32_t,6>, hash_strategy_t<6>, ALLOCATOR> hash_table_6;
184    hash_table<identity_strategy_t<uint32_t,7>, hash_strategy_t<7>, ALLOCATOR> hash_table_7;
185
186    hash_table<identity_strategy_t<uint64_t,8>, hash_strategy_t<8>, ALLOCATOR> hash_table_8;
187    hash_table<identity_strategy_t<uint64_t,9>, hash_strategy_d, ALLOCATOR> hash_table_9;
188    hash_table<identity_strategy_t<uint64_t,10>, hash_strategy_d, ALLOCATOR> hash_table_10;
189    hash_table<identity_strategy_t<uint64_t,11>, hash_strategy_d, ALLOCATOR> hash_table_11;
190    hash_table<identity_strategy_t<uint64_t,12>, hash_strategy_d, ALLOCATOR> hash_table_12;
191    hash_table<identity_strategy_t<uint64_t,13>, hash_strategy_d, ALLOCATOR> hash_table_13;
192    hash_table<identity_strategy_t<uint64_t,14>, hash_strategy_d, ALLOCATOR> hash_table_14;
193    hash_table<identity_strategy_t<uint64_t,15>, hash_strategy_d, ALLOCATOR> hash_table_15;
194    hash_table<identity_strategy_t<BitBlock,16>, hash_strategy_d, ALLOCATOR> hash_table_16;
195
196    hash_table<identity_strategy_d, hash_strategy_d, ALLOCATOR> hash_table_gte_17;
197
198};
199
200#endif // ID_SYMBOL_TABLE_TEMPLATE_HPP
201
202/*
203template<class SYMBOL, class ALLOCATOR>
204class div2: public symbol_table_strategy<SYMBOL, ALLOCATOR> {
205
206public:
207    div2() {}
208    ~div2() {}
209
210    void resolve(BitBlock * buffer, BitBlock * starts, BitBlock * ends, BitBlock * hash_basis_0, BitBlock * hash_basis_1, uint32_t segment_size, AoS_symbol * symbol_ary, const uint32_t symbol_ary_size) {
211        cout << "div2 Strategy" << endl;
212    }
213    //void resolve(uint8_t * segment, uint32_t segment_blocks, BitBlock * starts, BitBlock * ends, SoA_symbol & symbols);
214};
215*/
216/*
217template<class SYMBOL, class ALLOCATOR>
218class log2: public symbol_table_strategy<SYMBOL, ALLOCATOR> {
219
220public:
221    log2() {}
222    ~log2() {}
223
224    void resolve(BitBlock * buffer, BitBlock * starts, BitBlock * ends, BitBlock * hash_basis_0, BitBlock * hash_basis_1, uint32_t segment_size, AoS_symbol * symbol_ary, const uint32_t symbol_ary_size) {
225        cout << "log2 Strategy" << endl;
226    }
227    //void resolve(uint8_t * segment, uint32_t segment_blocks, BitBlock * starts, BitBlock * ends, SoA_symbol & symbols);
228};
229*/
230
Note: See TracBrowser for help on using the repository browser.