From e1b77835db9f3f52231c1c34bae7ec92457d6271 Mon Sep 17 00:00:00 2001 From: Martin Kronbichler Date: Thu, 4 Nov 2021 07:10:06 +0100 Subject: [PATCH] Switch from pair to struct --- include/deal.II/particles/particle_accessor.h | 70 +++++++++++--- include/deal.II/particles/particle_handler.h | 7 +- source/particles/particle_handler.cc | 94 +++++++++++-------- tests/particles/particle_iterator_02.cc | 21 ++--- 4 files changed, 122 insertions(+), 70 deletions(-) diff --git a/include/deal.II/particles/particle_accessor.h b/include/deal.II/particles/particle_accessor.h index d09ed9cd58..4b3ff0910c 100644 --- a/include/deal.II/particles/particle_accessor.h +++ b/include/deal.II/particles/particle_accessor.h @@ -45,12 +45,44 @@ namespace Particles class ParticleAccessor { public: + /** + * Data structure to describes the particles in a given cell. This is used + * inside an std::list in `particle_container`. + */ + struct ParticlesInCell + { + /** + * Default constructor. + */ + ParticlesInCell() = default; + + /** + * Construct from a vector of particles and a cell iterator. + */ + ParticlesInCell( + const std::vector::Handle> + &particles, + const typename Triangulation::active_cell_iterator + &cell_iterator) + : particles(particles) + , cell_iterator(cell_iterator) + {} + + /** + * A vector of particles on a cell. + */ + std::vector::Handle> particles; + + /** + * The underlying cell. + */ + typename Triangulation::active_cell_iterator cell_iterator; + }; + /** * A type for the storage container for particles. */ - using particle_container = std::list< - std::pair::Handle>, - typename Triangulation::active_cell_iterator>>; + using particle_container = std::list; /** * @copydoc Particle::write_particle_data_to_memory @@ -744,10 +776,10 @@ namespace Particles ParticleAccessor::get_surrounding_cell() const { Assert(state() == IteratorState::valid, ExcInternalError()); - Assert(particles_in_cell->second.state() == IteratorState::valid, + Assert(particles_in_cell->cell_iterator.state() == IteratorState::valid, ExcInternalError()); - return particles_in_cell->second; + return particles_in_cell->cell_iterator; } @@ -758,10 +790,10 @@ namespace Particles const Triangulation & /*triangulation*/) const { Assert(state() == IteratorState::valid, ExcInternalError()); - Assert(particles_in_cell->second.state() == IteratorState::valid, + Assert(particles_in_cell->cell_iterator.state() == IteratorState::valid, ExcInternalError()); - return particles_in_cell->second; + return particles_in_cell->cell_iterator; } @@ -803,7 +835,7 @@ namespace Particles ++particle_index_within_cell; - if (particle_index_within_cell >= particles_in_cell->first.size()) + if (particle_index_within_cell >= particles_in_cell->particles.size()) { particle_index_within_cell = 0; ++particles_in_cell; @@ -822,9 +854,17 @@ namespace Particles --particle_index_within_cell; else { - --particles_in_cell; - if (particles_in_cell != particles->end()) - particle_index_within_cell = particles_in_cell->first.size() - 1; + if (particles_in_cell == particles->begin()) + { + particles_in_cell = + const_cast(particles)->end(); + } + else + { + --particles_in_cell; + particle_index_within_cell = + particles_in_cell->particles.size() - 1; + } } } @@ -858,9 +898,9 @@ namespace Particles { if (particles != nullptr && property_pool != nullptr && particles_in_cell != particles->end() && - particle_index_within_cell < particles_in_cell->first.size()) + particle_index_within_cell < particles_in_cell->particles.size()) return IteratorState::valid; - else if (particles_in_cell == particles->end() && + else if (particles != nullptr && particles_in_cell == particles->end() && particle_index_within_cell == 0) return IteratorState::past_the_end; else @@ -875,7 +915,7 @@ namespace Particles inline typename PropertyPool::Handle & ParticleAccessor::get_handle() { - return particles_in_cell->first[particle_index_within_cell]; + return particles_in_cell->particles[particle_index_within_cell]; } @@ -884,7 +924,7 @@ namespace Particles inline const typename PropertyPool::Handle & ParticleAccessor::get_handle() const { - return particles_in_cell->first[particle_index_within_cell]; + return particles_in_cell->particles[particle_index_within_cell]; } } // namespace Particles diff --git a/include/deal.II/particles/particle_handler.h b/include/deal.II/particles/particle_handler.h index 7bbd290e1a..ddc2859621 100644 --- a/include/deal.II/particles/particle_handler.h +++ b/include/deal.II/particles/particle_handler.h @@ -79,9 +79,8 @@ namespace Particles /** * A type for the storage container for particles. */ - using particle_container = std::list< - std::pair::Handle>, - typename Triangulation::active_cell_iterator>>; + using particle_container = + typename ParticleAccessor::particle_container; /** * Default constructor. @@ -918,7 +917,7 @@ namespace Particles particle_container owned_particles; /** - * Set of particles currently living in the locally owned cells. + * Set of particles currently living in the ghost cells. */ particle_container ghost_particles; diff --git a/source/particles/particle_handler.cc b/source/particles/particle_handler.cc index 148c599d25..a75d95a981 100644 --- a/source/particles/particle_handler.cc +++ b/source/particles/particle_handler.cc @@ -189,12 +189,12 @@ namespace Particles ParticleHandler::clear_particles() { for (auto &particles_in_cell : owned_particles) - for (auto &particle : particles_in_cell.first) + for (auto &particle : particles_in_cell.particles) if (particle != PropertyPool::invalid_handle) property_pool->deregister_particle(particle); for (auto &particles_in_cell : ghost_particles) - for (auto &particle : particles_in_cell.first) + for (auto &particle : particles_in_cell.particles) if (particle != PropertyPool::invalid_handle) property_pool->deregister_particle(particle); @@ -221,14 +221,14 @@ namespace Particles // sort the particles by the active cell index particles.sort([](const typename ParticleContainer::value_type &a, const typename ParticleContainer::value_type &b) { - return a.second < b.second; + return a.cell_iterator < b.cell_iterator; }); std::array result = {}; for (const auto &particles_in_cell : particles) { const types::particle_index n_particles_in_cell = - particles_in_cell.first.size(); + particles_in_cell.particles.size(); // local_max_particles_per_cell result[0] = std::max(result[0], n_particles_in_cell); @@ -237,7 +237,7 @@ namespace Particles result[2] += n_particles_in_cell; // local_max_particle_index - for (const auto &particle : particles_in_cell.first) + for (const auto &particle : particles_in_cell.particles) { result[1] = std::max(result[1], property_pool.get_id(particle)); } @@ -259,6 +259,18 @@ namespace Particles std::array result_owned = my_update_cached_numbers(*property_pool, owned_particles); +#ifdef DEBUG + std::vector verify_cache( + triangulation->n_active_cells()); + for (auto it = owned_particles.begin(); it != owned_particles.end(); ++it) + verify_cache[it->cell_iterator->active_cell_index()] = it; + for (auto it = ghost_particles.begin(); it != ghost_particles.end(); ++it) + verify_cache[it->cell_iterator->active_cell_index()] = it; + + for (unsigned int i = 0; i < verify_cache.size(); ++i) + Assert(verify_cache[i] == cells_to_particle_cache[i], ExcInternalError()); +#endif + number_of_locally_owned_particles = result_owned[2]; result_owned[0] = std::max(result_owned[0], result_ghosted[0]); result_owned[1] = std::max(result_owned[1], result_ghosted[1]); @@ -300,7 +312,7 @@ namespace Particles return cells_to_particle_cache[cell->active_cell_index()] != typename particle_container::iterator() ? cells_to_particle_cache[cell->active_cell_index()] - ->first.size() : + ->particles.size() : 0; } else @@ -346,23 +358,23 @@ namespace Particles } else { - typename particle_container::iterator particles = + const typename particle_container::iterator particles = cells_to_particle_cache[active_cell_index]; + typename particle_container::iterator next = particles; + ++next; if (cell->is_locally_owned()) { return boost::make_iterator_range( particle_iterator( owned_particles, particles, *property_pool, 0), - particle_iterator( - owned_particles, ++particles, *property_pool, 0)); + particle_iterator(owned_particles, next, *property_pool, 0)); } else { return boost::make_iterator_range( particle_iterator( ghost_particles, particles, *property_pool, 0), - particle_iterator( - ghost_particles, ++particles, *property_pool, 0)); + particle_iterator(ghost_particles, next, *property_pool, 0)); } } } @@ -382,7 +394,7 @@ namespace Particles ParticleHandler::remove_particle( const ParticleHandler::particle_iterator &particle) { - auto &particles_on_cell = particle->particles_in_cell->first; + auto &particles_on_cell = particle->particles_in_cell->particles; // if the particle has an invalid handle (e.g. because it has // been duplicated before calling this function) do not try @@ -428,15 +440,17 @@ namespace Particles // the other function is valid std::vector::particle_iterator> copy( particles_to_remove); - std::sort( - copy.begin(), - copy.end(), - [&](const ParticleHandler::particle_iterator &a, - const ParticleHandler::particle_iterator &b) { - return a->particles_in_cell->second < b->particles_in_cell->second || - (a->particles_in_cell->second == b->particles_in_cell->second && - a->particle_index_within_cell > b->particle_index_within_cell); - }); + std::sort(copy.begin(), + copy.end(), + [&](const ParticleHandler::particle_iterator &a, + const ParticleHandler::particle_iterator &b) { + return a->particles_in_cell->cell_iterator < + b->particles_in_cell->cell_iterator || + (a->particles_in_cell->cell_iterator == + b->particles_in_cell->cell_iterator && + a->particle_index_within_cell > + b->particle_index_within_cell); + }); for (const auto &particle : copy) remove_particle(particle); @@ -478,8 +492,8 @@ namespace Particles cell); else { - cache->first.push_back(handle); - Assert(cache->second == cell, ExcInternalError()); + cache->particles.push_back(handle); + Assert(cache->cell_iterator == cell, ExcInternalError()); } } @@ -504,7 +518,7 @@ namespace Particles particle_iterator particle_it(owned_particles, cache, *property_pool, - cache->first.size() - 1); + cache->particles.size() - 1); data = particle_it->read_particle_data_from_memory(data); @@ -538,7 +552,7 @@ namespace Particles particle_iterator particle_it(owned_particles, cache, *property_pool, - cache->first.size() - 1); + cache->particles.size() - 1); particle_it->set_location(position); particle_it->set_reference_location(reference_position); @@ -1293,8 +1307,9 @@ namespace Particles // Mark it for MPI transfer otherwise if (current_cell->is_locally_owned()) { - auto &old = out_particle->particles_in_cell - ->first[out_particle->particle_index_within_cell]; + auto &old = + out_particle->particles_in_cell + ->particles[out_particle->particle_index_within_cell]; insert_particle(old, current_cell, owned_particles); // Avoid deallocating the memory of this particle @@ -1330,13 +1345,13 @@ namespace Particles typename PropertyPool::Handle sorted_handle = 0; for (auto &particles_in_cell : owned_particles) - for (auto &particle : particles_in_cell.first) + for (auto &particle : particles_in_cell.particles) { unsorted_handles.push_back(particle); particle = sorted_handle++; } for (auto &particles_in_cell : ghost_particles) - for (auto &particle : particles_in_cell.first) + for (auto &particle : particles_in_cell.particles) { unsorted_handles.push_back(particle); particle = sorted_handle++; @@ -1375,12 +1390,12 @@ namespace Particles cells_to_particle_cache[cell->active_cell_index()] != typename particle_container::iterator()) { - Assert(cells_to_particle_cache[cell->active_cell_index()]->second == - cell, + Assert(cells_to_particle_cache[cell->active_cell_index()] + ->cell_iterator == cell, ExcInternalError()); // Clear particle properties for (auto &ghost_particle : - cells_to_particle_cache[cell->active_cell_index()]->first) + cells_to_particle_cache[cell->active_cell_index()]->particles) property_pool->deregister_particle(ghost_particle); // Clear particles themselves @@ -1751,12 +1766,12 @@ namespace Particles received_particles); const typename particle_container::iterator &cache = cells_to_particle_cache[cell->active_cell_index()]; - Assert(cache->second == cell, ExcInternalError()); + Assert(cache->cell_iterator == cell, ExcInternalError()); particle_iterator particle_it(received_particles, cache, *property_pool, - cache->first.size() - 1); + cache->particles.size() - 1); recv_data_it = particle_it->read_particle_data_from_memory(recv_data_it); @@ -1875,7 +1890,7 @@ namespace Particles recv_data_it = recv_particle->read_particle_data_from_memory(recv_data_it); - Assert(recv_particle->particles_in_cell->second->is_ghost(), + Assert(recv_particle->particles_in_cell->cell_iterator->is_ghost(), ExcInternalError()); if (load_callback) @@ -2247,7 +2262,7 @@ namespace Particles break; auto particle = loaded_particles_on_cell.begin(); - for (unsigned int i = 0; i < cache->first.size();) + for (unsigned int i = 0; i < cache->particles.size();) { for (unsigned int child_index = 0; child_index < GeometryInfo::max_children_per_cell; @@ -2271,12 +2286,13 @@ namespace Particles // redo the loop; otherwise move on to next particle if (child_index != 0) { - insert_particle(cache->first[i], + insert_particle(cache->particles[i], child, owned_particles); - cache->first[i] = cache->first.back(); - cache->first.resize(cache->first.size() - 1); + cache->particles[i] = cache->particles.back(); + cache->particles.resize( + cache->particles.size() - 1); } else { diff --git a/tests/particles/particle_iterator_02.cc b/tests/particles/particle_iterator_02.cc index 2907dce62c..17cc1c082f 100644 --- a/tests/particles/particle_iterator_02.cc +++ b/tests/particles/particle_iterator_02.cc @@ -63,10 +63,11 @@ test() typename Particles::ParticleHandler::particle_container particle_container; - particle_container.resize(1); auto particle = pool.register_particle(); - particle_container[0].push_back(particle); + particle_container.emplace_back( + std::vector::Handle>(1, particle), + tr.begin_active()); pool.set_location(particle, position); pool.set_reference_location(particle, reference_position); @@ -78,21 +79,17 @@ test() particle_properties.begin()); Particles::ParticleIterator particle_begin(particle_container, + particle_container.begin(), pool, - tr.begin(), 0); Particles::ParticleIterator particle_end(particle_container, + particle_container.end(), pool, - tr.end(), 0); - Particles::ParticleIterator particle_nonexistent1(particle_container, - pool, - tr.begin(), - 1); - Particles::ParticleIterator particle_nonexistent2(particle_container, - pool, - tr.end(), - 1); + Particles::ParticleIterator particle_nonexistent1( + particle_container, particle_container.begin(), pool, 1); + Particles::ParticleIterator particle_nonexistent2( + particle_container, particle_container.end(), pool, 1); Particles::ParticleIterator particle_invalid; Assert(particle_begin->state() == IteratorState::valid, ExcInternalError()); -- 2.39.5