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