3 files changed, 132 insertions, 1 deletions
diff --git a/absl/container/internal/hashtablez_sampler.h b/absl/container/internal/hashtablez_sampler.h
index aff8d15f..a308e788 100644
--- a/absl/container/internal/hashtablez_sampler.h
+++ b/absl/container/internal/hashtablez_sampler.h
@@ -34,7 +34,6 @@
 // are using a table in an unusual circumstance where allocation or calling a
 // linux syscall is unacceptable, this could interfere.
 //
-//
 // This utility is internal-only. Use at your own risk.
 
 #ifndef ABSL_CONTAINER_INTERNAL_HASHTABLEZ_SAMPLER_H_
diff --git a/absl/container/internal/inlined_vector.h b/absl/container/internal/inlined_vector.h
new file mode 100644
index 00000000..30850609
--- /dev/null
+++ b/absl/container/internal/inlined_vector.h
@@ -0,0 +1,130 @@
+// Copyright 2019 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
+//
+//      https://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.
+
+#ifndef ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_INTERNAL_H_
+#define ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_INTERNAL_H_
+
+#include <cstddef>
+#include <iterator>
+#include <memory>
+
+#include "absl/meta/type_traits.h"
+
+namespace absl {
+namespace inlined_vector_internal {
+
+template <typename T, size_t N, typename A>
+class InlinedVectorStorage {
+  static_assert(
+      N > 0, "InlinedVector cannot be instantiated with `0` inline elements.");
+
+ public:
+  using allocator_type = A;
+  using value_type = typename allocator_type::value_type;
+  using pointer = typename allocator_type::pointer;
+  using const_pointer = typename allocator_type::const_pointer;
+  using reference = typename allocator_type::reference;
+  using const_reference = typename allocator_type::const_reference;
+  using rvalue_reference = typename allocator_type::value_type&&;
+  using size_type = typename allocator_type::size_type;
+  using difference_type = typename allocator_type::difference_type;
+  using iterator = pointer;
+  using const_iterator = const_pointer;
+  using reverse_iterator = std::reverse_iterator<iterator>;
+  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+
+  constexpr static size_type GetInlinedCapacity() {
+    return static_cast<size_type>(N);
+  }
+
+  explicit InlinedVectorStorage(const allocator_type& a)
+      : allocator_and_tag_(a) {}
+
+  // TODO(johnsoncj): Make the below types and members private after migration
+
+  // Holds whether the vector is allocated or not in the lowest bit and the size
+  // in the high bits:
+  //   `size_ = (size << 1) | is_allocated;`
+  class Tag {
+    size_type size_;
+
+   public:
+    Tag() : size_(0) {}
+    size_type size() const { return size_ / 2; }
+    void add_size(size_type n) { size_ += n * 2; }
+    void set_inline_size(size_type n) { size_ = n * 2; }
+    void set_allocated_size(size_type n) { size_ = (n * 2) + 1; }
+    bool allocated() const { return size_ % 2; }
+  };
+
+  // Derives from `allocator_type` to use the empty base class optimization.
+  // If the `allocator_type` is stateless, we can store our instance for free.
+  class AllocatorAndTag : private allocator_type {
+    Tag tag_;
+
+   public:
+    explicit AllocatorAndTag(const allocator_type& a) : allocator_type(a) {}
+    Tag& tag() { return tag_; }
+    const Tag& tag() const { return tag_; }
+    allocator_type& allocator() { return *this; }
+    const allocator_type& allocator() const { return *this; }
+  };
+
+  class Allocation {
+    size_type capacity_;
+    pointer buffer_;
+
+   public:
+    Allocation(allocator_type& a, size_type capacity)
+        : capacity_(capacity), buffer_(Create(a, capacity)) {}
+    void Dealloc(allocator_type& a) {
+      std::allocator_traits<allocator_type>::deallocate(a, buffer_, capacity_);
+    }
+    size_type capacity() const { return capacity_; }
+    const_pointer buffer() const { return buffer_; }
+    pointer buffer() { return buffer_; }
+    static pointer Create(allocator_type& a, size_type n) {
+      return std::allocator_traits<allocator_type>::allocate(a, n);
+    }
+  };
+
+  // Stores either the inlined or allocated representation
+  union Rep {
+    using ValueTypeBuffer =
+        absl::aligned_storage_t<sizeof(value_type), alignof(value_type)>;
+    using AllocationBuffer =
+        absl::aligned_storage_t<sizeof(Allocation), alignof(Allocation)>;
+
+    // Structs wrap the buffers to perform indirection that solves a bizarre
+    // compilation error on Visual Studio (all known versions).
+    struct InlinedRep {
+      ValueTypeBuffer inlined[N];
+    };
+
+    struct AllocatedRep {
+      AllocationBuffer allocation;
+    };
+
+    InlinedRep inlined_storage;
+    AllocatedRep allocation_storage;
+  };
+
+  AllocatorAndTag allocator_and_tag_;
+  Rep rep_;
+};
+
+}  // namespace inlined_vector_internal
+}  // namespace absl
+
+#endif  // ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_INTERNAL_H_
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
index 9e79cb38..87511148 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -1080,6 +1080,7 @@ ExpectedStats XorSeedExpectedStats() {
   ABSL_RAW_LOG(FATAL, "%s", "Unknown Group width");
   return {};
 }
+
 TEST(Table, DISABLED_EnsureNonQuadraticTopNXorSeedByProbeSeqLength) {
   ProbeStatsPerSize stats;
   std::vector<size_t> sizes = {Group::kWidth << 5, Group::kWidth << 10};
@@ -1173,6 +1174,7 @@ ExpectedStats LinearTransformExpectedStats() {
   ABSL_RAW_LOG(FATAL, "%s", "Unknown Group width");
   return {};
 }
+
 TEST(Table, DISABLED_EnsureNonQuadraticTopNLinearTransformByProbeSeqLength) {
   ProbeStatsPerSize stats;
   std::vector<size_t> sizes = {Group::kWidth << 5, Group::kWidth << 10};