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)
        {
            // Try to insert a mapping to the new element.
            // TODO: C++17: use try_emplace instead of emplace when we switch to C++17
            auto pair = m_CacheItemsMap.emplace(element, m_CacheItemsList.end());
            if (!pair.second)
            {
                // The element already exists. Move it to the head of the list.
                m_CacheItemsList.splice(m_CacheItemsList.begin(), m_CacheItemsList, pair.first->second);
                return 0;
            }
 
            // The element is new.
            m_CacheItemsList.push_front(element);
            pair.first->second = m_CacheItemsList.begin();
 
            if (m_CacheItemsMap.size() > m_MaxSize)
            {
                auto& item = m_CacheItemsList.back();
 
                if (deletedValue != nullptr)
                {
#if __cplusplus > 199711L || _MSC_VER >= 1800
                    *deletedValue = std::move(item);
#else
                    *deletedValue = item;
#endif
                }
                m_CacheItemsMap.erase(item);
                m_CacheItemsList.pop_back();
                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