Export of internal Abseil changes

--
ceee18732f9499d3a53d46d5974f12ea0774b900 by Abseil Team <absl-team@google.com>:

Remove division from the profile guided optimization

PiperOrigin-RevId: 428444108

--
fc27059f1b0c0b4cb8ddd9a7a88220af52c0c755 by Evan Brown <ezb@google.com>:

Rename btree_node::leaf to is_leaf and also add is_internal for readability improvements.

PiperOrigin-RevId: 428076422

--
6a90d18477cc3a6de84282b6e38d6f294aa72748 by Evan Brown <ezb@google.com>:

In sanitizer mode, add generation integers to b-tree nodes and iterators and validate that iterators have not been invalidated already when they're used.

Even though generation integers are stored in all nodes, we only use the one stored in the root node for validation. The reason we keep one in all the nodes is that nodes can become a root node after they are allocated.

Also change the order of args in init_leaf to not violate the style guide.

PiperOrigin-RevId: 428054226

--
ede4a0f676f43e7003fd2599c263d55222e760ba by Martijn Vels <mvels@google.com>:

Physically remove CordRepConcat

This CL removes all uses of CordRepConcat. This change is executed by removing all the dead 'btree_enabled()' and 'IsConcat' branches, and all subsequent dead code. This change explicitly does not optimize any of the remaining code other than the most trivial ones such as removing 'stack' loop vars and loops.

PiperOrigin-RevId: 428002308

--
7cc83d96118149cf1aa1258a066b8fd4517df5f6 by Evan Brown <ezb@google.com>:

Change btree_iterator from a struct to a class.

Motivation: btree_iterator has private members and invariants so it should be a class.

Also merge two private sections.

PiperOrigin-RevId: 427768836

--
524d478b0af422e1a867a8823d9fbad149030360 by Martijn Vels <mvels@google.com>:

Physically block the creation of new CordRepConcat nodes.

This change removes CordRepConcat creation, issuing a FATAL errors on the (practically impossible) call path on broken invariants. This change is deliberately limited in impact, subsequent changes will be more voluminous ripping out the (now dead) CordRepConcat code.

PiperOrigin-RevId: 427741022

--
e21eb354c1bb358ea8b64d0e3fbb378e87b8b8c4 by Derek Mauro <dmauro@google.com>:

Update the implementation of ABSL_DEPRECATED to work with GCC, and
recommend using the standard attribute [[deprecated]] for C++14 and newer

GCC users that are experiencing new warnings can silence them with
-Wno-deprecated-declatations.

GCC users that want to see the warnings but not error on them can use
-Wno-error=deprecated-declarations.
PiperOrigin-RevId: 427228952

--
0ab4ee5660f3a072054dc4ab5056925c26977c7a by Laramie Leavitt <lar@google.com>:

Change comment to avoid overflow.

PiperOrigin-RevId: 427090218
GitOrigin-RevId: ceee18732f9499d3a53d46d5974f12ea0774b900
Change-Id: Ida00477b6a3d02a8b7bb467be7621b618385d1e9

5 files changed, 396 insertions, 221 deletions

diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel
index 728c4be1..bc25bac9 100644
--- a/absl/container/BUILD.bazel
+++ b/absl/container/BUILD.bazel
@@ -914,6 +914,7 @@ cc_library(
         ":container_memory",
         ":layout",
         "//absl/base:core_headers",
+        "//absl/base:raw_logging_internal",
         "//absl/base:throw_delegate",
         "//absl/memory",
         "//absl/meta:type_traits",
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt
index b819deeb..648a3dba 100644
--- a/absl/container/CMakeLists.txt
+++ b/absl/container/CMakeLists.txt
@@ -35,6 +35,7 @@ absl_cc_library(
     absl::core_headers
     absl::layout
     absl::memory
+    absl::raw_logging_internal
     absl::strings
     absl::throw_delegate
     absl::type_traits
diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index b2c3d73f..e829e0ba 100644
--- a/absl/container/btree_test.cc
+++ b/absl/container/btree_test.cc
@@ -1213,6 +1213,11 @@ class BtreeNodePeer {
   constexpr static bool UsesLinearNodeSearch() {
     return btree_node<typename Btree::params_type>::use_linear_search::value;
   }
+
+  template <typename Btree>
+  constexpr static bool UsesGenerations() {
+    return Btree::params_type::kEnableGenerations;
+  }
 };
 
 namespace {
@@ -1478,8 +1483,10 @@ TEST(Btree, MovesComparisonsCopiesSwapsTracking) {
   EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<decltype(set61)>(), 61);
   EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<decltype(set100)>(), 100);
   if (sizeof(void *) == 8) {
-    EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<absl::btree_set<int32_t>>(),
-              BtreeNodePeer::GetNumSlotsPerNode<decltype(set61)>());
+    EXPECT_EQ(
+        BtreeNodePeer::GetNumSlotsPerNode<absl::btree_set<int32_t>>(),
+        // When we have generations, there is one fewer slot.
+        BtreeNodePeer::UsesGenerations<absl::btree_set<int32_t>>() ? 60 : 61);
   }
 
   // Test key insertion/deletion in random order.
@@ -1533,8 +1540,10 @@ TEST(Btree, MovesComparisonsCopiesSwapsTrackingThreeWayCompare) {
   EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<decltype(set61)>(), 61);
   EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<decltype(set100)>(), 100);
   if (sizeof(void *) == 8) {
-    EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<absl::btree_set<int32_t>>(),
-              BtreeNodePeer::GetNumSlotsPerNode<decltype(set61)>());
+    EXPECT_EQ(
+        BtreeNodePeer::GetNumSlotsPerNode<absl::btree_set<int32_t>>(),
+        // When we have generations, there is one fewer slot.
+        BtreeNodePeer::UsesGenerations<absl::btree_set<int32_t>>() ? 60 : 61);
   }
 
   // Test key insertion/deletion in random order.
@@ -3020,8 +3029,38 @@ TEST(Btree, InvalidComparatorsCaught) {
       }
     };
     absl::btree_set<int, ThreeWaySumGreaterZeroCmp> set;
-    EXPECT_DEATH(set.insert({0, 1, 2}),
-                 R"regex(lhs_comp_rhs < 0 -> rhs_comp_lhs > 0)regex");
+    EXPECT_DEATH(set.insert({0, 1, 2}), "lhs_comp_rhs < 0 -> rhs_comp_lhs > 0");
+  }
+}
+#endif
+
+#ifndef _MSC_VER
+// This test crashes on MSVC.
+TEST(Btree, InvalidIteratorUse) {
+  if (!BtreeNodePeer::UsesGenerations<absl::btree_set<int>>())
+    GTEST_SKIP() << "Generation validation for iterators is disabled.";
+
+  {
+    absl::btree_set<int> set;
+    for (int i = 0; i < 10; ++i) set.insert(i);
+    auto it = set.begin();
+    set.erase(it++);
+    EXPECT_DEATH(set.erase(it++), "invalidated iterator");
+  }
+  {
+    absl::btree_set<int> set;
+    for (int i = 0; i < 10; ++i) set.insert(i);
+    auto it = set.insert(20).first;
+    set.insert(30);
+    EXPECT_DEATH(*it, "invalidated iterator");
+  }
+  {
+    absl::btree_set<int> set;
+    for (int i = 0; i < 10000; ++i) set.insert(i);
+    auto it = set.find(5000);
+    ASSERT_NE(it, set.end());
+    set.erase(1);
+    EXPECT_DEATH(*it, "invalidated iterator");
   }
 }
 #endif
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index bbc319c1..6c10b00f 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -58,6 +58,7 @@
 #include <type_traits>
 #include <utility>
 
