bkietz commented on a change in pull request #10915: URL: https://github.com/apache/arrow/pull/10915#discussion_r692048362
########## File path: cpp/src/arrow/util/small_vector.h ########## @@ -0,0 +1,499 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +#pragma once + +#include <algorithm> +#include <cassert> +#include <cstddef> +#include <initializer_list> +#include <iterator> +#include <limits> +#include <new> +#include <type_traits> +#include <utility> + +#include "arrow/util/launder.h" +#include "arrow/util/macros.h" + +namespace arrow { +namespace internal { + +template <typename T> +struct StaticVectorMixin { + // properly aligned uninitialized storage for N T's + using storage_type = typename std::aligned_storage<sizeof(T), alignof(T)>::type; + + static T* ptr_at(storage_type* p, size_t i) { + return launder(reinterpret_cast<T*>(&p[i])); + } + + static constexpr const T* ptr_at(const storage_type* p, size_t i) { + return launder(reinterpret_cast<const T*>(&p[i])); + } + + static void move_storage(storage_type* src, storage_type* dest, size_t n) { + for (size_t i = 0; i < n; ++i) { + T* src_item = ptr_at(src, i); + T* dest_item = ptr_at(dest, i); + new (dest_item) T(std::move(*src_item)); + src_item->~T(); + } + } + + static void destroy_storage(storage_type* p, size_t n) { + for (size_t i = 0; i < n; ++i) { + ptr_at(p, i)->~T(); + } + } +}; + +template <typename T, size_t N, bool NonTrivialDestructor> +struct StaticVectorStorageBase : public StaticVectorMixin<T> { + using typename StaticVectorMixin<T>::storage_type; + + storage_type static_data_[N]; + size_t size_ = 0; + + void destroy() {} +}; + +template <typename T, size_t N> +struct StaticVectorStorageBase<T, N, true> : public StaticVectorMixin<T> { + using typename StaticVectorMixin<T>::storage_type; + + storage_type static_data_[N]; + size_t size_ = 0; + + ~StaticVectorStorageBase() noexcept { destroy(); } + + void destroy() noexcept { this->destroy_storage(static_data_, size_); } +}; + +template <typename T, size_t N, bool D = !std::is_trivially_destructible<T>::value> +struct StaticVectorStorage : public StaticVectorStorageBase<T, N, D> { + using Base = StaticVectorStorageBase<T, N, D>; + using typename Base::storage_type; + + using Base::size_; + using Base::static_data_; + + StaticVectorStorage() noexcept = default; + + T* data_ptr() { return this->ptr_at(static_data_, 0); } + + constexpr const T* const_data_ptr() const { return this->ptr_at(static_data_, 0); } + + // Adjust storage size, but don't initialize any objects + void bump_size(size_t addend) { + assert(size_ + addend <= N); + size_ += addend; + } + + void ensure_capacity(size_t min_capacity) { assert(min_capacity <= N); } + + // Adjust storage size, but don't destroy any objects + void reduce_size(size_t reduce_by) { + assert(reduce_by <= size_); + size_ -= reduce_by; + } + + // Move objects from another storage, but don't destroy any objects currently + // stored in *this. + // You need to call destroy() first if necessary (e.g. in a + // move assignment operator). + void move_from(StaticVectorStorage&& other) noexcept { + size_ = other.size_; + this->move_storage(other.static_data_, static_data_, size_); + other.size_ = 0; + } + + constexpr size_t capacity() const { return N; } + + constexpr size_t max_size() const { return N; } + + void reserve(size_t n) {} + + void clear() { + this->destroy_storage(static_data_, size_); + size_ = 0; + } +}; + +template <typename T, size_t N> +struct SmallVectorStorage : public StaticVectorMixin<T> { + using typename StaticVectorMixin<T>::storage_type; + + storage_type static_data_[N]; + size_t size_ = 0; + storage_type* data_ = static_data_; + size_t dynamic_capacity_ = 0; + + SmallVectorStorage() noexcept = default; + + ~SmallVectorStorage() { destroy(); } + + T* data_ptr() { return this->ptr_at(data_, 0); } + + constexpr const T* const_data_ptr() const { return this->ptr_at(data_, 0); } + + void bump_size(size_t addend) { + const size_t new_size = size_ + addend; + ensure_capacity(new_size); + size_ = new_size; + } + + void ensure_capacity(size_t min_capacity) { + if (dynamic_capacity_) { + // Grow dynamic storage if necessary + if (min_capacity > dynamic_capacity_) { + size_t new_capacity = std::max(dynamic_capacity_ * 2, min_capacity); + reallocate_dynamic(new_capacity); + } + } else if (min_capacity > N) { + switch_to_dynamic(min_capacity); + } + } + + void reduce_size(size_t reduce_by) { + assert(reduce_by <= size_); + size_ -= reduce_by; + } + + void destroy() { + this->destroy_storage(data_, size_); + if (dynamic_capacity_) { + delete[] data_; + } + } + + void move_from(SmallVectorStorage&& other) noexcept { + size_ = other.size_; + dynamic_capacity_ = other.dynamic_capacity_; + if (dynamic_capacity_) { + data_ = other.data_; + other.data_ = NULLPTR; + other.dynamic_capacity_ = 0; + } else { + this->move_storage(other.data_, data_, size_); + } + other.size_ = 0; + } + + constexpr size_t capacity() const { return dynamic_capacity_ ? dynamic_capacity_ : N; } + + constexpr size_t max_size() const { return std::numeric_limits<size_t>::max(); } + + void reserve(size_t n) { + if (dynamic_capacity_) { + if (n > dynamic_capacity_) { + reallocate_dynamic(n); + } + } else if (n > N) { + switch_to_dynamic(n); + } + } + + void clear() { + this->destroy_storage(data_, size_); + size_ = 0; + } + + private: + void switch_to_dynamic(size_t new_capacity) { + dynamic_capacity_ = new_capacity; + data_ = new storage_type[new_capacity]; + this->move_storage(static_data_, data_, size_); + } + + void reallocate_dynamic(size_t new_capacity) { + assert(new_capacity >= size_); + auto new_data = new storage_type[new_capacity]; + this->move_storage(data_, new_data, size_); + delete[] data_; + dynamic_capacity_ = new_capacity; + data_ = new_data; + } +}; + +template <typename T, size_t N, typename Storage> +class StaticVectorImpl { + private: + Storage storage_; + + T* data_ptr() { return storage_.data_ptr(); } + + constexpr const T* const_data_ptr() const { return storage_.const_data_ptr(); } + + public: + using size_type = size_t; + using difference_type = ptrdiff_t; + using value_type = T; + using pointer = T*; + using const_pointer = const T*; + using reference = T&; + using const_reference = const T&; + using iterator = T*; + using const_iterator = const T*; + + constexpr StaticVectorImpl() noexcept = default; + + // Move and copy constructors + StaticVectorImpl(StaticVectorImpl&& other) noexcept { + storage_.move_from(std::move(other.storage_)); + } + + StaticVectorImpl& operator=(StaticVectorImpl&& other) noexcept { + if (&other != this) { + storage_.destroy(); + storage_.move_from(std::move(other.storage_)); + } + return *this; + } + + StaticVectorImpl(const StaticVectorImpl& other) { + init_by_copying(other.storage_.size_, other.const_data_ptr()); + } + + StaticVectorImpl& operator=(const StaticVectorImpl& other) noexcept { + if (&other == this) { + return *this; + } + assign_by_copying(other.storage_.size_, other.data()); + return *this; + } + + // Automatic conversion from std::vector<T>, for convenience + StaticVectorImpl(const std::vector<T>& other) { // NOLINT: explicit + init_by_copying(other.size(), other.data()); + } + + StaticVectorImpl(std::vector<T>&& other) noexcept { // NOLINT: explicit + init_by_moving(other.size(), other.data()); + } + + StaticVectorImpl& operator=(const std::vector<T>& other) { + assign_by_copying(other.size(), other.data()); + return *this; + } + + StaticVectorImpl& operator=(std::vector<T>&& other) noexcept { + assign_by_moving(other.size(), other.data()); + return *this; + } + + // Constructing from count and optional initialization value + explicit StaticVectorImpl(size_t count) { + storage_.bump_size(count); + auto* p = data_ptr(); + for (size_t i = 0; i < count; ++i) { + new (&p[i]) T(); + } + } + + StaticVectorImpl(size_t count, const T& value) { + storage_.bump_size(count); + auto* p = data_ptr(); + for (size_t i = 0; i < count; ++i) { + new (&p[i]) T(value); + } + } + + StaticVectorImpl(std::initializer_list<T> values) { + storage_.bump_size(values.size()); + auto* p = data_ptr(); + for (auto&& v : values) { + // XXX cannot move initializer values? + new (p++) T(v); + } + } + + constexpr bool empty() const { return storage_.size_ == 0; } + + constexpr size_t size() const { return storage_.size_; } + + constexpr size_t capacity() const { return storage_.capacity(); } + + constexpr size_t max_size() const { return storage_.max_size(); } + + T& operator[](size_t i) { return data_ptr()[i]; } + + constexpr const T& operator[](size_t i) const { return const_data_ptr()[i]; } + + T& front() { return data_ptr()[0]; } + + constexpr const T& front() const { return const_data_ptr()[0]; } + + T& back() { return data_ptr()[storage_.size_ - 1]; } + + constexpr const T& back() const { return const_data_ptr()[storage_.size_ - 1]; } + + T* data() { return data_ptr(); } + + constexpr const T* data() const { return const_data_ptr(); } + + iterator begin() { return iterator(data_ptr()); } + + constexpr const_iterator begin() const { return const_iterator(const_data_ptr()); } + + iterator end() { return iterator(data_ptr() + storage_.size_); } + + constexpr const_iterator end() const { + return const_iterator(const_data_ptr() + storage_.size_); + } + + void reserve(size_t n) { storage_.reserve(n); } + + void clear() { storage_.clear(); } + + void push_back(const T& value) { + storage_.bump_size(1); + new (data_ptr() + storage_.size_ - 1) T(value); + } + + void push_back(T&& value) { + storage_.bump_size(1); + new (data_ptr() + storage_.size_ - 1) T(std::move(value)); + } + + template <typename... Args> + void emplace_back(Args&&... args) { + storage_.bump_size(1); + new (data_ptr() + storage_.size_ - 1) T(std::forward<Args>(args)...); + } + + template <typename InputIt> + iterator insert(const_iterator insert_at, InputIt first, InputIt last) { + const size_t n = storage_.size_; + const size_t it_size = static_cast<size_t>(last - first); // XXX might be O(n)? Review comment: (IIUC the most common non-random access iterators we use in the arrow codebase are `unordered_{set,map}::iterator`, so the consequence here would be `small_vec.insert(small_vec.begin() + 3, set.begin(), set.end())` won't compile) -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: github-unsubscr...@arrow.apache.org For queries about this service, please contact Infrastructure at: us...@infra.apache.org
