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

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