1 //
2 // Copyright (C) 2017 The Android Open Source Project
3 //
4 // Licensed under the Apache License, Version 2.0 (the "License");
5 // you may not use this file except in compliance with the License.
6 // You may obtain a copy of the License at
7 //
8 // http://www.apache.org/licenses/LICENSE-2.0
9 //
10 // Unless required by applicable law or agreed to in writing, software
11 // distributed under the License is distributed on an "AS IS" BASIS,
12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 // See the License for the specific language governing permissions and
14 // limitations under the License.
15 //
16
17 #include "trie_builder.h"
18
19 #include <android-base/strings.h>
20
21 using android::base::Split;
22
23 namespace android {
24 namespace properties {
25
TrieBuilder(const std::string & default_context,const std::string & default_type)26 TrieBuilder::TrieBuilder(const std::string& default_context, const std::string& default_type)
27 : builder_root_("root") {
28 auto* context_pointer = StringPointerFromContainer(default_context, &contexts_);
29 builder_root_.set_context(context_pointer);
30 auto* type_pointer = StringPointerFromContainer(default_type, &types_);
31 builder_root_.set_type(type_pointer);
32 }
33
AddToTrie(const std::string & name,const std::string & context,const std::string & type,bool exact,std::string * error)34 bool TrieBuilder::AddToTrie(const std::string& name, const std::string& context,
35 const std::string& type, bool exact, std::string* error) {
36 auto* context_pointer = StringPointerFromContainer(context, &contexts_);
37 auto* type_pointer = StringPointerFromContainer(type, &types_);
38 return AddToTrie(name, context_pointer, type_pointer, exact, error);
39 }
40
AddToTrie(const std::string & name,const std::string * context,const std::string * type,bool exact,std::string * error)41 bool TrieBuilder::AddToTrie(const std::string& name, const std::string* context,
42 const std::string* type, bool exact, std::string* error) {
43 TrieBuilderNode* current_node = &builder_root_;
44
45 auto name_pieces = Split(name, ".");
46
47 bool ends_with_dot = false;
48 if (name_pieces.back().empty()) {
49 ends_with_dot = true;
50 name_pieces.pop_back();
51 }
52
53 // Move us to the final node that we care about, adding incremental nodes if necessary.
54 while (name_pieces.size() > 1) {
55 auto child = current_node->FindChild(name_pieces.front());
56 if (child == nullptr) {
57 child = current_node->AddChild(name_pieces.front());
58 }
59 if (child == nullptr) {
60 *error = "Unable to allocate Trie node";
61 return false;
62 }
63 current_node = child;
64 name_pieces.erase(name_pieces.begin());
65 }
66
67 // Store our context based on what type of match it is.
68 if (exact) {
69 if (!current_node->AddExactMatchContext(name_pieces.front(), context, type)) {
70 *error = "Duplicate exact match detected for '" + name + "'";
71 return false;
72 }
73 } else if (!ends_with_dot) {
74 if (!current_node->AddPrefixContext(name_pieces.front(), context, type)) {
75 *error = "Duplicate prefix match detected for '" + name + "'";
76 return false;
77 }
78 } else {
79 auto child = current_node->FindChild(name_pieces.front());
80 if (child == nullptr) {
81 child = current_node->AddChild(name_pieces.front());
82 }
83 if (child == nullptr) {
84 *error = "Unable to allocate Trie node";
85 return false;
86 }
87 if (child->context() != nullptr || child->type() != nullptr) {
88 *error = "Duplicate prefix match detected for '" + name + "'";
89 return false;
90 }
91 child->set_context(context);
92 child->set_type(type);
93 }
94 return true;
95 }
96
StringPointerFromContainer(const std::string & string,std::set<std::string> * container)97 const std::string* TrieBuilder::StringPointerFromContainer(const std::string& string,
98 std::set<std::string>* container) {
99 // Get a pointer to the string in a given set, such that we only ever serialize each string once.
100 auto [iterator, _] = container->emplace(string);
101 return &(*iterator);
102 }
103
104 } // namespace properties
105 } // namespace android
106