JavaCard OS

JavaCardOS - JavaCardForum
http://www.javacardos.com/javacardforum/

LRU-MRU algorithm

http://www.javacardos.com/javacardforum/viewtopic.php?f=12&t=542

Page 1 of 1

LRU-MRU algorithm

Posted: Sat Jan 30, 2016 9:34 am
by kuafu

Code: Select all

/*
* Implementation of an LRU cache with a maximum size.
*
* See http://code.google.com/p/lru-cache-cpp/ for usage and limitations.
*
* Licensed under the GNU LGPL: http://www.gnu.org/copyleft/lesser.html
*
* Pierre-Luc Brunelle, 2011
* pierre-luc.brunelle@polytml.ca
*
* 使用stl中的map替换hash_table
* Peteryfren China, 2012
*
*2016.01.30 重构LRU，提升性能，摆脱map，添加erase接口。
. kuafu China ,2016
*
*/

#include <unordered_map>
#include <cassert>


namespace lru {

   //-------------------------------------------------------------
   // Bucket
   //-------------------------------------------------------------
   enum DIRECTION {
      MRU_TO_LRU = 0,
      LRU_TO_MRU
   };
   template<class K, class V>
   struct LRUValue
   {
      typedef std::pair<const K, LRUValue<K, V> > Val;

      LRUValue()
         : _v(), _older(NULL), _newer(NULL) { }

      LRUValue(const V & v, Val * older, Val * newer)
         : _v(v), _older(older), _newer(newer) { }

      V _v;
      Val * _older;
      Val * _newer;
   };


   //-------------------------------------------------------------
   // Const Iterator
   //-------------------------------------------------------------

   template<class K, class V>
   class LRUNoCacheConstIterator
   {
   public:
      typedef std::pair<const K, LRUValue<K, V> > Val;
      typedef LRUNoCacheConstIterator<K, V> const_iterator;
      typedef Val & reference;
      typedef Val * pointer;

      

      LRUNoCacheConstIterator(const Val * ptr = NULL, DIRECTION dir = MRU_TO_LRU);

      const_iterator & operator++();
      const_iterator operator++(int);
      const Val* operator*();
      bool operator==(const const_iterator & other);
      bool operator!=(const const_iterator & other);

      const K & key() const;
      const V & value() const;

   protected:

      const Val * _ptr;
      DIRECTION _dir;
   };


   template<class K, class V>
   LRUNoCacheConstIterator<K, V>::LRUNoCacheConstIterator(
      const typename LRUNoCacheConstIterator<K, V>::Val * ptr,
      DIRECTION dir)
      : _ptr(ptr), _dir(dir)
   {
   }


   template<class K, class V>
   LRUNoCacheConstIterator<K, V> & LRUNoCacheConstIterator<K, V>::operator++()
   {
      assert(_ptr);
      _ptr = (_dir == MRU_TO_LRU ? _ptr->second._older : _ptr->second._newer);
      return *this;
   }


   template<class K, class V>
   LRUNoCacheConstIterator<K, V> LRUNoCacheConstIterator<K, V>::operator++(int)
   {
      const_iterator ret = *this;
      ++*this;
      return ret;
   }

   template <class K, class V>
   const typename LRUNoCacheConstIterator<K, V>::Val* LRUNoCacheConstIterator<K, V>::operator*()
   {
      return _ptr;
   }


   template<class K, class V>
   bool LRUNoCacheConstIterator<K, V>::operator==(const const_iterator & other)
   {
      return _ptr == other._ptr;
   }


   template<class K, class V>
   bool LRUNoCacheConstIterator<K, V>::operator!=(const const_iterator & other)
   {
      return _ptr != other._ptr;
   }


   template<class K, class V>
   const K & LRUNoCacheConstIterator<K, V>::key() const
   {
      assert(_ptr);
      return _ptr->first;
   }


   template<class K, class V>
   const V & LRUNoCacheConstIterator<K, V>::value() const
   {
      assert(_ptr);
      return _ptr->second._v;
   }


   //-------------------------------------------------------------
   //  Iterator
   //-------------------------------------------------------------

   template<class K, class V>
   class LRUNoCacheIterator:public LRUNoCacheConstIterator<K,V>
   {
   public:
      typedef LRUNoCacheConstIterator<K,V> _Mybase;
      typedef std::pair<const K, LRUValue<K, V> > Val;
      typedef LRUNoCacheIterator<K, V> iterator;
      typedef Val & reference;
      typedef Val * pointer;



      LRUNoCacheIterator(Val * ptr = NULL, DIRECTION dir = MRU_TO_LRU);
      Val* operator*();
      iterator & operator++();
      iterator operator++(int);
      bool operator==(const iterator & other);
      bool operator!=(const iterator & other);

      
   
   };
   template <class K, class V>
   LRUNoCacheIterator<K, V>::LRUNoCacheIterator(Val* ptr, DIRECTION dir)
      : _Mybase(ptr, dir)
   {

   }

