about summary refs log tree commit diff
path: root/absl/container
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container')
-rw-r--r--absl/container/BUILD.bazel2
-rw-r--r--absl/container/fixed_array_test.cc17
-rw-r--r--absl/container/inlined_vector_test.cc19
-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
8 files changed, 189 insertions, 137 deletions
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel
index acdbc473d961..f3b3a2c0b42f 100644
--- a/absl/container/BUILD.bazel
+++ b/absl/container/BUILD.bazel
@@ -542,6 +542,7 @@ cc_library(
     copts = ABSL_DEFAULT_COPTS,
     deps = [
         "//absl/meta:type_traits",
+        "//absl/types:optional",
     ],
 )
 
@@ -565,7 +566,6 @@ cc_library(
         "//absl/base:endian",
         "//absl/memory",
         "//absl/meta:type_traits",
-        "//absl/types:optional",
         "//absl/utility",
     ],
 )
diff --git a/absl/container/fixed_array_test.cc b/absl/container/fixed_array_test.cc
index 205ff41fe114..1679ba4f65db 100644
--- a/absl/container/fixed_array_test.cc
+++ b/absl/container/fixed_array_test.cc
@@ -869,4 +869,21 @@ TEST(FixedArrayTest, AddressSanitizerAnnotations4) {
 }
 #endif  // ADDRESS_SANITIZER
 
+TEST(FixedArrayTest, AbslHashValueWorks) {
+  using V = absl::FixedArray<int>;
+  std::vector<V> cases;
+
+  // Generate a variety of vectors some of these are small enough for the inline
+  // space but are stored out of line.
+  for (int i = 0; i < 10; ++i) {
+    V v(i);
+    for (int j = 0; j < i; ++j) {
+      v[j] = j;
+    }
+    cases.push_back(v);
+  }
+
+  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(cases));
+}
+
 }  // namespace
diff --git a/absl/container/inlined_vector_test.cc b/absl/container/inlined_vector_test.cc
index 9408ee9dd5b4..5b1527e90b16 100644
--- a/absl/container/inlined_vector_test.cc
+++ b/absl/container/inlined_vector_test.cc
@@ -1762,4 +1762,23 @@ TEST(AllocatorSupportTest, SizeAllocConstructor) {
   }
 }
 
+TEST(InlinedVectorTest, AbslHashValueWorks) {
+  using V = absl::InlinedVector<int, 4>;
+  std::vector<V> cases;
+
+  // Generate a variety of vectors some of these are small enough for the inline
+  // space but are stored out of line.
+  for (int i = 0; i < 10; ++i) {
+    V v;
+    for (int j = 0; j < i; ++j) {
+      v.push_back(j);
+    }
+    cases.push_back(v);
+    v.resize(i % 4);
+    cases.push_back(v);
+  }
+
+  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(cases));
+}
+
 }  // anonymous namespace
diff --git a/absl/container/internal/common.h b/absl/container/internal/common.h
index a6dc9103df01..c7816566533d 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 99cd8344ad2e..dc669248c301 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 126a0ade431e..8b81653a57f6 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 8e3fa02d7e42..a5d0cae00bfb 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 d9f1826a09ca..7adcc96d1d52 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);
generated by cgit-pink 1.4.1 (git 2.44.2) at 2024-11-14T17ยท30+0000