| 122 | Trie& operator=(Trie&&) = default; |
| 123 | |
| 124 | int32_t Find(std::string_view s) const { |
| 125 | const Node* node = &nodes_[0]; |
| 126 | fast_index_type pos = 0; |
| 127 | if (s.length() > static_cast<size_t>(kMaxIndex)) { |
| 128 | return -1; |
| 129 | } |
| 130 | fast_index_type remaining = static_cast<fast_index_type>(s.length()); |
| 131 | |
| 132 | while (remaining > 0) { |
| 133 | auto substring_length = node->substring_length(); |
| 134 | if (substring_length > 0) { |
| 135 | auto substring_data = node->substring_data(); |
| 136 | if (remaining < substring_length) { |
| 137 | // Input too short |
| 138 | return -1; |
| 139 | } |
| 140 | for (fast_index_type i = 0; i < substring_length; ++i) { |
| 141 | if (s[pos++] != substring_data[i]) { |
| 142 | // Mismatching substring |
| 143 | return -1; |
| 144 | } |
| 145 | --remaining; |
| 146 | } |
| 147 | if (remaining == 0) { |
| 148 | // Matched node exactly |
| 149 | return node->found_index_; |
| 150 | } |
| 151 | } |
| 152 | // Lookup child using next input character |
| 153 | if (node->child_lookup_ == -1) { |
| 154 | // Input too long |
| 155 | return -1; |
| 156 | } |
| 157 | auto c = static_cast<uint8_t>(s[pos++]); |
| 158 | --remaining; |
| 159 | auto child_index = lookup_table_[node->child_lookup_ * 256 + c]; |
| 160 | if (child_index == -1) { |
| 161 | // Child not found |
| 162 | return -1; |
| 163 | } |
| 164 | node = &nodes_[child_index]; |
| 165 | } |
| 166 | |
| 167 | // Input exhausted |
| 168 | if (node->substring_.empty()) { |
| 169 | // Matched node exactly |
| 170 | return node->found_index_; |
| 171 | } else { |
| 172 | return -1; |
| 173 | } |
| 174 | } |
| 175 | |
| 176 | Status Validate() const; |
| 177 | |