1 | // Copyright 2013 The Flutter Authors. All rights reserved. |
---|---|
2 | // Use of this source code is governed by a BSD-style license that can be |
3 | // found in the LICENSE file. |
4 | |
5 | #include "flutter/fml/ascii_trie.h" |
6 | #include "flutter/fml/logging.h" |
7 | |
8 | namespace fml { |
9 | typedef AsciiTrie::TrieNode TrieNode; |
10 | typedef AsciiTrie::TrieNodePtr TrieNodePtr; |
11 | |
12 | namespace { |
13 | void Add(TrieNodePtr* trie, const char* entry) { |
14 | int ch = entry[0]; |
15 | FML_DCHECK(ch < AsciiTrie::kMaxAsciiValue); |
16 | if (ch != 0) { |
17 | if (!*trie) { |
18 | *trie = std::make_unique<TrieNode>(); |
19 | } |
20 | Add(&(*trie)->children[ch], entry + 1); |
21 | } |
22 | } |
23 | |
24 | TrieNodePtr MakeTrie(const std::vector<std::string>& entries) { |
25 | TrieNodePtr result; |
26 | for (const std::string& entry : entries) { |
27 | Add(&result, entry.c_str()); |
28 | } |
29 | return result; |
30 | } |
31 | } // namespace |
32 | |
33 | void AsciiTrie::Fill(const std::vector<std::string>& entries) { |
34 | node_ = MakeTrie(entries); |
35 | } |
36 | |
37 | bool AsciiTrie::Query(TrieNode* trie, const char* query) { |
38 | FML_DCHECK(trie); |
39 | const char* char_position = query; |
40 | TrieNode* trie_position = trie; |
41 | TrieNode* child = nullptr; |
42 | int ch; |
43 | while ((ch = *char_position) && (child = trie_position->children[ch].get())) { |
44 | char_position++; |
45 | trie_position = child; |
46 | } |
47 | return !child && trie_position != trie; |
48 | } |
49 | } // namespace fml |
50 |