source: trunk/symtab/ls_symbol_table.h @ 2152

Last change on this file since 2152 was 1742, checked in by vla24, 8 years ago

SymbolTable?: Fixed custom hashing function for parallel bitstream based grouping

File size: 8.3 KB
Line 
1/*
2 *  ls_symbol_table.h
3 *
4 *  Created on: 21-Sep-2009
5 *  Author: ksherdy
6 *  Description: Length Sorted Symbol table (Key Sorted)
7 * 
8 *  WARNING
9 * 
10 *  A key assumption in the packed symbol implementation is that GID values are 32 bits.
11 *  This assumption is reflected in the implementation of the push_gid<fw> operations.
12 */
13
14// #define SYMBOL_TABLE_DEBUG                   // Show debug messages.
15
16#define USE_LENGTH_SORT                         // USE_LENGTH_SORT or USE_LENGTH_AND_KEY_SORT must be defined
17//#define USE_LENGTH_AND_KEY_SORT               // WARNING - Experimental - Not Implemented,
18
19//#define USE_FUNCTION_OBJECTS                  // USE_FUNCTION_OBJECTS or USE_FUNCTION_TEMPLATES must be defined
20#define USE_FUNCTION_TEMPLATES                         
21
22//#define USE_SYMBOL_PTRS                       // USE_SYMBOL_PTRS or USE_SYMBOL_VALUES must be defined                                         
23#define USE_SYMBOL_VALUES
24
25#define USE_PACKED_SYMBOLS                      // Optimize symbol lengths 1..8 via multi symbol comparisons.
26#ifdef USE_PACKED_SYMBOLS
27                                                // USE_SIMD_AND or USE_SSE_4_2 must be defined 
28        #define USE_SIMD_AND                    // SIMD and splatted symbol comparisons.
29        //#define USE_SSE_4_2                   // SSE 4.2 string comparisons. Requires SSE 4.2 instruction runtime support.
30       
31        #ifdef USE_SYMBOL_VALUES 
32          #define INIT_ONES                     // Initializes array values to all 1's.
33        #endif
34#endif
35
36// WARNING - Experimental - Not Implemented.
37//#define USE_PARALLEL_TRIE                     // Optimize symbol lengths 1..32
38#ifdef USE_PARALLEL_TRIE
39                                                // USE_SIMD_AND or USE_SSE_4_2 must be defined 
40        #define USE_SIMD_AND                    // SIMD and splatted symbol comparisons.
41        //#define USE_SSE_4_2                   // SSE 4.2 string comparisons.
42       
43        #ifdef USE_SYMBOL_VALUES 
44          #define INIT_ONES                     // Initializes array values to all 1's.
45        #endif
46#endif
47
48
49#include "arrays/HeapArray.h"
50#include "arrays/HeapArray2D.h"
51#include "stringpool.h"
52#include "ls_symbol_table_compare.h"
53
54#ifndef LSYMTAB_H_
55#define LSYMTAB_H_
56
57#include <vector>
58using namespace std;
59
60class LSSymbolTable {
61       
62public: 
63       
64        LSSymbolTable();
65        ~LSSymbolTable();
66       
67        // Adds a new symbol value to the memory pool.
68        void put(unsigned char * symbol_ptr, uint32_t lgth);
69       
70        // Binds a unique global numeric identifier with each unique symbol.
71        void bind();   
72
73        // Builds symbol table arrays and destroys temporary internal data structures.
74        void finalize();
75       
76        /*
77        TODO -  In a general symbol table it may be best to avoid sorting symbol binding by key.
78                Key sorting provides 'just-in-case' information that may not be needed by all applications.
79        */
80        /*
81        // Lookup symbol gid by document symbol index. Returns a gid.
82        uint32_t lookup_gid(uint32_t doc_idx);
83       
84        // Lookup symbol value by gid. Returns a symbol value pointer.
85        unsigned char * lookup_value(uint32_t gid);
86       
87        // Lookup symbol length by gid. Returns a symbol value length.
88        uint32_t lookup_length(uint32_t gid);
89        */
90       
91        // Clear symbol table contents.
92        void clear();
93       
94        // DEBUG
95        void display_lgth_dist() const;
96               
97        void display_flattened_symbol_values() const;
98       
99        void display_flattened_gids() const;
100
101        // Used for dictionary
102        vector<int> get_flattened_gids();
103               
104private:
105       
106        // Flattens 2D length sorted, unique symbol values into a 1D gid indexed array.
107        void flatten_unique_symbol_values();
108       
109        // Flatten 3D length, key, indexed data structure into a 1D globally occurence indexed 1D array of gids.
110        void flatten_gids();           
111       
112        // Bind symbols of length less than 33 to numeric identifiers
113#ifdef USE_FUNCTION_OBJECTS
114        template<uint32_t L, class Compare>
115        inline void bind(const Compare & compare);
116#endif 
117       
118#ifdef USE_FUNCTION_TEMPLATES
119        template<uint32_t L>
120        inline void bind();
121#endif
122
123        // Sort symbols of length 32 or greater
124        inline void bind_gt(int max_lgth);
125       
126        static const unsigned short LGTH_BINS_ = 33;                            // initial number of length bins 0,1,...,LGTH_BINS-1 
127       
128                                                                                // IMPORTANT: gid is overloaded as both a unique symbol identifier
129                                                                                //            AND an as index into the gid_idx_key_vals_ and gid_idx_key_lgths_ arrays,
130                                                                                //        this allows lookup of key value and key length by gid
131
132        uint32_t crt_symbol_index_;
133        uint32_t crt_symbol_gid_;                                               // current gid, 0,1,...
134       
135        // length indexed 2D arrays
136                                                                                // parallel arrays, symbol_index_ and symbol_value_ptrs_
137        HeapArray2D<uint32_t> * symbol_index_;                                  // maintains global order information for scatter operations
138       
139#ifdef USE_SYMBOL_PTRS 
140        HeapArray2D<unsigned char *> * symbol_value_ptrs_;
141#endif
142       
143#ifdef USE_SYMBOL_VALUES
144        HeapArray2D<unsigned char> * symbol_values_;
145#endif 
146               
147        HeapArray2D<unsigned char> * uniq_symbol_values_;                       // parallel arrays, uniq_symbol_values_ and uniq_symbol_gids_   
148        HeapArray2D<uint32_t> * uniq_symbol_gids_;
149
150#ifdef USE_LENGTH_SORT 
151        HeapArray2D<uint32_t> * gids_;
152#endif
153       
154#ifdef USE_LENGTH_AND_KEY_SORT 
155        vector< vector< vector <uint32_t> > > symbol_indices_;                  // length indexed, key indexed, symbol indices,
156                                                                                // where symbol_indices_[l][k][i] returns the ith symbol occurence, of the kth key, of symbol length l.                                 
157       
158                                                                                // IMPORTANT:   ith key of length l value is uniq_symbol_value_[L][i]
159                                                                                //              ith key of length l gid is uniq_symbol_gids_[L][i]     
160#endif
161       
162        //flattened 1D arrays
163        HeapArray<unsigned char *> * gid_idx_symbol_value_ptrs_;                // gid indexed parallel arrays, gid_idx_symbol_value_ptrs_ and gid_idx_symbol_lengths_ 
164        HeapArray<uint32_t> * gid_idx_symbol_lengths_;                                                                 
165       
166        HeapArray<uint32_t> * doc_idx_gids_;                                    // document indexed symbol gids
167                       
168#ifdef USE_PACKED_SYMBOLS
169
170        SIMD_type packed_gid_mask_128_;         
171        HeapArray2D<SIMD_type> * uniq_key_packed_mask_splats_; 
172        HeapArray2D<SIMD_type> * uniq_key_packed_gid_masks_;   
173        HeapArray2D<uint32_t> * packed_gids_;   
174       
175        // Template Declarations
176        // Index SIMD (128 bit) values containing 8,16,32,64 bit values corresponding to length 1,2,(3,4),(5,6,7,8)
177        // symbols and convert/return the value to a 16 bit unsigned int.
178        template<uint32_t L>
179        inline void push_gid(const SIMD_type value, const uint32_t count);
180 
181        template<uint32_t L>
182        void packed_bind();             
183       
184        // Debug
185        template<uint32_t L>
186        void display_packed_data(); 
187        void display_gids(); 
188        void display_gid_indices();     
189       
190#endif 
191
192#ifdef USE_SYMBOL_VALUES       
193#ifdef USE_PARALLEL_TRIE
194               
195        HeapArray2D<SIMD_type> * pfx_key_byte_splats_;                          // parallel arrays
196        HeapArray2D<SIMD_type> * pfx_index_splats_;                             // maps into the unresolved symbol values array
197       
198        HeapArray2D<unsigned char> * unresolved_symbol_values_;                 // parallel arrays
199        HeapArray2D<uint32_t> * unresolved_symbol_indices_;
200       
201        template<uint32_t L>
202        void prefix_offsets(size_t * offsets);
203       
204        template<uint32_t L>
205        void ptrie_bind(const unsigned char * unresolved_symbol_values, size_t unresolved_symbol_count, size_t * offsets);
206       
207#endif
208#endif 
209       
210#ifdef USE_FUNCTION_OBJECTS
211
212        CmpS1 cmpS1;                                                                                                    // String comparison function objects
213        CmpS2 cmpS2;
214        CmpS3 cmpS3;
215        CmpS4 cmpS4;
216        CmpS5 cmpS5;
217        CmpS6 cmpS6;
218        CmpS7 cmpS7;
219        CmpS8 cmpS8;
220        CmpS9 cmpS9;
221
222        CmpS10 cmpS10;
223        CmpS11 cmpS11;
224        CmpS12 cmpS12;
225        CmpS13 cmpS13;
226        CmpS14 cmpS14;
227        CmpS15 cmpS15;
228
229        CmpS16 cmpS16;
230
231        CmpS17 cmpS17;
232        CmpS18 cmpS18;
233        CmpS19 cmpS19;
234       
235        CmpS20 cmpS20;
236        CmpS21 cmpS21;
237        CmpS22 cmpS22;
238        CmpS23 cmpS23;
239        CmpS24 cmpS24;
240        CmpS25 cmpS25;
241        CmpS26 cmpS26;
242        CmpS27 cmpS27;
243        CmpS28 cmpS28;
244        CmpS29 cmpS29;
245        CmpS30 cmpS30;
246       
247        CmpS31 cmpS31;
248        CmpS32 cmpS32;
249               
250#endif 
251       
252       
253};
254
255
256#ifdef USE_PACKED_SYMBOLS
257// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
258// Template Declarations
259/*
260        14.7.3(2): "An explicit specialization shall be declared in the
261        namespace of which the template is a member, or, for member templates,
262        in the namespace of which the enclosing class or enclosing class
263        template is a member.           
264*/
265
266template<> inline void LSSymbolTable::push_gid<1>(const SIMD_type value, const uint32_t count);
267template<> inline void LSSymbolTable::push_gid<2>(const SIMD_type value, const uint32_t count);
268template<> inline void LSSymbolTable::push_gid<3>(const SIMD_type value, const uint32_t count);
269template<> inline void LSSymbolTable::push_gid<4>(const SIMD_type value, const uint32_t count);
270template<> inline void LSSymbolTable::push_gid<5>(const SIMD_type value, const uint32_t count);
271template<> inline void LSSymbolTable::push_gid<6>(const SIMD_type value, const uint32_t count);
272template<> inline void LSSymbolTable::push_gid<7>(const SIMD_type value, const uint32_t count);
273template<> inline void LSSymbolTable::push_gid<8>(const SIMD_type value, const uint32_t count);
274                               
275#endif
276
277#endif /* LSYMTAB_H_ */ 
278
Note: See TracBrowser for help on using the repository browser.