   template<class K, class V>
   LRUNoCacheIterator<K, V> & LRUNoCacheIterator<K, V>::operator++()
   {
      assert(_Mybase::_ptr);
      _Mybase::_ptr = (_Mybase::_dir == MRU_TO_LRU ? _Mybase::_ptr->second._older : _Mybase::_ptr->second._newer);
      return *this;
   }
   
   
   template<class K, class V>
   LRUNoCacheIterator<K, V> LRUNoCacheIterator<K, V>::operator++(int)
   {
      iterator ret = *this;
      ++*this;
      return ret;
   }
   
   template <class K, class V>
      typename LRUNoCacheIterator<K, V>::Val* LRUNoCacheIterator<K, V>::operator*()
   {
      return (Val *)_Mybase::_ptr;
   }
   
   
   template<class K, class V>
   bool LRUNoCacheIterator<K, V>::operator==(const iterator & other)
   {
      return _Mybase::_ptr == other._ptr;
   }
   
   
   template<class K, class V>
   bool LRUNoCacheIterator<K, V>::operator!=(const iterator & other)
   {
      return _Mybase::_ptr != other._ptr;
   }
   
   
   
} // file scope


namespace lru {

   //-------------------------------------------------------------
   // LRU Cache
   //-------------------------------------------------------------

   
   template<class K, class V>
   class LRUNoCache
   {
   public:
      typedef LRUNoCacheIterator<K, V> iterator;
      typedef LRUNoCacheConstIterator<K, V> const_iterator;

      typedef std::pair<const K, LRUValue<K, V> > Val;

      typedef  std::unordered_map<K, LRUValue<K, V> > MAP_TYPE;
      typedef typename MAP_TYPE::size_type size_type;
      

      LRUNoCache(DIRECTION dir = MRU_TO_LRU);
      LRUNoCache(const LRUNoCache & other);
      virtual ~LRUNoCache() {  }

      V & operator[](const K & key);
      void insert(const K & key, const V & value);

      int size() const;
   
      bool empty() const;

      iterator find(const K & key);         // updates the MRU
      const_iterator find(const K & key) const;   // does not update the MRU

      const_iterator mru_begin() const; // from MRU to LRU
      

      iterator mru_begin();

      const_iterator lru_begin() const;           // from LRU to MRU
      iterator lru_begin();

   
      const_iterator begin() const;
      iterator begin();

      const_iterator end() const;
      iterator end();

      void dump_mru_to_lru(std::ostream & os) const;
      void SetDirection(DIRECTION _dir);

      DIRECTION getDirection() const;
      size_type erase(const K & key);

   protected:
      
      Val * _update(typename Val * it);
      virtual Val * _insert(const K & key);
   
      unsigned _size;
      //MAP_TYPE _map;
      Val * _mru;
      Val * _lru;
      DIRECTION dir;
   };

   template<class K, class V>
   class LRUWithCache :public LRUNoCache<K,V>
   {
   public:

      typedef std::pair<const K, LRUValue<K, V> > Val;
      typedef LRUNoCache<K, V> _Mybase;
      LRUWithCache(unsigned maxsize, DIRECTION dir = MRU_TO_LRU);// Pre-condition: maxsize >= 1
      LRUWithCache(const LRUWithCache & other);
      unsigned maxsize() const;

   protected:
      Val* _insert(const K& key) override;
      
      unsigned _maxsize;
   };



   // Reserve enough space to avoid resizing later on and thus invalidate iterators
   template<class K, class V>
   LRUNoCache<K, V>::LRUNoCache(DIRECTION _dir)
      : _mru(NULL),
       _lru(NULL),
      dir(_dir), _size(0)
   {

   }


   template<class K, class V>
   LRUNoCache<K, V>::LRUNoCache(const LRUNoCache<K, V> & other)
      :_mru(NULL),
      _lru(NULL),
      dir(other.dir)
   {
      for (const_iterator it = other.begin(); it != other.end(); ++it)
         this->insert(it.key(), it.value());   
   }


   template<class K, class V>
   V & LRUNoCache<K, V>::operator[](const K & key)
   {
   
      iterator it = find(key);
      Val* val;
      if (it == end())
         val = _insert(key);
      else
         val = *it;

      return val->second._v;
   }


   template<class K, class V>
   void LRUNoCache<K, V>::insert(const K & key, const V & value)
   {
      iterator it = find(key);
      Val* val;
      if (it == end())
         val = _insert(key);
      else
         val = *it;

       val->second._v = value;
   }


