From 806f042a765738f44aaf325e4d46c9a65eedb92d Mon Sep 17 00:00:00 2001 From: David Wells Date: Thu, 27 Jun 2024 15:05:27 -0400 Subject: [PATCH] AlignedVector: add AlignedVector::insert(). --- doc/news/changes/minor/20240926DavidWells | 4 ++ include/deal.II/base/aligned_vector.h | 65 +++++++++++++++++++++++ tests/base/aligned_vector_01.cc | 37 ++++++++++++- tests/base/aligned_vector_01.output | 5 +- 4 files changed, 108 insertions(+), 3 deletions(-) create mode 100644 doc/news/changes/minor/20240926DavidWells diff --git a/doc/news/changes/minor/20240926DavidWells b/doc/news/changes/minor/20240926DavidWells new file mode 100644 index 0000000000..c034e341ba --- /dev/null +++ b/doc/news/changes/minor/20240926DavidWells @@ -0,0 +1,4 @@ +Improved: Added AlignedVector::insert(), which works the same way as +std::vector::insert(). +
+(David Wells, 2024/09/26) diff --git a/include/deal.II/base/aligned_vector.h b/include/deal.II/base/aligned_vector.h index 84e74980d3..9650776940 100644 --- a/include/deal.II/base/aligned_vector.h +++ b/include/deal.II/base/aligned_vector.h @@ -255,6 +255,24 @@ public: void insert_back(ForwardIterator begin, ForwardIterator end); + /** + * Insert the range specified by @p begin and @p end after the element @p position. + * + * @note Unlike std::vector, this function uses random-access iterators so + * that the copy may be parallelized. + * + * @dealiiOperationIsMultithreaded + */ + template < + typename RandomAccessIterator, + typename = std::enable_if_t::iterator_category, + std::random_access_iterator_tag>>> + iterator + insert(const_iterator position, + RandomAccessIterator begin, + RandomAccessIterator end); + /** * Fills the vector with size() copies of a default constructed object. * @@ -1572,6 +1590,53 @@ AlignedVector::insert_back(ForwardIterator begin, ForwardIterator end) +template +template +inline typename AlignedVector::iterator +AlignedVector::insert(const_iterator position, + RandomAccessIterator begin, + RandomAccessIterator end) +{ + Assert(replicated_across_communicator == false, + ExcAlignedVectorChangeAfterReplication()); + Assert(this->begin() <= position && position <= this->end(), + ExcMessage("The position iterator is not valid.")); + const auto offset = position - this->begin(); + + const size_type old_size = size(); + const size_type range_size = end - begin; + const size_type new_size = old_size + range_size; + if (range_size != 0) + { + // This is similar to allocate_and_move(), except that we need to move + // whatever was before position and whatever is after it into two + // different places + T *new_data_ptr = nullptr; + Utilities::System::posix_memalign( + reinterpret_cast(&new_data_ptr), 64, new_size * sizeof(T)); + + // Correctly handle the case where the range is inside the present array + // by creating a temporary. + AlignedVector temporary(begin, end); + dealii::internal::AlignedVectorMoveConstruct( + elements.get(), elements.get() + offset, new_data_ptr); + dealii::internal::AlignedVectorMoveConstruct( + temporary.begin(), temporary.end(), new_data_ptr + offset); + dealii::internal::AlignedVectorMoveConstruct( + elements.get() + offset, + elements.get() + old_size, + new_data_ptr + offset + range_size); + + Deleter deleter(this); + elements = decltype(elements)(new_data_ptr, std::move(deleter)); + used_elements_end = elements.get() + new_size; + allocated_elements_end = elements.get() + new_size; + } + return this->begin() + offset; +} + + + template inline void AlignedVector::fill() diff --git a/tests/base/aligned_vector_01.cc b/tests/base/aligned_vector_01.cc index af0831ef6f..6d3b748b38 100644 --- a/tests/base/aligned_vector_01.cc +++ b/tests/base/aligned_vector_01.cc @@ -62,7 +62,42 @@ test() ExcInternalError()); } - deallog << "Insertion: "; + // Also check large insertions for equality and iterator position + { + std::deque temp(8192); + std::iota(temp.begin(), temp.end(), 0u); + + VEC f(temp.begin(), temp.begin() + temp.size() / 4); + const auto it0 = + f.insert(f.end(), temp.begin() + temp.size() / 2, temp.end()); + AssertThrow(static_cast(it0 - f.begin()) == temp.size() / 4, + ExcInternalError()); + AssertThrow(*it0 == temp[temp.size() / 2], ExcInternalError()); + AssertThrow(*(it0 - 1) == temp[temp.size() / 4 - 1], ExcInternalError()); + AssertThrow(f.back() == temp.back(), ExcInternalError()); + + const auto it1 = f.insert(f.begin() + temp.size() / 4, + temp.begin() + temp.size() / 4, + temp.begin() + temp.size() / 2); + AssertThrow(static_cast(it1 - f.begin()) == temp.size() / 4, + ExcInternalError()); + AssertThrow(*it1 == temp[temp.size() / 4], ExcInternalError()); + AssertThrow(std::equal(f.begin(), f.end(), temp.begin()), + ExcInternalError()); + } + + deallog << "back Insertion: "; + for (unsigned int i = 0; i < a.size(); ++i) + deallog << a[i] << ' '; + deallog << std::endl; + + { + AlignedVector temp(4); + std::fill(temp.begin(), temp.end(), 42u); + a.insert(a.begin() + 4, temp.begin(), temp.end()); + } + deallog << "Insertion at position 4: "; + for (unsigned int i = 0; i < a.size(); ++i) deallog << a[i] << ' '; deallog << std::endl; diff --git a/tests/base/aligned_vector_01.output b/tests/base/aligned_vector_01.output index 17920c6f64..22827eac2e 100644 --- a/tests/base/aligned_vector_01.output +++ b/tests/base/aligned_vector_01.output @@ -1,7 +1,8 @@ DEAL::Constructor: 0 0 0 0 -DEAL::Insertion: 0 0 1 0 5 42 0 0 1 0 5 42 27 -DEAL::Memory Shrinking: 112 to 64 +DEAL::back Insertion: 0 0 1 0 5 42 0 0 1 0 5 42 27 +DEAL::Insertion at position 4: 0 0 1 0 42 42 42 42 5 42 0 0 1 0 5 42 27 +DEAL::Memory Shrinking: 116 to 64 DEAL::Shrinking: 0 0 1 0 DEAL::Reserve: 0 0 1 0 DEAL::Assignment: 0 0 1 0 5 42 27 -- 2.39.5