tpl_linHash.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_LINHASH_H
# define TPL_LINHASH_H
# include <primes.H>
# include <tpl_dynArray.H>
# include <tpl_lhash.H>

# ifdef N
# define NBACKUP N
# undef N
# endif

# ifdef M
# define MBACKUP M
# undef M
# endif

using namespace Aleph;

namespace Aleph {

    template <typename Key, 
              template <class> class BucketType, 
              class Cmp = Aleph::equal_to<Key> >
class GenLinearHashTable 
{

public:
  
  typedef size_t (*Hash_Fct)(const Key &);

  typedef BucketType<Key> Bucket;

  static const float default_upper_alpha;

  static const float default_lower_alpha;

private:

  typedef Dnode<Key> BucketList;

  typedef typename Dnode<Key>::Iterator BucketItor;

  static size_t multiply_by_two(const size_t & n) { return n << 1; }

  static size_t divide_by_two(const size_t & n) { return n >> 1; }


  DynArray<BucketList>   table;
  Hash_Fct               hash_fct; // puntero a función hash
  size_t                 M; // Tamaño de la tabla
  size_t                 N; // Número de elementos que tiene la tabla
  size_t                 busy_slots_counter; // Cantidad de entradas del
                                             // arreglo ocupadas 
  bool                   remove_all_buckets; // Indica si se deben liberar
                                             // las cubetas cuando se
                                             // llame al destructor 
  float upper_alpha; // factor de carga superior
  float lower_alpha; // factor de carga inferior
  size_t p; // índice de la lista que se particiona (o aumenta)
  size_t l; // cantidad de veces que se ha duplicado la tabla
  size_t MP; // guarda el valor p + M
  size_t MM; // producto 2*M
  const size_t len;
  size_t call_hash_fct(const Key & key) const
  {
    const size_t hash = (*hash_fct)(key);

    const size_t i = hash % M;

    return i < p ? hash % MM : i;
  }
  void expand()
  {
        // expandir la tabla hasta que la carga esté debajo de upper_alpha
    for (float alpha = 1.0*N/MP; alpha >= upper_alpha; alpha = 1.0*N/MP)
      {
        BucketList * src_list_ptr = table.test(p);

        if (src_list_ptr != NULL) // ¿table[p] está escrita?
          if (not src_list_ptr->is_empty()) // ¿table[p] no está vacía'
            {
              BucketList * tgt_list_ptr = NULL; 
         
                  // recorrer toda la lista de colisiones
              for (BucketItor it(*src_list_ptr); it.has_current(); /* nothing */)
                {
                  Bucket * bucket = static_cast<Bucket*>(it.get_current());

                  it.next(); // avance al siguiente elemento de la lista
            
                  const Key & key = bucket->get_key();

                  const int i = (*hash_fct)(key) % MM;

                  if (i == p) // ¿pertenece esta clave a table[p]?
                    continue; // sí ==> clave permanece en table[p]

                  if (tgt_list_ptr == NULL)
                    tgt_list_ptr = &table.touch(MP);

                      // bucket no pertenece a table[p]] sino a table[p+m] ==>
                      // eliminar bucket de table[i] e insertarlo en table[p+m]
                  bucket->del();
                  tgt_list_ptr->append(bucket);
                }

              if (src_list_ptr->is_empty()) // ¿table[p] quedó vacía?
                --busy_slots_counter; // sí ==> un slot vacío 

              ++busy_slots_counter; // uno nuevo por table[p+M]
            } 
        ++p;
        ++MP;
        if (p == M) // (p == 2*M) ¿debe duplicarse el tamaño de la tabla?
          {     // sí ==> modificar el tamaño de la tabla a 2*M
            ++l;   // Cantidad de veces que se ha duplicado la tabla
            p = 0;
            MP = M = MM; // se les asigna 2*M
            MM = multiply_by_two(MM);
          }
      } 
  }
  void contract()
  {
        // contraer la tabla hasta que la carga esté por debajo de lower_alpha
    for (float alpha = (1.0*N)/MP; alpha <= lower_alpha and MP > len; 
         alpha = (1.0*N)/MP)
      {
        if (p == 0) // ¿debe dividirse entre 2 el tamaño de la tabla?
          {     // sí ==> actualizar tamaño de la tabla a M/2
            --l; // Cantidad de veces que se ha duplicado la tabla disminuye
            MM = M; // se divide entre dos
            M = divide_by_two(M);
            p = M - 1;
          }
        else
          // no ==> sólo reducir índice p
          --p;

        --MP;
        if (MP < table.size()) // ¿Existe table[MP]]? 
          {
            BucketList * src_list_ptr = table.test(MP);

            if (src_list_ptr != NULL) // ¿existe entrada para table[p+M]?
              {
                if (not src_list_ptr->is_empty()) // ¿está vacía table[p+M]?
                  {     // no ==> fusionar las listas
                    BucketList & tgt_list = table.touch(p); // asegura table[p]
                    
                    tgt_list.concat_list(src_list_ptr);

                    --busy_slots_counter; // table[p+M] devino vacía
                  }

                table.cut(MP); // eventualmente liberar memoria de table[p+M]
              }
          }
      }
  }

public:

