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 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 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 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 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
