diff options
author | Jisi Liu <jisi.liu@gmail.com> | 2016-04-28 14:34:59 -0700 |
---|---|---|
committer | Jisi Liu <jisi.liu@gmail.com> | 2016-04-28 14:34:59 -0700 |
commit | cf14183bcd5485b4a71541599ddce0b35eb71352 (patch) | |
tree | 12f6e5eb731d7a70cdac4cdafc8b3131629413e2 /src/google/protobuf/map.h | |
parent | f00300d7f04f1c38a7d70e271f9232b94dd0e326 (diff) | |
download | protobuf-cf14183bcd5485b4a71541599ddce0b35eb71352.tar.gz protobuf-cf14183bcd5485b4a71541599ddce0b35eb71352.tar.bz2 protobuf-cf14183bcd5485b4a71541599ddce0b35eb71352.zip |
Down integrate from Google internal.
Diffstat (limited to 'src/google/protobuf/map.h')
-rw-r--r-- | src/google/protobuf/map.h | 41 |
1 files changed, 27 insertions, 14 deletions
diff --git a/src/google/protobuf/map.h b/src/google/protobuf/map.h index 023ed971..bb0b14f9 100644 --- a/src/google/protobuf/map.h +++ b/src/google/protobuf/map.h @@ -614,11 +614,12 @@ class Map { !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)...); + // 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> @@ -804,6 +805,8 @@ class Map { // 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_++) { @@ -989,7 +992,7 @@ class Map { 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_; + size_type b = it.bucket_index_; Node* const item = it.node_; if (is_list) { GOOGLE_DCHECK(TableEntryIsNonEmptyList(b)); @@ -1001,15 +1004,18 @@ class Map { 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; + 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) { + table_[index_of_first_non_null_] == NULL) { ++index_of_first_non_null_; } } @@ -1045,6 +1051,8 @@ class Map { // 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; @@ -1057,11 +1065,16 @@ class Map { 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 { - result = InsertUniqueInList(b, node); + // 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 { - result = InsertUniqueInTree(b, node); + // 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_); @@ -1137,7 +1150,7 @@ class Map { num_buckets_ = new_num_buckets; table_ = CreateEmptyTable(num_buckets_); const size_type start = index_of_first_non_null_; - index_of_first_non_null_ = 0; + 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); @@ -1189,10 +1202,10 @@ class Map { return TableEntryIsList(table_, b); } static bool TableEntryIsEmpty(void* const* table, size_type b) { - return table[b] == 0; + return table[b] == NULL; } static bool TableEntryIsNonEmptyList(void* const* table, size_type b) { - return table[b] != 0 && table[b] != table[b ^ 1]; + return table[b] != NULL && table[b] != table[b ^ 1]; } static bool TableEntryIsTree(void* const* table, size_type b) { return !TableEntryIsEmpty(table, b) && @@ -1250,7 +1263,7 @@ class Map { size_type BucketNumber(const Key& k) const { // We inherit from hasher, so one-arg operator() provides a hash function. - size_type h = (*this)(k); + 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. |