GraphicsDataCacheBase Class Reference

A base class for the GraphicsDataCache. Implements LRU policy. More...

#include <GraphicsDataCache.h>

Inheritance diagram for GraphicsDataCacheBase:

Collaboration diagram for GraphicsDataCacheBase:

Classes
struct	BaseLookupResult
	A result of the cache lookup. More...
struct	LookupElement
	Element of the cache lookup. More...

Public Member Functions
virtual	~GraphicsDataCacheBase ()=default
void	Invalidate ()
	Invalidate the cache content. More...
double	GetScaledSampleRate () const noexcept
	Returns the sample rate associated with cache. More...
void	UpdateViewportWidth (int64_t width) noexcept
int64_t	GetMaxViewportWidth () const noexcept

Static Public Attributes
static constexpr uint32_t	CacheElementWidth = 256

Protected Types
using	Lookup = std::vector< LookupElement >
	Cache lookup is a vector, with items sorted using Key. More...

Protected Member Functions
	GraphicsDataCacheBase (double scaledSampleRate)
void	SetScaledSampleRate (double scaledSampleRate)
virtual GraphicsDataCacheElementBase *	CreateElement (const GraphicsDataCacheKey &key)=0
	Create a new Cache element. Implementation is responsible of the lifetime control. More...
virtual void	DisposeElement (GraphicsDataCacheElementBase *element)=0
	This method is called, when the cache element should be evicted. Implementation may not deallocate the object. More...
virtual bool	UpdateElement (const GraphicsDataCacheKey &key, GraphicsDataCacheElementBase &element)=0
	This method is called on all elements matching the request that are not complete (i. e. IsComplete if false). More...
BaseLookupResult	PerformBaseLookup (const ZoomInfo &zoomInfo, double t0, double t1)
	Perform a lookup inside the cache. This method modifies mLookup and invalidates any previous result. More...
const GraphicsDataCacheElementBase *	PerformBaseLookup (GraphicsDataCacheKey key)
	Perform a lookup for the given key. This method modifies mLookup and invalidates any previous result. More...

Private Member Functions
bool	CreateNewItems ()
void	DisposeNewItems ()
Lookup::iterator	FindKey (GraphicsDataCacheKey key)
void	PerformCleanup ()
void	PerformFullCleanup (int64_t currentSize, int64_t itemsToEvict)

Private Attributes
Lookup	mLookup
Lookup	mLookupHelper
Lookup	mNewLookupItems
std::vector< size_t >	mLRUHelper
double	mScaledSampleRate {}
int64_t	mMaxWidth { 1600 }
uint64_t	mCacheAccessIndex {}
int32_t	mCacheSizeMultiplier { 4 }

Friends
template<typename CacheElementType >
class	GraphicsDataCacheIterator

Detailed Description

A base class for the GraphicsDataCache. Implements LRU policy.

Definition at line 54 of file GraphicsDataCache.h.

Member Typedef Documentation

Lookup

using GraphicsDataCacheBase::Lookup = std::vector<LookupElement>

protected

Cache lookup is a vector, with items sorted using Key.

Definition at line 83 of file GraphicsDataCache.h.

Constructor & Destructor Documentation

~GraphicsDataCacheBase()

virtual GraphicsDataCacheBase::~GraphicsDataCacheBase ( )

virtualdefault

GraphicsDataCacheBase()

GraphicsDataCacheBase::GraphicsDataCacheBase ( double  scaledSampleRate )

explicitprotected

Definition at line 97 of file GraphicsDataCache.cpp.

    : mScaledSampleRate { sampleRate }
{
}

Member Function Documentation

CreateElement()

virtual GraphicsDataCacheElementBase * GraphicsDataCacheBase::CreateElement ( const GraphicsDataCacheKey &  key )

protectedpure virtual

Create a new Cache element. Implementation is responsible of the lifetime control.

Implemented in GraphicsDataCache< CacheElementType >, GraphicsDataCache< WaveBitmapCacheElement >, and GraphicsDataCache< WaveCacheElement >.

Referenced by CreateNewItems(), and PerformBaseLookup().

Here is the caller graph for this function:

CreateNewItems()

bool GraphicsDataCacheBase::CreateNewItems ( )

private

Definition at line 298 of file GraphicsDataCache.cpp.

{
   for (auto& item : mNewLookupItems)
   {
      item.Data = CreateElement(item.Key);
 
      if (item.Data == nullptr)
         return false;
 
      item.Data->LastUpdate = mCacheAccessIndex;
   }
 
   return true;
}

