[libc] Add a utility data structure named FixedVector.

[sivachandra]

Summary

This data structure uses a backing cpp::array object and supports a
vector like push_back API. In comparison with a traditional vector
data structure, it is of a fixed capacity and cannot be resized.

[michaelrj]

libc/src/__support/arraystore.h

15 ↗

(On Diff #450709)

Currently, there is no way to add or remove elements that aren't at the end of the array. I would say either add operator[] or rename this to ArrayStack.

[tschuett]

https://reviews.llvm.org/D112175
There was a StaticVector

[sivachandra]

libc/src/__support/arraystore.h

15 ↗

(On Diff #450709)

Currently, there is no way to add or remove elements that aren't at the end of the array.

What do you mean "at the end of the array"? This data structure is not to be used like an array. It's internal storage uses an array.

I would say either add operator[] or rename this to ArrayStack.

We normally add methods as required. There is no requirement for operator[] so it isn't present. Its not clear to me how the presence or absence of that method should affect the name. I am open to a better name though. The name ArrayStore was chosen in the same pattern as that of the current cpp::BlockStore. Some other languages have similar concepts named FixedVector. I can change the name to that if it sounds better.

[sivachandra]

Change the name of the data structure to FixedVector.

[sivachandra]

I am going to submit this now in order to make progress with other things. Feel free to add comments and I will address them post commit.

libc/src/__support/CMakeLists.txt

 )
 
 add_header_library(
   arg_list
   HDRS
     arg_list.h
 )
 
+add_header_library(
+  fixedvector
+  HDRS
+    fixedvector.h
+  DEPENDS
+    libc.src.__support.CPP.array
+)
+
 add_subdirectory(FPUtil)
 add_subdirectory(OSUtil)
 
 # Thread support is used by other "File". So, we add the "threads"
 # before "File".
 add_subdirectory(threads)
 
 add_subdirectory(File)

libc/src/__support/fixedvector.h

+//===-- A data structure for a fixed capacity data store --------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SUPPORT_FIXEDVECTOR_H
+#define LLVM_LIBC_SUPPORT_FIXEDVECTOR_H
+
+#include "src/__support/CPP/array.h"
+
+namespace __llvm_libc {
+
+// A fixed size data store backed by an underlying cpp::array data structure. It
+// supports vector like API but is not resizable like a vector.
+template <typename T, size_t CAPACITY> class FixedVector {
+  cpp::array<T, CAPACITY> store;
+  size_t item_count = 0;
+
+public:
+  constexpr FixedVector() = default;
+
+  bool push_back(const T &obj) {
+    if (item_count == CAPACITY)
+      return false;
+    store[item_count] = obj;
+    ++item_count;
+    return true;
+  }
+
+  const T &back() const { return store[item_count - 1]; }
+
+  T &back() { return store[item_count - 1]; }
+
+  bool pop_back() {
+    if (item_count == 0)
+      return false;
+    --item_count;
+    return true;
+  }
+
+  bool empty() const { return item_count == 0; }
+
+  // Empties the store for all practical purposes.
+  void reset() { item_count = 0; }
+
+  // This static method does not free up the resources held by |store|,
+  // say by calling `free` or something similar. It just does the equivalent
+  // of the `reset` method. Considering that FixedVector is of fixed storage,
+  // a `destroy` method like this should not be required. However, FixedVector
+  // is used in a few places as an alternate for data structures which use
+  // dynamically allocated storate. So, the `destroy` method like this
+  // matches the `destroy` API of those other data structures so that users
+  // can easily swap one data structure for the other.
+  static void destroy(FixedVector<T, CAPACITY> *store) { store->reset(); }
+};
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SUPPORT_FIXEDVECTOR_H

libc/test/src/__support/CMakeLists.txt

add_libc_unittest(
   SUITE
     libc_support_unittests
   SRCS
     uint128_test.cpp
   DEPENDS
     libc.src.__support.CPP.uint
 )
 
+add_libc_unittest(
+  fixedvector_test
+  SUITE
+    libc_support_unittests
+  SRCS
+    fixedvector_test.cpp
+  DEPENDS
+    libc.src.__support.fixedvector
+)
+
 add_executable(
   libc_str_to_float_comparison_test
   str_to_float_comparison_test.cpp
 )
 
 target_link_libraries(libc_str_to_float_comparison_test
   PRIVATE
     llvmlibc

libc/test/src/__support/fixedvector_test.cpp

+//===-- Unittests for FixedVector -----------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "src/__support/fixedvector.h"
+#include "utils/UnitTest/Test.h"
+
+TEST(LlvmLibcFixedVectorTest, PushAndPop) {
+  __llvm_libc::FixedVector<int, 20> fixed_vector;
+  ASSERT_TRUE(fixed_vector.empty());
+  for (int i = 0; i < 20; i++)
+    ASSERT_TRUE(fixed_vector.push_back(i));
+  ASSERT_FALSE(fixed_vector.empty());
+  ASSERT_FALSE(fixed_vector.push_back(123));
+  for (int i = 20; i > 0; --i) {
+    ASSERT_EQ(fixed_vector.back(), i - 1);
+    ASSERT_TRUE(fixed_vector.pop_back());
+  }
+  ASSERT_FALSE(fixed_vector.pop_back());
+  ASSERT_TRUE(fixed_vector.empty());
+}
+
+TEST(LlvmLibcFixedVectorTest, Reset) {
+  __llvm_libc::FixedVector<int, 20> fixed_vector;
+  ASSERT_TRUE(fixed_vector.empty());
+  for (int i = 0; i < 20; i++)
+    ASSERT_TRUE(fixed_vector.push_back(i));
+  ASSERT_FALSE(fixed_vector.empty());
+  fixed_vector.reset();
+  ASSERT_TRUE(fixed_vector.empty());
+}
+
+TEST(LlvmLibcFixedVectorTest, Destroy) {
+  __llvm_libc::FixedVector<int, 20> fixed_vector;
+  ASSERT_TRUE(fixed_vector.empty());
+  for (int i = 0; i < 20; i++)
+    ASSERT_TRUE(fixed_vector.push_back(i));
+  ASSERT_FALSE(fixed_vector.empty());
+  __llvm_libc::FixedVector<int, 20>::destroy(&fixed_vector);
+  ASSERT_TRUE(fixed_vector.empty());
+}