source: trunk/lib/symtab/ls_symbol_table.cxx @ 1518

Last change on this file since 1518 was 1462, checked in by vla24, 8 years ago

SymbolTable?: refactored symtab library

File size: 44.7 KB
Line 
1#include "ls_symbol_table.h"
2#include "ls_symbol_table_util.h"
3#define DEBUG 0
4#include <string>
5#include <iostream>
6#include "library_conversion.h"
7
8using namespace std;
9
10LSSymbolTable::LSSymbolTable(): crt_symbol_index_(0), crt_symbol_gid_(1) { // construct length bins 0,1,...32 and > 32
11
12        this->symbol_index_ = new HeapArray2D<uint32_t> (LSSymbolTable::LGTH_BINS_, 0, 1, sizeof(SIMD_type)); // rows, columns, chunk size, alignment   
13       
14#ifdef USE_SYMBOL_PTRS 
15        this->symbol_value_ptrs_ = new HeapArray2D<unsigned char *> (LSSymbolTable::LGTH_BINS_, 0, 1, sizeof(SIMD_type));
16#endif
17       
18#ifdef USE_SYMBOL_VALUES
19        this->symbol_values_ = new HeapArray2D<unsigned char>(LSSymbolTable::LGTH_BINS_, 0, sizeof(SIMD_type), sizeof(SIMD_type));
20#endif 
21       
22        this->uniq_symbol_values_ = new HeapArray2D<unsigned char> (LSSymbolTable::LGTH_BINS_, 0, 1, sizeof(SIMD_type));
23        this->uniq_symbol_gids_ = new HeapArray2D<uint32_t> (LSSymbolTable::LGTH_BINS_, 0, 1, sizeof(SIMD_type));
24
25#ifdef USE_LENGTH_SORT
26        this->gids_ = new HeapArray2D<uint32_t> (LSSymbolTable::LGTH_BINS_, 0, 1);
27#endif 
28
29#ifdef USE_LENGTH_AND_KEY_SORT 
30        this->symbol_indices_.resize(LSSymbolTable::LGTH_BINS_);
31#endif 
32
33#ifdef USE_PACKED_SYMBOLS
34        this->uniq_key_packed_mask_splats_ = new HeapArray2D<SIMD_type> (1+8, 0, sizeof(SIMD_type)); // 8+1 rows, 0th length row + lengths 1 through 8
35        this->uniq_key_packed_gid_masks_ = new HeapArray2D<SIMD_type> (1+8, 0, sizeof(SIMD_type));
36        this->packed_gids_ = new HeapArray2D<uint32_t> (1+8, 0, 1);
37#endif         
38
39#ifdef USE_PARALLEL_TRIE
40        this->pfx_key_byte_splats_ = new HeapArray2D<SIMD_type> (LSSymbolTable::LGTH_BINS_, 0, sizeof(SIMD_type));     
41        this->pfx_index_splats_ = new HeapArray2D<SIMD_type> (LSSymbolTable::LGTH_BINS_, 0, sizeof(SIMD_type));   
42
43        this->unresolved_symbol_values_ = new HeapArray2D<unsigned char> (LSSymbolTable::LGTH_BINS_, 0, sizeof(SIMD_type));                     
44        this->unresolved_symbol_indices_= new HeapArray2D<uint32_t> (LSSymbolTable::LGTH_BINS_, 0, sizeof(SIMD_type)); 
45#endif 
46       
47        this->gid_idx_symbol_value_ptrs_ = new HeapArray<unsigned char *>();
48        this->gid_idx_symbol_lengths_ = new HeapArray<uint32_t>();
49        this->doc_idx_gids_ = new HeapArray<uint32_t>();
50}
51
52LSSymbolTable::~LSSymbolTable() {
53        delete this->symbol_index_;
54        this->symbol_index_ = NULL;
55       
56#ifdef USE_SYMBOL_PTRS 
57        delete this->symbol_value_ptrs_;
58        this->symbol_value_ptrs_ = NULL;
59#endif 
60       
61#ifdef USE_SYMBOL_VALUES
62        delete this->symbol_values_;
63        symbol_values_ = NULL;
64#endif 
65       
66        delete this->uniq_symbol_values_;
67        this->uniq_symbol_values_ = NULL;
68       
69        delete this->uniq_symbol_gids_;
70        this->uniq_symbol_gids_ = NULL;
71
72#ifdef USE_LENGTH_SORT
73        delete this->gids_;
74        this->gids_ = NULL;
75#endif 
76       
77#ifdef USE_PACKED_SYMBOLS
78        delete this->uniq_key_packed_mask_splats_;
79        this->uniq_key_packed_mask_splats_ = NULL;
80
81        delete this->uniq_key_packed_gid_masks_;
82        this->uniq_key_packed_gid_masks_ = NULL;
83
84        delete this->packed_gids_;
85        this->packed_gids_ = NULL;
86#endif         
87
88#ifdef USE_PARALLEL_TRIE
89        delete this->pfx_key_byte_splats_;
90        this->pfx_key_byte_splats_ = NULL;
91       
92        delete this->pfx_index_splats_;
93        this->pfx_index_splats_ = NULL;
94
95        delete this->unresolved_symbol_values_;
96        this->unresolved_symbol_values_ = NULL;
97       
98        delete this->unresolved_symbol_indices_;               
99        this->unresolved_symbol_indices_ = NULL;
100#endif         
101       
102        delete this->gid_idx_symbol_value_ptrs_;
103        this->gid_idx_symbol_value_ptrs_ = NULL;
104       
105        delete this->gid_idx_symbol_lengths_;
106        this->gid_idx_symbol_lengths_ = NULL;
107       
108        delete this->doc_idx_gids_;
109        this->doc_idx_gids_ = NULL;     
110}
111
112/*
113 * Note: All symbols of length >= 8 are sorted using symbol pointers and lengths.
114 */
115void LSSymbolTable::put(unsigned char * symbol_ptr, uint32_t lgth) {
116        if (lgth >= this->symbol_index_->rows()) {
117                uint32_t next_size = (lgth << 1); 
118
119                this->symbol_index_->reserve(next_size);
120
121#ifdef USE_SYMBOL_PTRS         
122                this->symbol_value_ptrs_->reserve(next_size);
123#endif
124               
125#ifdef USE_SYMBOL_VALUES
126                this->symbol_values_->reserve(next_size);
127#endif         
128               
129                this->uniq_symbol_values_->reserve(next_size);
130                this->uniq_symbol_gids_->reserve(next_size);
131               
132#ifdef USE_LENGTH_AND_KEY_SORT         
133                this->symbol_indices_.resize(next_size);
134#endif         
135       
136        }
137
138        this->symbol_index_->push_back(lgth, this->crt_symbol_index_);
139        this->crt_symbol_index_++;
140
141#ifdef USE_SYMBOL_PTRS 
142        this->symbol_value_ptrs_->push_back(lgth, symbol_ptr);
143#endif
144       
145#ifdef USE_SYMBOL_VALUES
146#ifdef USE_PACKED_SYMBOLS       
147        switch(lgth) {
148                case 1:
149                case 2:
150                case 4:
151                case 8:
152                        this->symbol_values_->push_back_adv(lgth, symbol_ptr, lgth, 0);
153                        break;
154                case 3:
155                case 7:
156                        this->symbol_values_->push_back_adv(lgth, symbol_ptr, lgth, 1);
157                        break;
158                case 5:
159                        this->symbol_values_->push_back_adv(lgth, symbol_ptr, lgth, 3);
160                        break;
161                case 6:
162                        this->symbol_values_->push_back_adv(lgth, symbol_ptr, lgth, 2);
163                        break;
164                default:
165                        this->symbol_values_->push_back_adv(lgth, symbol_ptr, lgth, 0);
166                        break;
167        }       
168#else   
169        this->symbol_values_->push_back(lgth, symbol_ptr, lgth);
170#endif
171#endif 
172
173}
174
175void LSSymbolTable::bind() {
176
177        this->doc_idx_gids_->resize(this->crt_symbol_index_);   // Resize the array to avoid unnecessary memory allocations.   
178       
179#ifndef USE_PARALLEL_TRIE       
180#ifdef USE_PACKED_SYMBOLS         
181        this->packed_gid_mask_128_ = simd<8>::constant<0>();
182
183        packed_bind<1>();
184        this->packed_gid_mask_128_ = simd_and(simd<fw<2>::value>::lomask(),
185                        this->packed_gid_mask_128_); // clear high half fw 16
186
187        packed_bind<2>();
188        this->packed_gid_mask_128_ = simd_and(simd<fw<4>::value>::lomask(),
189                        this->packed_gid_mask_128_); // clear high half fw 32
190
191        packed_bind<3>();
192        packed_bind<4>();
193        this->packed_gid_mask_128_ = simd_and(simd<fw<8>::value>::lomask(),
194                        this->packed_gid_mask_128_); // clear high half fw 64
195       
196        packed_bind<5>();
197        packed_bind<6>();
198        packed_bind<7>();
199        packed_bind<8>();
200
201        this->crt_symbol_gid_ = *((uint32_t *) (&this->packed_gid_mask_128_)); // glue packed symbols and non-packed symbols, i.e. convert the current gid to a non-packed gid value
202        this->crt_symbol_gid_++;
203#endif 
204       
205#ifdef USE_FUNCTION_OBJECTS
206#ifndef USE_PACKED_SYMBOLS       
207        bind<1,CmpS1>(cmpS1);
208        bind<2,CmpS2>(cmpS2);
209        bind<3,CmpS3>(cmpS3);
210        bind<4,CmpS4>(cmpS4);
211        bind<5,CmpS5>(cmpS5);
212        bind<6,CmpS6>(cmpS6);
213        bind<7,CmpS7>(cmpS7);
214        bind<8,CmpS8>(cmpS8);
215#endif
216        bind<9,CmpS9>(cmpS9);
217        bind<10,CmpS10>(cmpS10);
218        bind<11,CmpS11>(cmpS11);
219        bind<12,CmpS12>(cmpS12);
220        bind<13,CmpS13>(cmpS13);
221        bind<14,CmpS14>(cmpS14);
222        bind<15,CmpS15>(cmpS15);
223        bind<16,CmpS16>(cmpS16);
224        bind<17,CmpS17>(cmpS17);
225        bind<18,CmpS18>(cmpS18);
226        bind<19,CmpS19>(cmpS19);
227
228        bind<20,CmpS20>(cmpS20);
229        bind<21,CmpS21>(cmpS21);
230        bind<22,CmpS22>(cmpS22);
231        bind<23,CmpS23>(cmpS23);
232        bind<24,CmpS24>(cmpS24);
233        bind<25,CmpS25>(cmpS25);
234        bind<26,CmpS26>(cmpS26);
235        bind<27,CmpS27>(cmpS27);
236        bind<28,CmpS28>(cmpS28);
237        bind<29,CmpS29>(cmpS29);
238
239        bind<30,CmpS30>(cmpS30);
240        bind<31,CmpS31>(cmpS31);
241        bind<32,CmpS32>(cmpS32);
242#endif 
243       
244#ifdef USE_FUNCTION_TEMPLATES
245
246#ifndef USE_PACKED_SYMBOLS     
247        bind<1>();
248        bind<2>();
249        bind<3>();
250        bind<4>();
251        bind<5>();
252        bind<6>();
253        bind<7>();
254        bind<8>();
255        flatten_gids();
256#endif 
257        bind<9>();
258        bind<10>();
259        bind<11>();
260        bind<12>();
261        bind<13>();
262        bind<14>();
263        bind<15>();
264        bind<16>();
265//      bind<17>();
266//      bind<18>();
267//      bind<19>();
268
269//      bind<20>();
270//      bind<21>();
271//      bind<22>();
272//      bind<23>();
273//      bind<24>();
274//      bind<25>();
275//      bind<26>();
276//      bind<27>();
277//      bind<28>();
278//      bind<29>();
279
280//      bind<30>();
281//      bind<31>();
282//      bind<32>();
283#endif 
284#endif
285       
286#ifdef USE_PARALLEL_TRIE
287               
288        size_t unresolved_symbol_value_count;
289        // single byte prefix gather offsets
290        size_t offsets[sizeof(SIMD_type)];// = {0,L,2*L,3*L,4*L,5*L,6*L,7*L,8*L,9*L,10*L,11*L,12*L,13*L,14*L,15*L};
291               
292        // two byte prefix gather offsets
293        // unsigned char prefix_offsets[16] = {0,1,L,L+1,2*L,2*L+1,3*L,3*L+1,4*L,4*L+1,5*L,5*L+1,6*L,6*L+1,7*L,7*L+1};
294       
295        /*
296        ptrie_bind<1>();
297        ptrie_bind<2>();
298        ptrie_bind<3>();
299        ptrie_bind<4>();
300        ptrie_bind<5>();
301        ptrie_bind<6>();
302        ptrie_bind<7>();
303        ptrie_bind<8>();       
304        ptrie_bind<9>();
305        */
306        unresolved_symbol_value_count = this->symbol_values_->size(10)/10; 
307        prefix_offsets<10>(offsets);
308        ptrie_bind<10>(&this->symbol_values_->get(10,0), unresolved_symbol_value_count, offsets);
309       
310        /*
311        ptrie_bind<11>();
312        ptrie_bind<12>();
313        ptrie_bind<13>();
314        ptrie_bind<14>();
315        ptrie_bind<15>();
316        ptrie_bind<16>();
317        ptrie_bind<17>();
318        ptrie_bind<18>();
319        ptrie_bind<19>();
320
321        ptrie_bind<20>();
322        ptrie_bind<21>();
323        ptrie_bind<22>();
324        ptrie_bind<23>();
325        ptrie_bind<24>();
326        ptrie_bind<25>();
327        ptrie_bind<26>();
328        ptrie_bind<27>();
329        ptrie_bind<28>();
330        ptrie_bind<29>();
331
332        ptrie_bind<30>();
333        ptrie_bind<31>();
334        ptrie_bind<32>();
335        */     
336#endif                 
337       
338        /*bind_gt_32();*/ // bind all lengths > 32, this information is not known at compile time, and hence function call overhead and not inline template functions
339        bind_gt(17);
340        // TODO - flatten_gids may not be required.
341        // flatten_gids(); // flatten 2D length sorted gid values into a 1D document indexed array of GID values  TODO TBD.
342
343        this->symbol_index_->clear(); // clear 2D array of document indices
344
345#ifdef USE_LENGTH_SORT
346        this->gids_->clear(); // clear 2D parallel array of gid values
347#endif 
348
349#ifdef USE_SYMBOL_PTRS 
350        this->symbol_value_ptrs_->clear();
351#endif         
352       
353#ifdef USE_SYMBOL_VALUES
354        this->symbol_values_->clear();
355#endif 
356       
357#ifdef USE_PACKED_SYMBOLS
358        this->packed_gids_->clear();
359#endif
360
361#ifdef USE_LENGTH_AND_KEY_SORT 
362        for(size_t i=0;i<this->symbol_indices_.capacity();i++) {
363                for(size_t j=0;j<this->symbol_indices_[i].size();j++) {
364                        this->symbol_indices_[i][j].resize(0);
365                }
366        }
367#endif
368       
369}
370
371void LSSymbolTable::finalize() {
372        flatten_unique_symbol_values();
373        // TODO - Destroy temporary data structures. TBD.
374}
375 
376/*
377 * Description: Converts 2D length sorted unique symbols values to a pair of parallel 1D GID indexed parallel symbol pointer and length arrays.
378 *
379 * Note: To construct the GID indexed arrays, this method requires that unique symbols values are assigned GIDs inserted into the original 2D array
380 *       in order of increasing length and are assigned GIDs in order of new symbol occurrences.
381 *       
382 * Warning: Since pointers to unique symbol values are maintained in the 1D array, gid_idx_symbol_value_ptrs_ must only be destroyed
383 *          with the destruction of the complete Symbol Table object.     
384 *         
385 *          TODO - Consider the option of copying values from the 2D arrays into 1D arrays to allow for array clean up.
386 */
387void LSSymbolTable::flatten_unique_symbol_values() {
388
389        this->gid_idx_symbol_value_ptrs_->resize(this->crt_symbol_gid_-1);
390        this->gid_idx_symbol_lengths_->resize(this->crt_symbol_gid_-1);
391       
392        size_t symbol_index = 0;
393        for (size_t lgth = 0; lgth < this->uniq_symbol_values_->rows(); lgth++) { // for each length, for each unique symbol value pointer, store pointer and length 1D
394                for (size_t i = 0; i < this->uniq_symbol_values_->size(lgth); i += lgth) {
395//                      this->gid_idx_symbol_value_ptrs_->push_back(&this->uniq_symbol_values_->get(lgth, i));
396//                      this->gid_idx_symbol_lengths_->push_back(lgth);
397                        this->gid_idx_symbol_value_ptrs_->set(symbol_index,&this->uniq_symbol_values_->get(lgth, i)); 
398                        this->gid_idx_symbol_lengths_->set(symbol_index,lgth);
399                        symbol_index++;
400                }
401        }
402}
403
404/*
405 * Description: Essentially a scatter operation. Scatters 2D length sorted resolved GID values into a 1D document indexed array of gid values (unique numeric identifiers).   
406 */
407void LSSymbolTable::flatten_gids() {
408
409        uint32_t lgth = 0;
410        uint32_t next_gid = 0;
411       
412#ifdef USE_PACKED_SYMBOLS               
413        for (lgth; lgth < this->packed_gids_->rows(); lgth++) { // for each symbol of each length, for each GID in each GID pack, flatten into a 1D array of document gid values
414                for (size_t i = 0; i < this->packed_gids_->size(lgth); i++) {
415                        next_gid = this->packed_gids_->get(lgth, i);   
416                        this->doc_idx_gids_->set(this->symbol_index_->get(lgth, i),     next_gid);
417                }
418        }
419#endif
420
421/*
422TODO - Not required.
423
424#ifdef USE_LENGTH_SORT
425        for (lgth; lgth < this->gids_->rows(); lgth++) { // for each symbol of each length, glue gid values onto the 1D array of document indexed gid values
426                for (size_t i = 0; i < this->gids_->size(lgth); i++) {
427                        next_gid = this->gids_->get(lgth, i);           
428                        this->doc_idx_gids_->set(this->symbol_index_->get(lgth, i),     next_gid);
429                }
430        }
431#endif         
432*/
433
434#ifdef USE_LENGTH_AND_KEY_SORT 
435        for(lgth; lgth < this->symbol_indices_.size(); lgth++) { // for each key of length l
436                for(size_t i=0; i<this->symbol_indices_[lgth].size(); i++) {
437                        next_gid = this->uniq_symbol_gids_->get(lgth,i); // insert the gid at symbol index position
438                        for(size_t j=0; j<(this->symbol_indices_[lgth][i]).size();j++) {
439                                this->doc_idx_gids_->set((this->symbol_indices_[lgth][i][j]), next_gid);
440                        }
441                }
442        }
443#endif
444
445}
446
447/*
448 * Description: Sets size of all symbol table arrays to 0. No memory de-allocation is performed.
449 */
450void LSSymbolTable::clear() {
451
452        this->symbol_index_->clear();
453       
454        #ifdef USE_SYMBOL_PTRS 
455                this->symbol_value_ptrs_->clear();
456        #endif
457       
458        #ifdef USE_SYMBOL_VALUES
459                this->symbol_values_->clear();
460        #endif 
461       
462        this->uniq_symbol_values_->clear();
463        this->uniq_symbol_gids_->clear();
464
465#ifdef USE_LENGTH_SORT
466        this->gids_->clear();
467#endif         
468
469#ifdef USE_LENGTH_AND_KEY_SORT 
470        for(size_t i=0;i<this->symbol_indices_.capacity();i++) {
471                for(size_t j=0;j<this->symbol_indices_[i].size();j++) {
472                        this->symbol_indices_[i][j].clear();
473                }
474                this->symbol_indices_[i].clear();
475        }
476#endif
477
478#ifdef USE_PACKED_SYMBOLS
479        this->uniq_key_packed_mask_splats_->clear();
480        this->uniq_key_packed_gid_masks_->clear();
481        this->packed_gids_->clear();
482#endif         
483       
484        this->gid_idx_symbol_lengths_->clear();
485        this->gid_idx_symbol_value_ptrs_->clear();
486        this->doc_idx_gids_->clear();
487
488        this->crt_symbol_gid_ = 0;
489}
490
491void LSSymbolTable::display_lgth_dist() const {
492        cout << "display_lgth_dist()" << endl;
493
494#ifdef USE_LENGTH_SORT 
495        for (size_t lgth = 0; lgth < this->symbol_index_->rows(); lgth++) {
496                cout << "L[" << lgth << "]" << " => "
497                                << this->symbol_index_->size(lgth) << endl;
498        }
499#endif
500
501#ifdef USE_LENGTH_AND_KEY_SORT 
502        for(size_t lgth=0; lgth<this->symbol_indices_.capacity(); lgth++) {
503                cout << "L[" << lgth << "]" << " => " << this->symbol_index_->size(lgth) << endl;
504        }
505#endif
506
507        cout << endl;
508}
509
510void LSSymbolTable::display_flattened_symbol_values() const {
511        cout << "display_flattened_symbol_values()" << endl;
512
513        for (size_t i = 0; i < this->gid_idx_symbol_lengths_->size(); i++) {
514                cout << "GID[" << i << "] => " << string(
515                                (char *) (this->gid_idx_symbol_value_ptrs_->get(i)),
516                                this->gid_idx_symbol_lengths_->get(i)) << endl;
517        }
518
519        cout << endl;
520}
521
522void LSSymbolTable::display_flattened_gids() const {
523        cout << "display_flattened_gids()" << endl;
524        cout << "DOC_IDX_GID[] => ";
525
526        for (size_t i = 0; i < this->doc_idx_gids_->size(); i++) {
527                cout << this->doc_idx_gids_->get(i) << " ";
528        }
529        cout << endl;
530}
531
532#ifdef USE_FUNCTION_OBJECTS
533
534template<uint32_t L, class Compare>
535inline void LSSymbolTable::bind(const Compare & compare) {
536
537        bool is_found;
538        uint32_t size;
539        uint32_t step;
540        bool is_equal;
541        unsigned char * uniq_key;
542               
543#ifdef USE_SYMBOL_PTRS 
544        size = this->symbol_value_ptrs_->size(L);
545        step = 1;
546#endif
547       
548#ifdef USE_SYMBOL_VALUES
549        size = this->symbol_values_->size(L);
550        step = L;
551#endif 
552       
553        for (size_t sym_val_idx = 0, sym_idx = 0; sym_val_idx < size; sym_val_idx+=step, sym_idx++) { // for each name of length L                     
554                is_found = false;
555                uint32_t uniq_symbol_value_bytes_ = this->uniq_symbol_values_->size(L);
556
557                uint32_t k = 0;
558                for (size_t j = 0; j < uniq_symbol_value_bytes_; j += L, k++) { // for each unique key name
559
560#ifdef USE_SYMBOL_PTRS                 
561                is_equal = compare(this->symbol_value_ptrs_->get(L,sym_val_idx), &this->uniq_symbol_values_->get(L,j));         
562#endif
563               
564#ifdef USE_SYMBOL_VALUES
565                is_equal = compare(&this->symbol_values_->get(L,sym_val_idx), &this->uniq_symbol_values_->get(L,j));
566#endif         
567                if(is_equal) {
568                               
569#ifdef USE_LENGTH_SORT         
570                                //this->gids_->push_back(L, this->uniq_symbol_gids_->get(L, k));
571                                this->doc_idx_gids_->set(this->symbol_index_->get(L,sym_idx), this->uniq_symbol_gids_->get(L, k));                             
572#endif
573
574#ifdef USE_LENGTH_AND_KEY_SORT                         
575                                this->symbol_indices_[L][k].push_back(this->symbol_index_->get(L,sym_val_idx)); // found, store symbol number
576#endif                         
577
578                                is_found = true;
579                                break;
580                        }
581                }
582
583                if (!is_found) { // not found, new unique key value
584                        // store new symbol value and gid value
585                        #ifdef USE_SYMBOL_PTRS                 
586                                uniq_key = this->symbol_value_ptrs_->get(L, sym_val_idx);
587                        #endif
588                               
589                        #ifdef USE_SYMBOL_VALUES
590                                uniq_key = &this->symbol_values_->get(L, sym_val_idx); 
591                        #endif
592                                       
593                        this->uniq_symbol_values_->push_back(L, uniq_key, L); // push a copy of the key value
594                        this->uniq_symbol_gids_->push_back(L, this->crt_symbol_gid_);
595
596#ifdef USE_LENGTH_SORT                         
597                        // this->gids_->push_back(L, this->crt_symbol_gid_);
598                        this->doc_idx_gids_->set(this->symbol_index_->get(L,sym_idx), this->crt_symbol_gid_);                   
599#endif
600                        this->crt_symbol_gid_++;
601
602#ifdef USE_LENGTH_AND_KEY_SORT                 
603                        // allocate new symbol index vector
604                        vector <uint32_t> idxs;
605                        this->symbol_indices_[L].push_back(idxs);
606                        this->symbol_indices_[L][k].push_back(this->symbol_index_->get(L,sym_val_idx));
607#endif                 
608                }
609        }       
610       
611}
612#endif 
613
614#ifdef USE_FUNCTION_TEMPLATES
615
616template<uint32_t L>
617inline void LSSymbolTable::bind() {
618        bool is_found;
619        uint32_t size;
620        uint32_t step;
621        bool is_equal;
622        unsigned char * uniq_key;
623               
624        #ifdef USE_SYMBOL_PTRS 
625                size = this->symbol_value_ptrs_->size(L);
626                step = 1;
627        #endif
628               
629        #ifdef USE_SYMBOL_VALUES
630                size = this->symbol_values_->size(L);
631                step = L;
632        #endif         
633
634        for (size_t sym_val_idx = 0, sym_idx = 0; sym_val_idx < size; sym_val_idx+=L, sym_idx++) { // for each name of length L
635
636                is_found = false;
637                uint32_t uniq_symbol_value_bytes_ = this->uniq_symbol_values_->size(L);
638
639                uint32_t k = 0;
640                for (size_t j = 0; j < uniq_symbol_value_bytes_; j += L, k++) { // for each unique key name
641
642#ifdef USE_SYMBOL_PTRS                 
643                is_equal = compare<L> (this->symbol_value_ptrs_->get(L, sym_val_idx), &this->uniq_symbol_values_->get(L, j));
644#endif
645               
646#ifdef USE_SYMBOL_VALUES
647                is_equal = compare<L> (&this->symbol_values_->get(L, sym_val_idx), &this->uniq_symbol_values_->get(L, j));
648#endif         
649                if(is_equal) {
650
651#ifdef USE_LENGTH_SORT                         
652                                // this->gids_->push_back(L, this->uniq_symbol_gids_->get(L, k));
653                            this->doc_idx_gids_->set(this->symbol_index_->get(L,sym_idx),       this->uniq_symbol_gids_->get(L, k));
654                           
655#endif
656
657#ifdef USE_LENGTH_AND_KEY_SORT                         
658                                this->symbol_indices_[L][k].push_back(this->symbol_index_->get(L,sym_val_idx)); // found, store symbol number
659#endif                         
660
661                                is_found = true;
662                                break;
663                        }
664                }
665
666                if (!is_found) { // not found, new unique key value
667                        // store new symbol value and gid value
668                        #ifdef USE_SYMBOL_PTRS 
669                                uniq_key = this->symbol_value_ptrs_->get(L, sym_val_idx); 
670                        #endif
671                               
672                        #ifdef USE_SYMBOL_VALUES
673                                uniq_key = &this->symbol_values_->get(L, sym_val_idx);
674                        #endif                         
675                       
676                        this->uniq_symbol_values_->push_back(L, uniq_key, L);
677                        this->uniq_symbol_gids_->push_back(L, this->crt_symbol_gid_);
678
679#ifdef USE_LENGTH_SORT                         
680                        //this->gids_->push_back(L, this->crt_symbol_gid_);
681                        this->doc_idx_gids_->set(this->symbol_index_->get(L,sym_idx), this->crt_symbol_gid_);                   
682#endif
683                        this->crt_symbol_gid_++;
684
685#ifdef USE_LENGTH_AND_KEY_SORT                 
686                        // allocate new symbol index vector
687                        vector <uint32_t> idxs;
688                        this->symbol_indices_[L].push_back(idxs);
689                        this->symbol_indices_[L][k].push_back(this->symbol_index_->get(L,sym_val_idx));
690#endif                 
691                }
692        }
693}
694
695#endif
696
697//Sort arrays of length 33 or greater
698void LSSymbolTable::bind_gt(int max_lgth) {
699
700        bool is_found;
701        uint32_t size;
702        uint32_t step;
703        bool is_equal;
704        unsigned char * uniq_key;       
705
706        for (size_t lgth = max_lgth+1; lgth < this->symbol_index_->rows(); lgth++) { // for each length >= 33
707
708                #ifdef USE_SYMBOL_PTRS 
709                        size = this->symbol_value_ptrs_->size(lgth);
710                        step = 1;
711                #endif
712                       
713                #ifdef USE_SYMBOL_VALUES
714                        size = this->symbol_values_->size(lgth);
715                        step = lgth;
716                #endif                 
717               
718                for (size_t sym_val_idx = 0, sym_idx = 0; sym_val_idx < size; sym_val_idx+=step, sym_idx++) { // for each unique key name
719               
720                        is_found = false;
721                        uint32_t uniq_symbol_value_bytes_ =     this->uniq_symbol_values_->size(lgth);
722
723                        uint32_t k = 0;
724                        for (size_t j = 0; j < uniq_symbol_value_bytes_; j += lgth, k++) { // for each unique key name
725
726                                #ifdef USE_SYMBOL_PTRS 
727                                        is_equal = simd_compare(this->symbol_value_ptrs_->get(lgth, sym_val_idx), &this->uniq_symbol_values_->get(lgth, j), lgth); 
728                                        //is_equal = mem_compare(this->symbol_value_ptr_[lgth][i], this->uniq_symbol_values_[lgth][j], lgth);
729                                #endif
730                                       
731                                #ifdef USE_SYMBOL_VALUES
732                                        is_equal = simd_compare(&this->symbol_values_->get(lgth, sym_val_idx), &this->uniq_symbol_values_->get(lgth, j), lgth);
733                                #endif                                                 
734                               
735                                if (is_equal) {
736
737#ifdef USE_LENGTH_SORT                         
738                                        // this->gids_->push_back(lgth, this->uniq_symbol_gids_->get(lgth, k));
739                                        this->doc_idx_gids_->set(this->symbol_index_->get(lgth, sym_idx), this->uniq_symbol_gids_->get(lgth, k));
740
741#endif
742
743#if USE_LENGTH_AND_KEY_SORT                                     
744                                        this->symbol_indices_[lgth][k].push_back(this->symbol_index_->get(lgth,sym_val_idx)); // found, store symbol number
745#endif
746                                        is_found = true;
747                                        break;
748                                }
749                        }
750
751                        if (!is_found) { // not found, new unique key value
752                                // store new unique key value and parallel gid value
753                                #ifdef USE_SYMBOL_PTRS 
754                                        uniq_key = this->symbol_value_ptrs_->get(lgth, sym_val_idx); 
755                                #endif
756                                       
757                                #ifdef USE_SYMBOL_VALUES
758                                        uniq_key = &this->symbol_values_->get(lgth, sym_val_idx);
759                                #endif 
760                               
761                                this->uniq_symbol_values_->push_back(lgth, uniq_key, lgth);
762                                this->uniq_symbol_gids_->push_back(lgth, this->crt_symbol_gid_);
763#ifdef USE_LENGTH_SORT                         
764                                //this->gids_->push_back(lgth, this->crt_symbol_gid_);
765                                this->doc_idx_gids_->set(this->symbol_index_->get(lgth,sym_idx), this->crt_symbol_gid_);
766#endif                         
767                                this->crt_symbol_gid_++;
768#if USE_LENGTH_AND_KEY_SORT                             
769                                // allocate new symbol index vector
770                                vector <uint32_t> idxs;
771                                this->symbol_indices_[lgth].push_back(idxs);
772                                this->symbol_indices_[lgth][k].push_back(this->symbol_index_->get(lgth,sym_val_idx));
773#endif                         
774                        }
775                }
776        }
777}
778
779#ifdef USE_PACKED_SYMBOLS // Short symbol optimization
780/*
781 * Note: Full packs and partial packs are placed in separate loops for two reasons: the logic is clearer and conditional branches are slightly less.
782 */
783template<uint32_t L>
784void LSSymbolTable::packed_bind() {
785        uint32_t pack_count = SYMBOL_PACK_COUNT[L];                                                             // symbols per SIMD register
786       
787        uint32_t symbol_count = 0;
788        uint32_t non_packed_symbol_count = 0;
789        uint32_t packed_symbol_count = 0;
790       
791        #ifdef USE_SYMBOL_PTRS
792                symbol_count = this->symbol_value_ptrs_->size(L);
793                non_packed_symbol_count = symbol_count & (pack_count - 1);     
794                packed_symbol_count = symbol_count - non_packed_symbol_count;
795        #endif
796               
797        #ifdef USE_SYMBOL_VALUES
798                symbol_count = this->symbol_values_->size(L)/SYMBOL_BYTES[L];
799                non_packed_symbol_count = symbol_count & (pack_count - 1);     
800                packed_symbol_count = symbol_count - non_packed_symbol_count;
801        #endif 
802                               
803        uint16_t exit_cond_mask_16 = 0xFFFF;
804        uint16_t done_mask_16 = 0;
805
806        SIMD_type result_gid = simd<1>::constant<0>();
807        SIMD_type crt_gid_mask_128 = simd<1>::constant<0>();
808        SIMD_type cmp_eq_mask_128 = simd<1>::constant<0>();
809
810        SIMD_type crt_uniq_key_mask_splat_128 = simd<1>::constant<0>();
811        SIMD_type key_mask_splat_128 = simd<1>::constant<0>();
812
813        SIMD_type crt_symbol_pack;
814        uint32_t uniq_key_mask_splats_index = 0;
815
816        /*
817         * Splat an initial key mask and gid pack.
818         */
819        if (symbol_count > 0) {
820                               
821                #ifdef USE_SYMBOL_PTRS
822                        key_mask_splat_128 =key_mask_splat<fw<L>::value> ((const unsigned char *) this->symbol_value_ptrs_->get(L, 0));         
823                #endif
824                       
825                #ifdef USE_SYMBOL_VALUES
826                        key_mask_splat_128 =key_mask_splat<fw<L>::value> ((const unsigned char *) &this->symbol_values_->get(L, 0));           
827                #endif                 
828                                       
829                uniq_key_packed_mask_splats_->push_back(L, key_mask_splat_128);
830                packed_gid_mask_128_ = inc<fw<L>::value> (packed_gid_mask_128_);
831                uniq_key_packed_gid_masks_->push_back(L, packed_gid_mask_128_);
832               
833                #ifdef USE_SYMBOL_PTRS
834                        this->uniq_symbol_values_->push_back(L, this->symbol_value_ptrs_->get(L, 0), L); // push_back an address makes copy of the value
835                #endif 
836                       
837                #ifdef USE_SYMBOL_VALUES
838                        this->uniq_symbol_values_->push_back(L,&this->symbol_values_->get(L,0),L);               // push_back an address makes copy of the value
839                #endif                 
840        }
841
842        /*
843         * Full symbol packs.
844         */     
845        size_t sym_idx=0;
846        size_t sym_val_idx=0;                                                                   // symbol index
847        size_t step=0;
848        size_t limit = 0;
849        size_t next_gid=0;
850
851        #ifdef USE_SYMBOL_PTRS 
852                step = pack_count;
853                limit = packed_symbol_count;                    // full SIMD packs in terms of symbol bytes rounded up to the next power of 2
854        #endif
855       
856        #ifdef USE_SYMBOL_VALUES
857                step = sizeof(SIMD_type);
858                limit = packed_symbol_count * SYMBOL_BYTES[L];          // full SIMD packs in terms of bytes, step sizeof(SIMD_type) bytes at a time
859        #endif
860       
861        for(sym_val_idx=0;sym_val_idx<limit;sym_val_idx+=step) { 
862               
863                #ifdef USE_SYMBOL_PTRS
864                        crt_symbol_pack = set<fw<L>::value> (&(this->symbol_value_ptrs_->get(L, sym_val_idx))); // set next symbol pack
865                #endif
866                       
867                #ifdef USE_SYMBOL_VALUES
868                        crt_symbol_pack = sisd_load_aligned((SIMD_type *)&this->symbol_values_->get(L,sym_val_idx));   
869                #endif 
870                       
871                cmp_eq_mask_128 = simd<1>::constant<0>();
872                done_mask_16 = 0;
873                uniq_key_mask_splats_index = 0;
874
875                while (1) { // compare a 'symbol pack' of symbols until all symbols in the pack are matched
876
877                        crt_uniq_key_mask_splat_128 = uniq_key_packed_mask_splats_->get(L, uniq_key_mask_splats_index); // get next SIMD key splat
878                        crt_gid_mask_128 = uniq_key_packed_gid_masks_->get(L, uniq_key_mask_splats_index);                              // get parallel gid splat 
879
880#ifdef USE_SIMD_AND
881                        cmp_eq_mask_128 = simd<fw<L>::value>::eq(crt_symbol_pack, crt_uniq_key_mask_splat_128);                 // SIMD compare value against key splat
882#endif                 
883
884#ifdef USE_SSE_4_2     
885                        cmp_eq_mask_128 = _mm_cmpestrm(crt_uniq_key_mask_splat_128, L, crt_symbol_pack, sizeof(SIMD_type), _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ORDERED | _SIDD_UNIT_MASK);
886                        cmp_eq_mask_128 = umask_2_smask<fw<L>::value>(cmp_eq_mask_128);
887#endif
888
889                        result_gid = simd_or(result_gid, simd_and(cmp_eq_mask_128, crt_gid_mask_128));
890                        done_mask_16 |= simdLibConvert<8>::movemask(cmp_eq_mask_128);
891
892#ifdef SYMBOL_TABLE_DEBUG
893                        print_simd_register("Symbol Pack", crt_symbol_pack);
894                        print_simd_register("Key Splat", crt_uniq_key_mask_splat_128);
895                        print_simd_register("Symbols AND Keys", cmp_eq_mask_128);
896                        print_simd_register("GID Mask", crt_gid_mask_128);
897                        print_simd_register("GIDs OR (Symbols AND Keys)", result_gid);
898                        print_general_register_32("Done Mask (16 bit)", done_mask_16);
899                        print_general_register_32("Exit Mask (16 bit)", exit_cond_mask_16);
900                        cout << endl;
901#endif
902
903                        if (exit_cond_mask_16 == done_mask_16) {
904
905                                if(DEBUG)cout << "L " << L << " pack_count " << pack_count << endl;
906                               
907                                // Set gids
908                                for(size_t gid_idx=0, simd_register_offset=0; gid_idx < pack_count; gid_idx++, simd_register_offset+=(bin<L>::value)) {
909                                        next_gid = (size_t) *((( (unsigned char *) &result_gid) )+simd_register_offset);
910                                        this->doc_idx_gids_->set(this->symbol_index_->get(L, sym_idx), next_gid);
911                                        sym_idx++;
912                                }
913
914                                result_gid = simd<1>::constant<0>();    // clear gid pack
915                                break;
916                        }
917
918                        if ((++uniq_key_mask_splats_index) == uniq_key_packed_mask_splats_->size(L)) { // add a new unique key and gid masks
919                                uint32_t i = bsf(~done_mask_16); // find 'pointer arithmetic' offset to a symbol yet to be matched
920                                crt_uniq_key_mask_splat_128 =key_mask_splat<fw<L>::value> ((const unsigned char *) (&crt_symbol_pack) + i); //gather/splat a new unique key mask
921
922#ifdef SYMBOL_TABLE_DEBUG
923                                print_simd_register("New Key Mask", crt_uniq_key_mask_splat_128);
924                                print_simd_register("New GID Mask", packed_gid_mask_128_);
925#endif
926                                uniq_key_packed_mask_splats_->push_back(L, crt_uniq_key_mask_splat_128);
927                                packed_gid_mask_128_ = inc<fw<L>::value> (packed_gid_mask_128_);
928                                uniq_key_packed_gid_masks_->push_back(L, packed_gid_mask_128_);
929                               
930                                this->uniq_symbol_values_->push_back(L, (const unsigned char *) (&crt_symbol_pack) + i, L); // this index does not track the array positions, it tracks the register position
931                        }
932                }
933        }
934
935        /*
936         * Partial symbol packs.
937         */                     
938        if(non_packed_symbol_count != 0) {
939
940                cmp_eq_mask_128 = simd<1>::constant<0>();
941                done_mask_16 = 0;
942                uniq_key_mask_splats_index = 0;
943               
944                #ifdef USE_SYMBOL_PTRS
945                        crt_symbol_pack = set<fw<L>::value> (&(this->symbol_value_ptrs_->get(L, sym_val_idx)), non_packed_symbol_count); // set next symbol pack
946                #endif
947                       
948                #ifdef USE_SYMBOL_VALUES
949                        crt_symbol_pack = sisd_load_aligned((SIMD_type *)&this->symbol_values_->get(L,sym_val_idx));   
950                #endif                 
951               
952                uint32_t mask_bits = (sizeof(SIMD_type) / pack_count) * (non_packed_symbol_count);
953                exit_cond_mask_16 = 1; 
954                exit_cond_mask_16 <<= mask_bits;
955                exit_cond_mask_16 -= 1;
956                       
957                while(1) {
958
959                        crt_uniq_key_mask_splat_128 = uniq_key_packed_mask_splats_->get(L, uniq_key_mask_splats_index); // get next SIMD key splat
960                        crt_gid_mask_128 = uniq_key_packed_gid_masks_->get(L, uniq_key_mask_splats_index); // get parallel gid splat 
961
962#ifdef USE_SIMD_AND
963                        cmp_eq_mask_128 = simd<fw<L>::value>::eq(crt_symbol_pack, crt_uniq_key_mask_splat_128); // SIMD compare value against key splat
964#ifdef SYMBOL_TABLE_DEBUG
965                        print_simd_register("cmp_eq_mask_128", cmp_eq_mask_128);
966#endif                 
967#endif                 
968
969#ifdef USE_SSE_4_2     
970                        cmp_eq_mask_128 = _mm_cmpestrm(crt_uniq_key_mask_splat_128, L, crt_symbol_pack, sizeof(SIMD_type), _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ORDERED | _SIDD_UNIT_MASK);
971                        cmp_eq_mask_128 = umask_2_smask<fw<L>::value>(cmp_eq_mask_128);
972#ifdef SYMBOL_TABLE_DEBUG
973                        print_simd_register("cmp_eq_mask_128",cmp_eq_mask_128);
974#endif                 
975#endif
976                        result_gid = simd_or(result_gid, simd_and(cmp_eq_mask_128, crt_gid_mask_128));
977                        done_mask_16 |= simdLibConvert<8>::movemask(cmp_eq_mask_128);
978                                               
979                        if(exit_cond_mask_16 == done_mask_16) {
980
981                                for(size_t gid_idx=0, crt_sym_idx=sym_idx, simd_register_offset=0; gid_idx < non_packed_symbol_count; gid_idx++, crt_sym_idx++, simd_register_offset+=(bin<L>::value)) {
982                                        next_gid = (size_t) *((( (unsigned char *) &result_gid) )+simd_register_offset);
983                                        this->doc_idx_gids_->set(this->symbol_index_->get(L, crt_sym_idx), next_gid);
984                                }
985                                break;
986                        }
987
988                        if ((++uniq_key_mask_splats_index) == uniq_key_packed_mask_splats_->size(L)) { // add a new unique key and gid masks
989                                uint32_t i = bsf(~done_mask_16); // find 'pointer arithmetic' offset to a symbol yet to be matched
990                                crt_uniq_key_mask_splat_128 =key_mask_splat<fw<L>::value> ((const unsigned char *) (&crt_symbol_pack) + i); //gather/splat a new unique key mask
991
992#ifdef SYMBOL_TABLE_DEBUG
993                                print_general_register_32("Done Mask (16 bit)", done_mask_16);
994                                print_simd_register("Next Key Mask", crt_uniq_key_mask_splat_128);
995                                print_simd_register("Next GID Mask", packed_gid_mask_128_);
996#endif
997                                uniq_key_packed_mask_splats_->push_back(L, crt_uniq_key_mask_splat_128);
998                                packed_gid_mask_128_ = inc<fw<L>::value> (packed_gid_mask_128_);
999                                uniq_key_packed_gid_masks_->push_back(L, packed_gid_mask_128_);
1000                               
1001                                this->uniq_symbol_values_->push_back(L, (const unsigned char *) (&crt_symbol_pack) + i, L); // this index does not track the array positions, it tracks the register position
1002                        }                                               
1003                }       
1004        }       
1005}
1006
1007#endif
1008
1009#ifdef USE_SYMBOL_VALUES       
1010#ifdef USE_PARALLEL_TRIE
1011
1012// NO NEED TO PASS IN THE UNRESOLVED SYMBOL COUNT
1013
1014template<uint32_t L>
1015void LSSymbolTable::prefix_offsets(size_t * prefix_offsets) {
1016        for(size_t i=0;i<sizeof(SIMD_type);i++) {
1017                prefix_offsets[i] = 10*i;
1018        }
1019}
1020
1021template<uint32_t L>
1022void LSSymbolTable::ptrie_bind(const unsigned char * symbol_values, size_t unresolved_symbol_count, size_t * offsets) {
1023       
1024        const uint32_t N = 1;                                                                                           // number of prefix bytes
1025        uint32_t non_packed_symbol_count = 0;
1026        uint32_t packed_symbol_count = 0;               
1027       
1028        non_packed_symbol_count = unresolved_symbol_count & (N-1);                      // number of prefix bytes must be a power of 2
1029        packed_symbol_count = unresolved_symbol_count - non_packed_symbol_count;
1030       
1031        SIMD_type crt_pfx_key_byte_splats_128 = simd<1>::constant<0>();         // current iteration values
1032        SIMD_type crt_pfx_index_splats_128 = simd<1>::constant<0>();            // current iteration values
1033        SIMD_type cmp_eq_mask_128 = simd<1>::constant<0>();                                     // comparison accumulator
1034        SIMD_type rslt_pfx_index_splats_128 = simd<1>::constant<0>();           // prefix index accumulator
1035       
1036        uint32_t prefix_key_byte_splats_index = 0;                                                      // next index value
1037       
1038        /*
1039         * Splat a SIMD register of prefix key bytes and
1040         * splat a SIMD register of unresolved symbol value indices.
1041         */
1042        if (unresolved_symbol_count > 0) {
1043                                                       
1044                crt_pfx_key_byte_splats_128 = simd<fw<N>::value>::splat(*(SIMD_type *) &this->symbol_values_->get(L, 0));               
1045                this->pfx_key_byte_splats_->push_back(L, crt_pfx_key_byte_splats_128);
1046                crt_pfx_index_splats_128 = inc<fw<N>::value> (crt_pfx_index_splats_128);
1047                this->pfx_index_splats_->push_back(L,crt_pfx_index_splats_128);
1048
1049                print_simd_register("crt_pfx_key_byte_splats_128", crt_pfx_key_byte_splats_128);
1050                print_simd_register("crt_pfx_index_splats_128", crt_pfx_index_splats_128);
1051
1052        }
1053               
1054        /*
1055         * Full symbol packs.
1056         */     
1057        size_t i = 0;                                                   
1058        size_t step = 0;
1059        size_t limit = 0;       
1060       
1061        step = sizeof(SIMD_type);
1062        limit = packed_symbol_count;                                                                                    // step w.r.t. number of bytes, i.e. sizeof(SIMD_type) bytes at a time
1063               
1064        unsigned char * base_addr = NULL;
1065
1066        uint16_t exit_cond_mask_16 = 0xFFFF;                                                                    // full pack exit condition value
1067        uint16_t done_mask_16 = 0;                                                                                              // current termination value   
1068               
1069        SIMD_type crt_prefix_pack_128;
1070        for(i=0;i<limit;i+=step) {
1071
1072                cmp_eq_mask_128 = simd<1>::constant<0>();
1073                done_mask_16 = 0;
1074                prefix_key_byte_splats_index = 0;                                                                               // loop index variable
1075               
1076                base_addr = &this->symbol_values_->get(L,i);                                                    // get next base address for parallel gather
1077                crt_prefix_pack_128 = simd<8>::gather(base_addr, offsets, SF1);                 // get next N byte prefix pack based on prefix_index values
1078                               
1079                print_simd_register("crt_prefix_pack",crt_prefix_pack_128);
1080               
1081                while(1) {      // SIMD compare and scatter input symbols to arrays of symbols with common prefix values
1082               
1083                        crt_pfx_key_byte_splats_128 = this->pfx_key_byte_splats_->get(L, prefix_key_byte_splats_index); 
1084                        crt_pfx_index_splats_128 = this->pfx_index_splats_->get(L, prefix_key_byte_splats_index);
1085                       
1086                        print_simd_register("crt_prefix_pack",crt_prefix_pack_128);
1087                        print_simd_register("crt_pfx_key_byte_splats_128",crt_pfx_key_byte_splats_128);
1088                        print_simd_register("crt_pfx_index_splats_128",crt_pfx_index_splats_128);
1089                                               
1090                        #ifdef USE_SIMD_AND
1091                                cmp_eq_mask_128 = simd<fw<N>::value>::eq(crt_prefix_pack_128, crt_pfx_key_byte_splats_128); 
1092                                #ifdef SYMBOL_TABLE_DEBUG
1093                                        print_simd_register("cmp_eq_mask_128", cmp_eq_mask_128);
1094                                #endif                 
1095                        #endif                 
1096               
1097                        #ifdef USE_SSE_4_2     
1098                                cmp_eq_mask_128 = _mm_cmpestrm(crt_pfx_key_byte_splats_128, L, crt_pfx_index_splats_128, sizeof(SIMD_type), _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ORDERED | _SIDD_UNIT_MASK);
1099                                cmp_eq_mask_128 = umask_2_smask<fw<L>::value>(cmp_eq_mask_128);
1100                                #ifdef SYMBOL_TABLE_DEBUG
1101                                        print_simd_register("cmp_eq_mask_128",cmp_eq_mask_128);
1102                                #endif                 
1103                        #endif
1104
1105                        rslt_pfx_index_splats_128 = simd_or(rslt_pfx_index_splats_128, simd_and(cmp_eq_mask_128, crt_pfx_index_splats_128));
1106                        done_mask_16 |= simd<8>::movemask(cmp_eq_mask_128);                                             
1107                                               
1108                        if(exit_cond_mask_16 == done_mask_16) { // distribute symbol value copies to 2D array bins based on prefix bytes
1109                               
1110                                print_simd_register("rslt_pfx_index_splats_128",rslt_pfx_index_splats_128);                                                             
1111                                uint16_t unresolved_symbols_idx;
1112
1113                                // for each prefix, copy the symbol index and symbol value to parallel 'unresolved symbol index' and 'unresolved symbol value' arrays
1114                                for(int simd_prefix_register_index=0,symbol_value_index=0,global_symbol_index=0;simd_prefix_register_index<sizeof(SIMD_type);simd_prefix_register_index+=N,symbol_value_index+=L,global_symbol_index++) {
1115                                       
1116                                        // TODO - Template specialization on N (number of prefix bytes)
1117                                        unresolved_symbols_idx = *((uint8_t *) (((uint8_t *)&rslt_pfx_index_splats_128) + simd_prefix_register_index));
1118                                        // unresolved_symbols_idx = *((uint16_t *) (((uint8_t *)&rslt_pfx_index_splats_128) + pfx_register_index));
1119       
1120                                        this->unresolved_symbol_indices_->push_back(unresolved_symbols_idx, this->symbol_index_->get(L,global_symbol_index));
1121                                        this->unresolved_symbol_values_->push_back(unresolved_symbols_idx, &symbol_values[symbol_value_index], L);             
1122                                }
1123                                cout << endl;
1124                               
1125                                #ifdef SYMBOL_TABLE_DEBUG
1126                                size_t cols;
1127                                for(int row=0;row<this->unresolved_symbol_values_->rows();row++) {
1128                                        cols = this->unresolved_symbol_values_->size(row);
1129                                        cout << "cols " << cols << endl;
1130                                        for(int col=0;col<cols;col+=L) {
1131                                                cout << string((char *) &this->unresolved_symbol_values_->get(row, col),L) << endl;
1132                                        }
1133                                }
1134                                cout << endl;
1135                                #endif
1136                               
1137                                break;
1138                        }
1139
1140                        printf("%d,%d\n",prefix_key_byte_splats_index,this->pfx_key_byte_splats_->size(L));
1141                       
1142                        if ((++prefix_key_byte_splats_index) == this->pfx_key_byte_splats_->size(L)) { // add a new unique key and gid masks
1143                               
1144                                uint32_t i = bsf(~done_mask_16); // find 'pointer arithmetic' offset to a symbol yet to be matched                                                                     
1145                                crt_pfx_key_byte_splats_128 = simd<fw<N>::value>::splat ((unsigned char *) (&crt_prefix_pack_128) + i); //gather/splat a new unique key mask
1146                       
1147                                this->pfx_key_byte_splats_->push_back(L, crt_pfx_key_byte_splats_128);
1148                                crt_pfx_index_splats_128 = inc<fw<N>::value> (crt_pfx_index_splats_128);
1149                                this->pfx_index_splats_->push_back(L,crt_pfx_index_splats_128);                         
1150
1151                                print_simd_register("crt_prefix_pack",crt_prefix_pack_128);
1152                                print_simd_register("crt_pfx_key_byte_splats_128",crt_pfx_key_byte_splats_128);
1153                                print_simd_register("crt_pfx_index_splats_128",crt_pfx_index_splats_128);                               
1154                               
1155                        }                               
1156                }               
1157        }
1158       
1159        /*
1160         * Resolve current Trie level, full match prefix sorted values
1161         */     
1162        bool is_equal;
1163       
1164        int cols = 0;
1165        int copy_to_index = 0;
1166       
1167        unsigned char * search_key_value;
1168        uint32_t crt_gid;
1169       
1170        size_t symbol_value_bytes;
1171        for(int row=0;row<this->unresolved_symbol_values_->rows();row++) {
1172               
1173                cout << this->unresolved_symbol_values_->size(row) << endl;
1174               
1175                search_key_value = &this->unresolved_symbol_values_->get(row, 0);                                                                                                       // parallel search key and gid values
1176                this->crt_symbol_gid_++;
1177                crt_gid = this->crt_symbol_gid_;
1178               
1179                this->uniq_symbol_values_->push_back(L, search_key_value, this->uniq_symbol_values_->size());                                           // save a copy of the key value and gid value
1180                this->uniq_symbol_gids_->push_back(L, this->crt_symbol_gid_);
1181               
1182                copy_to_index = 0;
1183                symbol_value_bytes = this->unresolved_symbol_values_->size(row);
1184               
1185                for(size_t global_symbol_index=0, symbol_value_index=0; symbol_value_index<symbol_value_bytes; global_symbol_index++, symbol_value_index+=L) {                                 
1186                                                       
1187                        cout << string((char *)search_key_value,L) << endl;
1188                        cout << string((char *)&this->unresolved_symbol_values_->get(row,symbol_value_index),L) << endl;
1189                       
1190                        is_equal = compare<L>(&this->unresolved_symbol_values_->get(row,symbol_value_index), search_key_value);
1191                       
1192                        if(is_equal) { // set the global symbol numeric identifier value, bind gid to symbol
1193                                this->doc_idx_gids_->set(this->unresolved_symbol_indices_->get(row, global_symbol_index), crt_gid);
1194                        } else {
1195                                // THIS VALUE NEEDS TO BE THE UNRESOLVED SYMBOLS PASSED TO THE NEXT LEVEL OF THE TRIE
1196                                //this->unresolved_symbol_values_->set(row, copy_to_index, search_key_value, L);
1197                                copy_to_index += L;
1198                        } 
1199                }
1200        }
1201               
1202        display_flattened_gids();
1203/*
1204    // Resolve current TRIE level
1205
1206    for i=0 to uniq_key_values_.size() {
1207
1208      key_value = ptrie_partial_match_values_[0]
1209
1210      // Get next partial match value AND based on this partial match value add ...
1211      // Add a new unique value AND add a new parallel GID value
1212
1213      crt_value = this->uniq_symbol_values_.get(L,i);
1214      crt_gid = this->uniq_symbol_gids_.get(L,i);
1215
1216      for(i=0 to ptrie_partial_match_values.size()) {
1217
1218        if(key == ptrie_partial_match_values_[i]) {
1219          // Bind symbol at 'symbol_index_' to a unique numeric identifier
1220
1221          // Set GID array value (gid_) at this index value
1222
1223          this->gids_.set(L,this->crt_symbol_index_.get(L,i);
1224
1225         
1226        } else {
1227          // Append the value to 'unresolved' symbols arrays AND
1228          // Append the symbol index value to the parallel index array
1229        }
1230      }
1231
1232      PTrie<L>(unresolved_symbol_index_array, symbol_count)
1233      unresolved_symbol_index_array.clear()
1234    }
1235
1236    // ptrie_partial_match_values_.clear()
1237 */     
1238       
1239        exit(1);
1240}
1241
1242#endif
1243#endif
1244
1245#ifdef USE_PACKED_SYMBOLS
1246
1247template<>
1248inline void LSSymbolTable::push_gid<1>(const SIMD_type value, const uint32_t count) {
1249
1250        SIMD_type lo, hi;
1251
1252        lo = simdLibConvert<fw<1>::value>::mergel(simd<1>::constant<0>(), value);
1253        hi = simdLibConvert<fw<1>::value>::mergeh(simd<1>::constant<0>(), value);
1254
1255        SIMD_type v[4];
1256
1257        v[0] = simdLibConvert<fw<2>::value>::mergel(simd<2>::constant<0>(), lo);
1258        v[1] = simdLibConvert<fw<2>::value>::mergeh(simd<2>::constant<0>(), lo);
1259        v[2] = simdLibConvert<fw<2>::value>::mergel(simd<2>::constant<0>(), hi);
1260        v[3] = simdLibConvert<fw<2>::value>::mergeh(simd<2>::constant<0>(), hi);
1261
1262        uint32_t push_count;
1263        for (size_t j = 0, i = 0; i < count; j++, i += 4) {
1264                push_count = (count - i >= 4) ? 4 : count - i;
1265                packed_gids_->push_back(1, (uint32_t *) &(v[j]), push_count);
1266        }
1267}
1268
1269template<>
1270inline void LSSymbolTable::push_gid<2>(const SIMD_type value, const uint32_t count) {
1271        SIMD_type v[2];
1272
1273        v[0] = simdLibConvert<fw<2>::value>::mergel(simd<2>::constant<0>(), value);
1274        v[1] = simdLibConvert<fw<2>::value>::mergeh(simd<2>::constant<0>(), value);
1275
1276        uint32_t push_count;
1277        for (size_t j = 0, i = 0; i < count; j++, i += 4) {
1278                push_count = (count - i >= 4) ? 4 : count - i;
1279                packed_gids_->push_back(2, (uint32_t *) &(v[j]), push_count);
1280        }
1281}
1282
1283template<>
1284inline void LSSymbolTable::push_gid<3>(const SIMD_type value, const uint32_t count) {
1285        packed_gids_->push_back(3, (uint32_t *) (&value), count);
1286}
1287
1288template<>
1289inline void LSSymbolTable::push_gid<4>(const SIMD_type value, const uint32_t count) {
1290        packed_gids_->push_back(4, (uint32_t *) (&value), count);
1291}
1292
1293template<>
1294inline void LSSymbolTable::push_gid<5>(const SIMD_type value, const uint32_t count) {
1295        SIMD_type t1 = simdLibConvert<64>::pack(simd<1>::constant<0>(), value);
1296        packed_gids_->push_back(5, (uint32_t *) (&t1), count);
1297}
1298
1299template<>
1300inline void LSSymbolTable::push_gid<6>(const SIMD_type value, const uint32_t count) {
1301        SIMD_type t1 = simdLibConvert<64>::pack(simd<1>::constant<0>(), value);
1302        packed_gids_->push_back(6, (uint32_t *) (&t1), count);
1303}
1304
1305template<>
1306inline void LSSymbolTable::push_gid<7>(const SIMD_type value, const uint32_t count) {
1307        SIMD_type t1 = simdLibConvert<64>::pack(simd<1>::constant<0>(), value);
1308        packed_gids_->push_back(7, (uint32_t *) (&t1), count);
1309}
1310
1311template<>
1312inline void LSSymbolTable::push_gid<8>(const SIMD_type value, const uint32_t count) {
1313        SIMD_type t1 = simdLibConvert<64>::pack(simd<1>::constant<0>(), value);
1314        packed_gids_->push_back(8, (uint32_t *) (&t1), count);
1315}
1316
1317#endif
1318
1319#ifdef USE_PACKED_SYMBOLS
1320
1321// Debug
1322void LSSymbolTable::display_gids() {
1323
1324        printf("%30s\n\n", "Length Sorted 32 bit gid values.");
1325
1326        uint32_t lgth;
1327        for (size_t lgth = 1; lgth < this->packed_gids_->rows(); lgth++) {
1328                printf("%29s%zu = ", "L", lgth);
1329                for (size_t i = 0; i < packed_gids_->size(lgth); i++) {
1330                        printf("%d ", packed_gids_->get(lgth, i));
1331                }
1332                printf("\n");
1333        }
1334        printf("\n");
1335}
1336
1337// Debug
1338void LSSymbolTable::display_gid_indices() {
1339        printf("%30s\n\n", "Length Sorted 32 bit document index values.");
1340
1341        uint32_t lgth;
1342        for (size_t lgth = 1; lgth < this->symbol_index_->rows(); lgth++) {
1343                printf("%29s%zu = ", "L", lgth);
1344                for (size_t i = 0; i < this->symbol_index_->size(lgth); i++) {
1345                        printf("%d ", symbol_index_->get(lgth, i));
1346                }
1347                printf("\n");
1348        }
1349        printf("\n");
1350}
1351
1352template<uint32_t L>
1353void LSSymbolTable::display_packed_data() {
1354
1355        uint32_t pack_count = SYMBOL_PACK_COUNT[L];
1356        uint32_t symbol_count;
1357#ifdef USE_SYMBOL_PTRS
1358        symbol_count = this->symbol_value_ptrs_->size(L);
1359#endif
1360
1361#ifdef USE_SYMBOL_VALUES
1362        symbol_count = this->symbol_values_->size(L)/SYMBOL_BYTES[L];
1363#endif
1364
1365        uint32_t non_packed_symbol_count = symbol_count & (pack_count - 1);
1366        uint32_t packed_symbol_count = symbol_count - non_packed_symbol_count; // total 'full' SIMD register bytes
1367
1368        printf("%30s = %d\n", "Symbol Count", symbol_count);
1369        printf("%30s = %d\n", "Symbol Length", L);
1370        printf("%30s = %d\n", "Pack Count", pack_count);
1371        printf("%30s = %d\n", "Packed Symbol Count", packed_symbol_count);
1372        printf("%30s = %d\n", "Non Packed Symbol Count", non_packed_symbol_count);
1373
1374uint32_t i;     
1375#ifdef USE_SYMBOL_PTRS
1376        printf("%30s = %d\n", "Field Width Mapping", fw<L>::value);
1377
1378        // packed symbols
1379        for (i = 0; i < packed_symbol_count; i += pack_count) {
1380                SIMD_type value = set<fw<L>::value> (&(this->symbol_value_ptrs_->get(L, i)));
1381                print_simd_register("Packed Symbol", value);
1382        }
1383
1384        // non packed symbols
1385        if (non_packed_symbol_count) {
1386                SIMD_type value = set<fw<L>::value> (&(this->symbol_value_ptrs_->get(L, i)),
1387                                non_packed_symbol_count);
1388                print_simd_register("Non Packed Symbol", value);
1389        }
1390        printf("\n");
1391#endif
1392
1393#ifdef USE_SYMBOL_VALUES
1394        uint32_t total_bytes = this->symbol_values_->size(L);
1395        printf("%30s = %d\n", "Total Bytes", total_bytes);
1396
1397        for(i=0;i<total_bytes;i+=sizeof(SIMD_type)) {
1398                SIMD_type value = sisd_load_aligned((SIMD_type *)&this->symbol_values_->get(L,i));
1399                print_simd_register("Symbol", value);
1400        }
1401        printf("\n");
1402#endif
1403
1404}
1405
1406#endif
1407
Note: See TracBrowser for help on using the repository browser.