BoundedInlineVector: Vector class of bounded size with inline allocation

Selling point is that it never touches the heap. Intended use case is
cheaply returning a variable, bounded, and small number of things from
a function.

Specifically, there are situations where we'd like to return things like

  ArrayView<ArrayView<float>>

where we currently have to allocate an array of ArrayView<float> for
the outer ArrayView to point to, which is a bother; however, although
the outer ArrayView is of variable size, that size is statically
guaranteed to not exceed some small constant. After this CL, we'll be
able to instead return

  BoundedInlineVector<ArrayView<float>, kSmallConstant>

which is much more convenient. We already had the option of returning e.g.

  std::vector<ArrayView<float>>

but that would bloat our binary with code to handle heap allocations
in places we'd rather be lean and mean.

https://godbolt.org/z/r-vcPj demonstrates that the overhead compared to
a raw C array + a size is ~zero.

Bug: webrtc:11391
Change-Id: Ifb6d937193052588be641aa62cc67ba0ec64ded6
Reviewed-on: https://webrtc-review.googlesource.com/c/src/+/168944
Commit-Queue: Karl Wiberg <kwiberg@webrtc.org>
Reviewed-by: Mirko Bonadei <mbonadei@webrtc.org>
Reviewed-by: Per Åhgren <peah@webrtc.org>
Reviewed-by: Danil Chapovalov <danilchap@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#30663}

4 files changed, 479 insertions, 0 deletions

diff --git a/rtc_base/BUILD.gn b/rtc_base/BUILD.gn
index 0805a5c549..d23cf13c47 100644
--- a/rtc_base/BUILD.gn
+++ b/rtc_base/BUILD.gn
@@ -325,6 +325,12 @@ rtc_source_set("sanitizer") {
   deps = [ "//third_party/abseil-cpp/absl/meta:type_traits" ]
 }
 
