LRUList.h

Go to the documentation of this file.

#ifndef PCAPPP_LRU_LIST
#define PCAPPP_LRU_LIST

#include <map>
#include <list>


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;
        }

        T* put(const T& element)
        {
            m_CacheItemsList.push_front(element);
            MapIterator iter = m_CacheItemsMap.find(element);
            if (iter != m_CacheItemsMap.end())
                m_CacheItemsList.erase(iter->second);
            m_CacheItemsMap[element] = m_CacheItemsList.begin();

            if (m_CacheItemsList.size() > m_MaxSize)
            {
                ListIterator lruIter = m_CacheItemsList.end();
                lruIter--;
                T* deletedValue = new T(*lruIter);
                m_CacheItemsMap.erase(*lruIter);
                m_CacheItemsList.erase(lruIter);

                return deletedValue;
            }

            return NULL;
        }

        const T& getMRUElement()
        {
            return m_CacheItemsList.front();
        }

        const T& getLRUElement()
        {
            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(element);
        }

        inline size_t getMaxSize() { return m_MaxSize; }

        inline size_t getSize() { 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 */