From 0514227d2547793b23e209809276375e41c76617 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Tue, 26 Nov 2019 09:00:19 -0800 Subject: Export of internal Abseil changes -- 2ba0e41a21fbdab36b2f4f3b0dd4b112bd788604 by Derek Mauro : Remove the include of , which is missing on some versions of MinGW. DWORD is easily replaced by uint32_t. PiperOrigin-RevId: 282576177 -- 238fd41114b3e83fcb91d2afe1e6dcce7cfd53b0 by Samuel Benzaquen : 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 : 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 --- absl/base/internal/sysinfo.cc | 2 +- absl/base/internal/sysinfo.h | 11 ++-- absl/base/internal/thread_identity.cc | 13 +++-- absl/base/internal/thread_identity.h | 9 +++- absl/container/btree_test.cc | 90 +++++++++++++++++++++++++------ absl/container/internal/btree.h | 1 - absl/container/internal/btree_container.h | 36 ++++++------- absl/container/internal/common.h | 5 ++ 8 files changed, 119 insertions(+), 48 deletions(-) diff --git a/absl/base/internal/sysinfo.cc b/absl/base/internal/sysinfo.cc index 4dd3add..93039bf 100644 --- a/absl/base/internal/sysinfo.cc +++ b/absl/base/internal/sysinfo.cc @@ -277,7 +277,7 @@ double NominalCPUFrequency() { #if defined(_WIN32) pid_t GetTID() { - return GetCurrentThreadId(); + return pid_t{GetCurrentThreadId()}; } #elif defined(__linux__) diff --git a/absl/base/internal/sysinfo.h b/absl/base/internal/sysinfo.h index b864a59..93356d8 100644 --- a/absl/base/internal/sysinfo.h +++ b/absl/base/internal/sysinfo.h @@ -26,10 +26,10 @@ #ifndef _WIN32 #include -#else -#include #endif +#include + #include "absl/base/port.h" namespace absl { @@ -51,9 +51,10 @@ int NumCPUs(); // On Linux, you may send a signal to the resulting ID with kill(). However, // it is recommended for portability that you use pthread_kill() instead. #ifdef _WIN32 -// On Windows, process id and thread id are of the same type according to -// the return types of GetProcessId() and GetThreadId() are both DWORD. -using pid_t = DWORD; +// On Windows, process id and thread id are of the same type according to the +// return types of GetProcessId() and GetThreadId() are both DWORD, an unsigned +// 32-bit type. +using pid_t = uint32_t; #endif pid_t GetTID(); diff --git a/absl/base/internal/thread_identity.cc b/absl/base/internal/thread_identity.cc index 91273a6..0ea159c 100644 --- a/absl/base/internal/thread_identity.cc +++ b/absl/base/internal/thread_identity.cc @@ -55,7 +55,12 @@ void AllocateThreadIdentityKey(ThreadIdentityReclaimerFunction reclaimer) { #ifdef __GNUC__ __attribute__((visibility("protected"))) #endif // __GNUC__ - ABSL_PER_THREAD_TLS_KEYWORD ThreadIdentity* thread_identity_ptr; +#if ABSL_PER_THREAD_TLS +// Prefer __thread to thread_local as benchmarks indicate it is a bit faster. +ABSL_PER_THREAD_TLS_KEYWORD ThreadIdentity* thread_identity_ptr = nullptr; +#elif defined(ABSL_HAVE_THREAD_LOCAL) +thread_local ThreadIdentity* thread_identity_ptr = nullptr; +#endif // ABSL_PER_THREAD_TLS #endif // TLS or CPP11 void SetCurrentThreadIdentity( @@ -69,8 +74,8 @@ void SetCurrentThreadIdentity( absl::call_once(init_thread_identity_key_once, AllocateThreadIdentityKey, reclaimer); -#ifdef __EMSCRIPTEN__ - // Emscripten PThread implementation does not support signals. +#if defined(__EMSCRIPTEN__) || defined(__MINGW32__) + // Emscripten and MinGW pthread implementations does not support signals. // See https://kripken.github.io/emscripten-site/docs/porting/pthreads.html // for more information. pthread_setspecific(thread_identity_pthread_key, @@ -89,7 +94,7 @@ void SetCurrentThreadIdentity( pthread_setspecific(thread_identity_pthread_key, reinterpret_cast(identity)); pthread_sigmask(SIG_SETMASK, &curr_signals, nullptr); -#endif // !__EMSCRIPTEN__ +#endif // !__EMSCRIPTEN__ && !__MINGW32__ #elif ABSL_THREAD_IDENTITY_MODE == ABSL_THREAD_IDENTITY_MODE_USE_TLS // NOTE: Not async-safe. But can be open-coded. diff --git a/absl/base/internal/thread_identity.h b/absl/base/internal/thread_identity.h index b34674a..7cbce9c 100644 --- a/absl/base/internal/thread_identity.h +++ b/absl/base/internal/thread_identity.h @@ -224,7 +224,14 @@ void ClearCurrentThreadIdentity(); #if ABSL_THREAD_IDENTITY_MODE == ABSL_THREAD_IDENTITY_MODE_USE_TLS || \ ABSL_THREAD_IDENTITY_MODE == ABSL_THREAD_IDENTITY_MODE_USE_CPP11 -extern ABSL_PER_THREAD_TLS_KEYWORD ThreadIdentity* thread_identity_ptr; +#if ABSL_PER_THREAD_TLS +ABSL_CONST_INIT extern ABSL_PER_THREAD_TLS_KEYWORD ThreadIdentity* + thread_identity_ptr; +#elif defined(ABSL_HAVE_THREAD_LOCAL) +ABSL_CONST_INIT extern thread_local ThreadIdentity* thread_identity_ptr; +#else +#error Thread-local storage not detected on this platform +#endif inline ThreadIdentity* CurrentThreadIdentityIfPresent() { return thread_identity_ptr; diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc index 48f70cb..ea73f03 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 &lhs, - const std::unique_ptr &rhs) const { - return *lhs < *rhs; +template +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 +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, Deref> s; - s.insert(absl::make_unique(1)); - s.insert(absl::make_unique(2)); - s.insert(absl::make_unique(3)); - s.insert(absl::make_unique(4)); - s.insert(absl::make_unique(5)); - auto nh = s.extract(s.find(absl::make_unique(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>(); + TestExtractWithTrackingForSet>(); + TestExtractWithTrackingForMap< + absl::btree_map>(); + TestExtractWithTrackingForMap< + absl::btree_multimap>(); } TEST(Btree, ExtractAndInsertNodeHandleMultiSet) { diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h index cf7ef02..40217dd 100644 --- a/absl/container/internal/btree.h +++ b/absl/container/internal/btree.h @@ -2031,7 +2031,6 @@ auto btree

::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 726861d..774412d 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 { insert_return_type insert(node_type &&node) { if (!node) return {this->end(), false, node_type()}; std::pair 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 { if (!node) return this->end(); std::pair 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 { // Node extraction routines. template node_type extract(const key_arg &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 { return this->tree_.insert_hint_multi( iterator(position), init_type(std::forward(args)...)); } - - private: - template - 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)..., - 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 { // Node extraction routines. template node_type extract(const key_arg &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 4bd5d46..cc7633d 100644 --- a/absl/container/internal/common.h +++ b/absl/container/internal/common.h @@ -166,6 +166,11 @@ struct CommonAccess { return node.slot(); } + template + static void Destroy(Node* node) { + node->destroy(); + } + template static void Reset(Node* node) { node->reset(); -- cgit v1.2.3