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>
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);
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);
