source: trunk/symtab/ls_symbol_table.h @ 1588

Last change on this file since 1588 was 1229, checked in by vla24, 8 years ago

Reorganized SymbolTable? library

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