source: trunk/symtab/PTriePsuedoCode.txt @ 2694

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

Reorganized SymbolTable? library

File size: 4.2 KB
Line 
10 => unknown
21 => known
3
4/*
5 A Code fragment to show how to build up a Trie layer. We could pass each levels Trie layers down the Trie.
6*/
7if(any field is all 0's) {
8  Grad leading Trie width bytes
9  Build another Trie layer mask
10  Compare against the current prefix pack
11} else {
12  Append to the corresponding Trie row
13}
14
15// Data Structures - Recursive Implementation
16
17// In this recursive implemenation Trie levels are implicitly associated with recursive function calls.
18
19'symbol_index_'
20
21
22// 'ptrie_partial_match_values_' - contains 'partially' matched symbols
23
24// Parallel Arrays
25
26// Parallel 'prefix_key' and 'ptrie_scatter_indices' arrays.
27// 'prefix_key' - contains current Trie level N byte symbol prefixes
28// 'ptrie_partial_match_values_idx' - maps prefix_key matches to ptrie_scatter_indices -
29// NOT REQUIRED because ptrie_partial_match_values_ are added in incrementally monotonically increasing order and ptrie_scatter_index arrays map N byte symbol prefixes to scatter array indices to be full matched
30
31// Parallel arrays on column index of ptrie_parallel_match_values_ and row index of 2D length partitioned uniq_key_values_ array.
32// ptrie_partial_match_values_
33// uniq_key_values_
34
35
36PTrie<L> (unresolved_symbol_values_array, symbol_count) {
37
38  if(symbol_count > 0) {
39
40    N_byte_symbol_prefix_pack_array = SIMD_Prefix_Pack(unresolved_symbol_values_array, symbol_count) // gathers N byte prefixes into an array of SIMD packs
41
42    // crt_ptrie_unique_key_index = 0
43
44    for each N_byte_simd_prefix_pack in N_byte_symbol_prefix_array {
45   
46      while(true) { // SIMD compare AND scatter all input symbols to TRIE arrays
47
48        // Get next N byte prefix value pack.
49
50        // Get next N byte key splat pack.
51
52        // Get next ptrie scatter array index pack.
53
54        // SIMD compare N byte prefix value pack versus next N byte key splat pack for equality on N byte prefix width fields.
55
56        // SIMD_and comparison result with ptrie scatter array index pack, i.e. create a match mask on the matching fields.
57
58        // SIMD or matching ptrie scatter array indices into a SIMD accumulator_register.
59
60        // Get done mask and compare the done mask versus the exit condition mask
61
62        if(done_mask_16 == exit_cond_mask_16) {
63
64          for i = 0 to SIMD register width / N
65
66            // next_ptrie_index = N byte field value
67
68            // Append/Write full L byte value to unresolved_match_values[next_ptrie_index] = unresolved_symbol_values_array[i*symbol_length]
69
70            // i = i * N
71
72          break;
73        }
74       
75        if(crt_ptrie_unique_key_index == ptrie_index_array.size) {
76
77        // Add a new N-byte prefix to the prefix_key array
78
79        // Add a new TRIE scatter array index (splat)
80       
81        }
82
83      }
84
85    } 
86
87    // Resolve current TRIE level
88
89    for i=0 to uniq_key_values_.size() {
90
91      key_value = ptrie_partial_match_values_[0]
92
93      // Get next partial match value AND based on this partial match value add ...
94      // Add a new unique value AND add a new parallel GID value
95
96      crt_value = this->uniq_symbol_values_.get(L,i);
97      crt_gid = this->uniq_symbol_gids_.get(L,i);
98
99      for(i=0 to ptrie_partial_match_values.size()) {
100
101        if(key == ptrie_partial_match_values_[i]) {
102          // Bind symbol at 'symbol_index_' to a unique numeric identifier
103
104          // Set GID array value (gid_) at this index value
105
106          this->gids_.set(L,this->crt_symbol_index_.get(L,i);
107
108         
109        } else {
110          // Append the value to 'unresolved' symbols arrays AND
111          // Append the symbol index value to the parallel index array
112        }
113      }
114
115      PTrie<L>(unresolved_symbol_index_array, symbol_count)
116      unresolved_symbol_index_array.clear()
117    }
118
119    // ptrie_partial_match_values_.clear()
120
121
122
123  }
124
125}
126
127// Data Structures - Iterative (non-recursive) Implementation
128//
129// In this iterative implementation explicit 2D arrays, and current TRIE level information must be explicitly maintained.
130//
131// Parallel 2D prefix_key / ptrie_scatter_index arrays. 2D prefix_key and ptrie_scatter_index arrays map N byte symbol prefixes to scatter array indices to be full matched
132//
133
134PTrie<L>(symbol_index_array, symbol_count) {
135
136  current_symbol_count = symbol_count
137
138  while(current_symbol_count > 0) {
139
140
141  }
142
143}
Note: See TracBrowser for help on using the repository browser.