LRUMap.hpp

Go to the documentation of this file.

// ANNA - Anna is Not Nothingness Anymore                                                         //
//                                                                                                //
// (c) Copyright 2005-2015 Eduardo Ramos Testillano & Francisco Ruiz Rayo                         //
//                                                                                                //
// See project site at http://redmine.teslayout.com/projects/anna-suite                           //
// See accompanying file LICENSE or copy at http://www.teslayout.com/projects/public/anna.LICENSE //


#ifndef anna_core_util_LRUMap_hpp
#define anna_core_util_LRUMap_hpp

#include <map>

#include <anna/config/defines.hpp>

namespace anna {

template <typename K, typename V> class LRUMap {
  typedef typename std::pair <V, anna::Millisecond> timed_value;
  typedef typename std::map <K, timed_value> container;
  typedef typename container::value_type value_type;

public:
  typedef typename container::iterator iterator;
  typedef typename container::const_iterator const_iterator;

  LRUMap(const char* name, const int maxSize) : a_name(name), a_maxSize(maxSize) { ;}

  ~LRUMap() { clear(); }

  bool isEmpty() const { return a_container.size() == 0; }

  int size() const { return a_container.size(); }

  V* find(const K& key) {
    iterator ii =  a_container.find(key);

    if(ii == end())
      return NULL;

    /*
     * Recupera el valor asociado a la clave K y actualiza el momento de acceso.
     */
    millisecond(ii) = functions::millisecond();
    return &value(ii);
  }

  void add(const K& key, const V& v) {
    iterator ii = a_container.find(key);

    // Sobreescribe el valor asociado a K y actualiza su tiempo de acceso.
    if(ii != end()) {
      value(ii) = v;
      millisecond(ii) = functions::millisecond();
      return;
    }

    // Si no se ha alcanzado el máximo, sólo hay que insertar el nuevo (K,V)
    if(size() < a_maxSize) {
      timed_value tvalue(v, functions::millisecond());
      a_container.insert(value_type(key, tvalue));
      return;
    }

    // Se ha alcanzado el máximo, hay que buscar el que haga más tiempo que no se
    // accede => el que tenga el menor 'Time' asociado.
    iterator minii = begin();
    Millisecond minTime = millisecond(minii);

    for(iterator ii = begin(), maxii = end(); ii != maxii; ii ++) {
      if(millisecond(ii) < minTime)
        minTime = millisecond(minii = ii);
    }

    /*
     * El map no permite sobre-escribir la clave => por eso tenemos que borrar el nodo
     * más antiguo y crear otro nuevo.
     */
    a_container.erase(minii);
    timed_value tvalue(v, functions::millisecond());
    a_container.insert(value_type(key, tvalue));
  }

  void clear() { a_container.clear(); }

  iterator begin() { return a_container.begin(); }

  const_iterator begin() const { return a_container.begin(); }

  iterator end() { return a_container.end(); }

  const_iterator end() const { return a_container.end(); }

  static K key(iterator& ii) { return ii->first;  }

  static V& value(iterator& ii) {
    timed_value* v = &ii->second;
    return v->first;
  }

  static Millisecond& millisecond(iterator& ii) {
    timed_value* v = &ii->second;
    return v->second;
  }

  static K key(const_iterator& ii) { return ii->first;  }

  static const V& value(const_iterator& ii) {
    const timed_value* v = &ii->second;
    return v->first;
  }

  static Millisecond millisecond(const_iterator& ii) {
    const timed_value* v = &ii->second;
    return v->second;
  }

  std::string asString() const
  {
    std::string msg("LRUMap { Name: ");
    msg += a_name;
    msg += functions::asText(" | N: ", a_maxSize);
    msg += functions::asText(" | n: ", size());
    return msg += " }";
  }

private:
  const char* a_name;
  const int a_maxSize;
  container a_container;
};

}

#endif