  GenLinearHashTable(Hash_Fct       __hash_fct, 
                     const size_t & __len, 
                     const float &  __lower_alpha,
                     const float &  __upper_alpha,
                     const bool &   __remove_all_buckets) 
    throw(std::exception, std::length_error, std::domain_error,
          std::bad_alloc, std::overflow_error) 
    : table(__len), hash_fct(__hash_fct), M(__len), N(0), 
      busy_slots_counter(0), remove_all_buckets(__remove_all_buckets), 
      upper_alpha(__upper_alpha), lower_alpha(__lower_alpha),
      p(0), l(0), MP(M), MM(multiply_by_two(M)), len(__len)
  {
    if (M == 0)
      std::length_error("table's length is zero");

    if (MM > table.max_size())
      throw std::length_error("table's length too big");
      
    if (upper_alpha <= lower_alpha)
      throw std::domain_error("lower alpha is greater than lower alpha");
  }

  void set_upper_alpha(const float &  __upper_alpha)
  {
    if (__upper_alpha <= lower_alpha)
      throw std::domain_error("upper_alpha lower than lower_alpha");

    upper_alpha = __upper_alpha;
  }

  void set_lower_alpha(const float &  __lower_alpha)
  {
    if (__lower_alpha >= upper_alpha)
      throw std::domain_error("lower_alpha greater than upper_alpha");

    lower_alpha = __lower_alpha;
  }

  void empty()
  {
        // Recorrer cada una de la listas y liberar sus cubetas
    for (int i = 0; i < MP; ++i)
      {
        BucketList * list = table.test(i);

        if (list != NULL)
          list->remove_all_and_delete();
      }
    
    M = MP = len;
    MM = multiply_by_two(M);
    N = p = l = 0;

    table.cut(len); 
  }

  ~GenLinearHashTable()
  {
    if (remove_all_buckets)
      empty();
  }
  Bucket * search(const Key & key)
  {
    const int i = call_hash_fct(key);

    BucketList * list = table.test(i);

    if (list == NULL) // ¿Ha sido escrita alguna vez table[i]?
      return NULL; // No ==> el elemento no se encuentra en la tabla

    if (list->is_empty()) 
      return NULL;

        // buscar key en la lista de cubetas
    for (BucketItor it(*list); it.has_current(); it.next())
      {
        Bucket * bucket = static_cast<Bucket*>(it.get_current());
        
        if (Cmp() (key, bucket->get_key()))
          return bucket; 
      }
    
    return NULL; 
  }



  const size_t & size() const { return N; }

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

  const size_t & busy_slots() const { return busy_slots_counter; }

