tpl_hash_cache.H

/* Aleph-w

     / \  | | ___ _ __ | |__      __      __
    / _ \ | |/ _ \ '_ \| '_ \ ____\ \ /\ / / Data structures & Algorithms
   / ___ \| |  __/ |_) | | | |_____\ V  V /  version 1.9b
  /_/   \_\_|\___| .__/|_| |_|      \_/\_/   https://github.com/lrleon/Aleph-w
  |_|

  This file is part of Aleph-w library

  Copyright (c) 2002-2018 Leandro Rabindranath Leon & Alejandro Mujica

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

  This program 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
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program. If not, see <https://www.gnu.org/licenses/>.
*/

# ifndef TPL_HASH_CACHE_H
# define TPL_HASH_CACHE_H

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

namespace Aleph {


  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 entrada está contenida
                             // dentro de 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;

      Dlink * link_inside() { return &dlink_inside; }

      LINKNAME_TO_TYPE(Cache_Entry, dlink_inside);

    public:

      Cache_Entry()
        : data(), 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 cubetas apartadas y metidas en tabla
    size_t cache_size;  // máx número de entradas que puede tener cache
    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 posición actual
      lru_list.insert(cache_entry->link_lru()); // llévela a trasero
    }

    void do_lru(Cache_Entry * cache_entry)
    {
      cache_entry->link_lru()->del(); // elimine de posición actual
      lru_list.append(cache_entry->link_lru()); // llévela al 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  entrada más antigua; 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 contenida en tabla ==> eliminarlo
      if (cache_entry->is_in_hash_table)
        remove_entry_from_hash_table(cache_entry);

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

      return cache_entry;
    }

  public:

    Hash_Cache(size_t (*hash_fct)(const Key&),
               size_t __hash_size, const size_t & __cache_size)
      : hash_table(__hash_size, hash_fct),
        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::unique_ptr<Chunk_Descriptor>
            chunk_descriptor (new Chunk_Descriptor (entries_array));
          chunk_list.insert(chunk_descriptor.get());

          // insertar cada Cache_Entry en 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(); // entrada más antigua
      cache_entry->get_key()    = key;             // escribirle el par
      cache_entry->get_data()   = data;
      inside_list.insert(cache_entry->link_inside());
      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 = (Cache_Entry*) hash_table.search(key);
      if (cache_entry != nullptr) // ¿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 != nullptr)
        {
          do_mru(next_entry);
          move_to_inside_front(cache_entry);
        }
      return next_entry;
    }

    void lock_entry(Cache_Entry * cache_entry)
    {

      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)
    {
      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)
    {
      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)
    {
      if (plus_size == 0)
        throw std::range_error ("bad plus_size");

      const size_t new_cache_size = cache_size + plus_size;

      // apartar plus_size nuevas entradas
      Cache_Entry * entries_array = new Cache_Entry [plus_size];

      try
        {
          std::unique_ptr<Chunk_Descriptor>     // apartar el descriptor
            chunk_descriptor (new Chunk_Descriptor (entries_array));

          // Calcular nuevo tamaño de tabla 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 en lru_list
          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:
      typedef Hash_Cache Set_Type;
      typedef Cache_Entry * Item_Type;

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

      Cache_Entry * get_curr()
      {
        Dlink * dl = Dlink::Iterator::get_curr();
        return Cache_Entry::dlink_inside_to_Cache_Entry(dl);
      }
    };
  };


} // end namespace Aleph

# endif // TPL_HASH_CACHE_H