about summary refs log tree commit diff
path: root/absl/container
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container')
-rw-r--r--absl/container/BUILD.bazel13
-rw-r--r--absl/container/CMakeLists.txt23
-rw-r--r--absl/container/flat_hash_set.h6
-rw-r--r--absl/container/inlined_vector.h979
-rw-r--r--absl/container/internal/compressed_tuple.h28
-rw-r--r--absl/container/internal/compressed_tuple_test.cc43
-rw-r--r--absl/container/internal/hashtable_debug.h2
-rw-r--r--absl/container/internal/have_sse.h49
-rw-r--r--absl/container/internal/layout.h4
-rw-r--r--absl/container/internal/layout_test.cc28
-rw-r--r--absl/container/internal/raw_hash_set.cc3
-rw-r--r--absl/container/internal/raw_hash_set.h33
-rw-r--r--absl/container/node_hash_set.h6
13 files changed, 611 insertions, 606 deletions
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel
index afc869f45aac..55aea3979f44 100644
--- a/absl/container/BUILD.bazel
+++ b/absl/container/BUILD.bazel
@@ -15,11 +15,11 @@
 #
 
 load(
-    "//absl:copts.bzl",
+    "//absl:copts/configure_copts.bzl",
     "ABSL_DEFAULT_COPTS",
-    "ABSL_TEST_COPTS",
     "ABSL_EXCEPTIONS_FLAG",
     "ABSL_EXCEPTIONS_FLAG_LINKOPTS",
+    "ABSL_TEST_COPTS",
 )
 
 package(default_visibility = ["//visibility:public"])
@@ -41,6 +41,8 @@ cc_test(
     copts = ABSL_TEST_COPTS,
     deps = [
         ":compressed_tuple",
+        "//absl/memory",
+        "//absl/utility",
         "@com_google_googletest//:gtest_main",
     ],
 )
