reuseIndexManagerBase.hpp

/*
 * CoDiPack, a Code Differentiation Package
 *
 * Copyright (C) 2015-2025 Chair for Scientific Computing (SciComp), University of Kaiserslautern-Landau
 * Homepage: http://scicomp.rptu.de
 * Contact:  Prof. Nicolas R. Gauger (codi@scicomp.uni-kl.de)
 *
 * Lead developers: Max Sagebaum, Johannes Blühdorn (SciComp, University of Kaiserslautern-Landau)
 *
 * This file is part of CoDiPack (http://scicomp.rptu.de/software/codi).
 *
 * CoDiPack is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * CoDiPack is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty
 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 *
 * See the GNU General Public License for more details.
 * You should have received a copy of the GNU
 * General Public License along with CoDiPack.
 * If not, see <http://www.gnu.org/licenses/>.
 *
 * For other licensing options please contact us.
 *
 * Authors:
 *  - SciComp, University of Kaiserslautern-Landau:
 *    - Max Sagebaum
 *    - Johannes Blühdorn
 *    - Former members:
 *      - Tim Albring
 */
#pragma once
 
#include <algorithm>
#include <vector>
 
#include "../../config.h"
#include "../../misc/macros.hpp"
#include "../../misc/mathUtility.hpp"
#include "../data/emptyData.hpp"
#include "indexManagerInterface.hpp"
namespace codi {

  template<typename T_Index, typename T_Impl>
  struct ReuseIndexManagerBase : public IndexManagerInterface<T_Index>, public EmptyData {
    public:
 
      using Index = CODI_DD(T_Index, int);                
      using Impl = CODI_DD(T_Impl, CODI_IMPLEMENTATION);  
      using Base = IndexManagerInterface<Index>;          
 
      using Position = EmptyData::Position;  
 
      /*******************************************************************************/
 
      static bool constexpr CopyNeedsStatement = true;  
      static bool constexpr IsLinear = false;           
      static bool constexpr NeedsStaticStorage = true;  

 
    protected:
 
      std::vector<Index> usedIndices;  
      size_t usedIndicesPos;           
 
      std::vector<Index> unusedIndices;  
      size_t unusedIndicesPos;           
 
      size_t indexSizeIncrement;  
 
      bool valid;  
 
    private:
      /*******************************************************************************/

      CODI_INLINE Impl& cast() {
        return static_cast<Impl&>(*this);
      }

      CODI_INLINE Impl const& cast() const {
        return static_cast<Impl const&>(*this);
      }

      CODI_NO_INLINE void generateNewIndices() {
        cast().generateNewIndices();
      }

 
    public:

      ReuseIndexManagerBase()
          : usedIndices(),
            usedIndicesPos(0),
            unusedIndices(),
            unusedIndicesPos(0),
            indexSizeIncrement(Config::SmallChunkSize),
            valid(true) {
        increaseIndicesSize(unusedIndices);
      }

      ~ReuseIndexManagerBase() {
        valid = false;
      }
 
      /*******************************************************************************/

      template<typename Tape>
      CODI_INLINE bool assignIndex(Index& index) {
        bool generatedNewIndex = false;
 
        if (Base::InactiveIndex == index) {
          if (0 == usedIndicesPos) {
            if (0 == unusedIndicesPos) {
              generateNewIndices();
              generatedNewIndex = true;
            }
 
            unusedIndicesPos -= 1;
            index = unusedIndices[unusedIndicesPos];
          } else {
            usedIndicesPos -= 1;
            index = usedIndices[usedIndicesPos];
          }
        }
 
        EventSystem<Tape>::notifyIndexAssignListeners(index);
 
        return generatedNewIndex;
      }

      template<typename Tape>
      CODI_INLINE bool assignUnusedIndex(Index& index) {
        freeIndex<Tape>(index);  // Zero check is performed inside.
 
        bool generatedNewIndex = false;
        if (0 == unusedIndicesPos) {
          generateNewIndices();
          generatedNewIndex = true;
        }
 
        unusedIndicesPos -= 1;
        index = unusedIndices[unusedIndicesPos];
 
        EventSystem<Tape>::notifyIndexAssignListeners(index);
 
        return generatedNewIndex;
      }

