PsoLruCache.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "CoreTypes.h"
#include "Containers/Set.h"
#include "Misc/AssertionMacros.h"
 
/* Implements a Least Recently Used (LRU) cache.
 *
 * @param KeyType The type of cache entry keys.
 * @param ValueType The type of cache entry values.
 */
template<typename KeyType, typename ValueType>
class TPsoLruCache
{
    struct FCacheEntry
    {
        KeyType Key;
 
        FCacheEntry* LessRecent;
 
        FCacheEntry* MoreRecent;
 
        ValueType Value;
 
        FCacheEntry(const KeyType& InKey, const ValueType& InValue)
            : Key(InKey)
            , LessRecent(nullptr)
            , MoreRecent(nullptr)
            , Value(InValue)
        { }
 
        inline void LinkBefore(FCacheEntry* Other)
        {
            LessRecent = Other;
 
            if (Other != nullptr)
            {
                Other->MoreRecent = this;
            }
        }
 
        inline void Unlink()
        {
            if (LessRecent != nullptr)
            {
                LessRecent->MoreRecent = MoreRecent;
            }
 
            if (MoreRecent != nullptr)
            {
                MoreRecent->LessRecent = LessRecent;
            }
 
            LessRecent = nullptr;
            MoreRecent = nullptr;
        }
    };
 
    struct FKeyFuncs : public BaseKeyFuncs<FCacheEntry*, KeyType>
    {
        inline static const KeyType& GetSetKey(const FCacheEntry* Entry)
        {
            return Entry->Key;
        }
 
        inline static bool Matches(KeyType A, KeyType B)
        {
            return A == B;
        }
 
        inline static uint32 GetKeyHash(KeyType Key)
        {
            return GetTypeHash(Key);
        }
    };
 
public:
 
    TPsoLruCache()
        : LeastRecent(nullptr)
        , MostRecent(nullptr)
        , MaxNumElements(0)
    { }
 
    TPsoLruCache(int32 InMaxNumElements)
        : LeastRecent(nullptr)
        , MostRecent(nullptr)
        , MaxNumElements(InMaxNumElements)
    {
        Empty(InMaxNumElements);
    }
 
    ~TPsoLruCache()
    {
        Empty();
    }
 
public:
 
    FSetElementId Add(const KeyType& Key, const ValueType& Value)
    {
        check(MaxNumElements > 0 && "Cannot add values to zero size FOpenGLLruCache");
        check(!LookupSet.Contains(Key));
 
        check(LookupSet.Num() < MaxNumElements);
        // add new entry
        FCacheEntry* NewEntry = new FCacheEntry(Key, Value);
        NewEntry->LinkBefore(MostRecent);
        MostRecent = NewEntry;
 
        if (LeastRecent == nullptr)
        {
            LeastRecent = NewEntry;
        }
        return LookupSet.Add(NewEntry);
    }
 
    inline bool Contains(const KeyType& Key) const
    {
        return LookupSet.Contains(Key);
    }
 
    template<typename Predicate>
    inline bool ContainsByPredicate(Predicate Pred) const
    {
        for (const FCacheEntry* Entry : LookupSet)
        {
            if (Pred(Entry->Key, Entry->Value))
            {
                return true;
            }
        }
 
        return false;
    }
 
    void Empty(int32 InMaxNumElements = 0)
    {
        check(InMaxNumElements >= 0);
 
        for (FCacheEntry* Entry : LookupSet)
        {
            delete Entry;
        }
 
        MaxNumElements = InMaxNumElements;
        LookupSet.Empty(MaxNumElements);
 
        MostRecent = nullptr;
        LeastRecent = nullptr;
    }
 
    template<typename Predicate>
    TArray<ValueType> FilterByPredicate(Predicate Pred) const
    {
        TArray<ValueType> Result;
 
        for (const FCacheEntry* Entry : LookupSet)
        {
            if (Pred(Entry->Key, Entry->Value))
            {
                Result.Add(Entry->Value);
            }
        }
 
        return Result;
    }
 
    inline const ValueType* Find(const KeyType& Key) const
    {
        FCacheEntry** EntryPtr = LookupSet.Find(Key);
 
        if (EntryPtr != nullptr)
        {
            return &(*EntryPtr)->Value;
        }
 
        return nullptr;
    }
 
    const ValueType* FindAndTouch(const KeyType& Key)
    {
        FCacheEntry** EntryPtr = LookupSet.Find(Key);
 
        if (EntryPtr == nullptr)
        {
            return nullptr;
        }
 
        MarkAsRecent(**EntryPtr);
 
        return &(*EntryPtr)->Value;
    }
 
    template<typename Predicate>
    const ValueType* FindByPredicate(Predicate Pred) const
    {
        for (const FCacheEntry* Entry : LookupSet)
        {
            if (Pred(Entry->Key, Entry->Value))
            {
                return &Entry->Value;
            }
        }
 
        return nullptr;
    }
 
    void GetKeys(TArray<KeyType>& OutKeys) const
    {
        for (const FCacheEntry* Entry : LookupSet)
        {
            OutKeys.Add(Entry->Key);
        }
    }
 
    inline int32 Max() const
    {
        return MaxNumElements;
    }
 
    inline int32 Num() const
    {
        return LookupSet.Num();
    }
 
    void Remove(const KeyType& Key)
    {
        FCacheEntry** EntryPtr = LookupSet.Find(Key);
 
        if (EntryPtr != nullptr)
        {
            Remove(*EntryPtr);
        }
    }
 
    bool Remove(const KeyType& Key, ValueType& RemovedValue)
    {
        FCacheEntry** EntryPtr = LookupSet.Find(Key);
 
        if (EntryPtr != nullptr)
        {
            RemovedValue = MoveTemp((*EntryPtr)->Value);
            Remove(*EntryPtr);
            return true;
        }
        return false;
    }
 
