aboutsummaryrefslogtreecommitdiff
path: root/src/google/protobuf/map.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/google/protobuf/map.h')
-rw-r--r--src/google/protobuf/map.h1082
1 files changed, 951 insertions, 131 deletions
diff --git a/src/google/protobuf/map.h b/src/google/protobuf/map.h
index dfc62420..a182abe6 100644
--- a/src/google/protobuf/map.h
+++ b/src/google/protobuf/map.h
@@ -31,9 +31,11 @@
#ifndef GOOGLE_PROTOBUF_MAP_H__
#define GOOGLE_PROTOBUF_MAP_H__
-#include <iterator>
#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>
@@ -41,17 +43,23 @@
#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;
-template <typename Enum> struct is_proto_enum;
-
class MapIterator;
+template <typename Enum> struct is_proto_enum;
+
namespace internal {
template <typename Key, typename T,
WireFormatLite::FieldType key_wire_type,
@@ -73,15 +81,15 @@ 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()); \
+#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
@@ -166,11 +174,47 @@ class LIBPROTOBUF_EXPORT MapKey {
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_) {
- return false;
+ // 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:
@@ -183,11 +227,6 @@ class LIBPROTOBUF_EXPORT MapKey {
return val_.uint32_value_ == other.val_.uint32_value_;
case FieldDescriptor::CPPTYPE_BOOL:
return val_.bool_value_ == other.val_.bool_value_;
- case FieldDescriptor::CPPTYPE_DOUBLE:
- case FieldDescriptor::CPPTYPE_FLOAT:
- case FieldDescriptor::CPPTYPE_ENUM:
- case FieldDescriptor::CPPTYPE_MESSAGE:
- GOOGLE_LOG(FATAL) << "Can't get here.";
}
GOOGLE_LOG(FATAL) << "Can't get here.";
return false;
@@ -196,6 +235,12 @@ class LIBPROTOBUF_EXPORT MapKey {
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;
@@ -214,12 +259,6 @@ class LIBPROTOBUF_EXPORT MapKey {
case FieldDescriptor::CPPTYPE_BOOL:
val_.bool_value_ = other.val_.bool_value_;
break;
- case FieldDescriptor::CPPTYPE_DOUBLE:
- case FieldDescriptor::CPPTYPE_FLOAT:
- case FieldDescriptor::CPPTYPE_ENUM:
- case FieldDescriptor::CPPTYPE_MESSAGE:
- GOOGLE_LOG(FATAL) << "Can't get here.";
- break;
}
}
@@ -457,8 +496,17 @@ class MapPair {
};
// google::protobuf::Map is an associative container type used to store protobuf map
-// fields. Its interface is similar to std::unordered_map. Users should use this
-// interface directly to visit or change map fields.
+// 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. Mutations to a Map do not invalidate
+// a Map's iterators, pointers to elements, or references to elements. Except
+// for erase(iterator), any non-const method can reorder iterators.
template <typename Key, typename T>
class Map {
public:
@@ -473,40 +521,56 @@ class Map {
typedef size_t size_type;
typedef hash<Key> hasher;
- typedef equal_to<Key> key_equal;
- Map()
+ Map(bool old_style = true)
: arena_(NULL),
- allocator_(arena_),
- elements_(0, hasher(), key_equal(), allocator_),
- default_enum_value_(0) {}
- explicit Map(Arena* arena)
+ default_enum_value_(0),
+ old_style_(old_style) {
+ Init();
+ }
+ explicit Map(Arena* arena, bool old_style = true)
: arena_(arena),
- allocator_(arena_),
- elements_(0, hasher(), key_equal(), allocator_),
- default_enum_value_(0) {
- arena_->OwnDestructor(&elements_);
+ default_enum_value_(0),
+ old_style_(old_style) {
+ Init();
}
-
Map(const Map& other)
: arena_(NULL),
- allocator_(arena_),
- elements_(0, hasher(), key_equal(), allocator_),
- default_enum_value_(other.default_enum_value_) {
+ 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)
+ Map(const InputIt& first, const InputIt& last, bool old_style = true)
: arena_(NULL),
- allocator_(arena_),
- elements_(0, hasher(), key_equal(), allocator_),
- default_enum_value_(0) {
+ default_enum_value_(0),
+ old_style_(old_style) {
+ Init();
insert(first, last);
}
- ~Map() { clear(); }
+ ~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.
@@ -544,8 +608,8 @@ class Map {
}
}
-#if __cplusplus >= 201103L && !defined(GOOGLE_PROTOBUF_OS_APPLE) && \
- !defined(GOOGLE_PROTOBUF_OS_NACL) && !defined(GOOGLE_PROTOBUF_OS_ANDROID)
+#if __cplusplus >= 201103L && !defined(GOOGLE_PROTOBUF_OS_APPLE) && \
+ !defined(GOOGLE_PROTOBUF_OS_NACL) && !defined(GOOGLE_PROTOBUF_OS_ANDROID)
template<class NodeType, class... Args>
void construct(NodeType* p, Args&&... args) {
new (static_cast<void*>(p)) NodeType(std::forward<Args>(args)...);
@@ -589,86 +653,837 @@ class Map {
friend class MapAllocator;
};
- typedef MapAllocator<std::pair<const Key, MapPair<Key, T>*> > Allocator;
- typedef hash_map<Key, value_type*, hash<Key>, equal_to<Key>, Allocator>
- InnerMap;
+ // 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 LIBPROTOBUF_EXPORT 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 LIBPROTOBUF_EXPORT 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) {
+ 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(table_) >= 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();
+ const 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()) {
+ 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_] == 0) {
+ ++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) {
+ // 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);
+ } else {
+ result = InsertUniqueInList(b, node);
+ }
+ } else {
+ result = 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_ = 0;
+ 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] == 0;
+ }
+ static bool TableEntryIsNonEmptyList(void* const* table, size_type b) {
+ return table[b] != 0 && 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 int 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 = (*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 LIBPROTOBUF_EXPORT 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
- : public std::iterator<std::forward_iterator_tag, value_type, ptrdiff_t,
+ : 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() {}
- explicit const_iterator(const InnerIt& it) : it_(it) {}
+ 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_reference operator*() const { return *it_->second; }
- const_pointer operator->() const { return it_->second; }
+ 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++() {
- ++it_;
+ if (this->OldStyle())
+ ++dit_;
+ else
+ ++it_;
return *this;
}
- const_iterator operator++(int) { return const_iterator(it_++); }
+ const_iterator operator++(int) {
+ return this->OldStyle() ? const_iterator(dit_++) : const_iterator(it_++);
+ }
friend bool operator==(const const_iterator& a, const const_iterator& b) {
- return a.it_ == b.it_;
+ 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.it_ != b.it_;
+ return !(a == b);
}
private:
InnerIt it_;
+ DeprecatedInnerIt dit_;
};
- class iterator : public std::iterator<std::forward_iterator_tag, value_type> {
+ 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() {}
- explicit iterator(const InnerIt& it) : it_(it) {}
-
- reference operator*() const { return *it_->second; }
- pointer operator->() const { return it_->second; }
+ 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++() {
- ++it_;
+ if (this->OldStyle())
+ ++dit_;
+ else
+ ++it_;
return *this;
}
- iterator operator++(int) { return iterator(it_++); }
+ iterator operator++(int) {
+ return this->OldStyle() ? iterator(dit_++) : iterator(it_++);
+ }
- // Implicitly convertible to const_iterator.
- operator const_iterator() const { return const_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) {
- return a.it_ == b.it_;
+ 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.it_ != b.it_;
+ return !(a == b);
}
private:
friend class Map;
+
InnerIt it_;
+ DeprecatedInnerIt dit_;
};
- iterator begin() { return iterator(elements_.begin()); }
- iterator end() { return iterator(elements_.end()); }
- const_iterator begin() const { return const_iterator(elements_.begin()); }
- const_iterator end() const { return const_iterator(elements_.end()); }
+ 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 elements_.size(); }
- bool empty() const { return elements_.empty(); }
+ 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 = &elements_[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,
@@ -690,13 +1505,16 @@ class Map {
// Lookup
size_type count(const key_type& key) const {
- return elements_.count(key);
+ if (find(key) != end()) assert(key == find(key)->first);
+ return find(key) == end() ? 0 : 1;
}
const_iterator find(const key_type& key) const {
- return const_iterator(elements_.find(key));
+ return old_style_ ? const_iterator(deprecated_elements_->find(key))
+ : const_iterator(iterator(elements_->find(key)));
}
iterator find(const key_type& key) {
- return iterator(elements_.find(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 {
@@ -720,13 +1538,22 @@ class Map {
// insert
std::pair<iterator, bool> insert(const value_type& value) {
- iterator it = find(value.first);
- if (it != end()) {
- return std::pair<iterator, bool>(it, false);
+ 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 {
- return std::pair<iterator, bool>(
- iterator(elements_.insert(std::pair<Key, value_type*>(
- value.first, CreateValueTypeInternal(value))).first), true);
+ 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>
@@ -739,33 +1566,31 @@ class Map {
}
}
- // Erase
+ // Erase and clear
size_type erase(const key_type& key) {
- typename InnerMap::iterator it = elements_.find(key);
- if (it == elements_.end()) {
+ iterator it = find(key);
+ if (it == end()) {
return 0;
} else {
- if (arena_ == NULL) delete it->second;
- elements_.erase(it);
+ erase(it);
return 1;
}
}
- void erase(iterator pos) {
- if (arena_ == NULL) delete pos.it_->second;
- elements_.erase(pos.it_);
+ 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) {
- for (iterator it = first; it != last;) {
- if (arena_ == NULL) delete it.it_->second;
- elements_.erase((it++).it_);
+ while (first != last) {
+ first = erase(first);
}
}
- void clear() {
- for (iterator it = begin(); it != end(); ++it) {
- if (arena_ == NULL) delete it.it_->second;
- }
- elements_.clear();
- }
+ void clear() { erase(begin(), end()); }
// Assign
Map& operator=(const Map& other) {
@@ -776,6 +1601,13 @@ class Map {
return *this;
}
+ // 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) {
@@ -810,9 +1642,15 @@ class Map {
}
Arena* arena_;
- Allocator allocator_;
- InnerMap elements_;
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_;
@@ -833,6 +1671,12 @@ 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:
@@ -845,11 +1689,6 @@ struct hash<google::protobuf::MapKey> {
return hash< ::google::protobuf::uint32>()(map_key.GetUInt32Value());
case google::protobuf::FieldDescriptor::CPPTYPE_BOOL:
return hash<bool>()(map_key.GetBoolValue());
- 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) << "Can't get here.";
}
GOOGLE_LOG(FATAL) << "Can't get here.";
return 0;
@@ -857,26 +1696,7 @@ struct hash<google::protobuf::MapKey> {
bool
operator()(const google::protobuf::MapKey& map_key1,
const google::protobuf::MapKey& map_key2) const {
- switch (map_key1.type()) {
-#define COMPARE_CPPTYPE(CPPTYPE, CPPTYPE_METHOD) \
- case google::protobuf::FieldDescriptor::CPPTYPE_##CPPTYPE: \
- return map_key1.Get##CPPTYPE_METHOD##Value() < \
- map_key2.Get##CPPTYPE_METHOD##Value();
- COMPARE_CPPTYPE(STRING, String)
- COMPARE_CPPTYPE(INT64, Int64)
- COMPARE_CPPTYPE(INT32, Int32)
- COMPARE_CPPTYPE(UINT64, UInt64)
- COMPARE_CPPTYPE(UINT32, UInt32)
- COMPARE_CPPTYPE(BOOL, Bool)
-#undef COMPARE_CPPTYPE
- 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) << "Can't get here.";
- }
- GOOGLE_LOG(FATAL) << "Can't get here.";
- return true;
+ return map_key1 < map_key2;
}
};
GOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_END
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-23 12:50:53 +0000