From ef034836d3bfcaff018593014f14a3ebc264cc81 Mon Sep 17 00:00:00 2001 From: Evan Brown Date: Mon, 6 Jun 2022 11:02:03 -0700 Subject: In b-tree, support unassignable value types. Avoid using value move/swap and delete those functions from slot_policy types. There was only one use of params_type::move in `erase`. PiperOrigin-RevId: 453237739 Change-Id: Ie81c6dba6c4db34e97a067d2c0defcded8044a5a --- absl/container/btree_set.h | 11 ------ absl/container/btree_test.cc | 60 ++++++++++++++++++++++++++++++ absl/container/internal/btree.h | 40 ++++++++++---------- absl/container/internal/container_memory.h | 27 -------------- 4 files changed, 80 insertions(+), 58 deletions(-) diff --git a/absl/container/btree_set.h b/absl/container/btree_set.h index 32a7c506..695b09f5 100644 --- a/absl/container/btree_set.h +++ b/absl/container/btree_set.h @@ -766,17 +766,6 @@ struct set_slot_policy { construct(alloc, new_slot, old_slot); destroy(alloc, old_slot); } - - template - static void swap(Alloc * /*alloc*/, slot_type *a, slot_type *b) { - using std::swap; - swap(*a, *b); - } - - template - static void move(Alloc * /*alloc*/, slot_type *src, slot_type *dest) { - *dest = std::move(*src); - } }; // A parameters structure for holding the type parameters for a btree_set. diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc index b3fa98f4..f20f3430 100644 --- a/absl/container/btree_test.cc +++ b/absl/container/btree_test.cc @@ -3188,6 +3188,66 @@ TEST(Btree, OnlyConstructibleByAllocatorType) { } } +class NotAssignable { + public: + explicit NotAssignable(int i) : i_(i) {} + NotAssignable(const NotAssignable &other) : i_(other.i_) {} + NotAssignable &operator=(NotAssignable &&other) = delete; + int Get() const { return i_; } + bool operator==(int i) const { return i_ == i; } + friend bool operator<(NotAssignable a, NotAssignable b) { + return a.i_ < b.i_; + } + + private: + int i_; +}; + +TEST(Btree, NotAssignableType) { + { + absl::btree_set set; + set.emplace(1); + set.emplace_hint(set.end(), 2); + set.insert(NotAssignable(3)); + set.insert(set.end(), NotAssignable(4)); + EXPECT_THAT(set, ElementsAre(1, 2, 3, 4)); + set.erase(set.begin()); + EXPECT_THAT(set, ElementsAre(2, 3, 4)); + } + { + absl::btree_multiset set; + set.emplace(1); + set.emplace_hint(set.end(), 2); + set.insert(NotAssignable(2)); + set.insert(set.end(), NotAssignable(3)); + EXPECT_THAT(set, ElementsAre(1, 2, 2, 3)); + set.erase(set.begin()); + EXPECT_THAT(set, ElementsAre(2, 2, 3)); + } + { + absl::btree_map map; + map.emplace(NotAssignable(1), 1); + map.emplace_hint(map.end(), NotAssignable(2), 2); + map.insert({NotAssignable(3), 3}); + map.insert(map.end(), {NotAssignable(4), 4}); + EXPECT_THAT(map, + ElementsAre(Pair(1, 1), Pair(2, 2), Pair(3, 3), Pair(4, 4))); + map.erase(map.begin()); + EXPECT_THAT(map, ElementsAre(Pair(2, 2), Pair(3, 3), Pair(4, 4))); + } + { + absl::btree_multimap map; + map.emplace(NotAssignable(1), 1); + map.emplace_hint(map.end(), NotAssignable(2), 2); + map.insert({NotAssignable(2), 3}); + map.insert(map.end(), {NotAssignable(3), 3}); + EXPECT_THAT(map, + ElementsAre(Pair(1, 1), Pair(2, 2), Pair(2, 3), Pair(3, 3))); + map.erase(map.begin()); + EXPECT_THAT(map, ElementsAre(Pair(2, 2), Pair(2, 3), Pair(3, 3))); + } +} + } // namespace } // namespace container_internal ABSL_NAMESPACE_END diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h index 1ff2e6e7..01f4e749 100644 --- a/absl/container/internal/btree.h +++ b/absl/container/internal/btree.h @@ -462,12 +462,6 @@ struct common_params { static void transfer(Alloc *alloc, slot_type *new_slot, slot_type *old_slot) { slot_policy::transfer(alloc, new_slot, old_slot); } - static void swap(Alloc *alloc, slot_type *a, slot_type *b) { - slot_policy::swap(alloc, a, b); - } - static void move(Alloc *alloc, slot_type *src, slot_type *dest) { - slot_policy::move(alloc, src, dest); - } }; // An adapter class that converts a lower-bound compare into an upper-bound @@ -2300,23 +2294,29 @@ auto btree