+rtc_source_set("bounded_inline_vector") {
+  public = [ "bounded_inline_vector.h" ]
+  sources = [ "bounded_inline_vector_impl.h" ]
+  deps = [ ":checks" ]
+}
+
 rtc_source_set("divide_round") {
   sources = [ "numerics/divide_round.h" ]
   deps = [
@@ -1123,6 +1129,7 @@ if (rtc_include_tests) {
       "base64_unittest.cc",
       "bind_unittest.cc",
       "bit_buffer_unittest.cc",
+      "bounded_inline_vector_unittest.cc",
       "buffer_queue_unittest.cc",
       "buffer_unittest.cc",
       "byte_buffer_unittest.cc",
@@ -1165,6 +1172,7 @@ if (rtc_include_tests) {
       sources += [ "win/windows_version_unittest.cc" ]
     }
     deps = [
+      ":bounded_inline_vector",
       ":checks",
       ":divide_round",
       ":gunit_helpers",
diff --git a/rtc_base/bounded_inline_vector.h b/rtc_base/bounded_inline_vector.h
new file mode 100644
index 0000000000..6e8eb23feb
--- /dev/null
+++ b/rtc_base/bounded_inline_vector.h
@@ -0,0 +1,138 @@
+/*
+ *  Copyright 2020 The WebRTC Project Authors. All rights reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+#ifndef RTC_BASE_BOUNDED_INLINE_VECTOR_H_
+#define RTC_BASE_BOUNDED_INLINE_VECTOR_H_
+
+#include <stdint.h>
+
+#include <memory>
+#include <type_traits>
+#include <utility>
+
+#include "rtc_base/bounded_inline_vector_impl.h"
+#include "rtc_base/checks.h"
+
+namespace webrtc {
+
+// A small std::vector-like type whose capacity is a compile-time constant. It
+// stores all data inline and never heap allocates (beyond what its element type
+// requires). Trying to grow it beyond its constant capacity is an error.
+//
+// TODO(bugs.webrtc.org/11391): Comparison operators.
+// TODO(bugs.webrtc.org/11391): Methods for adding and deleting elements.
+template <typename T, int fixed_capacity>
+class BoundedInlineVector {
+  static_assert(!std::is_const<T>::value, "T may not be const");
+  static_assert(fixed_capacity > 0, "Capacity must be strictly positive");
+
+ public:
+  using value_type = T;
+  using const_iterator = const T*;
+
+  BoundedInlineVector() = default;
+  BoundedInlineVector(const BoundedInlineVector&) = default;
+  BoundedInlineVector(BoundedInlineVector&&) = default;
+  BoundedInlineVector& operator=(const BoundedInlineVector&) = default;
+  BoundedInlineVector& operator=(BoundedInlineVector&&) = default;
+  ~BoundedInlineVector() = default;
+
+  // This constructor is implicit, to make it possible to write e.g.
+  //
+  //   BoundedInlineVector<double, 7> x = {2.72, 3.14};
+  //
+  // and
+  //
+  //   BoundedInlineVector<double, 7> GetConstants() {
+  //     return {2.72, 3.14};
+  //   }
+  template <typename... Ts,
+            typename std::enable_if_t<
+                bounded_inline_vector_impl::AllConvertible<T, Ts...>::value>* =
+                nullptr>
+  BoundedInlineVector(Ts&&... elements)  // NOLINT(runtime/explicit)
+      : storage_(std::forward<Ts>(elements)...) {
+    static_assert(sizeof...(Ts) <= fixed_capacity, "");
+  }
+
+  template <
+      int other_capacity,
+      typename std::enable_if_t<other_capacity != fixed_capacity>* = nullptr>
+  BoundedInlineVector(const BoundedInlineVector<T, other_capacity>& other) {
+    RTC_DCHECK_LE(other.size(), fixed_capacity);
+    bounded_inline_vector_impl::CopyElements(other.data(), other.size(),
+                                             storage_.data, &storage_.size);
+  }
+
+  template <
+      int other_capacity,
+      typename std::enable_if_t<other_capacity != fixed_capacity>* = nullptr>
+  BoundedInlineVector(BoundedInlineVector<T, other_capacity>&& other) {
+    RTC_DCHECK_LE(other.size(), fixed_capacity);
+    bounded_inline_vector_impl::MoveElements(other.data(), other.size(),
+                                             storage_.data, &storage_.size);
+  }
+
+  template <
+      int other_capacity,
+      typename std::enable_if_t<other_capacity != fixed_capacity>* = nullptr>
+  BoundedInlineVector& operator=(
+      const BoundedInlineVector<T, other_capacity>& other) {
+    bounded_inline_vector_impl::DestroyElements(storage_.data, storage_.size);
+    RTC_DCHECK_LE(other.size(), fixed_capacity);
+    bounded_inline_vector_impl::CopyElements(other.data(), other.size(),
+                                             storage_.data, &storage_.size);
+    return *this;
+  }
+
+  template <
+      int other_capacity,
+      typename std::enable_if_t<other_capacity != fixed_capacity>* = nullptr>
+  BoundedInlineVector& operator=(
+      BoundedInlineVector<T, other_capacity>&& other) {
+    bounded_inline_vector_impl::DestroyElements(storage_.data, storage_.size);
+    RTC_DCHECK_LE(other.size(), fixed_capacity);
+    bounded_inline_vector_impl::MoveElements(other.data(), other.size(),
+                                             storage_.data, &storage_.size);
+    return *this;
+  }
+
+  bool empty() const { return storage_.size == 0; }
+  int size() const { return storage_.size; }
+  constexpr int capacity() const { return fixed_capacity; }
+
+  const T* data() const { return storage_.data; }
+  T* data() { return storage_.data; }
+
+  const T& operator[](int index) const {
+    RTC_DCHECK_GE(index, 0);
+    RTC_DCHECK_LT(index, storage_.size);
+    return storage_.data[index];
+  }
+  T& operator[](int index) {
+    RTC_DCHECK_GE(index, 0);
+    RTC_DCHECK_LT(index, storage_.size);
+    return storage_.data[index];
+  }
+
+  T* begin() { return storage_.data; }
+  T* end() { return storage_.data + storage_.size; }
+  const T* begin() const { return storage_.data; }
+  const T* end() const { return storage_.data + storage_.size; }
+  const T* cbegin() const { return storage_.data; }
+  const T* cend() const { return storage_.data + storage_.size; }
+
+ private:
+  bounded_inline_vector_impl::Storage<T, fixed_capacity> storage_;
+};
+
+}  // namespace webrtc
+
+#endif  // RTC_BASE_BOUNDED_INLINE_VECTOR_H_
diff --git a/rtc_base/bounded_inline_vector_impl.h b/rtc_base/bounded_inline_vector_impl.h
new file mode 100644
index 0000000000..ab5249444b
--- /dev/null
+++ b/rtc_base/bounded_inline_vector_impl.h
@@ -0,0 +1,215 @@
+/*
+ *  Copyright 2020 The WebRTC Project Authors. All rights reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+#ifndef RTC_BASE_BOUNDED_INLINE_VECTOR_IMPL_H_
+#define RTC_BASE_BOUNDED_INLINE_VECTOR_IMPL_H_
+
+#include <stdint.h>
+
+#include <cstring>
+#include <memory>
+#include <type_traits>
+#include <utility>
+
+namespace webrtc {
+namespace bounded_inline_vector_impl {
+
+template <bool...>
+struct BoolPack;
+
+// Tests if all its parameters (x0, x1, ..., xn) are true. The implementation
+// checks whether (x0, x1, ..., xn, true) == (true, x0, x1, ..., xn), which is
+// true iff true == x0 && x0 == x1 && x1 == x2 ... && xn-1 == xn && xn == true.
+template <bool... Bs>
+using AllTrue = std::is_same<BoolPack<Bs..., true>, BoolPack<true, Bs...>>;
+
+template <typename To, typename... Froms>
+using AllConvertible = AllTrue<std::is_convertible<Froms, To>::value...>;
+
+// Initializes part of an uninitialized array. Unlike normal array
+// initialization, does not zero the remaining array elements. Caller is
+// responsible for ensuring that there is enough space in `data`.
+template <typename T>
+void InitializeElements(T* data) {}
+template <typename T, typename U, typename... Us>
+void InitializeElements(T* data, U&& element, Us&&... elements) {
+  // Placement new, because we construct a new object in uninitialized memory.
+  ::new (data) T(std::forward<U>(element));
+  InitializeElements(data + 1, std::forward<Us>(elements)...);
+}
+
+// Copies from source to uninitialized destination. Caller is responsible for
+// ensuring that there is enough space in `dst_data`.
+template <typename T>
+void CopyElements(const T* src_data, int src_size, T* dst_data, int* dst_size) {
+  if /*constexpr*/ (std::is_trivially_copy_constructible<T>::value) {
+    std::memcpy(dst_data, src_data, src_size * sizeof(T));
+  } else {
+    std::uninitialized_copy_n(src_data, src_size, dst_data);
+  }
+  *dst_size = src_size;
+}
+
+// Moves from source to uninitialized destination. Caller is responsible for
+// ensuring that there is enough space in `dst_data`.
+template <typename T>
+void MoveElements(T* src_data, int src_size, T* dst_data, int* dst_size) {
+  if /*constexpr*/ (std::is_trivially_move_constructible<T>::value) {
+    std::memcpy(dst_data, src_data, src_size * sizeof(T));
+  } else {
+    // TODO(kwiberg): Use std::uninitialized_move_n() instead (C++17).
+    for (int i = 0; i < src_size; ++i) {
+      // Placement new, because we create a new object in uninitialized
+      // memory.
+      ::new (&dst_data[i]) T(std::move(src_data[i]));
+    }
+  }
+  *dst_size = src_size;
+}
+
+// Destroys elements, leaving them uninitialized.
+template <typename T>
+void DestroyElements(T* data, int size) {
+  if /*constexpr*/ (!std::is_trivially_destructible<T>::value) {
+    for (int i = 0; i < size; ++i) {
+      data[i].~T();
+    }
+  }
+}
+
+// If elements are trivial and the total capacity is at most this many bytes,
+// copy everything instead of just the elements that are in use; this is more
+// efficient, and makes BoundedInlineVector trivially copyable.
+static constexpr int kSmallSize = 64;
+
+// Storage implementations.
+//
+// There are diferent Storage structs for diferent kinds of element types. The
+// common contract is the following:
+//
+//   * They have public `size` variables and `data` array members.
+//
+//   * Their owner is responsible for enforcing the invariant that the first
+//     `size` elements in `data` are initialized, and the remaining elements are
+//     not initialized.
+//
+//   * They implement default construction, construction with one or more
+//     elements, copy/move construction, copy/move assignment, and destruction;
+//     the owner must ensure that the invariant holds whenever these operations
+//     occur.
+
+// Storage implementation for nontrivial element types.
+template <typename T,
+          int fixed_capacity,
+          bool is_trivial = std::is_trivial<T>::value,
+          bool is_small = (sizeof(T) * fixed_capacity <= kSmallSize)>
+struct Storage {
+  static_assert(!std::is_trivial<T>::value, "");
+
+  template <
+      typename... Ts,
+      typename std::enable_if_t<AllConvertible<T, Ts...>::value>* = nullptr>
+  explicit Storage(Ts&&... elements) : size(sizeof...(Ts)) {
+    InitializeElements(data, std::forward<Ts>(elements)...);
+  }
+
+  Storage(const Storage& other) {
+    CopyElements(other.data, other.size, data, &size);
+  }
+
+  Storage(Storage&& other) {
+    MoveElements(other.data, other.size, data, &size);
+  }
+
+  Storage& operator=(const Storage& other) {
+    if (this != &other) {
+      DestroyElements(data, size);
+      CopyElements(other.data, other.size, data, &size);
+    }
+    return *this;
+  }
+
+  Storage& operator=(Storage&& other) {
+    DestroyElements(data, size);
+    size = 0;  // Needed in case of self assignment.
+    MoveElements(other.data, other.size, data, &size);
+    return *this;
+  }
+
+  ~Storage() { DestroyElements(data, size); }
+
+  int size;
+  union {
+    // Since this array is in a union, we get to construct and destroy it
+    // manually.
+    T data[fixed_capacity];  // NOLINT(runtime/arrays)
+  };
+};
+
+// Storage implementation for trivial element types when the capacity is small
+// enough that we can cheaply copy everything.
+template <typename T, int fixed_capacity>
+struct Storage<T, fixed_capacity, /*is_trivial=*/true, /*is_small=*/true> {
+  static_assert(std::is_trivial<T>::value, "");
+  static_assert(sizeof(T) * fixed_capacity <= kSmallSize, "");
+
+  template <
+      typename... Ts,
+      typename std::enable_if_t<AllConvertible<T, Ts...>::value>* = nullptr>
+  explicit Storage(Ts&&... elements) : size(sizeof...(Ts)) {
+    InitializeElements(data, std::forward<Ts>(elements)...);
+  }
+
+  Storage(const Storage&) = default;
+  Storage& operator=(const Storage&) = default;
+  ~Storage() = default;
+
+  int size;
+  T data[fixed_capacity];  // NOLINT(runtime/arrays)
+};
+
+// Storage implementation for trivial element types when the capacity is large
+// enough that we want to avoid copying uninitialized elements.
+template <typename T, int fixed_capacity>
+struct Storage<T, fixed_capacity, /*is_trivial=*/true, /*is_small=*/false> {
+  static_assert(std::is_trivial<T>::value, "");
+  static_assert(sizeof(T) * fixed_capacity > kSmallSize, "");
+
+  template <
+      typename... Ts,
+      typename std::enable_if_t<AllConvertible<T, Ts...>::value>* = nullptr>
+  explicit Storage(Ts&&... elements) : size(sizeof...(Ts)) {
+    InitializeElements(data, std::forward<Ts>(elements)...);
+  }
+
+  Storage(const Storage& other) : size(other.size) {
+    std::memcpy(data, other.data, other.size * sizeof(T));
+  }
+
+  Storage& operator=(const Storage& other) {
+    if (this != &other) {
+      size = other.size;
+      std::memcpy(data, other.data, other.size * sizeof(T));
+    }
+    return *this;
+  }
+
+  ~Storage() = default;
+
+  int size;
+  union {
+    T data[fixed_capacity];  // NOLINT(runtime/arrays)
+  };
+};
+
+}  // namespace bounded_inline_vector_impl
+}  // namespace webrtc
+
+#endif  // RTC_BASE_BOUNDED_INLINE_VECTOR_IMPL_H_
diff --git a/rtc_base/bounded_inline_vector_unittest.cc b/rtc_base/bounded_inline_vector_unittest.cc
new file mode 100644
index 0000000000..e5855a485c
--- /dev/null
+++ b/rtc_base/bounded_inline_vector_unittest.cc
@@ -0,0 +1,118 @@
+/*
+ *  Copyright 2020 The WebRTC Project Authors. All rights reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include "rtc_base/bounded_inline_vector.h"
+
+#include <memory>
+#include <string>
+#include <utility>
+
+#include "test/gmock.h"
+#include "test/gtest.h"
+
+namespace webrtc {
+namespace {
+
+using SmallTrivial = BoundedInlineVector<int, 2>;
+using LargeTrivial = BoundedInlineVector<int, 200>;
+using NonTrivial = BoundedInlineVector<std::string, 2>;
+static_assert(std::is_trivially_copyable<SmallTrivial>::value, "");
+static_assert(!std::is_trivially_copyable<LargeTrivial>::value, "");
+static_assert(std::is_trivially_destructible<LargeTrivial>::value, "");
+static_assert(!std::is_trivially_copyable<NonTrivial>::value, "");
+static_assert(!std::is_trivially_destructible<NonTrivial>::value, "");
+
+template <typename T>
+class BoundedInlineVectorTestAllTypes : public ::testing::Test {};
+
+using AllTypes =
+    ::testing::Types<int,                    // Scalar type.
+                     std::pair<int, float>,  // Trivial nonprimitive type.
+                     std::unique_ptr<int>,   // Move-only type.
+                     std::string>;           // Nontrivial copyable type.
+TYPED_TEST_SUITE(BoundedInlineVectorTestAllTypes, AllTypes);
+
+template <typename T>
+class BoundedInlineVectorTestCopyableTypes : public ::testing::Test {};
+
+using CopyableTypes = ::testing::Types<int, std::pair<int, float>, std::string>;
+TYPED_TEST_SUITE(BoundedInlineVectorTestCopyableTypes, CopyableTypes);
+
+TYPED_TEST(BoundedInlineVectorTestAllTypes, ConstructEmpty) {
+  BoundedInlineVector<TypeParam, 3> x;
+  EXPECT_EQ(x.size(), 0);
+  EXPECT_EQ(x.begin(), x.end());
+  static_assert(x.capacity() == 3, "");
+}
+
+TYPED_TEST(BoundedInlineVectorTestAllTypes, ConstructNonempty) {
+  BoundedInlineVector<TypeParam, 3> x = {TypeParam(), TypeParam()};
+  EXPECT_EQ(x.size(), 2);
+  static_assert(x.capacity() == 3, "");
+}
+
+TYPED_TEST(BoundedInlineVectorTestCopyableTypes, CopyConstruct) {
+  BoundedInlineVector<TypeParam, 3> x = {TypeParam(), TypeParam()};
+  BoundedInlineVector<TypeParam, 2> y = x;
+  EXPECT_EQ(y.size(), 2);
+  static_assert(x.capacity() == 3, "");
+  static_assert(y.capacity() == 2, "");
+}
+
+TYPED_TEST(BoundedInlineVectorTestCopyableTypes, CopyAssign) {
+  BoundedInlineVector<TypeParam, 3> x = {TypeParam(), TypeParam()};
+  BoundedInlineVector<TypeParam, 2> y;
+  EXPECT_EQ(y.size(), 0);
+  y = x;
+  EXPECT_EQ(y.size(), 2);
+}
+
+TYPED_TEST(BoundedInlineVectorTestAllTypes, MoveConstruct) {
+  BoundedInlineVector<TypeParam, 3> x = {TypeParam(), TypeParam()};
+  BoundedInlineVector<TypeParam, 2> y = std::move(x);
+  EXPECT_EQ(y.size(), 2);
+  static_assert(x.capacity() == 3, "");
+  static_assert(y.capacity() == 2, "");
+}
+
+TYPED_TEST(BoundedInlineVectorTestAllTypes, MoveAssign) {
+  BoundedInlineVector<TypeParam, 3> x = {TypeParam(), TypeParam()};
+  BoundedInlineVector<TypeParam, 2> y;
+  EXPECT_EQ(y.size(), 0);
+  y = std::move(x);
+  EXPECT_EQ(y.size(), 2);
+}
+
+TEST(BoundedInlineVectorTestOneType, Iteration) {
+  BoundedInlineVector<std::string, 4> sv{"one", "two", "three", "four"};
+  std::string cat;
+  for (const auto& s : sv) {
+    cat += s;
+  }
+  EXPECT_EQ(cat, "onetwothreefour");
+}
+
+TEST(BoundedInlineVectorTestOneType, Indexing) {
+  BoundedInlineVector<double, 1> x = {3.14};
+  EXPECT_EQ(x[0], 3.14);
+}
+
+template <typename T, int capacity, typename... Ts>
+BoundedInlineVector<T, capacity> Returns(Ts... values) {
+  return {std::forward<Ts>(values)...};
+}
+
+TYPED_TEST(BoundedInlineVectorTestAllTypes, Return) {
+  EXPECT_EQ((Returns<TypeParam, 3>().size()), 0);
+  EXPECT_EQ((Returns<TypeParam, 3>(TypeParam(), TypeParam()).size()), 2);
+}
+
+}  // namespace
+}  // namespace webrtc