include/anna/core/util/LRUMap.hpp

   1 // ANNA - Anna is Not Nothingness Anymore                                                         //
   2 //                                                                                                //
   3 // (c) Copyright 2005-2015 Eduardo Ramos Testillano & Francisco Ruiz Rayo                         //
   4 //                                                                                                //
   5 // See project site at http://redmine.teslayout.com/projects/anna-suite                           //
   6 // See accompanying file LICENSE or copy at http://www.teslayout.com/projects/public/anna.LICENSE //
   7
   8
   9 #ifndef anna_core_util_LRUMap_hpp
  10 #define anna_core_util_LRUMap_hpp
  11
  12 #include <map>
  13
  14 #include <anna/config/defines.hpp>
  15
  16 namespace anna {
  17
  18 /**
  19    Patrón que permite mantener una lista de N elementos de pares (Clave, Valor).
  20
  21    Es capaz de realizar una búsqueda indexada de la clave para obtener el valor,
  22    pero además es capaz de mantener estable el número de elementos contenidos
  23    en ésta clase.
  24
  25    Si se alcanza el número máximo de elementos indicados en el constructor, si se requiere
  26    incluir un nuevo objeto, primero liberará el objeto que lleve más tiempo si ser usado.
  27
  28    \param K clase que actuará como clave del mapa. Requiere el contructor de copia, y los operadores de comparación == y <.
  29    \param V clase que actuará como dato asociado a la clave. Requiere el constructor copia y el operador copia.
  30 */
  31 template <typename K, typename V> class LRUMap {
  32   typedef typename std::pair <V, anna::Millisecond> timed_value;
  33   typedef typename std::map <K, timed_value> container;
  34   typedef typename container::value_type value_type;
  35
  36 public:
  37   typedef typename container::iterator iterator;
  38   typedef typename container::const_iterator const_iterator;
  39
  40   /**
  41      Constructor.
  42      \param name Nombre logico de esta instancia.
  43      \param measure Unidad de medida. Solo se usa a efecto de salida de datos.
  44   */
  45   LRUMap(const char* name, const int maxSize) : a_name(name), a_maxSize(maxSize) { ;}
  46
  47   /**
  48    * Destructor.
  49    */
  50   ~LRUMap() { clear(); }
  51
  52   /**
  53      Devuelve el indicador de validez de esta media.
  54      \return \em true Si la media no tiene ningun valor o \em false en caso contrario.
  55   */
  56   bool isEmpty() const { return a_container.size() == 0; }
  57
  58   /**
  59    * Devuelve el número de elementos contenidos en este contenedor.
  60    * \return  el número de elementos contenidos en este contenedor.
  61    */
  62   int size() const { return a_container.size(); }
  63
  64   /**
  65    * Devuelve el puntero al valor asociado a la clave recibida como parámetro.
  66    * Puede ser NULL si la pareja (K,V) no está registrada en el contenedor.
  67    *
  68    * \param key Clave de la que obtener el valor asociado.
  69    *
  70    * \return El puntero al valor asociado a la clave recibida como parámetro.
  71    * */
  72   V* find(const K& key) {
  73     iterator ii =  a_container.find(key);
  74
  75     if(ii == end())
  76       return NULL;
  77
  78     /*
  79      * Recupera el valor asociado a la clave K y actualiza el momento de acceso.
  80      */
  81     millisecond(ii) = functions::millisecond();
  82     return &value(ii);
  83   }
  84
  85   /**
  86    * Establece el valor de pareja (K,V). Si no existe se crea y si existe se sobre escribe el
  87    * valor asociado a V, y se actualiza su tiempo de acceso.
  88    *
  89    * \param key Clave de la pareja (K,V).
  90    * \param v Valor asociado a la clave.
  91    */
  92   void add(const K& key, const V& v) {
  93     iterator ii = a_container.find(key);
  94
  95     // Sobreescribe el valor asociado a K y actualiza su tiempo de acceso.
  96     if(ii != end()) {
  97       value(ii) = v;
  98       millisecond(ii) = functions::millisecond();
  99       return;
 100     }
 101
 102     // Si no se ha alcanzado el máximo, sólo hay que insertar el nuevo (K,V)
 103     if(size() < a_maxSize) {
 104       timed_value tvalue(v, functions::millisecond());
 105       a_container.insert(value_type(key, tvalue));
 106       return;
 107     }
 108
 109     // Se ha alcanzado el máximo, hay que buscar el que haga más tiempo que no se
 110     // accede => el que tenga el menor 'Time' asociado.
 111     iterator minii = begin();
 112     Millisecond minTime = millisecond(minii);
 113
 114     for(iterator ii = begin(), maxii = end(); ii != maxii; ii ++) {
 115       if(millisecond(ii) < minTime)
 116         minTime = millisecond(minii = ii);
 117     }
 118
 119     /*
 120      * El map no permite sobre-escribir la clave => por eso tenemos que borrar el nodo
 121      * más antiguo y crear otro nuevo.
 122      */
 123     a_container.erase(minii);
 124     timed_value tvalue(v, functions::millisecond());
 125     a_container.insert(value_type(key, tvalue));
 126   }
 127
 128   /**
 129      Vacía este contenedor.
 130   */
 131   void clear() { a_container.clear(); }
 132
 133   /**
 134    * Devuelve un iterator al primer elemento del contenedor, teniendo que la ordenación de los
 135    * pares (K,V) se hará en base a K.
 136    * \return El primer elemento del contenedor.
 137   */
 138   iterator begin() { return a_container.begin(); }
 139
 140   /**
 141    * Devuelve un iterator al primer elemento del contenedor, teniendo que la ordenación de los
 142    * pares (K,V) se hará en base a K.
 143    * \return El primer elemento del contenedor.
 144   */
 145   const_iterator begin() const { return a_container.begin(); }
 146
 147   /**
 148    * Devuelve un iterator al final del contenedor, teniendo que la ordenación de los  pares (K,V) se hará en
 149    * base a K.
 150    * \return El primer elemento del contenedor.
 151    */
 152   iterator end() { return a_container.end(); }
 153
 154   /**
 155    * Devuelve un iterator al final del contenedor, teniendo que la ordenación de los  pares (K,V) se hará en
 156    * base a K.
 157    * \return El primer elemento del contenedor.
 158    */
 159   const_iterator end() const { return a_container.end(); }
 160
 161   /**
 162    * Devuelve la clave asociada al iterador recibido como parámetro.
 163    * \param ii Iterador que debe estar comprendido entre  [#begin (), #end).
 164    * \return la clave asociada al iterador recibido como parámetro.
 165    * \warning Los acceso mediante iterador no actualiza el tiempo de acceso a la pareja (K,V).
 166    */
 167   static K key(iterator& ii) { return ii->first;  }
 168
 169   /**
 170    * Devuelve el valor asociado al iterador recibido como parámetro.
 171    * \param ii Iterador que debe estar comprendido entre  [#begin (), #end).
 172    * \return el valor asociado al iterador recibido como parámetro.
 173    * \warning Los acceso mediante iterador no actualiza el tiempo de acceso a la pareja (K,V).
 174    */
 175   static V& value(iterator& ii) {
 176     timed_value* v = &ii->second;
 177     return v->first;
 178   }
 179
 180   /**
 181    * Devuelve el tiempo de acceso asociado al iterador recibido como parámetro.
 182    * \param ii Iterador que debe estar comprendido entre  [#begin (), #end).
 183    * \return el tiempo de acceso asociado al iterador recibido como parámetro.
 184    */
 185   static Millisecond& millisecond(iterator& ii) {
 186     timed_value* v = &ii->second;
 187     return v->second;
 188   }
 189
 190   /**
 191    * Devuelve la clave asociada al iterador recibido como parámetro.
 192    * \param ii Iterador que debe estar comprendido entre  [#begin (), #end).
 193    * \return la clave asociada al iterador recibido como parámetro.
 194    * \warning Los acceso mediante iterador no actualiza el tiempo de acceso a la pareja (K,V).
 195    */
 196   static K key(const_iterator& ii) { return ii->first;  }
 197
 198   /**
 199    * Devuelve el valor asociado al iterador recibido como parámetro.
 200    * \param ii Iterador que debe estar comprendido entre  [#begin (), #end).
 201    * \return el valor asociado al iterador recibido como parámetro.
 202    * \warning Los acceso mediante iterador no actualiza el tiempo de acceso a la pareja (K,V).
 203    */
 204   static const V& value(const_iterator& ii) {
 205     const timed_value* v = &ii->second;
 206     return v->first;
 207   }
 208
 209   /**
 210    * Devuelve el tiempo de acceso asociado al iterador recibido como parámetro.
 211    * \param ii Iterador que debe estar comprendido entre  [#begin (), #end).
 212    * \return el tiempo de acceso asociado al iterador recibido como parámetro.
 213    */
 214   static Millisecond millisecond(const_iterator& ii) {
 215     const timed_value* v = &ii->second;
 216     return v->second;
 217   }
 218
 219   /**
 220      Devuelve una cadena con la informacion referente a esta clase.
 221      \return Una cadena con la informacion referente a esta clase.
 222   */
 223   std::string asString() const
 224   {
 225     std::string msg("LRUMap { Name: ");
 226     msg += a_name;
 227     msg += functions::asText(" | N: ", a_maxSize);
 228     msg += functions::asText(" | n: ", size());
 229     return msg += " }";
 230   }
 231
 232 private:
 233   const char* a_name;
 234   const int a_maxSize;
 235   container a_container;
 236 };
 237
 238 }
 239
 240 #endif
 241
 242
 243