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 @@ -8,4 +8,6 @@ StringView.h TypeTraits.h Limits.h + vector.h + vector.cpp ) 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,98 @@ +//===-- 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 +#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_MAX__; + +public: + constexpr vector() : array_size{DEFAULT_SIZE} { + data_array = static_cast(malloc(DEFAULT_SIZE * sizeof(T))); + } + constexpr vector(size_t count) : array_size{count} { + data_array = static_cast(malloc(count * sizeof(T))); + } + constexpr vector(const vector &other) { + array_size = other.capacity(); + data_array = static_cast(malloc(array_size * sizeof(T))); + num_elements = other.size(); + for (size_t i = 0; i < num_elements; ++i) + data_array[i] = other.data()[i]; + } + + ~vector() { free(data_array); } + + constexpr vector &operator=(const vector &other); + constexpr void assign(size_t count, const T &value); + + // can only increase the size of the array + constexpr void reserve(size_t new_cap); + + constexpr void shrink_to_fit(); + + // 0s out all elements, but does not resize the array. + constexpr void clear(); + + constexpr void push_back(const T &value); + constexpr void pop_back(); + + constexpr void resize(size_t count); + // if count increases the size, fill with value. + constexpr void resize(size_t count, const T &value); + + // the std implementation of `at` has bounds checking and throws an exception + // on out of bounds reads, but this implementation cannot use exceptions, so + // it doesn't have bounds checking either. + constexpr T &at(size_t pos) { return data_array[pos]; } + + constexpr T &operator[](size_t pos) { return data_array[pos]; } + constexpr T &front() { return data_array[0]; } + constexpr T &back() { return data_array[num_elements - 1]; } + constexpr T *data() { 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: + // 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); + + // calls realloc on data_array so that its size matches array_size + constexpr void realloc_array(); +}; +} // namespace cpp +} // namespace __llvm_libc + +#endif // LLVM_LIBC_SRC_SUPPORT_CPP_VECTOR_H diff --git a/libc/src/__support/CPP/vector.cpp b/libc/src/__support/CPP/vector.cpp new file mode 100644 --- /dev/null +++ b/libc/src/__support/CPP/vector.cpp @@ -0,0 +1,103 @@ +//===-- 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 +// +//===----------------------------------------------------------------------===// + +#include "src/__support/CPP/vector.h" + +#include // For size_t. + +#include // For malloc/realloc/free + +namespace __llvm_libc { +namespace cpp { + +void simple_memset(void *dst, char value, size_t count) { + char *data_array = static_cast(dst); + for (size_t i = 0; i < count; ++i) + data_array[i] = value; +} + +template +constexpr vector &vector::operator=(const vector &other) { + if (this == &other) + return *this; + + array_size = other.capacity(); + data_array = static_cast(malloc(array_size * sizeof(T))); + num_elements = other.size(); + for (size_t i = 0; i < num_elements; ++i) + data_array[i] = other.data()[i]; + return *this; +} + +template +constexpr void vector::assign(size_t count, const T &value) { + if (array_size < count) + increase_size(count); + num_elements = count; + for (size_t i = 0; i < count; ++i) + data_array[i] = value; +} + +template constexpr void vector::reserve(size_t new_cap) { + if (new_cap < array_size || new_cap > MAX_SIZE) + return; + array_size = new_cap; + realloc_array(); +} + +template constexpr void vector::shrink_to_fit() { + array_size = num_elements; + realloc_array(); +} + +template constexpr void vector::clear() { + simple_memset(data_array, 0, num_elements * sizeof(T)); + num_elements = 0; +} + +template constexpr void vector::push_back(const T &value) { + if (num_elements >= array_size) + increase_size(num_elements + 1); + data_array[num_elements] = value; + ++num_elements; +} + +template constexpr void vector::pop_back() { --num_elements; } + +template constexpr void vector::resize(size_t count) { + if (count > num_elements) + simple_memset(data_array + num_elements, 0, count - num_elements); + num_elements = count; +} + +template +constexpr void vector::resize(size_t count, const T &value) { + if (count > num_elements) { + for (; num_elements < count; ++num_elements) { + data_array[num_elements] = value; + } + } + num_elements = count; +} + +template constexpr void vector::increase_size(size_t new_size) { + size_t temp_size = array_size; + while (temp_size < new_size) + temp_size = temp_size * GROWTH_FACTOR; + if (temp_size >= MAX_SIZE) + return; + array_size = temp_size; + realloc_array(); +} + +template constexpr void vector::realloc_array() { + data_array = static_cast realloc(array_size * sizeof(T)); +} + +} // namespace cpp +} // namespace __llvm_libc