diff options
Diffstat (limited to 'windows_msvc-x86_64/include/google/protobuf/map.h')
| -rw-r--r-- | windows_msvc-x86_64/include/google/protobuf/map.h | 1742 |
1 files changed, 1742 insertions, 0 deletions
diff --git a/windows_msvc-x86_64/include/google/protobuf/map.h b/windows_msvc-x86_64/include/google/protobuf/map.h new file mode 100644 index 0000000..1b9aa70 --- /dev/null +++ b/windows_msvc-x86_64/include/google/protobuf/map.h @@ -0,0 +1,1742 @@ +// Protocol Buffers - Google's data interchange format +// Copyright 2008 Google Inc. All rights reserved. +// https://developers.google.com/protocol-buffers/ +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following disclaimer +// in the documentation and/or other materials provided with the +// distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived from +// this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#ifndef GOOGLE_PROTOBUF_MAP_H__ +#define GOOGLE_PROTOBUF_MAP_H__ + +#include <google/protobuf/stubs/hash.h> +#include <iterator> +#include <limits> // To support Visual Studio 2008 +#include <set> +#include <utility> + +#include <google/protobuf/stubs/common.h> +#include <google/protobuf/arena.h> +#include <google/protobuf/generated_enum_util.h> +#include <google/protobuf/map_type_handler.h> +#include <google/protobuf/message.h> +#include <google/protobuf/descriptor.h> +#if __cpp_exceptions && LANG_CXX11 +#include <random> +#endif + +namespace google { +namespace protobuf { + +// The Map and MapIterator types are provided by this header file. +// Please avoid using other types defined here, unless they are public +// types within Map or MapIterator, such as Map::value_type. +template <typename Key, typename T> +class Map; + +class MapIterator; + +template <typename Enum> struct is_proto_enum; + +namespace internal { +template <typename Key, typename T, + WireFormatLite::FieldType key_wire_type, + WireFormatLite::FieldType value_wire_type, + int default_enum_value> +class MapFieldLite; + +template <typename Key, typename T, + WireFormatLite::FieldType key_wire_type, + WireFormatLite::FieldType value_wire_type, + int default_enum_value> +class MapField; + +template <typename Key, typename T> +class TypeDefinedMapFieldBase; + +class DynamicMapField; + +class GeneratedMessageReflection; +} // namespace internal + +#define TYPE_CHECK(EXPECTEDTYPE, METHOD) \ + if (type() != EXPECTEDTYPE) { \ + GOOGLE_LOG(FATAL) \ + << "Protocol Buffer map usage error:\n" \ + << METHOD << " type does not match\n" \ + << " Expected : " \ + << FieldDescriptor::CppTypeName(EXPECTEDTYPE) << "\n" \ + << " Actual : " \ + << FieldDescriptor::CppTypeName(type()); \ + } + +// MapKey is an union type for representing any possible +// map key. +class LIBPROTOBUF_EXPORT MapKey { + public: + MapKey() : type_(0) { + } + MapKey(const MapKey& other) : type_(0) { + CopyFrom(other); + } + + ~MapKey() { + if (type_ == FieldDescriptor::CPPTYPE_STRING) { + delete val_.string_value_; + } + } + + FieldDescriptor::CppType type() const { + if (type_ == 0) { + GOOGLE_LOG(FATAL) + << "Protocol Buffer map usage error:\n" + << "MapKey::type MapKey is not initialized. " + << "Call set methods to initialize MapKey."; + } + return (FieldDescriptor::CppType)type_; + } + + void SetInt64Value(int64 value) { + SetType(FieldDescriptor::CPPTYPE_INT64); + val_.int64_value_ = value; + } + void SetUInt64Value(uint64 value) { + SetType(FieldDescriptor::CPPTYPE_UINT64); + val_.uint64_value_ = value; + } + void SetInt32Value(int32 value) { + SetType(FieldDescriptor::CPPTYPE_INT32); + val_.int32_value_ = value; + } + void SetUInt32Value(uint32 value) { + SetType(FieldDescriptor::CPPTYPE_UINT32); + val_.uint32_value_ = value; + } + void SetBoolValue(bool value) { + SetType(FieldDescriptor::CPPTYPE_BOOL); + val_.bool_value_ = value; + } + void SetStringValue(const string& val) { + SetType(FieldDescriptor::CPPTYPE_STRING); + *val_.string_value_ = val; + } + + int64 GetInt64Value() const { + TYPE_CHECK(FieldDescriptor::CPPTYPE_INT64, + "MapKey::GetInt64Value"); + return val_.int64_value_; + } + uint64 GetUInt64Value() const { + TYPE_CHECK(FieldDescriptor::CPPTYPE_UINT64, + "MapKey::GetUInt64Value"); + return val_.uint64_value_; + } + int32 GetInt32Value() const { + TYPE_CHECK(FieldDescriptor::CPPTYPE_INT32, + "MapKey::GetInt32Value"); + return val_.int32_value_; + } + uint32 GetUInt32Value() const { + TYPE_CHECK(FieldDescriptor::CPPTYPE_UINT32, + "MapKey::GetUInt32Value"); + return val_.uint32_value_; + } + bool GetBoolValue() const { + TYPE_CHECK(FieldDescriptor::CPPTYPE_BOOL, + "MapKey::GetBoolValue"); + return val_.bool_value_; + } + const string& GetStringValue() const { + TYPE_CHECK(FieldDescriptor::CPPTYPE_STRING, + "MapKey::GetStringValue"); + return *val_.string_value_; + } + + bool operator<(const MapKey& other) const { + if (type_ != other.type_) { + // We could define a total order that handles this case, but + // there currently no need. So, for now, fail. + GOOGLE_LOG(FATAL) << "Unsupported: type mismatch"; + } + switch (type()) { + case FieldDescriptor::CPPTYPE_DOUBLE: + case FieldDescriptor::CPPTYPE_FLOAT: + case FieldDescriptor::CPPTYPE_ENUM: + case FieldDescriptor::CPPTYPE_MESSAGE: + GOOGLE_LOG(FATAL) << "Unsupported"; + return false; + case FieldDescriptor::CPPTYPE_STRING: + return *val_.string_value_ < *other.val_.string_value_; + case FieldDescriptor::CPPTYPE_INT64: + return val_.int64_value_ < other.val_.int64_value_; + case FieldDescriptor::CPPTYPE_INT32: + return val_.int32_value_ < other.val_.int32_value_; + case FieldDescriptor::CPPTYPE_UINT64: + return val_.uint64_value_ < other.val_.uint64_value_; + case FieldDescriptor::CPPTYPE_UINT32: + return val_.uint32_value_ < other.val_.uint32_value_; + case FieldDescriptor::CPPTYPE_BOOL: + return val_.bool_value_ < other.val_.bool_value_; + } + return false; + } + + bool operator==(const MapKey& other) const { + if (type_ != other.type_) { + // To be consistent with operator<, we don't allow this either. + GOOGLE_LOG(FATAL) << "Unsupported: type mismatch"; + } + switch (type()) { + case FieldDescriptor::CPPTYPE_DOUBLE: + case FieldDescriptor::CPPTYPE_FLOAT: + case FieldDescriptor::CPPTYPE_ENUM: + case FieldDescriptor::CPPTYPE_MESSAGE: + GOOGLE_LOG(FATAL) << "Unsupported"; + break; + case FieldDescriptor::CPPTYPE_STRING: + return *val_.string_value_ == *other.val_.string_value_; + case FieldDescriptor::CPPTYPE_INT64: + return val_.int64_value_ == other.val_.int64_value_; + case FieldDescriptor::CPPTYPE_INT32: + return val_.int32_value_ == other.val_.int32_value_; + case FieldDescriptor::CPPTYPE_UINT64: + return val_.uint64_value_ == other.val_.uint64_value_; + case FieldDescriptor::CPPTYPE_UINT32: + return val_.uint32_value_ == other.val_.uint32_value_; + case FieldDescriptor::CPPTYPE_BOOL: + return val_.bool_value_ == other.val_.bool_value_; + } + GOOGLE_LOG(FATAL) << "Can't get here."; + return false; + } + + void CopyFrom(const MapKey& other) { + SetType(other.type()); + switch (type_) { + case FieldDescriptor::CPPTYPE_DOUBLE: + case FieldDescriptor::CPPTYPE_FLOAT: + case FieldDescriptor::CPPTYPE_ENUM: + case FieldDescriptor::CPPTYPE_MESSAGE: + GOOGLE_LOG(FATAL) << "Unsupported"; + break; + case FieldDescriptor::CPPTYPE_STRING: + *val_.string_value_ = *other.val_.string_value_; + break; + case FieldDescriptor::CPPTYPE_INT64: + val_.int64_value_ = other.val_.int64_value_; + break; + case FieldDescriptor::CPPTYPE_INT32: + val_.int32_value_ = other.val_.int32_value_; + break; + case FieldDescriptor::CPPTYPE_UINT64: + val_.uint64_value_ = other.val_.uint64_value_; + break; + case FieldDescriptor::CPPTYPE_UINT32: + val_.uint32_value_ = other.val_.uint32_value_; + break; + case FieldDescriptor::CPPTYPE_BOOL: + val_.bool_value_ = other.val_.bool_value_; + break; + } + } + + private: + template <typename K, typename V> + friend class internal::TypeDefinedMapFieldBase; + friend class MapIterator; + friend class internal::DynamicMapField; + + union KeyValue { + KeyValue() {} + string* string_value_; + int64 int64_value_; + int32 int32_value_; + uint64 uint64_value_; + uint32 uint32_value_; + bool bool_value_; + } val_; + + void SetType(FieldDescriptor::CppType type) { + if (type_ == type) return; + if (type_ == FieldDescriptor::CPPTYPE_STRING) { + delete val_.string_value_; + } + type_ = type; + if (type_ == FieldDescriptor::CPPTYPE_STRING) { + val_.string_value_ = new string; + } + } + + // type_ is 0 or a valid FieldDescriptor::CppType. + int type_; +}; + +// MapValueRef points to a map value. +class LIBPROTOBUF_EXPORT MapValueRef { + public: + MapValueRef() : data_(NULL), type_(0) {} + + void SetInt64Value(int64 value) { + TYPE_CHECK(FieldDescriptor::CPPTYPE_INT64, + "MapValueRef::SetInt64Value"); + *reinterpret_cast<int64*>(data_) = value; + } + void SetUInt64Value(uint64 value) { + TYPE_CHECK(FieldDescriptor::CPPTYPE_UINT64, + "MapValueRef::SetUInt64Value"); + *reinterpret_cast<uint64*>(data_) = value; + } + void SetInt32Value(int32 value) { + TYPE_CHECK(FieldDescriptor::CPPTYPE_INT32, + "MapValueRef::SetInt32Value"); + *reinterpret_cast<int32*>(data_) = value; + } + void SetUInt32Value(uint32 value) { + TYPE_CHECK(FieldDescriptor::CPPTYPE_UINT32, + "MapValueRef::SetUInt32Value"); + *reinterpret_cast<uint32*>(data_) = value; + } + void SetBoolValue(bool value) { + TYPE_CHECK(FieldDescriptor::CPPTYPE_BOOL, + "MapValueRef::SetBoolValue"); + *reinterpret_cast<bool*>(data_) = value; + } + // TODO(jieluo) - Checks that enum is member. + void SetEnumValue(int value) { + TYPE_CHECK(FieldDescriptor::CPPTYPE_ENUM, + "MapValueRef::SetEnumValue"); + *reinterpret_cast<int*>(data_) = value; + } + void SetStringValue(const string& value) { + TYPE_CHECK(FieldDescriptor::CPPTYPE_STRING, + "MapValueRef::SetStringValue"); + *reinterpret_cast<string*>(data_) = value; + } + void SetFloatValue(float value) { + TYPE_CHECK(FieldDescriptor::CPPTYPE_FLOAT, + "MapValueRef::SetFloatValue"); + *reinterpret_cast<float*>(data_) = value; + } + void SetDoubleValue(double value) { + TYPE_CHECK(FieldDescriptor::CPPTYPE_DOUBLE, + "MapValueRef::SetDoubleValue"); + *reinterpret_cast<double*>(data_) = value; + } + + int64 GetInt64Value() const { + TYPE_CHECK(FieldDescriptor::CPPTYPE_INT64, + "MapValueRef::GetInt64Value"); + return *reinterpret_cast<int64*>(data_); + } + uint64 GetUInt64Value() const { + TYPE_CHECK(FieldDescriptor::CPPTYPE_UINT64, + "MapValueRef::GetUInt64Value"); + return *reinterpret_cast<uint64*>(data_); + } + int32 GetInt32Value() const { + TYPE_CHECK(FieldDescriptor::CPPTYPE_INT32, + "MapValueRef::GetInt32Value"); + return *reinterpret_cast<int32*>(data_); + } + uint32 GetUInt32Value() const { + TYPE_CHECK(FieldDescriptor::CPPTYPE_UINT32, + "MapValueRef::GetUInt32Value"); + return *reinterpret_cast<uint32*>(data_); + } + bool GetBoolValue() const { + TYPE_CHECK(FieldDescriptor::CPPTYPE_BOOL, + "MapValueRef::GetBoolValue"); + return *reinterpret_cast<bool*>(data_); + } + int GetEnumValue() const { + TYPE_CHECK(FieldDescriptor::CPPTYPE_ENUM, + "MapValueRef::GetEnumValue"); + return *reinterpret_cast<int*>(data_); + } + const string& GetStringValue() const { + TYPE_CHECK(FieldDescriptor::CPPTYPE_STRING, + "MapValueRef::GetStringValue"); + return *reinterpret_cast<string*>(data_); + } + float GetFloatValue() const { + TYPE_CHECK(FieldDescriptor::CPPTYPE_FLOAT, + "MapValueRef::GetFloatValue"); + return *reinterpret_cast<float*>(data_); + } + double GetDoubleValue() const { + TYPE_CHECK(FieldDescriptor::CPPTYPE_DOUBLE, + "MapValueRef::GetDoubleValue"); + return *reinterpret_cast<double*>(data_); + } + + const Message& GetMessageValue() const { + TYPE_CHECK(FieldDescriptor::CPPTYPE_MESSAGE, + "MapValueRef::GetMessageValue"); + return *reinterpret_cast<Message*>(data_); + } + + Message* MutableMessageValue() { + TYPE_CHECK(FieldDescriptor::CPPTYPE_MESSAGE, + "MapValueRef::MutableMessageValue"); + return reinterpret_cast<Message*>(data_); + } + + private: + template <typename K, typename V, + internal::WireFormatLite::FieldType key_wire_type, + internal::WireFormatLite::FieldType value_wire_type, + int default_enum_value> + friend class internal::MapField; + template <typename K, typename V> + friend class internal::TypeDefinedMapFieldBase; + friend class MapIterator; + friend class internal::GeneratedMessageReflection; + friend class internal::DynamicMapField; + + void SetType(FieldDescriptor::CppType type) { + type_ = type; + } + + FieldDescriptor::CppType type() const { + if (type_ == 0 || data_ == NULL) { + GOOGLE_LOG(FATAL) + << "Protocol Buffer map usage error:\n" + << "MapValueRef::type MapValueRef is not initialized."; + } + return (FieldDescriptor::CppType)type_; + } + void SetValue(const void* val) { + data_ = const_cast<void*>(val); + } + void CopyFrom(const MapValueRef& other) { + type_ = other.type_; + data_ = other.data_; + } + // Only used in DynamicMapField + void DeleteData() { + switch (type_) { +#define HANDLE_TYPE(CPPTYPE, TYPE) \ + case google::protobuf::FieldDescriptor::CPPTYPE_##CPPTYPE: { \ + delete reinterpret_cast<TYPE*>(data_); \ + break; \ + } + HANDLE_TYPE(INT32, int32); + HANDLE_TYPE(INT64, int64); + HANDLE_TYPE(UINT32, uint32); + HANDLE_TYPE(UINT64, uint64); + HANDLE_TYPE(DOUBLE, double); + HANDLE_TYPE(FLOAT, float); + HANDLE_TYPE(BOOL, bool); + HANDLE_TYPE(STRING, string); + HANDLE_TYPE(ENUM, int32); + HANDLE_TYPE(MESSAGE, Message); +#undef HANDLE_TYPE + } + } + // data_ point to a map value. MapValueRef does not + // own this value. + void* data_; + // type_ is 0 or a valid FieldDescriptor::CppType. + int type_; +}; + +#undef TYPE_CHECK + +// This is the class for google::protobuf::Map's internal value_type. Instead of using +// std::pair as value_type, we use this class which provides us more control of +// its process of construction and destruction. +template <typename Key, typename T> +class MapPair { + public: + typedef const Key first_type; + typedef T second_type; + + MapPair(const Key& other_first, const T& other_second) + : first(other_first), second(other_second) {} + explicit MapPair(const Key& other_first) : first(other_first), second() {} + MapPair(const MapPair& other) + : first(other.first), second(other.second) {} + + ~MapPair() {} + + // Implicitly convertible to std::pair of compatible types. + template <typename T1, typename T2> + operator std::pair<T1, T2>() const { + return std::pair<T1, T2>(first, second); + } + + const Key first; + T second; + + private: + friend class ::google::protobuf::Arena; + friend class Map<Key, T>; +}; + +// google::protobuf::Map is an associative container type used to store protobuf map +// fields. Each Map instance may or may not use a different hash function, a +// different iteration order, and so on. E.g., please don't examine +// implementation details to decide if the following would work: +// Map<int, int> m0, m1; +// m0[0] = m1[0] = m0[1] = m1[1] = 0; +// assert(m0.begin()->first == m1.begin()->first); // Bug! +// +// Map's interface is similar to std::unordered_map, except that Map is not +// designed to play well with exceptions. +template <typename Key, typename T> +class Map { + public: + typedef Key key_type; + typedef T mapped_type; + typedef MapPair<Key, T> value_type; + + typedef value_type* pointer; + typedef const value_type* const_pointer; + typedef value_type& reference; + typedef const value_type& const_reference; + + typedef size_t size_type; + typedef hash<Key> hasher; + + explicit Map(bool old_style = true) + : arena_(NULL), + default_enum_value_(0), + old_style_(old_style) { + Init(); + } + explicit Map(Arena* arena, bool old_style = true) + : arena_(arena), + default_enum_value_(0), + old_style_(old_style) { + Init(); + } + Map(const Map& other) + : arena_(NULL), + default_enum_value_(other.default_enum_value_), + old_style_(other.old_style_) { + Init(); + insert(other.begin(), other.end()); + } + template <class InputIt> + Map(const InputIt& first, const InputIt& last, bool old_style = true) + : arena_(NULL), + default_enum_value_(0), + old_style_(old_style) { + Init(); + insert(first, last); + } + + ~Map() { + clear(); + if (arena_ == NULL) { + if (old_style_) + delete deprecated_elements_; + else + delete elements_; + } + } + + private: + void Init() { + if (old_style_) + deprecated_elements_ = Arena::Create<DeprecatedInnerMap>( + arena_, 0, hasher(), equal_to<Key>(), + MapAllocator<std::pair<const Key, MapPair<Key, T>*> >(arena_)); + else + elements_ = + Arena::Create<InnerMap>(arena_, 0, hasher(), Allocator(arena_)); + } + + // re-implement std::allocator to use arena allocator for memory allocation. + // Used for google::protobuf::Map implementation. Users should not use this class + // directly. + template <typename U> + class MapAllocator { + public: + typedef U value_type; + typedef value_type* pointer; + typedef const value_type* const_pointer; + typedef value_type& reference; + typedef const value_type& const_reference; + typedef size_t size_type; + typedef ptrdiff_t difference_type; + + MapAllocator() : arena_(NULL) {} + explicit MapAllocator(Arena* arena) : arena_(arena) {} + template <typename X> + MapAllocator(const MapAllocator<X>& allocator) + : arena_(allocator.arena()) {} + + pointer allocate(size_type n, const_pointer hint = 0) { + // If arena is not given, malloc needs to be called which doesn't + // construct element object. + if (arena_ == NULL) { + return reinterpret_cast<pointer>(malloc(n * sizeof(value_type))); + } else { + return reinterpret_cast<pointer>( + Arena::CreateArray<uint8>(arena_, n * sizeof(value_type))); + } + } + + void deallocate(pointer p, size_type n) { + if (arena_ == NULL) { + free(p); + } + } + +#if __cplusplus >= 201103L && !defined(GOOGLE_PROTOBUF_OS_APPLE) && \ + !defined(GOOGLE_PROTOBUF_OS_NACL) && \ + !defined(GOOGLE_PROTOBUF_OS_ANDROID) && \ + !defined(GOOGLE_PROTOBUF_OS_EMSCRIPTEN) + template<class NodeType, class... Args> + void construct(NodeType* p, Args&&... args) { + // Clang 3.6 doesn't compile static casting to void* directly. (Issue + // #1266) According C++ standard 5.2.9/1: "The static_cast operator shall + // not cast away constness". So first the maybe const pointer is casted to + // const void* and after the const void* is const casted. + new (const_cast<void*>(static_cast<const void*>(p))) + NodeType(std::forward<Args>(args)...); + } + + template<class NodeType> + void destroy(NodeType* p) { + p->~NodeType(); + } +#else + void construct(pointer p, const_reference t) { new (p) value_type(t); } + + void destroy(pointer p) { p->~value_type(); } +#endif + + template <typename X> + struct rebind { + typedef MapAllocator<X> other; + }; + + template <typename X> + bool operator==(const MapAllocator<X>& other) const { + return arena_ == other.arena_; + } + + template <typename X> + bool operator!=(const MapAllocator<X>& other) const { + return arena_ != other.arena_; + } + + // To support Visual Studio 2008 + size_type max_size() const { + return std::numeric_limits<size_type>::max(); + } + + // To support gcc-4.4, which does not properly + // support templated friend classes + Arena* arena() const { + return arena_; + } + + private: + typedef void DestructorSkippable_; + Arena* const arena_; + }; + + // InnerMap's key type is Key and its value type is value_type*. We use a + // custom class here and for Node, below, to ensure that k_ is at offset 0, + // allowing safe conversion from pointer to Node to pointer to Key, and vice + // versa when appropriate. + class KeyValuePair { + public: + KeyValuePair(const Key& k, value_type* v) : k_(k), v_(v) {} + + const Key& key() const { return k_; } + Key& key() { return k_; } + value_type* const value() const { return v_; } + value_type*& value() { return v_; } + + private: + Key k_; + value_type* v_; + }; + + typedef MapAllocator<KeyValuePair> Allocator; + + // InnerMap is a generic hash-based map. It doesn't contain any + // protocol-buffer-specific logic. It is a chaining hash map with the + // additional feature that some buckets can be converted to use an ordered + // container. This ensures O(lg n) bounds on find, insert, and erase, while + // avoiding the overheads of ordered containers most of the time. + // + // The implementation doesn't need the full generality of unordered_map, + // and it doesn't have it. More bells and whistles can be added as needed. + // Some implementation details: + // 1. The hash function has type hasher and the equality function + // equal_to<Key>. We inherit from hasher to save space + // (empty-base-class optimization). + // 2. The number of buckets is a power of two. + // 3. Buckets are converted to trees in pairs: if we convert bucket b then + // buckets b and b^1 will share a tree. Invariant: buckets b and b^1 have + // the same non-NULL value iff they are sharing a tree. (An alternative + // implementation strategy would be to have a tag bit per bucket.) + // 4. As is typical for hash_map and such, the Keys and Values are always + // stored in linked list nodes. Pointers to elements are never invalidated + // until the element is deleted. + // 5. The trees' payload type is pointer to linked-list node. Tree-converting + // a bucket doesn't copy Key-Value pairs. + // 6. Once we've tree-converted a bucket, it is never converted back. However, + // the items a tree contains may wind up assigned to trees or lists upon a + // rehash. + // 7. The code requires no C++ features from C++11 or later. + // 8. Mutations to a map do not invalidate the map's iterators, pointers to + // elements, or references to elements. + // 9. Except for erase(iterator), any non-const method can reorder iterators. + class InnerMap : private hasher { + public: + typedef value_type* Value; + + InnerMap(size_type n, hasher h, Allocator alloc) + : hasher(h), + num_elements_(0), + seed_(Seed()), + table_(NULL), + alloc_(alloc) { + n = TableSize(n); + table_ = CreateEmptyTable(n); + num_buckets_ = index_of_first_non_null_ = n; + } + + ~InnerMap() { + if (table_ != NULL) { + clear(); + Dealloc<void*>(table_, num_buckets_); + } + } + + private: + enum { kMinTableSize = 8 }; + + // Linked-list nodes, as one would expect for a chaining hash table. + struct Node { + KeyValuePair kv; + Node* next; + }; + + // This is safe only if the given pointer is known to point to a Key that is + // part of a Node. + static Node* NodePtrFromKeyPtr(Key* k) { + return reinterpret_cast<Node*>(k); + } + + static Key* KeyPtrFromNodePtr(Node* node) { return &node->kv.key(); } + + // Trees. The payload type is pointer to Key, so that we can query the tree + // with Keys that are not in any particular data structure. When we insert, + // though, the pointer is always pointing to a Key that is inside a Node. + struct KeyCompare { + bool operator()(const Key* n0, const Key* n1) const { return *n0 < *n1; } + }; + typedef typename Allocator::template rebind<Key*>::other KeyPtrAllocator; + typedef std::set<Key*, KeyCompare, KeyPtrAllocator> Tree; + + // iterator and const_iterator are instantiations of iterator_base. + template <typename KeyValueType> + class iterator_base { + public: + typedef KeyValueType& reference; + typedef KeyValueType* pointer; + typedef typename Tree::iterator TreeIterator; + + // Invariants: + // node_ is always correct. This is handy because the most common + // operations are operator* and operator-> and they only use node_. + // When node_ is set to a non-NULL value, all the other non-const fields + // are updated to be correct also, but those fields can become stale + // if the underlying map is modified. When those fields are needed they + // are rechecked, and updated if necessary. + iterator_base() : node_(NULL) {} + + explicit iterator_base(const InnerMap* m) : m_(m) { + SearchFrom(m->index_of_first_non_null_); + } + + // Any iterator_base can convert to any other. This is overkill, and we + // rely on the enclosing class to use it wisely. The standard "iterator + // can convert to const_iterator" is OK but the reverse direction is not. + template <typename U> + explicit iterator_base(const iterator_base<U>& it) + : node_(it.node_), + m_(it.m_), + bucket_index_(it.bucket_index_), + tree_it_(it.tree_it_) {} + + iterator_base(Node* n, const InnerMap* m, size_type index) + : node_(n), + m_(m), + bucket_index_(index) {} + + iterator_base(TreeIterator tree_it, const InnerMap* m, size_type index) + : node_(NodePtrFromKeyPtr(*tree_it)), + m_(m), + bucket_index_(index), + tree_it_(tree_it) { + // Invariant: iterators that use tree_it_ have an even bucket_index_. + GOOGLE_DCHECK_EQ(bucket_index_ % 2, 0); + } + + // Advance through buckets, looking for the first that isn't empty. + // If nothing non-empty is found then leave node_ == NULL. + void SearchFrom(size_type start_bucket) { + GOOGLE_DCHECK(m_->index_of_first_non_null_ == m_->num_buckets_ || + m_->table_[m_->index_of_first_non_null_] != NULL); + node_ = NULL; + for (bucket_index_ = start_bucket; bucket_index_ < m_->num_buckets_; + bucket_index_++) { + if (m_->TableEntryIsNonEmptyList(bucket_index_)) { + node_ = static_cast<Node*>(m_->table_[bucket_index_]); + break; + } else if (m_->TableEntryIsTree(bucket_index_)) { + Tree* tree = static_cast<Tree*>(m_->table_[bucket_index_]); + GOOGLE_DCHECK(!tree->empty()); + tree_it_ = tree->begin(); + node_ = NodePtrFromKeyPtr(*tree_it_); + break; + } + } + } + + reference operator*() const { return node_->kv; } + pointer operator->() const { return &(operator*()); } + + friend bool operator==(const iterator_base& a, const iterator_base& b) { + return a.node_ == b.node_; + } + friend bool operator!=(const iterator_base& a, const iterator_base& b) { + return a.node_ != b.node_; + } + + iterator_base& operator++() { + if (node_->next == NULL) { + const bool is_list = revalidate_if_necessary(); + if (is_list) { + SearchFrom(bucket_index_ + 1); + } else { + GOOGLE_DCHECK_EQ(bucket_index_ & 1, 0); + Tree* tree = static_cast<Tree*>(m_->table_[bucket_index_]); + if (++tree_it_ == tree->end()) { + SearchFrom(bucket_index_ + 2); + } else { + node_ = NodePtrFromKeyPtr(*tree_it_); + } + } + } else { + node_ = node_->next; + } + return *this; + } + + iterator_base operator++(int /* unused */) { + iterator_base tmp = *this; + ++*this; + return tmp; + } + + // Assumes node_ and m_ are correct and non-NULL, but other fields may be + // stale. Fix them as needed. Then return true iff node_ points to a + // Node in a list. + bool revalidate_if_necessary() { + GOOGLE_DCHECK(node_ != NULL && m_ != NULL); + // Force bucket_index_ to be in range. + bucket_index_ &= (m_->num_buckets_ - 1); + // Common case: the bucket we think is relevant points to node_. + if (m_->table_[bucket_index_] == static_cast<void*>(node_)) + return true; + // Less common: the bucket is a linked list with node_ somewhere in it, + // but not at the head. + if (m_->TableEntryIsNonEmptyList(bucket_index_)) { + Node* l = static_cast<Node*>(m_->table_[bucket_index_]); + while ((l = l->next) != NULL) { + if (l == node_) { + return true; + } + } + } + // Well, bucket_index_ still might be correct, but probably + // not. Revalidate just to be sure. This case is rare enough that we + // don't worry about potential optimizations, such as having a custom + // find-like method that compares Node* instead of const Key&. + iterator_base i(m_->find(*KeyPtrFromNodePtr(node_))); + bucket_index_ = i.bucket_index_; + tree_it_ = i.tree_it_; + return m_->TableEntryIsList(bucket_index_); + } + + Node* node_; + const InnerMap* m_; + size_type bucket_index_; + TreeIterator tree_it_; + }; + + public: + typedef iterator_base<KeyValuePair> iterator; + typedef iterator_base<const KeyValuePair> const_iterator; + + iterator begin() { return iterator(this); } + iterator end() { return iterator(); } + const_iterator begin() const { return const_iterator(this); } + const_iterator end() const { return const_iterator(); } + + void clear() { + for (size_type b = 0; b < num_buckets_; b++) { + if (TableEntryIsNonEmptyList(b)) { + Node* node = static_cast<Node*>(table_[b]); + table_[b] = NULL; + do { + Node* next = node->next; + DestroyNode(node); + node = next; + } while (node != NULL); + } else if (TableEntryIsTree(b)) { + Tree* tree = static_cast<Tree*>(table_[b]); + GOOGLE_DCHECK(table_[b] == table_[b + 1] && (b & 1) == 0); + table_[b] = table_[b + 1] = NULL; + typename Tree::iterator tree_it = tree->begin(); + do { + Node* node = NodePtrFromKeyPtr(*tree_it); + typename Tree::iterator next = tree_it; + ++next; + tree->erase(tree_it); + DestroyNode(node); + tree_it = next; + } while (tree_it != tree->end()); + DestroyTree(tree); + b++; + } + } + num_elements_ = 0; + index_of_first_non_null_ = num_buckets_; + } + + const hasher& hash_function() const { return *this; } + + static size_type max_size() { + return static_cast<size_type>(1) << (sizeof(void**) >= 8 ? 60 : 28); + } + size_type size() const { return num_elements_; } + bool empty() const { return size() == 0; } + + iterator find(const Key& k) { return iterator(FindHelper(k).first); } + const_iterator find(const Key& k) const { return FindHelper(k).first; } + + // In traditional C++ style, this performs "insert if not present." + std::pair<iterator, bool> insert(const KeyValuePair& kv) { + std::pair<const_iterator, size_type> p = FindHelper(kv.key()); + // Case 1: key was already present. + if (p.first.node_ != NULL) + return std::make_pair(iterator(p.first), false); + // Case 2: insert. + if (ResizeIfLoadIsOutOfRange(num_elements_ + 1)) { + p = FindHelper(kv.key()); + } + const size_type b = p.second; // bucket number + Node* node = Alloc<Node>(1); + alloc_.construct(&node->kv, kv); + iterator result = InsertUnique(b, node); + ++num_elements_; + return std::make_pair(result, true); + } + + // The same, but if an insertion is necessary then the value portion of the + // inserted key-value pair is left uninitialized. + std::pair<iterator, bool> insert(const Key& k) { + std::pair<const_iterator, size_type> p = FindHelper(k); + // Case 1: key was already present. + if (p.first.node_ != NULL) + return std::make_pair(iterator(p.first), false); + // Case 2: insert. + if (ResizeIfLoadIsOutOfRange(num_elements_ + 1)) { + p = FindHelper(k); + } + const size_type b = p.second; // bucket number + Node* node = Alloc<Node>(1); + typedef typename Allocator::template rebind<Key>::other KeyAllocator; + KeyAllocator(alloc_).construct(&node->kv.key(), k); + iterator result = InsertUnique(b, node); + ++num_elements_; + return std::make_pair(result, true); + } + + Value& operator[](const Key& k) { + KeyValuePair kv(k, Value()); + return insert(kv).first->value(); + } + + void erase(iterator it) { + GOOGLE_DCHECK_EQ(it.m_, this); + const bool is_list = it.revalidate_if_necessary(); + size_type b = it.bucket_index_; + Node* const item = it.node_; + if (is_list) { + GOOGLE_DCHECK(TableEntryIsNonEmptyList(b)); + Node* head = static_cast<Node*>(table_[b]); + head = EraseFromLinkedList(item, head); + table_[b] = static_cast<void*>(head); + } else { + GOOGLE_DCHECK(TableEntryIsTree(b)); + Tree* tree = static_cast<Tree*>(table_[b]); + tree->erase(it.tree_it_); + if (tree->empty()) { + // Force b to be the minimum of b and b ^ 1. This is important + // only because we want index_of_first_non_null_ to be correct. + b &= ~static_cast<size_type>(1); + DestroyTree(tree); + table_[b] = table_[b + 1] = NULL; + } + } + DestroyNode(item); + --num_elements_; + if (GOOGLE_PREDICT_FALSE(b == index_of_first_non_null_)) { + while (index_of_first_non_null_ < num_buckets_ && + table_[index_of_first_non_null_] == NULL) { + ++index_of_first_non_null_; + } + } + } + + private: + std::pair<const_iterator, size_type> FindHelper(const Key& k) const { + size_type b = BucketNumber(k); + if (TableEntryIsNonEmptyList(b)) { + Node* node = static_cast<Node*>(table_[b]); + do { + if (IsMatch(*KeyPtrFromNodePtr(node), k)) { + return std::make_pair(const_iterator(node, this, b), b); + } else { + node = node->next; + } + } while (node != NULL); + } else if (TableEntryIsTree(b)) { + GOOGLE_DCHECK_EQ(table_[b], table_[b ^ 1]); + b &= ~static_cast<size_t>(1); + Tree* tree = static_cast<Tree*>(table_[b]); + Key* key = const_cast<Key*>(&k); + typename Tree::iterator tree_it = tree->find(key); + if (tree_it != tree->end()) { + return std::make_pair(const_iterator(tree_it, this, b), b); + } + } + return std::make_pair(end(), b); + } + + // Insert the given Node in bucket b. If that would make bucket b too big, + // and bucket b is not a tree, create a tree for buckets b and b^1 to share. + // Requires count(*KeyPtrFromNodePtr(node)) == 0 and that b is the correct + // bucket. num_elements_ is not modified. + iterator InsertUnique(size_type b, Node* node) { + GOOGLE_DCHECK(index_of_first_non_null_ == num_buckets_ || + table_[index_of_first_non_null_] != NULL); + // In practice, the code that led to this point may have already + // determined whether we are inserting into an empty list, a short list, + // or whatever. But it's probably cheap enough to recompute that here; + // it's likely that we're inserting into an empty or short list. + iterator result; + GOOGLE_DCHECK(find(*KeyPtrFromNodePtr(node)) == end()); + if (TableEntryIsEmpty(b)) { + result = InsertUniqueInList(b, node); + } else if (TableEntryIsNonEmptyList(b)) { + if (GOOGLE_PREDICT_FALSE(TableEntryIsTooLong(b))) { + TreeConvert(b); + result = InsertUniqueInTree(b, node); + GOOGLE_DCHECK_EQ(result.bucket_index_, b & ~static_cast<size_type>(1)); + } else { + // Insert into a pre-existing list. This case cannot modify + // index_of_first_non_null_, so we skip the code to update it. + return InsertUniqueInList(b, node); + } + } else { + // Insert into a pre-existing tree. This case cannot modify + // index_of_first_non_null_, so we skip the code to update it. + return InsertUniqueInTree(b, node); + } + index_of_first_non_null_ = + std::min(index_of_first_non_null_, result.bucket_index_); + return result; + } + + // Helper for InsertUnique. Handles the case where bucket b is a + // not-too-long linked list. + iterator InsertUniqueInList(size_type b, Node* node) { + node->next = static_cast<Node*>(table_[b]); + table_[b] = static_cast<void*>(node); + return iterator(node, this, b); + } + + // Helper for InsertUnique. Handles the case where bucket b points to a + // Tree. + iterator InsertUniqueInTree(size_type b, Node* node) { + GOOGLE_DCHECK_EQ(table_[b], table_[b ^ 1]); + // Maintain the invariant that node->next is NULL for all Nodes in Trees. + node->next = NULL; + return iterator(static_cast<Tree*>(table_[b]) + ->insert(KeyPtrFromNodePtr(node)) + .first, + this, b & ~static_cast<size_t>(1)); + } + + // Returns whether it did resize. Currently this is only used when + // num_elements_ increases, though it could be used in other situations. + // It checks for load too low as well as load too high: because any number + // of erases can occur between inserts, the load could be as low as 0 here. + // Resizing to a lower size is not always helpful, but failing to do so can + // destroy the expected big-O bounds for some operations. By having the + // policy that sometimes we resize down as well as up, clients can easily + // keep O(size()) = O(number of buckets) if they want that. + bool ResizeIfLoadIsOutOfRange(size_type new_size) { + const size_type kMaxMapLoadTimes16 = 12; // controls RAM vs CPU tradeoff + const size_type hi_cutoff = num_buckets_ * kMaxMapLoadTimes16 / 16; + const size_type lo_cutoff = hi_cutoff / 4; + // We don't care how many elements are in trees. If a lot are, + // we may resize even though there are many empty buckets. In + // practice, this seems fine. + if (GOOGLE_PREDICT_FALSE(new_size >= hi_cutoff)) { + if (num_buckets_ <= max_size() / 2) { + Resize(num_buckets_ * 2); + return true; + } + } else if (GOOGLE_PREDICT_FALSE(new_size <= lo_cutoff && + num_buckets_ > kMinTableSize)) { + size_type lg2_of_size_reduction_factor = 1; + // It's possible we want to shrink a lot here... size() could even be 0. + // So, estimate how much to shrink by making sure we don't shrink so + // much that we would need to grow the table after a few inserts. + const size_type hypothetical_size = new_size * 5 / 4 + 1; + while ((hypothetical_size << lg2_of_size_reduction_factor) < + hi_cutoff) { + ++lg2_of_size_reduction_factor; + } + size_type new_num_buckets = std::max<size_type>( + kMinTableSize, num_buckets_ >> lg2_of_size_reduction_factor); + if (new_num_buckets != num_buckets_) { + Resize(new_num_buckets); + return true; + } + } + return false; + } + + // Resize to the given number of buckets. + void Resize(size_t new_num_buckets) { + GOOGLE_DCHECK_GE(new_num_buckets, kMinTableSize); + void** const old_table = table_; + const size_type old_table_size = num_buckets_; + num_buckets_ = new_num_buckets; + table_ = CreateEmptyTable(num_buckets_); + const size_type start = index_of_first_non_null_; + index_of_first_non_null_ = num_buckets_; + for (size_type i = start; i < old_table_size; i++) { + if (TableEntryIsNonEmptyList(old_table, i)) { + TransferList(old_table, i); + } else if (TableEntryIsTree(old_table, i)) { + TransferTree(old_table, i++); + } + } + Dealloc<void*>(old_table, old_table_size); + } + + void TransferList(void* const* table, size_type index) { + Node* node = static_cast<Node*>(table[index]); + do { + Node* next = node->next; + InsertUnique(BucketNumber(*KeyPtrFromNodePtr(node)), node); + node = next; + } while (node != NULL); + } + + void TransferTree(void* const* table, size_type index) { + Tree* tree = static_cast<Tree*>(table[index]); + typename Tree::iterator tree_it = tree->begin(); + do { + Node* node = NodePtrFromKeyPtr(*tree_it); + InsertUnique(BucketNumber(**tree_it), node); + } while (++tree_it != tree->end()); + DestroyTree(tree); + } + + Node* EraseFromLinkedList(Node* item, Node* head) { + if (head == item) { + return head->next; + } else { + head->next = EraseFromLinkedList(item, head->next); + return head; + } + } + + bool TableEntryIsEmpty(size_type b) const { + return TableEntryIsEmpty(table_, b); + } + bool TableEntryIsNonEmptyList(size_type b) const { + return TableEntryIsNonEmptyList(table_, b); + } + bool TableEntryIsTree(size_type b) const { + return TableEntryIsTree(table_, b); + } + bool TableEntryIsList(size_type b) const { + return TableEntryIsList(table_, b); + } + static bool TableEntryIsEmpty(void* const* table, size_type b) { + return table[b] == NULL; + } + static bool TableEntryIsNonEmptyList(void* const* table, size_type b) { + return table[b] != NULL && table[b] != table[b ^ 1]; + } + static bool TableEntryIsTree(void* const* table, size_type b) { + return !TableEntryIsEmpty(table, b) && + !TableEntryIsNonEmptyList(table, b); + } + static bool TableEntryIsList(void* const* table, size_type b) { + return !TableEntryIsTree(table, b); + } + + void TreeConvert(size_type b) { + GOOGLE_DCHECK(!TableEntryIsTree(b) && !TableEntryIsTree(b ^ 1)); + typename Allocator::template rebind<Tree>::other tree_allocator(alloc_); + Tree* tree = tree_allocator.allocate(1); + // We want to use the three-arg form of construct, if it exists, but we + // create a temporary and use the two-arg construct that's known to exist. + // It's clunky, but the compiler should be able to generate more-or-less + // the same code. + tree_allocator.construct(tree, + Tree(KeyCompare(), KeyPtrAllocator(alloc_))); + // Now the tree is ready to use. + size_type count = CopyListToTree(b, tree) + CopyListToTree(b ^ 1, tree); + GOOGLE_DCHECK_EQ(count, tree->size()); + table_[b] = table_[b ^ 1] = static_cast<void*>(tree); + } + + // Copy a linked list in the given bucket to a tree. + // Returns the number of things it copied. + size_type CopyListToTree(size_type b, Tree* tree) { + size_type count = 0; + Node* node = static_cast<Node*>(table_[b]); + while (node != NULL) { + tree->insert(KeyPtrFromNodePtr(node)); + ++count; + Node* next = node->next; + node->next = NULL; + node = next; + } + return count; + } + + // Return whether table_[b] is a linked list that seems awfully long. + // Requires table_[b] to point to a non-empty linked list. + bool TableEntryIsTooLong(size_type b) { + const size_type kMaxLength = 8; + size_type count = 0; + Node* node = static_cast<Node*>(table_[b]); + do { + ++count; + node = node->next; + } while (node != NULL); + // Invariant: no linked list ever is more than kMaxLength in length. + GOOGLE_DCHECK_LE(count, kMaxLength); + return count >= kMaxLength; + } + + size_type BucketNumber(const Key& k) const { + // We inherit from hasher, so one-arg operator() provides a hash function. + size_type h = (*const_cast<InnerMap*>(this))(k); + // To help prevent people from making assumptions about the hash function, + // we use the seed differently depending on NDEBUG. The default hash + // function, the seeding, etc., are all likely to change in the future. +#ifndef NDEBUG + return (h * (seed_ | 1)) & (num_buckets_ - 1); +#else + return (h + seed_) & (num_buckets_ - 1); +#endif + } + + bool IsMatch(const Key& k0, const Key& k1) const { + return std::equal_to<Key>()(k0, k1); + } + + // Return a power of two no less than max(kMinTableSize, n). + // Assumes either n < kMinTableSize or n is a power of two. + size_type TableSize(size_type n) { + return n < kMinTableSize ? kMinTableSize : n; + } + + // Use alloc_ to allocate an array of n objects of type U. + template <typename U> + U* Alloc(size_type n) { + typedef typename Allocator::template rebind<U>::other alloc_type; + return alloc_type(alloc_).allocate(n); + } + + // Use alloc_ to deallocate an array of n objects of type U. + template <typename U> + void Dealloc(U* t, size_type n) { + typedef typename Allocator::template rebind<U>::other alloc_type; + alloc_type(alloc_).deallocate(t, n); + } + + void DestroyNode(Node* node) { + alloc_.destroy(&node->kv); + Dealloc<Node>(node, 1); + } + + void DestroyTree(Tree* tree) { + typename Allocator::template rebind<Tree>::other tree_allocator(alloc_); + tree_allocator.destroy(tree); + tree_allocator.deallocate(tree, 1); + } + + void** CreateEmptyTable(size_type n) { + GOOGLE_DCHECK(n >= kMinTableSize); + GOOGLE_DCHECK_EQ(n & (n - 1), 0); + void** result = Alloc<void*>(n); + memset(result, 0, n * sizeof(result[0])); + return result; + } + + // Return a randomish value. + size_type Seed() const { + // random_device can throw, so avoid it unless we are compiling with + // exceptions enabled. +#if __cpp_exceptions && LANG_CXX11 + try { + std::random_device rd; + std::knuth_b knuth(rd()); + std::uniform_int_distribution<size_type> u; + return u(knuth); + } catch (...) { } +#endif + size_type s = static_cast<size_type>(reinterpret_cast<uintptr_t>(this)); +#if defined(__x86_64__) && defined(__GNUC__) + uint32 hi, lo; + asm("rdtsc" : "=a" (lo), "=d" (hi)); + s += ((static_cast<uint64>(hi) << 32) | lo); +#endif + return s; + } + + size_type num_elements_; + size_type num_buckets_; + size_type seed_; + size_type index_of_first_non_null_; + void** table_; // an array with num_buckets_ entries + Allocator alloc_; + GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(InnerMap); + }; // end of class InnerMap + + typedef hash_map<Key, value_type*, hash<Key>, equal_to<Key>, + MapAllocator<std::pair<const Key, MapPair<Key, T>*> > > + DeprecatedInnerMap; + + public: + // Iterators + class iterator_base { + public: + // We support "old style" and "new style" iterators for now. This is + // temporary. Also, for "iterator()" we have an unknown category. + // TODO(gpike): get rid of this. + enum IteratorStyle { kUnknown, kOld, kNew }; + explicit iterator_base(IteratorStyle style) : iterator_style_(style) {} + + bool OldStyle() const { + GOOGLE_DCHECK_NE(iterator_style_, kUnknown); + return iterator_style_ == kOld; + } + bool UnknownStyle() const { + return iterator_style_ == kUnknown; + } + bool SameStyle(const iterator_base& other) const { + return iterator_style_ == other.iterator_style_; + } + + private: + IteratorStyle iterator_style_; + }; + + class const_iterator + : private iterator_base, + public std::iterator<std::forward_iterator_tag, value_type, ptrdiff_t, + const value_type*, const value_type&> { + typedef typename InnerMap::const_iterator InnerIt; + typedef typename DeprecatedInnerMap::const_iterator DeprecatedInnerIt; + + public: + const_iterator() : iterator_base(iterator_base::kUnknown) {} + explicit const_iterator(const DeprecatedInnerIt& dit) + : iterator_base(iterator_base::kOld), dit_(dit) {} + explicit const_iterator(const InnerIt& it) + : iterator_base(iterator_base::kNew), it_(it) {} + + const_iterator(const const_iterator& other) + : iterator_base(other), it_(other.it_), dit_(other.dit_) {} + + const_reference operator*() const { + return this->OldStyle() ? *dit_->second : *it_->value(); + } + const_pointer operator->() const { return &(operator*()); } + + const_iterator& operator++() { + if (this->OldStyle()) + ++dit_; + else + ++it_; + return *this; + } + const_iterator operator++(int) { + return this->OldStyle() ? const_iterator(dit_++) : const_iterator(it_++); + } + + friend bool operator==(const const_iterator& a, const const_iterator& b) { + if (!a.SameStyle(b)) return false; + if (a.UnknownStyle()) return true; + return a.OldStyle() ? (a.dit_ == b.dit_) : (a.it_ == b.it_); + } + friend bool operator!=(const const_iterator& a, const const_iterator& b) { + return !(a == b); + } + + private: + InnerIt it_; + DeprecatedInnerIt dit_; + }; + + class iterator : private iterator_base, + public std::iterator<std::forward_iterator_tag, value_type> { + typedef typename InnerMap::iterator InnerIt; + typedef typename DeprecatedInnerMap::iterator DeprecatedInnerIt; + + public: + iterator() : iterator_base(iterator_base::kUnknown) {} + explicit iterator(const DeprecatedInnerIt& dit) + : iterator_base(iterator_base::kOld), dit_(dit) {} + explicit iterator(const InnerIt& it) + : iterator_base(iterator_base::kNew), it_(it) {} + + reference operator*() const { + return this->OldStyle() ? *dit_->second : *it_->value(); + } + pointer operator->() const { return &(operator*()); } + + iterator& operator++() { + if (this->OldStyle()) + ++dit_; + else + ++it_; + return *this; + } + iterator operator++(int) { + return this->OldStyle() ? iterator(dit_++) : iterator(it_++); + } + + // Allow implicit conversion to const_iterator. + operator const_iterator() const { + return this->OldStyle() ? + const_iterator(typename DeprecatedInnerMap::const_iterator(dit_)) : + const_iterator(typename InnerMap::const_iterator(it_)); + } + + friend bool operator==(const iterator& a, const iterator& b) { + if (!a.SameStyle(b)) return false; + if (a.UnknownStyle()) return true; + return a.OldStyle() ? a.dit_ == b.dit_ : a.it_ == b.it_; + } + friend bool operator!=(const iterator& a, const iterator& b) { + return !(a == b); + } + + private: + friend class Map; + + InnerIt it_; + DeprecatedInnerIt dit_; + }; + + iterator begin() { + return old_style_ ? iterator(deprecated_elements_->begin()) + : iterator(elements_->begin()); + } + iterator end() { + return old_style_ ? iterator(deprecated_elements_->end()) + : iterator(elements_->end()); + } + const_iterator begin() const { + return old_style_ ? const_iterator(deprecated_elements_->begin()) + : const_iterator(iterator(elements_->begin())); + } + const_iterator end() const { + return old_style_ ? const_iterator(deprecated_elements_->end()) + : const_iterator(iterator(elements_->end())); + } + const_iterator cbegin() const { return begin(); } + const_iterator cend() const { return end(); } + + // Capacity + size_type size() const { + return old_style_ ? deprecated_elements_->size() : elements_->size(); + } + bool empty() const { return size() == 0; } + + // Element access + T& operator[](const key_type& key) { + value_type** value = + old_style_ ? &(*deprecated_elements_)[key] : &(*elements_)[key]; + if (*value == NULL) { + *value = CreateValueTypeInternal(key); + internal::MapValueInitializer<google::protobuf::is_proto_enum<T>::value, + T>::Initialize((*value)->second, + default_enum_value_); + } + return (*value)->second; + } + const T& at(const key_type& key) const { + const_iterator it = find(key); + GOOGLE_CHECK(it != end()); + return it->second; + } + T& at(const key_type& key) { + iterator it = find(key); + GOOGLE_CHECK(it != end()); + return it->second; + } + + // Lookup + size_type count(const key_type& key) const { + if (find(key) != end()) assert(key == find(key)->first); + return find(key) == end() ? 0 : 1; + } + const_iterator find(const key_type& key) const { + return old_style_ ? const_iterator(deprecated_elements_->find(key)) + : const_iterator(iterator(elements_->find(key))); + } + iterator find(const key_type& key) { + return old_style_ ? iterator(deprecated_elements_->find(key)) + : iterator(elements_->find(key)); + } + std::pair<const_iterator, const_iterator> equal_range( + const key_type& key) const { + const_iterator it = find(key); + if (it == end()) { + return std::pair<const_iterator, const_iterator>(it, it); + } else { + const_iterator begin = it++; + return std::pair<const_iterator, const_iterator>(begin, it); + } + } + std::pair<iterator, iterator> equal_range(const key_type& key) { + iterator it = find(key); + if (it == end()) { + return std::pair<iterator, iterator>(it, it); + } else { + iterator begin = it++; + return std::pair<iterator, iterator>(begin, it); + } + } + + // insert + std::pair<iterator, bool> insert(const value_type& value) { + if (old_style_) { + iterator it = find(value.first); + if (it != end()) { + return std::pair<iterator, bool>(it, false); + } else { + return std::pair<iterator, bool>( + iterator(deprecated_elements_->insert(std::pair<Key, value_type*>( + value.first, CreateValueTypeInternal(value))).first), true); + } + } else { + std::pair<typename InnerMap::iterator, bool> p = + elements_->insert(value.first); + if (p.second) { + p.first->value() = CreateValueTypeInternal(value); + } + return std::pair<iterator, bool>(iterator(p.first), p.second); + } + } + template <class InputIt> + void insert(InputIt first, InputIt last) { + for (InputIt it = first; it != last; ++it) { + iterator exist_it = find(it->first); + if (exist_it == end()) { + operator[](it->first) = it->second; + } + } + } + + // Erase and clear + size_type erase(const key_type& key) { + iterator it = find(key); + if (it == end()) { + return 0; + } else { + erase(it); + return 1; + } + } + iterator erase(iterator pos) { + if (arena_ == NULL) delete pos.operator->(); + iterator i = pos++; + if (old_style_) + deprecated_elements_->erase(i.dit_); + else + elements_->erase(i.it_); + return pos; + } + void erase(iterator first, iterator last) { + while (first != last) { + first = erase(first); + } + } + void clear() { erase(begin(), end()); } + + // Assign + Map& operator=(const Map& other) { + if (this != &other) { + clear(); + insert(other.begin(), other.end()); + } + return *this; + } + + void swap(Map& other) { + if (arena_ == other.arena_ && old_style_ == other.old_style_) { + std::swap(default_enum_value_, other.default_enum_value_); + if (old_style_) { + std::swap(deprecated_elements_, other.deprecated_elements_); + } else { + std::swap(elements_, other.elements_); + } + } else { + // TODO(zuguang): optimize this. The temporary copy can be allocated + // in the same arena as the other message, and the "other = copy" can + // be replaced with the fast-path swap above. + Map copy = *this; + *this = other; + other = copy; + } + } + + // Access to hasher. Currently this returns a copy, but it may + // be modified to return a const reference in the future. + hasher hash_function() const { + return old_style_ ? deprecated_elements_->hash_function() + : elements_->hash_function(); + } + + private: + // Set default enum value only for proto2 map field whose value is enum type. + void SetDefaultEnumValue(int default_enum_value) { + default_enum_value_ = default_enum_value; + } + + value_type* CreateValueTypeInternal(const Key& key) { + if (arena_ == NULL) { + return new value_type(key); + } else { + value_type* value = reinterpret_cast<value_type*>( + Arena::CreateArray<uint8>(arena_, sizeof(value_type))); + Arena::CreateInArenaStorage(const_cast<Key*>(&value->first), arena_); + Arena::CreateInArenaStorage(&value->second, arena_); + const_cast<Key&>(value->first) = key; + return value; + } + } + + value_type* CreateValueTypeInternal(const value_type& value) { + if (arena_ == NULL) { + return new value_type(value); + } else { + value_type* p = reinterpret_cast<value_type*>( + Arena::CreateArray<uint8>(arena_, sizeof(value_type))); + Arena::CreateInArenaStorage(const_cast<Key*>(&p->first), arena_); + Arena::CreateInArenaStorage(&p->second, arena_); + const_cast<Key&>(p->first) = value.first; + p->second = value.second; + return p; + } + } + + Arena* arena_; + int default_enum_value_; + // The following is a tagged union because we support two map styles + // for now. + // TODO(gpike): get rid of the old style. + const bool old_style_; + union { + InnerMap* elements_; + DeprecatedInnerMap* deprecated_elements_; + }; + + friend class ::google::protobuf::Arena; + typedef void InternalArenaConstructable_; + typedef void DestructorSkippable_; + template <typename K, typename V, + internal::WireFormatLite::FieldType key_wire_type, + internal::WireFormatLite::FieldType value_wire_type, + int default_enum_value> + friend class internal::MapFieldLite; +}; + +} // namespace protobuf +} // namespace google + +GOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_START +template<> +struct hash<google::protobuf::MapKey> { + size_t + operator()(const google::protobuf::MapKey& map_key) const { + switch (map_key.type()) { + case google::protobuf::FieldDescriptor::CPPTYPE_DOUBLE: + case google::protobuf::FieldDescriptor::CPPTYPE_FLOAT: + case google::protobuf::FieldDescriptor::CPPTYPE_ENUM: + case google::protobuf::FieldDescriptor::CPPTYPE_MESSAGE: + GOOGLE_LOG(FATAL) << "Unsupported"; + break; + case google::protobuf::FieldDescriptor::CPPTYPE_STRING: + return hash<string>()(map_key.GetStringValue()); + case google::protobuf::FieldDescriptor::CPPTYPE_INT64: + return hash< ::google::protobuf::int64>()(map_key.GetInt64Value()); + case google::protobuf::FieldDescriptor::CPPTYPE_INT32: + return hash< ::google::protobuf::int32>()(map_key.GetInt32Value()); + case google::protobuf::FieldDescriptor::CPPTYPE_UINT64: + return hash< ::google::protobuf::uint64>()(map_key.GetUInt64Value()); + case google::protobuf::FieldDescriptor::CPPTYPE_UINT32: + return hash< ::google::protobuf::uint32>()(map_key.GetUInt32Value()); + case google::protobuf::FieldDescriptor::CPPTYPE_BOOL: + return hash<bool>()(map_key.GetBoolValue()); + } + GOOGLE_LOG(FATAL) << "Can't get here."; + return 0; + } + bool + operator()(const google::protobuf::MapKey& map_key1, + const google::protobuf::MapKey& map_key2) const { + return map_key1 < map_key2; + } +}; +GOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_END + +#endif // GOOGLE_PROTOBUF_MAP_H__ |