00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
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) { }
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
00136 }
00137
00139 ~OLhashTable()
00140 {
00141 delete [] table;
00142 }
00143
00146 Record * search(const Key & key)
00147 {
00148
00149
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)
00153 if (Cmp() (table[i].key, key))
00154 return &table[i].record;
00155
00156 return NULL;
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
00171 while (table[i].status != BUSY)
00172 i = (i + 1) % M;
00173
00174
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];
00200
00201 for (int j = (i + 1) % M; true; ++j)
00202 switch (table[j].status)
00203 {
00204 case BUSY:
00205
00206 if (Cmp () ((*hash_fct)(table[j].key), bucket->key))
00207 {
00208 table[i].key = table[j].key;
00209 table[i].record = table[i].record;
00210 table[i].status = BUSY;
00211 table[j].status = DELETED;
00212
00213
00214 i = j;
00215 }
00216 break;
00217 case DELETED:
00218
00219
00220 i = j;
00221
00222 break;
00223 case EMPTY:
00224
00225
00226 table[i].status = EMPTY;
00227
00228 N--;
00229
00230 return;
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];
00247
00248 Bucket * old_table = table;
00249 const size_t old_M = M;
00250
00251 table = new_table;
00252 M = new_size;
00253 N = 0;
00254
00255 for (int i = 0; i < old_M; ++i)
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