| 90 | } |
| 91 | |
| 92 | forceinline void |
| 93 | DFA::DFAI::fill(void) { |
| 94 | key = static_cast<std::size_t>(n_states); |
| 95 | cmb_hash(key, n_trans); |
| 96 | cmb_hash(key, n_symbols); |
| 97 | cmb_hash(key, final_fst); |
| 98 | cmb_hash(key, final_lst); |
| 99 | // Compute smallest logarithm larger than n_symbols |
| 100 | n_log = 1; |
| 101 | while (n_symbols >= static_cast<unsigned int>(1<<n_log)) |
| 102 | n_log++; |
| 103 | // Allocate memory |
| 104 | table = heap.alloc<HashEntry>(1<<n_log); |
| 105 | // Initialize table |
| 106 | for (int i=(1<<n_log); i--; ) |
| 107 | table[i].fst = table[i].lst = nullptr; |
| 108 | int mask = (1 << n_log) - 1; |
| 109 | // Enter transitions to table |
| 110 | for (int i = 0; i<n_trans; ) { |
| 111 | cmb_hash(key, trans[i].i_state); |
| 112 | cmb_hash(key, trans[i].symbol); |
| 113 | cmb_hash(key, trans[i].o_state); |
| 114 | int s = trans[i].symbol; |
| 115 | Transition* fst = &trans[i]; |
| 116 | i++; |
| 117 | while ((i<n_trans) && (trans[i].symbol == s)) |
| 118 | i++; |
| 119 | Transition* lst = &trans[i]; |
| 120 | // Enter with linear collision resolution |
| 121 | int p = s & mask; |
| 122 | while (table[p].fst != nullptr) |
| 123 | p = (p+1) & mask; |
| 124 | table[p].symbol = s; |
| 125 | table[p].fst = fst; |
| 126 | table[p].lst = lst; |
| 127 | } |
| 128 | } |
| 129 | |
| 130 | forceinline |
| 131 | DFA::DFA(void) {} |