tpl_odhash.H

# ifndef TPL_ODHASH_H
# define TPL_ODHASH_H

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

using namespace Aleph;

namespace Aleph {

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

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


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

  typedef Key Key_Type;

  typedef Key Item_Type;

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

  enum Status { EMPTY, BUSY, DELETED };

  enum Probe { NO_PROBED, FIRST_PROBE, SECOND_PROBE, LINEAR_PROBE };

  struct Bucket
  {
    Key      key;               // clave
    unsigned status     : 4;    // status EMPTY, DELETED o BUSY
    unsigned probe_type : 4;    // FIRST_PROBE SECOND_PROBE LINEAR_PROBE 
    unsigned int probe_counter; // contador de sondeos

    Bucket() : status(EMPTY), probe_type(NO_PROBED), probe_counter(0)
    { /* empty */ }

    void reset() // put all as when constructed
    {
      status = EMPTY;
      probe_type = NO_PROBED;
      probe_counter = 0;
    }
  };

  Bucket * table           = NULL; // arreglo de cubetas
  Hash_Fct hash_fct        = NULL; // primera función hash
  Hash_Fct second_hash_fct = NULL; // segunda función hash

protected:

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

private:

  size_t   N;                       // número de cubetas ocupadas
  bool     with_resize;

  Bucket * allocate_bucket(Bucket & bucket, unsigned char probe_type)
  {
    I(bucket.status != BUSY);

    ++N;
    bucket.status     = BUSY;
    bucket.probe_type = probe_type;
    bucket.probe_counter++;

    return &bucket;
  }

  void decrease_probe_counter(Bucket * bucket)
  {
    I(bucket->status == BUSY or bucket->status == DELETED);

    bucket->probe_counter--;
    if (bucket->probe_counter == 0) // <marcar EMPTY sobre la cubeta?
        bucket->status = EMPTY;
  }

  void deallocate_bucket(Bucket * bucket)
  {
    I(bucket->status == BUSY);

    bucket->status = DELETED;
    const Key & key = bucket->key;

    const size_t i_fst = (*hash_fct)(key) % len;
    if (&table[i_fst] == bucket)
      {
        I(Cmp () (table[i_fst].key, key)); 
        I(table[i_fst].probe_type == FIRST_PROBE);
        ;
      }
    else
      {
        const size_t i_snd = (*second_hash_fct)(key) % len;
        if (&table[i_snd] == bucket)
          {
            I(Cmp () (table[i_snd].key, key));
            I(table[i_snd].probe_type == SECOND_PROBE);
            decrease_probe_counter(&table[i_fst]);
            ;
          }
        else
          {
            decrease_probe_counter(&table[i_fst]);
            decrease_probe_counter(&table[i_snd]);
            size_t i = i_snd;
            for (index_forward(i); &table[i] != bucket; index_forward(i))
              {
                I(table[i].status != EMPTY);
                decrease_probe_counter(&table[i]);
              }
            I(Cmp () (table[i].key, key));
            I(table[i].probe_type == LINEAR_PROBE);
          }
      }
    
    decrease_probe_counter(bucket);
    --N;
  }

  size_t index_forward(size_t & i) const
  {
    I(i < len);
    if (++i == len)
      i = 0;
    return i;
  }

  size_t index_backward(size_t & i) const
  {
    I(i < len);
    if (i-- == 0)
      i = len - 1;
    return i;
  }

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

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

    const int offset_with_base = (char*) bucket - (char*) &table[0];
    return offset_with_base % sizeof(*bucket) == 0;
  }

  size_t bucket_to_index(Bucket * bucket) 
  {
    I(is_valid_bucket(bucket));
    return bucket - &table[0];
  }

public:

  void swap(ODhashTable & other)
  {
    std::swap(table, other.table);
    std::swap(hash_fct, other.hash_fct);
    std::swap(second_hash_fct, other.second_hash_fct);
    std::swap(N, other.N);
    std::swap(len, other.len);
  }

  ODhashTable(Hash_Fct __first_hash_fct    = Aleph::dft_hash_fct<Key>, 
              Hash_Fct __second_hash_fct   = Aleph::snd_hash_fct<Key>, 
              const 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), hash_fct(__first_hash_fct), 
      second_hash_fct(__second_hash_fct), len(Primes::next_prime(__len)), 
      lower_alpha(__lower_alpha), upper_alpha(__upper_alpha),
      N(0), with_resize(__with_resize)
  {
    table = new Bucket[len];
  }

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

  ODhashTable(const ODhashTable & other)
    : ODhashTable(other.hash_fct, other.second_hash_fct, other.len, 
                  other.lower_alpha, other.upper_alpha, other.with_resize)
  {
    I(table != NULL);
    copy_from_table(other);
  }

  ODhashTable(ODhashTable && other)
    : ODhashTable(other.hash_fct, other.second_hash_fct, other.len, 
                  other.lower_alpha, other.upper_alpha, other.with_resize)
  {
    I(table != NULL);
    swap(other);
  }

  ODhashTable & operator = (const ODhashTable & 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;
        second_hash_fct = other.second_hash_fct;
        lower_alpha     = other.lower_alpha;
        upper_alpha     = other.upper_alpha;
        with_resize     = other.with_resize;
      }

    copy_from_table(other);

    return *this;
  }

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

  OHASH_COMMON(ODhashTable);

  Generic_Traverse(Key);
  Functional_Methods(Key);
  Equal_To_Method(ODhashTable);

  Key * search(const Key & key) const
  {
    const size_t i_fst = (*hash_fct)(key) % len; // 1er sondeo (1ra fun hash)
    if (table[i_fst].status == EMPTY) 
      return NULL;

    if (table[i_fst].status == BUSY and Cmp() (table[i_fst].key, key))
      {
        I(table[i_fst].probe_type == FIRST_PROBE);
        I(table[i_fst].probe_counter > 0);
        return &table[i_fst].key;
      }

    const size_t i_snd = (*second_hash_fct)(key) % len; // 2do sondeo

    if (table[i_snd].status == EMPTY)
      return NULL;

    if (table[i_snd].status == BUSY and Cmp() (table[i_snd].key, key)) 
      {
        I(table[i_snd].probe_type == SECOND_PROBE);
        I(table[i_snd].probe_counter > 0);
        return &table[i_snd].key;
      }

    size_t i = i_snd; 
        // sondeo lineal a partir de índice de 2da función hash
    for (int count = 0; count < len; ++count)
      {
        index_forward(i);
        switch (table[i].status)
          {
          case EMPTY:
            I(table[i].probe_counter == 0);
            return NULL;
          case BUSY:
            I(table[i].probe_counter > 0);
            if (Cmp() (table[i].key, key))
              {
                I(table[i].probe_type == LINEAR_PROBE);
                return &table[i].key;
              }
            break;
          case DELETED:
            I(table[i].probe_counter > 0);
            break;
          default: ERROR("ODhashTable search: inconsistent bucket status");
          }
      }
   
    return NULL; 
  }

  Hash_Fct get_second_hash_fct() const { return second_hash_fct; }

  void set_second_hash_fct(Hash_Fct fct)
  {
    second_hash_fct = fct;
  }

