Add GrowableArray<T> to ssl/internal.h.

Change-Id: I07aced6d2830dd5a2a04c296b1ffe7e8557369fe
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/37504
Reviewed-by: David Benjamin <davidben@google.com>
Commit-Queue: David Benjamin <davidben@google.com>

ssl/internal.h

diff --git a/ssl/internal.h b/ssl/internal.h
index c635583..792329bb 100644
--- a/ssl/internal.h
+++ b/ssl/internal.h
@@ -353,6 +353,97 @@
   size_t size_ = 0;
 };
 
+// GrowableArray<T> is an array that owns elements of |T|, backed by an
+// Array<T>. When necessary, pushing will automatically trigger a resize.
+//
+// Note, for simplicity, this class currently differs from |std::vector| in that
+// |T| must be efficiently default-constructible. Allocated elements beyond the
+// end of the array are constructed and destructed.
+template <typename T>
+class GrowableArray {
+ public:
+  GrowableArray() = default;
+  GrowableArray(const GrowableArray &) = delete;
+  GrowableArray(GrowableArray &&other) { *this = std::move(other); }
+  ~GrowableArray() {}
+
+  GrowableArray &operator=(const GrowableArray &) = delete;
+  GrowableArray &operator=(GrowableArray &&other) {
+    size_ = other.size_;
+    other.size_ = 0;
+    array_ = std::move(other.array_);
+    return *this;
+  }
+
+  size_t size() const { return size_; }
+  bool empty() const { return size_ == 0; }
+
+  const T &operator[](size_t i) const { return array_[i]; }
+  T &operator[](size_t i) { return array_[i]; }
+
+  T *begin() { return array_.data(); }
+  const T *cbegin() const { return array_.data(); }
+  T *end() { return array_.data() + size_; }
+  const T *cend() const { return array_.data() + size_; }
+
+  // Push adds |elem| at the end of the internal array, growing if necessary. It
+  // returns false when allocation fails.
+  bool Push(T elem) {
+    if (!MaybeGrow()) {
+      return false;
+    }
+    array_[size_] = std::move(elem);
+    size_++;
+    return true;
+  }
+
+  // CopyFrom replaces the contents of the array with a copy of |in|. It returns
+  // true on success and false on allocation error.
+  bool CopyFrom(Span<const T> in) {
+    if (!array_.CopyFrom(in)) {
+      return false;
+    }
+    size_ = in.size();
+    return true;
+  }
+
+ private:
+  // If there is no room for one more element, creates a new backing array with
+  // double the size of the old one and copies elements over.
+  bool MaybeGrow() {
+    if (array_.size() == 0) {
+      return array_.Init(kDefaultSize);
+    }
+    // No need to grow if we have room for one more T.
+    if (size_ < array_.size()) {
+      return true;
+    }
+    // Double the array's size if it's safe to do so.
+    if (array_.size() > std::numeric_limits<size_t>::max() / 2) {
+      OPENSSL_PUT_ERROR(SSL, ERR_R_OVERFLOW);
+      return false;
+    }
+    Array<T> new_array;
+    if (!new_array.Init(array_.size() * 2)) {
+      return false;
+    }
+    for (size_t i = 0; i < array_.size(); i++) {
+      new_array[i] = std::move(array_[i]);
+    }
+    array_ = std::move(new_array);
+
+    return true;
+  }
+
+  // |size_| is the number of elements stored in this GrowableArray.
+  size_t size_ = 0;
+  // |array_| is the backing array. Note that |array_.size()| is this
+  // GrowableArray's current capacity and that |size_ <= array_.size()|.
+  Array<T> array_;
+  // |kDefaultSize| is the default initial size of the backing array.
+  static constexpr size_t kDefaultSize = 16;
+};
+
 // CBBFinishArray behaves like |CBB_finish| but stores the result in an Array.
 OPENSSL_EXPORT bool CBBFinishArray(CBB *cbb, Array<uint8_t> *out);
 

ssl/ssl_test.cc

diff --git a/ssl/ssl_test.cc b/ssl/ssl_test.cc
index e702762..c01443e 100644
--- a/ssl/ssl_test.cc
+++ b/ssl/ssl_test.cc
@@ -473,6 +473,74 @@
   return true;
 }
 
+TEST(GrowableArrayTest, Resize) {
+  GrowableArray<size_t> array;
+  ASSERT_TRUE(array.empty());
+  EXPECT_EQ(array.size(), 0u);
+
+  ASSERT_TRUE(array.Push(42));
+  ASSERT_TRUE(!array.empty());
+  EXPECT_EQ(array.size(), 1u);
+
+  // Force a resize operation to occur
+  for (size_t i = 0; i < 16; i++) {
+    ASSERT_TRUE(array.Push(i + 1));
+  }
+
+  EXPECT_EQ(array.size(), 17u);
+
+  // Verify that expected values are still contained in array
+  for (size_t i = 0; i < array.size(); i++) {
+    EXPECT_EQ(array[i], i == 0 ? 42 : i);
+  }
+}
+
+TEST(GrowableArrayTest, MoveConstructor) {
+  GrowableArray<size_t> array;
+  for (size_t i = 0; i < 100; i++) {
+    ASSERT_TRUE(array.Push(i));
+  }
+
+  GrowableArray<size_t> array_moved(std::move(array));
+  for (size_t i = 0; i < 100; i++) {
+    EXPECT_EQ(array_moved[i], i);
+  }
+}
+
+TEST(GrowableArrayTest, GrowableArrayContainingGrowableArrays) {
+  // Representative example of a struct that contains a GrowableArray.
+  struct TagAndArray {
+    size_t tag;
+    GrowableArray<size_t> array;
+  };
+
+  GrowableArray<TagAndArray> array;
+  for (size_t i = 0; i < 100; i++) {
+    TagAndArray elem;
+    elem.tag = i;
+    for (size_t j = 0; j < i; j++) {
+      ASSERT_TRUE(elem.array.Push(j));
+    }
+    ASSERT_TRUE(array.Push(std::move(elem)));
+  }
+  EXPECT_EQ(array.size(), static_cast<size_t>(100));
+
+  GrowableArray<TagAndArray> array_moved(std::move(array));
+  EXPECT_EQ(array_moved.size(), static_cast<size_t>(100));
+  size_t count = 0;
+  for (const TagAndArray &elem : array_moved) {
+    // Test the square bracket operator returns the same value as iteration.
+    EXPECT_EQ(&elem, &array_moved[count]);
+
+    EXPECT_EQ(elem.tag, count);
+    EXPECT_EQ(elem.array.size(), count);
+    for (size_t j = 0; j < count; j++) {
+      EXPECT_EQ(elem.array[j], j);
+    }
+    count++;
+  }
+}
+
 TEST(SSLTest, CipherRules) {
   for (const CipherTest &t : kCipherTests) {
     SCOPED_TRACE(t.rule);