LruCache.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"
 
 
template<typename KeyType>
struct DefaultKeyComparer
{
    [[nodiscard]] static UE_FORCEINLINE_HINT bool Matches(KeyType A, KeyType B)
    {
        return (A == B);
    }
 
    [[nodiscard]] static UE_FORCEINLINE_HINT uint32 GetKeyHash(KeyType Key)
    {
        return GetTypeHash(Key);
    }
};
 
 
template<typename KeyType, typename ValueType, typename KeyComp = DefaultKeyComparer<KeyType> >
class TLruCache
{
    struct FCacheEntry
    {
        KeyType Key;
 
        FCacheEntry* LessRecent;
 
        FCacheEntry* MoreRecent;
 
        ValueType Value;
 
        [[nodiscard]] FCacheEntry(const KeyType& InKey, const ValueType& InValue)
            : Key(InKey)
            , LessRecent(nullptr)
            , MoreRecent(nullptr)
            , Value(InValue)
        {
        }
 
        [[nodiscard]] FCacheEntry(const KeyType& InKey)
            : Key(InKey)
            , LessRecent(nullptr)
            , MoreRecent(nullptr)
        {
        }
 
 
        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>
    {
        [[nodiscard]] UE_FORCEINLINE_HINT static const KeyType& GetSetKey(const FCacheEntry* Entry)
        {
            return Entry->Key;
        }
 
        [[nodiscard]] UE_FORCEINLINE_HINT static bool Matches(KeyType A, KeyType B)
        {
            return KeyComp::Matches(A, B);
        }
 
        [[nodiscard]] UE_FORCEINLINE_HINT static uint32 GetKeyHash(KeyType Key)
        {
            return KeyComp::GetKeyHash(Key);
        }
    };
 
public:
 
    [[nodiscard]] TLruCache()
        : LeastRecent(nullptr)
        , MostRecent(nullptr)
        , MaxNumElements(0)
    {
    }
 
    [[nodiscard]] TLruCache(int32 InMaxNumElements)
        : LeastRecent(nullptr)
        , MostRecent(nullptr)
        , MaxNumElements(InMaxNumElements)
    {
        Empty(InMaxNumElements);
    }
 
    ~TLruCache()
    {
        Empty();
    }
 
public:
 
    void Add(const KeyType& Key, const ValueType& Value)
    {
        check(MaxNumElements != 0 && "Cannot add values to zero size TLruCache");
 
        FCacheEntry** EntryPtr = LookupSet.Find(Key);
 
        if (EntryPtr != nullptr)
        {
            // update existing entry
            FCacheEntry* Entry = *EntryPtr;
            checkSlow(Entry->Key == Key);
 
            Entry->Value = Value;
            MarkAsRecent(*Entry);
        }
        else
        {
            // add new entry
            if (LookupSet.Num() == MaxNumElements)
            {
                Remove(LeastRecent);
            }
 
            FCacheEntry* NewEntry = new FCacheEntry(Key, Value);
            NewEntry->LinkBefore(MostRecent);
            MostRecent = NewEntry;
 
            if (LeastRecent == nullptr)
            {
                LeastRecent = NewEntry;
            }
 
            LookupSet.Add(NewEntry);
        }
    }
 
    ValueType& AddUninitialized_GetRef(const KeyType& Key)
    {
        check(MaxNumElements != 0 && "Cannot add values to zero size TLruCache");
 
        FCacheEntry** EntryPtr = LookupSet.Find(Key);
 
        if (EntryPtr != nullptr)
        {
            // update existing entry
            FCacheEntry* Entry = *EntryPtr;
            checkSlow(Entry->Key == Key);
 
            MarkAsRecent(*Entry);
            return Entry->Value;
        }
        else
        {
            // add new entry
            if (LookupSet.Num() == MaxNumElements)
            {
                Remove(LeastRecent);
            }
 
            FCacheEntry* NewEntry = new FCacheEntry(Key);
            NewEntry->LinkBefore(MostRecent);
            MostRecent = NewEntry;
 
            if (LeastRecent == nullptr)
            {
                LeastRecent = NewEntry;
            }
 
            LookupSet.Add(NewEntry);
            return NewEntry->Value;
        }
    }
 
 
 
