diff --git a/libc/src/__support/CPP/CMakeLists.txt b/libc/src/__support/CPP/CMakeLists.txt --- a/libc/src/__support/CPP/CMakeLists.txt +++ b/libc/src/__support/CPP/CMakeLists.txt @@ -1,3 +1,4 @@ +# TODO(michaelrj): separate the standalone_cpp library into individual targets. add_header_library( standalone_cpp HDRS @@ -10,3 +11,11 @@ StringView.h TypeTraits.h ) + +add_header_library( + vector + HDRS + vector.h + DEPENDS + libc.include.stdlib +) diff --git a/libc/src/__support/CPP/vector.h b/libc/src/__support/CPP/vector.h new file mode 100644 --- /dev/null +++ b/libc/src/__support/CPP/vector.h @@ -0,0 +1,92 @@ +//===-- A self contained equivalent of std::vector --------------*- 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_SRC_SUPPORT_CPP_VECTOR_H +#define LLVM_LIBC_SRC_SUPPORT_CPP_VECTOR_H + +#include // For size_t. + +#include // For malloc/realloc/free + +namespace __llvm_libc { +namespace cpp { + +// This implementation does not have a templated allocator since that feature +// isn't relevant for a libc setting. + +// Vector is a templated dynamically resizable array. This implementation is +// only meant for primitives or structs, and will not call destructors on held +// objects. +template class vector { + T *data_array; + size_t array_size; + size_t num_elements = 0; + static constexpr size_t DEFAULT_SIZE = 16; + static constexpr size_t GROWTH_FACTOR = 2; + static constexpr size_t MAX_SIZE = ~size_t(0); + +public: + constexpr vector() : array_size{DEFAULT_SIZE} { + data_array = static_cast(malloc(DEFAULT_SIZE * sizeof(T))); + } + + constexpr vector(const vector &other) = delete; + constexpr vector(const vector &&other) = delete; + + ~vector() { free(data_array); } + + constexpr vector &operator=(vector &other) = delete; + constexpr vector &operator=(vector &&other) = delete; + + constexpr void reserve(size_t new_size) { + if (new_size >= array_size) + increase_size(new_size + 1); + } + + constexpr void push_back(const T &value) { + if (num_elements >= array_size) + increase_size(num_elements + 1); + data_array[num_elements] = value; + ++num_elements; + } + + constexpr T &operator[](size_t pos) { return data_array[pos]; } + constexpr T *data() { return data_array; } + constexpr const T *data() const { return data_array; } + + constexpr bool empty() const { return num_elements == 0; } + + constexpr size_t size() const { return num_elements; } + constexpr size_t max_size() const { return MAX_SIZE; } + + constexpr size_t capacity() const { return array_size; } + +private: + static constexpr size_t MAX_DIV_BY_GROWTH = MAX_SIZE / GROWTH_FACTOR; + + // new_size is treated as the minimum size for the new array. This function + // will increase array_size by GROWTH_FACTOR until there is space for new_size + // items. + constexpr void increase_size(size_t new_size) { + size_t temp_size = array_size; + if (new_size >= MAX_DIV_BY_GROWTH) { + temp_size = new_size; + } else { + if (temp_size == 0) + temp_size = 1; + while (temp_size <= new_size) + temp_size = temp_size * GROWTH_FACTOR; + } + array_size = temp_size; + data_array = static_cast(realloc(data_array, array_size * sizeof(T))); + } +}; +} // namespace cpp +} // namespace __llvm_libc + +#endif // LLVM_LIBC_SRC_SUPPORT_CPP_VECTOR_H diff --git a/libc/test/utils/CPP/CMakeLists.txt b/libc/test/utils/CPP/CMakeLists.txt --- a/libc/test/utils/CPP/CMakeLists.txt +++ b/libc/test/utils/CPP/CMakeLists.txt @@ -39,3 +39,13 @@ DEPENDS libc.src.__support.CPP.standalone_cpp ) + +add_libc_unittest( + vector_test + SUITE + libc_cpp_utils_unittests + SRCS + vector_test.cpp + DEPENDS + libc.src.__support.CPP.vector +) diff --git a/libc/test/utils/CPP/vector_test.cpp b/libc/test/utils/CPP/vector_test.cpp new file mode 100644 --- /dev/null +++ b/libc/test/utils/CPP/vector_test.cpp @@ -0,0 +1,37 @@ +//===-- Unittests for vector ----------------------------------------------===// +// +// 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/vector.h" +#include "utils/UnitTest/Test.h" + +TEST(LlvmLibcVectorTest, SimpleConstructor) { + __llvm_libc::cpp::vector vec; +} + +TEST(LlvmLibcVectorTest, OrderedWriteOrderedReadTest) { + __llvm_libc::cpp::vector vec; + + for (size_t i = 0; i < 100; i = i + 2) { + vec.push_back(i); + } + ASSERT_EQ(vec.size(), size_t(50)); + ASSERT_GE(vec.capacity(), vec.size()); + for (size_t j = 0; j < vec.size(); ++j) { + ASSERT_EQ(vec[j], j * 2); + } +} + +TEST(LlvmLibcVectorTest, ReserveTest) { + __llvm_libc::cpp::vector vec; + + size_t prev_capacity = vec.capacity(); + + vec.reserve(prev_capacity * 2); + + ASSERT_GT(vec.capacity(), prev_capacity * 2); +}