      template<typename Tape>
      CODI_INLINE void copyIndex(Index& lhs, Index const& rhs) {
        if (Base::InactiveIndex == rhs) {
          freeIndex<Tape>(lhs);
        } else {
          assignIndex<Tape>(lhs);
        }
      }

      template<typename Tape>
      CODI_INLINE void freeIndex(Index& index) {
        if (valid && Base::InactiveIndex != index) {  // Do not free the zero index.
          codiAssert(index <= cast().getLargestCreatedIndex());
 
          EventSystem<Tape>::notifyIndexFreeListeners(index);
 
          if (usedIndicesPos == usedIndices.size()) {
            increaseIndicesSize(usedIndices);
          }
 
          usedIndices[usedIndicesPos] = index;
          usedIndicesPos += 1;
 
          index = Base::InactiveIndex;
        }
      }

      CODI_NO_INLINE void updateLargestCreatedIndex(Index const& index) {
        /* This method calculates the number of new indices that needs to be added to the unusedIndices vector.
           The length of the unusedIndices vector is adjusted in multiples of indexSizeIncrement.
           This is done by recursively calling by generateNewIndices. */
        if (index > cast().getLargestCreatedIndex()) {
          Index needToGenerate = index - cast().getLargestCreatedIndex();
          size_t newUnusedIndexSize = this->unusedIndicesPos + needToGenerate;
 
          // Round up newUnusedIndexSize to a multiple of indexSizeIncrement and then resize.
          newUnusedIndexSize = getNextMultiple(newUnusedIndexSize, this->indexSizeIncrement);
          this->unusedIndices.resize(newUnusedIndexSize);
 
          // Generate the new unusedIndices in steps of indexSizeIncrement.
          while (index > cast().getLargestCreatedIndex()) {
            generateNewIndices();
          }
        }
      }

      CODI_INLINE void reset() {
        size_t totalSize = usedIndicesPos + unusedIndicesPos;
        if (totalSize > unusedIndices.size()) {
          increaseIndicesSizeTo(unusedIndices, totalSize);
        }
 
        for (size_t pos = 0; pos < usedIndicesPos; ++pos) {
          unusedIndices[unusedIndicesPos + pos] = usedIndices[pos];
        }
        unusedIndicesPos = totalSize;
        usedIndicesPos = 0;
 
        if (Config::SortIndicesOnReset) {
          if (totalSize == unusedIndices.size()) {
            std::sort(unusedIndices.begin(), unusedIndices.end());
          } else {
            std::sort(&unusedIndices[0], &unusedIndices[unusedIndicesPos]);
          }
        }
      }

      void addToTapeValues(TapeValues& values) const {
        unsigned long storedIndices = this->usedIndicesPos + this->unusedIndicesPos;
        unsigned long allocatedIndices = this->usedIndices.size() + this->unusedIndices.size();
 
        double memoryStoredIndices = (double)storedIndices * (double)(sizeof(Index));
        double memoryAllocatedIndices = (double)allocatedIndices * (double)(sizeof(Index));
 
        TapeValues::LocalReductionOperation constexpr operation = Impl::NeedsStaticStorage
                                                                      ? TapeValues::LocalReductionOperation::Max
                                                                      : TapeValues::LocalReductionOperation::Sum;
 
        values.addUnsignedLongEntry("Indices stored", storedIndices, operation);
        values.addDoubleEntry("Memory used", memoryStoredIndices, operation, true, false);
        values.addDoubleEntry("Memory allocated", memoryAllocatedIndices, operation, false, true);
      }

 
    private:
 
      CODI_NO_INLINE void increaseIndicesSize(std::vector<Index>& v) {
        v.resize(v.size() + indexSizeIncrement);
      }
 
      CODI_NO_INLINE void increaseIndicesSizeTo(std::vector<Index>& v, size_t minimalSize) {
        codiAssert(v.size() < minimalSize);
 
        size_t increaseMul = (minimalSize - v.size()) / indexSizeIncrement + 1;  // +1 always rounds up.
        v.resize(v.size() + increaseMul * indexSizeIncrement);
      }
  };
}