@@ -462,6 +464,12 @@ cc_library(
 )
 
 cc_library(
+    name = "have_sse",
+    hdrs = ["internal/have_sse.h"],
+    copts = ABSL_DEFAULT_COPTS,
+)
+
+cc_library(
     name = "raw_hash_set",
     srcs = ["internal/raw_hash_set.cc"],
     hdrs = ["internal/raw_hash_set.h"],
@@ -471,6 +479,7 @@ cc_library(
         ":container_memory",
         ":hash_policy_traits",
         ":hashtable_debug_hooks",
+        ":have_sse",
         ":layout",
         "//absl/base:bits",
         "//absl/base:config",
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt
index 7cddd84bd693..9f78100468a5 100644
--- a/absl/container/CMakeLists.txt
+++ b/absl/container/CMakeLists.txt
@@ -30,7 +30,7 @@ absl_cc_library(
 absl_cc_library(
   NAME
     compressed_tuple
-  SRCS
+  HDRS
    "internal/compressed_tuple.h"
   DEPS
     absl::utility
@@ -44,6 +44,8 @@ absl_cc_test(
     "internal/compressed_tuple_test.cc"
   DEPS
     absl::compressed_tuple
+    absl::memory
+    absl::utility
     gmock_main
 )
 
@@ -452,6 +454,16 @@ absl_cc_library(
 
 absl_cc_library(
   NAME
+    have_sse
+  HDRS
+    "internal/have_sse.h"
+  COPTS
+    ${ABSL_DEFAULT_COPTS}
+  PUBLIC
+)
+
+absl_cc_library(
+  NAME
     node_hash_policy
   HDRS
     "internal/node_hash_policy.h"
@@ -494,15 +506,16 @@ absl_cc_library(
   COPTS
     ${ABSL_DEFAULT_COPTS}
   DEPS
+    absl::bits
     absl::compressed_tuple
+    absl::config
     absl::container_memory
+    absl::core_headers
+    absl::endian
     absl::hash_policy_traits
     absl::hashtable_debug_hooks
+    absl::have_sse
     absl::layout
-    absl::bits
-    absl::config
-    absl::core_headers
-    absl::endian
     absl::memory
     absl::meta
     absl::optional
diff --git a/absl/container/flat_hash_set.h b/absl/container/flat_hash_set.h
index 5ea6a81652d0..84984cc4927b 100644
--- a/absl/container/flat_hash_set.h
+++ b/absl/container/flat_hash_set.h
@@ -279,8 +279,7 @@ class flat_hash_set
   //
   // The element may be constructed even if there already is an element with the
   // key in the container, in which case the newly constructed element will be
-  // destroyed immediately. Prefer `try_emplace()` unless your key is not
-  // copyable or moveable.
+  // destroyed immediately.
   //
   // If rehashing occurs due to the insertion, all iterators are invalidated.
   using Base::emplace;
@@ -294,8 +293,7 @@ class flat_hash_set
   //
   // The element may be constructed even if there already is an element with the
   // key in the container, in which case the newly constructed element will be
-  // destroyed immediately. Prefer `try_emplace()` unless your key is not
-  // copyable or moveable.
+  // destroyed immediately.
   //
   // If rehashing occurs due to the insertion, all iterators are invalidated.
   using Base::emplace_hint;
diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h
index 642dae6cb907..fe228001bf2c 100644
--- a/absl/container/inlined_vector.h
+++ b/absl/container/inlined_vector.h
@@ -66,12 +66,11 @@ namespace absl {
 // designed to cover the same API footprint as covered by `std::vector`.
 template <typename T, size_t N, typename A = std::allocator<T>>
 class InlinedVector {
+  static_assert(N > 0, "InlinedVector requires inline capacity greater than 0");
   constexpr static typename A::size_type inlined_capacity() {
     return static_cast<typename A::size_type>(N);
   }
 
-  static_assert(inlined_capacity() > 0, "InlinedVector needs inlined capacity");
-
   template <typename Iterator>
   using DisableIfIntegral =
       absl::enable_if_t<!std::is_integral<Iterator>::value>;
@@ -131,7 +130,8 @@ class InlinedVector {
   InlinedVector(std::initializer_list<value_type> init_list,
                 const allocator_type& alloc = allocator_type())
       : allocator_and_tag_(alloc) {
-    AppendRange(init_list.begin(), init_list.end());
+    AppendRange(init_list.begin(), init_list.end(),
+                IteratorCategory<decltype(init_list.begin())>{});
   }
 
   // Creates an inlined vector with elements constructed from the provided
@@ -144,14 +144,25 @@ class InlinedVector {
   InlinedVector(InputIterator first, InputIterator last,
                 const allocator_type& alloc = allocator_type())
       : allocator_and_tag_(alloc) {
-    AppendRange(first, last);
+    AppendRange(first, last, IteratorCategory<InputIterator>{});
   }
 
   // Creates a copy of `other` using `other`'s allocator.
-  InlinedVector(const InlinedVector& other);
+  InlinedVector(const InlinedVector& other)
+      : InlinedVector(other, other.get_allocator()) {}
 
   // Creates a copy of `other` but with a specified allocator.
-  InlinedVector(const InlinedVector& other, const allocator_type& alloc);
+  InlinedVector(const InlinedVector& other, const allocator_type& alloc)
+      : allocator_and_tag_(alloc) {
+    reserve(other.size());
+    if (allocated()) {
+      UninitializedCopy(other.begin(), other.end(), allocated_space());
+      tag().set_allocated_size(other.size());
+    } else {
+      UninitializedCopy(other.begin(), other.end(), inlined_space());
+      tag().set_inline_size(other.size());
+    }
+  }
 
   // Creates an inlined vector by moving in the contents of `other`.
   //
@@ -163,9 +174,22 @@ class InlinedVector {
   //     allocation function as the `InlinedVector`'s allocator, so the move
   //     constructor is non-throwing if the allocator is non-throwing or
   //     `value_type`'s move constructor is specified as `noexcept`.
-  InlinedVector(InlinedVector&& v) noexcept(
+  InlinedVector(InlinedVector&& other) noexcept(
       absl::allocator_is_nothrow<allocator_type>::value ||
-      std::is_nothrow_move_constructible<value_type>::value);
+      std::is_nothrow_move_constructible<value_type>::value)
+      : allocator_and_tag_(other.allocator_and_tag_) {
+    if (other.allocated()) {
+      // We can just steal the underlying buffer from the source.
+      // That leaves the source empty, so we clear its size.
+      init_allocation(other.allocation());
+      other.tag() = Tag();
+    } else {
+      UninitializedCopy(
+          std::make_move_iterator(other.inlined_space()),
+          std::make_move_iterator(other.inlined_space() + other.size()),
+          inlined_space());
+    }
+  }
 
   // Creates an inlined vector by moving in the contents of `other`.
   //
@@ -175,8 +199,31 @@ class InlinedVector {
   // same assumptions as above, the `noexcept` specification is dominated by
   // whether the allocation can throw regardless of whether `value_type`'s move
   // constructor is specified as `noexcept`.
-  InlinedVector(InlinedVector&& v, const allocator_type& alloc) noexcept(
-      absl::allocator_is_nothrow<allocator_type>::value);
+  InlinedVector(InlinedVector&& other, const allocator_type& alloc) noexcept(
+      absl::allocator_is_nothrow<allocator_type>::value)
+      : allocator_and_tag_(alloc) {
+    if (other.allocated()) {
+      if (alloc == other.allocator()) {
+        // We can just steal the allocation from the source.
+        tag() = other.tag();
+        init_allocation(other.allocation());
+        other.tag() = Tag();
+      } else {
+        // We need to use our own allocator
+        reserve(other.size());
+        UninitializedCopy(std::make_move_iterator(other.begin()),
+                          std::make_move_iterator(other.end()),
+                          allocated_space());
+        tag().set_allocated_size(other.size());
+      }
+    } else {
+      UninitializedCopy(
+          std::make_move_iterator(other.inlined_space()),
+          std::make_move_iterator(other.inlined_space() + other.size()),
+          inlined_space());
+      tag().set_inline_size(other.size());
+    }
+  }
 
   ~InlinedVector() { clear(); }
 
@@ -255,7 +302,7 @@ class InlinedVector {
   reference at(size_type i) {
     if (ABSL_PREDICT_FALSE(i >= size())) {
       base_internal::ThrowStdOutOfRange(
-          "InlinedVector::at() failed bounds check");
+          "`InlinedVector::at(size_type)` failed bounds check");
     }
     return data()[i];
   }
@@ -265,7 +312,7 @@ class InlinedVector {
   const_reference at(size_type i) const {
     if (ABSL_PREDICT_FALSE(i >= size())) {
       base_internal::ThrowStdOutOfRange(
-          "InlinedVector::at() failed bounds check");
+          "`InlinedVector::at(size_type) const` failed bounds check");
     }
     return data()[i];
   }
@@ -366,7 +413,6 @@ class InlinedVector {
   // Returns a copy of the allocator of the inlined vector.
   allocator_type get_allocator() const { return allocator(); }
 
-
   // ---------------------------------------------------------------------------
   // InlinedVector Member Mutators
   // ---------------------------------------------------------------------------
@@ -376,7 +422,8 @@ class InlinedVector {
   // Replaces the contents of the inlined vector with copies of the elements in
   // the provided `std::initializer_list`.
   InlinedVector& operator=(std::initializer_list<value_type> init_list) {
-    AssignRange(init_list.begin(), init_list.end());
+    AssignRange(init_list.begin(), init_list.end(),
+                IteratorCategory<decltype(init_list.begin())>{});
     return *this;
   }
 
@@ -453,14 +500,15 @@ class InlinedVector {
   // inlined vector with copies of the values in the provided
   // `std::initializer_list`.
   void assign(std::initializer_list<value_type> init_list) {
-    AssignRange(init_list.begin(), init_list.end());
+    AssignRange(init_list.begin(), init_list.end(),
+                IteratorCategory<decltype(init_list.begin())>{});
   }
 
   // Overload of `InlinedVector::assign()` to replace the contents of the
   // inlined vector with values constructed from the range [`first`, `last`).
   template <typename InputIterator, DisableIfIntegral<InputIterator>* = nullptr>
   void assign(InputIterator first, InputIterator last) {
-    AssignRange(first, last);
+    AssignRange(first, last, IteratorCategory<InputIterator>{});
   }
 
   // `InlinedVector::resize()`
@@ -468,12 +516,46 @@ class InlinedVector {
   // Resizes the inlined vector to contain `n` elements. If `n` is smaller than
   // the inlined vector's current size, extra elements are destroyed. If `n` is
   // larger than the initial size, new elements are value-initialized.
-  void resize(size_type n);
+  void resize(size_type n) {
+    size_type s = size();
+    if (n < s) {
+      erase(begin() + n, end());
+      return;
+    }
+    reserve(n);
+    assert(capacity() >= n);
+
+    // Fill new space with elements constructed in-place.
+    if (allocated()) {
+      UninitializedFill(allocated_space() + s, allocated_space() + n);
+      tag().set_allocated_size(n);
+    } else {
+      UninitializedFill(inlined_space() + s, inlined_space() + n);
+      tag().set_inline_size(n);
+    }
+  }
 
   // Overload of `InlinedVector::resize()` to resize the inlined vector to
   // contain `n` elements where, if `n` is larger than `size()`, the new values
   // will be copy-constructed from `v`.
-  void resize(size_type n, const_reference v);
+  void resize(size_type n, const_reference v) {
+    size_type s = size();
+    if (n < s) {
+      erase(begin() + n, end());
+      return;
+    }
+    reserve(n);
+    assert(capacity() >= n);
+
+    // Fill new space with copies of `v`.
+    if (allocated()) {
+      UninitializedFill(allocated_space() + s, allocated_space() + n, v);
+      tag().set_allocated_size(n);
+    } else {
+      UninitializedFill(inlined_space() + s, inlined_space() + n, v);
+      tag().set_inline_size(n);
+    }
+  }
 
   // `InlinedVector::insert()`
   //
@@ -523,7 +605,27 @@ class InlinedVector {
   // Constructs and inserts an object in the inlined vector at the given
   // `position`, returning an `iterator` pointing to the newly emplaced element.
   template <typename... Args>
-  iterator emplace(const_iterator position, Args&&... args);
+  iterator emplace(const_iterator position, Args&&... args) {
+    assert(position >= begin());
+    assert(position <= end());
+    if (ABSL_PREDICT_FALSE(position == end())) {
+      emplace_back(std::forward<Args>(args)...);
+      return end() - 1;
+    }
+
+    T new_t = T(std::forward<Args>(args)...);
+
+    auto range = ShiftRight(position, 1);
+    if (range.first == range.second) {
+      // constructing into uninitialized memory
+      Construct(range.first, std::move(new_t));
+    } else {
+      // assigning into moved-from object
+      *range.first = T(std::move(new_t));
+    }
+
+    return range.first;
+  }
 
   // `InlinedVector::emplace_back()`
   //
@@ -596,7 +698,30 @@ class InlinedVector {
   // range [`from`, `to`) in the inlined vector. Returns an `iterator` pointing
   // to the first element following the range erased or the end iterator if `to`
   // was the end iterator.
-  iterator erase(const_iterator from, const_iterator to);
+  iterator erase(const_iterator from, const_iterator to) {
+    assert(begin() <= from);
+    assert(from <= to);
+    assert(to <= end());
+
+    iterator range_start = const_cast<iterator>(from);
+    iterator range_end = const_cast<iterator>(to);
+
+    size_type s = size();
+    ptrdiff_t erase_gap = std::distance(range_start, range_end);
+    if (erase_gap > 0) {
+      pointer space;
+      if (allocated()) {
+        space = allocated_space();
+        tag().set_allocated_size(s - erase_gap);
+      } else {
+        space = inlined_space();
+        tag().set_inline_size(s - erase_gap);
+      }
+      std::move(range_end, space + s, range_start);
+      Destroy(space + s - erase_gap, space + s);
+    }
+    return range_start;
+  }
 
   // `InlinedVector::clear()`
   //
@@ -667,16 +792,88 @@ class InlinedVector {
   // `InlinedVector::swap()`
   //
   // Swaps the contents of this inlined vector with the contents of `other`.
-  void swap(InlinedVector& other);
+  void swap(InlinedVector& other) {
+    if (ABSL_PREDICT_FALSE(this == &other)) return;
+
+    using std::swap;  // Augment ADL with `std::swap`.
+    if (allocated() && other.allocated()) {
+      // Both out of line, so just swap the tag, allocation, and allocator.
+      swap(tag(), other.tag());
+      swap(allocation(), other.allocation());
+      swap(allocator(), other.allocator());
+      return;
+    }
+    if (!allocated() && !other.allocated()) {
+      // Both inlined: swap up to smaller size, then move remaining elements.
+      InlinedVector* a = this;
+      InlinedVector* b = &other;
+      if (size() < other.size()) {
+        swap(a, b);
+      }
 
-  template <typename Hash>
-  friend Hash AbslHashValue(Hash hash, const InlinedVector& inlined_vector) {
-    const_pointer p = inlined_vector.data();
-    size_type n = inlined_vector.size();
-    return Hash::combine(Hash::combine_contiguous(std::move(hash), p, n), n);
+      const size_type a_size = a->size();
+      const size_type b_size = b->size();
+      assert(a_size >= b_size);
+      // `a` is larger. Swap the elements up to the smaller array size.
+      std::swap_ranges(a->inlined_space(), a->inlined_space() + b_size,
+                       b->inlined_space());
+
+      // Move the remaining elements:
+      //   [`b_size`, `a_size`) from `a` -> [`b_size`, `a_size`) from `b`
+      b->UninitializedCopy(a->inlined_space() + b_size,
+                           a->inlined_space() + a_size,
+                           b->inlined_space() + b_size);
+      a->Destroy(a->inlined_space() + b_size, a->inlined_space() + a_size);
+
+      swap(a->tag(), b->tag());
+      swap(a->allocator(), b->allocator());
+      assert(b->size() == a_size);
+      assert(a->size() == b_size);
+      return;
+    }
+
+    // One is out of line, one is inline.
+    // We first move the elements from the inlined vector into the
+    // inlined space in the other vector.  We then put the other vector's
+    // pointer/capacity into the originally inlined vector and swap
+    // the tags.
+    InlinedVector* a = this;
+    InlinedVector* b = &other;
+    if (a->allocated()) {
+      swap(a, b);
+    }
+    assert(!a->allocated());
+    assert(b->allocated());
+    const size_type a_size = a->size();
+    const size_type b_size = b->size();
+    // In an optimized build, `b_size` would be unused.
+    static_cast<void>(b_size);
+
+    // Made Local copies of `size()`, don't need `tag()` accurate anymore
+    swap(a->tag(), b->tag());
+
+    // Copy `b_allocation` out before `b`'s union gets clobbered by
+    // `inline_space`
+    Allocation b_allocation = b->allocation();
+
+    b->UninitializedCopy(a->inlined_space(), a->inlined_space() + a_size,
+                         b->inlined_space());
+    a->Destroy(a->inlined_space(), a->inlined_space() + a_size);
+
+    a->allocation() = b_allocation;
+
+    if (a->allocator() != b->allocator()) {
+      swap(a->allocator(), b->allocator());
+    }
+
+    assert(b->size() == a_size);
+    assert(a->size() == b_size);
   }
 
  private:
+  template <typename Hash, typename OtherT, size_t OtherN, typename OtherA>
+  friend Hash AbslHashValue(Hash, const InlinedVector<OtherT, OtherN, OtherA>&);
+
   // Holds whether the vector is allocated or not in the lowest bit and the size
   // in the high bits:
   //   `size_ = (size << 1) | is_allocated;`
@@ -773,10 +970,76 @@ class InlinedVector {
 
   bool allocated() const { return tag().allocated(); }
 
+  void ResetAllocation(Allocation new_allocation, size_type new_size) {
+    if (allocated()) {
+      Destroy(allocated_space(), allocated_space() + size());
+      assert(begin() == allocated_space());
+      allocation().Dealloc(allocator());
+      allocation() = new_allocation;
+    } else {
+      Destroy(inlined_space(), inlined_space() + size());
+      init_allocation(new_allocation);  // bug: only init once
+    }
+    tag().set_allocated_size(new_size);
+  }
+
+  template <typename... Args>
+  reference Construct(pointer p, Args&&... args) {
+    std::allocator_traits<allocator_type>::construct(
+        allocator(), p, std::forward<Args>(args)...);
+    return *p;
+  }
+
+  template <typename Iterator>
+  void UninitializedCopy(Iterator src, Iterator src_last, pointer dst) {
+    for (; src != src_last; ++dst, ++src) Construct(dst, *src);
+  }
+
+  template <typename... Args>
+  void UninitializedFill(pointer dst, pointer dst_last, const Args&... args) {
+    for (; dst != dst_last; ++dst) Construct(dst, args...);
+  }
+
+  // Destroy [`from`, `to`) in place.
+  void Destroy(pointer from, pointer to) {
+    for (pointer cur = from; cur != to; ++cur) {
+      std::allocator_traits<allocator_type>::destroy(allocator(), cur);
+    }
+#if !defined(NDEBUG)
+    // Overwrite unused memory with `0xab` so we can catch uninitialized usage.
+    // Cast to `void*` to tell the compiler that we don't care that we might be
+    // scribbling on a vtable pointer.
+    if (from != to) {
+      auto len = sizeof(value_type) * std::distance(from, to);
+      std::memset(reinterpret_cast<void*>(from), 0xab, len);
+    }
+#endif  // !defined(NDEBUG)
+  }
+
   // Enlarge the underlying representation so we can store `size_ + delta` elems
   // in allocated space. The size is not changed, and any newly added memory is
   // not initialized.
-  void EnlargeBy(size_type delta);
+  void EnlargeBy(size_type delta) {
+    const size_type s = size();
+    assert(s <= capacity());
+
+    size_type target = (std::max)(inlined_capacity(), s + delta);
+
+    // Compute new capacity by repeatedly doubling current capacity
+    // TODO(psrc): Check and avoid overflow?
+    size_type new_capacity = capacity();
+    while (new_capacity < target) {
+      new_capacity <<= 1;
+    }
+
+    Allocation new_allocation(allocator(), new_capacity);
+
+    UninitializedCopy(std::make_move_iterator(data()),
+                      std::make_move_iterator(data() + s),
+                      new_allocation.buffer());
+
+    ResetAllocation(new_allocation, s);
+  }
 
   // Shift all elements from `position` to `end()` by `n` places to the right.
   // If the vector needs to be enlarged, memory will be allocated.
@@ -787,19 +1050,61 @@ class InlinedVector {
   //
   // Updates the size of the InlinedVector internally.
   std::pair<iterator, iterator> ShiftRight(const_iterator position,
-                                           size_type n);
+                                           size_type n) {
+    iterator start_used = const_cast<iterator>(position);
+    iterator start_raw = const_cast<iterator>(position);
+    size_type s = size();
+    size_type required_size = s + n;
 
-  void ResetAllocation(Allocation new_allocation, size_type new_size) {
-    if (allocated()) {
-      Destroy(allocated_space(), allocated_space() + size());
-      assert(begin() == allocated_space());
-      allocation().Dealloc(allocator());
-      allocation() = new_allocation;
+    if (required_size > capacity()) {
+      // Compute new capacity by repeatedly doubling current capacity
+      size_type new_capacity = capacity();
+      while (new_capacity < required_size) {
+        new_capacity <<= 1;
+      }
+      // Move everyone into the new allocation, leaving a gap of `n` for the
+      // requested shift.
+      Allocation new_allocation(allocator(), new_capacity);
+      size_type index = position - begin();
+      UninitializedCopy(std::make_move_iterator(data()),
+                        std::make_move_iterator(data() + index),
+                        new_allocation.buffer());
+      UninitializedCopy(std::make_move_iterator(data() + index),
+                        std::make_move_iterator(data() + s),
+                        new_allocation.buffer() + index + n);
+      ResetAllocation(new_allocation, s);
+
+      // New allocation means our iterator is invalid, so we'll recalculate.
+      // Since the entire gap is in new space, there's no used space to reuse.
+      start_raw = begin() + index;
+      start_used = start_raw;
     } else {
-      Destroy(inlined_space(), inlined_space() + size());
-      init_allocation(new_allocation);  // bug: only init once
+      // If we had enough space, it's a two-part move. Elements going into
+      // previously-unoccupied space need an `UninitializedCopy()`. Elements
+      // going into a previously-occupied space are just a `std::move()`.
+      iterator pos = const_cast<iterator>(position);
+      iterator raw_space = end();
+      size_type slots_in_used_space = raw_space - pos;
+      size_type new_elements_in_used_space = (std::min)(n, slots_in_used_space);
+      size_type new_elements_in_raw_space = n - new_elements_in_used_space;
+      size_type old_elements_in_used_space =
+          slots_in_used_space - new_elements_in_used_space;
+
+      UninitializedCopy(
+          std::make_move_iterator(pos + old_elements_in_used_space),
+          std::make_move_iterator(raw_space),
+          raw_space + new_elements_in_raw_space);
+      std::move_backward(pos, pos + old_elements_in_used_space, raw_space);
+
+      // If the gap is entirely in raw space, the used space starts where the
+      // raw space starts, leaving no elements in used space. If the gap is
+      // entirely in used space, the raw space starts at the end of the gap,
+      // leaving all elements accounted for within the used space.
+      start_used = pos;
+      start_raw = pos + new_elements_in_used_space;
     }
-    tag().set_allocated_size(new_size);
+    tag().add_size(n);
+    return std::make_pair(start_used, start_raw);
   }
 
   template <typename... Args>
@@ -820,64 +1125,118 @@ class InlinedVector {
     return new_element;
   }
 
-  void InitAssign(size_type n);
-
-  void InitAssign(size_type n, const_reference v);
-
-  template <typename... Args>
-  reference Construct(pointer p, Args&&... args) {
-    std::allocator_traits<allocator_type>::construct(
-        allocator(), p, std::forward<Args>(args)...);
-    return *p;
+  void InitAssign(size_type n) {
+    if (n > inlined_capacity()) {
+      Allocation new_allocation(allocator(), n);
+      init_allocation(new_allocation);
+      UninitializedFill(allocated_space(), allocated_space() + n);
+      tag().set_allocated_size(n);
+    } else {
+      UninitializedFill(inlined_space(), inlined_space() + n);
+      tag().set_inline_size(n);
+    }
   }
 
-  template <typename Iterator>
-  void UninitializedCopy(Iterator src, Iterator src_last, pointer dst) {
-    for (; src != src_last; ++dst, ++src) Construct(dst, *src);
+  void InitAssign(size_type n, const_reference v) {
+    if (n > inlined_capacity()) {
+      Allocation new_allocation(allocator(), n);
+      init_allocation(new_allocation);
+      UninitializedFill(allocated_space(), allocated_space() + n, v);
+      tag().set_allocated_size(n);
+    } else {
+      UninitializedFill(inlined_space(), inlined_space() + n, v);
+      tag().set_inline_size(n);
+    }
   }
 
-  template <typename... Args>
-  void UninitializedFill(pointer dst, pointer dst_last, const Args&... args) {
-    for (; dst != dst_last; ++dst) Construct(dst, args...);
+  template <typename Iterator>
+  void AssignRange(Iterator first, Iterator last, std::forward_iterator_tag) {
+    auto length = std::distance(first, last);
+    // Prefer reassignment to copy construction for elements.
+    if (static_cast<size_type>(length) <= size()) {
+      erase(std::copy(first, last, begin()), end());
+      return;
+    }
+    reserve(length);
+    iterator out = begin();
+    for (; out != end(); ++first, ++out) *out = *first;
+    if (allocated()) {
+      UninitializedCopy(first, last, out);
+      tag().set_allocated_size(length);
+    } else {
+      UninitializedCopy(first, last, out);
+      tag().set_inline_size(length);
+    }
   }
 
-  // Destroy [`from`, `to`) in place.
-  void Destroy(pointer from, pointer to);
-
   template <typename Iterator>
-  void AppendRange(Iterator first, Iterator last, std::input_iterator_tag) {
+  void AssignRange(Iterator first, Iterator last, std::input_iterator_tag) {
+    // Optimized to avoid reallocation.
+    // Prefer reassignment to copy construction for elements.
+    iterator out = begin();
+    for (; first != last && out != end(); ++first, ++out) {
+      *out = *first;
+    }
+    erase(out, end());
     std::copy(first, last, std::back_inserter(*this));
   }
 
   template <typename Iterator>
-  void AppendRange(Iterator first, Iterator last, std::forward_iterator_tag);
+  void AppendRange(Iterator first, Iterator last, std::forward_iterator_tag) {
+    auto length = std::distance(first, last);
+    reserve(size() + length);
+    if (allocated()) {
+      UninitializedCopy(first, last, allocated_space() + size());
+      tag().set_allocated_size(size() + length);
+    } else {
+      UninitializedCopy(first, last, inlined_space() + size());
+      tag().set_inline_size(size() + length);
+    }
+  }
 
   template <typename Iterator>
-  void AppendRange(Iterator first, Iterator last) {
-    AppendRange(first, last, IteratorCategory<Iterator>());
+  void AppendRange(Iterator first, Iterator last, std::input_iterator_tag) {
+    std::copy(first, last, std::back_inserter(*this));
   }
 
-  template <typename Iterator>
-  void AssignRange(Iterator first, Iterator last, std::input_iterator_tag);
+  iterator InsertWithCount(const_iterator position, size_type n,
+                           const_reference v) {
+    assert(position >= begin() && position <= end());
+    if (ABSL_PREDICT_FALSE(n == 0)) return const_cast<iterator>(position);
 
-  template <typename Iterator>
-  void AssignRange(Iterator first, Iterator last, std::forward_iterator_tag);
+    value_type copy = v;
+    std::pair<iterator, iterator> it_pair = ShiftRight(position, n);
+    std::fill(it_pair.first, it_pair.second, copy);
+    UninitializedFill(it_pair.second, it_pair.first + n, copy);
 
-  template <typename Iterator>
-  void AssignRange(Iterator first, Iterator last) {
-    AssignRange(first, last, IteratorCategory<Iterator>());
+    return it_pair.first;
   }
 
-  iterator InsertWithCount(const_iterator position, size_type n,
-                           const_reference v);
+  template <typename ForwardIterator>
+  iterator InsertWithRange(const_iterator position, ForwardIterator first,
+                           ForwardIterator last, std::forward_iterator_tag) {
+    assert(position >= begin() && position <= end());
+    if (ABSL_PREDICT_FALSE(first == last))
+      return const_cast<iterator>(position);
+
+    auto n = std::distance(first, last);
+    std::pair<iterator, iterator> it_pair = ShiftRight(position, n);
+    size_type used_spots = it_pair.second - it_pair.first;
+    ForwardIterator open_spot = std::next(first, used_spots);
+    std::copy(first, open_spot, it_pair.first);
+    UninitializedCopy(open_spot, last, it_pair.second);
+    return it_pair.first;
+  }
 
   template <typename InputIterator>
   iterator InsertWithRange(const_iterator position, InputIterator first,
-                           InputIterator last, std::input_iterator_tag);
-
-  template <typename ForwardIterator>
-  iterator InsertWithRange(const_iterator position, ForwardIterator first,
-                           ForwardIterator last, std::forward_iterator_tag);
+                           InputIterator last, std::input_iterator_tag) {
+    assert(position >= begin() && position <= end());
+    size_type index = position - cbegin();
+    size_type i = index;
+    while (first != last) insert(begin() + i++, *first++);
+    return begin() + index;
+  }
 
   // Stores either the inlined or allocated representation
   union Rep {
@@ -889,7 +1248,7 @@ class InlinedVector {
     // Structs wrap the buffers to perform indirection that solves a bizarre
     // compilation error on Visual Studio (all known versions).
     struct InlinedRep {
-      ValueTypeBuffer inlined[inlined_capacity()];
+      ValueTypeBuffer inlined[N];
     };
     struct AllocatedRep {
       AllocationBuffer allocation;
@@ -975,477 +1334,19 @@ bool operator>=(const InlinedVector<T, N, A>& a,
   return !(a < b);
 }
 
+template <typename Hash, typename T, size_t N, typename A>
+Hash AbslHashValue(Hash hash, const InlinedVector<T, N, A>& inlined_vector) {
+  auto p = inlined_vector.data();
+  auto n = inlined_vector.size();
+  return Hash::combine(Hash::combine_contiguous(std::move(hash), p, n), n);
+}
+
 // -----------------------------------------------------------------------------
 // Implementation of InlinedVector
 //
 // Do not depend on any below implementation details!
 // -----------------------------------------------------------------------------
 
-template <typename T, size_t N, typename A>
-InlinedVector<T, N, A>::InlinedVector(const InlinedVector& other)
-    : allocator_and_tag_(other.allocator()) {
-  reserve(other.size());
-  if (allocated()) {
-    UninitializedCopy(other.begin(), other.end(), allocated_space());
-    tag().set_allocated_size(other.size());
-  } else {
-    UninitializedCopy(other.begin(), other.end(), inlined_space());
-    tag().set_inline_size(other.size());
-  }
-}
-
-template <typename T, size_t N, typename A>
-InlinedVector<T, N, A>::InlinedVector(const InlinedVector& other,
-                                      const allocator_type& alloc)
-    : allocator_and_tag_(alloc) {
-  reserve(other.size());
-  if (allocated()) {
-    UninitializedCopy(other.begin(), other.end(), allocated_space());
-    tag().set_allocated_size(other.size());
-  } else {
-    UninitializedCopy(other.begin(), other.end(), inlined_space());
-    tag().set_inline_size(other.size());
-  }
-}
-
-template <typename T, size_t N, typename A>
-InlinedVector<T, N, A>::InlinedVector(InlinedVector&& other) noexcept(
-    absl::allocator_is_nothrow<allocator_type>::value ||
-    std::is_nothrow_move_constructible<value_type>::value)
-    : allocator_and_tag_(other.allocator_and_tag_) {
-  if (other.allocated()) {
-    // We can just steal the underlying buffer from the source.
-    // That leaves the source empty, so we clear its size.
-    init_allocation(other.allocation());
-    other.tag() = Tag();
-  } else {
-    UninitializedCopy(
-        std::make_move_iterator(other.inlined_space()),
-        std::make_move_iterator(other.inlined_space() + other.size()),
-        inlined_space());
-  }
-}
-
-template <typename T, size_t N, typename A>
-InlinedVector<T, N, A>::InlinedVector(InlinedVector&& other,
-                                      const allocator_type& alloc) noexcept(  //
-    absl::allocator_is_nothrow<allocator_type>::value)
-    : allocator_and_tag_(alloc) {
-  if (other.allocated()) {
-    if (alloc == other.allocator()) {
-      // We can just steal the allocation from the source.
-      tag() = other.tag();
-      init_allocation(other.allocation());
-      other.tag() = Tag();
-    } else {
-      // We need to use our own allocator
-      reserve(other.size());
-      UninitializedCopy(std::make_move_iterator(other.begin()),
-                        std::make_move_iterator(other.end()),
-                        allocated_space());
-      tag().set_allocated_size(other.size());
-    }
-  } else {
-    UninitializedCopy(
-        std::make_move_iterator(other.inlined_space()),
-        std::make_move_iterator(other.inlined_space() + other.size()),
-        inlined_space());
-    tag().set_inline_size(other.size());
-  }
-}
-
-template <typename T, size_t N, typename A>
-void InlinedVector<T, N, A>::InitAssign(size_type n, const_reference v) {
-  if (n > inlined_capacity()) {
-    Allocation new_allocation(allocator(), n);
-    init_allocation(new_allocation);
-    UninitializedFill(allocated_space(), allocated_space() + n, v);
-    tag().set_allocated_size(n);
-  } else {
-    UninitializedFill(inlined_space(), inlined_space() + n, v);
-    tag().set_inline_size(n);
-  }
-}
-
-template <typename T, size_t N, typename A>
-void InlinedVector<T, N, A>::InitAssign(size_type n) {
-  if (n > inlined_capacity()) {
-    Allocation new_allocation(allocator(), n);
-    init_allocation(new_allocation);
-    UninitializedFill(allocated_space(), allocated_space() + n);
-    tag().set_allocated_size(n);
-  } else {
-    UninitializedFill(inlined_space(), inlined_space() + n);
-    tag().set_inline_size(n);
-  }
-}
-
-template <typename T, size_t N, typename A>
-void InlinedVector<T, N, A>::resize(size_type n) {
-  size_type s = size();
-  if (n < s) {
-    erase(begin() + n, end());
-    return;
-  }
-  reserve(n);
-  assert(capacity() >= n);
-
-  // Fill new space with elements constructed in-place.
-  if (allocated()) {
-    UninitializedFill(allocated_space() + s, allocated_space() + n);
-    tag().set_allocated_size(n);
-  } else {
-    UninitializedFill(inlined_space() + s, inlined_space() + n);
-    tag().set_inline_size(n);
-  }
-}
-
-template <typename T, size_t N, typename A>
-void InlinedVector<T, N, A>::resize(size_type n, const_reference v) {
-  size_type s = size();
-  if (n < s) {
-    erase(begin() + n, end());
-    return;
-  }
-  reserve(n);
-  assert(capacity() >= n);
-
-  // Fill new space with copies of 'v'.
-  if (allocated()) {
-    UninitializedFill(allocated_space() + s, allocated_space() + n, v);
-    tag().set_allocated_size(n);
-  } else {
-    UninitializedFill(inlined_space() + s, inlined_space() + n, v);
-    tag().set_inline_size(n);
-  }
-}
-
-template <typename T, size_t N, typename A>
-template <typename... Args>
-auto InlinedVector<T, N, A>::emplace(const_iterator position, Args&&... args)
-    -> iterator {
-  assert(position >= begin());
-  assert(position <= end());
-  if (ABSL_PREDICT_FALSE(position == end())) {
-    emplace_back(std::forward<Args>(args)...);
-    return end() - 1;
-  }
-
-  T new_t = T(std::forward<Args>(args)...);
-
-  auto range = ShiftRight(position, 1);
-  if (range.first == range.second) {
-    // constructing into uninitialized memory
-    Construct(range.first, std::move(new_t));
-  } else {
-    // assigning into moved-from object
-    *range.first = T(std::move(new_t));
-  }
-
-  return range.first;
-}
-
-template <typename T, size_t N, typename A>
-auto InlinedVector<T, N, A>::erase(const_iterator from, const_iterator to)
-    -> iterator {
-  assert(begin() <= from);
-  assert(from <= to);
-  assert(to <= end());
-
-  iterator range_start = const_cast<iterator>(from);
-  iterator range_end = const_cast<iterator>(to);
-
-  size_type s = size();
-  ptrdiff_t erase_gap = std::distance(range_start, range_end);
-  if (erase_gap > 0) {
-    pointer space;
-    if (allocated()) {
-      space = allocated_space();
-      tag().set_allocated_size(s - erase_gap);
-    } else {
-      space = inlined_space();
-      tag().set_inline_size(s - erase_gap);
-    }
-    std::move(range_end, space + s, range_start);
-    Destroy(space + s - erase_gap, space + s);
-  }
-  return range_start;
-}
-
-template <typename T, size_t N, typename A>
-void InlinedVector<T, N, A>::swap(InlinedVector& other) {
-  using std::swap;  // Augment ADL with `std::swap`.
-  if (ABSL_PREDICT_FALSE(this == &other)) return;
-
-  if (allocated() && other.allocated()) {
-    // Both out of line, so just swap the tag, allocation, and allocator.
-    swap(tag(), other.tag());
-    swap(allocation(), other.allocation());
-    swap(allocator(), other.allocator());
-    return;
-  }
-  if (!allocated() && !other.allocated()) {
-    // Both inlined: swap up to smaller size, then move remaining elements.
-    InlinedVector* a = this;
-    InlinedVector* b = &other;
-    if (size() < other.size()) {
-      swap(a, b);
-    }
-
-    const size_type a_size = a->size();
-    const size_type b_size = b->size();
-    assert(a_size >= b_size);
-    // `a` is larger. Swap the elements up to the smaller array size.
-    std::swap_ranges(a->inlined_space(), a->inlined_space() + b_size,
-                     b->inlined_space());
-
-    // Move the remaining elements:
-    //   [`b_size`, `a_size`) from `a` -> [`b_size`, `a_size`) from `b`
-    b->UninitializedCopy(a->inlined_space() + b_size,
-                         a->inlined_space() + a_size,
-                         b->inlined_space() + b_size);
-    a->Destroy(a->inlined_space() + b_size, a->inlined_space() + a_size);
-
-    swap(a->tag(), b->tag());
-    swap(a->allocator(), b->allocator());
-    assert(b->size() == a_size);
-    assert(a->size() == b_size);
-    return;
-  }
-
-  // One is out of line, one is inline.
-  // We first move the elements from the inlined vector into the
-  // inlined space in the other vector.  We then put the other vector's
-  // pointer/capacity into the originally inlined vector and swap
-  // the tags.
-  InlinedVector* a = this;
-  InlinedVector* b = &other;
-  if (a->allocated()) {
-    swap(a, b);
-  }
-  assert(!a->allocated());
-  assert(b->allocated());
-  const size_type a_size = a->size();
-  const size_type b_size = b->size();
-  // In an optimized build, `b_size` would be unused.
-  static_cast<void>(b_size);
-
-  // Made Local copies of `size()`, don't need `tag()` accurate anymore
-  swap(a->tag(), b->tag());
-
-  // Copy `b_allocation` out before `b`'s union gets clobbered by `inline_space`
-  Allocation b_allocation = b->allocation();
-
-  b->UninitializedCopy(a->inlined_space(), a->inlined_space() + a_size,
-                       b->inlined_space());
-  a->Destroy(a->inlined_space(), a->inlined_space() + a_size);
-
-  a->allocation() = b_allocation;
-
-  if (a->allocator() != b->allocator()) {
-    swap(a->allocator(), b->allocator());
-  }
-
-  assert(b->size() == a_size);
-  assert(a->size() == b_size);
-}
-
-template <typename T, size_t N, typename A>
-void InlinedVector<T, N, A>::EnlargeBy(size_type delta) {
-  const size_type s = size();
-  assert(s <= capacity());
-
-  size_type target = std::max(inlined_capacity(), s + delta);
-
-  // Compute new capacity by repeatedly doubling current capacity
-  // TODO(psrc): Check and avoid overflow?
-  size_type new_capacity = capacity();
-  while (new_capacity < target) {
-    new_capacity <<= 1;
-  }
-
-  Allocation new_allocation(allocator(), new_capacity);
-
-  UninitializedCopy(std::make_move_iterator(data()),
-                    std::make_move_iterator(data() + s),
-                    new_allocation.buffer());
-
-  ResetAllocation(new_allocation, s);
-}
-
-template <typename T, size_t N, typename A>
-auto InlinedVector<T, N, A>::ShiftRight(const_iterator position, size_type n)
-    -> std::pair<iterator, iterator> {
-  iterator start_used = const_cast<iterator>(position);
-  iterator start_raw = const_cast<iterator>(position);
-  size_type s = size();
-  size_type required_size = s + n;
-
-  if (required_size > capacity()) {
-    // Compute new capacity by repeatedly doubling current capacity
-    size_type new_capacity = capacity();
-    while (new_capacity < required_size) {
-      new_capacity <<= 1;
-    }
-    // Move everyone into the new allocation, leaving a gap of `n` for the
-    // requested shift.
-    Allocation new_allocation(allocator(), new_capacity);
-    size_type index = position - begin();
-    UninitializedCopy(std::make_move_iterator(data()),
-                      std::make_move_iterator(data() + index),
-                      new_allocation.buffer());
-    UninitializedCopy(std::make_move_iterator(data() + index),
-                      std::make_move_iterator(data() + s),
-                      new_allocation.buffer() + index + n);
-    ResetAllocation(new_allocation, s);
-
-    // New allocation means our iterator is invalid, so we'll recalculate.
-    // Since the entire gap is in new space, there's no used space to reuse.
-    start_raw = begin() + index;
-    start_used = start_raw;
-  } else {
-    // If we had enough space, it's a two-part move. Elements going into
-    // previously-unoccupied space need an `UninitializedCopy()`. Elements
-    // going into a previously-occupied space are just a `std::move()`.
-    iterator pos = const_cast<iterator>(position);
-    iterator raw_space = end();
-    size_type slots_in_used_space = raw_space - pos;
-    size_type new_elements_in_used_space = std::min(n, slots_in_used_space);
-    size_type new_elements_in_raw_space = n - new_elements_in_used_space;
-    size_type old_elements_in_used_space =
-        slots_in_used_space - new_elements_in_used_space;
-
-    UninitializedCopy(std::make_move_iterator(pos + old_elements_in_used_space),
-                      std::make_move_iterator(raw_space),
-                      raw_space + new_elements_in_raw_space);
-    std::move_backward(pos, pos + old_elements_in_used_space, raw_space);
-
-    // If the gap is entirely in raw space, the used space starts where the raw
-    // space starts, leaving no elements in used space. If the gap is entirely
-    // in used space, the raw space starts at the end of the gap, leaving all
-    // elements accounted for within the used space.
-    start_used = pos;
-    start_raw = pos + new_elements_in_used_space;
-  }
-  tag().add_size(n);
-  return std::make_pair(start_used, start_raw);
-}
-
-template <typename T, size_t N, typename A>
-void InlinedVector<T, N, A>::Destroy(pointer from, pointer to) {
-  for (pointer cur = from; cur != to; ++cur) {
-    std::allocator_traits<allocator_type>::destroy(allocator(), cur);
-  }
-#ifndef NDEBUG
-  // Overwrite unused memory with `0xab` so we can catch uninitialized usage.
-  // Cast to `void*` to tell the compiler that we don't care that we might be
-  // scribbling on a vtable pointer.
-  if (from != to) {
-    auto len = sizeof(value_type) * std::distance(from, to);
-    std::memset(reinterpret_cast<void*>(from), 0xab, len);
-  }
-#endif
-}
-
-template <typename T, size_t N, typename A>
-template <typename Iterator>
-void InlinedVector<T, N, A>::AppendRange(Iterator first, Iterator last,
-                                         std::forward_iterator_tag) {
-  auto length = std::distance(first, last);
-  reserve(size() + length);
-  if (allocated()) {
-    UninitializedCopy(first, last, allocated_space() + size());
-    tag().set_allocated_size(size() + length);
-  } else {
-    UninitializedCopy(first, last, inlined_space() + size());
-    tag().set_inline_size(size() + length);
-  }
-}
-
-template <typename T, size_t N, typename A>
-template <typename Iterator>
-void InlinedVector<T, N, A>::AssignRange(Iterator first, Iterator last,
-                                         std::input_iterator_tag) {
-  // Optimized to avoid reallocation.
-  // Prefer reassignment to copy construction for elements.
-  iterator out = begin();
-  for (; first != last && out != end(); ++first, ++out) {
-    *out = *first;
-  }
-  erase(out, end());
-  std::copy(first, last, std::back_inserter(*this));
-}
-
-template <typename T, size_t N, typename A>
-template <typename Iterator>
-void InlinedVector<T, N, A>::AssignRange(Iterator first, Iterator last,
-                                         std::forward_iterator_tag) {
-  auto length = std::distance(first, last);
-  // Prefer reassignment to copy construction for elements.
-  if (static_cast<size_type>(length) <= size()) {
-    erase(std::copy(first, last, begin()), end());
-    return;
-  }
-  reserve(length);
-  iterator out = begin();
-  for (; out != end(); ++first, ++out) *out = *first;
-  if (allocated()) {
-    UninitializedCopy(first, last, out);
-    tag().set_allocated_size(length);
-  } else {
-    UninitializedCopy(first, last, out);
-    tag().set_inline_size(length);
-  }
-}
-
-template <typename T, size_t N, typename A>
-auto InlinedVector<T, N, A>::InsertWithCount(const_iterator position,
-                                             size_type n, const_reference v)
-    -> iterator {
-  assert(position >= begin() && position <= end());
-  if (ABSL_PREDICT_FALSE(n == 0)) return const_cast<iterator>(position);
-
-  value_type copy = v;
-  std::pair<iterator, iterator> it_pair = ShiftRight(position, n);
-  std::fill(it_pair.first, it_pair.second, copy);
-  UninitializedFill(it_pair.second, it_pair.first + n, copy);
-
-  return it_pair.first;
-}
-
-template <typename T, size_t N, typename A>
-template <typename InputIterator>
-auto InlinedVector<T, N, A>::InsertWithRange(const_iterator position,
-                                             InputIterator first,
-                                             InputIterator last,
-                                             std::input_iterator_tag)
-    -> iterator {
-  assert(position >= begin() && position <= end());
-  size_type index = position - cbegin();
-  size_type i = index;
-  while (first != last) insert(begin() + i++, *first++);
-  return begin() + index;
-}
-
-template <typename T, size_t N, typename A>
-template <typename ForwardIterator>
-auto InlinedVector<T, N, A>::InsertWithRange(const_iterator position,
-                                             ForwardIterator first,
-                                             ForwardIterator last,
-                                             std::forward_iterator_tag)
-    -> iterator {
-  assert(position >= begin() && position <= end());
-  if (ABSL_PREDICT_FALSE(first == last)) return const_cast<iterator>(position);
-
-  auto n = std::distance(first, last);
-  std::pair<iterator, iterator> it_pair = ShiftRight(position, n);
-  size_type used_spots = it_pair.second - it_pair.first;
-  ForwardIterator open_spot = std::next(first, used_spots);
-  std::copy(first, open_spot, it_pair.first);
-  UninitializedCopy(open_spot, last, it_pair.second);
-  return it_pair.first;
-}
-
 }  // namespace absl
 
 #endif  // ABSL_CONTAINER_INLINED_VECTOR_H_
diff --git a/absl/container/internal/compressed_tuple.h b/absl/container/internal/compressed_tuple.h
index cc52614f5b37..b883ae2657ed 100644
--- a/absl/container/internal/compressed_tuple.h
+++ b/absl/container/internal/compressed_tuple.h
@@ -89,8 +89,10 @@ struct Storage {
   T value;
   constexpr Storage() = default;
   explicit constexpr Storage(T&& v) : value(absl::forward<T>(v)) {}
-  constexpr const T& get() const { return value; }
-  T& get() { return value; }
+  constexpr const T& get() const& { return value; }
+  T& get() & { return value; }
+  constexpr const T&& get() const&& { return absl::move(*this).value; }
+  T&& get() && { return std::move(*this).value; }
 };
 
 template <typename D, size_t I>
@@ -99,8 +101,10 @@ struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC Storage<D, I, true>
   using T = internal_compressed_tuple::ElemT<D, I>;
   constexpr Storage() = default;
   explicit constexpr Storage(T&& v) : T(absl::forward<T>(v)) {}
-  constexpr const T& get() const { return *this; }
-  T& get() { return *this; }
+  constexpr const T& get() const& { return *this; }
+  T& get() & { return *this; }
+  constexpr const T&& get() const&& { return absl::move(*this); }
+  T&& get() && { return std::move(*this); }
 };
 
 template <typename D, typename I>
@@ -152,14 +156,26 @@ class ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTuple
       : CompressedTuple::CompressedTupleImpl(absl::forward<Ts>(base)...) {}
 
   template <int I>
-  ElemT<I>& get() {
+  ElemT<I>& get() & {
     return internal_compressed_tuple::Storage<CompressedTuple, I>::get();
   }
 
   template <int I>
-  constexpr const ElemT<I>& get() const {
+  constexpr const ElemT<I>& get() const& {
     return internal_compressed_tuple::Storage<CompressedTuple, I>::get();
   }
+
+  template <int I>
+  ElemT<I>&& get() && {
+    return std::move(*this)
+        .internal_compressed_tuple::template Storage<CompressedTuple, I>::get();
+  }
+
+  template <int I>
+  constexpr const ElemT<I>&& get() const&& {
+    return absl::move(*this)
+        .internal_compressed_tuple::template Storage<CompressedTuple, I>::get();
+  }
 };
 
 // Explicit specialization for a zero-element tuple
diff --git a/absl/container/internal/compressed_tuple_test.cc b/absl/container/internal/compressed_tuple_test.cc
index 45030c675ee1..04ead100aa13 100644
--- a/absl/container/internal/compressed_tuple_test.cc
+++ b/absl/container/internal/compressed_tuple_test.cc
@@ -14,17 +14,25 @@
 
 #include "absl/container/internal/compressed_tuple.h"
 
+#include <memory>
 #include <string>
 
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
+#include "absl/memory/memory.h"
+#include "absl/utility/utility.h"
 
 namespace absl {
 namespace container_internal {
 namespace {
 
+enum class CallType { kConstRef, kConstMove };
+
 template <int>
-struct Empty {};
+struct Empty {
+  constexpr CallType value() const& { return CallType::kConstRef; }
+  constexpr CallType value() const&& { return CallType::kConstMove; }
+};
 
 template <typename T>
 struct NotEmpty {
@@ -140,15 +148,44 @@ TEST(CompressedTupleTest, NoElements) {
   EXPECT_TRUE(std::is_empty<CompressedTuple<>>::value);
 }
 
+TEST(CompressedTupleTest, MoveOnlyElements) {
+  CompressedTuple<std::unique_ptr<std::string>> str_tup(
+      absl::make_unique<std::string>("str"));
+
+  CompressedTuple<CompressedTuple<std::unique_ptr<std::string>>,
+                  std::unique_ptr<int>>
+  x(std::move(str_tup), absl::make_unique<int>(5));
+
+  EXPECT_EQ(*x.get<0>().get<0>(), "str");
+  EXPECT_EQ(*x.get<1>(), 5);
+
+  std::unique_ptr<std::string> x0 = std::move(x.get<0>()).get<0>();
+  std::unique_ptr<int> x1 = std::move(x).get<1>();
+
+  EXPECT_EQ(*x0, "str");
+  EXPECT_EQ(*x1, 5);
+}
+
 TEST(CompressedTupleTest, Constexpr) {
-  constexpr CompressedTuple<int, double, CompressedTuple<int>> x(
-      7, 1.25, CompressedTuple<int>(5));
+  constexpr CompressedTuple<int, double, CompressedTuple<int>, Empty<0>> x(
+      7, 1.25, CompressedTuple<int>(5), {});
   constexpr int x0 = x.get<0>();
   constexpr double x1 = x.get<1>();
   constexpr int x2 = x.get<2>().get<0>();
+  constexpr CallType x3 = x.get<3>().value();
+
   EXPECT_EQ(x0, 7);
   EXPECT_EQ(x1, 1.25);
   EXPECT_EQ(x2, 5);
+  EXPECT_EQ(x3, CallType::kConstRef);
+
+#if defined(__clang__)
+  // An apparent bug in earlier versions of gcc claims these are ambiguous.
+  constexpr int x2m = absl::move(x.get<2>()).get<0>();
+  constexpr CallType x3m = absl::move(x).get<3>().value();
+  EXPECT_EQ(x2m, 5);
+  EXPECT_EQ(x3m, CallType::kConstMove);
+#endif
 }
 
 #if defined(__clang__) || defined(__GNUC__)
diff --git a/absl/container/internal/hashtable_debug.h b/absl/container/internal/hashtable_debug.h
index c3bd65c9c4ec..38050c69f61f 100644
--- a/absl/container/internal/hashtable_debug.h
+++ b/absl/container/internal/hashtable_debug.h
@@ -60,7 +60,7 @@ std::vector<size_t> GetHashtableDebugNumProbesHistogram(const C& container) {
     size_t num_probes = GetHashtableDebugNumProbes(
         container,
         absl::container_internal::hashtable_debug_internal::GetKey<C>(*it, 0));
-    v.resize(std::max(v.size(), num_probes + 1));
+    v.resize((std::max)(v.size(), num_probes + 1));
     v[num_probes]++;
   }
   return v;
diff --git a/absl/container/internal/have_sse.h b/absl/container/internal/have_sse.h
new file mode 100644
index 000000000000..293478895b60
--- /dev/null
+++ b/absl/container/internal/have_sse.h
@@ -0,0 +1,49 @@
+// Copyright 2018 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+// Shared config probing for SSE instructions used in Swiss tables.
+#ifndef ABSL_CONTAINER_INTERNAL_HAVE_SSE_H_
+#define ABSL_CONTAINER_INTERNAL_HAVE_SSE_H_
+
+#ifndef SWISSTABLE_HAVE_SSE2
+#if defined(__SSE2__) ||  \
+    (defined(_MSC_VER) && \
+     (defined(_M_X64) || (defined(_M_IX86) && _M_IX86_FP >= 2)))
+#define SWISSTABLE_HAVE_SSE2 1
+#else
+#define SWISSTABLE_HAVE_SSE2 0
+#endif
+#endif
+
+#ifndef SWISSTABLE_HAVE_SSSE3
+#ifdef __SSSE3__
+#define SWISSTABLE_HAVE_SSSE3 1
+#else
+#define SWISSTABLE_HAVE_SSSE3 0
+#endif
+#endif
+
+#if SWISSTABLE_HAVE_SSSE3 && !SWISSTABLE_HAVE_SSE2
+#error "Bad configuration!"
+#endif
+
+#if SWISSTABLE_HAVE_SSE2
+#include <emmintrin.h>
+#endif
+
+#if SWISSTABLE_HAVE_SSSE3
+#include <tmmintrin.h>
+#endif
+
+#endif  // ABSL_CONTAINER_INTERNAL_HAVE_SSE_H_
diff --git a/absl/container/internal/layout.h b/absl/container/internal/layout.h
index a9c1244a4e79..3d21ac963b45 100644
--- a/absl/container/internal/layout.h
+++ b/absl/container/internal/layout.h
@@ -253,8 +253,10 @@ template <class From, class To>
 using CopyConst =
     typename std::conditional<std::is_const<From>::value, const To, To>::type;
 
+// Note: We're not qualifying this with absl:: because it doesn't compile under
+// MSVC.
 template <class T>
-using SliceType = absl::Span<T>;
+using SliceType = Span<T>;
 
 // This namespace contains no types. It prevents functions defined in it from
 // being found by ADL.
diff --git a/absl/container/internal/layout_test.cc b/absl/container/internal/layout_test.cc
index 224f741a7879..301e9f7808f1 100644
--- a/absl/container/internal/layout_test.cc
+++ b/absl/container/internal/layout_test.cc
@@ -45,7 +45,7 @@ Expected Type(Actual val) {
   return val;
 }
 
-// Helper class to test different size and alignments.
+// Helper classes to test different size and alignments.
 struct alignas(8) Int128 {
   uint64_t a, b;
   friend bool operator==(Int128 lhs, Int128 rhs) {
@@ -57,6 +57,14 @@ struct alignas(8) Int128 {
   }
 };
 
+// int64_t is *not* 8-byte aligned on all platforms!
+struct alignas(8) Int64 {
+  int64_t a;
+  friend bool operator==(Int64 lhs, Int64 rhs) {
+    return lhs.a == rhs.a;
+  }
+};
+
 // Properties of types that this test relies on.
 static_assert(sizeof(int8_t) == 1, "");
 static_assert(alignof(int8_t) == 1, "");
@@ -64,6 +72,8 @@ static_assert(sizeof(int16_t) == 2, "");
 static_assert(alignof(int16_t) == 2, "");
 static_assert(sizeof(int32_t) == 4, "");
 static_assert(alignof(int32_t) == 4, "");
+static_assert(sizeof(Int64) == 8, "");
+static_assert(alignof(Int64) == 8, "");
 static_assert(sizeof(Int128) == 16, "");
 static_assert(alignof(Int128) == 8, "");
 
@@ -1281,14 +1291,14 @@ TEST(Layout, OverAligned) {
 TEST(Layout, Alignment) {
   static_assert(Layout<int8_t>::Alignment() == 1, "");
   static_assert(Layout<int32_t>::Alignment() == 4, "");
-  static_assert(Layout<int64_t>::Alignment() == 8, "");
+  static_assert(Layout<Int64>::Alignment() == 8, "");
   static_assert(Layout<Aligned<int8_t, 64>>::Alignment() == 64, "");
-  static_assert(Layout<int8_t, int32_t, int64_t>::Alignment() == 8, "");
-  static_assert(Layout<int8_t, int64_t, int32_t>::Alignment() == 8, "");
-  static_assert(Layout<int32_t, int8_t, int64_t>::Alignment() == 8, "");
-  static_assert(Layout<int32_t, int64_t, int8_t>::Alignment() == 8, "");
-  static_assert(Layout<int64_t, int8_t, int32_t>::Alignment() == 8, "");
-  static_assert(Layout<int64_t, int32_t, int8_t>::Alignment() == 8, "");
+  static_assert(Layout<int8_t, int32_t, Int64>::Alignment() == 8, "");
+  static_assert(Layout<int8_t, Int64, int32_t>::Alignment() == 8, "");
+  static_assert(Layout<int32_t, int8_t, Int64>::Alignment() == 8, "");
+  static_assert(Layout<int32_t, Int64, int8_t>::Alignment() == 8, "");
+  static_assert(Layout<Int64, int8_t, int32_t>::Alignment() == 8, "");
+  static_assert(Layout<Int64, int32_t, int8_t>::Alignment() == 8, "");
 }
 
 TEST(Layout, ConstexprPartial) {
@@ -1323,7 +1333,7 @@ void ExpectPoisoned(const unsigned char (&buf)[N],
 }
 
 TEST(Layout, PoisonPadding) {
-  using L = Layout<int8_t, int64_t, int32_t, Int128>;
+  using L = Layout<int8_t, Int64, int32_t, Int128>;
 
   constexpr size_t n = L::Partial(1, 2, 3, 4).AllocSize();
   {
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc
index 10153129fd1e..180d3fe5a91f 100644
--- a/absl/container/internal/raw_hash_set.cc
+++ b/absl/container/internal/raw_hash_set.cc
@@ -14,6 +14,7 @@
 
 #include "absl/container/internal/raw_hash_set.h"
 
+#include <atomic>
 #include <cstddef>
 
 #include "absl/base/config.h"
@@ -29,7 +30,7 @@ inline size_t RandomSeed() {
   static thread_local size_t counter = 0;
   size_t value = ++counter;
 #else   // ABSL_HAVE_THREAD_LOCAL
-  static std::atomic<size_t> counter;
+  static std::atomic<size_t> counter(0);
   size_t value = counter.fetch_add(1, std::memory_order_relaxed);
 #endif  // ABSL_HAVE_THREAD_LOCAL
   return value ^ static_cast<size_t>(reinterpret_cast<uintptr_t>(&counter));
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index 575f1b007b44..b7b5ef8c7b44 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -91,36 +91,6 @@
 #ifndef ABSL_CONTAINER_INTERNAL_RAW_HASH_SET_H_
 #define ABSL_CONTAINER_INTERNAL_RAW_HASH_SET_H_
 
-#ifndef SWISSTABLE_HAVE_SSE2
-#if defined(__SSE2__) ||  \
-    (defined(_MSC_VER) && \
-     (defined(_M_X64) || (defined(_M_IX86) && _M_IX86_FP >= 2)))
-#define SWISSTABLE_HAVE_SSE2 1
-#else
-#define SWISSTABLE_HAVE_SSE2 0
-#endif
-#endif
-
-#ifndef SWISSTABLE_HAVE_SSSE3
-#ifdef __SSSE3__
-#define SWISSTABLE_HAVE_SSSE3 1
-#else
-#define SWISSTABLE_HAVE_SSSE3 0
-#endif
-#endif
-
-#if SWISSTABLE_HAVE_SSSE3 && !SWISSTABLE_HAVE_SSE2
-#error "Bad configuration!"
-#endif
-
-#if SWISSTABLE_HAVE_SSE2
-#include <emmintrin.h>
-#endif
-
-#if SWISSTABLE_HAVE_SSSE3
-#include <tmmintrin.h>
-#endif
-
 #include <algorithm>
 #include <cmath>
 #include <cstdint>
@@ -139,6 +109,7 @@
 #include "absl/container/internal/container_memory.h"
 #include "absl/container/internal/hash_policy_traits.h"
 #include "absl/container/internal/hashtable_debug_hooks.h"
+#include "absl/container/internal/have_sse.h"
 #include "absl/container/internal/layout.h"
 #include "absl/memory/memory.h"
 #include "absl/meta/type_traits.h"
@@ -1363,7 +1334,7 @@ class raw_hash_set {
   void rehash(size_t n) {
     if (n == 0 && capacity_ == 0) return;
     if (n == 0 && size_ == 0) return destroy_slots();
-    auto m = NormalizeCapacity(std::max(n, NumSlotsFast(size())));
+    auto m = NormalizeCapacity((std::max)(n, NumSlotsFast(size())));
     // n == 0 unconditionally rehashes as per the standard.
     if (n == 0 || m > capacity_) {
       resize(m);
diff --git a/absl/container/node_hash_set.h b/absl/container/node_hash_set.h
index e4034461a011..843b11aa58ad 100644
--- a/absl/container/node_hash_set.h
+++ b/absl/container/node_hash_set.h
@@ -273,8 +273,7 @@ class node_hash_set
   //
   // The element may be constructed even if there already is an element with the
   // key in the container, in which case the newly constructed element will be
-  // destroyed immediately. Prefer `try_emplace()` unless your key is not
-  // copyable or moveable.
+  // destroyed immediately.
   //
   // If rehashing occurs due to the insertion, all iterators are invalidated.
   using Base::emplace;
@@ -288,8 +287,7 @@ class node_hash_set
   //
   // The element may be constructed even if there already is an element with the
   // key in the container, in which case the newly constructed element will be
-  // destroyed immediately. Prefer `try_emplace()` unless your key is not
-  // copyable or moveable.
+  // destroyed immediately.
   //
   // If rehashing occurs due to the insertion, all iterators are invalidated.
   using Base::emplace_hint;
generated by cgit-pink 1.4.1 (git 2.44.2) at 2025-02-06T04ยท44+0000