LRUList.h

Go to the documentation of this file.

#pragma once
 
#include <list>
#include <cstddef>
#include <unordered_map>
 
#if __cplusplus > 199711L || _MSC_VER >= 1800
#   include <utility>
#endif
 
 
namespace pcpp
{
 
    template <typename T> class LRUList
    {
    public:
        using ListIterator = typename std::list<T>::iterator;
        using MapIterator = typename std::unordered_map<T, ListIterator>::iterator;
 
        explicit LRUList(std::size_t maxSize) : m_MaxSize(maxSize)
        {}
 
        int put(const T& element, T* deletedValue = nullptr)
        {
            m_CacheItemsList.push_front(element);
 
            // Inserting a new element. If an element with an equivalent key already exists the method returns an
            // iterator to the element that prevented the insertion
            std::pair<MapIterator, bool> pair =
                m_CacheItemsMap.insert(std::make_pair(element, m_CacheItemsList.begin()));
            if (!pair.second)  // already exists
            {
                m_CacheItemsList.erase(pair.first->second);
                pair.first->second = m_CacheItemsList.begin();
            }
 
            if (m_CacheItemsMap.size() > m_MaxSize)
            {
                ListIterator lruIter = m_CacheItemsList.end();
                --lruIter;
 
                if (deletedValue != nullptr)
                {
#if __cplusplus > 199711L || _MSC_VER >= 1800
                    *deletedValue = std::move(*lruIter);
#else
                    *deletedValue = *lruIter;
#endif
                }
                m_CacheItemsMap.erase(*lruIter);
                m_CacheItemsList.erase(lruIter);
                return 1;
            }
 
            return 0;
        }
 
        const T& getMRUElement() const
        {
            return m_CacheItemsList.front();
        }
 
        const T& getLRUElement() const
        {
            return m_CacheItemsList.back();
        }
 
        void eraseElement(const T& element)
        {
            MapIterator iter = m_CacheItemsMap.find(element);
            if (iter == m_CacheItemsMap.end())
            {
                return;
            }
 
            m_CacheItemsList.erase(iter->second);
            m_CacheItemsMap.erase(iter);
        }
 
        size_t getMaxSize() const
        {
            return m_MaxSize;
        }
 
        size_t getSize() const
        {
            return m_CacheItemsMap.size();
        }
 
    private:
        std::list<T> m_CacheItemsList;
        std::unordered_map<T, ListIterator> m_CacheItemsMap;
        size_t m_MaxSize;
    };
 
}  // namespace pcpp