1 // Protocol Buffers - Google's data interchange format
2 // Copyright 2008 Google Inc. All rights reserved.
3 //
4 // Use of this source code is governed by a BSD-style
5 // license that can be found in the LICENSE file or at
6 // https://developers.google.com/open-source/licenses/bsd
7
8 #include "google/protobuf/map.h"
9
10 #include <algorithm>
11 #include <functional>
12 #include <iterator>
13 #include <string>
14 #include <type_traits>
15
16 #include "absl/hash/hash.h"
17 #include "absl/strings/string_view.h"
18 #include "google/protobuf/message_lite.h"
19
20
21 // Must be included last.
22 #include "google/protobuf/port_def.inc"
23
24 namespace google {
25 namespace protobuf {
26 namespace internal {
27
28 const TableEntryPtr kGlobalEmptyTable[kGlobalEmptyTableSize] = {};
29
DestroyTree(Tree * tree)30 NodeBase* UntypedMapBase::DestroyTree(Tree* tree) {
31 NodeBase* head = tree->empty() ? nullptr : tree->begin()->second;
32 if (alloc_.arena() == nullptr) {
33 delete tree;
34 }
35 return head;
36 }
37
EraseFromTree(map_index_t b,typename Tree::iterator tree_it)38 void UntypedMapBase::EraseFromTree(map_index_t b,
39 typename Tree::iterator tree_it) {
40 ABSL_DCHECK(TableEntryIsTree(b));
41 Tree* tree = TableEntryToTree(table_[b]);
42 if (tree_it != tree->begin()) {
43 NodeBase* prev = std::prev(tree_it)->second;
44 prev->next = prev->next->next;
45 }
46 tree->erase(tree_it);
47 if (tree->empty()) {
48 DestroyTree(tree);
49 table_[b] = TableEntryPtr{};
50 }
51 }
52
InsertUniqueInTree(map_index_t b,GetKey get_key,NodeBase * node)53 void UntypedMapBase::InsertUniqueInTree(map_index_t b, GetKey get_key,
54 NodeBase* node) {
55 if (TableEntryIsNonEmptyList(b)) {
56 // To save in binary size, we delegate to an out-of-line function to do
57 // the conversion.
58 table_[b] = ConvertToTree(TableEntryToNode(table_[b]), get_key);
59 }
60 ABSL_DCHECK(TableEntryIsTree(b))
61 << (void*)table_[b] << " " << (uintptr_t)table_[b];
62
63 Tree* tree = TableEntryToTree(table_[b]);
64 auto it = tree->try_emplace(get_key(node), node).first;
65 // Maintain the linked list of the nodes in the tree.
66 // For simplicity, they are in the same order as the tree iteration.
67 if (it != tree->begin()) {
68 NodeBase* prev = std::prev(it)->second;
69 prev->next = node;
70 }
71 auto next = std::next(it);
72 node->next = next != tree->end() ? next->second : nullptr;
73 }
74
TransferTree(Tree * tree,GetKey get_key)75 void UntypedMapBase::TransferTree(Tree* tree, GetKey get_key) {
76 NodeBase* node = DestroyTree(tree);
77 do {
78 NodeBase* next = node->next;
79
80 map_index_t b = VariantBucketNumber(get_key(node));
81 // This is similar to InsertUnique, but with erasure.
82 if (TableEntryIsEmpty(b)) {
83 InsertUniqueInList(b, node);
84 index_of_first_non_null_ = (std::min)(index_of_first_non_null_, b);
85 } else if (TableEntryIsNonEmptyList(b) && !TableEntryIsTooLong(b)) {
86 InsertUniqueInList(b, node);
87 } else {
88 InsertUniqueInTree(b, get_key, node);
89 }
90
91 node = next;
92 } while (node != nullptr);
93 }
94
ConvertToTree(NodeBase * node,GetKey get_key)95 TableEntryPtr UntypedMapBase::ConvertToTree(NodeBase* node, GetKey get_key) {
96 auto* tree = Arena::Create<Tree>(alloc_.arena(), typename Tree::key_compare(),
97 typename Tree::allocator_type(alloc_));
98 for (; node != nullptr; node = node->next) {
99 tree->try_emplace(get_key(node), node);
100 }
101 ABSL_DCHECK_EQ(MapTreeLengthThreshold(), tree->size());
102
103 // Relink the nodes.
104 NodeBase* next = nullptr;
105 auto it = tree->end();
106 do {
107 node = (--it)->second;
108 node->next = next;
109 next = node;
110 } while (it != tree->begin());
111
112 return TreeToTableEntry(tree);
113 }
114
ClearTable(const ClearInput input)115 void UntypedMapBase::ClearTable(const ClearInput input) {
116 ABSL_DCHECK_NE(num_buckets_, kGlobalEmptyTableSize);
117
118 if (alloc_.arena() == nullptr) {
119 const auto loop = [=](auto destroy_node) {
120 const TableEntryPtr* table = table_;
121 for (map_index_t b = index_of_first_non_null_, end = num_buckets_;
122 b < end; ++b) {
123 NodeBase* node =
124 PROTOBUF_PREDICT_FALSE(internal::TableEntryIsTree(table[b]))
125 ? DestroyTree(TableEntryToTree(table[b]))
126 : TableEntryToNode(table[b]);
127
128 while (node != nullptr) {
129 NodeBase* next = node->next;
130 destroy_node(node);
131 SizedDelete(node, SizeFromInfo(input.size_info));
132 node = next;
133 }
134 }
135 };
136 switch (input.destroy_bits) {
137 case 0:
138 loop([](NodeBase*) {});
139 break;
140 case kKeyIsString:
141 loop([](NodeBase* node) {
142 static_cast<std::string*>(node->GetVoidKey())->~basic_string();
143 });
144 break;
145 case kValueIsString:
146 loop([size_info = input.size_info](NodeBase* node) {
147 static_cast<std::string*>(node->GetVoidValue(size_info))
148 ->~basic_string();
149 });
150 break;
151 case kKeyIsString | kValueIsString:
152 loop([size_info = input.size_info](NodeBase* node) {
153 static_cast<std::string*>(node->GetVoidKey())->~basic_string();
154 static_cast<std::string*>(node->GetVoidValue(size_info))
155 ->~basic_string();
156 });
157 break;
158 case kValueIsProto:
159 loop([size_info = input.size_info](NodeBase* node) {
160 static_cast<MessageLite*>(node->GetVoidValue(size_info))
161 ->DestroyInstance();
162 });
163 break;
164 case kKeyIsString | kValueIsProto:
165 loop([size_info = input.size_info](NodeBase* node) {
166 static_cast<std::string*>(node->GetVoidKey())->~basic_string();
167 static_cast<MessageLite*>(node->GetVoidValue(size_info))
168 ->DestroyInstance();
169 });
170 break;
171 case kUseDestructFunc:
172 loop(input.destroy_node);
173 break;
174 }
175 }
176
177 if (input.reset_table) {
178 std::fill(table_, table_ + num_buckets_, TableEntryPtr{});
179 num_elements_ = 0;
180 index_of_first_non_null_ = num_buckets_;
181 } else {
182 DeleteTable(table_, num_buckets_);
183 }
184 }
185
FindFromTree(map_index_t b,VariantKey key,Tree::iterator * it) const186 auto UntypedMapBase::FindFromTree(map_index_t b, VariantKey key,
187 Tree::iterator* it) const -> NodeAndBucket {
188 Tree* tree = TableEntryToTree(table_[b]);
189 auto tree_it = tree->find(key);
190 if (it != nullptr) *it = tree_it;
191 if (tree_it != tree->end()) {
192 return {tree_it->second, b};
193 }
194 return {nullptr, b};
195 }
196
SpaceUsedInTable(size_t sizeof_node) const197 size_t UntypedMapBase::SpaceUsedInTable(size_t sizeof_node) const {
198 size_t size = 0;
199 // The size of the table.
200 size += sizeof(void*) * num_buckets_;
201 // All the nodes.
202 size += sizeof_node * num_elements_;
203 // For each tree, count the overhead of those nodes.
204 // Two buckets at a time because we only care about trees.
205 for (map_index_t b = 0; b < num_buckets_; ++b) {
206 if (TableEntryIsTree(b)) {
207 size += sizeof(Tree);
208 size += sizeof(Tree::value_type) * TableEntryToTree(table_[b])->size();
209 }
210 }
211 return size;
212 }
213
214 } // namespace internal
215 } // namespace protobuf
216 } // namespace google
217
218 #include "google/protobuf/port_undef.inc"
219