source: trunk/symtab/ls_symbol_table_vectors.cxx @ 4035

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

Reorganized SymbolTable? library
File size: 11.3 KB
Line 
1#include "ls_symbol_table_vectors.h"
2
3#include <iostream>
4using namespace std;
5
6LSSymbolTable::LSSymbolTable():crt_symbol_index_(0), crt_symbol_gid_(1) { // construct length bins 0,1,...32 and > 32
7       
8        this->symbol_index_.resize(LSSymbolTable::LGTH_BINS_);
9        this->symbol_value_ptr.resize(LSSymbolTable::LGTH_BINS_);
10        this->uniq_symbol_value_ptrs_.resize(LSSymbolTable::LGTH_BINS_);
11        this->uniq_symbol_gids_.resize(LSSymbolTable::LGTH_BINS_);
12        this->symbol_indices_.resize(LSSymbolTable::LGTH_BINS_);       
13       
14}
15
16LSSymbolTable::~LSSymbolTable() {}
17
18void LSSymbolTable::LSSymbolTable::put(unsigned char * code_unit_ptr, uint32_t lgth) {
19       
20        if(lgth >= this->symbol_index_.capacity()) {
21               
22                size_t next_capacity;
23                next_capacity = lgth * 2; 
24               
25                this->symbol_index_.resize(next_capacity);
26                this->symbol_value_ptr.resize(next_capacity);
27                this->uniq_symbol_value_ptrs_.resize(next_capacity);
28                this->uniq_symbol_gids_.resize(next_capacity);         
29                this->symbol_indices_.resize(next_capacity);
30               
31        }       
32       
33        this->symbol_index_[lgth].push_back(this->crt_symbol_index_);
34        this->crt_symbol_index_++;
35        this->symbol_value_ptr[lgth].push_back(code_unit_ptr);
36
37}
38
39void LSSymbolTable::bind() {
40               
41#ifdef USE_FUNCTION_OBJECTS
42        bind<1,CmpS1>(cmpS1);
43        bind<2,CmpS2>(cmpS2);
44        bind<3,CmpS3>(cmpS3);
45        bind<4,CmpS4>(cmpS4);
46        bind<5,CmpS5>(cmpS5);
47        bind<6,CmpS6>(cmpS6);
48        bind<7,CmpS7>(cmpS7);
49        bind<8,CmpS8>(cmpS8);
50        bind<9,CmpS9>(cmpS9);
51       
52        bind<10,CmpS10>(cmpS10);
53        bind<11,CmpS11>(cmpS11);
54        bind<12,CmpS12>(cmpS12);
55        bind<13,CmpS13>(cmpS13);
56        bind<14,CmpS14>(cmpS14);
57        bind<15,CmpS15>(cmpS15);
58        bind<16,CmpS16>(cmpS16);
59        bind<17,CmpS17>(cmpS17);
60        bind<18,CmpS18>(cmpS18);
61        bind<19,CmpS19>(cmpS19);
62
63        bind<20,CmpS20>(cmpS20);
64        bind<21,CmpS21>(cmpS21);
65        bind<22,CmpS22>(cmpS22);
66        bind<23,CmpS23>(cmpS23);
67        bind<24,CmpS24>(cmpS24);
68        bind<25,CmpS25>(cmpS25);
69        bind<26,CmpS26>(cmpS26);
70        bind<27,CmpS27>(cmpS27);
71        bind<28,CmpS28>(cmpS28);
72        bind<29,CmpS29>(cmpS29);
73
74        bind<30,CmpS30>(cmpS30);       
75        bind<31,CmpS31>(cmpS31);
76        bind<32,CmpS32>(cmpS32);
77#endif 
78
79#ifdef USE_FUNCTION_TEMPLATES
80        bind<1>();
81        bind<2>();
82        bind<3>();
83        bind<4>();
84        bind<5>();
85        bind<6>();
86        bind<7>();
87        bind<8>();
88        bind<9>();
89       
90        bind<10>();
91        bind<11>();
92        bind<12>();
93        bind<13>();
94        bind<14>();
95        bind<15>();
96        bind<16>();
97        bind<17>();
98        bind<18>();
99        bind<19>();
100
101        bind<20>();
102        bind<21>();
103        bind<22>();
104        bind<23>();
105        bind<24>();
106        bind<25>();
107        bind<26>();
108        bind<27>();
109        bind<28>();
110        bind<29>();
111
112        bind<30>();     
113        bind<31>();
114        bind<32>();     
115#endif
116               
117        bind_gt_32();   // lengths > 32 not known at compile time implies no opportunity to use inlined templates
118       
119        flatten_gids();
120       
121        for(int i=0;i<this->symbol_index_.capacity();i++) { // clear buffered data
122                this->symbol_index_[i].clear();
123        }
124       
125        for(int i=0;i<this->symbol_value_ptr.capacity();i++) {
126                this->symbol_value_ptr[i].clear();
127        }
128               
129}
130
131void LSSymbolTable::finalize() {
132        flatten_unique_symbol_values();
133        // TODO - Destroy temporary data structures. TBD.
134}
135// IMPORTANT: This method assumes symbols values are inserted in order of increasing lengths and for each length by order of new symbol occurence.
136void LSSymbolTable::flatten_unique_symbol_values() {
137       
138        this->gid_idx_symbol_lengths_.reserve(this->crt_symbol_gid_);                                           // Requests that the capacity of the allocated storage space be at least enough to hold n elements.
139                                                                                                                                                                                // i.e. Avoid unnecessary memory allocations.
140                                                                                                                                                                                // Reserve (capacity only) + push_back increases the vector size.
141        this->gid_idx_symbol_value_ptrs_.reserve(this->crt_symbol_gid_);
142       
143        for(int lgth=0; lgth<this->uniq_symbol_value_ptrs_.size(); lgth++) {                                    // for each unique symbol value of each length
144                for(int i=0; i<this->uniq_symbol_value_ptrs_[lgth].size(); i++) {
145                        this->gid_idx_symbol_value_ptrs_.push_back(this->uniq_symbol_value_ptrs_[lgth][i]);     // append gid
146                        this->gid_idx_symbol_lengths_.push_back(lgth);                                                          // append parallel length information
147                }
148        }
149}
150
151// IMPORTANT: Assumes GIDs are assigned in order of increasing lengths and for each length by order of new symbol occurence.
152void LSSymbolTable::flatten_gids() {
153                                                                                                                                                               
154        this->doc_idx_gids_.resize(this->crt_symbol_index_);                                            // Resizes the vector to contain sz elements. Resize (size) increases the vector size.
155                                                                                                                                                                // Array indexing alone does not increase STL vector size.
156                                                                                                                                                               
157        for(int lgth=0; lgth < this->symbol_indices_.size(); lgth++) {                          // for each key of length l
158                for(int i=0; i<this->symbol_indices_[lgth].size(); i++) {                               
159                        size_t next_gid = this->uniq_symbol_gids_[lgth][i];                                     // insert the gid at symbol index position
160                        for(int j=0; j<(this->symbol_indices_[lgth][i]).size();j++) {
161                                this->doc_idx_gids_[(this->symbol_indices_[lgth][i][j])] = next_gid;   
162                        }
163                }
164        }
165}
166
167void LSSymbolTable::clear() {
168
169        for(int i=0;i<this->symbol_index_.capacity();i++) {
170                this->symbol_index_[i].clear();
171                this->symbol_value_ptr[i].clear();
172        }
173       
174        for(int i=0;i<this->uniq_symbol_value_ptrs_.capacity();i++) {
175                this->uniq_symbol_value_ptrs_[i].clear();
176                this->uniq_symbol_gids_[i].clear();
177        }
178
179        for(int i=0;i<this->symbol_indices_.capacity();i++) {
180                for(int j=0;j<this->symbol_indices_[i].size();j++) {
181                        this->symbol_indices_[i][j].clear();
182                }
183                this->symbol_indices_[i].clear();
184        }
185       
186        this->gid_idx_symbol_lengths_.clear();
187        this->gid_idx_symbol_value_ptrs_.clear();
188       
189        this->doc_idx_gids_.clear();
190       
191        this->crt_symbol_index_ = 0;
192        this->crt_symbol_gid_ = 0;
193}
194
195void LSSymbolTable::display_lgth_dist() const {
196        cout << "display_lgth_dist()" << endl;
197        for(int lgth=0; lgth<this->symbol_indices_.capacity(); lgth++) {
198                cout << "L[" << lgth << "]" << " => "  << this->symbol_indices_[lgth].size() << endl;
199        }
200        cout << endl;
201}
202
203void LSSymbolTable::display_lgth_sorted_symbol_values_gids() const {
204        cout << "display_lgth_sorted_symbol_values_gids" << endl;
205        for(int lgth=0; lgth<this->uniq_symbol_value_ptrs_.capacity(); lgth++) {
206                cout << "L[" << lgth << "]" << " => "; 
207                for(int i=0; i<this->uniq_symbol_value_ptrs_[lgth].size(); i++) {
208                        cout << "(";
209                        cout << string((char *) (this->uniq_symbol_value_ptrs_[lgth][i]), lgth);
210                        cout << ", ";
211                        cout << this->uniq_symbol_gids_[lgth][i];
212                        cout << ") ";
213                }
214                cout << endl;
215        }
216        cout << endl;
217}
218
219void LSSymbolTable::display_symbol_values(size_t lgth, size_t key_val_index) const {
220        for(int j=0; j<this->symbol_indices_[lgth][key_val_index].size(); j++) {
221                cout << this->symbol_indices_[lgth][key_val_index][j] << " "; 
222        }       
223}
224
225void LSSymbolTable::display_lgth_key_sorted_doc_idxs() const {
226        cout << "display_lgth_key_sorted_doc_idxs()" << endl;
227        for(int lgth=0; lgth<this->symbol_indices_.capacity(); lgth++) {
228                if(this->symbol_indices_[lgth].size()<1) {
229                        cout << "L[" << lgth << "]" << endl;
230                } else {
231                        for(int i=0; i<this->symbol_indices_[lgth].size(); i++) {
232                                cout << "L[" << lgth << "]['" << string((char *) (this->uniq_symbol_value_ptrs_[lgth][i]), lgth);
233                                cout << "']" << " => ";
234                                display_symbol_values(lgth,i);
235                                cout << endl;
236                        }
237                }
238        }
239        cout << endl;
240}
241
242void LSSymbolTable::display_flattened_symbol_values() const {
243        cout << "display_flattened_symbol_values()" << endl;
244        for(int i=0; i<this->gid_idx_symbol_value_ptrs_.size();i++) {
245                cout << "GID_IDX[" << i << "] => " << string((char *)(this->gid_idx_symbol_value_ptrs_[i]), this->gid_idx_symbol_lengths_[i]) << endl;
246        }
247        cout << endl;   
248}
249
250void LSSymbolTable::display_flattened_gids() const {
251        cout << "display_flattened_gids()" << endl; 
252        cout << "DOC_IDX_GID[] => ";
253               
254        for(int i=0; i<this->doc_idx_gids_.size();i++) {
255                 cout << this->doc_idx_gids_[i] << " ";
256        }
257        cout << endl;
258}
259
260#ifdef USE_FUNCTION_OBJECTS
261        template<size_t L, class Compare>
262        inline void LSSymbolTable::bind(const Compare & compare) { 
263       
264                bool is_found;
265                size_t size = this->symbol_value_ptr[L].size();
266               
267                for(int i=0; i<size; i++) {                                                                                             // for each name of length L
268       
269                        is_found = false;
270                        size_t uniq_symbol_value_ptrs_ = this->uniq_symbol_value_ptrs_[L].size();
271                       
272                        for(int j=0; j<uniq_symbol_value_ptrs_; j++) {                                                          // for each unique key name
273       
274                                if(compare(this->symbol_value_ptr[L][i], this->uniq_symbol_value_ptrs_[L][j])){
275                                        this->symbol_indices_[L][j].push_back(this->symbol_index_[L][i]);       // found, store symbol number
276                                        is_found = true;                                                                               
277                                        break;
278                                }
279                        }
280                       
281                        if(!is_found) {                                                                                                         // not found, new unique key value
282                                // store new symbol value and gid value
283                                this->uniq_symbol_value_ptrs_[L].push_back((unsigned char *)this->symbol_value_pool_.Insert((char *)this->symbol_value_ptr[L][i],L));
284                                this->uniq_symbol_gids_[L].push_back(this->crt_symbol_gid_);
285                                this->crt_symbol_gid_++;
286                                                       
287                                // allocate new symbol index vector
288                                vector <size_t> idxs;
289                                this->symbol_indices_[L].push_back(idxs);
290                                this->symbol_indices_[L][uniq_symbol_value_ptrs_].push_back(this->symbol_index_[L][i]);                         
291                        }               
292                }
293        }
294#endif
295
296#ifdef USE_FUNCTION_TEMPLATES
297        template<size_t L>
298        inline void LSSymbolTable::bind() {
299                bool is_found;
300                size_t size = this->symbol_value_ptr[L].size();
301               
302                for(int i=0; i<size; i++) {                                                                                             // for each name of length L
303       
304                        is_found = false;
305                        size_t uniq_symbol_values_ = this->uniq_symbol_value_ptrs_[L].size();
306                       
307                        for(int j=0; j<uniq_symbol_values_; j++) {                                                              // for each unique key name
308       
309                                if(compare<L>(this->symbol_value_ptr[L][i], this->uniq_symbol_value_ptrs_[L][j])){
310                                        this->symbol_indices_[L][j].push_back(this->symbol_index_[L][i]);       // found, store symbol number
311                                        is_found = true;                                                                               
312                                        break;
313                                }
314                        }
315                       
316                        if(!is_found) {                                                                                                         // not found, new unique key value
317                                // store new symbol value and gid value
318                                this->uniq_symbol_value_ptrs_[L].push_back((unsigned char *)this->symbol_value_pool_.Insert((char *)this->symbol_value_ptr[L][i],L));
319                                this->uniq_symbol_gids_[L].push_back(this->crt_symbol_gid_);
320                                this->crt_symbol_gid_++;
321                                                       
322                                // allocate new symbol index vector
323                                vector <unsigned int> idxs;
324                                this->symbol_indices_[L].push_back(idxs);
325                                this->symbol_indices_[L][uniq_symbol_values_].push_back(this->symbol_index_[L][i]);                             
326                        }
327                       
328                }               
329        }
330#endif
331
332//Sort arrays of length 33 or greater
333void LSSymbolTable::bind_gt_32() {
334        bool is_found;
335       
336        for(int lgth=33;lgth < this->symbol_index_.capacity(); lgth++) {                        // for each length >= 33
337               
338                size_t size = this->symbol_value_ptr[lgth].size();                                              // for each name
339               
340                for(int i=0; i<size; i++) {                                                                                             // for each unique key name
341               
342                        is_found = false;
343                        size_t uniq_symbol_values_ = this->uniq_symbol_value_ptrs_[lgth].size();
344                       
345                        for(int j=0; j<uniq_symbol_values_; j++) { 
346                                if(simd_compare(this->symbol_value_ptr[lgth][i], this->uniq_symbol_value_ptrs_[lgth][j], lgth)) {
347                                //if(mem_compare(this->symbol_value_ptr[lgth][i], this->uniq_symbol_values_[lgth][j], lgth)) {
348                                        this->symbol_indices_[lgth][j].push_back(this->symbol_index_[lgth][i]); // found, store symbol number
349                                        is_found = true;                                                                               
350                                        break;                         
351                                }       
352                        }
353               
354                        if(!is_found) {                                                                                                         // not found, new unique key value
355                                // store new unique key value and parallel gid value
356                                this->uniq_symbol_value_ptrs_[lgth].push_back((unsigned char *)this->symbol_value_pool_.Insert((char *)this->symbol_value_ptr[lgth][i],lgth));
357                                this->uniq_symbol_gids_[lgth].push_back(this->crt_symbol_gid_);
358                                this->crt_symbol_gid_++;                               
359                               
360                                // allocate new symbol index vector
361                                vector <unsigned int> idxs;
362                                this->symbol_indices_[lgth].push_back(idxs);
363                                this->symbol_indices_[lgth][uniq_symbol_values_].push_back(this->symbol_index_[lgth][i]);
364                        }
365                }
366        }
367}
Note: See TracBrowser for help on using the repository browser.