1b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// Protocol Buffers - Google's data interchange format 2b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// Copyright 2008 Google Inc. All rights reserved. 3b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// https://developers.google.com/protocol-buffers/ 4b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// 5b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// Redistribution and use in source and binary forms, with or without 6b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// modification, are permitted provided that the following conditions are 7b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// met: 8b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// 9b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// * Redistributions of source code must retain the above copyright 10b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// notice, this list of conditions and the following disclaimer. 11b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// * Redistributions in binary form must reproduce the above 12b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// copyright notice, this list of conditions and the following disclaimer 13b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// in the documentation and/or other materials provided with the 14b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// distribution. 15b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// * Neither the name of Google Inc. nor the names of its 16b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// contributors may be used to endorse or promote products derived from 17b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// this software without specific prior written permission. 18b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// 19b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 31b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#ifndef GOOGLE_PROTOBUF_MAP_H__ 32b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#define GOOGLE_PROTOBUF_MAP_H__ 33b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 34b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#include <google/protobuf/stubs/hash.h> 35b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#include <iterator> 36b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#include <limits> // To support Visual Studio 2008 37b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#include <set> 38b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#include <utility> 39b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 40b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#include <google/protobuf/stubs/common.h> 41b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#include <google/protobuf/arena.h> 42b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#include <google/protobuf/generated_enum_util.h> 43b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#include <google/protobuf/map_type_handler.h> 44b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#include <google/protobuf/message.h> 45b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#include <google/protobuf/descriptor.h> 46b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#if __cpp_exceptions && LANG_CXX11 47b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#include <random> 48b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#endif 49b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 50b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammernamespace google { 51b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammernamespace protobuf { 52b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 53b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// The Map and MapIterator types are provided by this header file. 54b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// Please avoid using other types defined here, unless they are public 55b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// types within Map or MapIterator, such as Map::value_type. 56b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammertemplate <typename Key, typename T> 57b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammerclass Map; 58b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 59b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammerclass MapIterator; 60b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 61b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammertemplate <typename Enum> struct is_proto_enum; 62b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 63b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammernamespace internal { 64b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammertemplate <typename Key, typename T, 65b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer WireFormatLite::FieldType key_wire_type, 66b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer WireFormatLite::FieldType value_wire_type, 67b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer int default_enum_value> 68b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammerclass MapFieldLite; 69b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 70b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammertemplate <typename Key, typename T, 71b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer WireFormatLite::FieldType key_wire_type, 72b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer WireFormatLite::FieldType value_wire_type, 73b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer int default_enum_value> 74b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammerclass MapField; 75b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 76b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammertemplate <typename Key, typename T> 77b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammerclass TypeDefinedMapFieldBase; 78b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 79b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammerclass DynamicMapField; 80b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 81b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammerclass GeneratedMessageReflection; 82b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer} // namespace internal 83b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 84b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#define TYPE_CHECK(EXPECTEDTYPE, METHOD) \ 85b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (type() != EXPECTEDTYPE) { \ 86b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_LOG(FATAL) \ 87b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer << "Protocol Buffer map usage error:\n" \ 88b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer << METHOD << " type does not match\n" \ 89b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer << " Expected : " \ 90b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer << FieldDescriptor::CppTypeName(EXPECTEDTYPE) << "\n" \ 91b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer << " Actual : " \ 92b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer << FieldDescriptor::CppTypeName(type()); \ 93b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 94b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 95b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// MapKey is an union type for representing any possible 96b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// map key. 97b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammerclass LIBPROTOBUF_EXPORT MapKey { 98b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer public: 99b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer MapKey() : type_(0) { 100b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 101b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer MapKey(const MapKey& other) : type_(0) { 102b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer CopyFrom(other); 103b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 104b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 105b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer ~MapKey() { 106b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (type_ == FieldDescriptor::CPPTYPE_STRING) { 107b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer delete val_.string_value_; 108b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 109b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 110b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 111b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer FieldDescriptor::CppType type() const { 112b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (type_ == 0) { 113b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_LOG(FATAL) 114b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer << "Protocol Buffer map usage error:\n" 115b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer << "MapKey::type MapKey is not initialized. " 116b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer << "Call set methods to initialize MapKey."; 117b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 118b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return (FieldDescriptor::CppType)type_; 119b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 120b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 121b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void SetInt64Value(int64 value) { 122b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer SetType(FieldDescriptor::CPPTYPE_INT64); 123b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer val_.int64_value_ = value; 124b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 125b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void SetUInt64Value(uint64 value) { 126b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer SetType(FieldDescriptor::CPPTYPE_UINT64); 127b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer val_.uint64_value_ = value; 128b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 129b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void SetInt32Value(int32 value) { 130b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer SetType(FieldDescriptor::CPPTYPE_INT32); 131b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer val_.int32_value_ = value; 132b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 133b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void SetUInt32Value(uint32 value) { 134b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer SetType(FieldDescriptor::CPPTYPE_UINT32); 135b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer val_.uint32_value_ = value; 136b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 137b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void SetBoolValue(bool value) { 138b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer SetType(FieldDescriptor::CPPTYPE_BOOL); 139b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer val_.bool_value_ = value; 140b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 141b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void SetStringValue(const string& val) { 142b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer SetType(FieldDescriptor::CPPTYPE_STRING); 143b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer *val_.string_value_ = val; 144b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 145b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 146b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer int64 GetInt64Value() const { 147b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_INT64, 148b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapKey::GetInt64Value"); 149b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return val_.int64_value_; 150b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 151b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer uint64 GetUInt64Value() const { 152b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_UINT64, 153b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapKey::GetUInt64Value"); 154b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return val_.uint64_value_; 155b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 156b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer int32 GetInt32Value() const { 157b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_INT32, 158b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapKey::GetInt32Value"); 159b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return val_.int32_value_; 160b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 161b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer uint32 GetUInt32Value() const { 162b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_UINT32, 163b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapKey::GetUInt32Value"); 164b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return val_.uint32_value_; 165b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 166b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bool GetBoolValue() const { 167b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_BOOL, 168b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapKey::GetBoolValue"); 169b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return val_.bool_value_; 170b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 171b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const string& GetStringValue() const { 172b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_STRING, 173b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapKey::GetStringValue"); 174b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return *val_.string_value_; 175b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 176b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 177b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bool operator<(const MapKey& other) const { 178b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (type_ != other.type_) { 179b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // We could define a total order that handles this case, but 180b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // there currently no need. So, for now, fail. 181b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_LOG(FATAL) << "Unsupported: type mismatch"; 182b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 183b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer switch (type()) { 184b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_DOUBLE: 185b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_FLOAT: 186b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_ENUM: 187b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_MESSAGE: 188b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_LOG(FATAL) << "Unsupported"; 189b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return false; 190b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_STRING: 191b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return *val_.string_value_ < *other.val_.string_value_; 192b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_INT64: 193b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return val_.int64_value_ < other.val_.int64_value_; 194b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_INT32: 195b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return val_.int32_value_ < other.val_.int32_value_; 196b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_UINT64: 197b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return val_.uint64_value_ < other.val_.uint64_value_; 198b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_UINT32: 199b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return val_.uint32_value_ < other.val_.uint32_value_; 200b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_BOOL: 201b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return val_.bool_value_ < other.val_.bool_value_; 202b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 203b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return false; 204b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 205b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 206b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bool operator==(const MapKey& other) const { 207b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (type_ != other.type_) { 208b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // To be consistent with operator<, we don't allow this either. 209b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_LOG(FATAL) << "Unsupported: type mismatch"; 210b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 211b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer switch (type()) { 212b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_DOUBLE: 213b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_FLOAT: 214b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_ENUM: 215b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_MESSAGE: 216b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_LOG(FATAL) << "Unsupported"; 217b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer break; 218b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_STRING: 219b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return *val_.string_value_ == *other.val_.string_value_; 220b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_INT64: 221b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return val_.int64_value_ == other.val_.int64_value_; 222b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_INT32: 223b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return val_.int32_value_ == other.val_.int32_value_; 224b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_UINT64: 225b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return val_.uint64_value_ == other.val_.uint64_value_; 226b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_UINT32: 227b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return val_.uint32_value_ == other.val_.uint32_value_; 228b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_BOOL: 229b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return val_.bool_value_ == other.val_.bool_value_; 230b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 231b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_LOG(FATAL) << "Can't get here."; 232b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return false; 233b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 234b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 235b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void CopyFrom(const MapKey& other) { 236b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer SetType(other.type()); 237b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer switch (type_) { 238b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_DOUBLE: 239b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_FLOAT: 240b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_ENUM: 241b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_MESSAGE: 242b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_LOG(FATAL) << "Unsupported"; 243b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer break; 244b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_STRING: 245b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer *val_.string_value_ = *other.val_.string_value_; 246b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer break; 247b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_INT64: 248b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer val_.int64_value_ = other.val_.int64_value_; 249b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer break; 250b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_INT32: 251b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer val_.int32_value_ = other.val_.int32_value_; 252b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer break; 253b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_UINT64: 254b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer val_.uint64_value_ = other.val_.uint64_value_; 255b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer break; 256b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_UINT32: 257b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer val_.uint32_value_ = other.val_.uint32_value_; 258b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer break; 259b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case FieldDescriptor::CPPTYPE_BOOL: 260b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer val_.bool_value_ = other.val_.bool_value_; 261b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer break; 262b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 263b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 264b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 265b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer private: 266b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer template <typename K, typename V> 267b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer friend class internal::TypeDefinedMapFieldBase; 268b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer friend class MapIterator; 269b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer friend class internal::DynamicMapField; 270b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 271b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer union KeyValue { 272b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer KeyValue() {} 273b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer string* string_value_; 274b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer int64 int64_value_; 275b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer int32 int32_value_; 276b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer uint64 uint64_value_; 277b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer uint32 uint32_value_; 278b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bool bool_value_; 279b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } val_; 280b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 281b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void SetType(FieldDescriptor::CppType type) { 282b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (type_ == type) return; 283b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (type_ == FieldDescriptor::CPPTYPE_STRING) { 284b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer delete val_.string_value_; 285b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 286b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer type_ = type; 287b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (type_ == FieldDescriptor::CPPTYPE_STRING) { 288b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer val_.string_value_ = new string; 289b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 290b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 291b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 292b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // type_ is 0 or a valid FieldDescriptor::CppType. 293b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer int type_; 294b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer}; 295b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 296b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// MapValueRef points to a map value. 297b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammerclass LIBPROTOBUF_EXPORT MapValueRef { 298b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer public: 299b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer MapValueRef() : data_(NULL), type_(0) {} 300b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 301b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void SetInt64Value(int64 value) { 302b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_INT64, 303b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapValueRef::SetInt64Value"); 304b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer *reinterpret_cast<int64*>(data_) = value; 305b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 306b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void SetUInt64Value(uint64 value) { 307b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_UINT64, 308b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapValueRef::SetUInt64Value"); 309b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer *reinterpret_cast<uint64*>(data_) = value; 310b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 311b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void SetInt32Value(int32 value) { 312b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_INT32, 313b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapValueRef::SetInt32Value"); 314b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer *reinterpret_cast<int32*>(data_) = value; 315b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 316b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void SetUInt32Value(uint32 value) { 317b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_UINT32, 318b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapValueRef::SetUInt32Value"); 319b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer *reinterpret_cast<uint32*>(data_) = value; 320b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 321b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void SetBoolValue(bool value) { 322b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_BOOL, 323b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapValueRef::SetBoolValue"); 324b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer *reinterpret_cast<bool*>(data_) = value; 325b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 326b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // TODO(jieluo) - Checks that enum is member. 327b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void SetEnumValue(int value) { 328b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_ENUM, 329b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapValueRef::SetEnumValue"); 330b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer *reinterpret_cast<int*>(data_) = value; 331b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 332b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void SetStringValue(const string& value) { 333b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_STRING, 334b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapValueRef::SetStringValue"); 335b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer *reinterpret_cast<string*>(data_) = value; 336b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 337b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void SetFloatValue(float value) { 338b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_FLOAT, 339b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapValueRef::SetFloatValue"); 340b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer *reinterpret_cast<float*>(data_) = value; 341b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 342b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void SetDoubleValue(double value) { 343b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_DOUBLE, 344b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapValueRef::SetDoubleValue"); 345b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer *reinterpret_cast<double*>(data_) = value; 346b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 347b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 348b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer int64 GetInt64Value() const { 349b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_INT64, 350b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapValueRef::GetInt64Value"); 351b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return *reinterpret_cast<int64*>(data_); 352b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 353b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer uint64 GetUInt64Value() const { 354b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_UINT64, 355b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapValueRef::GetUInt64Value"); 356b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return *reinterpret_cast<uint64*>(data_); 357b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 358b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer int32 GetInt32Value() const { 359b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_INT32, 360b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapValueRef::GetInt32Value"); 361b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return *reinterpret_cast<int32*>(data_); 362b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 363b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer uint32 GetUInt32Value() const { 364b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_UINT32, 365b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapValueRef::GetUInt32Value"); 366b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return *reinterpret_cast<uint32*>(data_); 367b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 368b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bool GetBoolValue() const { 369b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_BOOL, 370b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapValueRef::GetBoolValue"); 371b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return *reinterpret_cast<bool*>(data_); 372b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 373b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer int GetEnumValue() const { 374b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_ENUM, 375b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapValueRef::GetEnumValue"); 376b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return *reinterpret_cast<int*>(data_); 377b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 378b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const string& GetStringValue() const { 379b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_STRING, 380b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapValueRef::GetStringValue"); 381b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return *reinterpret_cast<string*>(data_); 382b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 383b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer float GetFloatValue() const { 384b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_FLOAT, 385b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapValueRef::GetFloatValue"); 386b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return *reinterpret_cast<float*>(data_); 387b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 388b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer double GetDoubleValue() const { 389b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_DOUBLE, 390b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapValueRef::GetDoubleValue"); 391b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return *reinterpret_cast<double*>(data_); 392b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 393b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 394b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const Message& GetMessageValue() const { 395b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_MESSAGE, 396b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapValueRef::GetMessageValue"); 397b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return *reinterpret_cast<Message*>(data_); 398b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 399b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 400b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Message* MutableMessageValue() { 401b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TYPE_CHECK(FieldDescriptor::CPPTYPE_MESSAGE, 402b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer "MapValueRef::MutableMessageValue"); 403b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return reinterpret_cast<Message*>(data_); 404b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 405b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 406b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer private: 407b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer template <typename K, typename V, 408b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer internal::WireFormatLite::FieldType key_wire_type, 409b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer internal::WireFormatLite::FieldType value_wire_type, 410b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer int default_enum_value> 411b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer friend class internal::MapField; 412b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer template <typename K, typename V> 413b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer friend class internal::TypeDefinedMapFieldBase; 414b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer friend class MapIterator; 415b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer friend class internal::GeneratedMessageReflection; 416b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer friend class internal::DynamicMapField; 417b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 418b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void SetType(FieldDescriptor::CppType type) { 419b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer type_ = type; 420b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 421b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 422b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer FieldDescriptor::CppType type() const { 423b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (type_ == 0 || data_ == NULL) { 424b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_LOG(FATAL) 425b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer << "Protocol Buffer map usage error:\n" 426b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer << "MapValueRef::type MapValueRef is not initialized."; 427b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 428b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return (FieldDescriptor::CppType)type_; 429b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 430b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void SetValue(const void* val) { 431b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer data_ = const_cast<void*>(val); 432b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 433b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void CopyFrom(const MapValueRef& other) { 434b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer type_ = other.type_; 435b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer data_ = other.data_; 436b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 437b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Only used in DynamicMapField 438b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void DeleteData() { 439b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer switch (type_) { 440b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#define HANDLE_TYPE(CPPTYPE, TYPE) \ 441b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case google::protobuf::FieldDescriptor::CPPTYPE_##CPPTYPE: { \ 442b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer delete reinterpret_cast<TYPE*>(data_); \ 443b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer break; \ 444b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 445b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer HANDLE_TYPE(INT32, int32); 446b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer HANDLE_TYPE(INT64, int64); 447b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer HANDLE_TYPE(UINT32, uint32); 448b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer HANDLE_TYPE(UINT64, uint64); 449b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer HANDLE_TYPE(DOUBLE, double); 450b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer HANDLE_TYPE(FLOAT, float); 451b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer HANDLE_TYPE(BOOL, bool); 452b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer HANDLE_TYPE(STRING, string); 453b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer HANDLE_TYPE(ENUM, int32); 454b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer HANDLE_TYPE(MESSAGE, Message); 455b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#undef HANDLE_TYPE 456b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 457b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 458b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // data_ point to a map value. MapValueRef does not 459b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // own this value. 460b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void* data_; 461b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // type_ is 0 or a valid FieldDescriptor::CppType. 462b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer int type_; 463b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer}; 464b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 465b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#undef TYPE_CHECK 466b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 467b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// This is the class for google::protobuf::Map's internal value_type. Instead of using 468b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// std::pair as value_type, we use this class which provides us more control of 469b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// its process of construction and destruction. 470b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammertemplate <typename Key, typename T> 471b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammerclass MapPair { 472b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer public: 473b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef const Key first_type; 474b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef T second_type; 475b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 476b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer MapPair(const Key& other_first, const T& other_second) 477b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : first(other_first), second(other_second) {} 478b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer explicit MapPair(const Key& other_first) : first(other_first), second() {} 479b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer MapPair(const MapPair& other) 480b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : first(other.first), second(other.second) {} 481b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 482b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer ~MapPair() {} 483b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 484b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Implicitly convertible to std::pair of compatible types. 485b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer template <typename T1, typename T2> 486b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer operator std::pair<T1, T2>() const { 487b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return std::pair<T1, T2>(first, second); 488b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 489b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 490b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const Key first; 491b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer T second; 492b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 493b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer private: 494b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer friend class ::google::protobuf::Arena; 495b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer friend class Map<Key, T>; 496b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer}; 497b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 498b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// google::protobuf::Map is an associative container type used to store protobuf map 499b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// fields. Each Map instance may or may not use a different hash function, a 500b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// different iteration order, and so on. E.g., please don't examine 501b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// implementation details to decide if the following would work: 502b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// Map<int, int> m0, m1; 503b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// m0[0] = m1[0] = m0[1] = m1[1] = 0; 504b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// assert(m0.begin()->first == m1.begin()->first); // Bug! 505b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// 506b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// Map's interface is similar to std::unordered_map, except that Map is not 507b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer// designed to play well with exceptions. 508b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammertemplate <typename Key, typename T> 509b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammerclass Map { 510b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer public: 511b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef Key key_type; 512b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef T mapped_type; 513b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef MapPair<Key, T> value_type; 514b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 515b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef value_type* pointer; 516b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef const value_type* const_pointer; 517b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef value_type& reference; 518b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef const value_type& const_reference; 519b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 520b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef size_t size_type; 521b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef hash<Key> hasher; 522b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 523b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Map(bool old_style = true) 524b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : arena_(NULL), 525b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer default_enum_value_(0), 526b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer old_style_(old_style) { 527b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Init(); 528b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 529b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer explicit Map(Arena* arena, bool old_style = true) 530b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : arena_(arena), 531b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer default_enum_value_(0), 532b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer old_style_(old_style) { 533b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Init(); 534b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 535b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Map(const Map& other) 536b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : arena_(NULL), 537b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer default_enum_value_(other.default_enum_value_), 538b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer old_style_(other.old_style_) { 539b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Init(); 540b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer insert(other.begin(), other.end()); 541b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 542b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer template <class InputIt> 543b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Map(const InputIt& first, const InputIt& last, bool old_style = true) 544b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : arena_(NULL), 545b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer default_enum_value_(0), 546b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer old_style_(old_style) { 547b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Init(); 548b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer insert(first, last); 549b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 550b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 551b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer ~Map() { 552b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer clear(); 553b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (arena_ == NULL) { 554b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (old_style_) 555b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer delete deprecated_elements_; 556b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer else 557b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer delete elements_; 558b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 559b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 560b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 561b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer private: 562b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void Init() { 563b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (old_style_) 564b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer deprecated_elements_ = Arena::Create<DeprecatedInnerMap>( 565b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer arena_, 0, hasher(), equal_to<Key>(), 566b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer MapAllocator<std::pair<const Key, MapPair<Key, T>*> >(arena_)); 567b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer else 568b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer elements_ = 569b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Arena::Create<InnerMap>(arena_, 0, hasher(), Allocator(arena_)); 570b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 571b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 572b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // re-implement std::allocator to use arena allocator for memory allocation. 573b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Used for google::protobuf::Map implementation. Users should not use this class 574b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // directly. 575b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer template <typename U> 576b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer class MapAllocator { 577b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer public: 578b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef U value_type; 579b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef value_type* pointer; 580b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef const value_type* const_pointer; 581b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef value_type& reference; 582b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef const value_type& const_reference; 583b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef size_t size_type; 584b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef ptrdiff_t difference_type; 585b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 586b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer MapAllocator() : arena_(NULL) {} 587b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer explicit MapAllocator(Arena* arena) : arena_(arena) {} 588b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer template <typename X> 589b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer MapAllocator(const MapAllocator<X>& allocator) 590b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : arena_(allocator.arena_) {} 591b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 592b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer pointer allocate(size_type n, const_pointer hint = 0) { 593b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // If arena is not given, malloc needs to be called which doesn't 594b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // construct element object. 595b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (arena_ == NULL) { 596b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return reinterpret_cast<pointer>(malloc(n * sizeof(value_type))); 597b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } else { 598b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return reinterpret_cast<pointer>( 599b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Arena::CreateArray<uint8>(arena_, n * sizeof(value_type))); 600b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 601b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 602b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 603b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void deallocate(pointer p, size_type n) { 604b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (arena_ == NULL) { 605b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer free(p); 606b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 607b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 608b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 609b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#if __cplusplus >= 201103L && !defined(GOOGLE_PROTOBUF_OS_APPLE) && \ 610b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer !defined(GOOGLE_PROTOBUF_OS_NACL) && \ 611b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer !defined(GOOGLE_PROTOBUF_OS_ANDROID) && \ 612b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer !defined(GOOGLE_PROTOBUF_OS_EMSCRIPTEN) 613b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer template<class NodeType, class... Args> 614b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void construct(NodeType* p, Args&&... args) { 615b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Clang 3.6 doesn't compile static casting to void* directly. (Issue 616b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // #1266) According C++ standard 5.2.9/1: "The static_cast operator shall 617b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // not cast away constness". So first the maybe const pointer is casted to 618b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // const void* and after the const void* is const casted. 619b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer new (const_cast<void*>(static_cast<const void*>(p))) 620b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer NodeType(std::forward<Args>(args)...); 621b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 622b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 623b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer template<class NodeType> 624b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void destroy(NodeType* p) { 625b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer p->~NodeType(); 626b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 627b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#else 628b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void construct(pointer p, const_reference t) { new (p) value_type(t); } 629b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 630b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void destroy(pointer p) { p->~value_type(); } 631b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#endif 632b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 633b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer template <typename X> 634b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer struct rebind { 635b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef MapAllocator<X> other; 636b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer }; 637b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 638b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer template <typename X> 639b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bool operator==(const MapAllocator<X>& other) const { 640b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return arena_ == other.arena_; 641b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 642b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 643b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer template <typename X> 644b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bool operator!=(const MapAllocator<X>& other) const { 645b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return arena_ != other.arena_; 646b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 647b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 648b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // To support Visual Studio 2008 649b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type max_size() const { 650b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return std::numeric_limits<size_type>::max(); 651b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 652b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 653b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer private: 654b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef void DestructorSkippable_; 655b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Arena* const arena_; 656b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 657b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer template <typename X> 658b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer friend class MapAllocator; 659b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer }; 660b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 661b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // InnerMap's key type is Key and its value type is value_type*. We use a 662b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // custom class here and for Node, below, to ensure that k_ is at offset 0, 663b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // allowing safe conversion from pointer to Node to pointer to Key, and vice 664b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // versa when appropriate. 665b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer class KeyValuePair { 666b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer public: 667b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer KeyValuePair(const Key& k, value_type* v) : k_(k), v_(v) {} 668b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 669b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const Key& key() const { return k_; } 670b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Key& key() { return k_; } 671b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer value_type* const value() const { return v_; } 672b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer value_type*& value() { return v_; } 673b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 674b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer private: 675b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Key k_; 676b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer value_type* v_; 677b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer }; 678b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 679b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef MapAllocator<KeyValuePair> Allocator; 680b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 681b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // InnerMap is a generic hash-based map. It doesn't contain any 682b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // protocol-buffer-specific logic. It is a chaining hash map with the 683b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // additional feature that some buckets can be converted to use an ordered 684b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // container. This ensures O(lg n) bounds on find, insert, and erase, while 685b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // avoiding the overheads of ordered containers most of the time. 686b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // 687b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // The implementation doesn't need the full generality of unordered_map, 688b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // and it doesn't have it. More bells and whistles can be added as needed. 689b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Some implementation details: 690b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // 1. The hash function has type hasher and the equality function 691b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // equal_to<Key>. We inherit from hasher to save space 692b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // (empty-base-class optimization). 693b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // 2. The number of buckets is a power of two. 694b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // 3. Buckets are converted to trees in pairs: if we convert bucket b then 695b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // buckets b and b^1 will share a tree. Invariant: buckets b and b^1 have 696b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // the same non-NULL value iff they are sharing a tree. (An alternative 697b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // implementation strategy would be to have a tag bit per bucket.) 698b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // 4. As is typical for hash_map and such, the Keys and Values are always 699b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // stored in linked list nodes. Pointers to elements are never invalidated 700b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // until the element is deleted. 701b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // 5. The trees' payload type is pointer to linked-list node. Tree-converting 702b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // a bucket doesn't copy Key-Value pairs. 703b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // 6. Once we've tree-converted a bucket, it is never converted back. However, 704b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // the items a tree contains may wind up assigned to trees or lists upon a 705b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // rehash. 706b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // 7. The code requires no C++ features from C++11 or later. 707b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // 8. Mutations to a map do not invalidate the map's iterators, pointers to 708b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // elements, or references to elements. 709b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // 9. Except for erase(iterator), any non-const method can reorder iterators. 710b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer class InnerMap : private hasher { 711b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer public: 712b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef value_type* Value; 713b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 714b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer InnerMap(size_type n, hasher h, Allocator alloc) 715b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : hasher(h), 716b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer num_elements_(0), 717b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer seed_(Seed()), 718b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer table_(NULL), 719b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer alloc_(alloc) { 720b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer n = TableSize(n); 721b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer table_ = CreateEmptyTable(n); 722b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer num_buckets_ = index_of_first_non_null_ = n; 723b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 724b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 725b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer ~InnerMap() { 726b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (table_ != NULL) { 727b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer clear(); 728b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Dealloc<void*>(table_, num_buckets_); 729b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 730b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 731b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 732b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer private: 733b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer enum { kMinTableSize = 8 }; 734b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 735b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Linked-list nodes, as one would expect for a chaining hash table. 736b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer struct Node { 737b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer KeyValuePair kv; 738b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Node* next; 739b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer }; 740b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 741b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // This is safe only if the given pointer is known to point to a Key that is 742b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // part of a Node. 743b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer static Node* NodePtrFromKeyPtr(Key* k) { 744b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return reinterpret_cast<Node*>(k); 745b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 746b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 747b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer static Key* KeyPtrFromNodePtr(Node* node) { return &node->kv.key(); } 748b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 749b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Trees. The payload type is pointer to Key, so that we can query the tree 750b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // with Keys that are not in any particular data structure. When we insert, 751b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // though, the pointer is always pointing to a Key that is inside a Node. 752b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer struct KeyCompare { 753b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bool operator()(const Key* n0, const Key* n1) const { return *n0 < *n1; } 754b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer }; 755b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef typename Allocator::template rebind<Key*>::other KeyPtrAllocator; 756b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef std::set<Key*, KeyCompare, KeyPtrAllocator> Tree; 757b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 758b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // iterator and const_iterator are instantiations of iterator_base. 759b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer template <typename KeyValueType> 760b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer class iterator_base { 761b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer public: 762b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef KeyValueType& reference; 763b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef KeyValueType* pointer; 764b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef typename Tree::iterator TreeIterator; 765b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 766b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Invariants: 767b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // node_ is always correct. This is handy because the most common 768b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // operations are operator* and operator-> and they only use node_. 769b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // When node_ is set to a non-NULL value, all the other non-const fields 770b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // are updated to be correct also, but those fields can become stale 771b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // if the underlying map is modified. When those fields are needed they 772b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // are rechecked, and updated if necessary. 773b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator_base() : node_(NULL) {} 774b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 775b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer explicit iterator_base(const InnerMap* m) : m_(m) { 776b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer SearchFrom(m->index_of_first_non_null_); 777b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 778b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 779b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Any iterator_base can convert to any other. This is overkill, and we 780b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // rely on the enclosing class to use it wisely. The standard "iterator 781b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // can convert to const_iterator" is OK but the reverse direction is not. 782b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer template <typename U> 783b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer explicit iterator_base(const iterator_base<U>& it) 784b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : node_(it.node_), 785b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer m_(it.m_), 786b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bucket_index_(it.bucket_index_), 787b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer tree_it_(it.tree_it_) {} 788b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 789b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator_base(Node* n, const InnerMap* m, size_type index) 790b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : node_(n), 791b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer m_(m), 792b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bucket_index_(index) {} 793b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 794b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator_base(TreeIterator tree_it, const InnerMap* m, size_type index) 795b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : node_(NodePtrFromKeyPtr(*tree_it)), 796b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer m_(m), 797b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bucket_index_(index), 798b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer tree_it_(tree_it) { 799b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Invariant: iterators that use tree_it_ have an even bucket_index_. 800b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_DCHECK_EQ(bucket_index_ % 2, 0); 801b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 802b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 803b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Advance through buckets, looking for the first that isn't empty. 804b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // If nothing non-empty is found then leave node_ == NULL. 805b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void SearchFrom(size_type start_bucket) { 806b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_DCHECK(m_->index_of_first_non_null_ == m_->num_buckets_ || 807b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer m_->table_[m_->index_of_first_non_null_] != NULL); 808b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer node_ = NULL; 809b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer for (bucket_index_ = start_bucket; bucket_index_ < m_->num_buckets_; 810b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bucket_index_++) { 811b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (m_->TableEntryIsNonEmptyList(bucket_index_)) { 812b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer node_ = static_cast<Node*>(m_->table_[bucket_index_]); 813b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer break; 814b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } else if (m_->TableEntryIsTree(bucket_index_)) { 815b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Tree* tree = static_cast<Tree*>(m_->table_[bucket_index_]); 816b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_DCHECK(!tree->empty()); 817b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer tree_it_ = tree->begin(); 818b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer node_ = NodePtrFromKeyPtr(*tree_it_); 819b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer break; 820b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 821b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 822b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 823b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 824b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer reference operator*() const { return node_->kv; } 825b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer pointer operator->() const { return &(operator*()); } 826b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 827b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer friend bool operator==(const iterator_base& a, const iterator_base& b) { 828b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return a.node_ == b.node_; 829b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 830b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer friend bool operator!=(const iterator_base& a, const iterator_base& b) { 831b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return a.node_ != b.node_; 832b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 833b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 834b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator_base& operator++() { 835b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (node_->next == NULL) { 836b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const bool is_list = revalidate_if_necessary(); 837b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (is_list) { 838b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer SearchFrom(bucket_index_ + 1); 839b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } else { 840b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_DCHECK_EQ(bucket_index_ & 1, 0); 841b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Tree* tree = static_cast<Tree*>(m_->table_[bucket_index_]); 842b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (++tree_it_ == tree->end()) { 843b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer SearchFrom(bucket_index_ + 2); 844b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } else { 845b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer node_ = NodePtrFromKeyPtr(*tree_it_); 846b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 847b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 848b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } else { 849b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer node_ = node_->next; 850b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 851b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return *this; 852b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 853b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 854b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator_base operator++(int /* unused */) { 855b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator_base tmp = *this; 856b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer ++*this; 857b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return tmp; 858b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 859b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 860b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Assumes node_ and m_ are correct and non-NULL, but other fields may be 861b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // stale. Fix them as needed. Then return true iff node_ points to a 862b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Node in a list. 863b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bool revalidate_if_necessary() { 864b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_DCHECK(node_ != NULL && m_ != NULL); 865b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Force bucket_index_ to be in range. 866b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bucket_index_ &= (m_->num_buckets_ - 1); 867b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Common case: the bucket we think is relevant points to node_. 868b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (m_->table_[bucket_index_] == static_cast<void*>(node_)) 869b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return true; 870b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Less common: the bucket is a linked list with node_ somewhere in it, 871b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // but not at the head. 872b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (m_->TableEntryIsNonEmptyList(bucket_index_)) { 873b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Node* l = static_cast<Node*>(m_->table_[bucket_index_]); 874b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer while ((l = l->next) != NULL) { 875b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (l == node_) { 876b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return true; 877b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 878b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 879b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 880b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Well, bucket_index_ still might be correct, but probably 881b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // not. Revalidate just to be sure. This case is rare enough that we 882b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // don't worry about potential optimizations, such as having a custom 883b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // find-like method that compares Node* instead of const Key&. 884b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator_base i(m_->find(*KeyPtrFromNodePtr(node_))); 885b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bucket_index_ = i.bucket_index_; 886b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer tree_it_ = i.tree_it_; 887b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return m_->TableEntryIsList(bucket_index_); 888b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 889b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 890b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Node* node_; 891b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const InnerMap* m_; 892b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type bucket_index_; 893b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TreeIterator tree_it_; 894b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer }; 895b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 896b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer public: 897b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef iterator_base<KeyValuePair> iterator; 898b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef iterator_base<const KeyValuePair> const_iterator; 899b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 900b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator begin() { return iterator(this); } 901b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator end() { return iterator(); } 902b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const_iterator begin() const { return const_iterator(this); } 903b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const_iterator end() const { return const_iterator(); } 904b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 905b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void clear() { 906b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer for (size_type b = 0; b < num_buckets_; b++) { 907b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (TableEntryIsNonEmptyList(b)) { 908b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Node* node = static_cast<Node*>(table_[b]); 909b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer table_[b] = NULL; 910b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer do { 911b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Node* next = node->next; 912b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer DestroyNode(node); 913b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer node = next; 914b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } while (node != NULL); 915b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } else if (TableEntryIsTree(b)) { 916b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Tree* tree = static_cast<Tree*>(table_[b]); 917b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_DCHECK(table_[b] == table_[b + 1] && (b & 1) == 0); 918b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer table_[b] = table_[b + 1] = NULL; 919b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typename Tree::iterator tree_it = tree->begin(); 920b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer do { 921b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Node* node = NodePtrFromKeyPtr(*tree_it); 922b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typename Tree::iterator next = tree_it; 923b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer ++next; 924b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer tree->erase(tree_it); 925b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer DestroyNode(node); 926b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer tree_it = next; 927b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } while (tree_it != tree->end()); 928b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer DestroyTree(tree); 929b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer b++; 930b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 931b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 932b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer num_elements_ = 0; 933b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer index_of_first_non_null_ = num_buckets_; 934b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 935b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 936b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const hasher& hash_function() const { return *this; } 937b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 938b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer static size_type max_size() { 939b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return static_cast<size_type>(1) << (sizeof(void**) >= 8 ? 60 : 28); 940b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 941b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type size() const { return num_elements_; } 942b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bool empty() const { return size() == 0; } 943b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 944b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator find(const Key& k) { return iterator(FindHelper(k).first); } 945b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const_iterator find(const Key& k) const { return FindHelper(k).first; } 946b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 947b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // In traditional C++ style, this performs "insert if not present." 948b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer std::pair<iterator, bool> insert(const KeyValuePair& kv) { 949b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer std::pair<const_iterator, size_type> p = FindHelper(kv.key()); 950b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Case 1: key was already present. 951b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (p.first.node_ != NULL) 952b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return std::make_pair(iterator(p.first), false); 953b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Case 2: insert. 954b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (ResizeIfLoadIsOutOfRange(num_elements_ + 1)) { 955b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer p = FindHelper(kv.key()); 956b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 957b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const size_type b = p.second; // bucket number 958b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Node* node = Alloc<Node>(1); 959b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer alloc_.construct(&node->kv, kv); 960b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator result = InsertUnique(b, node); 961b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer ++num_elements_; 962b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return std::make_pair(result, true); 963b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 964b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 965b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // The same, but if an insertion is necessary then the value portion of the 966b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // inserted key-value pair is left uninitialized. 967b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer std::pair<iterator, bool> insert(const Key& k) { 968b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer std::pair<const_iterator, size_type> p = FindHelper(k); 969b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Case 1: key was already present. 970b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (p.first.node_ != NULL) 971b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return std::make_pair(iterator(p.first), false); 972b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Case 2: insert. 973b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (ResizeIfLoadIsOutOfRange(num_elements_ + 1)) { 974b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer p = FindHelper(k); 975b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 976b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const size_type b = p.second; // bucket number 977b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Node* node = Alloc<Node>(1); 978b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef typename Allocator::template rebind<Key>::other KeyAllocator; 979b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer KeyAllocator(alloc_).construct(&node->kv.key(), k); 980b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator result = InsertUnique(b, node); 981b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer ++num_elements_; 982b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return std::make_pair(result, true); 983b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 984b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 985b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Value& operator[](const Key& k) { 986b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer KeyValuePair kv(k, Value()); 987b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return insert(kv).first->value(); 988b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 989b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 990b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void erase(iterator it) { 991b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_DCHECK_EQ(it.m_, this); 992b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const bool is_list = it.revalidate_if_necessary(); 993b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type b = it.bucket_index_; 994b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Node* const item = it.node_; 995b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (is_list) { 996b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_DCHECK(TableEntryIsNonEmptyList(b)); 997b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Node* head = static_cast<Node*>(table_[b]); 998b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer head = EraseFromLinkedList(item, head); 999b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer table_[b] = static_cast<void*>(head); 1000b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } else { 1001b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_DCHECK(TableEntryIsTree(b)); 1002b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Tree* tree = static_cast<Tree*>(table_[b]); 1003b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer tree->erase(it.tree_it_); 1004b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (tree->empty()) { 1005b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Force b to be the minimum of b and b ^ 1. This is important 1006b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // only because we want index_of_first_non_null_ to be correct. 1007b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer b &= ~static_cast<size_type>(1); 1008b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer DestroyTree(tree); 1009b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer table_[b] = table_[b + 1] = NULL; 1010b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1011b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1012b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer DestroyNode(item); 1013b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer --num_elements_; 1014b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (GOOGLE_PREDICT_FALSE(b == index_of_first_non_null_)) { 1015b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer while (index_of_first_non_null_ < num_buckets_ && 1016b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer table_[index_of_first_non_null_] == NULL) { 1017b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer ++index_of_first_non_null_; 1018b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1019b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1020b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1021b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1022b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer private: 1023b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer std::pair<const_iterator, size_type> FindHelper(const Key& k) const { 1024b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type b = BucketNumber(k); 1025b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (TableEntryIsNonEmptyList(b)) { 1026b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Node* node = static_cast<Node*>(table_[b]); 1027b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer do { 1028b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (IsMatch(*KeyPtrFromNodePtr(node), k)) { 1029b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return std::make_pair(const_iterator(node, this, b), b); 1030b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } else { 1031b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer node = node->next; 1032b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1033b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } while (node != NULL); 1034b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } else if (TableEntryIsTree(b)) { 1035b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_DCHECK_EQ(table_[b], table_[b ^ 1]); 1036b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer b &= ~static_cast<size_t>(1); 1037b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Tree* tree = static_cast<Tree*>(table_[b]); 1038b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Key* key = const_cast<Key*>(&k); 1039b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typename Tree::iterator tree_it = tree->find(key); 1040b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (tree_it != tree->end()) { 1041b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return std::make_pair(const_iterator(tree_it, this, b), b); 1042b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1043b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1044b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return std::make_pair(end(), b); 1045b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1046b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1047b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Insert the given Node in bucket b. If that would make bucket b too big, 1048b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // and bucket b is not a tree, create a tree for buckets b and b^1 to share. 1049b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Requires count(*KeyPtrFromNodePtr(node)) == 0 and that b is the correct 1050b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // bucket. num_elements_ is not modified. 1051b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator InsertUnique(size_type b, Node* node) { 1052b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_DCHECK(index_of_first_non_null_ == num_buckets_ || 1053b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer table_[index_of_first_non_null_] != NULL); 1054b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // In practice, the code that led to this point may have already 1055b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // determined whether we are inserting into an empty list, a short list, 1056b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // or whatever. But it's probably cheap enough to recompute that here; 1057b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // it's likely that we're inserting into an empty or short list. 1058b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator result; 1059b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_DCHECK(find(*KeyPtrFromNodePtr(node)) == end()); 1060b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (TableEntryIsEmpty(b)) { 1061b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer result = InsertUniqueInList(b, node); 1062b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } else if (TableEntryIsNonEmptyList(b)) { 1063b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (GOOGLE_PREDICT_FALSE(TableEntryIsTooLong(b))) { 1064b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TreeConvert(b); 1065b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer result = InsertUniqueInTree(b, node); 1066b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_DCHECK_EQ(result.bucket_index_, b & ~static_cast<size_type>(1)); 1067b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } else { 1068b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Insert into a pre-existing list. This case cannot modify 1069b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // index_of_first_non_null_, so we skip the code to update it. 1070b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return InsertUniqueInList(b, node); 1071b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1072b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } else { 1073b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Insert into a pre-existing tree. This case cannot modify 1074b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // index_of_first_non_null_, so we skip the code to update it. 1075b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return InsertUniqueInTree(b, node); 1076b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1077b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer index_of_first_non_null_ = 1078b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer std::min(index_of_first_non_null_, result.bucket_index_); 1079b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return result; 1080b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1081b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1082b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Helper for InsertUnique. Handles the case where bucket b is a 1083b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // not-too-long linked list. 1084b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator InsertUniqueInList(size_type b, Node* node) { 1085b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer node->next = static_cast<Node*>(table_[b]); 1086b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer table_[b] = static_cast<void*>(node); 1087b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return iterator(node, this, b); 1088b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1089b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1090b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Helper for InsertUnique. Handles the case where bucket b points to a 1091b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Tree. 1092b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator InsertUniqueInTree(size_type b, Node* node) { 1093b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_DCHECK_EQ(table_[b], table_[b ^ 1]); 1094b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Maintain the invariant that node->next is NULL for all Nodes in Trees. 1095b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer node->next = NULL; 1096b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return iterator(static_cast<Tree*>(table_[b]) 1097b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer ->insert(KeyPtrFromNodePtr(node)) 1098b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer .first, 1099b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer this, b & ~static_cast<size_t>(1)); 1100b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1101b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1102b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Returns whether it did resize. Currently this is only used when 1103b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // num_elements_ increases, though it could be used in other situations. 1104b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // It checks for load too low as well as load too high: because any number 1105b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // of erases can occur between inserts, the load could be as low as 0 here. 1106b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Resizing to a lower size is not always helpful, but failing to do so can 1107b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // destroy the expected big-O bounds for some operations. By having the 1108b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // policy that sometimes we resize down as well as up, clients can easily 1109b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // keep O(size()) = O(number of buckets) if they want that. 1110b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bool ResizeIfLoadIsOutOfRange(size_type new_size) { 1111b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const size_type kMaxMapLoadTimes16 = 12; // controls RAM vs CPU tradeoff 1112b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const size_type hi_cutoff = num_buckets_ * kMaxMapLoadTimes16 / 16; 1113b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const size_type lo_cutoff = hi_cutoff / 4; 1114b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // We don't care how many elements are in trees. If a lot are, 1115b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // we may resize even though there are many empty buckets. In 1116b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // practice, this seems fine. 1117b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (GOOGLE_PREDICT_FALSE(new_size >= hi_cutoff)) { 1118b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (num_buckets_ <= max_size() / 2) { 1119b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Resize(num_buckets_ * 2); 1120b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return true; 1121b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1122b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } else if (GOOGLE_PREDICT_FALSE(new_size <= lo_cutoff && 1123b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer num_buckets_ > kMinTableSize)) { 1124b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type lg2_of_size_reduction_factor = 1; 1125b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // It's possible we want to shrink a lot here... size() could even be 0. 1126b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // So, estimate how much to shrink by making sure we don't shrink so 1127b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // much that we would need to grow the table after a few inserts. 1128b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const size_type hypothetical_size = new_size * 5 / 4 + 1; 1129b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer while ((hypothetical_size << lg2_of_size_reduction_factor) < 1130b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer hi_cutoff) { 1131b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer ++lg2_of_size_reduction_factor; 1132b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1133b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type new_num_buckets = std::max<size_type>( 1134b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer kMinTableSize, num_buckets_ >> lg2_of_size_reduction_factor); 1135b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (new_num_buckets != num_buckets_) { 1136b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Resize(new_num_buckets); 1137b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return true; 1138b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1139b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1140b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return false; 1141b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1142b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1143b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Resize to the given number of buckets. 1144b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void Resize(size_t new_num_buckets) { 1145b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_DCHECK_GE(new_num_buckets, kMinTableSize); 1146b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void** const old_table = table_; 1147b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const size_type old_table_size = num_buckets_; 1148b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer num_buckets_ = new_num_buckets; 1149b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer table_ = CreateEmptyTable(num_buckets_); 1150b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const size_type start = index_of_first_non_null_; 1151b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer index_of_first_non_null_ = num_buckets_; 1152b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer for (size_type i = start; i < old_table_size; i++) { 1153b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (TableEntryIsNonEmptyList(old_table, i)) { 1154b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TransferList(old_table, i); 1155b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } else if (TableEntryIsTree(old_table, i)) { 1156b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer TransferTree(old_table, i++); 1157b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1158b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1159b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Dealloc<void*>(old_table, old_table_size); 1160b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1161b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1162b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void TransferList(void* const* table, size_type index) { 1163b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Node* node = static_cast<Node*>(table[index]); 1164b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer do { 1165b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Node* next = node->next; 1166b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer InsertUnique(BucketNumber(*KeyPtrFromNodePtr(node)), node); 1167b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer node = next; 1168b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } while (node != NULL); 1169b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1170b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1171b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void TransferTree(void* const* table, size_type index) { 1172b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Tree* tree = static_cast<Tree*>(table[index]); 1173b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typename Tree::iterator tree_it = tree->begin(); 1174b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer do { 1175b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Node* node = NodePtrFromKeyPtr(*tree_it); 1176b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer InsertUnique(BucketNumber(**tree_it), node); 1177b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } while (++tree_it != tree->end()); 1178b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer DestroyTree(tree); 1179b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1180b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1181b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Node* EraseFromLinkedList(Node* item, Node* head) { 1182b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (head == item) { 1183b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return head->next; 1184b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } else { 1185b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer head->next = EraseFromLinkedList(item, head->next); 1186b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return head; 1187b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1188b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1189b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1190b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bool TableEntryIsEmpty(size_type b) const { 1191b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return TableEntryIsEmpty(table_, b); 1192b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1193b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bool TableEntryIsNonEmptyList(size_type b) const { 1194b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return TableEntryIsNonEmptyList(table_, b); 1195b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1196b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bool TableEntryIsTree(size_type b) const { 1197b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return TableEntryIsTree(table_, b); 1198b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1199b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bool TableEntryIsList(size_type b) const { 1200b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return TableEntryIsList(table_, b); 1201b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1202b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer static bool TableEntryIsEmpty(void* const* table, size_type b) { 1203b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return table[b] == NULL; 1204b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1205b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer static bool TableEntryIsNonEmptyList(void* const* table, size_type b) { 1206b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return table[b] != NULL && table[b] != table[b ^ 1]; 1207b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1208b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer static bool TableEntryIsTree(void* const* table, size_type b) { 1209b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return !TableEntryIsEmpty(table, b) && 1210b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer !TableEntryIsNonEmptyList(table, b); 1211b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1212b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer static bool TableEntryIsList(void* const* table, size_type b) { 1213b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return !TableEntryIsTree(table, b); 1214b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1215b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1216b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void TreeConvert(size_type b) { 1217b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_DCHECK(!TableEntryIsTree(b) && !TableEntryIsTree(b ^ 1)); 1218b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typename Allocator::template rebind<Tree>::other tree_allocator(alloc_); 1219b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Tree* tree = tree_allocator.allocate(1); 1220b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // We want to use the three-arg form of construct, if it exists, but we 1221b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // create a temporary and use the two-arg construct that's known to exist. 1222b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // It's clunky, but the compiler should be able to generate more-or-less 1223b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // the same code. 1224b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer tree_allocator.construct(tree, 1225b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Tree(KeyCompare(), KeyPtrAllocator(alloc_))); 1226b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Now the tree is ready to use. 1227b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type count = CopyListToTree(b, tree) + CopyListToTree(b ^ 1, tree); 1228b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_DCHECK_EQ(count, tree->size()); 1229b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer table_[b] = table_[b ^ 1] = static_cast<void*>(tree); 1230b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1231b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1232b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Copy a linked list in the given bucket to a tree. 1233b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Returns the number of things it copied. 1234b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type CopyListToTree(size_type b, Tree* tree) { 1235b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type count = 0; 1236b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Node* node = static_cast<Node*>(table_[b]); 1237b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer while (node != NULL) { 1238b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer tree->insert(KeyPtrFromNodePtr(node)); 1239b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer ++count; 1240b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Node* next = node->next; 1241b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer node->next = NULL; 1242b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer node = next; 1243b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1244b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return count; 1245b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1246b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1247b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Return whether table_[b] is a linked list that seems awfully long. 1248b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Requires table_[b] to point to a non-empty linked list. 1249b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bool TableEntryIsTooLong(size_type b) { 1250b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const int kMaxLength = 8; 1251b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type count = 0; 1252b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Node* node = static_cast<Node*>(table_[b]); 1253b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer do { 1254b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer ++count; 1255b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer node = node->next; 1256b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } while (node != NULL); 1257b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Invariant: no linked list ever is more than kMaxLength in length. 1258b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_DCHECK_LE(count, kMaxLength); 1259b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return count >= kMaxLength; 1260b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1261b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1262b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type BucketNumber(const Key& k) const { 1263b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // We inherit from hasher, so one-arg operator() provides a hash function. 1264b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type h = (*const_cast<InnerMap*>(this))(k); 1265b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // To help prevent people from making assumptions about the hash function, 1266b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // we use the seed differently depending on NDEBUG. The default hash 1267b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // function, the seeding, etc., are all likely to change in the future. 1268b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#ifndef NDEBUG 1269b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return (h * (seed_ | 1)) & (num_buckets_ - 1); 1270b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#else 1271b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return (h + seed_) & (num_buckets_ - 1); 1272b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#endif 1273b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1274b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1275b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bool IsMatch(const Key& k0, const Key& k1) const { 1276b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return std::equal_to<Key>()(k0, k1); 1277b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1278b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1279b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Return a power of two no less than max(kMinTableSize, n). 1280b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Assumes either n < kMinTableSize or n is a power of two. 1281b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type TableSize(size_type n) { 1282b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return n < kMinTableSize ? kMinTableSize : n; 1283b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1284b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1285b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Use alloc_ to allocate an array of n objects of type U. 1286b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer template <typename U> 1287b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer U* Alloc(size_type n) { 1288b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef typename Allocator::template rebind<U>::other alloc_type; 1289b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return alloc_type(alloc_).allocate(n); 1290b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1291b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1292b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Use alloc_ to deallocate an array of n objects of type U. 1293b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer template <typename U> 1294b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void Dealloc(U* t, size_type n) { 1295b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef typename Allocator::template rebind<U>::other alloc_type; 1296b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer alloc_type(alloc_).deallocate(t, n); 1297b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1298b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1299b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void DestroyNode(Node* node) { 1300b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer alloc_.destroy(&node->kv); 1301b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Dealloc<Node>(node, 1); 1302b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1303b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1304b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void DestroyTree(Tree* tree) { 1305b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typename Allocator::template rebind<Tree>::other tree_allocator(alloc_); 1306b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer tree_allocator.destroy(tree); 1307b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer tree_allocator.deallocate(tree, 1); 1308b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1309b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1310b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void** CreateEmptyTable(size_type n) { 1311b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_DCHECK(n >= kMinTableSize); 1312b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_DCHECK_EQ(n & (n - 1), 0); 1313b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void** result = Alloc<void*>(n); 1314b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer memset(result, 0, n * sizeof(result[0])); 1315b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return result; 1316b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1317b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1318b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Return a randomish value. 1319b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type Seed() const { 1320b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // random_device can throw, so avoid it unless we are compiling with 1321b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // exceptions enabled. 1322b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#if __cpp_exceptions && LANG_CXX11 1323b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer try { 1324b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer std::random_device rd; 1325b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer std::knuth_b knuth(rd()); 1326b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer std::uniform_int_distribution<size_type> u; 1327b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return u(knuth); 1328b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } catch (...) { } 1329b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#endif 1330b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type s = static_cast<size_type>(reinterpret_cast<uintptr_t>(this)); 1331b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#if defined(__x86_64__) && defined(__GNUC__) 1332b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer uint32 hi, lo; 1333b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer asm("rdtsc" : "=a" (lo), "=d" (hi)); 1334b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer s += ((static_cast<uint64>(hi) << 32) | lo); 1335b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#endif 1336b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return s; 1337b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1338b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1339b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type num_elements_; 1340b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type num_buckets_; 1341b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type seed_; 1342b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type index_of_first_non_null_; 1343b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void** table_; // an array with num_buckets_ entries 1344b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Allocator alloc_; 1345b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(InnerMap); 1346b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer }; // end of class InnerMap 1347b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1348b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef hash_map<Key, value_type*, hash<Key>, equal_to<Key>, 1349b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer MapAllocator<std::pair<const Key, MapPair<Key, T>*> > > 1350b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer DeprecatedInnerMap; 1351b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1352b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer public: 1353b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Iterators 1354b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer class iterator_base { 1355b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer public: 1356b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // We support "old style" and "new style" iterators for now. This is 1357b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // temporary. Also, for "iterator()" we have an unknown category. 1358b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // TODO(gpike): get rid of this. 1359b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer enum IteratorStyle { kUnknown, kOld, kNew }; 1360b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer explicit iterator_base(IteratorStyle style) : iterator_style_(style) {} 1361b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1362b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bool OldStyle() const { 1363b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_DCHECK_NE(iterator_style_, kUnknown); 1364b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return iterator_style_ == kOld; 1365b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1366b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bool UnknownStyle() const { 1367b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return iterator_style_ == kUnknown; 1368b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1369b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bool SameStyle(const iterator_base& other) const { 1370b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return iterator_style_ == other.iterator_style_; 1371b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1372b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1373b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer private: 1374b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer IteratorStyle iterator_style_; 1375b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer }; 1376b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1377b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer class const_iterator 1378b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : private iterator_base, 1379b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer public std::iterator<std::forward_iterator_tag, value_type, ptrdiff_t, 1380b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const value_type*, const value_type&> { 1381b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef typename InnerMap::const_iterator InnerIt; 1382b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef typename DeprecatedInnerMap::const_iterator DeprecatedInnerIt; 1383b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1384b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer public: 1385b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const_iterator() : iterator_base(iterator_base::kUnknown) {} 1386b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer explicit const_iterator(const DeprecatedInnerIt& dit) 1387b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : iterator_base(iterator_base::kOld), dit_(dit) {} 1388b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer explicit const_iterator(const InnerIt& it) 1389b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : iterator_base(iterator_base::kNew), it_(it) {} 1390b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1391b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const_iterator(const const_iterator& other) 1392b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : iterator_base(other), it_(other.it_), dit_(other.dit_) {} 1393b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1394b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const_reference operator*() const { 1395b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return this->OldStyle() ? *dit_->second : *it_->value(); 1396b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1397b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const_pointer operator->() const { return &(operator*()); } 1398b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1399b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const_iterator& operator++() { 1400b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (this->OldStyle()) 1401b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer ++dit_; 1402b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer else 1403b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer ++it_; 1404b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return *this; 1405b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1406b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const_iterator operator++(int) { 1407b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return this->OldStyle() ? const_iterator(dit_++) : const_iterator(it_++); 1408b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1409b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1410b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer friend bool operator==(const const_iterator& a, const const_iterator& b) { 1411b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (!a.SameStyle(b)) return false; 1412b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (a.UnknownStyle()) return true; 1413b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return a.OldStyle() ? (a.dit_ == b.dit_) : (a.it_ == b.it_); 1414b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1415b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer friend bool operator!=(const const_iterator& a, const const_iterator& b) { 1416b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return !(a == b); 1417b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1418b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1419b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer private: 1420b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer InnerIt it_; 1421b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer DeprecatedInnerIt dit_; 1422b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer }; 1423b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1424b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer class iterator : private iterator_base, 1425b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer public std::iterator<std::forward_iterator_tag, value_type> { 1426b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef typename InnerMap::iterator InnerIt; 1427b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef typename DeprecatedInnerMap::iterator DeprecatedInnerIt; 1428b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1429b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer public: 1430b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator() : iterator_base(iterator_base::kUnknown) {} 1431b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer explicit iterator(const DeprecatedInnerIt& dit) 1432b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : iterator_base(iterator_base::kOld), dit_(dit) {} 1433b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer explicit iterator(const InnerIt& it) 1434b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : iterator_base(iterator_base::kNew), it_(it) {} 1435b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1436b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer reference operator*() const { 1437b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return this->OldStyle() ? *dit_->second : *it_->value(); 1438b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1439b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer pointer operator->() const { return &(operator*()); } 1440b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1441b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator& operator++() { 1442b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (this->OldStyle()) 1443b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer ++dit_; 1444b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer else 1445b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer ++it_; 1446b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return *this; 1447b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1448b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator operator++(int) { 1449b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return this->OldStyle() ? iterator(dit_++) : iterator(it_++); 1450b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1451b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1452b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Allow implicit conversion to const_iterator. 1453b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer operator const_iterator() const { 1454b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return this->OldStyle() ? 1455b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const_iterator(typename DeprecatedInnerMap::const_iterator(dit_)) : 1456b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const_iterator(typename InnerMap::const_iterator(it_)); 1457b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1458b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1459b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer friend bool operator==(const iterator& a, const iterator& b) { 1460b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (!a.SameStyle(b)) return false; 1461b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (a.UnknownStyle()) return true; 1462b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return a.OldStyle() ? a.dit_ == b.dit_ : a.it_ == b.it_; 1463b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1464b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer friend bool operator!=(const iterator& a, const iterator& b) { 1465b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return !(a == b); 1466b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1467b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1468b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer private: 1469b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer friend class Map; 1470b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1471b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer InnerIt it_; 1472b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer DeprecatedInnerIt dit_; 1473b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer }; 1474b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1475b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator begin() { 1476b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return old_style_ ? iterator(deprecated_elements_->begin()) 1477b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : iterator(elements_->begin()); 1478b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1479b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator end() { 1480b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return old_style_ ? iterator(deprecated_elements_->end()) 1481b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : iterator(elements_->end()); 1482b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1483b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const_iterator begin() const { 1484b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return old_style_ ? const_iterator(deprecated_elements_->begin()) 1485b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : const_iterator(iterator(elements_->begin())); 1486b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1487b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const_iterator end() const { 1488b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return old_style_ ? const_iterator(deprecated_elements_->end()) 1489b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : const_iterator(iterator(elements_->end())); 1490b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1491b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const_iterator cbegin() const { return begin(); } 1492b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const_iterator cend() const { return end(); } 1493b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1494b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Capacity 1495b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type size() const { 1496b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return old_style_ ? deprecated_elements_->size() : elements_->size(); 1497b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1498b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bool empty() const { return size() == 0; } 1499b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1500b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Element access 1501b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer T& operator[](const key_type& key) { 1502b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer value_type** value = 1503b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer old_style_ ? &(*deprecated_elements_)[key] : &(*elements_)[key]; 1504b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (*value == NULL) { 1505b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer *value = CreateValueTypeInternal(key); 1506b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer internal::MapValueInitializer<google::protobuf::is_proto_enum<T>::value, 1507b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer T>::Initialize((*value)->second, 1508b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer default_enum_value_); 1509b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1510b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return (*value)->second; 1511b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1512b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const T& at(const key_type& key) const { 1513b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const_iterator it = find(key); 1514b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_CHECK(it != end()); 1515b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return it->second; 1516b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1517b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer T& at(const key_type& key) { 1518b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator it = find(key); 1519b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_CHECK(it != end()); 1520b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return it->second; 1521b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1522b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1523b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Lookup 1524b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type count(const key_type& key) const { 1525b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (find(key) != end()) assert(key == find(key)->first); 1526b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return find(key) == end() ? 0 : 1; 1527b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1528b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const_iterator find(const key_type& key) const { 1529b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return old_style_ ? const_iterator(deprecated_elements_->find(key)) 1530b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : const_iterator(iterator(elements_->find(key))); 1531b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1532b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator find(const key_type& key) { 1533b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return old_style_ ? iterator(deprecated_elements_->find(key)) 1534b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : iterator(elements_->find(key)); 1535b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1536b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer std::pair<const_iterator, const_iterator> equal_range( 1537b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const key_type& key) const { 1538b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const_iterator it = find(key); 1539b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (it == end()) { 1540b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return std::pair<const_iterator, const_iterator>(it, it); 1541b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } else { 1542b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const_iterator begin = it++; 1543b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return std::pair<const_iterator, const_iterator>(begin, it); 1544b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1545b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1546b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer std::pair<iterator, iterator> equal_range(const key_type& key) { 1547b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator it = find(key); 1548b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (it == end()) { 1549b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return std::pair<iterator, iterator>(it, it); 1550b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } else { 1551b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator begin = it++; 1552b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return std::pair<iterator, iterator>(begin, it); 1553b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1554b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1555b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1556b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // insert 1557b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer std::pair<iterator, bool> insert(const value_type& value) { 1558b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (old_style_) { 1559b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator it = find(value.first); 1560b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (it != end()) { 1561b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return std::pair<iterator, bool>(it, false); 1562b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } else { 1563b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return std::pair<iterator, bool>( 1564b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator(deprecated_elements_->insert(std::pair<Key, value_type*>( 1565b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer value.first, CreateValueTypeInternal(value))).first), true); 1566b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1567b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } else { 1568b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer std::pair<typename InnerMap::iterator, bool> p = 1569b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer elements_->insert(value.first); 1570b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (p.second) { 1571b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer p.first->value() = CreateValueTypeInternal(value); 1572b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1573b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return std::pair<iterator, bool>(iterator(p.first), p.second); 1574b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1575b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1576b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer template <class InputIt> 1577b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void insert(InputIt first, InputIt last) { 1578b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer for (InputIt it = first; it != last; ++it) { 1579b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator exist_it = find(it->first); 1580b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (exist_it == end()) { 1581b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer operator[](it->first) = it->second; 1582b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1583b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1584b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1585b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1586b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Erase and clear 1587b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_type erase(const key_type& key) { 1588b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator it = find(key); 1589b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (it == end()) { 1590b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return 0; 1591b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } else { 1592b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer erase(it); 1593b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return 1; 1594b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1595b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1596b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator erase(iterator pos) { 1597b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (arena_ == NULL) delete pos.operator->(); 1598b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer iterator i = pos++; 1599b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (old_style_) 1600b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer deprecated_elements_->erase(i.dit_); 1601b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer else 1602b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer elements_->erase(i.it_); 1603b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return pos; 1604b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1605b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void erase(iterator first, iterator last) { 1606b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer while (first != last) { 1607b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer first = erase(first); 1608b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1609b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1610b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void clear() { erase(begin(), end()); } 1611b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1612b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Assign 1613b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Map& operator=(const Map& other) { 1614b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (this != &other) { 1615b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer clear(); 1616b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer insert(other.begin(), other.end()); 1617b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1618b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return *this; 1619b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1620b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1621b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Access to hasher. Currently this returns a copy, but it may 1622b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // be modified to return a const reference in the future. 1623b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer hasher hash_function() const { 1624b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return old_style_ ? deprecated_elements_->hash_function() 1625b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer : elements_->hash_function(); 1626b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1627b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1628b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer private: 1629b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // Set default enum value only for proto2 map field whose value is enum type. 1630b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer void SetDefaultEnumValue(int default_enum_value) { 1631b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer default_enum_value_ = default_enum_value; 1632b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1633b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1634b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer value_type* CreateValueTypeInternal(const Key& key) { 1635b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (arena_ == NULL) { 1636b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return new value_type(key); 1637b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } else { 1638b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer value_type* value = reinterpret_cast<value_type*>( 1639b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Arena::CreateArray<uint8>(arena_, sizeof(value_type))); 1640b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Arena::CreateInArenaStorage(const_cast<Key*>(&value->first), arena_); 1641b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Arena::CreateInArenaStorage(&value->second, arena_); 1642b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const_cast<Key&>(value->first) = key; 1643b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return value; 1644b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1645b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1646b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1647b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer value_type* CreateValueTypeInternal(const value_type& value) { 1648b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer if (arena_ == NULL) { 1649b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return new value_type(value); 1650b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } else { 1651b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer value_type* p = reinterpret_cast<value_type*>( 1652b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Arena::CreateArray<uint8>(arena_, sizeof(value_type))); 1653b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Arena::CreateInArenaStorage(const_cast<Key*>(&p->first), arena_); 1654b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Arena::CreateInArenaStorage(&p->second, arena_); 1655b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const_cast<Key&>(p->first) = value.first; 1656b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer p->second = value.second; 1657b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return p; 1658b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1659b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1660b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1661b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer Arena* arena_; 1662b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer int default_enum_value_; 1663b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // The following is a tagged union because we support two map styles 1664b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // for now. 1665b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer // TODO(gpike): get rid of the old style. 1666b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const bool old_style_; 1667b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer union { 1668b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer InnerMap* elements_; 1669b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer DeprecatedInnerMap* deprecated_elements_; 1670b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer }; 1671b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1672b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer friend class ::google::protobuf::Arena; 1673b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef void InternalArenaConstructable_; 1674b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer typedef void DestructorSkippable_; 1675b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer template <typename K, typename V, 1676b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer internal::WireFormatLite::FieldType key_wire_type, 1677b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer internal::WireFormatLite::FieldType value_wire_type, 1678b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer int default_enum_value> 1679b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer friend class internal::MapFieldLite; 1680b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer}; 1681b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1682b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer} // namespace protobuf 1683b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer} // namespace google 1684b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1685b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas BerghammerGOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_START 1686b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammertemplate<> 1687b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammerstruct hash<google::protobuf::MapKey> { 1688b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer size_t 1689b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer operator()(const google::protobuf::MapKey& map_key) const { 1690b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer switch (map_key.type()) { 1691b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case google::protobuf::FieldDescriptor::CPPTYPE_DOUBLE: 1692b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case google::protobuf::FieldDescriptor::CPPTYPE_FLOAT: 1693b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case google::protobuf::FieldDescriptor::CPPTYPE_ENUM: 1694b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case google::protobuf::FieldDescriptor::CPPTYPE_MESSAGE: 1695b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_LOG(FATAL) << "Unsupported"; 1696b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer break; 1697b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case google::protobuf::FieldDescriptor::CPPTYPE_STRING: 1698b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return hash<string>()(map_key.GetStringValue()); 1699b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case google::protobuf::FieldDescriptor::CPPTYPE_INT64: 1700b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return hash< ::google::protobuf::int64>()(map_key.GetInt64Value()); 1701b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case google::protobuf::FieldDescriptor::CPPTYPE_INT32: 1702b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return hash< ::google::protobuf::int32>()(map_key.GetInt32Value()); 1703b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case google::protobuf::FieldDescriptor::CPPTYPE_UINT64: 1704b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return hash< ::google::protobuf::uint64>()(map_key.GetUInt64Value()); 1705b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case google::protobuf::FieldDescriptor::CPPTYPE_UINT32: 1706b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return hash< ::google::protobuf::uint32>()(map_key.GetUInt32Value()); 1707b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer case google::protobuf::FieldDescriptor::CPPTYPE_BOOL: 1708b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return hash<bool>()(map_key.GetBoolValue()); 1709b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1710b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer GOOGLE_LOG(FATAL) << "Can't get here."; 1711b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return 0; 1712b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1713b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer bool 1714b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer operator()(const google::protobuf::MapKey& map_key1, 1715b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer const google::protobuf::MapKey& map_key2) const { 1716b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer return map_key1 < map_key2; 1717b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer } 1718b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer}; 1719b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas BerghammerGOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_END 1720b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer 1721b0575e93e4c39dec69365b850088a1eb7f82c5b3Tamas Berghammer#endif // GOOGLE_PROTOBUF_MAP_H__ 1722