References CreateElement(), mCacheAccessIndex, and mNewLookupItems.

Referenced by PerformBaseLookup().

Here is the call graph for this function:

Here is the caller graph for this function:

DisposeElement()

virtual void GraphicsDataCacheBase::DisposeElement ( GraphicsDataCacheElementBase *  element )

protectedpure virtual

This method is called, when the cache element should be evicted. Implementation may not deallocate the object.

Implemented in GraphicsDataCache< CacheElementType >, GraphicsDataCache< WaveBitmapCacheElement >, and GraphicsDataCache< WaveCacheElement >.

Referenced by Invalidate(), PerformCleanup(), and PerformFullCleanup().

Here is the caller graph for this function:

DisposeNewItems()

void GraphicsDataCacheBase::DisposeNewItems ( )

private

Definition at line 313 of file GraphicsDataCache.cpp.

{
   std::for_each(
      mNewLookupItems.begin(), mNewLookupItems.end(),
      [](auto elem)
      {
         if (elem.Data != nullptr)
            elem.Data->Dispose();
      });
}

References mNewLookupItems.

Referenced by PerformBaseLookup().

Here is the caller graph for this function:

FindKey()

GraphicsDataCacheBase::Lookup::iterator GraphicsDataCacheBase::FindKey ( GraphicsDataCacheKey  key )

private

Definition at line 325 of file GraphicsDataCache.cpp.

{
   return std::find_if(
      mLookup.begin(), mLookup.end(),
      [sampleRate = mScaledSampleRate, key](auto lhs)
      { return IsSameKey(sampleRate, lhs.Key, key); });
}

References key, mLookup, mScaledSampleRate, and anonymous_namespace{ClipSegmentTest.cpp}::sampleRate.

Referenced by PerformBaseLookup().

Here is the caller graph for this function:

GetMaxViewportWidth()

int64_t GraphicsDataCacheBase::GetMaxViewportWidth ( ) const

noexcept

Definition at line 92 of file GraphicsDataCache.cpp.

{
   return mMaxWidth;
}

References mMaxWidth.

Referenced by WaveBitmapCache::LookupHelper::PerformLookup().

Here is the caller graph for this function:

GetScaledSampleRate()

double GraphicsDataCacheBase::GetScaledSampleRate ( ) const

noexcept

Returns the sample rate associated with cache.

Definition at line 82 of file GraphicsDataCache.cpp.

{
   return mScaledSampleRate;
}

References mScaledSampleRate.

Referenced by WaveDataCache::InitializeElement(), and WaveBitmapCache::LookupHelper::PerformLookup().

Here is the caller graph for this function:

Invalidate()

void GraphicsDataCacheBase::Invalidate

(

)

Invalidate the cache content.

Definition at line 74 of file GraphicsDataCache.cpp.

{
   for (auto& item : mLookup)
      DisposeElement(item.Data);
 
   mLookup.clear();
}

References DisposeElement(), and mLookup.

Referenced by WaveBitmapCache::CheckCache(), WaveBitmapCache::SetPaintParameters(), SetScaledSampleRate(), WaveBitmapCache::SetSelection(), and GraphicsDataCache< CacheElementType >::~GraphicsDataCache().

Here is the call graph for this function:

Here is the caller graph for this function:

PerformBaseLookup() [1/2]

GraphicsDataCacheBase::BaseLookupResult GraphicsDataCacheBase::PerformBaseLookup ( const ZoomInfo &  zoomInfo, double  t0, double  t1  )

protected

Perform a lookup inside the cache. This method modifies mLookup and invalidates any previous result.

Definition at line 123 of file GraphicsDataCache.cpp.

