summaryrefslogtreecommitdiff
path: root/absl/container
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2019-11-26 09:00:19 -0800
committerGravatar Gennadiy Rozental <rogeeff@google.com>2019-11-26 12:37:42 -0500
commit0514227d2547793b23e209809276375e41c76617 (patch)
treef2cfabd8a93bf4308eb62cad6e672d821bca0725 /absl/container
parent7f4fe64af80fe3c84db8ea938276c3690573c45e (diff)
Export of internal Abseil changes
-- 2ba0e41a21fbdab36b2f4f3b0dd4b112bd788604 by Derek Mauro <dmauro@google.com>: Remove the include of <intsafe.h>, which is missing on some versions of MinGW. DWORD is easily replaced by uint32_t. PiperOrigin-RevId: 282576177 -- 238fd41114b3e83fcb91d2afe1e6dcce7cfd53b0 by Samuel Benzaquen <sbenza@google.com>: Remove assertion in erase(iterator) that tries to use the comparator. Add missing this-> qualifier. Fix bug where node elements are not being destroyed properly. PiperOrigin-RevId: 282427096 -- 6b9446e3b38ed97451c010933e86a572ab659ab2 by Derek Mauro <dmauro@google.com>: Improves/fixes feature detection in thread_identity Only use ABSL_PER_THREAD_TLS_KEYWORD when it is supported (previously on some platforms it evaluated to nothing, which completely breaks everything), but prefer it to thread_local since benchmarks indicate it is slightly faster in this critical code path. Disable the calls to pthread_sigmask on MinGW where it is not supported. PiperOrigin-RevId: 282425291 GitOrigin-RevId: 2ba0e41a21fbdab36b2f4f3b0dd4b112bd788604 Change-Id: I34073ecbb4a43ad71f54161c136d88fc728888f1
Diffstat (limited to 'absl/container')
-rw-r--r--absl/container/btree_test.cc90
-rw-r--r--absl/container/internal/btree.h1
-rw-r--r--absl/container/internal/btree_container.h36
-rw-r--r--absl/container/internal/common.h5
4 files changed, 95 insertions, 37 deletions
diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index 48f70cb0..ea73f032 100644
--- a/absl/container/btree_test.cc
+++ b/absl/container/btree_test.cc
@@ -45,6 +45,7 @@ namespace absl {
namespace container_internal {
namespace {
+using ::absl::test_internal::CopyableMovableInstance;
using ::absl::test_internal::InstanceTracker;
using ::absl::test_internal::MovableOnlyInstance;
using ::testing::ElementsAre;
@@ -1823,25 +1824,80 @@ TEST(Btree, ExtractAndInsertNodeHandleSet) {
EXPECT_EQ(res.node.value(), 3);
}
-struct Deref {
- bool operator()(const std::unique_ptr<int> &lhs,
- const std::unique_ptr<int> &rhs) const {
- return *lhs < *rhs;
+template <typename Set>
+void TestExtractWithTrackingForSet() {
+ InstanceTracker tracker;
+ {
+ Set s;
+ // Add enough elements to make sure we test internal nodes too.
+ const size_t kSize = 1000;
+ while (s.size() < kSize) {
+ s.insert(MovableOnlyInstance(s.size()));
+ }
+ for (int i = 0; i < kSize; ++i) {
+ // Extract with key
+ auto nh = s.extract(MovableOnlyInstance(i));
+ EXPECT_EQ(s.size(), kSize - 1);
+ EXPECT_EQ(nh.value().value(), i);
+ // Insert with node
+ s.insert(std::move(nh));
+ EXPECT_EQ(s.size(), kSize);
+
+ // Extract with iterator
+ auto it = s.find(MovableOnlyInstance(i));
+ nh = s.extract(it);
+ EXPECT_EQ(s.size(), kSize - 1);
+ EXPECT_EQ(nh.value().value(), i);
+ // Insert with node and hint
+ s.insert(s.begin(), std::move(nh));
+ EXPECT_EQ(s.size(), kSize);
+ }
}
-};
+ EXPECT_EQ(0, tracker.instances());
+}
+
+template <typename Map>
+void TestExtractWithTrackingForMap() {
+ InstanceTracker tracker;
+ {
+ Map m;
+ // Add enough elements to make sure we test internal nodes too.
+ const size_t kSize = 1000;
+ while (m.size() < kSize) {
+ m.insert(
+ {CopyableMovableInstance(m.size()), MovableOnlyInstance(m.size())});
+ }
+ for (int i = 0; i < kSize; ++i) {
+ // Extract with key
+ auto nh = m.extract(CopyableMovableInstance(i));
+ EXPECT_EQ(m.size(), kSize - 1);
+ EXPECT_EQ(nh.key().value(), i);
+ EXPECT_EQ(nh.mapped().value(), i);
+ // Insert with node
+ m.insert(std::move(nh));
+ EXPECT_EQ(m.size(), kSize);
+
+ // Extract with iterator
+ auto it = m.find(CopyableMovableInstance(i));
+ nh = m.extract(it);
+ EXPECT_EQ(m.size(), kSize - 1);
+ EXPECT_EQ(nh.key().value(), i);
+ EXPECT_EQ(nh.mapped().value(), i);
+ // Insert with node and hint
+ m.insert(m.begin(), std::move(nh));
+ EXPECT_EQ(m.size(), kSize);
+ }
+ }
+ EXPECT_EQ(0, tracker.instances());
+}
-TEST(Btree, ExtractWithUniquePtr) {
- absl::btree_set<std::unique_ptr<int>, Deref> s;
- s.insert(absl::make_unique<int>(1));
- s.insert(absl::make_unique<int>(2));
- s.insert(absl::make_unique<int>(3));
- s.insert(absl::make_unique<int>(4));
- s.insert(absl::make_unique<int>(5));
- auto nh = s.extract(s.find(absl::make_unique<int>(3)));
- EXPECT_EQ(s.size(), 4);
- EXPECT_EQ(*nh.value(), 3);
- s.insert(std::move(nh));
- EXPECT_EQ(s.size(), 5);
+TEST(Btree, ExtractTracking) {
+ TestExtractWithTrackingForSet<absl::btree_set<MovableOnlyInstance>>();
+ TestExtractWithTrackingForSet<absl::btree_multiset<MovableOnlyInstance>>();
+ TestExtractWithTrackingForMap<
+ absl::btree_map<CopyableMovableInstance, MovableOnlyInstance>>();
+ TestExtractWithTrackingForMap<
+ absl::btree_multimap<CopyableMovableInstance, MovableOnlyInstance>>();
}
TEST(Btree, ExtractAndInsertNodeHandleMultiSet) {
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index cf7ef02c..40217dd5 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -2031,7 +2031,6 @@ auto btree<P>::erase(iterator iter) -> iterator {
iterator internal_iter(iter);
--iter;
assert(iter.node->leaf());
- assert(!compare_keys(internal_iter.key(), iter.key()));
params_type::move(mutable_allocator(), iter.node->slot(iter.position),
internal_iter.node->slot(internal_iter.position));
internal_delete = true;
diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h
index 726861d5..774412d9 100644
--- a/absl/container/internal/btree_container.h
+++ b/absl/container/internal/btree_container.h
@@ -296,9 +296,10 @@ class btree_set_container : public btree_container<Tree> {
insert_return_type insert(node_type &&node) {
if (!node) return {this->end(), false, node_type()};
std::pair<iterator, bool> res =
- insert(std::move(params_type::element(CommonAccess::GetSlot(node))));
+ this->tree_.insert_unique(params_type::key(CommonAccess::GetSlot(node)),
+ CommonAccess::GetSlot(node));
if (res.second) {
- CommonAccess::Reset(&node);
+ CommonAccess::Destroy(&node);
return {res.first, true, node_type()};
} else {
return {res.first, false, std::move(node)};
@@ -308,8 +309,8 @@ class btree_set_container : public btree_container<Tree> {
if (!node) return this->end();
std::pair<iterator, bool> res = this->tree_.insert_hint_unique(
iterator(hint), params_type::key(CommonAccess::GetSlot(node)),
- std::move(params_type::element(CommonAccess::GetSlot(node))));
- if (res.second) CommonAccess::Reset(&node);
+ CommonAccess::GetSlot(node));
+ if (res.second) CommonAccess::Destroy(&node);
return res.first;
}
@@ -323,7 +324,7 @@ class btree_set_container : public btree_container<Tree> {
// Node extraction routines.
template <typename K = key_type>
node_type extract(const key_arg<K> &key) {
- auto it = find(key);
+ auto it = this->find(key);
return it == this->end() ? node_type() : extract(it);
}
using super_type::extract;
@@ -523,24 +524,21 @@ class btree_multiset_container : public btree_container<Tree> {
return this->tree_.insert_hint_multi(
iterator(position), init_type(std::forward<Args>(args)...));
}
-
- private:
- template <typename... Args>
- iterator insert_node_helper(node_type &&node, Args &&... args) {
+ iterator insert(node_type &&node) {
if (!node) return this->end();
iterator res =
- insert(std::forward<Args>(args)...,
- std::move(params_type::element(CommonAccess::GetSlot(node))));
- CommonAccess::Reset(&node);
+ this->tree_.insert_multi(params_type::key(CommonAccess::GetSlot(node)),
+ CommonAccess::GetSlot(node));
+ CommonAccess::Destroy(&node);
return res;
}
-
- public:
- iterator insert(node_type &&node) {
- return insert_node_helper(std::move(node));
- }
iterator insert(const_iterator hint, node_type &&node) {
- return insert_node_helper(std::move(node), hint);
+ if (!node) return this->end();
+ iterator res = this->tree_.insert_hint_multi(
+ iterator(hint),
+ std::move(params_type::element(CommonAccess::GetSlot(node))));
+ CommonAccess::Destroy(&node);
+ return res;
}
// Deletion routines.
@@ -553,7 +551,7 @@ class btree_multiset_container : public btree_container<Tree> {
// Node extraction routines.
template <typename K = key_type>
node_type extract(const key_arg<K> &key) {
- auto it = find(key);
+ auto it = this->find(key);
return it == this->end() ? node_type() : extract(it);
}
using super_type::extract;
diff --git a/absl/container/internal/common.h b/absl/container/internal/common.h
index 4bd5d469..cc7633dc 100644
--- a/absl/container/internal/common.h
+++ b/absl/container/internal/common.h
@@ -167,6 +167,11 @@ struct CommonAccess {
}
template <typename Node>
+ static void Destroy(Node* node) {
+ node->destroy();
+ }
+
+ template <typename Node>
static void Reset(Node* node) {
node->reset();
}