Squashed 'third_party/abseil_cpp/' changes from 768eb2ca2..ccdbb5941

ccdbb5941 Export of internal Abseil changes
01f5f81f9 Export of internal Abseil changes
2c92bdc7c Export of internal Abseil changes
e7ebf9803 Export of internal Abseil changes
2eba343b5 Export of internal Abseil changes
a8b03d90e Export of internal Abseil changes
1d31b5c36 Export of internal Abseil changes
da3a87690 Export of internal Abseil changes
8faf20461 Exclude empty directories (#697)
2069dc796 Export of internal Abseil changes
4832bf6bf Added a BUILD file in root to expose license. (#695)
af8f994af Export of internal Abseil changes
33caf1097 Export of internal Abseil changes
cf1a02e2d Export of internal Abseil changes

git-subtree-dir: third_party/abseil_cpp
git-subtree-split: ccdbb5941f992fabda7eae3ce72f55efc17c826a

1 files changed, 61 insertions, 90 deletions

diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index b23138f095..f52fe235a2 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -817,33 +817,52 @@ class btree_node {
     absl::container_internal::SanitizerPoisonObject(slot(i));
   }
 
-  // Transfers value from slot `src_i` in `src` to slot `dest_i` in `this`.
-  void transfer(const size_type dest_i, const size_type src_i, btree_node *src,
-                allocator_type *alloc) {
+  // Transfers value from slot `src_i` in `src_node` to slot `dest_i` in `this`.
+  void transfer(const size_type dest_i, const size_type src_i,
+                btree_node *src_node, allocator_type *alloc) {
     absl::container_internal::SanitizerUnpoisonObject(slot(dest_i));
-    params_type::transfer(alloc, slot(dest_i), src->slot(src_i));
-    absl::container_internal::SanitizerPoisonObject(src->slot(src_i));
+    params_type::transfer(alloc, slot(dest_i), src_node->slot(src_i));
+    absl::container_internal::SanitizerPoisonObject(src_node->slot(src_i));
   }
 
-  // Move n values starting at value i in this node into the values starting at
-  // value j in dest_node.
-  void uninitialized_move_n(const size_type n, const size_type i,
-                            const size_type j, btree_node *dest_node,
-                            allocator_type *alloc) {
+  // Transfers `n` values starting at value `src_i` in `src_node` into the
+  // values starting at value `dest_i` in `this`.
+  void transfer_n(const size_type n, const size_type dest_i,
+                  const size_type src_i, btree_node *src_node,
+                  allocator_type *alloc) {
     absl::container_internal::SanitizerUnpoisonMemoryRegion(
-        dest_node->slot(j), n * sizeof(slot_type));
-    for (slot_type *src = slot(i), *end = src + n, *dest = dest_node->slot(j);
+        slot(dest_i), n * sizeof(slot_type));
+    for (slot_type *src = src_node->slot(src_i), *end = src + n,
+                   *dest = slot(dest_i);
          src != end; ++src, ++dest) {
-      params_type::construct(alloc, dest, src);
+      params_type::transfer(alloc, dest, src);
     }
+    // We take care to avoid poisoning transferred-to nodes in case of overlap.
+    const size_type overlap =
+        this == src_node ? (std::max)(src_i, dest_i + n) - src_i : 0;
+    assert(n >= overlap);
+    absl::container_internal::SanitizerPoisonMemoryRegion(
+        src_node->slot(src_i + overlap), (n - overlap) * sizeof(slot_type));
   }
 
-  // Destroys a range of n values, starting at index i.
-  void value_destroy_n(const size_type i, const size_type n,
-                       allocator_type *alloc) {
-    for (int j = 0; j < n; ++j) {
-      value_destroy(i + j, alloc);
+  // Same as above, except that we start at the end and work our way to the
+  // beginning.
+  void transfer_n_backward(const size_type n, const size_type dest_i,
+                           const size_type src_i, btree_node *src_node,
+                           allocator_type *alloc) {
+    absl::container_internal::SanitizerUnpoisonMemoryRegion(
+        slot(dest_i), n * sizeof(slot_type));
+    for (slot_type *src = src_node->slot(src_i + n - 1), *end = src - n,
+                   *dest = slot(dest_i + n - 1);
+         src != end; --src, --dest) {
+      params_type::transfer(alloc, dest, src);
     }
+    // We take care to avoid poisoning transferred-to nodes in case of overlap.
+    assert(this != src_node || dest_i >= src_i);
+    const size_type num_to_poison =
+        this == src_node ? (std::min)(n, dest_i - src_i) : n;
+    absl::container_internal::SanitizerPoisonMemoryRegion(
+        src_node->slot(src_i), num_to_poison * sizeof(slot_type));
   }
 
   template <typename P>
@@ -1531,10 +1550,8 @@ inline void btree_node<P>::emplace_value(const size_type i,
   // Shift old values to create space for new value and then construct it in
   // place.
   if (i < finish()) {
-    value_init(finish(), alloc, slot(finish() - 1));
-    for (size_type j = finish() - 1; j > i; --j)
-      params_type::move(alloc, slot(j - 1), slot(j));
-    value_destroy(i, alloc);
+    transfer_n_backward(finish() - i, /*dest_i=*/i + 1, /*src_i=*/i, this,
+                        alloc);
   }
   value_init(i, alloc, std::forward<Args>(args)...);
   set_finish(finish() + 1);
@@ -1564,7 +1581,9 @@ template <typename P>
 inline void btree_node<P>::remove_values_ignore_children(
     const int i, const int to_erase, allocator_type *alloc) {
   params_type::move(alloc, slot(i + to_erase), finish_slot(), slot(i));
-  value_destroy_n(finish() - to_erase, to_erase, alloc);
+  for (int j = finish() - to_erase; j < finish(); ++j) {
+    value_destroy(j, alloc);
+  }
   set_finish(finish() - to_erase);
 }
 
@@ -1579,22 +1598,17 @@ void btree_node<P>::rebalance_right_to_left(const int to_move,
   assert(to_move <= right->count());
 
   // 1) Move the delimiting value in the parent to the left node.
-  value_init(finish(), alloc, parent()->slot(position()));
+  transfer(finish(), position(), parent(), alloc);
 
   // 2) Move the (to_move - 1) values from the right node to the left node.
-  right->uninitialized_move_n(to_move - 1, right->start(), finish() + 1, this,
-                              alloc);
+  transfer_n(to_move - 1, finish() + 1, right->start(), right, alloc);
 
   // 3) Move the new delimiting value to the parent from the right node.
-  params_type::move(alloc, right->slot(to_move - 1),
-                    parent()->slot(position()));
-
-  // 4) Shift the values in the right node to their correct position.
-  params_type::move(alloc, right->slot(to_move), right->finish_slot(),
-                    right->start_slot());
+  parent()->transfer(position(), right->start() + to_move - 1, right, alloc);
 
-  // 5) Destroy the now-empty to_move entries in the right node.
-  right->value_destroy_n(right->finish() - to_move, to_move, alloc);
+  // 4) Shift the values in the right node to their correct positions.
+  right->transfer_n(right->count() - to_move, right->start(),
+                    right->start() + to_move, right, alloc);
 
   if (!leaf()) {
     // Move the child pointers from the right to the left node.
@@ -1629,54 +1643,19 @@ void btree_node<P>::rebalance_left_to_right(const int to_move,
   // Lastly, a new delimiting value is moved from the left node into the
   // parent, and the remaining empty left node entries are destroyed.
 
-  if (right->count() >= to_move) {
-    // The original location of the right->count() values are sufficient to hold
-    // the new to_move entries from the parent and left node.
-
-    // 1) Shift existing values in the right node to their correct positions.
-    right->uninitialized_move_n(to_move, right->finish() - to_move,
-                                right->finish(), right, alloc);
-    for (slot_type *src = right->slot(right->finish() - to_move - 1),
-                   *dest = right->slot(right->finish() - 1),
-                   *end = right->start_slot();
-         src >= end; --src, --dest) {
-      params_type::move(alloc, src, dest);
-    }
-
-    // 2) Move the delimiting value in the parent to the right node.
-    params_type::move(alloc, parent()->slot(position()),
-                      right->slot(to_move - 1));
+  // 1) Shift existing values in the right node to their correct positions.
+  right->transfer_n_backward(right->count(), right->start() + to_move,
+                             right->start(), right, alloc);
 
-    // 3) Move the (to_move - 1) values from the left node to the right node.
-    params_type::move(alloc, slot(finish() - (to_move - 1)), finish_slot(),
-                      right->start_slot());
-  } else {
-    // The right node does not have enough initialized space to hold the new
-    // to_move entries, so part of them will move to uninitialized space.
-
-    // 1) Shift existing values in the right node to their correct positions.
-    right->uninitialized_move_n(right->count(), right->start(),
-                                right->start() + to_move, right, alloc);
+  // 2) Move the delimiting value in the parent to the right node.
+  right->transfer(right->start() + to_move - 1, position(), parent(), alloc);
 
-    // 2) Move the delimiting value in the parent to the right node.
-    right->value_init(to_move - 1, alloc, parent()->slot(position()));
-
-    // 3) Move the (to_move - 1) values from the left node to the right node.
-    const size_type uninitialized_remaining = to_move - right->count() - 1;
-    uninitialized_move_n(uninitialized_remaining,
-                         finish() - uninitialized_remaining, right->finish(),
-                         right, alloc);
-    params_type::move(alloc, slot(finish() - (to_move - 1)),
-                      slot(finish() - uninitialized_remaining),
-                      right->start_slot());
-  }
+  // 3) Move the (to_move - 1) values from the left node to the right node.
+  right->transfer_n(to_move - 1, right->start(), finish() - (to_move - 1), this,
+                    alloc);
 
   // 4) Move the new delimiting value to the parent from the left node.
-  params_type::move(alloc, slot(finish() - to_move),
-                    parent()->slot(position()));
-
-  // 5) Destroy the now-empty to_move entries in the left node.
-  value_destroy_n(finish() - to_move, to_move, alloc);
+  parent()->transfer(position(), finish() - to_move, this, alloc);
 
   if (!leaf()) {
     // Move the child pointers from the left to the right node.
@@ -1716,10 +1695,7 @@ void btree_node<P>::split(const int insert_position, btree_node *dest,
   assert(count() >= 1);
 
   // Move values from the left sibling to the right sibling.
-  uninitialized_move_n(dest->count(), finish(), dest->start(), dest, alloc);
-
-  // Destroy the now-empty entries in the left node.
-  value_destroy_n(finish(), dest->count(), alloc);
+  dest->transfer_n(dest->count(), dest->start(), finish(), this, alloc);
 
   // The split key is the largest value in the left sibling.
   --mutable_finish();
@@ -1746,11 +1722,7 @@ void btree_node<P>::merge(btree_node *src, allocator_type *alloc) {
   value_init(finish(), alloc, parent()->slot(position()));
 
   // Move the values from the right to the left node.
-  src->uninitialized_move_n(src->count(), src->start(), finish() + 1, this,
-                            alloc);
-
-  // Destroy the now-empty entries in the right node.
-  src->value_destroy_n(src->start(), src->count(), alloc);
+  transfer_n(src->count(), finish() + 1, src->start(), src, alloc);
 
   if (!leaf()) {
     // Move the child pointers from the right to the left node.
@@ -2474,9 +2446,8 @@ inline auto btree<P>::internal_emplace(iterator iter, Args &&... args)
       // Transfer the values from the old root to the new root.
       node_type *old_root = root();
       node_type *new_root = iter.node;
-      for (int i = old_root->start(), f = old_root->finish(); i < f; ++i) {
-        new_root->transfer(i, i, old_root, alloc);
-      }
+      new_root->transfer_n(old_root->count(), new_root->start(),
+                           old_root->start(), old_root, alloc);
       new_root->set_finish(old_root->finish());
       old_root->set_finish(old_root->start());
       delete_leaf_node(old_root);