{
   if (bool(t0 > t1) || IsSameSample(mScaledSampleRate, t0, t1))
      return {};
 
   const double pixelsPerSecond = zoomInfo.GetZoom();
 
   const int64_t left  = zoomInfo.TimeToPosition(t0);
   const int64_t right = zoomInfo.TimeToPosition(t1) + 1;
 
   const int64_t width = right - left;
 
   const int64_t cacheLeft       = left / CacheElementWidth;
   const int64_t cacheRight      = (right + CacheElementWidth - 1) / CacheElementWidth;
   const int64_t cacheItemsCount = cacheRight - cacheLeft;
 
   const int64_t cacheLeftColumn  = cacheLeft * CacheElementWidth;
   const int64_t cacheRightColumn = cacheRight * CacheElementWidth;
 
   const double samplesPerPixel = mScaledSampleRate / pixelsPerSecond;
 
   UpdateViewportWidth(width);
 
   mNewLookupItems.clear();
   mNewLookupItems.reserve(cacheItemsCount);
 
   const auto ppsMatchRange =
      GetPPSMatchRange(mLookup, pixelsPerSecond, mScaledSampleRate);
 
   for (int64_t itemIndex = 0; itemIndex < cacheItemsCount; ++itemIndex)
   {
      const int64_t column = cacheLeftColumn + itemIndex * CacheElementWidth;
 
      const int64_t firstSample =
         static_cast<int64_t>(column * samplesPerPixel);
 
      const auto it = std::find_if(
         ppsMatchRange.first, ppsMatchRange.second,
         [firstSample](auto element)
         { return element.Key.FirstSample == firstSample; });
 
      if (it == ppsMatchRange.second)
         mNewLookupItems.push_back({ pixelsPerSecond, firstSample });
   }
 
   bool needsSmoothing = !mNewLookupItems.empty();
 
   ++mCacheAccessIndex;
 
   if (!CreateNewItems())
   {
      DisposeNewItems();
      return {};
   }
 
   mLookupHelper.reserve(mLookup.size() + mNewLookupItems.size());
 
   std::merge(
      mLookup.begin(), mLookup.end(), mNewLookupItems.begin(),
      mNewLookupItems.end(), std::back_inserter(mLookupHelper),
      [sampleRate = mScaledSampleRate](auto lhs, auto rhs)
      { return IsKeyLess(sampleRate, lhs.Key, rhs.Key); });
 
   std::swap(mLookup, mLookupHelper);
   mLookupHelper.clear();
 
   // Find the very first item satisfying the range
   const GraphicsDataCacheKey firstItemKey {
      pixelsPerSecond, int64_t(cacheLeftColumn * samplesPerPixel)
   };
 
   auto it = FindKey(firstItemKey);
 
   assert(it != mLookup.end());
 
   if (it == mLookup.end())
      return {};
 
   GraphicsDataCacheElementBase* prevItem = nullptr;
 
   for (int64_t itemIndex = 0; itemIndex < cacheItemsCount; ++itemIndex)
   {
      auto data = it->Data;
 
      data->LastCacheAccess = mCacheAccessIndex;
      data->AwaitsEviction  = false;
 
      if (!data->IsComplete && data->LastUpdate != mCacheAccessIndex)
      {
         if (!UpdateElement(it->Key, *data))
            return {};
 
         needsSmoothing = true;
      }
 
      if (needsSmoothing)
         data->Smooth(prevItem);
 
      prevItem = data;
 
      ++it;
   }
 
   PerformCleanup();
 
   it        = FindKey(firstItemKey);
   auto last = it;
 
   std::advance(last, cacheItemsCount);
 
   return { it, last,
            static_cast<size_t>(std::max(int64_t(0), left - cacheLeftColumn)),
            static_cast<size_t>(
               std::max(int64_t(0), cacheRightColumn - right)) };
}

References CacheElementWidth, CreateNewItems(), DisposeNewItems(), FindKey(), anonymous_namespace{GraphicsDataCache.cpp}::GetPPSMatchRange(), ZoomInfo::GetZoom(), anonymous_namespace{GraphicsDataCache.cpp}::IsSameSample(), GraphicsDataCacheElementBase::LastCacheAccess, mCacheAccessIndex, mLookup, mLookupHelper, mNewLookupItems, mScaledSampleRate, PerformCleanup(), anonymous_namespace{ClipSegmentTest.cpp}::sampleRate, anonymous_namespace{NoteTrack.cpp}::swap(), ZoomInfo::TimeToPosition(), UpdateElement(), and UpdateViewportWidth().

Referenced by GraphicsDataCache< CacheElementType >::PerformLookup().

Here is the call graph for this function:

Here is the caller graph for this function:

PerformBaseLookup() [2/2]

const GraphicsDataCacheElementBase * GraphicsDataCacheBase::PerformBaseLookup ( GraphicsDataCacheKey  key )

protected

Perform a lookup for the given key. This method modifies mLookup and invalidates any previous result.

Definition at line 241 of file GraphicsDataCache.cpp.

