Debian Codegraph @

third_party/protobuf-lite/google/protobuf/map.h

raw
1 // Protocol Buffers - Google's data interchange format
2 // Copyright 2008 Google Inc. All rights reserved.
3 // https://developers.google.com/protocol-buffers/
4 //
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are
7 // met:
8 //
9 // * Redistributions of source code must retain the above copyright
10 // notice, this list of conditions and the following disclaimer.
11 // * Redistributions in binary form must reproduce the above
12 // copyright notice, this list of conditions and the following disclaimer
13 // in the documentation and/or other materials provided with the
14 // distribution.
15 // * Neither the name of Google Inc. nor the names of its
16 // contributors may be used to endorse or promote products derived from
17 // this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30
31 // This file defines the map container and its helpers to support protobuf maps.
32 //
33 // The Map and MapIterator types are provided by this header file.
34 // Please avoid using other types defined here, unless they are public
35 // types within Map or MapIterator, such as Map::value_type.
36
37 #ifndef GOOGLE_PROTOBUF_MAP_H__
38 #define GOOGLE_PROTOBUF_MAP_H__
39
40 #include <functional>
41 #include <initializer_list>
42 #include <iterator>
43 #include <limits> // To support Visual Studio 2008
44 #include <map>
45 #include <string>
46 #include <type_traits>
47 #include <utility>
48
49 #if defined(__cpp_lib_string_view)
50 #include <string_view>
51 #endif // defined(__cpp_lib_string_view)
52
53 #include <google/protobuf/stubs/common.h>
54 #include <google/protobuf/arena.h>
55 #include <google/protobuf/generated_enum_util.h>
56 #include <google/protobuf/map_type_handler.h>
57 #include <google/protobuf/stubs/hash.h>
58
59 #ifdef SWIG
60 #error "You cannot SWIG proto headers"
61 #endif
62
63 #include <google/protobuf/port_def.inc>
64
65 namespace google {
66 namespace protobuf {
67
68 template <typename Key, typename T>
69 class Map;
70
71 class MapIterator;
72
73 template <typename Enum>
74 struct is_proto_enum;
75
76 namespace internal {
77 template <typename Derived, typename Key, typename T,
78 WireFormatLite::FieldType key_wire_type,
79 WireFormatLite::FieldType value_wire_type>
80 class MapFieldLite;
81
82 template <typename Derived, typename Key, typename T,
83 WireFormatLite::FieldType key_wire_type,
84 WireFormatLite::FieldType value_wire_type>
85 class MapField;
86
87 template <typename Key, typename T>
88 class TypeDefinedMapFieldBase;
89
90 class DynamicMapField;
91
92 class GeneratedMessageReflection;
93
94 // re-implement std::allocator to use arena allocator for memory allocation.
95 // Used for Map implementation. Users should not use this class
96 // directly.
97 template <typename U>
98 class MapAllocator {
99 public:
100 using value_type = U;
101 using pointer = value_type*;
102 using const_pointer = const value_type*;
103 using reference = value_type&;
104 using const_reference = const value_type&;
105 using size_type = size_t;
106 using difference_type = ptrdiff_t;
107
108 constexpr MapAllocator() : arena_(nullptr) {}
109 explicit constexpr MapAllocator(Arena* arena) : arena_(arena) {}
110 template <typename X>
111 MapAllocator(const MapAllocator<X>& allocator) // NOLINT(runtime/explicit)
112 : arena_(allocator.arena()) {}
113
114 pointer allocate(size_type n, const void* /* hint */ = nullptr) {
115 // If arena is not given, malloc needs to be called which doesn't
116 // construct element object.
117 if (arena_ == nullptr) {
118 return static_cast<pointer>(::operator new(n * sizeof(value_type)));
119 } else {
120 return reinterpret_cast<pointer>(
121 Arena::CreateArray<uint8>(arena_, n * sizeof(value_type)));
122 }
123 }
124
125 void deallocate(pointer p, size_type n) {
126 if (arena_ == nullptr) {
127 #if defined(__GXX_DELETE_WITH_SIZE__) || defined(__cpp_sized_deallocation)
128 ::operator delete(p, n * sizeof(value_type));
129 #else
130 (void)n;
131 ::operator delete(p);
132 #endif
133 }
134 }
135
136 #if !defined(GOOGLE_PROTOBUF_OS_APPLE) && !defined(GOOGLE_PROTOBUF_OS_NACL) && \
137 !defined(GOOGLE_PROTOBUF_OS_EMSCRIPTEN)
138 template <class NodeType, class... Args>
139 void construct(NodeType* p, Args&&... args) {
140 // Clang 3.6 doesn't compile static casting to void* directly. (Issue
141 // #1266) According C++ standard 5.2.9/1: "The static_cast operator shall
142 // not cast away constness". So first the maybe const pointer is casted to
143 // const void* and after the const void* is const casted.
144 new (const_cast<void*>(static_cast<const void*>(p)))
145 NodeType(std::forward<Args>(args)...);
146 }
147
148 template <class NodeType>
149 void destroy(NodeType* p) {
150 p->~NodeType();
151 }
152 #else
153 void construct(pointer p, const_reference t) { new (p) value_type(t); }
154
155 void destroy(pointer p) { p->~value_type(); }
156 #endif
157
158 template <typename X>
159 struct rebind {
160 using other = MapAllocator<X>;
161 };
162
163 template <typename X>
164 bool operator==(const MapAllocator<X>& other) const {
165 return arena_ == other.arena_;
166 }
167
168 template <typename X>
169 bool operator!=(const MapAllocator<X>& other) const {
170 return arena_ != other.arena_;
171 }
172
173 // To support Visual Studio 2008
174 size_type max_size() const {
175 // parentheses around (std::...:max) prevents macro warning of max()
176 return (std::numeric_limits<size_type>::max)();
177 }
178
179 // To support gcc-4.4, which does not properly
180 // support templated friend classes
181 Arena* arena() const { return arena_; }
182
183 private:
184 using DestructorSkippable_ = void;
185 Arena* arena_;
186 };
187
188 template <typename T>
189 using KeyForTree =
190 typename std::conditional<std::is_scalar<T>::value, T,
191 std::reference_wrapper<const T>>::type;
192
193 // Default case: Not transparent.
194 // We use std::hash<key_type>/std::less<key_type> and all the lookup functions
195 // only accept `key_type`.
196 template <typename key_type>
197 struct TransparentSupport {
198 using hash = std::hash<key_type>;
199 using less = std::less<key_type>;
200
201 static bool Equals(const key_type& a, const key_type& b) { return a == b; }
202
203 template <typename K>
204 using key_arg = key_type;
205 };
206
207 #if defined(__cpp_lib_string_view)
208 // If std::string_view is available, we add transparent support for std::string
209 // keys. We use std::hash<std::string_view> as it supports the input types we
210 // care about. The lookup functions accept arbitrary `K`. This will include any
211 // key type that is convertible to std::string_view.
212 template <>
213 struct TransparentSupport<std::string> {
214 static std::string_view ImplicitConvert(std::string_view str) { return str; }
215 // If the element is not convertible to std::string_view, try to convert to
216 // std::string first.
217 // The template makes this overload lose resolution when both have the same
218 // rank otherwise.
219 template <typename = void>
220 static std::string_view ImplicitConvert(const std::string& str) {
221 return str;
222 }
223
224 struct hash : private std::hash<std::string_view> {
225 using is_transparent = void;
226
227 template <typename T>
228 size_t operator()(const T& str) const {
229 return base()(ImplicitConvert(str));
230 }
231
232 private:
233 const std::hash<std::string_view>& base() const { return *this; }
234 };
235 struct less {
236 using is_transparent = void;
237
238 template <typename T, typename U>
239 bool operator()(const T& t, const U& u) const {
240 return ImplicitConvert(t) < ImplicitConvert(u);
241 }
242 };
243
244 template <typename T, typename U>
245 static bool Equals(const T& t, const U& u) {
246 return ImplicitConvert(t) == ImplicitConvert(u);
247 }
248
249 template <typename K>
250 using key_arg = K;
251 };
252 #endif // defined(__cpp_lib_string_view)
253
254 template <typename Key>
255 using TreeForMap =
256 std::map<KeyForTree<Key>, void*, typename TransparentSupport<Key>::less,
257 MapAllocator<std::pair<const KeyForTree<Key>, void*>>>;
258
259 inline bool TableEntryIsEmpty(void* const* table, size_t b) {
260 return table[b] == nullptr;
261 }
262 inline bool TableEntryIsNonEmptyList(void* const* table, size_t b) {
263 return table[b] != nullptr && table[b] != table[b ^ 1];
264 }
265 inline bool TableEntryIsTree(void* const* table, size_t b) {
266 return !TableEntryIsEmpty(table, b) && !TableEntryIsNonEmptyList(table, b);
267 }
268 inline bool TableEntryIsList(void* const* table, size_t b) {
269 return !TableEntryIsTree(table, b);
270 }
271
272 // This captures all numeric types.
273 inline size_t MapValueSpaceUsedExcludingSelfLong(bool) { return 0; }
274 inline size_t MapValueSpaceUsedExcludingSelfLong(const std::string& str) {
275 return StringSpaceUsedExcludingSelfLong(str);
276 }
277 template <typename T,
278 typename = decltype(std::declval<const T&>().SpaceUsedLong())>
279 size_t MapValueSpaceUsedExcludingSelfLong(const T& message) {
280 return message.SpaceUsedLong() - sizeof(T);
281 }
282
283 constexpr size_t kGlobalEmptyTableSize = 1;
284 PROTOBUF_EXPORT extern void* const kGlobalEmptyTable[kGlobalEmptyTableSize];
285
286 // Space used for the table, trees, and nodes.
287 // Does not include the indirect space used. Eg the data of a std::string.
288 template <typename Key>
289 PROTOBUF_NOINLINE size_t SpaceUsedInTable(void** table, size_t num_buckets,
290 size_t num_elements,
291 size_t sizeof_node) {
292 size_t size = 0;
293 // The size of the table.
294 size += sizeof(void*) * num_buckets;
295 // All the nodes.
296 size += sizeof_node * num_elements;
297 // For each tree, count the overhead of the those nodes.
298 // Two buckets at a time because we only care about trees.
299 for (size_t b = 0; b < num_buckets; b += 2) {
300 if (internal::TableEntryIsTree(table, b)) {
301 using Tree = TreeForMap<Key>;
302 Tree* tree = static_cast<Tree*>(table[b]);
303 // Estimated cost of the red-black tree nodes, 3 pointers plus a
304 // bool (plus alignment, so 4 pointers).
305 size += tree->size() *
306 (sizeof(typename Tree::value_type) + sizeof(void*) * 4);
307 }
308 }
309 return size;
310 }
311
312 template <typename Map,
313 typename = typename std::enable_if<
314 !std::is_scalar<typename Map::key_type>::value ||
315 !std::is_scalar<typename Map::mapped_type>::value>::type>
316 size_t SpaceUsedInValues(const Map* map) {
317 size_t size = 0;
318 for (const auto& v : *map) {
319 size += internal::MapValueSpaceUsedExcludingSelfLong(v.first) +
320 internal::MapValueSpaceUsedExcludingSelfLong(v.second);
321 }
322 return size;
323 }
324
325 inline size_t SpaceUsedInValues(const void*) { return 0; }
326
327 } // namespace internal
328
329 // This is the class for Map's internal value_type. Instead of using
330 // std::pair as value_type, we use this class which provides us more control of
331 // its process of construction and destruction.
332 template <typename Key, typename T>
333 struct MapPair {
334 using first_type = const Key;
335 using second_type = T;
336
337 MapPair(const Key& other_first, const T& other_second)
338 : first(other_first), second(other_second) {}
339 explicit MapPair(const Key& other_first) : first(other_first), second() {}
340 explicit MapPair(Key&& other_first)
341 : first(std::move(other_first)), second() {}
342 MapPair(const MapPair& other) : first(other.first), second(other.second) {}
343
344 ~MapPair() {}
345
346 // Implicitly convertible to std::pair of compatible types.
347 template <typename T1, typename T2>
348 operator std::pair<T1, T2>() const { // NOLINT(runtime/explicit)
349 return std::pair<T1, T2>(first, second);
350 }
351
352 const Key first;
353 T second;
354
355 private:
356 friend class Arena;
357 friend class Map<Key, T>;
358 };
359
360 // Map is an associative container type used to store protobuf map
361 // fields. Each Map instance may or may not use a different hash function, a
362 // different iteration order, and so on. E.g., please don't examine
363 // implementation details to decide if the following would work:
364 // Map<int, int> m0, m1;
365 // m0[0] = m1[0] = m0[1] = m1[1] = 0;
366 // assert(m0.begin()->first == m1.begin()->first); // Bug!
367 //
368 // Map's interface is similar to std::unordered_map, except that Map is not
369 // designed to play well with exceptions.
370 template <typename Key, typename T>
371 class Map {
372 public:
373 using key_type = Key;
374 using mapped_type = T;
375 using value_type = MapPair<Key, T>;
376
377 using pointer = value_type*;
378 using const_pointer = const value_type*;
379 using reference = value_type&;
380 using const_reference = const value_type&;
381
382 using size_type = size_t;
383 using hasher = typename internal::TransparentSupport<Key>::hash;
384
385 constexpr Map() : elements_(nullptr) {}
386 explicit Map(Arena* arena) : elements_(arena) {}
387
388 Map(const Map& other) : Map() { insert(other.begin(), other.end()); }
389
390 Map(Map&& other) noexcept : Map() {
391 if (other.arena() != nullptr) {
392 *this = other;
393 } else {
394 swap(other);
395 }
396 }
397
398 Map& operator=(Map&& other) noexcept {
399 if (this != &other) {
400 if (arena() != other.arena()) {
401 *this = other;
402 } else {
403 swap(other);
404 }
405 }
406 return *this;
407 }
408
409 template <class InputIt>
410 Map(const InputIt& first, const InputIt& last) : Map() {
411 insert(first, last);
412 }
413
414 ~Map() {}
415
416 private:
417 using Allocator = internal::MapAllocator<void*>;
418
419 // InnerMap is a generic hash-based map. It doesn't contain any
420 // protocol-buffer-specific logic. It is a chaining hash map with the
421 // additional feature that some buckets can be converted to use an ordered
422 // container. This ensures O(lg n) bounds on find, insert, and erase, while
423 // avoiding the overheads of ordered containers most of the time.
424 //
425 // The implementation doesn't need the full generality of unordered_map,
426 // and it doesn't have it. More bells and whistles can be added as needed.
427 // Some implementation details:
428 // 1. The hash function has type hasher and the equality function
429 // equal_to<Key>. We inherit from hasher to save space
430 // (empty-base-class optimization).
431 // 2. The number of buckets is a power of two.
432 // 3. Buckets are converted to trees in pairs: if we convert bucket b then
433 // buckets b and b^1 will share a tree. Invariant: buckets b and b^1 have
434 // the same non-null value iff they are sharing a tree. (An alternative
435 // implementation strategy would be to have a tag bit per bucket.)
436 // 4. As is typical for hash_map and such, the Keys and Values are always
437 // stored in linked list nodes. Pointers to elements are never invalidated
438 // until the element is deleted.
439 // 5. The trees' payload type is pointer to linked-list node. Tree-converting
440 // a bucket doesn't copy Key-Value pairs.
441 // 6. Once we've tree-converted a bucket, it is never converted back. However,
442 // the items a tree contains may wind up assigned to trees or lists upon a
443 // rehash.
444 // 7. The code requires no C++ features from C++14 or later.
445 // 8. Mutations to a map do not invalidate the map's iterators, pointers to
446 // elements, or references to elements.
447 // 9. Except for erase(iterator), any non-const method can reorder iterators.
448 // 10. InnerMap uses KeyForTree<Key> when using the Tree representation, which
449 // is either `Key`, if Key is a scalar, or `reference_wrapper<const Key>`
450 // otherwise. This avoids unnecessary copies of string keys, for example.
451 class InnerMap : private hasher {
452 public:
453 explicit constexpr InnerMap(Arena* arena)
454 : hasher(),
455 num_elements_(0),
456 num_buckets_(internal::kGlobalEmptyTableSize),
457 seed_(0),
458 index_of_first_non_null_(internal::kGlobalEmptyTableSize),
459 table_(const_cast<void**>(internal::kGlobalEmptyTable)),
460 alloc_(arena) {}
461
462 ~InnerMap() {
463 if (alloc_.arena() == nullptr &&
464 num_buckets_ != internal::kGlobalEmptyTableSize) {
465 clear();
466 Dealloc<void*>(table_, num_buckets_);
467 }
468 }
469
470 private:
471 enum { kMinTableSize = 8 };
472
473 // Linked-list nodes, as one would expect for a chaining hash table.
474 struct Node {
475 value_type kv;
476 Node* next;
477 };
478
479 // Trees. The payload type is a copy of Key, so that we can query the tree
480 // with Keys that are not in any particular data structure.
481 // The value is a void* pointing to Node. We use void* instead of Node* to
482 // avoid code bloat. That way there is only one instantiation of the tree
483 // class per key type.
484 using Tree = internal::TreeForMap<Key>;
485 using TreeIterator = typename Tree::iterator;
486
487 static Node* NodeFromTreeIterator(TreeIterator it) {
488 return static_cast<Node*>(it->second);
489 }
490
491 // iterator and const_iterator are instantiations of iterator_base.
492 template <typename KeyValueType>
493 class iterator_base {
494 public:
495 using reference = KeyValueType&;
496 using pointer = KeyValueType*;
497
498 // Invariants:
499 // node_ is always correct. This is handy because the most common
500 // operations are operator* and operator-> and they only use node_.
501 // When node_ is set to a non-null value, all the other non-const fields
502 // are updated to be correct also, but those fields can become stale
503 // if the underlying map is modified. When those fields are needed they
504 // are rechecked, and updated if necessary.
505 iterator_base() : node_(nullptr), m_(nullptr), bucket_index_(0) {}
506
507 explicit iterator_base(const InnerMap* m) : m_(m) {
508 SearchFrom(m->index_of_first_non_null_);
509 }
510
511 // Any iterator_base can convert to any other. This is overkill, and we
512 // rely on the enclosing class to use it wisely. The standard "iterator
513 // can convert to const_iterator" is OK but the reverse direction is not.
514 template <typename U>
515 explicit iterator_base(const iterator_base<U>& it)
516 : node_(it.node_), m_(it.m_), bucket_index_(it.bucket_index_) {}
517
518 iterator_base(Node* n, const InnerMap* m, size_type index)
519 : node_(n), m_(m), bucket_index_(index) {}
520
521 iterator_base(TreeIterator tree_it, const InnerMap* m, size_type index)
522 : node_(NodeFromTreeIterator(tree_it)), m_(m), bucket_index_(index) {
523 // Invariant: iterators that use buckets with trees have an even
524 // bucket_index_.
525 GOOGLE_DCHECK_EQ(bucket_index_ % 2, 0u);
526 }
527
528 // Advance through buckets, looking for the first that isn't empty.
529 // If nothing non-empty is found then leave node_ == nullptr.
530 void SearchFrom(size_type start_bucket) {
531 GOOGLE_DCHECK(m_->index_of_first_non_null_ == m_->num_buckets_ ||
532 m_->table_[m_->index_of_first_non_null_] != nullptr);
533 node_ = nullptr;
534 for (bucket_index_ = start_bucket; bucket_index_ < m_->num_buckets_;
535 bucket_index_++) {
536 if (m_->TableEntryIsNonEmptyList(bucket_index_)) {
537 node_ = static_cast<Node*>(m_->table_[bucket_index_]);
538 break;
539 } else if (m_->TableEntryIsTree(bucket_index_)) {
540 Tree* tree = static_cast<Tree*>(m_->table_[bucket_index_]);
541 GOOGLE_DCHECK(!tree->empty());
542 node_ = NodeFromTreeIterator(tree->begin());
543 break;
544 }
545 }
546 }
547
548 reference operator*() const { return node_->kv; }
549 pointer operator->() const { return &(operator*()); }
550
551 friend bool operator==(const iterator_base& a, const iterator_base& b) {
552 return a.node_ == b.node_;
553 }
554 friend bool operator!=(const iterator_base& a, const iterator_base& b) {
555 return a.node_ != b.node_;
556 }
557
558 iterator_base& operator++() {
559 if (node_->next == nullptr) {
560 TreeIterator tree_it;
561 const bool is_list = revalidate_if_necessary(&tree_it);
562 if (is_list) {
563 SearchFrom(bucket_index_ + 1);
564 } else {
565 GOOGLE_DCHECK_EQ(bucket_index_ & 1, 0u);
566 Tree* tree = static_cast<Tree*>(m_->table_[bucket_index_]);
567 if (++tree_it == tree->end()) {
568 SearchFrom(bucket_index_ + 2);
569 } else {
570 node_ = NodeFromTreeIterator(tree_it);
571 }
572 }
573 } else {
574 node_ = node_->next;
575 }
576 return *this;
577 }
578
579 iterator_base operator++(int /* unused */) {
580 iterator_base tmp = *this;
581 ++*this;
582 return tmp;
583 }
584
585 // Assumes node_ and m_ are correct and non-null, but other fields may be
586 // stale. Fix them as needed. Then return true iff node_ points to a
587 // Node in a list. If false is returned then *it is modified to be
588 // a valid iterator for node_.
589 bool revalidate_if_necessary(TreeIterator* it) {
590 GOOGLE_DCHECK(node_ != nullptr && m_ != nullptr);
591 // Force bucket_index_ to be in range.
592 bucket_index_ &= (m_->num_buckets_ - 1);
593 // Common case: the bucket we think is relevant points to node_.
594 if (m_->table_[bucket_index_] == static_cast<void*>(node_)) return true;
595 // Less common: the bucket is a linked list with node_ somewhere in it,
596 // but not at the head.
597 if (m_->TableEntryIsNonEmptyList(bucket_index_)) {
598 Node* l = static_cast<Node*>(m_->table_[bucket_index_]);
599 while ((l = l->next) != nullptr) {
600 if (l == node_) {
601 return true;
602 }
603 }
604 }
605 // Well, bucket_index_ still might be correct, but probably
606 // not. Revalidate just to be sure. This case is rare enough that we
607 // don't worry about potential optimizations, such as having a custom
608 // find-like method that compares Node* instead of the key.
609 iterator_base i(m_->find(node_->kv.first, it));
610 bucket_index_ = i.bucket_index_;
611 return m_->TableEntryIsList(bucket_index_);
612 }
613
614 Node* node_;
615 const InnerMap* m_;
616 size_type bucket_index_;
617 };
618
619 public:
620 using iterator = iterator_base<value_type>;
621 using const_iterator = iterator_base<const value_type>;
622
623 Arena* arena() const { return alloc_.arena(); }
624
625 void Swap(InnerMap* other) {
626 std::swap(num_elements_, other->num_elements_);
627 std::swap(num_buckets_, other->num_buckets_);
628 std::swap(seed_, other->seed_);
629 std::swap(index_of_first_non_null_, other->index_of_first_non_null_);
630 std::swap(table_, other->table_);
631 std::swap(alloc_, other->alloc_);
632 }
633
634 iterator begin() { return iterator(this); }
635 iterator end() { return iterator(); }
636 const_iterator begin() const { return const_iterator(this); }
637 const_iterator end() const { return const_iterator(); }
638
639 void clear() {
640 for (size_type b = 0; b < num_buckets_; b++) {
641 if (TableEntryIsNonEmptyList(b)) {
642 Node* node = static_cast<Node*>(table_[b]);
643 table_[b] = nullptr;
644 do {
645 Node* next = node->next;
646 DestroyNode(node);
647 node = next;
648 } while (node != nullptr);
649 } else if (TableEntryIsTree(b)) {
650 Tree* tree = static_cast<Tree*>(table_[b]);
651 GOOGLE_DCHECK(table_[b] == table_[b + 1] && (b & 1) == 0);
652 table_[b] = table_[b + 1] = nullptr;
653 typename Tree::iterator tree_it = tree->begin();
654 do {
655 Node* node = NodeFromTreeIterator(tree_it);
656 typename Tree::iterator next = tree_it;
657 ++next;
658 tree->erase(tree_it);
659 DestroyNode(node);
660 tree_it = next;
661 } while (tree_it != tree->end());
662 DestroyTree(tree);
663 b++;
664 }
665 }
666 num_elements_ = 0;
667 index_of_first_non_null_ = num_buckets_;
668 }
669
670 const hasher& hash_function() const { return *this; }
671
672 static size_type max_size() {
673 return static_cast<size_type>(1) << (sizeof(void**) >= 8 ? 60 : 28);
674 }
675 size_type size() const { return num_elements_; }
676 bool empty() const { return size() == 0; }
677
678 template <typename K>
679 iterator find(const K& k) {
680 return iterator(FindHelper(k).first);
681 }
682
683 template <typename K>
684 const_iterator find(const K& k) const {
685 return FindHelper(k).first;
686 }
687
688 // Insert the key into the map, if not present. In that case, the value will
689 // be value initialized.
690 template <typename K>
691 std::pair<iterator, bool> insert(K&& k) {
692 std::pair<const_iterator, size_type> p = FindHelper(k);
693 // Case 1: key was already present.
694 if (p.first.node_ != nullptr)
695 return std::make_pair(iterator(p.first), false);
696 // Case 2: insert.
697 if (ResizeIfLoadIsOutOfRange(num_elements_ + 1)) {
698 p = FindHelper(k);
699 }
700 const size_type b = p.second; // bucket number
701 Node* node;
702 // If K is not key_type, make the conversion to key_type explicit.
703 using TypeToInit = typename std::conditional<
704 std::is_same<typename std::decay<K>::type, key_type>::value, K&&,
705 key_type>::type;
706 if (alloc_.arena() == nullptr) {
707 node = new Node{value_type(static_cast<TypeToInit>(std::forward<K>(k))),
708 nullptr};
709 } else {
710 node = Alloc<Node>(1);
711 Arena::CreateInArenaStorage(
712 const_cast<Key*>(&node->kv.first), alloc_.arena(),
713 static_cast<TypeToInit>(std::forward<K>(k)));
714 Arena::CreateInArenaStorage(&node->kv.second, alloc_.arena());
715 }
716
717 iterator result = InsertUnique(b, node);
718 ++num_elements_;
719 return std::make_pair(result, true);
720 }
721
722 template <typename K>
723 value_type& operator[](K&& k) {
724 return *insert(std::forward<K>(k)).first;
725 }
726
727 void erase(iterator it) {
728 GOOGLE_DCHECK_EQ(it.m_, this);
729 typename Tree::iterator tree_it;
730 const bool is_list = it.revalidate_if_necessary(&tree_it);
731 size_type b = it.bucket_index_;
732 Node* const item = it.node_;
733 if (is_list) {
734 GOOGLE_DCHECK(TableEntryIsNonEmptyList(b));
735 Node* head = static_cast<Node*>(table_[b]);
736 head = EraseFromLinkedList(item, head);
737 table_[b] = static_cast<void*>(head);
738 } else {
739 GOOGLE_DCHECK(TableEntryIsTree(b));
740 Tree* tree = static_cast<Tree*>(table_[b]);
741 tree->erase(tree_it);
742 if (tree->empty()) {
743 // Force b to be the minimum of b and b ^ 1. This is important
744 // only because we want index_of_first_non_null_ to be correct.
745 b &= ~static_cast<size_type>(1);
746 DestroyTree(tree);
747 table_[b] = table_[b + 1] = nullptr;
748 }
749 }
750 DestroyNode(item);
751 --num_elements_;
752 if (PROTOBUF_PREDICT_FALSE(b == index_of_first_non_null_)) {
753 while (index_of_first_non_null_ < num_buckets_ &&
754 table_[index_of_first_non_null_] == nullptr) {
755 ++index_of_first_non_null_;
756 }
757 }
758 }
759
760 size_t SpaceUsedInternal() const {
761 return internal::SpaceUsedInTable<Key>(table_, num_buckets_,
762 num_elements_, sizeof(Node));
763 }
764
765 private:
766 const_iterator find(const Key& k, TreeIterator* it) const {
767 return FindHelper(k, it).first;
768 }
769 template <typename K>
770 std::pair<const_iterator, size_type> FindHelper(const K& k) const {
771 return FindHelper(k, nullptr);
772 }
773 template <typename K>
774 std::pair<const_iterator, size_type> FindHelper(const K& k,
775 TreeIterator* it) const {
776 size_type b = BucketNumber(k);
777 if (TableEntryIsNonEmptyList(b)) {
778 Node* node = static_cast<Node*>(table_[b]);
779 do {
780 if (internal::TransparentSupport<Key>::Equals(node->kv.first, k)) {
781 return std::make_pair(const_iterator(node, this, b), b);
782 } else {
783 node = node->next;
784 }
785 } while (node != nullptr);
786 } else if (TableEntryIsTree(b)) {
787 GOOGLE_DCHECK_EQ(table_[b], table_[b ^ 1]);
788 b &= ~static_cast<size_t>(1);
789 Tree* tree = static_cast<Tree*>(table_[b]);
790 auto tree_it = tree->find(k);
791 if (tree_it != tree->end()) {
792 if (it != nullptr) *it = tree_it;
793 return std::make_pair(const_iterator(tree_it, this, b), b);
794 }
795 }
796 return std::make_pair(end(), b);
797 }
798
799 // Insert the given Node in bucket b. If that would make bucket b too big,
800 // and bucket b is not a tree, create a tree for buckets b and b^1 to share.
801 // Requires count(*KeyPtrFromNodePtr(node)) == 0 and that b is the correct
802 // bucket. num_elements_ is not modified.
803 iterator InsertUnique(size_type b, Node* node) {
804 GOOGLE_DCHECK(index_of_first_non_null_ == num_buckets_ ||
805 table_[index_of_first_non_null_] != nullptr);
806 // In practice, the code that led to this point may have already
807 // determined whether we are inserting into an empty list, a short list,
808 // or whatever. But it's probably cheap enough to recompute that here;
809 // it's likely that we're inserting into an empty or short list.
810 iterator result;
811 GOOGLE_DCHECK(find(node->kv.first) == end());
812 if (TableEntryIsEmpty(b)) {
813 result = InsertUniqueInList(b, node);
814 } else if (TableEntryIsNonEmptyList(b)) {
815 if (PROTOBUF_PREDICT_FALSE(TableEntryIsTooLong(b))) {
816 TreeConvert(b);
817 result = InsertUniqueInTree(b, node);
818 GOOGLE_DCHECK_EQ(result.bucket_index_, b & ~static_cast<size_type>(1));
819 } else {
820 // Insert into a pre-existing list. This case cannot modify
821 // index_of_first_non_null_, so we skip the code to update it.
822 return InsertUniqueInList(b, node);
823 }
824 } else {
825 // Insert into a pre-existing tree. This case cannot modify
826 // index_of_first_non_null_, so we skip the code to update it.
827 return InsertUniqueInTree(b, node);
828 }
829 // parentheses around (std::min) prevents macro expansion of min(...)
830 index_of_first_non_null_ =
831 (std::min)(index_of_first_non_null_, result.bucket_index_);
832 return result;
833 }
834
835 // Returns whether we should insert after the head of the list. For
836 // non-optimized builds, we randomly decide whether to insert right at the
837 // head of the list or just after the head. This helps add a little bit of
838 // non-determinism to the map ordering.
839 bool ShouldInsertAfterHead(void* node) {
840 #ifdef NDEBUG
841 (void) node;
842 return false;
843 #else
844 // Doing modulo with a prime mixes the bits more.
845 return (reinterpret_cast<uintptr_t>(node) ^ seed_) % 13 > 6;
846 #endif
847 }
848
849 // Helper for InsertUnique. Handles the case where bucket b is a
850 // not-too-long linked list.
851 iterator InsertUniqueInList(size_type b, Node* node) {
852 if (table_[b] != nullptr && ShouldInsertAfterHead(node)) {
853 Node* first = static_cast<Node*>(table_[b]);
854 node->next = first->next;
855 first->next = node;
856 return iterator(node, this, b);
857 }
858
859 node->next = static_cast<Node*>(table_[b]);
860 table_[b] = static_cast<void*>(node);
861 return iterator(node, this, b);
862 }
863
864 // Helper for InsertUnique. Handles the case where bucket b points to a
865 // Tree.
866 iterator InsertUniqueInTree(size_type b, Node* node) {
867 GOOGLE_DCHECK_EQ(table_[b], table_[b ^ 1]);
868 // Maintain the invariant that node->next is null for all Nodes in Trees.
869 node->next = nullptr;
870 return iterator(
871 static_cast<Tree*>(table_[b])->insert({node->kv.first, node}).first,
872 this, b & ~static_cast<size_t>(1));
873 }
874
875 // Returns whether it did resize. Currently this is only used when
876 // num_elements_ increases, though it could be used in other situations.
877 // It checks for load too low as well as load too high: because any number
878 // of erases can occur between inserts, the load could be as low as 0 here.
879 // Resizing to a lower size is not always helpful, but failing to do so can
880 // destroy the expected big-O bounds for some operations. By having the
881 // policy that sometimes we resize down as well as up, clients can easily
882 // keep O(size()) = O(number of buckets) if they want that.
883 bool ResizeIfLoadIsOutOfRange(size_type new_size) {
884 const size_type kMaxMapLoadTimes16 = 12; // controls RAM vs CPU tradeoff
885 const size_type hi_cutoff = num_buckets_ * kMaxMapLoadTimes16 / 16;
886 const size_type lo_cutoff = hi_cutoff / 4;
887 // We don't care how many elements are in trees. If a lot are,
888 // we may resize even though there are many empty buckets. In
889 // practice, this seems fine.
890 if (PROTOBUF_PREDICT_FALSE(new_size >= hi_cutoff)) {
891 if (num_buckets_ <= max_size() / 2) {
892 Resize(num_buckets_ * 2);
893 return true;
894 }
895 } else if (PROTOBUF_PREDICT_FALSE(new_size <= lo_cutoff &&
896 num_buckets_ > kMinTableSize)) {
897 size_type lg2_of_size_reduction_factor = 1;
898 // It's possible we want to shrink a lot here... size() could even be 0.
899 // So, estimate how much to shrink by making sure we don't shrink so
900 // much that we would need to grow the table after a few inserts.
901 const size_type hypothetical_size = new_size * 5 / 4 + 1;
902 while ((hypothetical_size << lg2_of_size_reduction_factor) <
903 hi_cutoff) {
904 ++lg2_of_size_reduction_factor;
905 }
906 size_type new_num_buckets = std::max<size_type>(
907 kMinTableSize, num_buckets_ >> lg2_of_size_reduction_factor);
908 if (new_num_buckets != num_buckets_) {
909 Resize(new_num_buckets);
910 return true;
911 }
912 }
913 return false;
914 }
915
916 // Resize to the given number of buckets.
917 void Resize(size_t new_num_buckets) {
918 if (num_buckets_ == internal::kGlobalEmptyTableSize) {
919 // This is the global empty array.
920 // Just overwrite with a new one. No need to transfer or free anything.
921 num_buckets_ = index_of_first_non_null_ = kMinTableSize;
922 table_ = CreateEmptyTable(num_buckets_);
923 seed_ = Seed();
924 return;
925 }
926
927 GOOGLE_DCHECK_GE(new_num_buckets, kMinTableSize);
928 void** const old_table = table_;
929 const size_type old_table_size = num_buckets_;
930 num_buckets_ = new_num_buckets;
931 table_ = CreateEmptyTable(num_buckets_);
932 const size_type start = index_of_first_non_null_;
933 index_of_first_non_null_ = num_buckets_;
934 for (size_type i = start; i < old_table_size; i++) {
935 if (internal::TableEntryIsNonEmptyList(old_table, i)) {
936 TransferList(old_table, i);
937 } else if (internal::TableEntryIsTree(old_table, i)) {
938 TransferTree(old_table, i++);
939 }
940 }
941 Dealloc<void*>(old_table, old_table_size);
942 }
943
944 void TransferList(void* const* table, size_type index) {
945 Node* node = static_cast<Node*>(table[index]);
946 do {
947 Node* next = node->next;
948 InsertUnique(BucketNumber(node->kv.first), node);
949 node = next;
950 } while (node != nullptr);
951 }
952
953 void TransferTree(void* const* table, size_type index) {
954 Tree* tree = static_cast<Tree*>(table[index]);
955 typename Tree::iterator tree_it = tree->begin();
956 do {
957 InsertUnique(BucketNumber(std::cref(tree_it->first).get()),
958 NodeFromTreeIterator(tree_it));
959 } while (++tree_it != tree->end());
960 DestroyTree(tree);
961 }
962
963 Node* EraseFromLinkedList(Node* item, Node* head) {
964 if (head == item) {
965 return head->next;
966 } else {
967 head->next = EraseFromLinkedList(item, head->next);
968 return head;
969 }
970 }
971
972 bool TableEntryIsEmpty(size_type b) const {
973 return internal::TableEntryIsEmpty(table_, b);
974 }
975 bool TableEntryIsNonEmptyList(size_type b) const {
976 return internal::TableEntryIsNonEmptyList(table_, b);
977 }
978 bool TableEntryIsTree(size_type b) const {
979 return internal::TableEntryIsTree(table_, b);
980 }
981 bool TableEntryIsList(size_type b) const {
982 return internal::TableEntryIsList(table_, b);
983 }
984
985 void TreeConvert(size_type b) {
986 GOOGLE_DCHECK(!TableEntryIsTree(b) && !TableEntryIsTree(b ^ 1));
987 Tree* tree =
988 Arena::Create<Tree>(alloc_.arena(), typename Tree::key_compare(),
989 typename Tree::allocator_type(alloc_));
990 size_type count = CopyListToTree(b, tree) + CopyListToTree(b ^ 1, tree);
991 GOOGLE_DCHECK_EQ(count, tree->size());
992 table_[b] = table_[b ^ 1] = static_cast<void*>(tree);
993 }
994
995 // Copy a linked list in the given bucket to a tree.
996 // Returns the number of things it copied.
997 size_type CopyListToTree(size_type b, Tree* tree) {
998 size_type count = 0;
999 Node* node = static_cast<Node*>(table_[b]);
1000 while (node != nullptr) {
1001 tree->insert({node->kv.first, node});
1002 ++count;
1003 Node* next = node->next;
1004 node->next = nullptr;
1005 node = next;
1006 }
1007 return count;
1008 }
1009
1010 // Return whether table_[b] is a linked list that seems awfully long.
1011 // Requires table_[b] to point to a non-empty linked list.
1012 bool TableEntryIsTooLong(size_type b) {
1013 const size_type kMaxLength = 8;
1014 size_type count = 0;
1015 Node* node = static_cast<Node*>(table_[b]);
1016 do {
1017 ++count;
1018 node = node->next;
1019 } while (node != nullptr);
1020 // Invariant: no linked list ever is more than kMaxLength in length.
1021 GOOGLE_DCHECK_LE(count, kMaxLength);
1022 return count >= kMaxLength;
1023 }
1024
1025 template <typename K>
1026 size_type BucketNumber(const K& k) const {
1027 // We xor the hash value against the random seed so that we effectively
1028 // have a random hash function.
1029 uint64 h = hash_function()(k) ^ seed_;
1030
1031 // We use the multiplication method to determine the bucket number from
1032 // the hash value. The constant kPhi (suggested by Knuth) is roughly
1033 // (sqrt(5) - 1) / 2 * 2^64.
1034 constexpr uint64 kPhi = uint64{0x9e3779b97f4a7c15};
1035 return ((kPhi * h) >> 32) & (num_buckets_ - 1);
1036 }
1037
1038 // Return a power of two no less than max(kMinTableSize, n).
1039 // Assumes either n < kMinTableSize or n is a power of two.
1040 size_type TableSize(size_type n) {
1041 return n < static_cast<size_type>(kMinTableSize)
1042 ? static_cast<size_type>(kMinTableSize)
1043 : n;
1044 }
1045
1046 // Use alloc_ to allocate an array of n objects of type U.
1047 template <typename U>
1048 U* Alloc(size_type n) {
1049 using alloc_type = typename Allocator::template rebind<U>::other;
1050 return alloc_type(alloc_).allocate(n);
1051 }
1052
1053 // Use alloc_ to deallocate an array of n objects of type U.
1054 template <typename U>
1055 void Dealloc(U* t, size_type n) {
1056 using alloc_type = typename Allocator::template rebind<U>::other;
1057 alloc_type(alloc_).deallocate(t, n);
1058 }
1059
1060 void DestroyNode(Node* node) {
1061 if (alloc_.arena() == nullptr) {
1062 delete node;
1063 }
1064 }
1065
1066 void DestroyTree(Tree* tree) {
1067 if (alloc_.arena() == nullptr) {
1068 delete tree;
1069 }
1070 }
1071
1072 void** CreateEmptyTable(size_type n) {
1073 GOOGLE_DCHECK(n >= kMinTableSize);
1074 GOOGLE_DCHECK_EQ(n & (n - 1), 0);
1075 void** result = Alloc<void*>(n);
1076 memset(result, 0, n * sizeof(result[0]));
1077 return result;
1078 }
1079
1080 // Return a randomish value.
1081 size_type Seed() const {
1082 // We get a little bit of randomness from the address of the map. The
1083 // lower bits are not very random, due to alignment, so we discard them
1084 // and shift the higher bits into their place.
1085 size_type s = reinterpret_cast<uintptr_t>(this) >> 12;
1086 #if defined(__x86_64__) && defined(__GNUC__) && \
1087 !defined(GOOGLE_PROTOBUF_NO_RDTSC)
1088 uint32 hi, lo;
1089 asm volatile("rdtsc" : "=a"(lo), "=d"(hi));
1090 s += ((static_cast<uint64>(hi) << 32) | lo);
1091 #endif
1092 return s;
1093 }
1094
1095 friend class Arena;
1096 using InternalArenaConstructable_ = void;
1097 using DestructorSkippable_ = void;
1098
1099 size_type num_elements_;
1100 size_type num_buckets_;
1101 size_type seed_;
1102 size_type index_of_first_non_null_;
1103 void** table_; // an array with num_buckets_ entries
1104 Allocator alloc_;
1105 GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(InnerMap);
1106 }; // end of class InnerMap
1107
1108 template <typename LookupKey>
1109 using key_arg = typename internal::TransparentSupport<
1110 key_type>::template key_arg<LookupKey>;
1111
1112 public:
1113 // Iterators
1114 class const_iterator {
1115 using InnerIt = typename InnerMap::const_iterator;
1116
1117 public:
1118 using iterator_category = std::forward_iterator_tag;
1119 using value_type = typename Map::value_type;
1120 using difference_type = ptrdiff_t;
1121 using pointer = const value_type*;
1122 using reference = const value_type&;
1123
1124 const_iterator() {}
1125 explicit const_iterator(const InnerIt& it) : it_(it) {}
1126
1127 const_reference operator*() const { return *it_; }
1128 const_pointer operator->() const { return &(operator*()); }
1129
1130 const_iterator& operator++() {
1131 ++it_;
1132 return *this;
1133 }
1134 const_iterator operator++(int) { return const_iterator(it_++); }
1135
1136 friend bool operator==(const const_iterator& a, const const_iterator& b) {
1137 return a.it_ == b.it_;
1138 }
1139 friend bool operator!=(const const_iterator& a, const const_iterator& b) {
1140 return !(a == b);
1141 }
1142
1143 private:
1144 InnerIt it_;
1145 };
1146
1147 class iterator {
1148 using InnerIt = typename InnerMap::iterator;
1149
1150 public:
1151 using iterator_category = std::forward_iterator_tag;
1152 using value_type = typename Map::value_type;
1153 using difference_type = ptrdiff_t;
1154 using pointer = value_type*;
1155 using reference = value_type&;
1156
1157 iterator() {}
1158 explicit iterator(const InnerIt& it) : it_(it) {}
1159
1160 reference operator*() const { return *it_; }
1161 pointer operator->() const { return &(operator*()); }
1162
1163 iterator& operator++() {
1164 ++it_;
1165 return *this;
1166 }
1167 iterator operator++(int) { return iterator(it_++); }
1168
1169 // Allow implicit conversion to const_iterator.
1170 operator const_iterator() const { // NOLINT(runtime/explicit)
1171 return const_iterator(typename InnerMap::const_iterator(it_));
1172 }
1173
1174 friend bool operator==(const iterator& a, const iterator& b) {
1175 return a.it_ == b.it_;
1176 }
1177 friend bool operator!=(const iterator& a, const iterator& b) {
1178 return !(a == b);
1179 }
1180
1181 private:
1182 friend class Map;
1183
1184 InnerIt it_;
1185 };
1186
1187 iterator begin() { return iterator(elements_.begin()); }
1188 iterator end() { return iterator(elements_.end()); }
1189 const_iterator begin() const { return const_iterator(elements_.begin()); }
1190 const_iterator end() const { return const_iterator(elements_.end()); }
1191 const_iterator cbegin() const { return begin(); }
1192 const_iterator cend() const { return end(); }
1193
1194 // Capacity
1195 size_type size() const { return elements_.size(); }
1196 bool empty() const { return size() == 0; }
1197
1198 // Element access
1199 template <typename K = key_type>
1200 T& operator[](const key_arg<K>& key) {
1201 return elements_[key].second;
1202 }
1203 template <
1204 typename K = key_type,
1205 // Disable for integral types to reduce code bloat.
1206 typename = typename std::enable_if<!std::is_integral<K>::value>::type>
1207 T& operator[](key_arg<K>&& key) {
1208 return elements_[std::forward<K>(key)].second;
1209 }
1210
1211 template <typename K = key_type>
1212 const T& at(const key_arg<K>& key) const {
1213 const_iterator it = find(key);
1214 GOOGLE_CHECK(it != end()) << "key not found: " << static_cast<Key>(key);
1215 return it->second;
1216 }
1217
1218 template <typename K = key_type>
1219 T& at(const key_arg<K>& key) {
1220 iterator it = find(key);
1221 GOOGLE_CHECK(it != end()) << "key not found: " << static_cast<Key>(key);
1222 return it->second;
1223 }
1224
1225 // Lookup
1226 template <typename K = key_type>
1227 size_type count(const key_arg<K>& key) const {
1228 return find(key) == end() ? 0 : 1;
1229 }
1230
1231 template <typename K = key_type>
1232 const_iterator find(const key_arg<K>& key) const {
1233 return const_iterator(elements_.find(key));
1234 }
1235 template <typename K = key_type>
1236 iterator find(const key_arg<K>& key) {
1237 return iterator(elements_.find(key));
1238 }
1239
1240 template <typename K = key_type>
1241 bool contains(const key_arg<K>& key) const {
1242 return find(key) != end();
1243 }
1244
1245 template <typename K = key_type>
1246 std::pair<const_iterator, const_iterator> equal_range(
1247 const key_arg<K>& key) const {
1248 const_iterator it = find(key);
1249 if (it == end()) {
1250 return std::pair<const_iterator, const_iterator>(it, it);
1251 } else {
1252 const_iterator begin = it++;
1253 return std::pair<const_iterator, const_iterator>(begin, it);
1254 }
1255 }
1256
1257 template <typename K = key_type>
1258 std::pair<iterator, iterator> equal_range(const key_arg<K>& key) {
1259 iterator it = find(key);
1260 if (it == end()) {
1261 return std::pair<iterator, iterator>(it, it);
1262 } else {
1263 iterator begin = it++;
1264 return std::pair<iterator, iterator>(begin, it);
1265 }
1266 }
1267
1268 // insert
1269 std::pair<iterator, bool> insert(const value_type& value) {
1270 std::pair<typename InnerMap::iterator, bool> p =
1271 elements_.insert(value.first);
1272 if (p.second) {
1273 p.first->second = value.second;
1274 }
1275 return std::pair<iterator, bool>(iterator(p.first), p.second);
1276 }
1277 template <class InputIt>
1278 void insert(InputIt first, InputIt last) {
1279 for (InputIt it = first; it != last; ++it) {
1280 iterator exist_it = find(it->first);
1281 if (exist_it == end()) {
1282 operator[](it->first) = it->second;
1283 }
1284 }
1285 }
1286 void insert(std::initializer_list<value_type> values) {
1287 insert(values.begin(), values.end());
1288 }
1289
1290 // Erase and clear
1291 template <typename K = key_type>
1292 size_type erase(const key_arg<K>& key) {
1293 iterator it = find(key);
1294 if (it == end()) {
1295 return 0;
1296 } else {
1297 erase(it);
1298 return 1;
1299 }
1300 }
1301 iterator erase(iterator pos) {
1302 iterator i = pos++;
1303 elements_.erase(i.it_);
1304 return pos;
1305 }
1306 void erase(iterator first, iterator last) {
1307 while (first != last) {
1308 first = erase(first);
1309 }
1310 }
1311 void clear() { elements_.clear(); }
1312
1313 // Assign
1314 Map& operator=(const Map& other) {
1315 if (this != &other) {
1316 clear();
1317 insert(other.begin(), other.end());
1318 }
1319 return *this;
1320 }
1321
1322 void swap(Map& other) {
1323 if (arena() == other.arena()) {
1324 elements_.Swap(&other.elements_);
1325 } else {
1326 // TODO(zuguang): optimize this. The temporary copy can be allocated
1327 // in the same arena as the other message, and the "other = copy" can
1328 // be replaced with the fast-path swap above.
1329 Map copy = *this;
1330 *this = other;
1331 other = copy;
1332 }
1333 }
1334
1335 // Access to hasher. Currently this returns a copy, but it may
1336 // be modified to return a const reference in the future.
1337 hasher hash_function() const { return elements_.hash_function(); }
1338
1339 size_t SpaceUsedExcludingSelfLong() const {
1340 if (empty()) return 0;
1341 return elements_.SpaceUsedInternal() + internal::SpaceUsedInValues(this);
1342 }
1343
1344 private:
1345 Arena* arena() const { return elements_.arena(); }
1346 InnerMap elements_;
1347
1348 friend class Arena;
1349 using InternalArenaConstructable_ = void;
1350 using DestructorSkippable_ = void;
1351 template <typename Derived, typename K, typename V,
1352 internal::WireFormatLite::FieldType key_wire_type,
1353 internal::WireFormatLite::FieldType value_wire_type>
1354 friend class internal::MapFieldLite;
1355 };
1356
1357 } // namespace protobuf
1358 } // namespace google
1359
1360 #include <google/protobuf/port_undef.inc>
1361
1362 #endif // GOOGLE_PROTOBUF_MAP_H__