---

misc/lru.h

Go to the documentation of this file.

#ifndef MISC_LRU_H
#define MISC_LRU_H

/*

  GLT OpenGL C++ Toolkit (LGPL)
  Copyright (C) 2000-2002 Nigel Stewart  

  Email: nigels.com@gmail.com   
  WWW:   http://www.nigels.com/glt/

  This library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Lesser General Public
  License as published by the Free Software Foundation; either
  version 2.1 of the License, or (at your option) any later version.

  This library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser General Public
  License along with this library; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

*/

#include <glt/config.h>

#ifdef GLT_WIN32
#pragma warning(disable : 4786)     
#endif

#include <cassert>
#include <list>
#include <map>

#if defined(_STLP_MAP) || defined(__SGI_STL_MAP)
#include <hash_map>
using namespace std;
#define USE_HASH_MAP
#else 
  #if defined(_CPP_MAP)
  #include <ext/hash_map>
  using namespace __gnu_cxx;
  #define USE_HASH_MAP
  #endif
#endif

template<class T1,class T2>
class lru
{
public:

    typedef std::list< std::pair<T1,T2> >           List;

    #ifdef USE_HASH_MAP
    typedef hash_map<T1,typename List::iterator>   Map;
    #else
    typedef std::map<T1,typename List::iterator>        Map;
    #endif

    lru()
    {
    }
    
    ~lru()
    {
        clear();
    }

    const uint32 size() const
    {
        return _list.size();
    }

    const T2 &front() const
    {
        assert(size());
        return _list.front().second;
    }

    const T2 &back() const
    {
        assert(size());
        return _list.back().second;
    }

    const T2 pop_front() 
    {
        const T1 id  = _list.front().first;
        _index.erase(id);

        const T2 tmp = _list.front().second;
        _list.erase(_list.begin());
        return tmp;
    }

    const T2 pop_back() 
    {
        const T1 id  = _list.back().first;
        _index.erase(id);

        const T2 tmp = _list.back().second;
        _list.erase(--_list.end());

        return tmp;
    }

    T2 &insert(const T1 &first)
    {
        // Check that container is not empty
        assert(size());

        // Check that the item is not already inserted
        assert(!find(first,false));

        // Take the least recently used (LRU) item in the list
        typename List::iterator n = _list.end();
        --n;

        // Move it to front of list
        _list.splice(_list.begin(),_list,n);

        // Remove it from index
        _index.erase(n->first);

        // Replace with current data
        n->first = first;

        // Update index
        _index[first] = n;

        // Return second 
        return n->second;
    }

    const T2 &insert(const T1 &first,const T2 &second)
    {
        // Check that the item is not already inserted
        assert(!find(first,false));

        // Insert into list
        _list.push_front(make_pair(first,second));

        // Iterator
        typename List::iterator n = _list.begin();

        // Insert into balanced tree index
        _index[first] = n;

        // Return second 
        return n->second;
    }

    T2 *find(const T1 &first,bool touch = true) 
    {
        typename Map::iterator i = _index.find(first);

        if (i==_index.end())
            return NULL;
        else
        {
            // Move node to front of list, if necessary
            if (touch)
            {
                typename List::iterator n = i->second;
                _list.splice(_list.begin(),_list,n);
                return &(_list.front().second);
            }
            else
                return &(i->second->second);
        }
    }

    const T2 &operator[](const uint32 n) const
    {
        assert(_list.size());

        typename List::const_iterator i = _list.begin();
        for (uint32 j=0; j<n-1; j++,i++)
            if (i==_list.end())
                return _list.back().second;

        return i->second;
    }

    void clear()
    {
        _index.clear();
        _list.clear();
    }

private:

    List    _list;
    Map     _index;
};

#endif

---