{
   auto it = FindKey(key);
 
   ++mCacheAccessIndex;
 
   if (it != mLookup.end())
   {
      GraphicsDataCacheElementBase* data = it->Data;
 
      if (!data->IsComplete && data->LastUpdate != mCacheAccessIndex)
      {
         if (!UpdateElement(it->Key, *data))
            return {};
      }
 
      data->Smooth(it == mLookup.begin() ? nullptr : (it - 1)->Data);
 
      return data;
   }
 
   mNewLookupItems.clear();
   mNewLookupItems.reserve(1);
 
   mNewLookupItems.push_back({ key, nullptr });
 
   LookupElement newElement { key, CreateElement(key) };
 
   if (newElement.Data == nullptr)
      return nullptr;
 
   newElement.Data->LastUpdate      = mCacheAccessIndex;
   newElement.Data->LastCacheAccess = mCacheAccessIndex;
   newElement.Data->AwaitsEviction  = false;
 
   auto insertedPosition = mLookup.insert(
      std::upper_bound(
         mLookup.begin(), mLookup.end(), key,
         [sampleRate = mScaledSampleRate](auto lhs, auto rhs)
         {
            if constexpr (std::is_same_v<
                             std::decay_t<decltype(lhs)>, GraphicsDataCacheKey>)
               return IsKeyLess(sampleRate, lhs, rhs.Key);
            else
               return IsKeyLess(sampleRate, lhs.Key, rhs);
         }),
      newElement);
 
   newElement.Data->Smooth(
      insertedPosition == mLookup.begin() ? nullptr :
                                            (insertedPosition - 1)->Data);
 
   PerformCleanup();
 
   return newElement.Data;
}

References CreateElement(), FindKey(), GraphicsDataCacheElementBase::IsComplete, key, GraphicsDataCacheElementBase::LastUpdate, mCacheAccessIndex, mLookup, mNewLookupItems, mScaledSampleRate, PerformCleanup(), anonymous_namespace{ClipSegmentTest.cpp}::sampleRate, GraphicsDataCacheElementBase::Smooth(), and UpdateElement().

Here is the call graph for this function:

PerformCleanup()

void GraphicsDataCacheBase::PerformCleanup ( )

private

Definition at line 333 of file GraphicsDataCache.cpp.

{
   const int64_t lookupSize = static_cast<int64_t>(mLookup.size());
 
   const auto allowedItems =
      RoundUpUnsafe(mMaxWidth, CacheElementWidth) * mCacheSizeMultiplier;
 
   const int64_t itemsToEvict = lookupSize - allowedItems;
 
   if (itemsToEvict <= 0)
      return;
 
   if (itemsToEvict == 1)
   {
      auto it = std::min_element(
         mLookup.begin(), mLookup.end(),
         [](auto lhs, auto rhs)
         { return lhs.Data->LastCacheAccess < rhs.Data->LastCacheAccess; });
 
      if (it->Data->LastCacheAccess < mCacheAccessIndex)
      {
         DisposeElement(it->Data);
         mLookup.erase(it);
      }
   }
   else
   {
      PerformFullCleanup(lookupSize, itemsToEvict);
   }
}

References CacheElementWidth, DisposeElement(), mCacheAccessIndex, mCacheSizeMultiplier, mLookup, mMaxWidth, PerformFullCleanup(), and RoundUpUnsafe().

Referenced by PerformBaseLookup().

Here is the call graph for this function:

Here is the caller graph for this function:

PerformFullCleanup()

void GraphicsDataCacheBase::PerformFullCleanup ( int64_t  currentSize, int64_t  itemsToEvict  )

private

Definition at line 364 of file GraphicsDataCache.cpp.

{
   mLRUHelper.reserve(currentSize);
 
   for (size_t i = 0; i < currentSize; ++i)
      mLRUHelper.push_back(i);
 
   std::make_heap(
      mLRUHelper.begin(), mLRUHelper.end(),
      [this](size_t lhs, size_t rhs)
      {
         return mLookup[lhs].Data->LastCacheAccess >
                mLookup[rhs].Data->LastCacheAccess;
      });
 
   for (int64_t itemIndex = 0; itemIndex < itemsToEvict; ++itemIndex)
   {
      std::pop_heap(mLRUHelper.begin(), mLRUHelper.end());
 
      const size_t index = mLRUHelper.back();
      mLRUHelper.pop_back();
 
      auto data = mLookup[index].Data;
 
      if (data->LastCacheAccess >= mCacheAccessIndex)
         break;
 
      DisposeElement(data);
      data->AwaitsEviction = true;
   }
 
   mLookup.erase(
      std::remove_if(
         mLookup.begin(), mLookup.end(),
         [](auto item) { return item.Data->AwaitsEviction; }),
      mLookup.end());
 
   mLRUHelper.clear();
}

