LRUList.h

Go to the documentation of this file.

#ifndef PCAPPP_LRU_LIST
#define PCAPPP_LRU_LIST
 
#include <map>
#include <list>
 
#if __cplusplus > 199711L || _MSC_VER >= 1800
#include <utility>
#endif
 
 
namespace pcpp
{
 
    template<typename T>
    class LRUList
    {
    public:
 
        typedef typename std::list<T>::iterator ListIterator;
        typedef typename std::map<T, ListIterator>::iterator MapIterator;
 
        LRUList(size_t maxSize)
        {
            m_MaxSize = maxSize;
        }
 
        int put(const T& element, T* deletedValue = NULL)
        {
            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 == false) // 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 != NULL)
#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::map<T, ListIterator> m_CacheItemsMap;
        size_t m_MaxSize;
    };
 
} // namespace pcpp
 
#endif /* PCAPPP_LRU_LIST */