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