| 91 | } |
| 92 | |
| 93 | Status TrieBuilder::CreateChildNode(Trie::Node* parent, uint8_t ch, |
| 94 | std::string_view substring) { |
| 95 | const auto kMaxSubstringLength = Trie::kMaxSubstringLength; |
| 96 | |
| 97 | while (substring.length() > kMaxSubstringLength) { |
| 98 | // Substring doesn't fit in node => create intermediate node |
| 99 | auto mid_node = Trie::Node{-1, -1, substring.substr(0, kMaxSubstringLength)}; |
| 100 | RETURN_NOT_OK(AppendChildNode(parent, ch, std::move(mid_node))); |
| 101 | // Recurse |
| 102 | parent = &trie_.nodes_.back(); |
| 103 | ch = static_cast<uint8_t>(substring[kMaxSubstringLength]); |
| 104 | substring = substring.substr(kMaxSubstringLength + 1); |
| 105 | } |
| 106 | |
| 107 | // Create final matching node |
| 108 | auto child_node = Trie::Node{trie_.size_, -1, substring}; |
| 109 | RETURN_NOT_OK(AppendChildNode(parent, ch, std::move(child_node))); |
| 110 | ++trie_.size_; |
| 111 | return Status::OK(); |
| 112 | } |
| 113 | |
| 114 | Status TrieBuilder::CreateChildNode(Trie::Node* parent, char ch, |
| 115 | std::string_view substring) { |