DtReusableMemoryVector.h

Go to the documentation of this file.

/*****************************************************************************
 * Copyright (c) 2020 MAK Technologies, Inc.
 * All rights reserved.
 *****************************************************************************/

#pragma once

#include <list>
#include <vector>
#include <iostream>

#include <vrvGraphicsUtils/DtAssert.h>

namespace makVrv 
{
   class DtNullRemoval{};

   template<class T, class I, class R = DtNullRemoval>
   // A vector allowing allocation/de-allocation/reuse of blocks of arbitrary size
   // Internally uses a vector.
   // Invalidated memory(range) is tracked and added to 'free' blocks.
   // When a request for a size comes in, will attempt to satisfy the request
   // by finding a 'free' block of that size and update/re-arrange the free blocks 
   // accordingly.
   // If size requested is size of free block, that block is erased.
   // If size requested > size of free block, that block's remainder free memory start, end
   // is updated to reflect the new 'free' block.
   class DtReusableMemoryVector
   {
   public:
      DtReusableMemoryVector();
      ~DtReusableMemoryVector();
   public:
      int findFreeBlock(const size_t sizeRequired);

      std::pair<int, int> remove(const R& removalPredicate);

      void removeIndices(int startIndex, int endIndex);
      
      void printFreeBlocks(void);

      size_t size(void) const;

      const T& operator[](int index) const;

      T& operator[](int index);

      void reserve(size_t reserveSize);

      const T* data(void) const;
      
      void updateFreeBlocks(int startIndex, int endIndex);

   protected:
      struct Block
      {
         int startIndex;
         size_t size;
      };

      typedef std::list<Block> ListFreeBlocks;

      ListFreeBlocks myListFreeBlocks;

      I myInitializerForT;

      typedef std::vector<T> VectorOfTs;
      VectorOfTs myVectorOfTs;
   };


   template<class T, class I, class R>
   DtReusableMemoryVector<T, I, R>::DtReusableMemoryVector()
   {
      //intentional nop
   }
   template<class T, class I, class R>
   DtReusableMemoryVector<T, I, R>::~DtReusableMemoryVector()
   {
      //intentional nop
   }

   template<class T, class I, class R>
   int DtReusableMemoryVector<T, I, R>::findFreeBlock(const size_t sizeRequired)
   {
      int startIndex = -1;
      for (typename ListFreeBlocks::iterator it = myListFreeBlocks.begin(); it != myListFreeBlocks.end(); ++it)
      {
         Block& block = *it;
         if (sizeRequired <= block.size)
         {
            startIndex = block.startIndex;
            if (block.size == sizeRequired)
            {
               myListFreeBlocks.erase(it);
            }
            else
            {
               block.startIndex = startIndex + sizeRequired;
               block.size = block.size - sizeRequired;

            }
            break;
         }
      }

      if (startIndex == -1)
      {
         T info;
         myInitializerForT(info);

         startIndex = myVectorOfTs.size();
         myVectorOfTs.resize(myVectorOfTs.size() + sizeRequired, info);
      }

      return startIndex;
   }

   template<class T, class I, class R>
   void DtReusableMemoryVector<T, I, R>::printFreeBlocks(void)
   {
      std::cout << "free blocks: start" << std::endl;
      for (typename ListFreeBlocks::iterator it = myListFreeBlocks.begin(); it != myListFreeBlocks.end(); ++it)
      {
         std::cout << "block: start: " << it->startIndex << " size: " << it->size << std::endl;
      }
      std::cout << "free blocks: end" << std::endl << std::endl;
   }

   template<class T, class I, class R>
   size_t DtReusableMemoryVector<T, I, R>::size(void) const
   {
      return myVectorOfTs.size();
   }

   template<class T, class I, class R>
   const T& DtReusableMemoryVector<T, I, R>::operator[](int index) const
   {
      return myVectorOfTs[index];
   }

