summaryrefslogtreecommitdiff
path: root/absl/container/internal
diff options
context:
space:
mode:
authorGravatar Evan Brown <ezb@google.com>2022-06-06 11:02:03 -0700
committerGravatar Copybara-Service <copybara-worker@google.com>2022-06-06 11:02:59 -0700
commitef034836d3bfcaff018593014f14a3ebc264cc81 (patch)
treee0408329dea54f3fa09a9b25c9b94d222b49e5ab /absl/container/internal
parent6481443560a92d0a3a55a31807de0cd712cd4f88 (diff)
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
Diffstat (limited to 'absl/container/internal')
-rw-r--r--absl/container/internal/btree.h40
-rw-r--r--absl/container/internal/container_memory.h27
2 files changed, 20 insertions, 47 deletions
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<P>::operator=(btree &&other) noexcept -> btree & {
template <typename P>
auto btree<P>::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 <class Allocator>
- 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<Allocator>::destroy(*alloc, &a->value);
- absl::allocator_traits<Allocator>::construct(*alloc, &a->value,
- std::move(b->value));
- absl::allocator_traits<Allocator>::destroy(*alloc, &b->value);
- absl::allocator_traits<Allocator>::construct(*alloc, &b->value,
- std::move(tmp));
- }
- }
-
- template <class Allocator>
- 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<Allocator>::destroy(*alloc, &dest->value);
- absl::allocator_traits<Allocator>::construct(*alloc, &dest->value,
- std::move(src->value));
- }
- }
};
} // namespace container_internal