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 */