    template<typename Predicate>
    int32 RemoveByPredicate(Predicate Pred)
    {
        int32 NumRemoved = 0;
 
        for (const FCacheEntry* Entry : LookupSet)
        {
            if (Pred(Entry->Key, Entry->Value))
            {
                Remove(Entry);
                ++NumRemoved;
            }
        }
 
        return NumRemoved;
    }
 
    inline ValueType RemoveLeastRecent()
    {
        check(LeastRecent);
        ValueType LeastRecentElement = MoveTemp(LeastRecent->Value);
        Remove(LeastRecent);
        return LeastRecentElement;
    }
 
    inline const ValueType GetLeastRecent() const
    {
        check(LeastRecent);
        return LeastRecent->Value;
    }
 
    inline ValueType RemoveMostRecent()
    {
        check(MostRecent);
        ValueType MostRecentElement = MoveTemp(MostRecent->Value);
        Remove(MostRecent);
        return MostRecentElement;
    }
 
    inline void MarkAsRecent(const FSetElementId& LRUNode)
    {
        MarkAsRecent(*LookupSet[LRUNode]);
    }
 
public:
 
    template<bool Const>
    class TBaseIterator
    {
    public:
 
        inline TBaseIterator()
            : CurrentEntry(nullptr)
        { }
 
        inline TBaseIterator(const TPsoLruCache& Cache)
            : CurrentEntry(Cache.MostRecent)
        { }
 
    public:
 
        inline TBaseIterator& operator++()
        {
            Increment();
            return *this;
        }
 
        inline friend bool operator==(const TBaseIterator& Lhs, const TBaseIterator& Rhs)
        {
            return Lhs.CurrentEntry == Rhs.CurrentEntry;
        }
 
        inline friend bool operator!=(const TBaseIterator& Lhs, const TBaseIterator& Rhs)
        {
            return Lhs.CurrentEntry != Rhs.CurrentEntry;
        }
 
        ValueType& operator->() const
        {
            check(CurrentEntry != nullptr);
            return CurrentEntry->Value;
        }
 
        ValueType& operator*() const
        {
            check(CurrentEntry != nullptr);
            return CurrentEntry->Value;
        }
 
        inline explicit operator bool() const
        {
            return (CurrentEntry != nullptr);
        }
 
        inline bool operator!() const
        {
            return !(bool)*this;
        }
 
    public:
 
        inline KeyType& Key() const
        {
            check(CurrentEntry != nullptr);
            return CurrentEntry->Key;
        }
 
        inline ValueType& Value() const
        {
            check(CurrentEntry != nullptr);
            return CurrentEntry->Value;
        }
 
    protected:
 
        FCacheEntry* GetCurrentEntry()
        {
            return CurrentEntry;
        }
 
        void Increment()
        {
            check(CurrentEntry != nullptr);
            CurrentEntry = CurrentEntry->LessRecent;
        }
 
    private:
 
        FCacheEntry* CurrentEntry;
    };
 
 
    class TConstIterator
        : public TBaseIterator<true>
    {
    public:
 
        inline TConstIterator()
            : TBaseIterator<true>()
        { }
 
        inline TConstIterator(const TPsoLruCache& Cache)
            : TBaseIterator<true>(Cache)
        { }
    };
 
    
    class TIterator
        : public TBaseIterator<false>
    {
    public:
 
        inline TIterator()
            : TBaseIterator<false>()
            , Cache(nullptr)
        { }
 
        inline TIterator(TPsoLruCache& InCache)
            : TBaseIterator<false>(InCache)
            , Cache(&InCache)
        { }
 
        inline void RemoveCurrentAndIncrement()
        {
            check(Cache != nullptr);
 
            FCacheEntry* MoreRecentEntry = this->GetCurrentEntry();
            this->Increment();
            Cache->Remove(MoreRecentEntry);
        }
 
    private:
        
        TPsoLruCache* Cache;
    };
 
protected:
 
    inline void MarkAsRecent(FCacheEntry& Entry)
    {
        check(LeastRecent != nullptr);
        check(MostRecent != nullptr);
 
        // if entry is least recent and not the only item in the list, make it not least recent
        if ((&Entry == LeastRecent) && (LeastRecent->MoreRecent != nullptr))
        {
            LeastRecent = LeastRecent->MoreRecent;
        }
 
        // relink if not already the most recent item
        if (&Entry != MostRecent)
        {
            Entry.Unlink();
            Entry.LinkBefore(MostRecent);
            MostRecent = &Entry;
        }
    }
 
    inline void Remove(FCacheEntry* Entry)
    {
        if (Entry == nullptr)
        {
            return;
        }
 
        LookupSet.Remove(Entry->Key);
 
        if (Entry == LeastRecent)
        {
            LeastRecent = Entry->MoreRecent;
        }
 
        if (Entry == MostRecent)
        {
            MostRecent = Entry->LessRecent;
        }
 
        Entry->Unlink();
        delete Entry;
    }
 
private:
 
    friend TIterator begin(TPsoLruCache& Cache) { return TIterator(Cache); }
    friend TConstIterator begin(const TPsoLruCache& Cache) { return TConstIterator(Cache); }
    friend TIterator end(TPsoLruCache& Cache) { return TIterator(); }
    friend TConstIterator end(const TPsoLruCache& Cache) { return TConstIterator(); }
 
private:
 
    TSet<FCacheEntry*, FKeyFuncs> LookupSet;
 
    FCacheEntry* LeastRecent;
 
    FCacheEntry* MostRecent;
 
    int32 MaxNumElements;
};