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
8namespace fml {
9typedef AsciiTrie::TrieNode TrieNode;
10typedef AsciiTrie::TrieNodePtr TrieNodePtr;
11
12namespace {
13void 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
24TrieNodePtr 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
33void AsciiTrie::Fill(const std::vector<std::string>& entries) {
34 node_ = MakeTrie(entries);
35}
36
37bool 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