tpl_lhash.H

# ifndef TPL_LHASH_H
# define TPL_LHASH_H

# include <iostream>
# include <primes.H>
# include <hash-fct.H>
# include <tpl_dlist.H>
# include <tpl_dynArray.H>
# include <hash-dry.H>

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

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

using namespace Primes;

using namespace Aleph;

namespace Aleph {

    template <typename Key, class BucketType, class Cmp> 
class GenLhashTable
{
public:

  typedef BucketType Bucket;

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

  typedef Key Key_Type;

  typedef Key Item_Type;

protected:

  Hash_Fct hash_fct;

private:

  typedef Dnode<Key>                    BucketList;// Tipo lista cubetas
  typedef typename Dnode<Key>::Iterator BucketItor;// Iterador cubetas
  typedef Dnode<Key>                    Node;      // Sinónimo nodo

  BucketList *                          table;

protected:

  size_t len;                  // Tamaño de la tabla
  float  lower_alpha;
  float  upper_alpha;

private:

  size_t N;                  // Número de elementos de la tabla
  size_t busy_slots_counter; // Cantidad de entradas ocupadas
  bool remove_all_buckets;   // liberar cubetas en destructor
  bool with_resize;

public:

  GenLhashTable(Hash_Fct       __hash_fct, 
                size_t         table_size    = Primes::DefaultPrime,
                const float &  __lower_alpha = hash_default_lower_alpha,
                const float &  __upper_alpha = hash_default_upper_alpha,
                const bool     __remove_all_buckets = true,
                const bool     __with_resize        = true) 
    throw(std::exception, std::bad_alloc) 
    : hash_fct(__hash_fct), table(NULL),
      len(Primes::next_prime(table_size)), 
      lower_alpha(__lower_alpha), upper_alpha(__upper_alpha),
      N(0), busy_slots_counter(0), remove_all_buckets(__remove_all_buckets),
      with_resize(__with_resize)
  { 
    table = new BucketList [len];
  }

  void swap(GenLhashTable & other)
  {
    std::swap(hash_fct, other.hash_fct);
    std::swap(table, other.table);
    std::swap(len, other.len);
    std::swap(N, other.N);
    std::swap(busy_slots_counter, other.busy_slots_counter);
    std::swap(remove_all_buckets, other.remove_all_buckets);
    std::swap(with_resize, other.with_resize);
  }

  void empty()
  {
    for (int i = 0; i < len; ++i)
      for (BucketItor itor(table[i]); itor.has_curr(); /* nada */)
        delete (Bucket*) itor.del();
    busy_slots_counter = N = 0;
  }

private:

  Bucket * search_in_bucket_list(BucketList & list, const Key & key) const
  {
    for (BucketItor it(list); it.has_curr(); it.next())
      {
        Bucket * bucket = static_cast<Bucket*>(it.get_current());
        if (Cmp () (key, bucket->get_key())) 
          return bucket; 
      }

    return NULL;
  }

public:

  Hash_Fct get_hash_fct() const { return hash_fct; }

  void set_hash_fct(Hash_Fct fct)
  {
    hash_fct = fct;
  }

  float current_alpha() const { return 1.0*N/len; }

  Bucket * insert(Bucket * bucket) 
  {
    const size_t i = (*hash_fct)(bucket->get_key()) % len;
    BucketList & list = table[i];

    if (list.is_empty()) // ¿está vacía la lista table[i]?
      ++busy_slots_counter;  // sí ==> actualizar contador ocupación

    if (search_in_bucket_list(list, bucket->get_key()) != NULL)
      return NULL;

    list.append(bucket); // insertar cubeta al final
    ++N;

    if (with_resize and current_alpha() >= upper_alpha)
      resize(next_prime(2*len));

    return bucket;
  }

  Bucket * search(const Key & key) const
  {
    const size_t i = (*hash_fct)(key) % len;
    return search_in_bucket_list(table[i], key);
  }

private:

  // Remove without perform resizing. This is strictly required inside
  // the del() method of Iterator. In addtion dries the code
  Bucket * remove_bucket(Bucket * bucket) 
  {     // guarda próxima colisión
    Bucket * next = static_cast<Bucket*>(bucket->get_next());
    bucket->del(); // eliminar de su lista de colisiones
    if (next->is_empty()) // ¿la lista devino vacía?
      --busy_slots_counter;// sí ==> actualizar contador listas ocupadas

    --N;

    return bucket;
  }

public:

  Bucket * remove(Bucket * bucket) 
  {     // guarda próxima colisión
    remove_bucket(bucket);

    if (with_resize and current_alpha() < lower_alpha)
      resize(next_prime(len/2));

    return bucket;
  }

  size_t resize(size_t new_size) throw(std::exception, std::bad_alloc)
  {
    I(len > 0);

    if (new_size == len or new_size == 0)
      return len; 

    BucketList * new_table = new BucketList [new_size];
    BucketList * old_table = table; // guardar estado  tabla actual
    const size_t old_size  = len;
    table                  = new_table; // tabla vacía con nuevo arreglo
    len                    = new_size;
    busy_slots_counter     = N = 0;

    for (int i = 0; i < old_size; ++i) // reinsertar cubetas
          // recorrer lista colisiones en old_table[i]
      for (BucketItor it(old_table[i]); it.has_curr(); /* Nada */)
        insert((Bucket*) it.del()); // eliminar e insertar en table[]

    delete [] old_table; // liberar memoria antigua tabla

    return len;
  }

