summaryrefslogtreecommitdiff
path: root/absl/container/internal
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2019-02-07 14:13:06 -0800
committerGravatar Shaindel Schwartz <shaindel@google.com>2019-02-07 17:48:22 -0500
commit2901ec32a919311384d6ad4194e2d927c06831f7 (patch)
treeeedb15fc3c7510d7580e4a6136bbf18734edfd8a /absl/container/internal
parentd78310fe5a82f2e0e6e16509ef8079c8d7e4674e (diff)
Export of internal Abseil changes.
-- 5da9755667df37e38ccaf6938c9f408e294110bb by Shaindel Schwartz <shaindel@google.com>: Import of CCTZ from GitHub. PiperOrigin-RevId: 232942734 -- b6fb275769c66fdd2bd92b119198c59e9a7dd737 by Samuel Benzaquen <sbenza@google.com>: Fix integral underflow when from-arg width is INT_MIN. PiperOrigin-RevId: 232888037 -- 4135dbba4a26c4642277fc2a7e2a833d593daa1c by Abseil Team <absl-team@google.com>: Add the insert_return_type alias to raw_hash_set. PiperOrigin-RevId: 232683892 -- 0b120b7d3693800bbb886f6fc607ae54a9338cb1 by Abseil Team <absl-team@google.com>: Macros to detect and disabled SafeStack https://clang.llvm.org/docs/SafeStack.html PiperOrigin-RevId: 232680114 -- a77b3fb533a9e37966d1d6ef5ccd09c73fff2ca1 by Abseil Team <absl-team@google.com>: Avoid potential red zone clobber Pushing on the stack on x86-64 may clobber local variables held below %rsp in the red zone. Avoid this by using lea on x86-64. PiperOrigin-RevId: 232592478 -- bf326a0eefa92f4e704287563df0c5a5b1873b6d by Eric Fiselier <ericwf@google.com>: Add additional tests for AbslHashValue. PiperOrigin-RevId: 232344325 -- 816e4f98fd7632c944c779db87b7dac4e138afcf by Eric Fiselier <ericwf@google.com>: Avoid upcoming GCC 9.0 warnings about base class init. Currently, in trunk, GCC has a new warning under -Wextra that diagnoses when a derived class fails to explicitly initialize the base class in a constructor initializer list. This patch avoids this warning. PiperOrigin-RevId: 232327626 -- 779c0f44b3c2b7a04d4bdf978641eb8180515bf6 by Eric Fiselier <ericwf@google.com>: Guard against C++2a char8_t change. PiperOrigin-RevId: 232326178 -- 41e5395b85bbbfb5bf418cc21b04ad4ccb15a284 by Eric Fiselier <ericwf@google.com>: Avoid Clang Warning PiperOrigin-RevId: 232138866 GitOrigin-RevId: 5da9755667df37e38ccaf6938c9f408e294110bb Change-Id: I49ee4f58db177b81b039d7d949f671c97c5a7933
Diffstat (limited to 'absl/container/internal')
-rw-r--r--absl/container/internal/common.h136
-rw-r--r--absl/container/internal/hashtablez_sampler.cc2
-rw-r--r--absl/container/internal/hashtablez_sampler.h12
-rw-r--r--absl/container/internal/raw_hash_set.h136
-rw-r--r--absl/container/internal/raw_hash_set_test.cc2
5 files changed, 152 insertions, 136 deletions
diff --git a/absl/container/internal/common.h b/absl/container/internal/common.h
index a6dc9103..c7816566 100644
--- a/absl/container/internal/common.h
+++ b/absl/container/internal/common.h
@@ -18,6 +18,7 @@
#include <type_traits>
#include "absl/meta/type_traits.h"
+#include "absl/types/optional.h"
namespace absl {
namespace container_internal {
@@ -42,7 +43,140 @@ struct KeyArg<false> {
using type = key_type;
};
+// The node_handle concept from C++17.
+// We specialize node_handle for sets and maps. node_handle_base holds the
+// common API of both.
+template <typename PolicyTraits, typename Alloc>
+class node_handle_base {
+ protected:
+ using slot_type = typename PolicyTraits::slot_type;
+
+ public:
+ using allocator_type = Alloc;
+
+ constexpr node_handle_base() {}
+ node_handle_base(node_handle_base&& other) noexcept {
+ *this = std::move(other);
+ }
+ ~node_handle_base() { destroy(); }
+ node_handle_base& operator=(node_handle_base&& other) noexcept {
+ destroy();
+ if (!other.empty()) {
+ alloc_ = other.alloc_;
+ PolicyTraits::transfer(alloc(), slot(), other.slot());
+ other.reset();
+ }
+ return *this;
+ }
+
+ bool empty() const noexcept { return !alloc_; }
+ explicit operator bool() const noexcept { return !empty(); }
+ allocator_type get_allocator() const { return *alloc_; }
+
+ protected:
+ friend struct CommonAccess;
+
+ node_handle_base(const allocator_type& a, slot_type* s) : alloc_(a) {
+ PolicyTraits::transfer(alloc(), slot(), s);
+ }
+
+ void destroy() {
+ if (!empty()) {
+ PolicyTraits::destroy(alloc(), slot());
+ reset();
+ }
+ }
+
+ void reset() {
+ assert(alloc_.has_value());
+ alloc_ = absl::nullopt;
+ }
+
+ slot_type* slot() const {
+ assert(!empty());
+ return reinterpret_cast<slot_type*>(std::addressof(slot_space_));
+ }
+ allocator_type* alloc() { return std::addressof(*alloc_); }
+
+ private:
+ absl::optional<allocator_type> alloc_;
+ mutable absl::aligned_storage_t<sizeof(slot_type), alignof(slot_type)>
+ slot_space_;
+};
+
+// For sets.
+template <typename Policy, typename PolicyTraits, typename Alloc,
+ typename = void>
+class node_handle : public node_handle_base<PolicyTraits, Alloc> {
+ using Base = typename node_handle::node_handle_base;
+
+ public:
+ using value_type = typename PolicyTraits::value_type;
+
+ constexpr node_handle() {}
+
+ value_type& value() const { return PolicyTraits::element(this->slot()); }
+
+ private:
+ friend struct CommonAccess;
+
+ node_handle(const Alloc& a, typename Base::slot_type* s) : Base(a, s) {}
+};
+
+// For maps.
+template <typename Policy, typename PolicyTraits, typename Alloc>
+class node_handle<Policy, PolicyTraits, Alloc,
+ absl::void_t<typename Policy::mapped_type>>
+ : public node_handle_base<PolicyTraits, Alloc> {
+ using Base = typename node_handle::node_handle_base;
+
+ public:
+ using key_type = typename Policy::key_type;
+ using mapped_type = typename Policy::mapped_type;
+
+ constexpr node_handle() {}
+
+ auto key() const -> decltype(PolicyTraits::key(this->slot())) {
+ return PolicyTraits::key(this->slot());
+ }
+
+ mapped_type& mapped() const {
+ return PolicyTraits::value(&PolicyTraits::element(this->slot()));
+ }
+
+ private:
+ friend struct CommonAccess;
+
+ node_handle(const Alloc& a, typename Base::slot_type* s) : Base(a, s) {}
+};
+
+// Provide access to non-public node-handle functions.
+struct CommonAccess {
+ template <typename Node>
+ static auto GetSlot(const Node& node) -> decltype(node.slot()) {
+ return node.slot();
+ }
+
+ template <typename Node>
+ static void Reset(Node* node) {
+ node->reset();
+ }
+
+ template <typename T, typename... Args>
+ static T Make(Args&&... args) {
+ return T(std::forward<Args>(args)...);
+ }
+};
+
+// Implement the insert_return_type<> concept of C++17.
+template <class Iterator, class NodeType>
+struct InsertReturnType {
+ Iterator position;
+ bool inserted;
+ NodeType node;
+};
+
} // namespace container_internal
-} // namespace absl
+} // namespace absl
#endif // ABSL_CONTAINER_INTERNAL_CONTAINER_H_
diff --git a/absl/container/internal/hashtablez_sampler.cc b/absl/container/internal/hashtablez_sampler.cc
index 99cd8344..dc669248 100644
--- a/absl/container/internal/hashtablez_sampler.cc
+++ b/absl/container/internal/hashtablez_sampler.cc
@@ -254,7 +254,7 @@ HashtablezInfo* SampleSlow(int64_t* next_sample) {
}
#if ABSL_PER_THREAD_TLS == 1
-ABSL_PER_THREAD_TLS_KEYWORD int64_t next_sample = 0;
+ABSL_PER_THREAD_TLS_KEYWORD int64_t global_next_sample = 0;
#endif // ABSL_PER_THREAD_TLS == 1
void UnsampleSlow(HashtablezInfo* info) {
diff --git a/absl/container/internal/hashtablez_sampler.h b/absl/container/internal/hashtablez_sampler.h
index 126a0ade..8b81653a 100644
--- a/absl/container/internal/hashtablez_sampler.h
+++ b/absl/container/internal/hashtablez_sampler.h
@@ -146,23 +146,23 @@ class HashtablezInfoHandle {
HashtablezInfo* info_;
};
-// Returns an RAII sampling handle that manages registration and unregistation
-// with the global sampler.
#if ABSL_PER_THREAD_TLS == 1
-extern ABSL_PER_THREAD_TLS_KEYWORD int64_t next_sample;
+extern ABSL_PER_THREAD_TLS_KEYWORD int64_t global_next_sample;
#endif // ABSL_PER_THREAD_TLS
+// Returns an RAII sampling handle that manages registration and unregistation
+// with the global sampler.
inline HashtablezInfoHandle Sample() {
#if ABSL_PER_THREAD_TLS == 0
static auto* mu = new absl::Mutex;
- static int64_t next_sample = 0;
+ static int64_t global_next_sample = 0;
absl::MutexLock l(mu);
#endif // !ABSL_HAVE_THREAD_LOCAL
- if (ABSL_PREDICT_TRUE(--next_sample > 0)) {
+ if (ABSL_PREDICT_TRUE(--global_next_sample > 0)) {
return HashtablezInfoHandle(nullptr);
}
- return HashtablezInfoHandle(SampleSlow(&next_sample));
+ return HashtablezInfoHandle(SampleSlow(&global_next_sample));
}
// Holds samples and their associated stack traces with a soft limit of
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index 8e3fa02d..a5d0cae0 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -115,7 +115,6 @@
#include "absl/container/internal/layout.h"
#include "absl/memory/memory.h"
#include "absl/meta/type_traits.h"
-#include "absl/types/optional.h"
#include "absl/utility/utility.h"
namespace absl {
@@ -502,126 +501,6 @@ inline size_t GrowthToLowerboundCapacity(size_t growth) {
return growth + static_cast<size_t>((static_cast<int64_t>(growth) - 1) / 7);
}
-// The node_handle concept from C++17.
-// We specialize node_handle for sets and maps. node_handle_base holds the
-// common API of both.
-template <typename Policy, typename Alloc>
-class node_handle_base {
- protected:
- using PolicyTraits = hash_policy_traits<Policy>;
- using slot_type = typename PolicyTraits::slot_type;
-
- public:
- using allocator_type = Alloc;
-
- constexpr node_handle_base() {}
- node_handle_base(node_handle_base&& other) noexcept {
- *this = std::move(other);
- }
- ~node_handle_base() { destroy(); }
- node_handle_base& operator=(node_handle_base&& other) {
- destroy();
- if (!other.empty()) {
- alloc_ = other.alloc_;
- PolicyTraits::transfer(alloc(), slot(), other.slot());
- other.reset();
- }
- return *this;
- }
-
- bool empty() const noexcept { return !alloc_; }
- explicit operator bool() const noexcept { return !empty(); }
- allocator_type get_allocator() const { return *alloc_; }
-
- protected:
- template <typename, typename, typename, typename>
- friend class raw_hash_set;
-
- node_handle_base(const allocator_type& a, slot_type* s) : alloc_(a) {
- PolicyTraits::transfer(alloc(), slot(), s);
- }
-
- void destroy() {
- if (!empty()) {
- PolicyTraits::destroy(alloc(), slot());
- reset();
- }
- }
-
- void reset() {
- assert(alloc_.has_value());
- alloc_ = absl::nullopt;
- }
-
- slot_type* slot() const {
- assert(!empty());
- return reinterpret_cast<slot_type*>(std::addressof(slot_space_));
- }
- allocator_type* alloc() { return std::addressof(*alloc_); }
-
- private:
- absl::optional<allocator_type> alloc_;
- mutable absl::aligned_storage_t<sizeof(slot_type), alignof(slot_type)>
- slot_space_;
-};
-
-// For sets.
-template <typename Policy, typename Alloc, typename = void>
-class node_handle : public node_handle_base<Policy, Alloc> {
- using Base = typename node_handle::node_handle_base;
-
- public:
- using value_type = typename Base::PolicyTraits::value_type;
-
- constexpr node_handle() {}
-
- value_type& value() const {
- return Base::PolicyTraits::element(this->slot());
- }
-
- private:
- template <typename, typename, typename, typename>
- friend class raw_hash_set;
-
- node_handle(const Alloc& a, typename Base::slot_type* s) : Base(a, s) {}
-};
-
-// For maps.
-template <typename Policy, typename Alloc>
-class node_handle<Policy, Alloc, absl::void_t<typename Policy::mapped_type>>
- : public node_handle_base<Policy, Alloc> {
- using Base = typename node_handle::node_handle_base;
-
- public:
- using key_type = typename Policy::key_type;
- using mapped_type = typename Policy::mapped_type;
-
- constexpr node_handle() {}
-
- auto key() const -> decltype(Base::PolicyTraits::key(this->slot())) {
- return Base::PolicyTraits::key(this->slot());
- }
-
- mapped_type& mapped() const {
- return Base::PolicyTraits::value(
- &Base::PolicyTraits::element(this->slot()));
- }
-
- private:
- template <typename, typename, typename, typename>
- friend class raw_hash_set;
-
- node_handle(const Alloc& a, typename Base::slot_type* s) : Base(a, s) {}
-};
-
-// Implement the insert_return_type<> concept of C++17.
-template <class Iterator, class NodeType>
-struct insert_return_type {
- Iterator position;
- bool inserted;
- NodeType node;
-};
-
// Policy: a policy defines how to perform different operations on
// the slots of the hashtable (see hash_policy_traits.h for the full interface
// of policy).
@@ -828,7 +707,8 @@ class raw_hash_set {
iterator inner_;
};
- using node_type = container_internal::node_handle<Policy, Alloc>;
+ using node_type = node_handle<Policy, hash_policy_traits<Policy>, Alloc>;
+ using insert_return_type = InsertReturnType<iterator, node_type>;
raw_hash_set() noexcept(
std::is_nothrow_default_constructible<hasher>::value&&
@@ -1136,13 +1016,14 @@ class raw_hash_set {
insert(ilist.begin(), ilist.end());
}
- insert_return_type<iterator, node_type> insert(node_type&& node) {
+ insert_return_type insert(node_type&& node) {
if (!node) return {end(), false, node_type()};
- const auto& elem = PolicyTraits::element(node.slot());
+ const auto& elem = PolicyTraits::element(CommonAccess::GetSlot(node));
auto res = PolicyTraits::apply(
- InsertSlot<false>{*this, std::move(*node.slot())}, elem);
+ InsertSlot<false>{*this, std::move(*CommonAccess::GetSlot(node))},
+ elem);
if (res.second) {
- node.reset();
+ CommonAccess::Reset(&node);
return {res.first, true, node_type()};
} else {
return {res.first, false, std::move(node)};
@@ -1306,7 +1187,8 @@ class raw_hash_set {
}
node_type extract(const_iterator position) {
- node_type node(alloc_ref(), position.inner_.slot_);
+ auto node =
+ CommonAccess::Make<node_type>(alloc_ref(), position.inner_.slot_);
erase_meta_only(position);
return node;
}
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
index d9f1826a..7adcc96d 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -1706,7 +1706,7 @@ TEST(Nodes, ExtractInsert) {
EXPECT_FALSE(node.empty());
StringTable t2;
- auto res = t2.insert(std::move(node));
+ StringTable::insert_return_type res = t2.insert(std::move(node));
EXPECT_TRUE(res.inserted);
EXPECT_THAT(*res.position, Pair(k0, ""));
EXPECT_FALSE(res.node);