15a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// Protocol Buffers - Google's data interchange format 25a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// Copyright 2008 Google Inc. All rights reserved. 35a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// https://developers.google.com/protocol-buffers/ 45a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// 55a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// Redistribution and use in source and binary forms, with or without 65a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// modification, are permitted provided that the following conditions are 75a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// met: 85a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// 95a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// * Redistributions of source code must retain the above copyright 105a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// notice, this list of conditions and the following disclaimer. 115a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// * Redistributions in binary form must reproduce the above 125a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// copyright notice, this list of conditions and the following disclaimer 135a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// in the documentation and/or other materials provided with the 145a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// distribution. 155a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// * Neither the name of Google Inc. nor the names of its 165a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// contributors may be used to endorse or promote products derived from 175a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// this software without specific prior written permission. 185a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// 195a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 205a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 215a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 225a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 235a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 245a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 255a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 265a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 275a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 285a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 295a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 305a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 315a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#ifndef GOOGLE_PROTOBUF_MAP_H__ 325a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#define GOOGLE_PROTOBUF_MAP_H__ 335a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 345a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#include <google/protobuf/stubs/hash.h> 355a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#include <iterator> 365a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#include <limits> // To support Visual Studio 2008 375a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#include <set> 385a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#include <utility> 395a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 405a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#include <google/protobuf/stubs/common.h> 415a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#include <google/protobuf/arena.h> 425a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#include <google/protobuf/generated_enum_util.h> 435a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#include <google/protobuf/map_type_handler.h> 445a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#include <google/protobuf/message.h> 455a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#include <google/protobuf/descriptor.h> 465a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#if __cpp_exceptions && LANG_CXX11 475a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#include <random> 485a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#endif 495a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 505a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robotnamespace google { 515a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robotnamespace protobuf { 525a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 535a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// The Map and MapIterator types are provided by this header file. 545a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// Please avoid using other types defined here, unless they are public 555a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// types within Map or MapIterator, such as Map::value_type. 565a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robottemplate <typename Key, typename T> 575a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robotclass Map; 585a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 595a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robotclass MapIterator; 605a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 615a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robottemplate <typename Enum> struct is_proto_enum; 625a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 635a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robotnamespace internal { 645a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robottemplate <typename Key, typename T, 655a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot WireFormatLite::FieldType key_wire_type, 665a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot WireFormatLite::FieldType value_wire_type, 675a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot int default_enum_value> 685a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robotclass MapFieldLite; 695a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 705a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robottemplate <typename Key, typename T, 715a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot WireFormatLite::FieldType key_wire_type, 725a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot WireFormatLite::FieldType value_wire_type, 735a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot int default_enum_value> 745a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robotclass MapField; 755a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 765a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robottemplate <typename Key, typename T> 775a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robotclass TypeDefinedMapFieldBase; 785a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 795a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robotclass DynamicMapField; 805a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 815a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robotclass GeneratedMessageReflection; 825a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot} // namespace internal 835a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 845a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#define TYPE_CHECK(EXPECTEDTYPE, METHOD) \ 855a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (type() != EXPECTEDTYPE) { \ 865a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_LOG(FATAL) \ 875a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot << "Protocol Buffer map usage error:\n" \ 885a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot << METHOD << " type does not match\n" \ 895a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot << " Expected : " \ 905a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot << FieldDescriptor::CppTypeName(EXPECTEDTYPE) << "\n" \ 915a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot << " Actual : " \ 925a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot << FieldDescriptor::CppTypeName(type()); \ 935a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 945a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 955a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// MapKey is an union type for representing any possible 965a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// map key. 975a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robotclass LIBPROTOBUF_EXPORT MapKey { 985a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot public: 995a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot MapKey() : type_(0) { 1005a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 1015a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot MapKey(const MapKey& other) : type_(0) { 1025a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot CopyFrom(other); 1035a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 1045a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 1055a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot ~MapKey() { 1065a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (type_ == FieldDescriptor::CPPTYPE_STRING) { 1075a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot delete val_.string_value_; 1085a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 1095a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 1105a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 1115a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot FieldDescriptor::CppType type() const { 1125a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (type_ == 0) { 1135a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_LOG(FATAL) 1145a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot << "Protocol Buffer map usage error:\n" 1155a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot << "MapKey::type MapKey is not initialized. " 1165a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot << "Call set methods to initialize MapKey."; 1175a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 1185a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return (FieldDescriptor::CppType)type_; 1195a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 1205a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 1215a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void SetInt64Value(int64 value) { 1225a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot SetType(FieldDescriptor::CPPTYPE_INT64); 1235a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot val_.int64_value_ = value; 1245a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 1255a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void SetUInt64Value(uint64 value) { 1265a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot SetType(FieldDescriptor::CPPTYPE_UINT64); 1275a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot val_.uint64_value_ = value; 1285a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 1295a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void SetInt32Value(int32 value) { 1305a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot SetType(FieldDescriptor::CPPTYPE_INT32); 1315a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot val_.int32_value_ = value; 1325a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 1335a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void SetUInt32Value(uint32 value) { 1345a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot SetType(FieldDescriptor::CPPTYPE_UINT32); 1355a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot val_.uint32_value_ = value; 1365a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 1375a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void SetBoolValue(bool value) { 1385a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot SetType(FieldDescriptor::CPPTYPE_BOOL); 1395a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot val_.bool_value_ = value; 1405a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 1415a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void SetStringValue(const string& val) { 1425a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot SetType(FieldDescriptor::CPPTYPE_STRING); 1435a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot *val_.string_value_ = val; 1445a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 1455a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 1465a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot int64 GetInt64Value() const { 1475a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_INT64, 1485a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapKey::GetInt64Value"); 1495a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return val_.int64_value_; 1505a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 1515a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot uint64 GetUInt64Value() const { 1525a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_UINT64, 1535a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapKey::GetUInt64Value"); 1545a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return val_.uint64_value_; 1555a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 1565a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot int32 GetInt32Value() const { 1575a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_INT32, 1585a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapKey::GetInt32Value"); 1595a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return val_.int32_value_; 1605a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 1615a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot uint32 GetUInt32Value() const { 1625a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_UINT32, 1635a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapKey::GetUInt32Value"); 1645a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return val_.uint32_value_; 1655a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 1665a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bool GetBoolValue() const { 1675a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_BOOL, 1685a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapKey::GetBoolValue"); 1695a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return val_.bool_value_; 1705a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 1715a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const string& GetStringValue() const { 1725a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_STRING, 1735a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapKey::GetStringValue"); 1745a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return *val_.string_value_; 1755a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 1765a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 1775a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bool operator<(const MapKey& other) const { 1785a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (type_ != other.type_) { 1795a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // We could define a total order that handles this case, but 1805a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // there currently no need. So, for now, fail. 1815a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_LOG(FATAL) << "Unsupported: type mismatch"; 1825a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 1835a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot switch (type()) { 1845a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_DOUBLE: 1855a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_FLOAT: 1865a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_ENUM: 1875a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_MESSAGE: 1885a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_LOG(FATAL) << "Unsupported"; 1895a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return false; 1905a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_STRING: 1915a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return *val_.string_value_ < *other.val_.string_value_; 1925a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_INT64: 1935a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return val_.int64_value_ < other.val_.int64_value_; 1945a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_INT32: 1955a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return val_.int32_value_ < other.val_.int32_value_; 1965a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_UINT64: 1975a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return val_.uint64_value_ < other.val_.uint64_value_; 1985a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_UINT32: 1995a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return val_.uint32_value_ < other.val_.uint32_value_; 2005a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_BOOL: 2015a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return val_.bool_value_ < other.val_.bool_value_; 2025a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 2035a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return false; 2045a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 2055a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 2065a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bool operator==(const MapKey& other) const { 2075a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (type_ != other.type_) { 2085a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // To be consistent with operator<, we don't allow this either. 2095a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_LOG(FATAL) << "Unsupported: type mismatch"; 2105a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 2115a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot switch (type()) { 2125a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_DOUBLE: 2135a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_FLOAT: 2145a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_ENUM: 2155a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_MESSAGE: 2165a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_LOG(FATAL) << "Unsupported"; 2175a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot break; 2185a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_STRING: 2195a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return *val_.string_value_ == *other.val_.string_value_; 2205a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_INT64: 2215a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return val_.int64_value_ == other.val_.int64_value_; 2225a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_INT32: 2235a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return val_.int32_value_ == other.val_.int32_value_; 2245a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_UINT64: 2255a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return val_.uint64_value_ == other.val_.uint64_value_; 2265a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_UINT32: 2275a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return val_.uint32_value_ == other.val_.uint32_value_; 2285a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_BOOL: 2295a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return val_.bool_value_ == other.val_.bool_value_; 2305a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 2315a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_LOG(FATAL) << "Can't get here."; 2325a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return false; 2335a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 2345a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 2355a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void CopyFrom(const MapKey& other) { 2365a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot SetType(other.type()); 2375a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot switch (type_) { 2385a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_DOUBLE: 2395a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_FLOAT: 2405a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_ENUM: 2415a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_MESSAGE: 2425a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_LOG(FATAL) << "Unsupported"; 2435a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot break; 2445a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_STRING: 2455a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot *val_.string_value_ = *other.val_.string_value_; 2465a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot break; 2475a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_INT64: 2485a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot val_.int64_value_ = other.val_.int64_value_; 2495a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot break; 2505a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_INT32: 2515a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot val_.int32_value_ = other.val_.int32_value_; 2525a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot break; 2535a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_UINT64: 2545a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot val_.uint64_value_ = other.val_.uint64_value_; 2555a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot break; 2565a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_UINT32: 2575a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot val_.uint32_value_ = other.val_.uint32_value_; 2585a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot break; 2595a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case FieldDescriptor::CPPTYPE_BOOL: 2605a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot val_.bool_value_ = other.val_.bool_value_; 2615a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot break; 2625a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 2635a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 2645a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 2655a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot private: 2665a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot template <typename K, typename V> 2675a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot friend class internal::TypeDefinedMapFieldBase; 2685a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot friend class MapIterator; 2695a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot friend class internal::DynamicMapField; 2705a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 2715a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot union KeyValue { 2725a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot KeyValue() {} 2735a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot string* string_value_; 2745a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot int64 int64_value_; 2755a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot int32 int32_value_; 2765a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot uint64 uint64_value_; 2775a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot uint32 uint32_value_; 2785a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bool bool_value_; 2795a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } val_; 2805a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 2815a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void SetType(FieldDescriptor::CppType type) { 2825a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (type_ == type) return; 2835a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (type_ == FieldDescriptor::CPPTYPE_STRING) { 2845a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot delete val_.string_value_; 2855a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 2865a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot type_ = type; 2875a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (type_ == FieldDescriptor::CPPTYPE_STRING) { 2885a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot val_.string_value_ = new string; 2895a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 2905a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 2915a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 2925a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // type_ is 0 or a valid FieldDescriptor::CppType. 2935a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot int type_; 2945a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot}; 2955a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 2965a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// MapValueRef points to a map value. 2975a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robotclass LIBPROTOBUF_EXPORT MapValueRef { 2985a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot public: 2995a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot MapValueRef() : data_(NULL), type_(0) {} 3005a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 3015a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void SetInt64Value(int64 value) { 3025a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_INT64, 3035a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapValueRef::SetInt64Value"); 3045a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot *reinterpret_cast<int64*>(data_) = value; 3055a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 3065a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void SetUInt64Value(uint64 value) { 3075a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_UINT64, 3085a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapValueRef::SetUInt64Value"); 3095a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot *reinterpret_cast<uint64*>(data_) = value; 3105a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 3115a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void SetInt32Value(int32 value) { 3125a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_INT32, 3135a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapValueRef::SetInt32Value"); 3145a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot *reinterpret_cast<int32*>(data_) = value; 3155a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 3165a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void SetUInt32Value(uint32 value) { 3175a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_UINT32, 3185a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapValueRef::SetUInt32Value"); 3195a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot *reinterpret_cast<uint32*>(data_) = value; 3205a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 3215a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void SetBoolValue(bool value) { 3225a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_BOOL, 3235a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapValueRef::SetBoolValue"); 3245a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot *reinterpret_cast<bool*>(data_) = value; 3255a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 3265a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // TODO(jieluo) - Checks that enum is member. 3275a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void SetEnumValue(int value) { 3285a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_ENUM, 3295a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapValueRef::SetEnumValue"); 3305a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot *reinterpret_cast<int*>(data_) = value; 3315a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 3325a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void SetStringValue(const string& value) { 3335a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_STRING, 3345a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapValueRef::SetStringValue"); 3355a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot *reinterpret_cast<string*>(data_) = value; 3365a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 3375a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void SetFloatValue(float value) { 3385a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_FLOAT, 3395a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapValueRef::SetFloatValue"); 3405a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot *reinterpret_cast<float*>(data_) = value; 3415a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 3425a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void SetDoubleValue(double value) { 3435a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_DOUBLE, 3445a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapValueRef::SetDoubleValue"); 3455a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot *reinterpret_cast<double*>(data_) = value; 3465a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 3475a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 3485a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot int64 GetInt64Value() const { 3495a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_INT64, 3505a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapValueRef::GetInt64Value"); 3515a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return *reinterpret_cast<int64*>(data_); 3525a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 3535a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot uint64 GetUInt64Value() const { 3545a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_UINT64, 3555a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapValueRef::GetUInt64Value"); 3565a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return *reinterpret_cast<uint64*>(data_); 3575a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 3585a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot int32 GetInt32Value() const { 3595a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_INT32, 3605a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapValueRef::GetInt32Value"); 3615a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return *reinterpret_cast<int32*>(data_); 3625a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 3635a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot uint32 GetUInt32Value() const { 3645a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_UINT32, 3655a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapValueRef::GetUInt32Value"); 3665a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return *reinterpret_cast<uint32*>(data_); 3675a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 3685a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bool GetBoolValue() const { 3695a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_BOOL, 3705a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapValueRef::GetBoolValue"); 3715a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return *reinterpret_cast<bool*>(data_); 3725a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 3735a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot int GetEnumValue() const { 3745a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_ENUM, 3755a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapValueRef::GetEnumValue"); 3765a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return *reinterpret_cast<int*>(data_); 3775a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 3785a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const string& GetStringValue() const { 3795a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_STRING, 3805a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapValueRef::GetStringValue"); 3815a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return *reinterpret_cast<string*>(data_); 3825a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 3835a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot float GetFloatValue() const { 3845a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_FLOAT, 3855a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapValueRef::GetFloatValue"); 3865a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return *reinterpret_cast<float*>(data_); 3875a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 3885a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot double GetDoubleValue() const { 3895a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_DOUBLE, 3905a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapValueRef::GetDoubleValue"); 3915a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return *reinterpret_cast<double*>(data_); 3925a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 3935a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 3945a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const Message& GetMessageValue() const { 3955a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_MESSAGE, 3965a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapValueRef::GetMessageValue"); 3975a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return *reinterpret_cast<Message*>(data_); 3985a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 3995a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 4005a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Message* MutableMessageValue() { 4015a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TYPE_CHECK(FieldDescriptor::CPPTYPE_MESSAGE, 4025a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot "MapValueRef::MutableMessageValue"); 4035a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return reinterpret_cast<Message*>(data_); 4045a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 4055a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 4065a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot private: 4075a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot template <typename K, typename V, 4085a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot internal::WireFormatLite::FieldType key_wire_type, 4095a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot internal::WireFormatLite::FieldType value_wire_type, 4105a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot int default_enum_value> 4115a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot friend class internal::MapField; 4125a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot template <typename K, typename V> 4135a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot friend class internal::TypeDefinedMapFieldBase; 4145a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot friend class MapIterator; 4155a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot friend class internal::GeneratedMessageReflection; 4165a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot friend class internal::DynamicMapField; 4175a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 4185a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void SetType(FieldDescriptor::CppType type) { 4195a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot type_ = type; 4205a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 4215a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 4225a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot FieldDescriptor::CppType type() const { 4235a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (type_ == 0 || data_ == NULL) { 4245a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_LOG(FATAL) 4255a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot << "Protocol Buffer map usage error:\n" 4265a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot << "MapValueRef::type MapValueRef is not initialized."; 4275a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 4285a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return (FieldDescriptor::CppType)type_; 4295a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 4305a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void SetValue(const void* val) { 4315a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot data_ = const_cast<void*>(val); 4325a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 4335a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void CopyFrom(const MapValueRef& other) { 4345a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot type_ = other.type_; 4355a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot data_ = other.data_; 4365a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 4375a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Only used in DynamicMapField 4385a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void DeleteData() { 4395a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot switch (type_) { 4405a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#define HANDLE_TYPE(CPPTYPE, TYPE) \ 4415a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case google::protobuf::FieldDescriptor::CPPTYPE_##CPPTYPE: { \ 4425a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot delete reinterpret_cast<TYPE*>(data_); \ 4435a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot break; \ 4445a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 4455a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot HANDLE_TYPE(INT32, int32); 4465a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot HANDLE_TYPE(INT64, int64); 4475a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot HANDLE_TYPE(UINT32, uint32); 4485a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot HANDLE_TYPE(UINT64, uint64); 4495a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot HANDLE_TYPE(DOUBLE, double); 4505a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot HANDLE_TYPE(FLOAT, float); 4515a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot HANDLE_TYPE(BOOL, bool); 4525a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot HANDLE_TYPE(STRING, string); 4535a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot HANDLE_TYPE(ENUM, int32); 4545a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot HANDLE_TYPE(MESSAGE, Message); 4555a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#undef HANDLE_TYPE 4565a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 4575a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 4585a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // data_ point to a map value. MapValueRef does not 4595a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // own this value. 4605a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void* data_; 4615a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // type_ is 0 or a valid FieldDescriptor::CppType. 4625a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot int type_; 4635a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot}; 4645a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 4655a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#undef TYPE_CHECK 4665a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 4675a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// This is the class for google::protobuf::Map's internal value_type. Instead of using 4685a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// std::pair as value_type, we use this class which provides us more control of 4695a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// its process of construction and destruction. 4705a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robottemplate <typename Key, typename T> 4715a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robotclass MapPair { 4725a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot public: 4735a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef const Key first_type; 4745a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef T second_type; 4755a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 4765a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot MapPair(const Key& other_first, const T& other_second) 4775a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : first(other_first), second(other_second) {} 4785a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot explicit MapPair(const Key& other_first) : first(other_first), second() {} 4795a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot MapPair(const MapPair& other) 4805a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : first(other.first), second(other.second) {} 4815a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 4825a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot ~MapPair() {} 4835a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 4845a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Implicitly convertible to std::pair of compatible types. 4855a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot template <typename T1, typename T2> 4865a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot operator std::pair<T1, T2>() const { 4875a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return std::pair<T1, T2>(first, second); 4885a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 4895a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 4905a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const Key first; 4915a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot T second; 4925a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 4935a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot private: 4945a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot friend class ::google::protobuf::Arena; 4955a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot friend class Map<Key, T>; 4965a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot}; 4975a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 4985a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// google::protobuf::Map is an associative container type used to store protobuf map 4995a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// fields. Each Map instance may or may not use a different hash function, a 5005a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// different iteration order, and so on. E.g., please don't examine 5015a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// implementation details to decide if the following would work: 5025a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// Map<int, int> m0, m1; 5035a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// m0[0] = m1[0] = m0[1] = m1[1] = 0; 5045a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// assert(m0.begin()->first == m1.begin()->first); // Bug! 5055a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// 5065a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// Map's interface is similar to std::unordered_map, except that Map is not 5075a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot// designed to play well with exceptions. 5085a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robottemplate <typename Key, typename T> 5095a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robotclass Map { 5105a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot public: 5115a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef Key key_type; 5125a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef T mapped_type; 5135a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef MapPair<Key, T> value_type; 5145a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 5155a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef value_type* pointer; 5165a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef const value_type* const_pointer; 5175a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef value_type& reference; 5185a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef const value_type& const_reference; 5195a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 5205a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef size_t size_type; 5215a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef hash<Key> hasher; 5225a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 5235a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Map(bool old_style = true) 5245a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : arena_(NULL), 5255a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot default_enum_value_(0), 5265a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot old_style_(old_style) { 5275a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Init(); 5285a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 5295a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot explicit Map(Arena* arena, bool old_style = true) 5305a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : arena_(arena), 5315a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot default_enum_value_(0), 5325a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot old_style_(old_style) { 5335a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Init(); 5345a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 5355a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Map(const Map& other) 5365a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : arena_(NULL), 5375a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot default_enum_value_(other.default_enum_value_), 5385a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot old_style_(other.old_style_) { 5395a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Init(); 5405a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot insert(other.begin(), other.end()); 5415a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 5425a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot template <class InputIt> 5435a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Map(const InputIt& first, const InputIt& last, bool old_style = true) 5445a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : arena_(NULL), 5455a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot default_enum_value_(0), 5465a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot old_style_(old_style) { 5475a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Init(); 5485a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot insert(first, last); 5495a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 5505a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 5515a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot ~Map() { 5525a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot clear(); 5535a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (arena_ == NULL) { 5545a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (old_style_) 5555a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot delete deprecated_elements_; 5565a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot else 5575a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot delete elements_; 5585a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 5595a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 5605a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 5615a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot private: 5625a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void Init() { 5635a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (old_style_) 5645a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot deprecated_elements_ = Arena::Create<DeprecatedInnerMap>( 5655a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot arena_, 0, hasher(), equal_to<Key>(), 5665a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot MapAllocator<std::pair<const Key, MapPair<Key, T>*> >(arena_)); 5675a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot else 5685a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot elements_ = 5695a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Arena::Create<InnerMap>(arena_, 0, hasher(), Allocator(arena_)); 5705a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 5715a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 5725a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // re-implement std::allocator to use arena allocator for memory allocation. 5735a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Used for google::protobuf::Map implementation. Users should not use this class 5745a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // directly. 5755a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot template <typename U> 5765a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot class MapAllocator { 5775a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot public: 5785a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef U value_type; 5795a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef value_type* pointer; 5805a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef const value_type* const_pointer; 5815a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef value_type& reference; 5825a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef const value_type& const_reference; 5835a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef size_t size_type; 5845a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef ptrdiff_t difference_type; 5855a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 5865a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot MapAllocator() : arena_(NULL) {} 5875a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot explicit MapAllocator(Arena* arena) : arena_(arena) {} 5885a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot template <typename X> 5895a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot MapAllocator(const MapAllocator<X>& allocator) 5905a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : arena_(allocator.arena()) {} 5915a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 5925a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot pointer allocate(size_type n, const_pointer hint = 0) { 5935a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // If arena is not given, malloc needs to be called which doesn't 5945a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // construct element object. 5955a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (arena_ == NULL) { 5965a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return reinterpret_cast<pointer>(malloc(n * sizeof(value_type))); 5975a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } else { 5985a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return reinterpret_cast<pointer>( 5995a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Arena::CreateArray<uint8>(arena_, n * sizeof(value_type))); 6005a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 6015a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 6025a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 6035a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void deallocate(pointer p, size_type n) { 6045a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (arena_ == NULL) { 6055a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot free(p); 6065a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 6075a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 6085a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 6095a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#if __cplusplus >= 201103L && !defined(GOOGLE_PROTOBUF_OS_APPLE) && \ 6105a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot !defined(GOOGLE_PROTOBUF_OS_NACL) && \ 6115a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot !defined(GOOGLE_PROTOBUF_OS_ANDROID) && \ 6125a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot !defined(GOOGLE_PROTOBUF_OS_EMSCRIPTEN) 6135a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot template<class NodeType, class... Args> 6145a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void construct(NodeType* p, Args&&... args) { 6155a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Clang 3.6 doesn't compile static casting to void* directly. (Issue 6165a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // #1266) According C++ standard 5.2.9/1: "The static_cast operator shall 6175a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // not cast away constness". So first the maybe const pointer is casted to 6185a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // const void* and after the const void* is const casted. 6195a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot new (const_cast<void*>(static_cast<const void*>(p))) 6205a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot NodeType(std::forward<Args>(args)...); 6215a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 6225a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 6235a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot template<class NodeType> 6245a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void destroy(NodeType* p) { 6255a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot p->~NodeType(); 6265a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 6275a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#else 6285a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void construct(pointer p, const_reference t) { new (p) value_type(t); } 6295a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 6305a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void destroy(pointer p) { p->~value_type(); } 6315a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#endif 6325a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 6335a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot template <typename X> 6345a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot struct rebind { 6355a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef MapAllocator<X> other; 6365a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot }; 6375a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 6385a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot template <typename X> 6395a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bool operator==(const MapAllocator<X>& other) const { 6405a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return arena_ == other.arena_; 6415a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 6425a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 6435a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot template <typename X> 6445a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bool operator!=(const MapAllocator<X>& other) const { 6455a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return arena_ != other.arena_; 6465a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 6475a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 6485a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // To support Visual Studio 2008 6495a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type max_size() const { 6505a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return std::numeric_limits<size_type>::max(); 6515a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 6525a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 6535a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // To support gcc-4.4, which does not properly 6545a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // support templated friend classes 6555a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Arena* arena() const { 6565a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return arena_; 6575a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 6585a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 6595a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot private: 6605a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef void DestructorSkippable_; 6615a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Arena* const arena_; 6625a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot }; 6635a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 6645a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // InnerMap's key type is Key and its value type is value_type*. We use a 6655a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // custom class here and for Node, below, to ensure that k_ is at offset 0, 6665a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // allowing safe conversion from pointer to Node to pointer to Key, and vice 6675a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // versa when appropriate. 6685a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot class KeyValuePair { 6695a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot public: 6705a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot KeyValuePair(const Key& k, value_type* v) : k_(k), v_(v) {} 6715a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 6725a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const Key& key() const { return k_; } 6735a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Key& key() { return k_; } 6745a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot value_type* const value() const { return v_; } 6755a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot value_type*& value() { return v_; } 6765a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 6775a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot private: 6785a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Key k_; 6795a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot value_type* v_; 6805a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot }; 6815a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 6825a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef MapAllocator<KeyValuePair> Allocator; 6835a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 6845a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // InnerMap is a generic hash-based map. It doesn't contain any 6855a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // protocol-buffer-specific logic. It is a chaining hash map with the 6865a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // additional feature that some buckets can be converted to use an ordered 6875a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // container. This ensures O(lg n) bounds on find, insert, and erase, while 6885a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // avoiding the overheads of ordered containers most of the time. 6895a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // 6905a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // The implementation doesn't need the full generality of unordered_map, 6915a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // and it doesn't have it. More bells and whistles can be added as needed. 6925a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Some implementation details: 6935a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // 1. The hash function has type hasher and the equality function 6945a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // equal_to<Key>. We inherit from hasher to save space 6955a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // (empty-base-class optimization). 6965a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // 2. The number of buckets is a power of two. 6975a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // 3. Buckets are converted to trees in pairs: if we convert bucket b then 6985a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // buckets b and b^1 will share a tree. Invariant: buckets b and b^1 have 6995a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // the same non-NULL value iff they are sharing a tree. (An alternative 7005a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // implementation strategy would be to have a tag bit per bucket.) 7015a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // 4. As is typical for hash_map and such, the Keys and Values are always 7025a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // stored in linked list nodes. Pointers to elements are never invalidated 7035a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // until the element is deleted. 7045a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // 5. The trees' payload type is pointer to linked-list node. Tree-converting 7055a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // a bucket doesn't copy Key-Value pairs. 7065a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // 6. Once we've tree-converted a bucket, it is never converted back. However, 7075a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // the items a tree contains may wind up assigned to trees or lists upon a 7085a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // rehash. 7095a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // 7. The code requires no C++ features from C++11 or later. 7105a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // 8. Mutations to a map do not invalidate the map's iterators, pointers to 7115a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // elements, or references to elements. 7125a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // 9. Except for erase(iterator), any non-const method can reorder iterators. 7135a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot class InnerMap : private hasher { 7145a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot public: 7155a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef value_type* Value; 7165a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 7175a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot InnerMap(size_type n, hasher h, Allocator alloc) 7185a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : hasher(h), 7195a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot num_elements_(0), 7205a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot seed_(Seed()), 7215a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot table_(NULL), 7225a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot alloc_(alloc) { 7235a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot n = TableSize(n); 7245a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot table_ = CreateEmptyTable(n); 7255a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot num_buckets_ = index_of_first_non_null_ = n; 7265a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 7275a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 7285a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot ~InnerMap() { 7295a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (table_ != NULL) { 7305a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot clear(); 7315a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Dealloc<void*>(table_, num_buckets_); 7325a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 7335a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 7345a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 7355a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot private: 7365a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot enum { kMinTableSize = 8 }; 7375a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 7385a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Linked-list nodes, as one would expect for a chaining hash table. 7395a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot struct Node { 7405a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot KeyValuePair kv; 7415a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Node* next; 7425a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot }; 7435a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 7445a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // This is safe only if the given pointer is known to point to a Key that is 7455a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // part of a Node. 7465a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot static Node* NodePtrFromKeyPtr(Key* k) { 7475a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return reinterpret_cast<Node*>(k); 7485a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 7495a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 7505a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot static Key* KeyPtrFromNodePtr(Node* node) { return &node->kv.key(); } 7515a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 7525a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Trees. The payload type is pointer to Key, so that we can query the tree 7535a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // with Keys that are not in any particular data structure. When we insert, 7545a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // though, the pointer is always pointing to a Key that is inside a Node. 7555a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot struct KeyCompare { 7565a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bool operator()(const Key* n0, const Key* n1) const { return *n0 < *n1; } 7575a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot }; 7585a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef typename Allocator::template rebind<Key*>::other KeyPtrAllocator; 7595a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef std::set<Key*, KeyCompare, KeyPtrAllocator> Tree; 7605a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 7615a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // iterator and const_iterator are instantiations of iterator_base. 7625a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot template <typename KeyValueType> 7635a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot class iterator_base { 7645a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot public: 7655a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef KeyValueType& reference; 7665a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef KeyValueType* pointer; 7675a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef typename Tree::iterator TreeIterator; 7685a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 7695a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Invariants: 7705a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // node_ is always correct. This is handy because the most common 7715a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // operations are operator* and operator-> and they only use node_. 7725a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // When node_ is set to a non-NULL value, all the other non-const fields 7735a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // are updated to be correct also, but those fields can become stale 7745a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // if the underlying map is modified. When those fields are needed they 7755a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // are rechecked, and updated if necessary. 7765a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator_base() : node_(NULL) {} 7775a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 7785a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot explicit iterator_base(const InnerMap* m) : m_(m) { 7795a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot SearchFrom(m->index_of_first_non_null_); 7805a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 7815a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 7825a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Any iterator_base can convert to any other. This is overkill, and we 7835a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // rely on the enclosing class to use it wisely. The standard "iterator 7845a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // can convert to const_iterator" is OK but the reverse direction is not. 7855a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot template <typename U> 7865a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot explicit iterator_base(const iterator_base<U>& it) 7875a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : node_(it.node_), 7885a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot m_(it.m_), 7895a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bucket_index_(it.bucket_index_), 7905a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot tree_it_(it.tree_it_) {} 7915a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 7925a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator_base(Node* n, const InnerMap* m, size_type index) 7935a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : node_(n), 7945a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot m_(m), 7955a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bucket_index_(index) {} 7965a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 7975a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator_base(TreeIterator tree_it, const InnerMap* m, size_type index) 7985a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : node_(NodePtrFromKeyPtr(*tree_it)), 7995a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot m_(m), 8005a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bucket_index_(index), 8015a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot tree_it_(tree_it) { 8025a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Invariant: iterators that use tree_it_ have an even bucket_index_. 8035a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_DCHECK_EQ(bucket_index_ % 2, 0); 8045a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 8055a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 8065a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Advance through buckets, looking for the first that isn't empty. 8075a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // If nothing non-empty is found then leave node_ == NULL. 8085a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void SearchFrom(size_type start_bucket) { 8095a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_DCHECK(m_->index_of_first_non_null_ == m_->num_buckets_ || 8105a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot m_->table_[m_->index_of_first_non_null_] != NULL); 8115a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot node_ = NULL; 8125a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot for (bucket_index_ = start_bucket; bucket_index_ < m_->num_buckets_; 8135a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bucket_index_++) { 8145a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (m_->TableEntryIsNonEmptyList(bucket_index_)) { 8155a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot node_ = static_cast<Node*>(m_->table_[bucket_index_]); 8165a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot break; 8175a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } else if (m_->TableEntryIsTree(bucket_index_)) { 8185a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Tree* tree = static_cast<Tree*>(m_->table_[bucket_index_]); 8195a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_DCHECK(!tree->empty()); 8205a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot tree_it_ = tree->begin(); 8215a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot node_ = NodePtrFromKeyPtr(*tree_it_); 8225a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot break; 8235a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 8245a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 8255a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 8265a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 8275a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot reference operator*() const { return node_->kv; } 8285a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot pointer operator->() const { return &(operator*()); } 8295a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 8305a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot friend bool operator==(const iterator_base& a, const iterator_base& b) { 8315a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return a.node_ == b.node_; 8325a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 8335a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot friend bool operator!=(const iterator_base& a, const iterator_base& b) { 8345a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return a.node_ != b.node_; 8355a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 8365a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 8375a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator_base& operator++() { 8385a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (node_->next == NULL) { 8395a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const bool is_list = revalidate_if_necessary(); 8405a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (is_list) { 8415a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot SearchFrom(bucket_index_ + 1); 8425a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } else { 8435a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_DCHECK_EQ(bucket_index_ & 1, 0); 8445a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Tree* tree = static_cast<Tree*>(m_->table_[bucket_index_]); 8455a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (++tree_it_ == tree->end()) { 8465a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot SearchFrom(bucket_index_ + 2); 8475a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } else { 8485a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot node_ = NodePtrFromKeyPtr(*tree_it_); 8495a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 8505a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 8515a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } else { 8525a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot node_ = node_->next; 8535a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 8545a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return *this; 8555a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 8565a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 8575a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator_base operator++(int /* unused */) { 8585a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator_base tmp = *this; 8595a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot ++*this; 8605a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return tmp; 8615a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 8625a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 8635a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Assumes node_ and m_ are correct and non-NULL, but other fields may be 8645a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // stale. Fix them as needed. Then return true iff node_ points to a 8655a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Node in a list. 8665a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bool revalidate_if_necessary() { 8675a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_DCHECK(node_ != NULL && m_ != NULL); 8685a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Force bucket_index_ to be in range. 8695a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bucket_index_ &= (m_->num_buckets_ - 1); 8705a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Common case: the bucket we think is relevant points to node_. 8715a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (m_->table_[bucket_index_] == static_cast<void*>(node_)) 8725a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return true; 8735a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Less common: the bucket is a linked list with node_ somewhere in it, 8745a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // but not at the head. 8755a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (m_->TableEntryIsNonEmptyList(bucket_index_)) { 8765a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Node* l = static_cast<Node*>(m_->table_[bucket_index_]); 8775a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot while ((l = l->next) != NULL) { 8785a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (l == node_) { 8795a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return true; 8805a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 8815a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 8825a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 8835a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Well, bucket_index_ still might be correct, but probably 8845a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // not. Revalidate just to be sure. This case is rare enough that we 8855a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // don't worry about potential optimizations, such as having a custom 8865a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // find-like method that compares Node* instead of const Key&. 8875a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator_base i(m_->find(*KeyPtrFromNodePtr(node_))); 8885a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bucket_index_ = i.bucket_index_; 8895a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot tree_it_ = i.tree_it_; 8905a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return m_->TableEntryIsList(bucket_index_); 8915a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 8925a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 8935a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Node* node_; 8945a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const InnerMap* m_; 8955a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type bucket_index_; 8965a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TreeIterator tree_it_; 8975a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot }; 8985a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 8995a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot public: 9005a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef iterator_base<KeyValuePair> iterator; 9015a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef iterator_base<const KeyValuePair> const_iterator; 9025a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 9035a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator begin() { return iterator(this); } 9045a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator end() { return iterator(); } 9055a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const_iterator begin() const { return const_iterator(this); } 9065a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const_iterator end() const { return const_iterator(); } 9075a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 9085a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void clear() { 9095a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot for (size_type b = 0; b < num_buckets_; b++) { 9105a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (TableEntryIsNonEmptyList(b)) { 9115a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Node* node = static_cast<Node*>(table_[b]); 9125a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot table_[b] = NULL; 9135a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot do { 9145a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Node* next = node->next; 9155a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot DestroyNode(node); 9165a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot node = next; 9175a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } while (node != NULL); 9185a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } else if (TableEntryIsTree(b)) { 9195a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Tree* tree = static_cast<Tree*>(table_[b]); 9205a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_DCHECK(table_[b] == table_[b + 1] && (b & 1) == 0); 9215a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot table_[b] = table_[b + 1] = NULL; 9225a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typename Tree::iterator tree_it = tree->begin(); 9235a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot do { 9245a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Node* node = NodePtrFromKeyPtr(*tree_it); 9255a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typename Tree::iterator next = tree_it; 9265a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot ++next; 9275a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot tree->erase(tree_it); 9285a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot DestroyNode(node); 9295a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot tree_it = next; 9305a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } while (tree_it != tree->end()); 9315a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot DestroyTree(tree); 9325a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot b++; 9335a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 9345a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 9355a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot num_elements_ = 0; 9365a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot index_of_first_non_null_ = num_buckets_; 9375a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 9385a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 9395a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const hasher& hash_function() const { return *this; } 9405a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 9415a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot static size_type max_size() { 9425a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return static_cast<size_type>(1) << (sizeof(void**) >= 8 ? 60 : 28); 9435a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 9445a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type size() const { return num_elements_; } 9455a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bool empty() const { return size() == 0; } 9465a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 9475a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator find(const Key& k) { return iterator(FindHelper(k).first); } 9485a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const_iterator find(const Key& k) const { return FindHelper(k).first; } 9495a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 9505a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // In traditional C++ style, this performs "insert if not present." 9515a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot std::pair<iterator, bool> insert(const KeyValuePair& kv) { 9525a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot std::pair<const_iterator, size_type> p = FindHelper(kv.key()); 9535a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Case 1: key was already present. 9545a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (p.first.node_ != NULL) 9555a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return std::make_pair(iterator(p.first), false); 9565a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Case 2: insert. 9575a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (ResizeIfLoadIsOutOfRange(num_elements_ + 1)) { 9585a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot p = FindHelper(kv.key()); 9595a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 9605a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const size_type b = p.second; // bucket number 9615a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Node* node = Alloc<Node>(1); 9625a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot alloc_.construct(&node->kv, kv); 9635a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator result = InsertUnique(b, node); 9645a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot ++num_elements_; 9655a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return std::make_pair(result, true); 9665a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 9675a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 9685a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // The same, but if an insertion is necessary then the value portion of the 9695a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // inserted key-value pair is left uninitialized. 9705a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot std::pair<iterator, bool> insert(const Key& k) { 9715a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot std::pair<const_iterator, size_type> p = FindHelper(k); 9725a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Case 1: key was already present. 9735a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (p.first.node_ != NULL) 9745a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return std::make_pair(iterator(p.first), false); 9755a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Case 2: insert. 9765a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (ResizeIfLoadIsOutOfRange(num_elements_ + 1)) { 9775a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot p = FindHelper(k); 9785a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 9795a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const size_type b = p.second; // bucket number 9805a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Node* node = Alloc<Node>(1); 9815a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef typename Allocator::template rebind<Key>::other KeyAllocator; 9825a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot KeyAllocator(alloc_).construct(&node->kv.key(), k); 9835a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator result = InsertUnique(b, node); 9845a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot ++num_elements_; 9855a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return std::make_pair(result, true); 9865a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 9875a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 9885a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Value& operator[](const Key& k) { 9895a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot KeyValuePair kv(k, Value()); 9905a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return insert(kv).first->value(); 9915a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 9925a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 9935a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void erase(iterator it) { 9945a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_DCHECK_EQ(it.m_, this); 9955a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const bool is_list = it.revalidate_if_necessary(); 9965a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type b = it.bucket_index_; 9975a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Node* const item = it.node_; 9985a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (is_list) { 9995a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_DCHECK(TableEntryIsNonEmptyList(b)); 10005a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Node* head = static_cast<Node*>(table_[b]); 10015a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot head = EraseFromLinkedList(item, head); 10025a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot table_[b] = static_cast<void*>(head); 10035a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } else { 10045a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_DCHECK(TableEntryIsTree(b)); 10055a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Tree* tree = static_cast<Tree*>(table_[b]); 10065a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot tree->erase(it.tree_it_); 10075a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (tree->empty()) { 10085a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Force b to be the minimum of b and b ^ 1. This is important 10095a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // only because we want index_of_first_non_null_ to be correct. 10105a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot b &= ~static_cast<size_type>(1); 10115a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot DestroyTree(tree); 10125a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot table_[b] = table_[b + 1] = NULL; 10135a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 10145a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 10155a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot DestroyNode(item); 10165a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot --num_elements_; 10175a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (GOOGLE_PREDICT_FALSE(b == index_of_first_non_null_)) { 10185a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot while (index_of_first_non_null_ < num_buckets_ && 10195a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot table_[index_of_first_non_null_] == NULL) { 10205a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot ++index_of_first_non_null_; 10215a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 10225a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 10235a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 10245a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 10255a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot private: 10265a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot std::pair<const_iterator, size_type> FindHelper(const Key& k) const { 10275a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type b = BucketNumber(k); 10285a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (TableEntryIsNonEmptyList(b)) { 10295a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Node* node = static_cast<Node*>(table_[b]); 10305a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot do { 10315a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (IsMatch(*KeyPtrFromNodePtr(node), k)) { 10325a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return std::make_pair(const_iterator(node, this, b), b); 10335a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } else { 10345a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot node = node->next; 10355a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 10365a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } while (node != NULL); 10375a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } else if (TableEntryIsTree(b)) { 10385a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_DCHECK_EQ(table_[b], table_[b ^ 1]); 10395a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot b &= ~static_cast<size_t>(1); 10405a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Tree* tree = static_cast<Tree*>(table_[b]); 10415a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Key* key = const_cast<Key*>(&k); 10425a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typename Tree::iterator tree_it = tree->find(key); 10435a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (tree_it != tree->end()) { 10445a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return std::make_pair(const_iterator(tree_it, this, b), b); 10455a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 10465a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 10475a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return std::make_pair(end(), b); 10485a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 10495a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 10505a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Insert the given Node in bucket b. If that would make bucket b too big, 10515a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // and bucket b is not a tree, create a tree for buckets b and b^1 to share. 10525a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Requires count(*KeyPtrFromNodePtr(node)) == 0 and that b is the correct 10535a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // bucket. num_elements_ is not modified. 10545a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator InsertUnique(size_type b, Node* node) { 10555a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_DCHECK(index_of_first_non_null_ == num_buckets_ || 10565a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot table_[index_of_first_non_null_] != NULL); 10575a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // In practice, the code that led to this point may have already 10585a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // determined whether we are inserting into an empty list, a short list, 10595a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // or whatever. But it's probably cheap enough to recompute that here; 10605a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // it's likely that we're inserting into an empty or short list. 10615a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator result; 10625a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_DCHECK(find(*KeyPtrFromNodePtr(node)) == end()); 10635a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (TableEntryIsEmpty(b)) { 10645a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot result = InsertUniqueInList(b, node); 10655a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } else if (TableEntryIsNonEmptyList(b)) { 10665a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (GOOGLE_PREDICT_FALSE(TableEntryIsTooLong(b))) { 10675a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TreeConvert(b); 10685a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot result = InsertUniqueInTree(b, node); 10695a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_DCHECK_EQ(result.bucket_index_, b & ~static_cast<size_type>(1)); 10705a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } else { 10715a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Insert into a pre-existing list. This case cannot modify 10725a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // index_of_first_non_null_, so we skip the code to update it. 10735a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return InsertUniqueInList(b, node); 10745a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 10755a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } else { 10765a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Insert into a pre-existing tree. This case cannot modify 10775a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // index_of_first_non_null_, so we skip the code to update it. 10785a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return InsertUniqueInTree(b, node); 10795a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 10805a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot index_of_first_non_null_ = 10815a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot std::min(index_of_first_non_null_, result.bucket_index_); 10825a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return result; 10835a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 10845a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 10855a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Helper for InsertUnique. Handles the case where bucket b is a 10865a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // not-too-long linked list. 10875a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator InsertUniqueInList(size_type b, Node* node) { 10885a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot node->next = static_cast<Node*>(table_[b]); 10895a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot table_[b] = static_cast<void*>(node); 10905a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return iterator(node, this, b); 10915a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 10925a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 10935a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Helper for InsertUnique. Handles the case where bucket b points to a 10945a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Tree. 10955a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator InsertUniqueInTree(size_type b, Node* node) { 10965a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_DCHECK_EQ(table_[b], table_[b ^ 1]); 10975a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Maintain the invariant that node->next is NULL for all Nodes in Trees. 10985a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot node->next = NULL; 10995a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return iterator(static_cast<Tree*>(table_[b]) 11005a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot ->insert(KeyPtrFromNodePtr(node)) 11015a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot .first, 11025a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot this, b & ~static_cast<size_t>(1)); 11035a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 11045a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 11055a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Returns whether it did resize. Currently this is only used when 11065a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // num_elements_ increases, though it could be used in other situations. 11075a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // It checks for load too low as well as load too high: because any number 11085a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // of erases can occur between inserts, the load could be as low as 0 here. 11095a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Resizing to a lower size is not always helpful, but failing to do so can 11105a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // destroy the expected big-O bounds for some operations. By having the 11115a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // policy that sometimes we resize down as well as up, clients can easily 11125a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // keep O(size()) = O(number of buckets) if they want that. 11135a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bool ResizeIfLoadIsOutOfRange(size_type new_size) { 11145a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const size_type kMaxMapLoadTimes16 = 12; // controls RAM vs CPU tradeoff 11155a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const size_type hi_cutoff = num_buckets_ * kMaxMapLoadTimes16 / 16; 11165a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const size_type lo_cutoff = hi_cutoff / 4; 11175a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // We don't care how many elements are in trees. If a lot are, 11185a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // we may resize even though there are many empty buckets. In 11195a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // practice, this seems fine. 11205a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (GOOGLE_PREDICT_FALSE(new_size >= hi_cutoff)) { 11215a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (num_buckets_ <= max_size() / 2) { 11225a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Resize(num_buckets_ * 2); 11235a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return true; 11245a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 11255a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } else if (GOOGLE_PREDICT_FALSE(new_size <= lo_cutoff && 11265a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot num_buckets_ > kMinTableSize)) { 11275a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type lg2_of_size_reduction_factor = 1; 11285a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // It's possible we want to shrink a lot here... size() could even be 0. 11295a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // So, estimate how much to shrink by making sure we don't shrink so 11305a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // much that we would need to grow the table after a few inserts. 11315a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const size_type hypothetical_size = new_size * 5 / 4 + 1; 11325a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot while ((hypothetical_size << lg2_of_size_reduction_factor) < 11335a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot hi_cutoff) { 11345a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot ++lg2_of_size_reduction_factor; 11355a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 11365a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type new_num_buckets = std::max<size_type>( 11375a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot kMinTableSize, num_buckets_ >> lg2_of_size_reduction_factor); 11385a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (new_num_buckets != num_buckets_) { 11395a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Resize(new_num_buckets); 11405a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return true; 11415a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 11425a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 11435a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return false; 11445a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 11455a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 11465a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Resize to the given number of buckets. 11475a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void Resize(size_t new_num_buckets) { 11485a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_DCHECK_GE(new_num_buckets, kMinTableSize); 11495a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void** const old_table = table_; 11505a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const size_type old_table_size = num_buckets_; 11515a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot num_buckets_ = new_num_buckets; 11525a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot table_ = CreateEmptyTable(num_buckets_); 11535a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const size_type start = index_of_first_non_null_; 11545a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot index_of_first_non_null_ = num_buckets_; 11555a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot for (size_type i = start; i < old_table_size; i++) { 11565a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (TableEntryIsNonEmptyList(old_table, i)) { 11575a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TransferList(old_table, i); 11585a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } else if (TableEntryIsTree(old_table, i)) { 11595a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot TransferTree(old_table, i++); 11605a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 11615a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 11625a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Dealloc<void*>(old_table, old_table_size); 11635a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 11645a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 11655a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void TransferList(void* const* table, size_type index) { 11665a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Node* node = static_cast<Node*>(table[index]); 11675a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot do { 11685a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Node* next = node->next; 11695a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot InsertUnique(BucketNumber(*KeyPtrFromNodePtr(node)), node); 11705a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot node = next; 11715a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } while (node != NULL); 11725a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 11735a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 11745a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void TransferTree(void* const* table, size_type index) { 11755a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Tree* tree = static_cast<Tree*>(table[index]); 11765a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typename Tree::iterator tree_it = tree->begin(); 11775a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot do { 11785a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Node* node = NodePtrFromKeyPtr(*tree_it); 11795a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot InsertUnique(BucketNumber(**tree_it), node); 11805a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } while (++tree_it != tree->end()); 11815a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot DestroyTree(tree); 11825a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 11835a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 11845a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Node* EraseFromLinkedList(Node* item, Node* head) { 11855a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (head == item) { 11865a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return head->next; 11875a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } else { 11885a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot head->next = EraseFromLinkedList(item, head->next); 11895a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return head; 11905a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 11915a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 11925a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 11935a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bool TableEntryIsEmpty(size_type b) const { 11945a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return TableEntryIsEmpty(table_, b); 11955a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 11965a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bool TableEntryIsNonEmptyList(size_type b) const { 11975a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return TableEntryIsNonEmptyList(table_, b); 11985a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 11995a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bool TableEntryIsTree(size_type b) const { 12005a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return TableEntryIsTree(table_, b); 12015a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 12025a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bool TableEntryIsList(size_type b) const { 12035a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return TableEntryIsList(table_, b); 12045a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 12055a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot static bool TableEntryIsEmpty(void* const* table, size_type b) { 12065a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return table[b] == NULL; 12075a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 12085a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot static bool TableEntryIsNonEmptyList(void* const* table, size_type b) { 12095a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return table[b] != NULL && table[b] != table[b ^ 1]; 12105a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 12115a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot static bool TableEntryIsTree(void* const* table, size_type b) { 12125a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return !TableEntryIsEmpty(table, b) && 12135a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot !TableEntryIsNonEmptyList(table, b); 12145a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 12155a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot static bool TableEntryIsList(void* const* table, size_type b) { 12165a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return !TableEntryIsTree(table, b); 12175a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 12185a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 12195a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void TreeConvert(size_type b) { 12205a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_DCHECK(!TableEntryIsTree(b) && !TableEntryIsTree(b ^ 1)); 12215a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typename Allocator::template rebind<Tree>::other tree_allocator(alloc_); 12225a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Tree* tree = tree_allocator.allocate(1); 12235a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // We want to use the three-arg form of construct, if it exists, but we 12245a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // create a temporary and use the two-arg construct that's known to exist. 12255a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // It's clunky, but the compiler should be able to generate more-or-less 12265a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // the same code. 12275a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot tree_allocator.construct(tree, 12285a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Tree(KeyCompare(), KeyPtrAllocator(alloc_))); 12295a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Now the tree is ready to use. 12305a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type count = CopyListToTree(b, tree) + CopyListToTree(b ^ 1, tree); 12315a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_DCHECK_EQ(count, tree->size()); 12325a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot table_[b] = table_[b ^ 1] = static_cast<void*>(tree); 12335a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 12345a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 12355a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Copy a linked list in the given bucket to a tree. 12365a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Returns the number of things it copied. 12375a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type CopyListToTree(size_type b, Tree* tree) { 12385a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type count = 0; 12395a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Node* node = static_cast<Node*>(table_[b]); 12405a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot while (node != NULL) { 12415a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot tree->insert(KeyPtrFromNodePtr(node)); 12425a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot ++count; 12435a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Node* next = node->next; 12445a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot node->next = NULL; 12455a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot node = next; 12465a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 12475a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return count; 12485a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 12495a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 12505a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Return whether table_[b] is a linked list that seems awfully long. 12515a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Requires table_[b] to point to a non-empty linked list. 12525a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bool TableEntryIsTooLong(size_type b) { 12535a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const int kMaxLength = 8; 12545a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type count = 0; 12555a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Node* node = static_cast<Node*>(table_[b]); 12565a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot do { 12575a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot ++count; 12585a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot node = node->next; 12595a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } while (node != NULL); 12605a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Invariant: no linked list ever is more than kMaxLength in length. 12615a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_DCHECK_LE(count, kMaxLength); 12625a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return count >= kMaxLength; 12635a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 12645a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 12655a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type BucketNumber(const Key& k) const { 12665a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // We inherit from hasher, so one-arg operator() provides a hash function. 12675a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type h = (*const_cast<InnerMap*>(this))(k); 12685a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // To help prevent people from making assumptions about the hash function, 12695a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // we use the seed differently depending on NDEBUG. The default hash 12705a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // function, the seeding, etc., are all likely to change in the future. 12715a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#ifndef NDEBUG 12725a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return (h * (seed_ | 1)) & (num_buckets_ - 1); 12735a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#else 12745a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return (h + seed_) & (num_buckets_ - 1); 12755a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#endif 12765a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 12775a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 12785a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bool IsMatch(const Key& k0, const Key& k1) const { 12795a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return std::equal_to<Key>()(k0, k1); 12805a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 12815a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 12825a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Return a power of two no less than max(kMinTableSize, n). 12835a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Assumes either n < kMinTableSize or n is a power of two. 12845a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type TableSize(size_type n) { 12855a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return n < kMinTableSize ? kMinTableSize : n; 12865a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 12875a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 12885a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Use alloc_ to allocate an array of n objects of type U. 12895a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot template <typename U> 12905a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot U* Alloc(size_type n) { 12915a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef typename Allocator::template rebind<U>::other alloc_type; 12925a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return alloc_type(alloc_).allocate(n); 12935a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 12945a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 12955a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Use alloc_ to deallocate an array of n objects of type U. 12965a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot template <typename U> 12975a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void Dealloc(U* t, size_type n) { 12985a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef typename Allocator::template rebind<U>::other alloc_type; 12995a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot alloc_type(alloc_).deallocate(t, n); 13005a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 13015a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 13025a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void DestroyNode(Node* node) { 13035a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot alloc_.destroy(&node->kv); 13045a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Dealloc<Node>(node, 1); 13055a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 13065a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 13075a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void DestroyTree(Tree* tree) { 13085a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typename Allocator::template rebind<Tree>::other tree_allocator(alloc_); 13095a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot tree_allocator.destroy(tree); 13105a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot tree_allocator.deallocate(tree, 1); 13115a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 13125a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 13135a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void** CreateEmptyTable(size_type n) { 13145a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_DCHECK(n >= kMinTableSize); 13155a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_DCHECK_EQ(n & (n - 1), 0); 13165a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void** result = Alloc<void*>(n); 13175a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot memset(result, 0, n * sizeof(result[0])); 13185a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return result; 13195a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 13205a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 13215a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Return a randomish value. 13225a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type Seed() const { 13235a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // random_device can throw, so avoid it unless we are compiling with 13245a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // exceptions enabled. 13255a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#if __cpp_exceptions && LANG_CXX11 13265a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot try { 13275a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot std::random_device rd; 13285a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot std::knuth_b knuth(rd()); 13295a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot std::uniform_int_distribution<size_type> u; 13305a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return u(knuth); 13315a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } catch (...) { } 13325a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#endif 13335a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type s = static_cast<size_type>(reinterpret_cast<uintptr_t>(this)); 13345a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#if defined(__x86_64__) && defined(__GNUC__) 13355a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot uint32 hi, lo; 13365a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot asm("rdtsc" : "=a" (lo), "=d" (hi)); 13375a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot s += ((static_cast<uint64>(hi) << 32) | lo); 13385a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#endif 13395a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return s; 13405a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 13415a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 13425a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type num_elements_; 13435a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type num_buckets_; 13445a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type seed_; 13455a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type index_of_first_non_null_; 13465a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void** table_; // an array with num_buckets_ entries 13475a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Allocator alloc_; 13485a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(InnerMap); 13495a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot }; // end of class InnerMap 13505a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 13515a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef hash_map<Key, value_type*, hash<Key>, equal_to<Key>, 13525a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot MapAllocator<std::pair<const Key, MapPair<Key, T>*> > > 13535a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot DeprecatedInnerMap; 13545a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 13555a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot public: 13565a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Iterators 13575a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot class iterator_base { 13585a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot public: 13595a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // We support "old style" and "new style" iterators for now. This is 13605a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // temporary. Also, for "iterator()" we have an unknown category. 13615a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // TODO(gpike): get rid of this. 13625a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot enum IteratorStyle { kUnknown, kOld, kNew }; 13635a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot explicit iterator_base(IteratorStyle style) : iterator_style_(style) {} 13645a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 13655a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bool OldStyle() const { 13665a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_DCHECK_NE(iterator_style_, kUnknown); 13675a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return iterator_style_ == kOld; 13685a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 13695a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bool UnknownStyle() const { 13705a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return iterator_style_ == kUnknown; 13715a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 13725a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bool SameStyle(const iterator_base& other) const { 13735a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return iterator_style_ == other.iterator_style_; 13745a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 13755a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 13765a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot private: 13775a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot IteratorStyle iterator_style_; 13785a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot }; 13795a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 13805a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot class const_iterator 13815a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : private iterator_base, 13825a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot public std::iterator<std::forward_iterator_tag, value_type, ptrdiff_t, 13835a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const value_type*, const value_type&> { 13845a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef typename InnerMap::const_iterator InnerIt; 13855a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef typename DeprecatedInnerMap::const_iterator DeprecatedInnerIt; 13865a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 13875a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot public: 13885a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const_iterator() : iterator_base(iterator_base::kUnknown) {} 13895a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot explicit const_iterator(const DeprecatedInnerIt& dit) 13905a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : iterator_base(iterator_base::kOld), dit_(dit) {} 13915a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot explicit const_iterator(const InnerIt& it) 13925a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : iterator_base(iterator_base::kNew), it_(it) {} 13935a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 13945a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const_iterator(const const_iterator& other) 13955a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : iterator_base(other), it_(other.it_), dit_(other.dit_) {} 13965a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 13975a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const_reference operator*() const { 13985a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return this->OldStyle() ? *dit_->second : *it_->value(); 13995a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 14005a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const_pointer operator->() const { return &(operator*()); } 14015a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 14025a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const_iterator& operator++() { 14035a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (this->OldStyle()) 14045a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot ++dit_; 14055a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot else 14065a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot ++it_; 14075a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return *this; 14085a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 14095a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const_iterator operator++(int) { 14105a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return this->OldStyle() ? const_iterator(dit_++) : const_iterator(it_++); 14115a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 14125a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 14135a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot friend bool operator==(const const_iterator& a, const const_iterator& b) { 14145a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (!a.SameStyle(b)) return false; 14155a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (a.UnknownStyle()) return true; 14165a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return a.OldStyle() ? (a.dit_ == b.dit_) : (a.it_ == b.it_); 14175a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 14185a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot friend bool operator!=(const const_iterator& a, const const_iterator& b) { 14195a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return !(a == b); 14205a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 14215a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 14225a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot private: 14235a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot InnerIt it_; 14245a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot DeprecatedInnerIt dit_; 14255a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot }; 14265a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 14275a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot class iterator : private iterator_base, 14285a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot public std::iterator<std::forward_iterator_tag, value_type> { 14295a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef typename InnerMap::iterator InnerIt; 14305a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef typename DeprecatedInnerMap::iterator DeprecatedInnerIt; 14315a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 14325a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot public: 14335a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator() : iterator_base(iterator_base::kUnknown) {} 14345a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot explicit iterator(const DeprecatedInnerIt& dit) 14355a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : iterator_base(iterator_base::kOld), dit_(dit) {} 14365a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot explicit iterator(const InnerIt& it) 14375a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : iterator_base(iterator_base::kNew), it_(it) {} 14385a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 14395a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot reference operator*() const { 14405a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return this->OldStyle() ? *dit_->second : *it_->value(); 14415a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 14425a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot pointer operator->() const { return &(operator*()); } 14435a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 14445a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator& operator++() { 14455a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (this->OldStyle()) 14465a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot ++dit_; 14475a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot else 14485a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot ++it_; 14495a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return *this; 14505a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 14515a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator operator++(int) { 14525a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return this->OldStyle() ? iterator(dit_++) : iterator(it_++); 14535a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 14545a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 14555a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Allow implicit conversion to const_iterator. 14565a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot operator const_iterator() const { 14575a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return this->OldStyle() ? 14585a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const_iterator(typename DeprecatedInnerMap::const_iterator(dit_)) : 14595a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const_iterator(typename InnerMap::const_iterator(it_)); 14605a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 14615a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 14625a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot friend bool operator==(const iterator& a, const iterator& b) { 14635a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (!a.SameStyle(b)) return false; 14645a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (a.UnknownStyle()) return true; 14655a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return a.OldStyle() ? a.dit_ == b.dit_ : a.it_ == b.it_; 14665a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 14675a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot friend bool operator!=(const iterator& a, const iterator& b) { 14685a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return !(a == b); 14695a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 14705a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 14715a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot private: 14725a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot friend class Map; 14735a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 14745a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot InnerIt it_; 14755a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot DeprecatedInnerIt dit_; 14765a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot }; 14775a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 14785a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator begin() { 14795a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return old_style_ ? iterator(deprecated_elements_->begin()) 14805a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : iterator(elements_->begin()); 14815a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 14825a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator end() { 14835a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return old_style_ ? iterator(deprecated_elements_->end()) 14845a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : iterator(elements_->end()); 14855a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 14865a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const_iterator begin() const { 14875a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return old_style_ ? const_iterator(deprecated_elements_->begin()) 14885a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : const_iterator(iterator(elements_->begin())); 14895a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 14905a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const_iterator end() const { 14915a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return old_style_ ? const_iterator(deprecated_elements_->end()) 14925a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : const_iterator(iterator(elements_->end())); 14935a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 14945a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const_iterator cbegin() const { return begin(); } 14955a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const_iterator cend() const { return end(); } 14965a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 14975a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Capacity 14985a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type size() const { 14995a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return old_style_ ? deprecated_elements_->size() : elements_->size(); 15005a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 15015a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bool empty() const { return size() == 0; } 15025a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 15035a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Element access 15045a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot T& operator[](const key_type& key) { 15055a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot value_type** value = 15065a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot old_style_ ? &(*deprecated_elements_)[key] : &(*elements_)[key]; 15075a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (*value == NULL) { 15085a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot *value = CreateValueTypeInternal(key); 15095a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot internal::MapValueInitializer<google::protobuf::is_proto_enum<T>::value, 15105a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot T>::Initialize((*value)->second, 15115a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot default_enum_value_); 15125a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 15135a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return (*value)->second; 15145a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 15155a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const T& at(const key_type& key) const { 15165a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const_iterator it = find(key); 15175a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_CHECK(it != end()); 15185a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return it->second; 15195a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 15205a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot T& at(const key_type& key) { 15215a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator it = find(key); 15225a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_CHECK(it != end()); 15235a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return it->second; 15245a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 15255a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 15265a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Lookup 15275a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type count(const key_type& key) const { 15285a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (find(key) != end()) assert(key == find(key)->first); 15295a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return find(key) == end() ? 0 : 1; 15305a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 15315a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const_iterator find(const key_type& key) const { 15325a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return old_style_ ? const_iterator(deprecated_elements_->find(key)) 15335a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : const_iterator(iterator(elements_->find(key))); 15345a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 15355a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator find(const key_type& key) { 15365a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return old_style_ ? iterator(deprecated_elements_->find(key)) 15375a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : iterator(elements_->find(key)); 15385a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 15395a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot std::pair<const_iterator, const_iterator> equal_range( 15405a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const key_type& key) const { 15415a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const_iterator it = find(key); 15425a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (it == end()) { 15435a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return std::pair<const_iterator, const_iterator>(it, it); 15445a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } else { 15455a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const_iterator begin = it++; 15465a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return std::pair<const_iterator, const_iterator>(begin, it); 15475a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 15485a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 15495a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot std::pair<iterator, iterator> equal_range(const key_type& key) { 15505a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator it = find(key); 15515a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (it == end()) { 15525a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return std::pair<iterator, iterator>(it, it); 15535a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } else { 15545a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator begin = it++; 15555a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return std::pair<iterator, iterator>(begin, it); 15565a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 15575a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 15585a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 15595a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // insert 15605a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot std::pair<iterator, bool> insert(const value_type& value) { 15615a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (old_style_) { 15625a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator it = find(value.first); 15635a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (it != end()) { 15645a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return std::pair<iterator, bool>(it, false); 15655a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } else { 15665a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return std::pair<iterator, bool>( 15675a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator(deprecated_elements_->insert(std::pair<Key, value_type*>( 15685a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot value.first, CreateValueTypeInternal(value))).first), true); 15695a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 15705a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } else { 15715a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot std::pair<typename InnerMap::iterator, bool> p = 15725a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot elements_->insert(value.first); 15735a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (p.second) { 15745a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot p.first->value() = CreateValueTypeInternal(value); 15755a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 15765a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return std::pair<iterator, bool>(iterator(p.first), p.second); 15775a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 15785a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 15795a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot template <class InputIt> 15805a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void insert(InputIt first, InputIt last) { 15815a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot for (InputIt it = first; it != last; ++it) { 15825a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator exist_it = find(it->first); 15835a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (exist_it == end()) { 15845a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot operator[](it->first) = it->second; 15855a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 15865a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 15875a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 15885a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 15895a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Erase and clear 15905a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_type erase(const key_type& key) { 15915a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator it = find(key); 15925a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (it == end()) { 15935a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return 0; 15945a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } else { 15955a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot erase(it); 15965a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return 1; 15975a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 15985a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 15995a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator erase(iterator pos) { 16005a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (arena_ == NULL) delete pos.operator->(); 16015a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot iterator i = pos++; 16025a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (old_style_) 16035a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot deprecated_elements_->erase(i.dit_); 16045a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot else 16055a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot elements_->erase(i.it_); 16065a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return pos; 16075a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 16085a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void erase(iterator first, iterator last) { 16095a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot while (first != last) { 16105a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot first = erase(first); 16115a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 16125a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 16135a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void clear() { erase(begin(), end()); } 16145a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 16155a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Assign 16165a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Map& operator=(const Map& other) { 16175a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (this != &other) { 16185a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot clear(); 16195a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot insert(other.begin(), other.end()); 16205a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 16215a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return *this; 16225a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 16235a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 16245a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Access to hasher. Currently this returns a copy, but it may 16255a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // be modified to return a const reference in the future. 16265a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot hasher hash_function() const { 16275a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return old_style_ ? deprecated_elements_->hash_function() 16285a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot : elements_->hash_function(); 16295a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 16305a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 16315a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot private: 16325a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // Set default enum value only for proto2 map field whose value is enum type. 16335a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot void SetDefaultEnumValue(int default_enum_value) { 16345a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot default_enum_value_ = default_enum_value; 16355a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 16365a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 16375a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot value_type* CreateValueTypeInternal(const Key& key) { 16385a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (arena_ == NULL) { 16395a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return new value_type(key); 16405a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } else { 16415a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot value_type* value = reinterpret_cast<value_type*>( 16425a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Arena::CreateArray<uint8>(arena_, sizeof(value_type))); 16435a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Arena::CreateInArenaStorage(const_cast<Key*>(&value->first), arena_); 16445a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Arena::CreateInArenaStorage(&value->second, arena_); 16455a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const_cast<Key&>(value->first) = key; 16465a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return value; 16475a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 16485a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 16495a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 16505a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot value_type* CreateValueTypeInternal(const value_type& value) { 16515a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot if (arena_ == NULL) { 16525a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return new value_type(value); 16535a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } else { 16545a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot value_type* p = reinterpret_cast<value_type*>( 16555a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Arena::CreateArray<uint8>(arena_, sizeof(value_type))); 16565a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Arena::CreateInArenaStorage(const_cast<Key*>(&p->first), arena_); 16575a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Arena::CreateInArenaStorage(&p->second, arena_); 16585a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const_cast<Key&>(p->first) = value.first; 16595a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot p->second = value.second; 16605a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return p; 16615a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 16625a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 16635a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 16645a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot Arena* arena_; 16655a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot int default_enum_value_; 16665a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // The following is a tagged union because we support two map styles 16675a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // for now. 16685a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot // TODO(gpike): get rid of the old style. 16695a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const bool old_style_; 16705a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot union { 16715a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot InnerMap* elements_; 16725a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot DeprecatedInnerMap* deprecated_elements_; 16735a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot }; 16745a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 16755a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot friend class ::google::protobuf::Arena; 16765a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef void InternalArenaConstructable_; 16775a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot typedef void DestructorSkippable_; 16785a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot template <typename K, typename V, 16795a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot internal::WireFormatLite::FieldType key_wire_type, 16805a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot internal::WireFormatLite::FieldType value_wire_type, 16815a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot int default_enum_value> 16825a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot friend class internal::MapFieldLite; 16835a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot}; 16845a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 16855a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot} // namespace protobuf 16865a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot} // namespace google 16875a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 16885a6e989368cab2b72ab8db50330d02e459b47d4android-build-team RobotGOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_START 16895a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robottemplate<> 16905a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robotstruct hash<google::protobuf::MapKey> { 16915a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot size_t 16925a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot operator()(const google::protobuf::MapKey& map_key) const { 16935a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot switch (map_key.type()) { 16945a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case google::protobuf::FieldDescriptor::CPPTYPE_DOUBLE: 16955a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case google::protobuf::FieldDescriptor::CPPTYPE_FLOAT: 16965a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case google::protobuf::FieldDescriptor::CPPTYPE_ENUM: 16975a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case google::protobuf::FieldDescriptor::CPPTYPE_MESSAGE: 16985a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_LOG(FATAL) << "Unsupported"; 16995a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot break; 17005a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case google::protobuf::FieldDescriptor::CPPTYPE_STRING: 17015a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return hash<string>()(map_key.GetStringValue()); 17025a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case google::protobuf::FieldDescriptor::CPPTYPE_INT64: 17035a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return hash< ::google::protobuf::int64>()(map_key.GetInt64Value()); 17045a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case google::protobuf::FieldDescriptor::CPPTYPE_INT32: 17055a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return hash< ::google::protobuf::int32>()(map_key.GetInt32Value()); 17065a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case google::protobuf::FieldDescriptor::CPPTYPE_UINT64: 17075a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return hash< ::google::protobuf::uint64>()(map_key.GetUInt64Value()); 17085a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case google::protobuf::FieldDescriptor::CPPTYPE_UINT32: 17095a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return hash< ::google::protobuf::uint32>()(map_key.GetUInt32Value()); 17105a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot case google::protobuf::FieldDescriptor::CPPTYPE_BOOL: 17115a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return hash<bool>()(map_key.GetBoolValue()); 17125a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 17135a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot GOOGLE_LOG(FATAL) << "Can't get here."; 17145a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return 0; 17155a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 17165a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot bool 17175a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot operator()(const google::protobuf::MapKey& map_key1, 17185a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot const google::protobuf::MapKey& map_key2) const { 17195a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot return map_key1 < map_key2; 17205a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot } 17215a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot}; 17225a6e989368cab2b72ab8db50330d02e459b47d4android-build-team RobotGOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_END 17235a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot 17245a6e989368cab2b72ab8db50330d02e459b47d4android-build-team Robot#endif // GOOGLE_PROTOBUF_MAP_H__ 1725