tpl_olhash.H

00001 
00002 /*
00003   This file is part of Aleph system
00004 
00005   Copyright (c) 2002, 2003, 2004, 2005, 2006
00006   UNIVERSITY LOS ANDES (ULA) Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA  
00007 
00008   - Center of Studies in Microelectronics & Distributed Systems (CEMISID) 
00009   - ULA Computer Science Department
00010   - FUNDACITE Mérida - Ministerio de Ciencia y Tecnología
00011 
00012   PERMISSION TO USE, COPY, MODIFY AND DISTRIBUTE THIS SOFTWARE AND ITS
00013   DOCUMENTATION IS HEREBY GRANTED, PROVIDED THAT BOTH THE COPYRIGHT
00014   NOTICE AND THIS PERMISSION NOTICE APPEAR IN ALL COPIES OF THE
00015   SOFTWARE, DERIVATIVE WORKS OR MODIFIED VERSIONS, AND ANY PORTIONS
00016   THEREOF, AND THAT BOTH NOTICES APPEAR IN SUPPORTING DOCUMENTATION.
00017 
00018   Aleph is distributed in the hope that it will be useful, but WITHOUT
00019   ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
00020   or FITNESS FOR A PARTICULAR PURPOSE.
00021 
00022   UNIVERSIDAD DE LOS ANDES requests users of this software to return to 
00023 
00024   Leandro Leon
00025   CEMISID 
00026   Ed La Hechicera 
00027   3er piso, ala sur
00028   Facultad de Ingenieria 
00029   Universidad de Los Andes 
00030   Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA    or
00031 
00032   lrleon@ula.ve
00033 
00034   any improvements or extensions that they make and grant Universidad 
00035   de Los Andes (ULA) the rights to redistribute these changes. 
00036 
00037   Aleph is (or was) granted by: 
00038   - Consejo de Desarrollo Cientifico, Humanistico, Tecnico de la ULA 
00039     (CDCHT)
00040   - Fundacite Mérida
00041 */
00042 
00043 
00044 # ifndef TPL_OLHASH_H
00045 # define TPL_OLHASH_H
00046 
00047 # include <primes.H>
00048 # include <ahFunction.H>
00049 
00050 using namespace Primes;
00051 
00052 using namespace Aleph;
00053 
00054 # ifdef N
00055 # define NBACKUP N
00056 # undef N
00057 # endif
00058 
00059 # ifdef M
00060 # define MBACKUP M
00061 # undef M
00062 # endif
00063 
00064 namespace Aleph {
00065 
00082   template <typename Key, typename Record, class Cmp = Aleph::equal_to<Key> >
00083 class OLhashTable
00084 {
00085 
00086 public:
00087 
00089   typedef size_t (*HashFctType)(const Key &);
00090 
00091 
00092 private:
00093 
00094   enum Status { EMPTY, BUSY, DELETED };
00095 
00096   struct Bucket
00097   {
00098     Key key;
00099     Record record;
00100     char status;
00101 
00102     Bucket() : status(EMPTY) { /* empty */ }
00103   };
00104 
00105   static Bucket * record_to_bucket(Record * rec)
00106   {
00107     Bucket * ret_val = 0;
00108     long offset = reinterpret_cast<long>(&ret_val->record);
00109     return reinterpret_cast<Bucket*>(reinterpret_cast<long>(rec) - offset); 
00110   }
00111   
00112   Bucket * table;
00113   size_t N;
00114   size_t M;
00115   HashFctType hash_fct;
00116 
00117   bool is_valid_bucket(Bucket * bucket) const
00118   {
00119     if (bucket < &table[0] or bucket >= &table[M])
00120       return false;
00121 
00122     int offset_with_base = (reinterpret_cast<char*>(bucket) -
00123                             reinterpret_cast<char*>(&table[0]));
00124 
00125     return offset_with_base % sizeof(*bucket) == 0;
00126   }
00127 
00128 public:
00129 
00132   OLhashTable(HashFctType __hash_fct, const size_t & len)
00133     : table(new Bucket [len + 1]), M(len + 1), N(0), hash_fct(__hash_fct)
00134   {
00135     // empty
00136   }
00137 
00139   ~OLhashTable()
00140   {
00141     delete [] table;
00142   }
00143 
00146   Record * search(const Key & key)
00147   {
00148         // Comenzar desde índice hash y sondear linealmente hasta
00149         // encontrar una cubeta EMPTY
00150     for (int i = (*hash_fct)(key) % M, c = 0; c < M and table[i].status != EMPTY;
00151          ++c, ++i)
00152       if (table[i].status == BUSY) // ¿Hay una clave en la cubeta?
00153         if (Cmp() (table[i].key, key)) // Comparar la clave
00154           return &table[i].record;
00155 
00156     return NULL; // No se encuentra la clave
00157   }
00160   Record * insert(const Key & key, const Record & record)
00161 
00162     throw(std::exception, std::overflow_error)
00163 
00164   {
00165     if (N >= M)
00166       throw std::overflow_error("Hash table is full");
00167 
00168     int i = (*hash_fct)(key) % M; 
00169 
00170         // Sondear linealmente las cubetas disponibles
00171     while (table[i].status != BUSY) 
00172       i = (i + 1) % M;
00173 
00174         // i contiene una celda con status DELETED o EMPTY
00175 
00176     table[i].key    = key;
00177     table[i].record = record;
00178     table[i].status = BUSY;
00179     N++;
00180 
00181     return &table[i].record;
00182   }
00188   void remove(Record * record)
00189   {
00190     Bucket * bucket = record_to_bucket(record);
00191 
00192 
00193     if (not is_valid_bucket(bucket))
00194       throw std::invalid_argument("record address is not inside table's range");
00195 
00196     if (bucket->status != BUSY)
00197       throw std::domain_error("Bucket containing record is not busy");
00198 
00199     int i = bucket - &table[0]; // índice de cubeta a eliminar; cubeta brecha
00200 
00201     for (int j = (i + 1) % M; true; ++j)
00202       switch (table[j].status)
00203         {
00204         case BUSY:
00205               // Verificar si cubeta contiene una colisión.
00206           if (Cmp () ((*hash_fct)(table[j].key), bucket->key))
00207             {   // contiene colisión ==> mover su contenido hacia table[i]
00208               table[i].key    = table[j].key;
00209               table[i].record = table[i].record;
00210               table[i].status = BUSY;
00211               table[j].status = DELETED; // esta cubeta deviene DELETED y
00212                                          // eventualmente candidata a
00213                                          // marcarse con EMPTY
00214               i = j; // table[j] deviene cubeta brecha
00215             }
00216           break;
00217         case DELETED: // en este caso, la cubeta i no puede marcarse con
00218                       // EMPTY porque si no rompe la cadena de sondeo lineal  
00219             
00220           i = j; // table[j] deviene cubeta brecha
00221 
00222           break;
00223         case EMPTY: // en este caso j sería la cubeta que detendría la búsqueda,
00224                     // pero, puesto que i está más atrás y no interrumpe la
00225                     // búsqueda, la marcamos con EMPTY y terminamos 
00226           table[i].status = EMPTY;
00227 
00228           N--;
00229               
00230           return; // terminar
00231         }
00232   }
00237   const size_t & resize(const size_t & new_size) 
00238     throw(std::exception, std::bad_alloc, std::overflow_error)
00239   {
00240     if (new_size == M)
00241       return M;
00242 
00243     if (N >= new_size)
00244       throw std::overflow_error ("New size is not enough for current"
00245                                  " number of entries");  
00246     Bucket * new_table = new Bucket [new_size];  // aparta nuevo arreglo
00247 
00248     Bucket * old_table = table; // respaldar valores de la antigua tabla
00249     const size_t old_M = M;
00250 
00251     table                   = new_table; // reiniciar tabla a nuevo arreglo
00252     M                       = new_size;
00253     N                       = 0;
00254 
00255     for (int i = 0; i < old_M; ++i) // recorrer antigua tabla y reinsertar
00256       if (old_table[i].status == BUSY)
00257         insert(old_table[i].key, old_table[i].record);
00258 
00259     delete [] old_table;
00260 
00261     return M;
00262   }
00263 
00265   const size_t size() const { return N; }
00266 
00268   const size_t & capacity() const { return M; }
00269 
00270 };
00271 
00272 }
00273 # endif // TPL_OLHASH_H
00274 

Leandro R. León