tpl_olhash.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_OLHASH_H
# define TPL_OLHASH_H

# include <primes.H>
# include <ahFunction.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, typename Record, class Cmp = Aleph::equal_to<Key> >
class OLhashTable
{

public:

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


private:

  enum Status { EMPTY, BUSY, DELETED };

  struct Bucket
  {
    Key key;
    Record record;
    char status;

    Bucket() : status(EMPTY) { /* empty */ }
  };

  static Bucket * record_to_bucket(Record * rec)
  {
    Bucket * ret_val = 0;
    long offset = reinterpret_cast<long>(&ret_val->record);
    return reinterpret_cast<Bucket*>(reinterpret_cast<long>(rec) - offset); 
  }
  
  Bucket * table;
  size_t N;
  size_t M;
  HashFctType hash_fct;

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

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

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

public:

  OLhashTable(HashFctType __hash_fct, const size_t & len)
    : table(new Bucket [len + 1]), M(len + 1), N(0), hash_fct(__hash_fct)
  {
    // empty
  }

  ~OLhashTable()
  {
    delete [] table;
  }

  Record * search(const Key & key)
  {
        // Comenzar desde índice hash y sondear linealmente hasta
        // encontrar una cubeta EMPTY
    for (int i = (*hash_fct)(key) % M, c = 0; c < M and table[i].status != EMPTY;
         ++c, ++i)
      if (table[i].status == BUSY) // ¿Hay una clave en la cubeta?
        if (Cmp() (table[i].key, key)) // Comparar la clave
          return &table[i].record;

    return NULL; // No se encuentra la clave
  }
  Record * insert(const Key & key, const Record & record)

    throw(std::exception, std::overflow_error)

  {
    if (N >= M)
      throw std::overflow_error("Hash table is full");

    int i = (*hash_fct)(key) % M; 

        // Sondear linealmente las cubetas disponibles
    while (table[i].status != BUSY) 
      i = (i + 1) % M;

        // i contiene una celda con status DELETED o EMPTY

    table[i].key    = key;
    table[i].record = record;
    table[i].status = BUSY;
    N++;

    return &table[i].record;
  }
  void remove(Record * record)
  {
    Bucket * bucket = record_to_bucket(record);


    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");

    int i = bucket - &table[0]; // índice de cubeta a eliminar; cubeta brecha

    for (int j = (i + 1) % M; true; ++j)
      switch (table[j].status)
        {
        case BUSY:
              // Verificar si cubeta contiene una colisión.
          if (Cmp () ((*hash_fct)(table[j].key), bucket->key))
            {   // contiene colisión ==> mover su contenido hacia table[i]
              table[i].key    = table[j].key;
              table[i].record = table[i].record;
              table[i].status = BUSY;
              table[j].status = DELETED; // esta cubeta deviene DELETED y
                                         // eventualmente candidata a
                                         // marcarse con EMPTY
              i = j; // table[j] deviene cubeta brecha
            }
          break;
        case DELETED: // en este caso, la cubeta i no puede marcarse con
                      // EMPTY porque si no rompe la cadena de sondeo lineal  
            
          i = j; // table[j] deviene cubeta brecha

          break;
        case EMPTY: // en este caso j sería la cubeta que detendría la búsqueda,
                    // pero, puesto que i está más atrás y no interrumpe la
                    // búsqueda, la marcamos con EMPTY y terminamos 
          table[i].status = EMPTY;

          N--;
              
          return; // terminar
        }
  }
  const size_t & resize(const size_t & new_size) 
    throw(std::exception, std::bad_alloc, std::overflow_error)
  {
    if (new_size == M)
      return M;

    if (N >= new_size)
      throw std::overflow_error ("New size is not enough for current"
                                 " number of entries");  
    Bucket * new_table = new Bucket [new_size];  // aparta nuevo arreglo

    Bucket * old_table = table; // respaldar valores de la antigua tabla
    const size_t old_M = M;

    table                   = new_table; // reiniciar tabla a nuevo arreglo
    M                       = new_size;
    N                       = 0;

    for (int i = 0; i < old_M; ++i) // recorrer antigua tabla y reinsertar
      if (old_table[i].status == BUSY)
        insert(old_table[i].key, old_table[i].record);

    delete [] old_table;

    return M;
  }

  const size_t size() const { return N; }

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

};

}
# endif // TPL_OLHASH_H

---