tpl_hash_cache.H

/*
  This file is part of Aleph system

  Copyright (c) 2002, 2003, 2004, 2005, 2006
  UNIVERSITY LOS ANDES (ULA) Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA  

  - Center of Studies in Microelectronics & Distributed Systems (CEMISID) 
  - ULA Computer Science Department
  - FUNDACITE Mérida - Ministerio de Ciencia y Tecnología

  PERMISSION TO USE, COPY, MODIFY AND DISTRIBUTE THIS SOFTWARE AND ITS
  DOCUMENTATION IS HEREBY GRANTED, PROVIDED THAT BOTH THE COPYRIGHT
  NOTICE AND THIS PERMISSION NOTICE APPEAR IN ALL COPIES OF THE
  SOFTWARE, DERIVATIVE WORKS OR MODIFIED VERSIONS, AND ANY PORTIONS
  THEREOF, AND THAT BOTH NOTICES APPEAR IN SUPPORTING DOCUMENTATION.

  Aleph 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.

  UNIVERSIDAD DE LOS ANDES requests users of this software to return to 

  Leandro Leon
  CEMISID 
  Ed La Hechicera 
  3er piso, ala sur
  Facultad de Ingenieria 
  Universidad de Los Andes 
  Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA    or

  lrleon@ula.ve

  any improvements or extensions that they make and grant Universidad 
  de Los Andes (ULA) the rights to redistribute these changes. 

  Aleph is (or was) granted by: 
  - Consejo de Desarrollo Cientifico, Humanistico, Tecnico de la ULA 
    (CDCHT)
  - Fundacite Mérida
*/


# ifndef TPL_HASH_CACHE_H
# define TPL_HASH_CACHE_H

# include <memory>
# include <aleph.H>
# include <tpl_dnode.H>
# include <tpl_lhash.H>

    template <typename  Key, typename Data, class Cmp = Aleph::equal_to<Key> >
class Hash_Cache
{

public:

  class Cache_Entry : public LhashTable<Key, Cmp>::Bucket
  { 

    friend class Hash_Cache<Key, Data>;

    Data    data; 

    Dlink   dlink_lru; // enlace a la cola lru 
    Dlink* link_lru() { return &dlink_lru; }
    bool locked; // indica si la entrada está trancada
    bool is_in_hash_table; // indica si la entrada está contenida dentro de
                           // la tabla hash 
    void lock() 
    { 
      if (locked)
        throw std::runtime_error("Cache_Entry is already locked");

      locked = true; 
    }

    void unlock()
    { 
      if (not locked)
        throw std::runtime_error("Cache_Entry is not locked");

      locked = false; 
    }
    Dlink   dlink_inside; // enlace a la lista de entradas que 

    Dlink * link_inside() { return &dlink_inside; }

    LINKNAME_TO_TYPE(Cache_Entry, dlink_inside);

  public:
    Cache_Entry() : locked(false), is_in_hash_table(false) { /* empty */ }


    Data & get_data() { return data; }
    const bool & is_locked() const { return locked; }

    const bool & is_in_table() const { return is_in_hash_table; }
  }; // fin class Cache_Entry

private:

  LhashTable<Key, Cmp> hash_table;
  LINKNAME_TO_TYPE(Cache_Entry, dlink_lru);
  Dlink    lru_list; // cabecera de la lista lru
  size_t   num_lru;  // número de elementos en lista lru
  Dlink  inside_list; // lista de entradas (cubetas) ya apartadas y
                      // metidas en la tabla hash

  size_t cache_size;  // tamaño del cache; máximo número de entradas que
                      // puede contener  
  Dlink  locked_list; // lista de entradas trancadas
  size_t num_locked;  // número de elementos trancados
  typedef Dnode<Cache_Entry*> Chunk_Descriptor;

  Chunk_Descriptor chunk_list;  
  void insert_entry_to_lru_list(Cache_Entry * cache_entry)
  {
    num_lru++;
    lru_list.insert(cache_entry->link_lru());
  }