+#include "absl/base/internal/raw_logging.h"
 #include "absl/base/macros.h"
 #include "absl/container/internal/common.h"
 #include "absl/container/internal/compressed_tuple.h"
@@ -74,6 +75,16 @@ namespace absl {
 ABSL_NAMESPACE_BEGIN
 namespace container_internal {
 
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+#error ABSL_BTREE_ENABLE_GENERATIONS cannot be directly set
+#elif defined(ABSL_HAVE_ADDRESS_SANITIZER) || \
+    defined(ABSL_HAVE_MEMORY_SANITIZER)
+// When compiled in sanitizer mode, we add generation integers to the nodes and
+// iterators. When iterators are used, we validate that the container has not
+// been mutated since the iterator was constructed.
+#define ABSL_BTREE_ENABLE_GENERATIONS
+#endif
+
 template <typename Compare, typename T, typename U>
 using compare_result_t = absl::result_of_t<const Compare(const T &, const U &)>;
 
@@ -348,6 +359,12 @@ struct common_params {
   static constexpr bool kIsKeyCompareTransparent =
       IsTransparent<original_key_compare>::value ||
       kIsKeyCompareStringAdapted;
+  static constexpr bool kEnableGenerations =
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+      true;
+#else
+      false;
+#endif
 
   // A type which indicates if we have a key-compare-to functor or a plain old
   // key-compare functor.
@@ -518,6 +535,13 @@ class btree_node {
   //   // A pointer to the node's parent.
   //   btree_node *parent;
   //
+  //   // When ABSL_BTREE_ENABLE_GENERATIONS is defined, we also have a
+  //   // generation integer in order to check that when iterators are
+  //   // used, they haven't been invalidated already. Only the generation on
+  //   // the root is used, but we have one on each node because whether a node
+  //   // is root or not can change.
+  //   uint32_t generation;
+  //
   //   // The position of the node in the node's parent.
   //   field_type position;
   //   // The index of the first populated value in `values`.
@@ -564,13 +588,16 @@ class btree_node {
   btree_node() = default;
 
  private:
-  using layout_type = absl::container_internal::Layout<btree_node *, field_type,
-                                                       slot_type, btree_node *>;
+  using layout_type =
+      absl::container_internal::Layout<btree_node *, uint32_t, field_type,
+                                       slot_type, btree_node *>;
   constexpr static size_type SizeWithNSlots(size_type n) {
-    return layout_type(/*parent*/ 1,
-                       /*position, start, finish, max_count*/ 4,
-                       /*slots*/ n,
-                       /*children*/ 0)
+    return layout_type(
+               /*parent*/ 1,
+               /*generation*/ params_type::kEnableGenerations ? 1 : 0,
+               /*position, start, finish, max_count*/ 4,
+               /*slots*/ n,
+               /*children*/ 0)
         .AllocSize();
   }
   // A lower bound for the overhead of fields other than slots in a leaf node.
@@ -609,16 +636,20 @@ class btree_node {
 
   // Leaves can have less than kNodeSlots values.
   constexpr static layout_type LeafLayout(const int slot_count = kNodeSlots) {
-    return layout_type(/*parent*/ 1,
-                       /*position, start, finish, max_count*/ 4,
-                       /*slots*/ slot_count,
-                       /*children*/ 0);
+    return layout_type(
+        /*parent*/ 1,
+        /*generation*/ params_type::kEnableGenerations ? 1 : 0,
+        /*position, start, finish, max_count*/ 4,
+        /*slots*/ slot_count,
+        /*children*/ 0);
   }
   constexpr static layout_type InternalLayout() {
-    return layout_type(/*parent*/ 1,
-                       /*position, start, finish, max_count*/ 4,
-                       /*slots*/ kNodeSlots,
-                       /*children*/ kNodeSlots + 1);
+    return layout_type(
+        /*parent*/ 1,
+        /*generation*/ params_type::kEnableGenerations ? 1 : 0,
+        /*position, start, finish, max_count*/ 4,
+        /*slots*/ kNodeSlots,
+        /*children*/ kNodeSlots + 1);
   }
   constexpr static size_type LeafSize(const int slot_count = kNodeSlots) {
     return LeafLayout(slot_count).AllocSize();
@@ -632,44 +663,47 @@ class btree_node {
   template <size_type N>
   inline typename layout_type::template ElementType<N> *GetField() {
     // We assert that we don't read from values that aren't there.
-    assert(N < 3 || !leaf());
+    assert(N < 4 || is_internal());
     return InternalLayout().template Pointer<N>(reinterpret_cast<char *>(this));
   }
   template <size_type N>
   inline const typename layout_type::template ElementType<N> *GetField() const {
-    assert(N < 3 || !leaf());
+    assert(N < 4 || is_internal());
     return InternalLayout().template Pointer<N>(
         reinterpret_cast<const char *>(this));
   }
   void set_parent(btree_node *p) { *GetField<0>() = p; }
-  field_type &mutable_finish() { return GetField<1>()[2]; }
-  slot_type *slot(int i) { return &GetField<2>()[i]; }
+  field_type &mutable_finish() { return GetField<2>()[2]; }
+  slot_type *slot(int i) { return &GetField<3>()[i]; }
   slot_type *start_slot() { return slot(start()); }
   slot_type *finish_slot() { return slot(finish()); }
-  const slot_type *slot(int i) const { return &GetField<2>()[i]; }
-  void set_position(field_type v) { GetField<1>()[0] = v; }
-  void set_start(field_type v) { GetField<1>()[1] = v; }
-  void set_finish(field_type v) { GetField<1>()[2] = v; }
+  const slot_type *slot(int i) const { return &GetField<3>()[i]; }
+  void set_position(field_type v) { GetField<2>()[0] = v; }
+  void set_start(field_type v) { GetField<2>()[1] = v; }
+  void set_finish(field_type v) { GetField<2>()[2] = v; }
   // This method is only called by the node init methods.
-  void set_max_count(field_type v) { GetField<1>()[3] = v; }
+  void set_max_count(field_type v) { GetField<2>()[3] = v; }
 
  public:
   // Whether this is a leaf node or not. This value doesn't change after the
   // node is created.
-  bool leaf() const { return GetField<1>()[3] != kInternalNodeMaxCount; }
+  bool is_leaf() const { return GetField<2>()[3] != kInternalNodeMaxCount; }
+  // Whether this is an internal node or not. This value doesn't change after
+  // the node is created.
+  bool is_internal() const { return !is_leaf(); }
 
   // Getter for the position of this node in its parent.
-  field_type position() const { return GetField<1>()[0]; }
+  field_type position() const { return GetField<2>()[0]; }
 
   // Getter for the offset of the first value in the `values` array.
   field_type start() const {
-    // TODO(ezb): when floating storage is implemented, return GetField<1>()[1];
-    assert(GetField<1>()[1] == 0);
+    // TODO(ezb): when floating storage is implemented, return GetField<2>()[1];
+    assert(GetField<2>()[1] == 0);
     return 0;
   }
 
   // Getter for the offset after the last value in the `values` array.
-  field_type finish() const { return GetField<1>()[2]; }
+  field_type finish() const { return GetField<2>()[2]; }
 
   // Getters for the number of values stored in this node.
   field_type count() const {
@@ -679,7 +713,7 @@ class btree_node {
   field_type max_count() const {
     // Internal nodes have max_count==kInternalNodeMaxCount.
     // Leaf nodes have max_count in [1, kNodeSlots].
-    const field_type max_count = GetField<1>()[3];
+    const field_type max_count = GetField<2>()[3];
     return max_count == field_type{kInternalNodeMaxCount}
                ? field_type{kNodeSlots}
                : max_count;
@@ -690,21 +724,44 @@ class btree_node {
   // Getter for whether the node is the root of the tree. The parent of the
   // root of the tree is the leftmost node in the tree which is guaranteed to
   // be a leaf.
-  bool is_root() const { return parent()->leaf(); }
+  bool is_root() const { return parent()->is_leaf(); }
   void make_root() {
     assert(parent()->is_root());
+    set_generation(parent()->generation());
     set_parent(parent()->parent());
   }
 
+  // Gets the root node's generation integer, which is the one used by the tree.
+  uint32_t *get_root_generation() const {
+    assert(params_type::kEnableGenerations);
+    const btree_node *curr = this;
+    for (; !curr->is_root(); curr = curr->parent()) continue;
+    return const_cast<uint32_t *>(&curr->GetField<1>()[0]);
+  }
+
+  // Returns the generation for iterator validation.
+  uint32_t generation() const {
+    return params_type::kEnableGenerations ? *get_root_generation() : 0;
+  }
+  // Updates generation. Should only be called on a root node or during node
+  // initialization.
+  void set_generation(uint32_t generation) {
+    if (params_type::kEnableGenerations) GetField<1>()[0] = generation;
+  }
+  // Updates the generation. We do this whenever the node is mutated.
+  void next_generation() {
+    if (params_type::kEnableGenerations) ++*get_root_generation();
+  }
+
   // Getters for the key/value at position i in the node.
   const key_type &key(int i) const { return params_type::key(slot(i)); }
   reference value(int i) { return params_type::element(slot(i)); }
   const_reference value(int i) const { return params_type::element(slot(i)); }
 
   // Getters/setter for the child at position i in the node.
-  btree_node *child(int i) const { return GetField<3>()[i]; }
+  btree_node *child(int i) const { return GetField<4>()[i]; }
   btree_node *start_child() const { return child(start()); }
-  btree_node *&mutable_child(int i) { return GetField<3>()[i]; }
+  btree_node *&mutable_child(int i) { return GetField<4>()[i]; }
   void clear_child(int i) {
     absl::container_internal::SanitizerPoisonObject(&mutable_child(i));
   }
@@ -861,7 +918,8 @@ class btree_node {
   void merge(btree_node *src, allocator_type *alloc);
 
   // Node allocation/deletion routines.
-  void init_leaf(btree_node *parent, int max_count) {
+  void init_leaf(int max_count, btree_node *parent) {
+    set_generation(0);
     set_parent(parent);
     set_position(0);
     set_start(0);
@@ -871,7 +929,7 @@ class btree_node {
         start_slot(), max_count * sizeof(slot_type));
   }
   void init_internal(btree_node *parent) {
-    init_leaf(parent, kNodeSlots);
+    init_leaf(kNodeSlots, parent);
     // Set `max_count` to a sentinel value to indicate that this node is
     // internal.
     set_max_count(kInternalNodeMaxCount);
@@ -890,15 +948,18 @@ class btree_node {
  private:
   template <typename... Args>
   void value_init(const field_type i, allocator_type *alloc, Args &&... args) {
+    next_generation();
     absl::container_internal::SanitizerUnpoisonObject(slot(i));
     params_type::construct(alloc, slot(i), std::forward<Args>(args)...);
   }
   void value_destroy(const field_type i, allocator_type *alloc) {
+    next_generation();
     params_type::destroy(alloc, slot(i));
     absl::container_internal::SanitizerPoisonObject(slot(i));
   }
   void value_destroy_n(const field_type i, const field_type n,
                        allocator_type *alloc) {
+    next_generation();
     for (slot_type *s = slot(i), *end = slot(i + n); s != end; ++s) {
       params_type::destroy(alloc, s);
       absl::container_internal::SanitizerPoisonObject(s);
@@ -914,6 +975,7 @@ class btree_node {
   // 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) {
+    next_generation();
     transfer(slot(dest_i), src_node->slot(src_i), alloc);
   }
 
@@ -922,6 +984,7 @@ class btree_node {
   void transfer_n(const size_type n, const size_type dest_i,
                   const size_type src_i, btree_node *src_node,
                   allocator_type *alloc) {
+    next_generation();
     for (slot_type *src = src_node->slot(src_i), *end = src + n,
                    *dest = slot(dest_i);
          src != end; ++src, ++dest) {
@@ -934,6 +997,7 @@ class btree_node {
   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) {
+    next_generation();
     for (slot_type *src = src_node->slot(src_i + n - 1), *end = src - n,
                    *dest = slot(dest_i + n - 1);
          src != end; --src, --dest) {
@@ -944,14 +1008,13 @@ class btree_node {
   template <typename P>
   friend class btree;
   template <typename N, typename R, typename P>
-  friend struct btree_iterator;
+  friend class btree_iterator;
   friend class BtreeNodePeer;
   friend struct btree_access;
 };
 
 template <typename Node, typename Reference, typename Pointer>
-struct btree_iterator {
- private:
+class btree_iterator {
   using key_type = typename Node::key_type;
   using size_type = typename Node::size_type;
   using params_type = typename Node::params_type;
@@ -979,9 +1042,15 @@ struct btree_iterator {
   using reference = Reference;
   using iterator_category = std::bidirectional_iterator_tag;
 
-  btree_iterator() : node(nullptr), position(-1) {}
-  explicit btree_iterator(Node *n) : node(n), position(n->start()) {}
-  btree_iterator(Node *n, int p) : node(n), position(p) {}
+  btree_iterator() : btree_iterator(nullptr, -1) {}
+  explicit btree_iterator(Node *n) : btree_iterator(n, n->start()) {}
+  btree_iterator(Node *n, int p) : node_(n), position_(p) {
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+    // Use `~uint32_t{}` as a sentinel value for iterator generations so it
+    // doesn't match the initial value for the actual generation.
+    generation_ = n != nullptr ? n->generation() : ~uint32_t{};
+#endif
+  }
 
   // NOTE: this SFINAE allows for implicit conversions from iterator to
   // const_iterator, but it specifically avoids hiding the copy constructor so
@@ -992,58 +1061,32 @@ struct btree_iterator {
                     std::is_same<btree_iterator, const_iterator>::value,
                 int> = 0>
   btree_iterator(const btree_iterator<N, R, P> other)  // NOLINT
-      : node(other.node), position(other.position) {}
-
- private:
-  // This SFINAE allows explicit conversions from const_iterator to
-  // iterator, but also avoids hiding the copy constructor.
-  // NOTE: the const_cast is safe because this constructor is only called by
-  // non-const methods and the container owns the nodes.
-  template <typename N, typename R, typename P,
-            absl::enable_if_t<
-                std::is_same<btree_iterator<N, R, P>, const_iterator>::value &&
-                    std::is_same<btree_iterator, iterator>::value,
-                int> = 0>
-  explicit btree_iterator(const btree_iterator<N, R, P> other)
-      : node(const_cast<node_type *>(other.node)), position(other.position) {}
-
-  // Increment/decrement the iterator.
-  void increment() {
-    if (node->leaf() && ++position < node->finish()) {
-      return;
-    }
-    increment_slow();
-  }
-  void increment_slow();
-
-  void decrement() {
-    if (node->leaf() && --position >= node->start()) {
-      return;
-    }
-    decrement_slow();
+      : node_(other.node_), position_(other.position_) {
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+    generation_ = other.generation_;
+#endif
   }
-  void decrement_slow();
 
- public:
   bool operator==(const iterator &other) const {
-    return node == other.node && position == other.position;
+    return node_ == other.node_ && position_ == other.position_;
   }
   bool operator==(const const_iterator &other) const {
-    return node == other.node && position == other.position;
+    return node_ == other.node_ && position_ == other.position_;
   }
   bool operator!=(const iterator &other) const {
-    return node != other.node || position != other.position;
+    return node_ != other.node_ || position_ != other.position_;
   }
   bool operator!=(const const_iterator &other) const {
-    return node != other.node || position != other.position;
+    return node_ != other.node_ || position_ != other.position_;
   }
 
   // Accessors for the key/value the iterator is pointing at.
   reference operator*() const {
-    ABSL_HARDENING_ASSERT(node != nullptr);
-    ABSL_HARDENING_ASSERT(node->start() <= position);
-    ABSL_HARDENING_ASSERT(node->finish() > position);
-    return node->value(position);
+    ABSL_HARDENING_ASSERT(node_ != nullptr);
+    ABSL_HARDENING_ASSERT(node_->start() <= position_);
+    ABSL_HARDENING_ASSERT(node_->finish() > position_);
+    assert_valid_generation();
+    return node_->value(position_);
   }
   pointer operator->() const { return &operator*(); }
 
@@ -1083,15 +1126,74 @@ struct btree_iterator {
   friend class base_checker;
   friend struct btree_access;
 
-  const key_type &key() const { return node->key(position); }
-  slot_type *slot() { return node->slot(position); }
+  // This SFINAE allows explicit conversions from const_iterator to
+  // iterator, but also avoids hiding the copy constructor.
+  // NOTE: the const_cast is safe because this constructor is only called by
+  // non-const methods and the container owns the nodes.
+  template <typename N, typename R, typename P,
+            absl::enable_if_t<
+                std::is_same<btree_iterator<N, R, P>, const_iterator>::value &&
+                    std::is_same<btree_iterator, iterator>::value,
+                int> = 0>
+  explicit btree_iterator(const btree_iterator<N, R, P> other)
+      : node_(const_cast<node_type *>(other.node_)),
+        position_(other.position_) {
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+    generation_ = other.generation_;
+#endif
+  }
+
+  // Increment/decrement the iterator.
+  void increment() {
+    assert_valid_generation();
+    if (node_->is_leaf() && ++position_ < node_->finish()) {
+      return;
+    }
+    increment_slow();
+  }
+  void increment_slow();
+
+  void decrement() {
+    assert_valid_generation();
+    if (node_->is_leaf() && --position_ >= node_->start()) {
+      return;
+    }
+    decrement_slow();
+  }
+  void decrement_slow();
+
+  // Updates the generation. For use internally right before we return an
+  // iterator to the user.
+  void update_generation() {
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+    if (node_ != nullptr) generation_ = node_->generation();
+#endif
+  }
+
+  const key_type &key() const { return node_->key(position_); }
+  slot_type *slot() { return node_->slot(position_); }
+
+  void assert_valid_generation() const {
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+    if (node_ != nullptr && node_->generation() != generation_) {
+      ABSL_INTERNAL_LOG(
+          FATAL,
+          "Attempting to use an invalidated iterator. The corresponding b-tree "
+          "container has been mutated since this iterator was constructed.");
+    }
+#endif
+  }
 
   // The node in the tree the iterator is pointing at.
-  Node *node;
+  Node *node_;
   // The position within the node of the tree the iterator is pointing at.
   // NOTE: this is an int rather than a field_type because iterators can point
   // to invalid positions (such as -1) in certain circumstances.
-  int position;
+  int position_;
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+  // Used to check that the iterator hasn't been invalidated.
+  uint32_t generation_;
+#endif
 };
 
 template <typename Params>
@@ -1106,6 +1208,9 @@ class btree {
   struct alignas(node_type::Alignment()) EmptyNodeType : node_type {
     using field_type = typename node_type::field_type;
     node_type *parent;
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+    uint32_t generation = 0;
+#endif
     field_type position = 0;
     field_type start = 0;
     field_type finish = 0;
@@ -1490,12 +1595,12 @@ class btree {
   }
   node_type *new_leaf_node(node_type *parent) {
     node_type *n = allocate(node_type::LeafSize());
-    n->init_leaf(parent, kNodeSlots);
+    n->init_leaf(kNodeSlots, parent);
     return n;
   }
   node_type *new_leaf_root_node(const int max_count) {
     node_type *n = allocate(node_type::LeafSize(max_count));
-    n->init_leaf(/*parent=*/n, max_count);
+    n->init_leaf(max_count, /*parent=*/n);
     return n;
   }
 
@@ -1519,10 +1624,10 @@ class btree {
   void try_shrink();
 
   iterator internal_end(iterator iter) {
-    return iter.node != nullptr ? iter : end();
+    return iter.node_ != nullptr ? iter : end();
   }
   const_iterator internal_end(const_iterator iter) const {
-    return iter.node != nullptr ? iter : end();
+    return iter.node_ != nullptr ? iter : end();
   }
 
   // Emplaces a value into the btree immediately before iter. Requires that
@@ -1532,9 +1637,8 @@ class btree {
 
   // Returns an iterator pointing to the first value >= the value "iter" is
   // pointing at. Note that "iter" might be pointing to an invalid location such
-  // as iter.position == iter.node->finish(). This routine simply moves iter up
-  // in the tree to a valid location.
-  // Requires: iter.node is non-null.
+  // as iter.position_ == iter.node_->finish(). This routine simply moves iter
+  // up in the tree to a valid location. Requires: iter.node_ is non-null.
   template <typename IterType>
   static IterType internal_last(IterType iter);
 
@@ -1570,7 +1674,7 @@ class btree {
     if (node == nullptr || (node == root() && empty())) {
       return node_stats(0, 0);
     }
-    if (node->leaf()) {
+    if (node->is_leaf()) {
       return node_stats(1, 0);
     }
     node_stats res(0, 1);
@@ -1612,7 +1716,7 @@ inline void btree_node<P>::emplace_value(const size_type i,
   value_init(i, alloc, std::forward<Args>(args)...);
   set_finish(finish() + 1);
 
-  if (!leaf() && finish() > i + 1) {
+  if (is_internal() && finish() > i + 1) {
     for (field_type j = finish(); j > i + 1; --j) {
       set_child(j, child(j - 1));
     }
@@ -1630,7 +1734,7 @@ inline void btree_node<P>::remove_values(const field_type i,
   const field_type src_i = i + to_erase;
   transfer_n(orig_finish - src_i, i, src_i, this, alloc);
 
-  if (!leaf()) {
+  if (is_internal()) {
     // Delete all children between begin and end.
     for (int j = 0; j < to_erase; ++j) {
       clear_and_delete(child(i + j + 1), alloc);
@@ -1667,7 +1771,7 @@ void btree_node<P>::rebalance_right_to_left(const int to_move,
   right->transfer_n(right->count() - to_move, right->start(),
                     right->start() + to_move, right, alloc);
 
-  if (!leaf()) {
+  if (is_internal()) {
     // Move the child pointers from the right to the left node.
     for (int i = 0; i < to_move; ++i) {
       init_child(finish() + i + 1, right->child(i));
@@ -1714,7 +1818,7 @@ void btree_node<P>::rebalance_left_to_right(const int to_move,
   // 4) Move the new delimiting value to the parent from the left node.
   parent()->transfer(position(), finish() - to_move, this, alloc);
 
-  if (!leaf()) {
+  if (is_internal()) {
     // Move the child pointers from the left to the right node.
     for (int i = right->finish(); i >= right->start(); --i) {
       right->init_child(i + to_move, right->child(i));
@@ -1760,7 +1864,7 @@ void btree_node<P>::split(const int insert_position, btree_node *dest,
   value_destroy(finish(), alloc);
   parent()->init_child(position() + 1, dest);
 
-  if (!leaf()) {
+  if (is_internal()) {
     for (int i = dest->start(), j = finish() + 1; i <= dest->finish();
          ++i, ++j) {
       assert(child(j) != nullptr);
@@ -1781,7 +1885,7 @@ void btree_node<P>::merge(btree_node *src, allocator_type *alloc) {
   // Move the values from the right to the left node.
   transfer_n(src->count(), finish() + 1, src->start(), src, alloc);
 
-  if (!leaf()) {
+  if (is_internal()) {
     // Move the child pointers from the right to the left node.
     for (int i = src->start(), j = finish() + 1; i <= src->finish(); ++i, ++j) {
       init_child(j, src->child(i));
@@ -1799,7 +1903,7 @@ void btree_node<P>::merge(btree_node *src, allocator_type *alloc) {
 
 template <typename P>
 void btree_node<P>::clear_and_delete(btree_node *node, allocator_type *alloc) {
-  if (node->leaf()) {
+  if (node->is_leaf()) {
     node->value_destroy_n(node->start(), node->count(), alloc);
     deallocate(LeafSize(node->max_count()), node, alloc);
     return;
@@ -1813,7 +1917,15 @@ void btree_node<P>::clear_and_delete(btree_node *node, allocator_type *alloc) {
   btree_node *delete_root_parent = node->parent();
 
   // Navigate to the leftmost leaf under node, and then delete upwards.
-  while (!node->leaf()) node = node->start_child();
+  while (node->is_internal()) node = node->start_child();
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+  // When generations are enabled, we delete the leftmost leaf last in case it's
+  // the parent of the root and we need to check whether it's a leaf before we
+  // can update the root's generation.
+  // TODO(ezb): if we change btree_node::is_root to check a bool inside the node
+  // instead of checking whether the parent is a leaf, we can remove this logic.
+  btree_node *leftmost_leaf = node;
+#endif
   // Use `int` because `pos` needs to be able to hold `kNodeSlots+1`, which
   // isn't guaranteed to be a valid `field_type`.
   int pos = node->position();
@@ -1823,14 +1935,17 @@ void btree_node<P>::clear_and_delete(btree_node *node, allocator_type *alloc) {
     assert(pos <= parent->finish());
     do {
       node = parent->child(pos);
-      if (!node->leaf()) {
+      if (node->is_internal()) {
         // Navigate to the leftmost leaf under node.
-        while (!node->leaf()) node = node->start_child();
+        while (node->is_internal()) node = node->start_child();
         pos = node->position();
         parent = node->parent();
       }
       node->value_destroy_n(node->start(), node->count(), alloc);
-      deallocate(LeafSize(node->max_count()), node, alloc);
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+      if (leftmost_leaf != node)
+#endif
+        deallocate(LeafSize(node->max_count()), node, alloc);
       ++pos;
     } while (pos <= parent->finish());
 
@@ -1842,7 +1957,12 @@ void btree_node<P>::clear_and_delete(btree_node *node, allocator_type *alloc) {
       parent = node->parent();
       node->value_destroy_n(node->start(), node->count(), alloc);
       deallocate(InternalSize(), node, alloc);
-      if (parent == delete_root_parent) return;
+      if (parent == delete_root_parent) {
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+        deallocate(LeafSize(leftmost_leaf->max_count()), leftmost_leaf, alloc);
+#endif
+        return;
+      }
       ++pos;
     } while (pos > parent->finish());
   }
@@ -1852,49 +1972,49 @@ void btree_node<P>::clear_and_delete(btree_node *node, allocator_type *alloc) {
 // btree_iterator methods
 template <typename N, typename R, typename P>
 void btree_iterator<N, R, P>::increment_slow() {
-  if (node->leaf()) {
-    assert(position >= node->finish());
+  if (node_->is_leaf()) {
+    assert(position_ >= node_->finish());
     btree_iterator save(*this);
-    while (position == node->finish() && !node->is_root()) {
-      assert(node->parent()->child(node->position()) == node);
-      position = node->position();
-      node = node->parent();
+    while (position_ == node_->finish() && !node_->is_root()) {
+      assert(node_->parent()->child(node_->position()) == node_);
+      position_ = node_->position();
+      node_ = node_->parent();
     }
     // TODO(ezb): assert we aren't incrementing end() instead of handling.
-    if (position == node->finish()) {
+    if (position_ == node_->finish()) {
       *this = save;
     }
   } else {
-    assert(position < node->finish());
-    node = node->child(position + 1);
-    while (!node->leaf()) {
-      node = node->start_child();
+    assert(position_ < node_->finish());
+    node_ = node_->child(position_ + 1);
+    while (node_->is_internal()) {
+      node_ = node_->start_child();
     }
-    position = node->start();
+    position_ = node_->start();
   }
 }
 
 template <typename N, typename R, typename P>
 void btree_iterator<N, R, P>::decrement_slow() {
-  if (node->leaf()) {
-    assert(position <= -1);
+  if (node_->is_leaf()) {
+    assert(position_ <= -1);
     btree_iterator save(*this);
-    while (position < node->start() && !node->is_root()) {
-      assert(node->parent()->child(node->position()) == node);
-      position = node->position() - 1;
-      node = node->parent();
+    while (position_ < node_->start() && !node_->is_root()) {
+      assert(node_->parent()->child(node_->position()) == node_);
+      position_ = node_->position() - 1;
+      node_ = node_->parent();
     }
     // TODO(ezb): assert we aren't decrementing begin() instead of handling.
-    if (position < node->start()) {
+    if (position_ < node_->start()) {
       *this = save;
     }
   } else {
-    assert(position >= node->start());
-    node = node->child(position);
-    while (!node->leaf()) {
-      node = node->child(node->finish());
+    assert(position_ >= node_->start());
+    node_ = node_->child(position_);
+    while (node_->is_internal()) {
+      node_ = node_->child(node_->finish());
     }
-    position = node->finish() - 1;
+    position_ = node_->finish() - 1;
   }
 }
 
@@ -2009,7 +2129,7 @@ auto btree<P>::insert_unique(const K &key, Args &&... args)
     }
   } else {
     iterator last = internal_last(iter);
-    if (last.node && !compare_keys(key, last.key())) {
+    if (last.node_ && !compare_keys(key, last.key())) {
       // The key already exists in the tree, do nothing.
       return {last, false};
     }
@@ -2067,7 +2187,7 @@ auto btree<P>::insert_multi(const key_type &key, ValueType &&v) -> iterator {
   }
 
   iterator iter = internal_upper_bound(key);
-  if (iter.node == nullptr) {
+  if (iter.node_ == nullptr) {
     iter = end();
   }
   return internal_emplace(iter, std::forward<ValueType>(v));
@@ -2154,21 +2274,22 @@ 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->leaf()) {
+  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.
     iterator internal_iter(iter);
     --iter;
-    assert(iter.node->leaf());
-    params_type::move(mutable_allocator(), iter.node->slot(iter.position),
-                      internal_iter.node->slot(internal_iter.position));
+    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());
+  iter.node_->remove_values(iter.position_, /*to_erase=*/1,
+                            mutable_allocator());
   --size_;
 
   // We want to return the next value after the one we just erased. If we
@@ -2176,7 +2297,7 @@ auto btree<P>::erase(iterator iter) -> iterator {
   // value is ++(++iter). If we erased from a leaf node (internal_delete ==
   // false) then the next value is ++iter. Note that ++iter may point to an
   // internal node and the value in the internal node may move to a leaf node
-  // (iter.node) when rebalancing is performed at the leaf level.
+  // (iter.node_) when rebalancing is performed at the leaf level.
 
   iterator res = rebalance_after_delete(iter);
 
@@ -2193,14 +2314,14 @@ auto btree<P>::rebalance_after_delete(iterator iter) -> iterator {
   iterator res(iter);
   bool first_iteration = true;
   for (;;) {
-    if (iter.node == root()) {
+    if (iter.node_ == root()) {
       try_shrink();
       if (empty()) {
         return end();
       }
       break;
     }
-    if (iter.node->count() >= kMinNodeValues) {
+    if (iter.node_->count() >= kMinNodeValues) {
       break;
     }
     bool merged = try_merge_or_rebalance(&iter);
@@ -2213,14 +2334,15 @@ auto btree<P>::rebalance_after_delete(iterator iter) -> iterator {
     if (!merged) {
       break;
     }
-    iter.position = iter.node->position();
-    iter.node = iter.node->parent();
+    iter.position_ = iter.node_->position();
+    iter.node_ = iter.node_->parent();
   }
+  res.update_generation();
 
   // Adjust our return value. If we're pointing at the end of a node, advance
   // the iterator.
-  if (res.position == res.node->finish()) {
-    res.position = res.node->finish() - 1;
+  if (res.position_ == res.node_->finish()) {
+    res.position_ = res.node_->finish() - 1;
     ++res;
   }
 
@@ -2242,28 +2364,31 @@ auto btree<P>::erase_range(iterator begin, iterator end)
     return {count, this->end()};
   }
 
-  if (begin.node == end.node) {
-    assert(end.position > begin.position);
-    begin.node->remove_values(begin.position, end.position - begin.position,
-                              mutable_allocator());
+  if (begin.node_ == end.node_) {
+    assert(end.position_ > begin.position_);
+    begin.node_->remove_values(begin.position_, end.position_ - begin.position_,
+                               mutable_allocator());
     size_ -= count;
     return {count, rebalance_after_delete(begin)};
   }
 
   const size_type target_size = size_ - count;
   while (size_ > target_size) {
-    if (begin.node->leaf()) {
+    if (begin.node_->is_leaf()) {
       const size_type remaining_to_erase = size_ - target_size;
-      const size_type remaining_in_node = begin.node->finish() - begin.position;
+      const size_type remaining_in_node =
+          begin.node_->finish() - begin.position_;
       const size_type to_erase =
           (std::min)(remaining_to_erase, remaining_in_node);
-      begin.node->remove_values(begin.position, to_erase, mutable_allocator());
+      begin.node_->remove_values(begin.position_, to_erase,
+                                 mutable_allocator());
       size_ -= to_erase;
       begin = rebalance_after_delete(begin);
     } else {
       begin = erase(begin);
     }
   }
+  begin.update_generation();
   return {count, begin};
 }
 
@@ -2300,16 +2425,16 @@ void btree<P>::verify() const {
   assert(leftmost() != nullptr);
   assert(rightmost_ != nullptr);
   assert(empty() || size() == internal_verify(root(), nullptr, nullptr));
-  assert(leftmost() == (++const_iterator(root(), -1)).node);
-  assert(rightmost_ == (--const_iterator(root(), root()->finish())).node);
-  assert(leftmost()->leaf());
-  assert(rightmost_->leaf());
+  assert(leftmost() == (++const_iterator(root(), -1)).node_);
+  assert(rightmost_ == (--const_iterator(root(), root()->finish())).node_);
+  assert(leftmost()->is_leaf());
+  assert(rightmost_->is_leaf());
 }
 
 template <typename P>
 void btree<P>::rebalance_or_split(iterator *iter) {
-  node_type *&node = iter->node;
-  int &insert_position = iter->position;
+  node_type *&node = iter->node_;
+  int &insert_position = iter->position_;
   assert(node->count() == node->max_count());
   assert(kNodeSlots == node->max_count());
 
@@ -2384,16 +2509,17 @@ void btree<P>::rebalance_or_split(iterator *iter) {
     // Create a new root node and set the current root node as the child of the
     // new root.
     parent = new_internal_node(parent);
+    parent->set_generation(root()->generation());
     parent->init_child(parent->start(), root());
     mutable_root() = parent;
     // If the former root was a leaf node, then it's now the rightmost node.
-    assert(!parent->start_child()->leaf() ||
+    assert(parent->start_child()->is_internal() ||
            parent->start_child() == rightmost_);
   }
 
   // Split the node.
   node_type *split_node;
-  if (node->leaf()) {
+  if (node->is_leaf()) {
     split_node = new_leaf_node(parent);
     node->split(insert_position, split_node, mutable_allocator());
     if (rightmost_ == node) rightmost_ = split_node;
@@ -2416,50 +2542,51 @@ void btree<P>::merge_nodes(node_type *left, node_type *right) {
 
 template <typename P>
 bool btree<P>::try_merge_or_rebalance(iterator *iter) {
-  node_type *parent = iter->node->parent();
-  if (iter->node->position() > parent->start()) {
+  node_type *parent = iter->node_->parent();
+  if (iter->node_->position() > parent->start()) {
     // Try merging with our left sibling.
-    node_type *left = parent->child(iter->node->position() - 1);
+    node_type *left = parent->child(iter->node_->position() - 1);
     assert(left->max_count() == kNodeSlots);
-    if (1U + left->count() + iter->node->count() <= kNodeSlots) {
-      iter->position += 1 + left->count();
-      merge_nodes(left, iter->node);
-      iter->node = left;
+    if (1U + left->count() + iter->node_->count() <= kNodeSlots) {
+      iter->position_ += 1 + left->count();
+      merge_nodes(left, iter->node_);
+      iter->node_ = left;
       return true;
     }
   }
-  if (iter->node->position() < parent->finish()) {
+  if (iter->node_->position() < parent->finish()) {
     // Try merging with our right sibling.
-    node_type *right = parent->child(iter->node->position() + 1);
+    node_type *right = parent->child(iter->node_->position() + 1);
     assert(right->max_count() == kNodeSlots);
-    if (1U + iter->node->count() + right->count() <= kNodeSlots) {
-      merge_nodes(iter->node, right);
+    if (1U + iter->node_->count() + right->count() <= kNodeSlots) {
+      merge_nodes(iter->node_, right);
       return true;
     }
     // Try rebalancing with our right sibling. We don't perform rebalancing if
-    // we deleted the first element from iter->node and the node is not
+    // we deleted the first element from iter->node_ and the node is not
     // empty. This is a small optimization for the common pattern of deleting
     // from the front of the tree.
     if (right->count() > kMinNodeValues &&
-        (iter->node->count() == 0 || iter->position > iter->node->start())) {
-      int to_move = (right->count() - iter->node->count()) / 2;
+        (iter->node_->count() == 0 || iter->position_ > iter->node_->start())) {
+      int to_move = (right->count() - iter->node_->count()) / 2;
       to_move = (std::min)(to_move, right->count() - 1);
-      iter->node->rebalance_right_to_left(to_move, right, mutable_allocator());
+      iter->node_->rebalance_right_to_left(to_move, right, mutable_allocator());
       return false;
     }
   }
-  if (iter->node->position() > parent->start()) {
+  if (iter->node_->position() > parent->start()) {
     // Try rebalancing with our left sibling. We don't perform rebalancing if
-    // we deleted the last element from iter->node and the node is not
+    // we deleted the last element from iter->node_ and the node is not
     // empty. This is a small optimization for the common pattern of deleting
     // from the back of the tree.
-    node_type *left = parent->child(iter->node->position() - 1);
+    node_type *left = parent->child(iter->node_->position() - 1);
     if (left->count() > kMinNodeValues &&
-        (iter->node->count() == 0 || iter->position < iter->node->finish())) {
-      int to_move = (left->count() - iter->node->count()) / 2;
+        (iter->node_->count() == 0 ||
+         iter->position_ < iter->node_->finish())) {
+      int to_move = (left->count() - iter->node_->count()) / 2;
       to_move = (std::min)(to_move, left->count() - 1);
-      left->rebalance_left_to_right(to_move, iter->node, mutable_allocator());
-      iter->position += to_move;
+      left->rebalance_left_to_right(to_move, iter->node_, mutable_allocator());
+      iter->position_ += to_move;
       return false;
     }
   }
@@ -2473,7 +2600,7 @@ void btree<P>::try_shrink() {
     return;
   }
   // Deleted the last item on the root node, shrink the height of the tree.
-  if (orig_root->leaf()) {
+  if (orig_root->is_leaf()) {
     assert(size() == 0);
     mutable_root() = rightmost_ = EmptyNode();
   } else {
@@ -2487,15 +2614,16 @@ void btree<P>::try_shrink() {
 template <typename P>
 template <typename IterType>
 inline IterType btree<P>::internal_last(IterType iter) {
-  assert(iter.node != nullptr);
-  while (iter.position == iter.node->finish()) {
-    iter.position = iter.node->position();
-    iter.node = iter.node->parent();
-    if (iter.node->leaf()) {
-      iter.node = nullptr;
+  assert(iter.node_ != nullptr);
+  while (iter.position_ == iter.node_->finish()) {
+    iter.position_ = iter.node_->position();
+    iter.node_ = iter.node_->parent();
+    if (iter.node_->is_leaf()) {
+      iter.node_ = nullptr;
       break;
     }
   }
+  iter.update_generation();
   return iter;
 }
 
@@ -2503,37 +2631,39 @@ template <typename P>
 template <typename... Args>
 inline auto btree<P>::internal_emplace(iterator iter, Args &&... args)
     -> iterator {
-  if (!iter.node->leaf()) {
+  if (iter.node_->is_internal()) {
     // We can't insert on an internal node. Instead, we'll insert after the
     // previous value which is guaranteed to be on a leaf node.
     --iter;
-    ++iter.position;
+    ++iter.position_;
   }
-  const field_type max_count = iter.node->max_count();
+  const field_type max_count = iter.node_->max_count();
   allocator_type *alloc = mutable_allocator();
-  if (iter.node->count() == max_count) {
+  if (iter.node_->count() == max_count) {
     // Make room in the leaf for the new item.
     if (max_count < kNodeSlots) {
       // Insertion into the root where the root is smaller than the full node
       // size. Simply grow the size of the root node.
-      assert(iter.node == root());
-      iter.node =
+      assert(iter.node_ == root());
+      iter.node_ =
           new_leaf_root_node((std::min<int>)(kNodeSlots, 2 * max_count));
       // Transfer the values from the old root to the new root.
       node_type *old_root = root();
-      node_type *new_root = iter.node;
+      node_type *new_root = iter.node_;
       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());
+      new_root->set_generation(old_root->generation());
       node_type::clear_and_delete(old_root, alloc);
       mutable_root() = rightmost_ = new_root;
     } else {
       rebalance_or_split(&iter);
     }
   }
-  iter.node->emplace_value(iter.position, alloc, std::forward<Args>(args)...);
+  iter.node_->emplace_value(iter.position_, alloc, std::forward<Args>(args)...);
   ++size_;
+  iter.update_generation();
   return iter;
 }
 
@@ -2544,8 +2674,8 @@ inline auto btree<P>::internal_locate(const K &key) const
   iterator iter(const_cast<node_type *>(root()));
   for (;;) {
     SearchResult<int, is_key_compare_to::value> res =
-        iter.node->lower_bound(key, key_comp());
-    iter.position = res.value;
+        iter.node_->lower_bound(key, key_comp());
+    iter.position_ = res.value;
     if (res.IsEq()) {
       return {iter, MatchKind::kEq};
     }
@@ -2553,10 +2683,10 @@ inline auto btree<P>::internal_locate(const K &key) const
     // down the tree if the keys are equal, but determining equality would
     // require doing an extra comparison on each node on the way down, and we
     // will need to go all the way to the leaf node in the expected case.
-    if (iter.node->leaf()) {
+    if (iter.node_->is_leaf()) {
       break;
     }
-    iter.node = iter.node->child(iter.position);
+    iter.node_ = iter.node_->child(iter.position_);
   }
   // Note: in the non-key-compare-to case, the key may actually be equivalent
   // here (and the MatchKind::kNe is ignored).
@@ -2576,13 +2706,13 @@ auto btree<P>::internal_lower_bound(const K &key) const
   SearchResult<int, is_key_compare_to::value> res;
   bool seen_eq = false;
   for (;;) {
-    res = iter.node->lower_bound(key, key_comp());
-    iter.position = res.value;
-    if (iter.node->leaf()) {
+    res = iter.node_->lower_bound(key, key_comp());
+    iter.position_ = res.value;
+    if (iter.node_->is_leaf()) {
       break;
     }
     seen_eq = seen_eq || res.IsEq();
-    iter.node = iter.node->child(iter.position);
+    iter.node_ = iter.node_->child(iter.position_);
   }
   if (res.IsEq()) return {iter, MatchKind::kEq};
   return {internal_last(iter), seen_eq ? MatchKind::kEq : MatchKind::kNe};
@@ -2593,11 +2723,11 @@ template <typename K>
 auto btree<P>::internal_upper_bound(const K &key) const -> iterator {
   iterator iter(const_cast<node_type *>(root()));
   for (;;) {
-    iter.position = iter.node->upper_bound(key, key_comp());
-    if (iter.node->leaf()) {
+    iter.position_ = iter.node_->upper_bound(key, key_comp());
+    if (iter.node_->is_leaf()) {
       break;
     }
-    iter.node = iter.node->child(iter.position);
+    iter.node_ = iter.node_->child(iter.position_);
   }
   return internal_last(iter);
 }
@@ -2612,7 +2742,7 @@ auto btree<P>::internal_find(const K &key) const -> iterator {
     }
   } else {
     const iterator iter = internal_last(res.value);
-    if (iter.node != nullptr && !compare_keys(key, iter.key())) {
+    if (iter.node_ != nullptr && !compare_keys(key, iter.key())) {
       return iter;
     }
   }
@@ -2634,7 +2764,7 @@ int btree<P>::internal_verify(const node_type *node, const key_type *lo,
     assert(!compare_keys(node->key(i), node->key(i - 1)));
   }
   int count = node->count();
-  if (!node->leaf()) {
+  if (node->is_internal()) {
     for (int i = node->start(); i <= node->finish(); ++i) {
       assert(node->child(i) != nullptr);
       assert(node->child(i)->parent() == node);
@@ -2659,8 +2789,8 @@ struct btree_access {
         ++it;
         continue;
       }
-      auto *node = it.node;
-      if (!node->leaf()) {
+      auto *node = it.node_;
+      if (node->is_internal()) {
         // Handle internal nodes normally.
         it = container.erase(it);
         continue;
@@ -2669,26 +2799,28 @@ struct btree_access {
       // at once before doing rebalancing.
 
       // The current position to transfer slots to.
-      int to_pos = it.position;
-      node->value_destroy(it.position, alloc);
-      while (++it.position < node->finish()) {
+      int to_pos = it.position_;
+      node->value_destroy(it.position_, alloc);
+      while (++it.position_ < node->finish()) {
+        it.update_generation();
         if (pred(*it)) {
-          node->value_destroy(it.position, alloc);
+          node->value_destroy(it.position_, alloc);
         } else {
-          node->transfer(node->slot(to_pos++), node->slot(it.position),
-                         alloc);
+          node->transfer(node->slot(to_pos++), node->slot(it.position_), alloc);
         }
       }
       const int num_deleted = node->finish() - to_pos;
       tree.size_ -= num_deleted;
       node->set_finish(to_pos);
-      it.position = to_pos;
+      it.position_ = to_pos;
       it = tree.rebalance_after_delete(it);
     }
     return initial_size - container.size();
   }
 };
 
+#undef ABSL_BTREE_ENABLE_GENERATIONS
+
 }  // namespace container_internal
 ABSL_NAMESPACE_END
 }  // namespace absl
diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h
index bae5c6e2..cc2e1793 100644
--- a/absl/container/internal/btree_container.h
+++ b/absl/container/internal/btree_container.h
@@ -537,6 +537,7 @@ class btree_multiset_container : public btree_container<Tree> {
   using params_type = typename Tree::params_type;
   using init_type = typename params_type::init_type;
   using is_key_compare_to = typename params_type::is_key_compare_to;
+  friend class BtreeNodePeer;
 
   template <class K>
   using key_arg = typename super_type::template key_arg<K>;
@@ -668,6 +669,7 @@ template <typename Tree>
 class btree_multimap_container : public btree_multiset_container<Tree> {
   using super_type = btree_multiset_container<Tree>;
   using params_type = typename Tree::params_type;
+  friend class BtreeNodePeer;
 
  public:
   using mapped_type = typename params_type::mapped_type;