Line data    Source code

       1             : //* This file is part of the MOOSE framework
       2             : //* https://mooseframework.inl.gov
       3             : //*
       4             : //* All rights reserved, see COPYRIGHT for full restrictions
       5             : //* https://github.com/idaholab/moose/blob/master/COPYRIGHT
       6             : //*
       7             : //* Licensed under LGPL 2.1, please see LICENSE for details
       8             : //* https://www.gnu.org/licenses/lgpl-2.1.html
       9             : 
      10             : #pragma once
      11             : 
      12             : #include "Buffer.h"
      13             : 
      14             : namespace MooseUtils
      15             : {
      16             : 
      17             : /**
      18             :  * An optimized circular buffer.
      19             :  *
      20             :  * This also always ensures that begin() < end().
      21             :  * That means that if the end of the buffer capacity is reached, an O(N) operation
      22             :  * will be used to move data from the end of the capacity to the beginning
      23             :  *
      24             :  * This is done so that begin()/end() iterators can be used in OpenMP loops
      25             :  * Also means that operator[] works sequentially between 0 and size()
      26             :  *
      27             :  * It will also automatically grow larger if capacity is reached
      28             :  *
      29             :  * NOTE: This buffer will not properly wrap around as a standard circular buffer
      30             :  * does. Once the end of the internal storage has been reached, the data
      31             :  * will be moved to the beginning of the internal storage via a copy. This is
      32             :  * needed to ensure that the access through the begin()/end() iterators
      33             :  * is contiguous.
      34             :  */
      35             : template <typename T>
      36             : class CircularBuffer : public Buffer<T>
      37             : {
      38             : public:
      39             :   CircularBuffer();
      40             : 
      41             :   CircularBuffer(const std::size_t capacity);
      42             : 
      43             :   virtual void erase(const std::size_t num) override;
      44             :   virtual void eraseChunk(const std::size_t chunk_size) override;
      45             : 
      46             :   virtual typename Buffer<T>::iterator beginChunk(const std::size_t chunk_size) override;
      47             :   virtual typename Buffer<T>::const_iterator
      48             :   beginChunk(const std::size_t chunk_size) const override;
      49             :   virtual typename Buffer<T>::iterator endChunk(const std::size_t chunk_size) override;
      50             :   virtual typename Buffer<T>::const_iterator endChunk(const std::size_t chunk_size) const override;
      51             : 
      52             : protected:
      53             :   virtual std::size_t newEnd(const std::size_t new_end) override;
      54             : };
      55             : 
      56             : template <typename T>
      57             : CircularBuffer<T>::CircularBuffer() : Buffer<T>()
      58             : {
      59             : }
      60             : 
      61             : template <typename T>
      62           1 : CircularBuffer<T>::CircularBuffer(const std::size_t capacity) : Buffer<T>(capacity)
      63             : {
      64           1 : }
      65             : 
      66             : template <typename T>
      67             : void
      68          11 : CircularBuffer<T>::erase(const std::size_t num)
      69             : {
      70             :   mooseAssert(num <= this->size(), "Cannot erase past the last entry");
      71             : 
      72          11 :   this->_begin_pos += num;
      73             : 
      74             :   // If there's nothing in the buffer - let's reset the positions
      75          11 :   if (this->_begin_pos == this->_end_pos)
      76           2 :     this->clear();
      77          11 : }
      78             : 
      79             : template <typename T>
      80             : void
      81           5 : CircularBuffer<T>::eraseChunk(const std::size_t chunk_size)
      82             : {
      83           5 :   if (chunk_size > this->size())
      84           1 :     this->erase(this->size());
      85             :   else
      86           4 :     this->erase(chunk_size);
      87           5 : }
      88             : 
      89             : template <typename T>
      90             : typename Buffer<T>::iterator
      91           5 : CircularBuffer<T>::beginChunk(const std::size_t /* chunk_size */)
      92             : {
      93           5 :   return this->begin();
      94             : }
      95             : 
      96             : template <typename T>
      97             : typename Buffer<T>::const_iterator
      98           0 : CircularBuffer<T>::beginChunk(const std::size_t /* chunk_size */) const
      99             : {
     100           0 :   return this->begin();
     101             : }
     102             : 
     103             : template <typename T>
     104             : typename Buffer<T>::iterator
     105           5 : CircularBuffer<T>::endChunk(const std::size_t chunk_size)
     106             : {
     107           5 :   if (chunk_size > this->size())
     108           1 :     return this->end();
     109             :   else
     110           4 :     return this->begin() + chunk_size;
     111             : }
     112             : 
     113             : template <typename T>
     114             : typename Buffer<T>::const_iterator
     115           0 : CircularBuffer<T>::endChunk(const std::size_t chunk_size) const
     116             : {
     117           0 :   if (chunk_size > this->size())
     118           0 :     return this->end();
     119             :   else
     120           0 :     return this->begin() + chunk_size;
     121             : }
     122             : 
     123             : template <typename T>
     124             : std::size_t
     125          38 : CircularBuffer<T>::newEnd(const std::size_t new_end)
     126             : {
     127          38 :   auto actual_new_end = new_end;
     128             : 
     129          38 :   if (new_end > this->_data.size())
     130             :   {
     131           4 :     const auto new_size = new_end - this->_begin_pos;
     132             : 
     133             :     // See if we need to grow our capacity
     134           4 :     if (this->_begin_pos == 0) // If we're already using the beginning - just resize
     135           1 :       this->_data.resize(2 * new_size);
     136             :     else
     137             :     {
     138             :       // Move everything to the beginning
     139           3 :       auto to_it = this->_data.begin();
     140          14 :       for (auto from_it = this->begin(); from_it < this->end(); ++from_it)
     141          11 :         *to_it++ = std::move(*from_it);
     142             : 
     143           3 :       this->_begin_pos = 0;
     144           3 :       actual_new_end = new_size;
     145             : 
     146             :       // If there still isn't room... add space
     147           3 :       if (actual_new_end > this->_data.size())
     148           1 :         this->_data.resize(2 * new_size);
     149             :     }
     150             :   }
     151             : 
     152          38 :   return actual_new_end;
     153             : }
     154             : 
     155             : }