References DisposeElement(), mCacheAccessIndex, mLookup, and mLRUHelper.

Referenced by PerformCleanup().

Here is the call graph for this function:

Here is the caller graph for this function:

SetScaledSampleRate()

void GraphicsDataCacheBase::SetScaledSampleRate ( double  scaledSampleRate )

protected

Definition at line 102 of file GraphicsDataCache.cpp.

{
   if (
      std::abs(mScaledSampleRate - scaledSampleRate) <=
      std::numeric_limits<double>::epsilon())
      return;
 
   mScaledSampleRate = scaledSampleRate;
   Invalidate();
}

References Invalidate(), and mScaledSampleRate.

Referenced by WaveBitmapCache::WaveBitmapCache().

Here is the call graph for this function:

Here is the caller graph for this function:

UpdateElement()

virtual bool GraphicsDataCacheBase::UpdateElement ( const GraphicsDataCacheKey &  key, GraphicsDataCacheElementBase &  element  )

protectedpure virtual

This method is called on all elements matching the request that are not complete (i. e. IsComplete if false).

Implemented in GraphicsDataCache< CacheElementType >, GraphicsDataCache< WaveBitmapCacheElement >, and GraphicsDataCache< WaveCacheElement >.

Referenced by PerformBaseLookup().

Here is the caller graph for this function:

UpdateViewportWidth()

void GraphicsDataCacheBase::UpdateViewportWidth ( int64_t  width )

noexcept

Definition at line 87 of file GraphicsDataCache.cpp.

{
   mMaxWidth = std::max(mMaxWidth, width);
}

Referenced by PerformBaseLookup().

Here is the caller graph for this function:

Friends And Related Function Documentation

GraphicsDataCacheIterator

template<typename CacheElementType >

friend class GraphicsDataCacheIterator

friend

Definition at line 143 of file GraphicsDataCache.h.

Member Data Documentation

CacheElementWidth

constexpr uint32_t GraphicsDataCacheBase::CacheElementWidth = 256

staticconstexpr

Definition at line 58 of file GraphicsDataCache.h.

Referenced by anonymous_namespace{GraphicsDataCacheTests.cpp}::CheckCacheElementLookup(), anonymous_namespace{WaveformView.cpp}::WaveformPainter::Draw(), WaveDataCache::InitializeElement(), anonymous_namespace{GraphicsDataCache.cpp}::IsSamePPS(), PerformBaseLookup(), PerformCleanup(), and TEST_CASE().

mCacheAccessIndex

uint64_t GraphicsDataCacheBase::mCacheAccessIndex {}

private

Definition at line 138 of file GraphicsDataCache.h.

Referenced by CreateNewItems(), PerformBaseLookup(), PerformCleanup(), and PerformFullCleanup().

mCacheSizeMultiplier

int32_t GraphicsDataCacheBase::mCacheSizeMultiplier { 4 }

private

Definition at line 140 of file GraphicsDataCache.h.

Referenced by PerformCleanup().

mLookup

Lookup GraphicsDataCacheBase::mLookup

private

Definition at line 124 of file GraphicsDataCache.h.

Referenced by FindKey(), Invalidate(), PerformBaseLookup(), PerformCleanup(), and PerformFullCleanup().

mLookupHelper

Lookup GraphicsDataCacheBase::mLookupHelper

private

Definition at line 126 of file GraphicsDataCache.h.

Referenced by PerformBaseLookup().

mLRUHelper

std::vector<size_t> GraphicsDataCacheBase::mLRUHelper

private

Definition at line 130 of file GraphicsDataCache.h.

Referenced by PerformFullCleanup().

mMaxWidth

int64_t GraphicsDataCacheBase::mMaxWidth { 1600 }

private

Definition at line 136 of file GraphicsDataCache.h.

Referenced by GetMaxViewportWidth(), and PerformCleanup().

mNewLookupItems

Lookup GraphicsDataCacheBase::mNewLookupItems

private

Definition at line 128 of file GraphicsDataCache.h.

Referenced by CreateNewItems(), DisposeNewItems(), and PerformBaseLookup().

mScaledSampleRate

double GraphicsDataCacheBase::mScaledSampleRate {}

private

Definition at line 133 of file GraphicsDataCache.h.

Referenced by FindKey(), GetScaledSampleRate(), PerformBaseLookup(), and SetScaledSampleRate().

---

The documentation for this class was generated from the following files:

• GraphicsDataCache.h
• GraphicsDataCache.cpp