[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

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

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(
+  arraystore
+  HDRS
+    arraystore.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/arraystore.h

+//===-- A data structure for a fixed size 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
+//
+//===----------------------------------------------------------------------===//
+
+#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 SIZE> class ArrayStore {
+  cpp::array<T, SIZE> store;
+  size_t item_count = 0;
+
+public:
+  constexpr ArrayStore() = default;
+
+  bool push_back(const T &obj) {
+    if (item_count == SIZE)
+      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; }
+
+  static void destroy(ArrayStore<T, SIZE> *store) { store->reset(); }
+};
+
+} // namespace __llvm_libc

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(
+  arraystore_test
+  SUITE
+    libc_support_unittests
+  SRCS
+    arraystore_test.cpp
+  DEPENDS
+    libc.src.__support.arraystore
+)
+
 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/arraystore_test.cpp

+//===-- Unittests for ArrayStore ------------------------------------------===//
+//
+// 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/arraystore.h"
+#include "utils/UnitTest/Test.h"
+
+TEST(LlvmLibcArrayStoreTest, PushAndPop) {
+  __llvm_libc::ArrayStore<int, 20> array_store;
+  ASSERT_TRUE(array_store.empty());
+  for (int i = 0; i < 20; i++)
+    ASSERT_TRUE(array_store.push_back(i));
+  ASSERT_FALSE(array_store.empty());
+  ASSERT_FALSE(array_store.push_back(123));
+  for (int i = 20; i > 0; --i) {
+    ASSERT_EQ(array_store.back(), i - 1);
+    ASSERT_TRUE(array_store.pop_back());
+  }
+  ASSERT_FALSE(array_store.pop_back());
+  ASSERT_TRUE(array_store.empty());
+}
+
+TEST(LlvmLibcArrayStoreTest, Reset) {
+  __llvm_libc::ArrayStore<int, 20> array_store;
+  ASSERT_TRUE(array_store.empty());
+  for (int i = 0; i < 20; i++)
+    ASSERT_TRUE(array_store.push_back(i));
+  ASSERT_FALSE(array_store.empty());
+  array_store.reset();
+  ASSERT_TRUE(array_store.empty());
+}
+
+TEST(LlvmLibcArrayStoreTest, Destroy) {
+  __llvm_libc::ArrayStore<int, 20> array_store;
+  ASSERT_TRUE(array_store.empty());
+  for (int i = 0; i < 20; i++)
+    ASSERT_TRUE(array_store.push_back(i));
+  ASSERT_FALSE(array_store.empty());
+  __llvm_libc::ArrayStore<int, 20>::destroy(&array_store);
+  ASSERT_TRUE(array_store.empty());
+}