   template<class K, class V>
   int LRUNoCache<K, V>::size() const
   {
      //return _map.size();
      return _size;
   }


   

   template<class K, class V>
   bool LRUNoCache<K, V>::empty() const
   {
      return size() > 0;
   }


   // updates MRU
   template<class K, class V>
   typename LRUNoCache<K, V>::iterator LRUNoCache<K, V>::find(const K & key)
   {
      iterator it;
      if (MRU_TO_LRU == dir) 
         it = mru_begin();   
      else
         it = lru_begin();
      
      iterator _end = end();
      for (; it != _end; ++it) {
         if (it.key() == key) {
            return  iterator(_update(*it), dir);
         }
      }
      return _end;
   }


   // does not update MRU
   template<class K, class V>
   typename LRUNoCache<K, V>::const_iterator LRUNoCache<K, V>::find(const K & key) const
   {
   
      const_iterator it;
      if (MRU_TO_LRU == dir)
         it = mru_begin();
      else
         it = lru_begin();

      const_iterator _end = end();
      for (; it != _end; ++it) {
         if (it.key() == key) {
            return   const_iterator(*it, dir);
         }
      }
   
      return _end;

   }

   template <class K, class V>
   typename LRUNoCache<K, V>::const_iterator LRUNoCache<K, V>::mru_begin() const
   {
      return const_iterator(_mru, MRU_TO_LRU);
   }

   template<class K, class V>
   void LRUNoCache<K, V>::dump_mru_to_lru(std::ostream & os) const
   {
      os << "LRUCacheH4(" << size() << "/" << maxsize() << "): MRU --> LRU: " << std::endl;
      for (const_iterator it = mru_begin(); it != end(); ++it)
         os << it.key() << ": " << it.value() << std::endl;
   }

   template <class K, class V>
   void LRUNoCache<K, V>::SetDirection(DIRECTION _dir)
   {
      dir =_dir;
   }

   template <class K, class V>
   DIRECTION LRUNoCache<K, V>::getDirection() const
   {
      return dir;
   }

   

   template <class K, class V>
   typename LRUNoCache<K, V>::iterator LRUNoCache<K, V>::mru_begin()
   {
      return iterator(_mru, MRU_TO_LRU);
   }

   template<class K, class V>
   typename LRUNoCache<K, V>::const_iterator LRUNoCache<K, V>::lru_begin() const
   {
      return const_iterator(_lru, LRU_TO_MRU);
   }

   template <class K, class V>
   typename LRUNoCache<K, V>::iterator LRUNoCache<K, V>::lru_begin()
   {
      return iterator(_lru, LRU_TO_MRU);
   }

   template <class K, class V>
   typename LRUNoCache<K, V>::const_iterator LRUNoCache<K, V>::begin() const
   {
      return const_iterator(dir == MRU_TO_LRU ? _mru : _lru, dir);
   }

   template <class K, class V>
   typename LRUNoCache<K, V>::iterator LRUNoCache<K, V>::begin(){
   
      return iterator(dir == MRU_TO_LRU ? _mru : _lru, dir);
   }

   template <class K, class V>
   typename LRUNoCache<K, V>::iterator LRUNoCache<K, V>::end()
   {
   
      return iterator();
   }

   template<class K, class V>
   typename LRUNoCache<K, V>::const_iterator LRUNoCache<K, V>::end() const
   {
      return const_iterator();
   }


   

   template<class K, class V>
   typename LRUNoCache<K, V>::Val * LRUNoCache<K, V>::_update(typename Val * it)
   {
      LRUValue<K, V> & v = it->second;
      Val * older = v._older;
      Val * newer = v._newer;
      Val * moved = it;

      // possibly update the LRU
      if (moved == _lru && _lru->second._newer)
         _lru = _lru->second._newer;

      if (moved != _mru) {
         // "remove" key from current position
         if (older)
            older->second._newer = newer;
         if (newer)
            newer->second._older = older;

         // "insert" key to MRU position
         v._older = _mru;
         v._newer = NULL;
         _mru->second._newer = moved;
         _mru = moved;
      }

      return moved;
   }


   

   template<class K, class V>
   typename LRUNoCache<K, V>::Val * LRUNoCache<K, V>::_insert(const K & key)
   {
      // insert key to MRU position
   
      //std::pair<typename MAP_TYPE::iterator, bool> ret
      //      = _map.insert(make_pair(key, LRUValue<K, V>(V(), _mru, NULL)));
      //pair<const K, LRUValue<K, V> >
      //Val * inserted = &*ret.first;
      Val * inserted = new Val(key, LRUValue<K, V>(V(), _mru, NULL));
      _size += 1;
      if (_mru)
         _mru->second._newer = inserted;
      _mru = inserted;

      // possibly update the LRU
      if (!_lru)
         _lru = _mru;
      else if (!_lru->second._newer)
         _lru->second._newer = _mru;

      return inserted;
   }