   template<class T, class I, class R>
   T& DtReusableMemoryVector<T, I, R>::operator[](int index)
   {
      return myVectorOfTs[index];
   }

   template<class T, class I, class R>
   std::pair<int,int> DtReusableMemoryVector<T, I, R>::DtReusableMemoryVector::remove(const R& removalPredicate)
   {
      int index = 0;
      int startIndex = -1;
      int endIndex = -1;
      bool removalStarted = false;
      for (typename VectorOfTs::iterator it = myVectorOfTs.begin(); it != myVectorOfTs.end(); ++it, ++index)
      {
         T& info = *it;
         if (removalPredicate(info))
         {
            if (removalStarted == false)
            {
               removalStarted = true;
               startIndex = index;
            }
            if (removalStarted)
            {
               endIndex = index;
            }
            myInitializerForT(info);
         }
      }

      ASSERT_PREDICATE(startIndex < (int)myVectorOfTs.size());
      if(!(startIndex < (int)myVectorOfTs.size()))
      {
         std::cout << "start index not valid!!"<<std::endl;
      }
      
      ASSERT_PREDICATE(endIndex < (int)myVectorOfTs.size());
      if(!(endIndex < (int)myVectorOfTs.size()))
      {
         std::cout << "end index not valid!!" << std::endl;
      }

      updateFreeBlocks(startIndex, endIndex);

      std::pair<int, int> startAndEnd;
      startAndEnd.first = startIndex;
      startAndEnd.second = endIndex;

      return startAndEnd;
   }

   template<class T, class I, class R>
   void DtReusableMemoryVector<T, I, R>::DtReusableMemoryVector::removeIndices(int startIndex, int endIndex)
   {
      ASSERT_PREDICATE(startIndex < (int)myVectorOfTs.size());
      if (!(startIndex < (int)myVectorOfTs.size()))
      {
         std::cout << "start index not valid!!" << std::endl;
      }

      ASSERT_PREDICATE(endIndex < (int)myVectorOfTs.size());
      if (!(endIndex < (int)myVectorOfTs.size()))
      {
         std::cout << "end index not valid!!" << std::endl;
      }

      for(int currIndex = startIndex; currIndex<=endIndex; ++currIndex)
      {
         T& info = myVectorOfTs[currIndex];
         myInitializerForT(info);
      }

      updateFreeBlocks(startIndex, endIndex);
   }

   template<class T, class I, class R>
   void DtReusableMemoryVector<T, I, R>::reserve(size_t reserveSize)
   {
      myVectorOfTs.reserve(reserveSize);
   }

   template<class T, class I, class R>
   const T* DtReusableMemoryVector<T, I, R>::data(void) const
   {
      return myVectorOfTs.data();
   }

   template<class T, class I, class R>
   void DtReusableMemoryVector<T, I, R>::updateFreeBlocks(int startIndex, int endIndex)
   {
      Block block;
      block.startIndex = startIndex;
      block.size = endIndex - startIndex + 1;

      //Find out if this new free block should combine with other free blocks
      for (auto freeBlockItr = myListFreeBlocks.begin(); freeBlockItr != myListFreeBlocks.end();)
      {
         auto nextItr = freeBlockItr;
         nextItr++;
         Block& freeBlock = *freeBlockItr;
         if (freeBlock.startIndex + freeBlock.size == startIndex)
         {
            freeBlock.size = freeBlock.size + block.size;
            block = freeBlock;
            myListFreeBlocks.erase(freeBlockItr);
         } 
         else if (block.startIndex + block.size == freeBlock.startIndex)
         {
            freeBlock.size = freeBlock.size + block.size;
            freeBlock.startIndex = block.startIndex;
            block = freeBlock;
            myListFreeBlocks.erase(freeBlockItr);
         }
         freeBlockItr = nextItr;
      }

      myListFreeBlocks.insert(myListFreeBlocks.end(), block);
   }

}