  void remove_entry_from_lru_list(Cache_Entry * cache_entry)
  {
    num_lru--;
    cache_entry->link_lru()->del();
  }

  void insert_entry_to_locked_list(Cache_Entry * cache_entry)
  {
    num_locked++;
    locked_list.insert(cache_entry->link_lru());
  }

  void remove_entry_from_locked_list(Cache_Entry * cache_entry)
  {
    num_locked--;
    cache_entry->link_lru()->del();
  }

  void move_to_inside_front(Cache_Entry * cache_entry)
  {
    cache_entry->link_inside()->del();
    inside_list.insert(cache_entry->link_inside());
  }

  void do_mru(Cache_Entry * cache_entry) 
  { 
    cache_entry->link_lru()->del(); // elimine de su posición actual
    lru_list.insert(cache_entry->link_lru()); // colóquelo en el trasero
  }
  void do_lru(Cache_Entry * cache_entry) 
  { 
    cache_entry->link_lru()->del(); // elimine de su posición actual
    lru_list.append(cache_entry->link_lru()); // insértelo en el frente
  }
  void remove_entry_from_hash_table(Cache_Entry * cache_entry)
  {
    cache_entry->link_inside()->del();

    hash_table.remove(cache_entry);
    cache_entry->is_in_hash_table = false;
    do_lru(cache_entry);
  }

  Cache_Entry * get_lru_entry()
  {

    if (lru_list.is_empty())   // ¿existe una entrada disponible?
      throw std::underflow_error("All entries are locked"); // no ==> ¡excepción! 

        // obtenga la entrada más antigua -la menos recientemente accedida
    Dlink * lru_entry_link = lru_list.get_prev();
    Cache_Entry * cache_entry = dlink_lru_to_Cache_Entry(lru_entry_link);

        // si cache_entry está contenida en la tabla hay que eliminarlo
    if (cache_entry->is_in_hash_table) 
      remove_entry_from_hash_table(cache_entry);

    do_mru(cache_entry); // la entrada deviene la más recientemente accedida
            
    return cache_entry;
  }

public:

  Hash_Cache(size_t         (*hash_fct)(const Key&), 
             const size_t & __hash_size,
             const size_t & __cache_size) 

    throw (std::exception, std::bad_alloc)

    : hash_table(hash_fct, __hash_size, false),
      num_lru(0), cache_size(__cache_size), num_locked(0)
  {
        // apartar entradas del cache
    Cache_Entry * entries_array = new Cache_Entry [cache_size];

    try 
    { 


          // apartar el descriptor del arreglo
      std::auto_ptr<Chunk_Descriptor> 
        chunk_descriptor (new Chunk_Descriptor (entries_array));

      chunk_list.insert(chunk_descriptor.get());

            // insertar todos los Cache_Entry en la lista lru
      for (int i = 0; i < cache_size; i++)
        insert_entry_to_lru_list(&entries_array[i]);
          
      chunk_descriptor.release();

    }
    catch (...)
      {
        delete [] entries_array;
        throw;
      }

  }

  virtual ~Hash_Cache() 
  {
        // recorrer lista de bloques y liberarlos
    while (not chunk_list.is_empty())
      {
        Chunk_Descriptor * current_chunk = chunk_list.remove_next();

        delete [] current_chunk->get_data();
        delete current_chunk;
      }
  }      

  Cache_Entry * insert(const Key & key, const Data & data) 
  {
    Cache_Entry * cache_entry = get_lru_entry(); // obtener entrada más antigua
          
        // escribirle el par
    cache_entry->get_key()  = key;  
    cache_entry->get_data() = data;
          
    inside_list.insert(cache_entry->link_inside()); // insértela en inside_list

        // insertarla en la tabla hash
    hash_table.insert(cache_entry);
    cache_entry->is_in_hash_table = true;

    return cache_entry;
  }
  Cache_Entry * search(const Key & key)
  {
        // buscar en la tabla hash
    Cache_Entry * cache_entry = static_cast<Cache_Entry*>(hash_table.search(key));
      
    if (cache_entry != NULL) // ¿fue encontrada la clave?
      {     // sí ==> hacerla la más recientemente usada
        do_mru(cache_entry);
        move_to_inside_front(cache_entry);
      } 
      
    return cache_entry;
  }

