LCOV - code coverage report
Current view: top level - include/geom - stored_range.h (source / functions) Hit Total Coverage
Test: libMesh/libmesh: #4573 (924896) with base 3f0912 Lines: 72 77 93.5 %
Date: 2026-11-18 21:52:26 Functions: 67 69 97.1 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : // The libMesh Finite Element Library.
       2             : // Copyright (C) 2002-2026 Benjamin S. Kirk, John W. Peterson, Roy H. Stogner
       3             : 
       4             : // This library is free software; you can redistribute it and/or
       5             : // modify it under the terms of the GNU Lesser General Public
       6             : // License as published by the Free Software Foundation; either
       7             : // version 2.1 of the License, or (at your option) any later version.
       8             : 
       9             : // This library is distributed in the hope that it will be useful,
      10             : // but WITHOUT ANY WARRANTY; without even the implied warranty of
      11             : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      12             : // Lesser General Public License for more details.
      13             : 
      14             : // You should have received a copy of the GNU Lesser General Public
      15             : // License along with this library; if not, write to the Free Software
      16             : // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
      17             : 
      18             : 
      19             : 
      20             : #ifndef LIBMESH_STORED_RANGE_H
      21             : #define LIBMESH_STORED_RANGE_H
      22             : 
      23             : // Local includes
      24             : #include "libmesh/threads.h"
      25             : 
      26             : // C++ includes
      27             : #include <type_traits> // std::remove*
      28             : #include <vector>
      29             : #include <memory> // std::unique_ptr
      30             : #include <functional> // std::function
      31             : 
      32             : namespace libMesh
      33             : {
      34             : 
      35             : /**
      36             :  * The \p StoredRange class defines a contiguous, divisible set of objects.
      37             :  * This class is used primarily as the argument to function objects.  The
      38             :  * range can then be subdivided into a number of "tasks" which can be executed
      39             :  * in parallel.  This concept is central to the Threading Building Blocks
      40             :  * template library which can optionally be used by \p libMesh to implement
      41             :  * shared-memory parallelism.
      42             :  *
      43             :  * The implementation takes a user-provided object range and packs it into
      44             :  * a contiguous vector which can then be subdivided efficiently.  A first-cut
      45             :  * implementation using raw element iterators incurred simply too much overhead
      46             :  * by using the predicated iterators, specifically operations such as advancing
      47             :  * such iterators has a cost proportional to the amount the iterator is advanced.
      48             :  * Hence in this implementation the user-provided range is packed into a vector.
      49             :  *
      50             :  * \author Benjamin S. Kirk
      51             :  * \date 2008
      52             :  * \brief Utility class for defining generic ranges for threading.
      53             :  */
      54             : template <typename iterator_type, typename object_type>
      55             : class StoredRange
      56             : {
      57             : public:
      58             :   /**
      59             :    * Allows an \p StoredRange to behave like an STL container.
      60             :    */
      61             :   typedef typename std::vector<object_type> vec_type;
      62             :   typedef const object_type * const_iterator;
      63             :   typedef typename std::unique_ptr<vec_type, std::function<void (vec_type *)>> ptr_type;
      64             : 
      65             :   /**
      66             :    * Allows conversion from non-const to const pointer objects
      67             :    */
      68             :   typedef std::remove_const_t<std::remove_pointer_t<object_type>> * nonconst_object_type;
      69             : 
      70             :   /**
      71             :    * Constructor. Optionally takes the \p grainsize parameter, which is the
      72             :    * smallest chunk the range may be broken into for parallel
      73             :    * execution.
      74             :    */
      75             :   StoredRange (const unsigned int new_grainsize = libMesh::default_grainsize()) :
      76             :     _end(),
      77             :     _begin(),
      78             :     _last(),
      79             :     _first(),
      80             :     _grainsize(new_grainsize),
      81             :     _objs(ptr_type(new vec_type(), [](vec_type * p){delete p;}))
      82             :   {}
      83             : 
      84             :   /**
      85             :    * Constructor.  Takes the beginning and end of the range.
      86             :    * Optionally takes the \p grainsize parameter, which is the
      87             :    * smallest chunk the range may be broken into for parallel
      88             :    * execution.
      89             :    */
      90      616401 :   StoredRange (const iterator_type & first,
      91             :                const iterator_type & last,
      92             :                const unsigned int new_grainsize = libMesh::default_grainsize()) :
      93      176385 :     _end(),
      94      176385 :     _begin(),
      95      176385 :     _last(),
      96      176385 :     _first(),
      97      176385 :     _grainsize(new_grainsize),
      98     1678013 :     _objs(ptr_type(new vec_type(), [](vec_type * p){delete p;}))
      99             :   {
     100      616401 :     this->reset(first, last);
     101      616401 :   }
     102             : 
     103             :   /**
     104             :    * Constructor.  Takes a std::vector of objects.
     105             :    * Optionally takes the \p grainsize parameter, which is the
     106             :    * smallest chunk the range may be broken into for parallel
     107             :    * execution.
     108             :    *
     109             :    * \note The std::vector passed in here MUST live for the
     110             :    * lifetime of this StoredRange! We are not responsible for
     111             :    * deleting this pointer.
     112             :    */
     113      117431 :   StoredRange (vec_type * objs,
     114             :                const unsigned int new_grainsize = libMesh::default_grainsize()) :
     115      117431 :     _end(end_of(*objs)),
     116       69471 :     _begin(objs->data()),
     117       69471 :     _last(objs->size()),
     118       69471 :     _first(0),
     119       69471 :     _grainsize(new_grainsize),
     120      309325 :     _objs(ptr_type(objs, [](vec_type *){/*don't delete*/}))
     121             :   {
     122      117431 :   }
     123             : 
     124             :   /**
     125             :    * Constructor.  Takes pointers to objects, which are expected to
     126             :    * themselves be pointers but with const removed.  This lets us
     127             :    * create a const range view of a saved non-const range.
     128             :    *
     129             :    * Optionally takes the \p grainsize parameter, which is the
     130             :    * smallest chunk the range may be broken into for parallel
     131             :    * execution.
     132             :    *
     133             :    * \note The pointer range passed in here MUST be dereferenceable
     134             :    * for the lifetime of this StoredRange!
     135             :    */
     136       57778 :   StoredRange (const nonconst_object_type * begin,
     137             :                const nonconst_object_type * end,
     138             :                const unsigned int new_grainsize = libMesh::default_grainsize()) :
     139       31497 :     _end(end),
     140       31497 :     _begin(begin),
     141       84059 :     _last(std::distance(begin, end)),
     142       31497 :     _first(0),
     143       31497 :     _grainsize(new_grainsize),
     144       26281 :     _objs(nullptr)
     145             :   {
     146       26281 :   }
     147             : 
     148             :   /**
     149             :    * Copy constructor.  The \p StoredRange can be copied into
     150             :    * subranges for parallel execution.  In this way the
     151             :    * initial \p StoredRange can be thought of as the root of
     152             :    * a binary tree.  The root element is the only element
     153             :    * which interacts with the user.  It takes a specified
     154             :    * range of objects and packs it into a contiguous vector
     155             :    * which can be split efficiently. However, there is no need
     156             :    * for the child ranges to contain this vector, so long as
     157             :    * the parent outlives the children.  So we implement
     158             :    * the copy constructor to specifically omit the \p _objs
     159             :    * vector.
     160             :    */
     161           9 :   StoredRange (const StoredRange<iterator_type,object_type> & er):
     162          15 :     _end(er._end),
     163          15 :     _begin(er._begin),
     164          15 :     _last(er._last),
     165          15 :     _first(er._first),
     166          15 :     _grainsize(er._grainsize),
     167           6 :     _objs(nullptr)
     168             :   {
     169             :     // specifically, do *not* copy the vector
     170           0 :   }
     171             : 
     172             :   /**
     173             :    * NOTE: When using pthreads this constructor is MANDATORY!!!
     174             :    *
     175             :    * Copy constructor.  The \p StoredRange can be copied into
     176             :    * subranges for parallel execution.  In this way the
     177             :    * initial \p StoredRange can be thought of as the root of
     178             :    * a binary tree.  The root element is the only element
     179             :    * which interacts with the user.  It takes a specified
     180             :    * range of objects and packs it into a contiguous vector
     181             :    * which can be split efficiently. However, there is no need
     182             :    * for the child ranges to contain this vector, so long as
     183             :    * the parent outlives the children.  So we implement
     184             :    * the copy constructor to specifically omit the \p _objs
     185             :    * vector. This version allows you to set the beginning and
     186             :    * ending of this new range to be different from that of the
     187             :    * one we're copying.
     188             :    */
     189       17270 :   StoredRange (const StoredRange<iterator_type,object_type> & er,
     190             :                const const_iterator & begin_range,
     191             :                const const_iterator & end_range):
     192        8482 :     _end(end_range),
     193        8482 :     _begin(begin_range),
     194           0 :     _last(0), // Initialize these in a moment
     195           0 :     _first(0),
     196       17270 :     _grainsize(er._grainsize),
     197        8788 :     _objs(nullptr)
     198             :   {
     199             :     // specifically, do *not* copy the vector
     200             : 
     201       17270 :     _first = std::distance(er._begin, _begin);
     202       17270 :     _last = _first + std::distance(_begin, _end);
     203       17270 :   }
     204             : 
     205             :   /**
     206             :    * Splits the range \p r.  The first half
     207             :    * of the range is left in place, the second
     208             :    * half of the range is placed in *this.
     209             :    */
     210             :   StoredRange (StoredRange<iterator_type,object_type> & r, Threads::split ) :
     211             :     _end(r._end),
     212             :     _begin(r._begin),
     213             :     _last(r._last),
     214             :     _first(r._first),
     215             :     _grainsize(r._grainsize),
     216             :     _objs(nullptr)
     217             :   {
     218             :     const_iterator
     219             :       beginning = r._begin,
     220             :       ending    = r._end,
     221             :       middle    = beginning + std::distance(beginning, ending)/2u;
     222             : 
     223             :     r._end = _begin = middle;
     224             : 
     225             :     std::size_t
     226             :       first = r._first,
     227             :       last  = r._last,
     228             :       half  = first + (last-first)/2u;
     229             : 
     230             :     r._last = _first = half;
     231             :   }
     232             : 
     233             :   /**
     234             :    * Destructor.  Releases the object array if we created it.
     235             :    */
     236      698789 :   ~StoredRange () = default;
     237             : 
     238             :   /**
     239             :    * Resets the \p StoredRange to contain [first,last).
     240             :    *
     241             :    * \returns A reference to itself for convenience, so functions
     242             :    * expecting a \p StoredRange<> can be passed e.g. foo.reset(begin,end).
     243             :    */
     244             :   StoredRange<iterator_type, object_type> &
     245      616401 :   reset (const iterator_type & first,
     246             :          const iterator_type & last)
     247             :   {
     248             :     // _objs must be initialized in order to call reset()
     249      305603 :     libmesh_assert(_objs);
     250             : 
     251      305603 :     _objs->clear();
     252             : 
     253    73022229 :     for (iterator_type it=first; it!=last; ++it)
     254    57727217 :       _objs->push_back(*it);
     255             : 
     256      616401 :     _begin = _objs->data();
     257      616401 :     _end   = end_of(*_objs);
     258             : 
     259      616401 :     _first = 0;
     260      616401 :     _last  = _objs->size();
     261             : 
     262      616401 :     return *this;
     263             :   }
     264             : 
     265             :   /**
     266             :    * Resets the range to the last specified range.  This method only exists
     267             :    * for efficiency -- it is more efficient to set the range to its previous
     268             :    * value without rebuilding the underlying vector.
     269             :    *
     270             :    * \returns A reference to itself for convenience, so functions
     271             :    * expecting a StoredRange<> can be passed e.g. foo.reset().
     272             :    */
     273       28433 :   StoredRange<iterator_type, object_type> & reset ()
     274             :   {
     275             :     // _objs must be initialized in order to call reset()
     276       11580 :     libmesh_assert(_objs);
     277             : 
     278       40090 :     _begin = _objs->data();
     279       40090 :     _end   = end_of(*_objs);
     280             : 
     281       23237 :     _first = 0;
     282       34817 :     _last  = _objs->size();
     283             : 
     284       28433 :     return *this;
     285             :   }
     286             : 
     287             :   /**
     288             :    * Beginning of the range.
     289             :    */
     290     1176990 :   const_iterator begin () const { return _begin; }
     291             : 
     292             :   /**
     293             :    * End of the range.
     294             :    */
     295    57690031 :   const_iterator end () const { return _end; }
     296             : 
     297             :   /**
     298             :    * Index in the stored vector of the first object.
     299             :    */
     300        3100 :   std::size_t first_idx () const { return _first; }
     301             : 
     302             :   /**
     303             :    * Index in the stored vector of the last object.
     304             :    */
     305             :   std::size_t last_idx () const { return _last; }
     306             : 
     307             :   /**
     308             :    * The grain size for the range.  The range will be subdivided into
     309             :    * subranges not to exceed the grain size.
     310             :    */
     311      918928 :   std::size_t grainsize () const {return _grainsize;}
     312             : 
     313             :   /**
     314             :    * Set the grain size.
     315             :    */
     316             :   void grainsize (const unsigned int & gs) {_grainsize = gs;}
     317             : 
     318             :   /**
     319             :    * \returns The size of the range.
     320             :    */
     321     1250534 :   std::size_t size () const { return std::distance(_begin, _end); }
     322             : 
     323             :   /**
     324             :    * \returns Whether two ranges are equal.
     325             :    */
     326      151210 :   bool operator== (const StoredRange<iterator_type, object_type> & other) const
     327             :   {
     328    18990355 :     for (auto it = this->begin(), it2 = other.begin();
     329    18990355 :          it != this->end() || it2 != other.end(); ++it, ++it2)
     330             :       {
     331    18839145 :         if (it == this->end() || it2 == other.end())
     332           0 :           return false;
     333             : 
     334    18839145 :         if (*it != *it2)
     335           0 :           return false;
     336             :       }
     337             : 
     338      151210 :     return true;
     339             :   }
     340             : 
     341             :   //------------------------------------------------------------------------
     342             :   // Methods that implement Range concept
     343             :   //------------------------------------------------------------------------
     344             : 
     345             :   /**
     346             :    * \returns \p true if the range is empty.
     347             :    */
     348         618 :   bool empty() const { return (_begin == _end); }
     349             : 
     350             :   /**
     351             :    * \returns \p true if the range can be subdivided.
     352             :    */
     353             :   bool is_divisible() const { return this->grainsize() < static_cast<unsigned int>(std::distance(_begin, _end)); }
     354             : 
     355             : private:
     356             : 
     357             :   /**
     358             :    * Helper for pre-C++26 compiles, where the compiler may have
     359             :    * empty_vector.data() return nullptr and technically pointer
     360             :    * arithmetic on nullptr may be Undefined Behavior.
     361             :    */
     362      333739 :   static const_iterator end_of(vec_type & objs) {
     363      790496 :     return objs.size() ? (objs.data()+objs.size()) : objs.data();
     364             :   }
     365             : 
     366             :   const_iterator _end;
     367             :   const_iterator _begin;
     368             :   std::size_t _last;
     369             :   std::size_t _first;
     370             :   std::size_t _grainsize;
     371             : 
     372             :   ptr_type _objs;
     373             : };
     374             : 
     375             : } // namespace libMesh
     376             : 
     377             : #endif // LIBMESH_STORED_RANGE_H

Generated by: LCOV version 1.14