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