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.
SerializeStrings(const std::set<std::string> & strings)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
WritePropertyEntry(const PropertyEntryBuilder & property_entry)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
WriteTrieNode(const TrieBuilderNode & builder_node)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
TrieSerializer()112 TrieSerializer::TrieSerializer() {}
113
SerializeTrie(const TrieBuilder & trie_builder)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