  const size_t & expansions() const { return l; }

  Bucket* insert(Bucket * bucket)
  {
    const int i = call_hash_fct(bucket->get_key());

    BucketList & list = table.touch(i); // asegura memoria para table[i]

    if (list.is_empty())
      ++busy_slots_counter;

    list.append(bucket);

    ++N;

    expand();

    return bucket;
  }
  Bucket * remove(Bucket * bucket)
  {
    Bucket * next = static_cast<Bucket*>(bucket->get_next());

    bucket->del(); // elimine de lista de colisiones

    if (next->is_empty()) // ¿lista de colisiones quedó vacía?
      --busy_slots_counter; // sí ==> un slot vacío

    --N;

    contract();

    return bucket;
  }
  void print()
  {
    for (int i = 0; i < MP; ++i)
      {
        cout << "table[" << i << "] = [ ";
        
        if (table.exist(i))
          {
            BucketList & list = table.access(i);

            if (not list.is_empty())
              for (BucketItor it(list); it.has_current(); it.next())
                {
                  Bucket * bucket = static_cast<Bucket*>(it.get_current());

                  const Key & key = bucket->get_key();

                  cout << key << ",";
                }
          }
        cout << "]" << endl;
      }
  }
};

    template <typename Key, template <class> class BucketType, class Cmp>
  const float
GenLinearHashTable<Key, BucketType, Cmp>::default_upper_alpha = 0.95;

    template <typename Key, template <class> class BucketType, class Cmp>
  const float 
GenLinearHashTable<Key, BucketType, Cmp>::default_lower_alpha = 0.25;


    template <typename Key, class Cmp = Aleph::equal_to<Key> >
class LinearHashTable : public GenLinearHashTable<Key, LhashBucket, Cmp>
{
  // ...

typedef GenLinearHashTable<Key, LhashBucket, Cmp> Base;

public:

  typedef typename GenLinearHashTable<Key, LhashBucket, Cmp>::Bucket Bucket;

  typedef typename GenLhashTable<Key, LhashBucket<Key>, Cmp>::Hash_Fct Hash_Fct;

  LinearHashTable(Hash_Fct       hash_fct, 
                  const size_t & len,
                  const float &  lower_alpha = Base::default__lower_alpha,
                  const float &  upper_alpha = Base::default_upper_alpha,
                  const bool &   remove_all_buckets = true)
    throw(std::exception, std::length_error, std::runtime_error,
          std::bad_alloc, std::overflow_error)
    : Base(hash_fct, len, lower_alpha, upper_alpha, remove_all_buckets)
  {
    // Empty
  }

};

  template <typename Key, class Cmp = Aleph::equal_to<Key> >
class LinearHashTableVtl : public GenLinearHashTable<Key, LhashBucketVtl, Cmp>
{
  // ...

  typedef GenLinearHashTable<Key, LhashBucketVtl, Cmp> Base;

public:

  typedef typename GenLinearHashTable<Key, LhashBucketVtl, Cmp>::Bucket Bucket;

      typedef typename 
  GenLhashTable<Key, LhashBucketVtl<Key>, Cmp >::Hash_Fct Hash_Fct;

  LinearHashTableVtl(Hash_Fct       hash_fct, 
                     const size_t & len,
                     const float &  lower_alpha = Base::default_lower_alpha,
                     const float &  upper_alpha = Base::default_upper_alpha,
                     const bool &   remove_all_buckets = true)
    throw(std::exception, std::length_error, std::runtime_error,
          std::bad_alloc, std::overflow_error)
    : Base(hash_fct, len, lower_alpha, upper_alpha, remove_all_buckets)
  {
    // Empty
  }

};

} // end namespace Aleph

# ifdef NBACKUP
# define N NBACKUP
# undef NBACKUP
# endif

# ifdef MBACKUP
# define M MBACKUP
# undef MBACKUP
# endif

# endif // TPL_LINHASH_H

---