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

source code of include/google/protobuf/map.h