::operator=(btree &&other) noexcept -> btree & { template auto btree

::erase(iterator iter) -> iterator { - bool internal_delete = false; - if (iter.node_->is_internal()) { - // Deletion of a value on an internal node. First, move the largest value - // from our left child here, then delete that position (in remove_values() - // below). We can get to the largest value from our left child by - // decrementing iter. + iter.node_->value_destroy(iter.position_, mutable_allocator()); + iter.update_generation(); + + const bool internal_delete = iter.node_->is_internal(); + if (internal_delete) { + // Deletion of a value on an internal node. First, transfer the largest + // value from our left child here, then erase/rebalance from that position. + // We can get to the largest value from our left child by decrementing iter. iterator internal_iter(iter); --iter; assert(iter.node_->is_leaf()); - params_type::move(mutable_allocator(), iter.node_->slot(iter.position_), - internal_iter.node_->slot(internal_iter.position_)); - internal_delete = true; - } - - // Delete the key from the leaf. - iter.node_->remove_values(iter.position_, /*to_erase=*/1, - mutable_allocator()); + internal_iter.node_->transfer(internal_iter.position_, iter.position_, + iter.node_, mutable_allocator()); + } else { + // Shift values after erased position in leaf. In the internal case, we + // don't need to do this because the leaf position is the end of the node. + const field_type transfer_from = iter.position_ + 1; + const field_type num_to_transfer = iter.node_->finish() - transfer_from; + iter.node_->transfer_n(num_to_transfer, iter.position_, transfer_from, + iter.node_, mutable_allocator()); + } + // Update node finish and container size. + iter.node_->set_finish(iter.node_->finish() - 1); --size_; // We want to return the next value after the one we just erased. If we diff --git a/absl/container/internal/container_memory.h b/absl/container/internal/container_memory.h index 94185c6e..00e9f6d7 100644 --- a/absl/container/internal/container_memory.h +++ b/absl/container/internal/container_memory.h @@ -433,33 +433,6 @@ struct map_slot_policy { } destroy(alloc, old_slot); } - - template - static void swap(Allocator* alloc, slot_type* a, slot_type* b) { - if (kMutableKeys::value) { - using std::swap; - swap(a->mutable_value, b->mutable_value); - } else { - value_type tmp = std::move(a->value); - absl::allocator_traits::destroy(*alloc, &a->value); - absl::allocator_traits::construct(*alloc, &a->value, - std::move(b->value)); - absl::allocator_traits::destroy(*alloc, &b->value); - absl::allocator_traits::construct(*alloc, &b->value, - std::move(tmp)); - } - } - - template - static void move(Allocator* alloc, slot_type* src, slot_type* dest) { - if (kMutableKeys::value) { - dest->mutable_value = std::move(src->mutable_value); - } else { - absl::allocator_traits::destroy(*alloc, &dest->value); - absl::allocator_traits::construct(*alloc, &dest->value, - std::move(src->value)); - } - } }; } // namespace container_internal -- cgit v1.2.3