  Cache_Entry * search_next(Cache_Entry * cache_entry)
  {
    Cache_Entry *next_entry = 
      static_cast<Cache_Entry*>(hash_table.search_next(cache_entry));
      
    if (next_entry != NULL)
      {
        do_mru(next_entry);
        move_to_inside_front(cache_entry);
      } 
      
    return next_entry;
  }

  void lock_entry(Cache_Entry * cache_entry) 

    throw(std::exception, std::runtime_error, std::domain_error)

  {

    if (cache_entry->is_locked())
      throw std::runtime_error("Cache_Entry is already locked");

    if (not cache_entry->is_in_table())
      throw std::domain_error("Cache_Entry is not in the cache");

    remove_entry_from_lru_list(cache_entry);
    insert_entry_to_locked_list(cache_entry);
      
    cache_entry->lock();
  }
  void unlock_entry(Cache_Entry * cache_entry) 

    throw(std::exception, std::runtime_error)

  { 

    if (not cache_entry->is_locked())
      throw std::runtime_error("Cache_Entry is not locked");

    remove_entry_from_locked_list(cache_entry);
    insert_entry_to_lru_list(cache_entry);

    cache_entry->unlock();
  }
  void remove(Cache_Entry * cache_entry) 

    throw(std::exception, std::runtime_error, std::domain_error)

  {

    if (cache_entry->is_locked())
      throw std::runtime_error("Cache_Entry is already locked");

    if (not cache_entry->is_in_table())
      throw std::domain_error("Cache_Entry is not in the cache");

    remove_entry_from_hash_table(cache_entry);
  }
  void expand(const size_t & plus_size) 

    throw(std::exception, std::range_error, std::bad_alloc)

  {

    if (plus_size == 0)
      throw std::range_error ("bad plus_size");

    const size_t new_cache_size = cache_size + plus_size;

    Cache_Entry * entries_array = new Cache_Entry [plus_size];

    try
      {


            // apartar el descriptor
        std::auto_ptr<Chunk_Descriptor> 
          chunk_descriptor (new Chunk_Descriptor (entries_array));

            // Calcular el nuevo tamaño de la tabla hash y relocalizar sus
            // entradas  
        const float curr_hash_ratio = 1.0*cache_size/hash_table.capacity();
        const size_t new_hash_capacity = new_cache_size/curr_hash_ratio;
        hash_table.resize(new_hash_capacity);

            // Meter nuevas entradas del cache en la lista lru
        for (int i = 0; i < plus_size; i++)
          insert_entry_to_lru_list(&entries_array[i]);
             
        chunk_list.insert(chunk_descriptor.release());

        cache_size = new_cache_size;

      }
    catch (...)
      {
        delete []  entries_array;
        throw;
      }

  }


  const size_t & capacity() const { return cache_size; }

  const size_t & size() const { return hash_table.size(); }

  const size_t & get_num_locked() const { return num_locked; }

  const size_t & get_num_busy_slots() const 
  { 
    return hash_table.get_num_busy_slots(); 
  }

  const size_t & get_hash_capacity() const 
  {
    return hash_table.capacity();
  }

  class Iterator : public Dlink::Iterator
  {

  public:

    Iterator(Hash_Cache & cache) 
      : Dlink::Iterator(&cache.inside_list) { /* empty */ }

    Cache_Entry * get_current()  
    { 
      Cache_Entry * ret_val =  
        Cache_Entry::dlink_inside_to_Cache_Entry(Dlink::Iterator::get_current()); 

      return ret_val;  
    } 
  };
};

# endif // TPL_HASH_CACHE_H 

---