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

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