  virtual ~GenLhashTable()
  {
    if (remove_all_buckets)
      empty();

    delete [] table; 
  }

  Bucket * search_next(Bucket * bucket) const 
  {
    I(bucket != NULL);

    const size_t i = (*hash_fct)(bucket->get_key()) % len;

    BucketItor itor(table[i]); 
    itor.set(bucket);

    while (true)
      {
        itor.next();

        if (not itor.has_curr()) 
          return NULL;

        Bucket * node = static_cast<Bucket*>(itor.get_curr());

        if (Cmp () (bucket->get_key(), node->get_key())) 
          return node;
      }
  }

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

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

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

  bool is_empty() const { return N == 0; }

  class Iterator
  {
  private:

    int             curr_index; // índice en table
    BucketItor      curr_itor;  // Iterador sobre table[curr_index]
    GenLhashTable * hash_table;

        // Avanza a próxima entrada de table
    void locate_next_available_entry() 
    {
      while (true)
        {
          if (curr_index == hash_table->len)
            throw std::overflow_error ("hash table iterator overflow");

          if (curr_index == hash_table->len - 1)
            {  // quedar en estado overflow
              curr_index = hash_table->len;
              return;
            }

          ++curr_index;

          if (not hash_table->table[curr_index].is_empty())
            {
              BucketItor itor(hash_table->table[curr_index]);
              curr_itor = itor;
              return;
            }
        }
    }

    void locate_next_available_bucket() 
    {
      curr_itor.next();

      if (not curr_itor.has_curr())
        locate_next_available_entry();
    }

    void locate_prev_available_entry() 
    {
      while (true)
        {
          if (curr_index == -1)
            throw std::underflow_error ("hash table iterator underflow");

          if (curr_index == 0)
            { // quedar en estado underflow
              curr_index = -1;
              return;
            }

          --curr_index;

          if (not hash_table->table[curr_index].is_empty())
            {
              BucketItor itor(hash_table->table[curr_index]);
              curr_itor = itor;
              curr_itor.reset_last();
              return;
            }
        }
    }
    
    void locate_prev_available_bucket() 
    {
      curr_itor.prev();

      if (not curr_itor.has_curr())
        locate_prev_available_entry();
    }

public:

    typedef GenLhashTable Set_Type;

    typedef Bucket * Item_Type;

    Iterator(const GenLhashTable & table) 
      : curr_index(-1), hash_table(&const_cast<GenLhashTable&>(table))
    {
      try
        {
          locate_next_available_entry();
        }
      catch (std::overflow_error)
        { /* nothing to do */ }
    }
    
    Iterator() : curr_index(-1), hash_table(NULL)
    {
      // Empty  
    }

    void reset_first()
    {
      curr_index = -1;
      
      locate_next_available_entry();
    }

    void reset_last()
    { 
      curr_index = hash_table->len;

      locate_prev_available_entry();
    }

    bool has_curr() const 
    {
      return curr_index >= 0 and curr_index < hash_table->len;
    }
    
    Bucket * get_curr() 
      throw(std::exception, std::overflow_error, std::underflow_error)
    {
      if (curr_index == -1)
        throw std::underflow_error ("hash table iterator underflow");

      if (curr_index == hash_table->len) 
        throw std::overflow_error ("hash table iterator overflow");

      return static_cast<Bucket*>(curr_itor.get_curr());
    }

    void next() 
    {
      if (curr_index == hash_table->len) 
        throw std::overflow_error ("hash table iterator overflow");

      locate_next_available_bucket();
    }    

    void prev() 
    {
      if (curr_index == -1) 
        throw std::underflow_error ("hash table iterator underflow");

      locate_prev_available_bucket();
    }    

    Bucket * del()
    {
      Bucket * ret_val = get_curr();
      next();
      hash_table->remove_bucket(ret_val);
      return ret_val;
    }
  };

  HASH_STATS();
};

    template <typename Key>
class LhashBucket : public Dnode<Key>
{
public:

  LhashBucket(const LhashBucket & bucket) : Dnode<Key>(bucket) {}

  LhashBucket() {}

  LhashBucket(const Key & key) : Dnode<Key>(key) {}

  Key & get_key() { return this->get_data(); }
};

    template <typename Key>
class LhashBucketVtl : public Dnode<Key>
{
public:
  LhashBucketVtl(const LhashBucketVtl & bucket) : Dnode<Key>(bucket) {}

  LhashBucketVtl() {}

  virtual ~LhashBucketVtl() {}

  LhashBucketVtl(const Key & key) : Dnode<Key>(key) {}

  Key & get_key() { return this->get_data(); }
};

    template <typename Key, class Cmp = Aleph::equal_to<Key> > 
class LhashTable : public GenLhashTable<Key, LhashBucket<Key>, Cmp>
{
public:

  typedef GenLhashTable<Key, LhashBucket<Key>, Cmp> Base;

  using Base::Base;
};

    template <typename Key, class Cmp = Aleph::equal_to<Key> > 
class LhashTableVtl : public GenLhashTable<Key, LhashBucketVtl<Key>, Cmp>
{
 public:

  typedef GenLhashTable<Key, LhashBucketVtl<Key>, Cmp> Base;

  using Base::Base;
};


} // end namespace Aleph

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

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

# endif/* TPL_LHASH_H */