   template <class K, class V>
   LRUWithCache<K, V>::LRUWithCache(unsigned maxsize, DIRECTION dir):_Mybase(dir)
      ,_maxsize(maxsize)
   {
      assert(maxsize);
   }

   template <class K, class V>
   LRUWithCache<K, V>::LRUWithCache(const LRUWithCache& other):_Mybase(other),_maxsize(other._maxsize)
   {

   }

   template <class K, class V>
   unsigned LRUWithCache<K, V>::maxsize() const
   {
      return _maxsize;
   }

   template <class K, class V>
   typename LRUWithCache<K, V>::Val* LRUWithCache<K, V>::_insert(const K& key)
   {
      // if we have grown too large, remove LRU
      if (_Mybase::_size >= _maxsize) {
         Val * old_lru = _Mybase::_lru;
         if (_Mybase::_lru->second._newer) {
            _Mybase::_lru = _Mybase::_lru->second._newer;
            _Mybase::_lru->second._older = NULL;
         }
         delete old_lru;
         _Mybase::_size -= 1;
         //_Mybase::_map.erase(old_lru->first);
      }
      return _Mybase::_insert(key);
   }

   template <class K, class V>
   typename LRUNoCache<K, V>::size_type LRUNoCache<K, V>::erase(const K& key) {
      
      if (!_size)
         return 0;

      if (_mru && _mru->first == key) {
         Val* erase_obj = _mru;
           // 当 map 中的数量等于1的时候，_mru 和 _lru指向同一个地方
         if (_mru->second._older) {
            _mru = _mru->second._older;
            _mru->second._newer = NULL;
         }
         else{
            _mru = nullptr;// _mru 没有后继，说明_mru 和_lru 是同一个东西
            _lru = nullptr;
         }
         delete erase_obj;
         _size -=1;
         return 1;
        // return   _map.erase(key);   
      }

      if(_lru && _lru->first == key){
         Val* erase_obj = _lru;
         // 到这里的时候 _map的值必然大于1，
         //因为_mru 和 _lru指向同一个地方，能通过之前的检查，则说明_mru 和 _lru不是指向相同位置
         if (_lru->second._newer) {
            _lru = _lru->second._newer;
            _lru->second._older = NULL;
         }
         else{
            assert(false);
         }
         //return    _map.erase(key);
         delete erase_obj;
         _size -= 1;
         return 1;
      }

      // 到这里的时候 _map的值必然大于2 ，而且要查找的对象不能在头和尾
      iterator _end = end();
      iterator it = begin();
      ++it;
      for (; it != _end; ++it) {
         if (it.key() == key) {   
            Val*  val = *it;
            if (val->second._older)
               val->second._older->second._newer = val->second._newer;
            if (val->second._newer)
               val->second._newer->second._older = val->second._older;
            //return _map.erase(key);
            delete val;
            _size -= 1;
            return 1;
         }
      }
      
      
      return 0;
   }
   
}  // namespace lru

Re: LRU-MRU algorithm

Posted: Sat Jan 30, 2016 9:35 am
by kuafu

Code: Select all

#include "stdafx.h"


#include <iostream>

#include "lru.hpp"
#include <vector>

using namespace lru;
using namespace std;
typedef LRUWithCache<int, int> CacheType;
void print_(const CacheType& tc)
{
   cout << "================ MRU" << endl;

   for (CacheType::const_iterator it = tc.mru_begin(); it != tc.end(); ++it)
      cout << it.key() << " " << it.value() << endl;

   cout << "================ LRU" << endl;

   for (CacheType::const_iterator it = tc.lru_begin(); it != tc.end(); ++it)
      cout << it.key() << " " << it.value() << endl;

   cout << "================" << endl << endl;

}
int main()
{
   

   CacheType tc(3);

   tc.insert(1, 101);
   tc.insert(2, 102);
   tc.insert(3, 103);
   tc.insert(4, 104);
   tc.insert(5, 105);
   tc.insert(6, 105);

   cout << tc[1] << endl;
   
   print_(tc);
   tc.erase(1);
   print_(tc);
   
   tc.erase(2);
   print_(tc);


   tc.erase(4);
   print_(tc);

   tc.insert(2, 1002);
   print_(tc);

   tc.find(3);
   tc.size();
   print_(tc);

   tc.find(2);

   print_(tc);


   system("PAUSE");
   return 0;
}

Re: LRU-MRU algorithm

Posted: Sat Jan 30, 2016 9:31 pm
by UNKNwYSHSA
What's this?
All times are UTC-04:00
Page 1 of 1
Powered by phpBB® Forum Software © phpBB Limited
https://www.phpbb.com/