tpl_olhash.H

# ifndef TPL_OLHASH_H
# define TPL_OLHASH_H

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

using namespace Primes;

using namespace Aleph;

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

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

namespace Aleph {

  template <typename Key, class Cmp = Aleph::equal_to<Key>>
class OLhashTable
{
public:

  typedef Key Key_Type;

  typedef Key Item_Type;

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

  enum Status { EMPTY, BUSY, DELETED };

  struct Bucket
  {
    Key key;
    char status;

    Bucket() : status(EMPTY) {}
    void reset() { status = EMPTY; }
  };

  static Bucket * key_to_bucket(Key * rec)
  {
    Bucket * ret_val = 0;
    long offset = (long) &ret_val->key;
    return (Bucket*) ((long) rec - offset); 
  }
  
  Bucket *    table;
  size_t      N;

protected:

  size_t      len;
  float       lower_alpha;
  float       upper_alpha;

private:

  Hash_Fct hash_fct;
  bool     with_resize;

  bool is_valid_bucket(Bucket * bucket) const
  {
    if (bucket < &table[0] or bucket >= &table[len]) 
      return false;

    int offset_with_base = (char*) bucket - (char*) &table[0];

    return offset_with_base % sizeof(*bucket) == 0;
  }

public:

  OLhashTable(Hash_Fct      __hash_fct     = Aleph::dft_hash_fct<Key>, 
              Hash_Fct      null_hash_fct  = NULL, /* Ficticius compatibily */
              size_t         __len         = Primes::DefaultPrime,
              const float &  __lower_alpha = hash_default_lower_alpha,
              const float &  __upper_alpha = hash_default_upper_alpha,
              const bool     __with_resize = true)
    : table(NULL), N(0), len(Primes::next_prime(__len)), 
      lower_alpha(__lower_alpha), upper_alpha(__upper_alpha),
      hash_fct(__hash_fct), with_resize(__with_resize)
  {
    table = new Bucket [len];
  }

  ~OLhashTable()
  {
    if (table != NULL)
      delete [] table;
  }

  void swap(OLhashTable & other)
  {
    std::swap(table, other.table);
    std::swap(N, other.N);
    std::swap(len, other.len);
    std::swap(hash_fct, other.hash_fct);
    std::swap(lower_alpha, other.lower_alpha);
    std::swap(upper_alpha, other.upper_alpha);
    std::swap(with_resize, other.with_resize);
  }

  OLhashTable(const OLhashTable & other)
    : OLhashTable(other.hash_fct, NULL, other.len,
                  other.lower_alpha, other.upper_alpha, other.with_resize)
  {
    copy_from_table(other);
  }

  OLhashTable(OLhashTable && other)
    : OLhashTable(other.hash_fct, NULL, other.len,
                  other.lower_alpha, other.upper_alpha, other.with_resize)
  {
    swap(other);
  }

  OLhashTable & operator = (const OLhashTable & other)
  {
    if (this == &other)
      return *this;

    if (len > other.N)
      clean_table();
    else
      {
        Bucket * new_table = new Bucket [other.len];
        delete [] table;
        table = new_table;
        N = 0;
        len = other.len;
        hash_fct = other.hash_fct;
        lower_alpha = other.lower_alpha;
        upper_alpha = other.upper_alpha;
      }

    copy_from_table(other);

    return *this;
  }

  OLhashTable & operator = (OLhashTable && other)
  {
    swap(other);
    return *this;
  }

  Key * search(const Key & key) const
  {   
    long i = (*hash_fct)(key) % len, c = 0;

    while (c < len and table[i].status != EMPTY)
      {
        if (table[i].status == BUSY and Cmp () (table[i].key, key))
          return &table[i].key;

        ++c;
        if (++i == len)
          i = 0;
      }

    return NULL; // No se encuentra la clave
  }

private:

  Bucket * allocate_bucket(const Key & key)
  {
    if (N >= len)
      throw std::overflow_error("Hash table is full");

    size_t i = (*hash_fct)(key) % len; 

    while (table[i].status == BUSY) // find a slot that is not busy
      {
        if (Cmp () (key, table[i].key))
          return NULL;

        if (++i == len)
          i = 0;
      }

    Bucket * bucket = &table[i];

        // i contiene celda con DELETED o EMPTY ==> ocuparla
    bucket->status = BUSY;
    N++;

    return bucket;
  }

  void deallocate_bucket(Bucket * bucket)
  {
    if (not is_valid_bucket(bucket))
      throw std::invalid_argument("record address is not inside table's range");

    if (bucket->status != BUSY)
      throw std::domain_error("Bucket containing record is not busy");

    --N;
    int i = bucket - &table[0]; // índice de brecha
    table[i].status = DELETED;
  }

  public:

  void remove(const Key & key)
  {
    Key * key_ptr = search(key);
    if (key_ptr == NULL)
      throw std::domain_error("Key not in hash table");

    remove(key_ptr);
  }

  OHASH_COMMON(OLhashTable);

  Generic_Traverse(Key);
  Functional_Methods(Key)
  Equal_To_Method(OLhashTable);

  Stats stats() const
  {                                                                     
    DynArray<size_t> lens;                                              
    size_t num_busy = 0, num_deleted = 0, num_empty = 0;                        
    size_t max_len = std::numeric_limits<size_t>::min();                        
    for (int i = 0; i < len; ++i)                                       
      switch (table[i].status)                                          
        {                                                               
        case BUSY:                                                      
          {                                                             
            ++num_busy;                                                 
            const Key & key = table[i].key;                             
            long i = (*hash_fct)(key) % len;                            
            size_t count = 1;                                           
                                                                        
            while (true)                                                        
              {                                                         
                if (table[i].status == BUSY and Cmp () (table[i].key, key)) 
                  break;                                                        
                ++count;                                                        
                if (++i == len)                                         
                  i = 0;                                                        
              }                                                         
                                                                        
            max_len = std::max(max_len, count);                         
            update_stat_len(lens, count);                               
            break;                                                      
          }                                                             
        case EMPTY:                                                     
          ++num_empty;                                                  
          update_stat_len(lens, 0);                                     
          break;                                                                
        case DELETED:                                                   
          ++num_deleted;                                                        
          break;                                                                
        }                                                               
                                                                        
    float avg = 0, sum = 0;                                             
    for (int i = 0; i < lens.size(); ++i)                               
      {                                                                 
        avg += lens(i)*i;                                               
        sum += lens(i);                                                 
      }                                                                 
                                                                        
    avg /= sum;                                                         
    float var = 0;                                                      
    for (int i = 0; i < lens.size(); ++i)                               
      {                                                                 
        float s = i - avg;                                              
        var += lens(i)*s*s;                                             
      }                                                                 
    var /= sum;                                                         
                                                                        
    Stats stats;                                                                
    stats.num_busy = num_busy;                                          
    stats.num_deleted = num_deleted;                                    
    stats.num_empty = num_empty;                                                
    std::swap(lens, stats.lens);                                                
    stats.avg = avg;                                                    
    stats.var = var;                                                    
    stats.max_len = max_len;                                            
                                                                        
    return stats;                                               
  }
};
                                                                        
}
# endif // TPL_OLHASH_H