    [[nodiscard]] UE_FORCEINLINE_HINT bool Contains(const KeyType& Key) const
    {
        return LookupSet.Contains(Key);
    }
 
    template<typename Predicate>
    [[nodiscard]] 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)
    {
        for (FCacheEntry* Entry : LookupSet)
        {
            delete Entry;
        }
 
        MaxNumElements = InMaxNumElements;
        LookupSet.Empty(FMath::Max(MaxNumElements, 0));
 
        MostRecent = nullptr;
        LeastRecent = nullptr;
    }
 
    template<typename Predicate>
    [[nodiscard]] 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;
    }
 
    [[nodiscard]] inline const ValueType* Find(const KeyType& Key) const
    {
        FCacheEntry*const * EntryPtr = LookupSet.Find(Key);
 
        if (EntryPtr != nullptr)
        {
            return &(*EntryPtr)->Value;
        }
 
        return nullptr;
    }
 
    [[nodiscard]] inline ValueType* Find(const KeyType& Key)
    {
        FCacheEntry* const* EntryPtr = LookupSet.Find(Key);
 
        if (EntryPtr != nullptr)
        {
            return &(*EntryPtr)->Value;
        }
 
        return nullptr;
    }
 
    [[nodiscard]] inline const ValueType& FindChecked(const KeyType& Key) const
    {
        FCacheEntry*const * EntryPtr = LookupSet.Find(Key);
 
        check(EntryPtr);
 
        return (*EntryPtr)->Value;
    }
 
    [[nodiscard]] inline ValueType& FindChecked(const KeyType& Key)
    {
        FCacheEntry*const * EntryPtr = LookupSet.Find(Key);
 
        check(EntryPtr);
 
        return (*EntryPtr)->Value;
    }
 
    [[nodiscard]] inline ValueType FindRef(const KeyType& Key) const
    {
        FCacheEntry*const * EntryPtr = LookupSet.Find(Key);
 
        if (EntryPtr != nullptr)
        {
            return (*EntryPtr)->Value;
        }
 
        return ValueType();
    }
 
    [[nodiscard]] ValueType* FindAndTouch(const KeyType& Key)
    {
        FCacheEntry** EntryPtr = LookupSet.Find(Key);
 
        if (EntryPtr == nullptr)
        {
            return nullptr;
        }
 
        MarkAsRecent(**EntryPtr);
 
        return &(*EntryPtr)->Value;
    }
 
    [[nodiscard]] ValueType& FindAndTouchChecked(const KeyType& Key)
    {
        FCacheEntry** EntryPtr = LookupSet.Find(Key);
 
        check(EntryPtr);
 
        MarkAsRecent(**EntryPtr);
 
        return (*EntryPtr)->Value;
    }
 
    [[nodiscard]] ValueType FindAndTouchRef(const KeyType& Key)
    {
        FCacheEntry** EntryPtr = LookupSet.Find(Key);
 
        if (EntryPtr == nullptr)
        {
            return ValueType();
        }
 
        MarkAsRecent(**EntryPtr);
 
        return (*EntryPtr)->Value;
    }
 
    template<typename Predicate>
    [[nodiscard]] 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);
        }
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT int32 Max() const
    {
        return MaxNumElements;
    }
 
    [[nodiscard]] bool IsEmpty() const
    {
        return LookupSet.IsEmpty();
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT int32 Num() const
    {
        return LookupSet.Num();
    }
 
    void Remove(const KeyType& Key)
    {
        FCacheEntry** EntryPtr = LookupSet.Find(Key);
 
        if (EntryPtr != nullptr)
        {
            Remove(*EntryPtr);
        }
    }
 
    template<typename Predicate>
    int32 RemoveByPredicate(Predicate Pred)
    {
        int32 NumRemoved = 0;
 
        for (auto It = LookupSet.CreateIterator(); It; ++It)
        {
            FCacheEntry* Entry = *It;
            if (Pred(Entry->Key, Entry->Value))
            {
                if (Entry == LeastRecent)
                {
                    LeastRecent = Entry->MoreRecent;
                }
 
                if (Entry == MostRecent)
                {
                    MostRecent = Entry->LessRecent;
                }
 
                It.RemoveCurrent(); // remove before delete so hashkey doesn't change
 
                Entry->Unlink();
                delete Entry;
 
                ++NumRemoved;
            }
        }
 
        return NumRemoved;
    }
 
    inline ValueType RemoveLeastRecent()
    {
        check(LeastRecent);
        ValueType LeastRecentElement = MoveTemp(LeastRecent->Value);
        Remove(LeastRecent);
        return LeastRecentElement;
    }
 
    [[nodiscard]] inline KeyType GetLeastRecentKey() const
    {
        check(LeastRecent);
        return LeastRecent->Key;
    }
 
public:
 
    template<bool Const>
    class TBaseIterator
    {
    public:
 
        [[nodiscard]] UE_FORCEINLINE_HINT TBaseIterator()
            : CurrentEntry(nullptr)
        {
        }
 
        [[nodiscard]] UE_FORCEINLINE_HINT TBaseIterator(const TLruCache& Cache)
            : CurrentEntry(Cache.MostRecent)
        {
        }
 
    public:
 
        inline TBaseIterator& operator++()
        {
            Increment();
            return *this;
        }
 
        [[nodiscard]] UE_FORCEINLINE_HINT bool operator==(const TBaseIterator& Rhs) const
        {
            return CurrentEntry == Rhs.CurrentEntry;
        }
 
        [[nodiscard]] UE_FORCEINLINE_HINT bool operator!=(const TBaseIterator& Rhs) const
        {
            return CurrentEntry != Rhs.CurrentEntry;
        }
 
        [[nodiscard]] ValueType& operator->() const
        {
            check(CurrentEntry != nullptr);
            return CurrentEntry->Value;
        }
 
        [[nodiscard]] ValueType& operator*() const
        {
            check(CurrentEntry != nullptr);
            return CurrentEntry->Value;
        }
 
        [[nodiscard]] UE_FORCEINLINE_HINT explicit operator bool() const
        {
            return (CurrentEntry != nullptr);
        }
 
        [[nodiscard]] UE_FORCEINLINE_HINT bool operator!() const
        {
            return !(bool)*this;
        }
 
    public:
 
        [[nodiscard]] inline KeyType& Key() const
        {
            check(CurrentEntry != nullptr);
            return CurrentEntry->Key;
        }
 
        [[nodiscard]] inline ValueType& Value() const
        {
            check(CurrentEntry != nullptr);
            return CurrentEntry->Value;
        }
 
    protected:
 
        [[nodiscard]] FCacheEntry* GetCurrentEntry()
        {
            return CurrentEntry;
        }
 
        void Increment()
        {
            check(CurrentEntry != nullptr);
            CurrentEntry = CurrentEntry->LessRecent;
        }
 
    private:
 
        FCacheEntry* CurrentEntry;
    };
 
 
    class TConstIterator
        : public TBaseIterator<true>
    {
    public:
 
        [[nodiscard]] UE_FORCEINLINE_HINT TConstIterator()
            : TBaseIterator<true>()
        {
        }
 
        [[nodiscard]] UE_FORCEINLINE_HINT TConstIterator(const TLruCache& Cache)
            : TBaseIterator<true>(Cache)
        {
        }
    };
 
 
    class TIterator
        : public TBaseIterator<false>
    {
    public:
 
        [[nodiscard]] inline TIterator()
            : TBaseIterator<false>()
            , Cache(nullptr)
        {
        }
 
        [[nodiscard]] inline TIterator(TLruCache& InCache)
            : TBaseIterator<false>(InCache)
            , Cache(&InCache)
        {
        }
 
        inline void RemoveCurrentAndIncrement()
        {
            check(Cache != nullptr);
 
            FCacheEntry* MoreRecentEntry = this->GetCurrentEntry();
            this->Increment();
            Cache->Remove(MoreRecentEntry);
        }
 
    private:
 
        TLruCache* 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;
    }
 
public:
 
    [[nodiscard]] TIterator begin() { return TIterator(*this); }
    [[nodiscard]] TConstIterator begin() const { return TConstIterator(*this); }
    [[nodiscard]] TIterator end() { return TIterator(); }
    [[nodiscard]] TConstIterator end() const { return TConstIterator(); }
 
private:
 
    TSet<FCacheEntry*, FKeyFuncs> LookupSet;
 
    FCacheEntry* LeastRecent;
 
    FCacheEntry* MostRecent;
 
    int32 MaxNumElements;
};