summaryrefslogtreecommitdiff
path: root/absl/container
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container')
-rw-r--r--absl/container/btree_test.cc38
-rw-r--r--absl/container/internal/btree.h47
-rw-r--r--absl/container/internal/btree_container.h10
-rw-r--r--absl/container/internal/raw_hash_set.h14
4 files changed, 73 insertions, 36 deletions
diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index 464dabac..d5d79151 100644
--- a/absl/container/btree_test.cc
+++ b/absl/container/btree_test.cc
@@ -1708,10 +1708,25 @@ TEST(Btree, StrSplitCompatible) {
EXPECT_EQ(split_set, expected_set);
}
-// We can't use EXPECT_EQ/etc. to compare absl::weak_ordering because they
-// convert literal 0 to int and absl::weak_ordering can only be compared with
-// literal 0. Defining this function allows for avoiding ClangTidy warnings.
-bool Identity(const bool b) { return b; }
+TEST(Btree, KeyComp) {
+ absl::btree_set<int> s;
+ EXPECT_TRUE(s.key_comp()(1, 2));
+ EXPECT_FALSE(s.key_comp()(2, 2));
+ EXPECT_FALSE(s.key_comp()(2, 1));
+
+ absl::btree_map<int, int> m1;
+ EXPECT_TRUE(m1.key_comp()(1, 2));
+ EXPECT_FALSE(m1.key_comp()(2, 2));
+ EXPECT_FALSE(m1.key_comp()(2, 1));
+
+ // Even though we internally adapt the comparator of `m2` to be three-way and
+ // heterogeneous, the comparator we expose through key_comp() is the original
+ // unadapted comparator.
+ absl::btree_map<std::string, int> m2;
+ EXPECT_TRUE(m2.key_comp()("a", "b"));
+ EXPECT_FALSE(m2.key_comp()("b", "b"));
+ EXPECT_FALSE(m2.key_comp()("b", "a"));
+}
TEST(Btree, ValueComp) {
absl::btree_set<int> s;
@@ -1724,13 +1739,13 @@ TEST(Btree, ValueComp) {
EXPECT_FALSE(m1.value_comp()(std::make_pair(2, 0), std::make_pair(2, 0)));
EXPECT_FALSE(m1.value_comp()(std::make_pair(2, 0), std::make_pair(1, 0)));
+ // Even though we internally adapt the comparator of `m2` to be three-way and
+ // heterogeneous, the comparator we expose through value_comp() is based on
+ // the original unadapted comparator.
absl::btree_map<std::string, int> m2;
- EXPECT_TRUE(Identity(
- m2.value_comp()(std::make_pair("a", 0), std::make_pair("b", 0)) < 0));
- EXPECT_TRUE(Identity(
- m2.value_comp()(std::make_pair("b", 0), std::make_pair("b", 0)) == 0));
- EXPECT_TRUE(Identity(
- m2.value_comp()(std::make_pair("b", 0), std::make_pair("a", 0)) > 0));
+ EXPECT_TRUE(m2.value_comp()(std::make_pair("a", 0), std::make_pair("b", 0)));
+ EXPECT_FALSE(m2.value_comp()(std::make_pair("b", 0), std::make_pair("b", 0)));
+ EXPECT_FALSE(m2.value_comp()(std::make_pair("b", 0), std::make_pair("a", 0)));
}
TEST(Btree, DefaultConstruction) {
@@ -2906,8 +2921,7 @@ TEST(Btree, SupportsFunctionPtrComparator) {
map[1] = 1;
EXPECT_THAT(map, ElementsAre(Pair(1, 1)));
EXPECT_TRUE(map.key_comp()(1, 2));
- // TODO(ezb): support value_comp() in this case and uncomment.
- // EXPECT_TRUE(map.value_comp()(std::make_pair(1, 1), std::make_pair(2, 2)));
+ EXPECT_TRUE(map.value_comp()(std::make_pair(1, 1), std::make_pair(2, 2)));
}
template <typename Compare>
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index d372a1d6..f636c5fc 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -88,7 +88,12 @@ struct StringBtreeDefaultLess {
// Compatibility constructor.
StringBtreeDefaultLess(std::less<std::string>) {} // NOLINT
- StringBtreeDefaultLess(std::less<string_view>) {} // NOLINT
+ StringBtreeDefaultLess(std::less<absl::string_view>) {} // NOLINT
+
+ // Allow converting to std::less for use in key_comp()/value_comp().
+ explicit operator std::less<std::string>() const { return {}; }
+ explicit operator std::less<absl::string_view>() const { return {}; }
+ explicit operator std::less<absl::Cord>() const { return {}; }
absl::weak_ordering operator()(absl::string_view lhs,
absl::string_view rhs) const {
@@ -115,7 +120,12 @@ struct StringBtreeDefaultGreater {
StringBtreeDefaultGreater() = default;
StringBtreeDefaultGreater(std::greater<std::string>) {} // NOLINT
- StringBtreeDefaultGreater(std::greater<string_view>) {} // NOLINT
+ StringBtreeDefaultGreater(std::greater<absl::string_view>) {} // NOLINT
+
+ // Allow converting to std::greater for use in key_comp()/value_comp().
+ explicit operator std::greater<std::string>() const { return {}; }
+ explicit operator std::greater<absl::string_view>() const { return {}; }
+ explicit operator std::greater<absl::Cord>() const { return {}; }
absl::weak_ordering operator()(absl::string_view lhs,
absl::string_view rhs) const {
@@ -217,6 +227,8 @@ struct prefers_linear_node_search<
template <typename Key, typename Compare, typename Alloc, int TargetNodeSize,
bool Multi, typename SlotPolicy>
struct common_params {
+ using original_key_compare = Compare;
+
// If Compare is a common comparator for a string-like type, then we adapt it
// to use heterogeneous lookup and to be a key-compare-to comparator.
using key_compare = typename key_compare_to_adapter<Compare>::type;
@@ -317,16 +329,21 @@ struct map_params : common_params<Key, Compare, Alloc, TargetNodeSize, Multi,
using value_type = typename super_type::value_type;
using init_type = typename super_type::init_type;
- using key_compare = typename super_type::key_compare;
- // Inherit from key_compare for empty base class optimization.
- struct value_compare : private key_compare {
- value_compare() = default;
- explicit value_compare(const key_compare &cmp) : key_compare(cmp) {}
+ using original_key_compare = typename super_type::original_key_compare;
+ // Reference: https://en.cppreference.com/w/cpp/container/map/value_compare
+ class value_compare {
+ template <typename Params>
+ friend class btree;
- template <typename T, typename U>
- auto operator()(const T &left, const U &right) const
- -> decltype(std::declval<key_compare>()(left.first, right.first)) {
- return key_compare::operator()(left.first, right.first);
+ protected:
+ explicit value_compare(original_key_compare c) : comp(std::move(c)) {}
+
+ original_key_compare comp; // NOLINT
+
+ public:
+ auto operator()(const value_type &lhs, const value_type &rhs) const
+ -> decltype(comp(lhs.first, rhs.first)) {
+ return comp(lhs.first, rhs.first);
}
};
using is_map_container = std::true_type;
@@ -392,7 +409,8 @@ struct set_params : common_params<Key, Compare, Alloc, TargetNodeSize, Multi,
set_slot_policy<Key>> {
using value_type = Key;
using slot_type = typename set_params::common_params::slot_type;
- using value_compare = typename set_params::common_params::key_compare;
+ using value_compare =
+ typename set_params::common_params::original_key_compare;
using is_map_container = std::false_type;
template <typename V>
@@ -1129,6 +1147,7 @@ class btree {
using size_type = typename Params::size_type;
using difference_type = typename Params::difference_type;
using key_compare = typename Params::key_compare;
+ using original_key_compare = typename Params::original_key_compare;
using value_compare = typename Params::value_compare;
using allocator_type = typename Params::allocator_type;
using reference = typename Params::reference;
@@ -1338,7 +1357,9 @@ class btree {
return compare_internal::compare_result_as_less_than(key_comp()(a, b));
}
- value_compare value_comp() const { return value_compare(key_comp()); }
+ value_compare value_comp() const {
+ return value_compare(original_key_compare(key_comp()));
+ }
// Verifies the structure of the btree.
void verify() const;
diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h
index 03be708e..4f5d56dd 100644
--- a/absl/container/internal/btree_container.h
+++ b/absl/container/internal/btree_container.h
@@ -51,7 +51,7 @@ class btree_container {
using value_type = typename Tree::value_type;
using size_type = typename Tree::size_type;
using difference_type = typename Tree::difference_type;
- using key_compare = typename Tree::key_compare;
+ using key_compare = typename Tree::original_key_compare;
using value_compare = typename Tree::value_compare;
using allocator_type = typename Tree::allocator_type;
using reference = typename Tree::reference;
@@ -214,7 +214,7 @@ class btree_container {
allocator_type get_allocator() const { return tree_.get_allocator(); }
// The key comparator used by the btree.
- key_compare key_comp() const { return tree_.key_comp(); }
+ key_compare key_comp() const { return key_compare(tree_.key_comp()); }
value_compare value_comp() const { return tree_.value_comp(); }
// Support absl::Hash.
@@ -247,7 +247,7 @@ class btree_set_container : public btree_container<Tree> {
using key_type = typename Tree::key_type;
using value_type = typename Tree::value_type;
using size_type = typename Tree::size_type;
- using key_compare = typename Tree::key_compare;
+ using key_compare = typename Tree::original_key_compare;
using allocator_type = typename Tree::allocator_type;
using iterator = typename Tree::iterator;
using const_iterator = typename Tree::const_iterator;
@@ -398,7 +398,7 @@ class btree_map_container : public btree_set_container<Tree> {
using key_type = typename Tree::key_type;
using mapped_type = typename params_type::mapped_type;
using value_type = typename Tree::value_type;
- using key_compare = typename Tree::key_compare;
+ using key_compare = typename Tree::original_key_compare;
using allocator_type = typename Tree::allocator_type;
using iterator = typename Tree::iterator;
using const_iterator = typename Tree::const_iterator;
@@ -543,7 +543,7 @@ class btree_multiset_container : public btree_container<Tree> {
using key_type = typename Tree::key_type;
using value_type = typename Tree::value_type;
using size_type = typename Tree::size_type;
- using key_compare = typename Tree::key_compare;
+ using key_compare = typename Tree::original_key_compare;
using allocator_type = typename Tree::allocator_type;
using iterator = typename Tree::iterator;
using const_iterator = typename Tree::const_iterator;
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index b23e0078..669785e6 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -628,7 +628,9 @@ class raw_hash_set {
static Layout MakeLayout(size_t capacity) {
assert(IsValidCapacity(capacity));
- return Layout(capacity + Group::kWidth + 1, capacity);
+ // The extra control bytes are for 1 sentinel byte followed by
+ // `Group::kWidth - 1` bytes that are cloned from the beginning.
+ return Layout(capacity + Group::kWidth, capacity);
}
using AllocTraits = absl::allocator_traits<allocator_type>;
@@ -1782,8 +1784,8 @@ class raw_hash_set {
growth_left() = CapacityToGrowth(capacity()) - size_;
}
- // Sets the control byte, and if `i < Group::kWidth`, set the cloned byte at
- // the end too.
+ // Sets the control byte, and if `i < Group::kWidth - 1`, set the cloned byte
+ // at the end too.
void set_ctrl(size_t i, ctrl_t h) {
assert(i < capacity_);
@@ -1794,8 +1796,8 @@ class raw_hash_set {
}
ctrl_[i] = h;
- ctrl_[((i - Group::kWidth) & capacity_) + 1 +
- ((Group::kWidth - 1) & capacity_)] = h;
+ constexpr size_t kClonedBytes = Group::kWidth - 1;
+ ctrl_[((i - kClonedBytes) & capacity_) + (kClonedBytes & capacity_)] = h;
}
size_t& growth_left() { return settings_.template get<0>(); }
@@ -1814,7 +1816,7 @@ class raw_hash_set {
// TODO(alkis): Investigate removing some of these fields:
// - ctrl/slots can be derived from each other
// - size can be moved into the slot array
- ctrl_t* ctrl_ = EmptyGroup(); // [(capacity + 1) * ctrl_t]
+ ctrl_t* ctrl_ = EmptyGroup(); // [(capacity + Group::kWidth) * ctrl_t]
slot_type* slots_ = nullptr; // [capacity * slot_type]
size_t size_ = 0; // number of full slots
size_t capacity_ = 0; // total number of slots
generated by cgit v1.2.3 (git 2.39.1) at 2025-01-02 01:03:16 +0000