private:

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

    const size_t i_fst = (*hash_fct)(key) % len; // sondeo con 1ra función hash
    if (table[i_fst].status != BUSY) // ¿cubeta disponible?
      return allocate_bucket(table[i_fst], FIRST_PROBE);

    if (Cmp () (table[i_fst].key, key)) // test if key is alredy present
      return NULL;

    const size_t i_snd = (*second_hash_fct)(key) % len; // 2do hash
    if (table[i_snd].status != BUSY) // ¿cubeta disponible?
      {
        table[i_fst].probe_counter++;
        return allocate_bucket(table[i_snd], SECOND_PROBE);
      }

    if (Cmp () (table[i_snd].key, key)) // test if key is alredy present
      return NULL;

    size_t i = i_snd;
    for (int c = 0; c < len; ++c)
      {  
        index_forward(i);
        switch (table[i].status)
        {
        case BUSY: 
          if (Cmp() (table[i].key, key))
            { // duplicated key ==> rollback previous probe_counter increases
              for (int k = 0; k < c; ++k)
                {
                  index_backward(i);
                  table[i].probe_counter--;
                }
              return NULL;
            }
          break;
        case DELETED: 
        case EMPTY:
          table[i_fst].probe_counter++;
          table[i_snd].probe_counter++;
          return allocate_bucket(table[i], LINEAR_PROBE); 
        default: ERROR("ODhashTable: Invalid bucket status"); break;
        }
        table[i].probe_counter++;
      }

    return NULL;
  }

  void remove_bucket(Bucket * bucket)
  {
    if (not is_valid_bucket(bucket))
      throw std::invalid_argument("key pty does not belong to hash table");

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

    deallocate_bucket(bucket);
  }

  // returns true if the bucket contains the key
  bool process_entry_for_remove(Bucket * bucket, const Key & key)
  {
    switch (bucket->status)
      {
      case EMPTY:
        throw std::domain_error("Key not in hash table");
      case BUSY:
        if (Cmp () (bucket->key, key))
          {
            bucket->status = DELETED;
            decrease_probe_counter(bucket);
            return true;
          }
      case DELETED:
        decrease_probe_counter(bucket);
        break;
      default: ERROR("Inconsistent bucket status");
      }
    return false;
  }

public:

  void remove(const Key & key)
  {
    --N;
    try
      {
        const size_t i_fst = (*hash_fct)(key) % len;
        if (process_entry_for_remove(&table[i_fst], key))
          return;
    
        const size_t i_snd = (*second_hash_fct)(key) % len;
        if (process_entry_for_remove(&table[i_snd], key))
          return;

        size_t i = i_snd;
        for (int c = 0; i < len; ++c)
          {
            index_forward(i);
            if (process_entry_for_remove(&table[i], key))
              return;
          }
      }
    catch (...)
      {
        ++N;
        rehash(); // in order to leave the table in a consistent state
        throw;
      }
  }
  
  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;                             
            size_t count = 1;
            const size_t i_fst = (*hash_fct)(key) % len;
            if (Cmp () (table[i_fst].key, key))
                {
                  I(table[i_fst].probe_type == FIRST_PROBE);
                  I(table[i_fst].probe_counter > 0);
                  ;
                }
            else 
              {
                ++count;
                size_t i_snd = (*second_hash_fct)(key) % len;
                if (Cmp () (table[i_snd].key, key))
                {
                  I(table[i_snd].probe_type == SECOND_PROBE);
                  I(table[i_snd].probe_counter > 0);
                  ;
                }
                else
                  {
                    for (size_t i = index_forward(i_snd); true; index_forward(i))
                      {
                        if (table[i].status == BUSY and 
                            Cmp () (table[i].key, key))
                          break;
                        ++count;
                      }
                  }
              }
            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;                                               
  }
};




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

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

# undef EMPTY
# undef BUSY
# undef DELETED
# undef NO_PROBED    
# undef FIRST_PROBE  
# undef SECOND_PROBE 
# undef LINEAR_PROBE 

} // end namespace Aleph

# endif // TPL_ODHASH_H