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_serializer.h" 18 19 namespace android { 20 namespace properties { 21 22 // Serialized strings contains: 23 // 1) A uint32_t count of elements in the below array 24 // 2) A sorted array of uint32_t offsets pointing to null terminated strings 25 // 3) Each of the null terminated strings themselves packed back to back 26 // This returns the offset into arena where the serialized strings start. 27 void TrieSerializer::SerializeStrings(const std::set<std::string>& strings) { 28 arena_->AllocateAndWriteUint32(strings.size()); 29 30 // Allocate space for the array. 31 uint32_t offset_array_offset = arena_->AllocateUint32Array(strings.size()); 32 33 // Write offset pointers and strings; these are already alphabetically sorted by virtue of being 34 // in an std::set. 35 auto it = strings.begin(); 36 for (unsigned int i = 0; i < strings.size(); ++i, ++it) { 37 uint32_t string_offset = arena_->AllocateAndWriteString(*it); 38 arena_->uint32_array(offset_array_offset)[i] = string_offset; 39 } 40 } 41 42 uint32_t TrieSerializer::WritePropertyEntry(const PropertyEntryBuilder& property_entry) { 43 uint32_t context_index = property_entry.context != nullptr && !property_entry.context->empty() 44 ? serialized_info()->FindContextIndex(property_entry.context->c_str()) 45 : ~0u; 46 uint32_t type_index = property_entry.type != nullptr && !property_entry.type->empty() 47 ? serialized_info()->FindTypeIndex(property_entry.type->c_str()) 48 : ~0u; 49 uint32_t offset; 50 auto serialized_property_entry = arena_->AllocateObject<PropertyEntry>(&offset); 51 serialized_property_entry->name_offset = arena_->AllocateAndWriteString(property_entry.name); 52 serialized_property_entry->namelen = property_entry.name.size(); 53 serialized_property_entry->context_index = context_index; 54 serialized_property_entry->type_index = type_index; 55 return offset; 56 } 57 58 uint32_t TrieSerializer::WriteTrieNode(const TrieBuilderNode& builder_node) { 59 uint32_t trie_offset; 60 auto trie = arena_->AllocateObject<TrieNodeInternal>(&trie_offset); 61 62 trie->property_entry = WritePropertyEntry(builder_node.property_entry()); 63 64 // Write prefix matches 65 auto sorted_prefix_matches = builder_node.prefixes(); 66 // Prefixes are sorted by descending length 67 std::sort(sorted_prefix_matches.begin(), sorted_prefix_matches.end(), 68 [](const auto& lhs, const auto& rhs) { return lhs.name.size() > rhs.name.size(); }); 69 70 trie->num_prefixes = sorted_prefix_matches.size(); 71 72 uint32_t prefix_entries_array_offset = arena_->AllocateUint32Array(sorted_prefix_matches.size()); 73 trie->prefix_entries = prefix_entries_array_offset; 74 75 for (unsigned int i = 0; i < sorted_prefix_matches.size(); ++i) { 76 uint32_t property_entry_offset = WritePropertyEntry(sorted_prefix_matches[i]); 77 arena_->uint32_array(prefix_entries_array_offset)[i] = property_entry_offset; 78 } 79 80 // Write exact matches 81 auto sorted_exact_matches = builder_node.exact_matches(); 82 // Exact matches are sorted alphabetically 83 std::sort(sorted_exact_matches.begin(), sorted_exact_matches.end(), 84 [](const auto& lhs, const auto& rhs) { return lhs.name < rhs.name; }); 85 86 trie->num_exact_matches = sorted_exact_matches.size(); 87 88 uint32_t exact_match_entries_array_offset = 89 arena_->AllocateUint32Array(sorted_exact_matches.size()); 90 trie->exact_match_entries = exact_match_entries_array_offset; 91 92 for (unsigned int i = 0; i < sorted_exact_matches.size(); ++i) { 93 uint32_t property_entry_offset = WritePropertyEntry(sorted_exact_matches[i]); 94 arena_->uint32_array(exact_match_entries_array_offset)[i] = property_entry_offset; 95 } 96 97 // Write children 98 auto sorted_children = builder_node.children(); 99 std::sort(sorted_children.begin(), sorted_children.end(), 100 [](const auto& lhs, const auto& rhs) { return lhs.name() < rhs.name(); }); 101 102 trie->num_child_nodes = sorted_children.size(); 103 uint32_t children_offset_array_offset = arena_->AllocateUint32Array(sorted_children.size()); 104 trie->child_nodes = children_offset_array_offset; 105 106 for (unsigned int i = 0; i < sorted_children.size(); ++i) { 107 arena_->uint32_array(children_offset_array_offset)[i] = WriteTrieNode(sorted_children[i]); 108 } 109 return trie_offset; 110 } 111 112 TrieSerializer::TrieSerializer() {} 113 114 std::string TrieSerializer::SerializeTrie(const TrieBuilder& trie_builder) { 115 arena_.reset(new TrieNodeArena()); 116 117 auto header = arena_->AllocateObject<PropertyInfoAreaHeader>(nullptr); 118 header->current_version = 1; 119 header->minimum_supported_version = 1; 120 121 // Store where we're about to write the contexts. 122 header->contexts_offset = arena_->size(); 123 SerializeStrings(trie_builder.contexts()); 124 125 // Store where we're about to write the types. 126 header->types_offset = arena_->size(); 127 SerializeStrings(trie_builder.types()); 128 129 // We need to store size() up to this point now for Find*Offset() to work. 130 header->size = arena_->size(); 131 132 uint32_t root_trie_offset = WriteTrieNode(trie_builder.builder_root()); 133 header->root_offset = root_trie_offset; 134 135 // Record the real size now that we've written everything 136 header->size = arena_->size(); 137 138 return arena_->truncated_data(); 139 } 140 141 } // namespace properties 142 } // namespace android 143
