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