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 #ifndef StaticHashTable_C
00027 #define StaticHashTable_C
00028
00029 #include "StaticHashTable.H"
00030 #include <OpenFOAM/List.H>
00031 #include <OpenFOAM/IOstreams.H>
00032
00033
00034
00035 template<class T, class Key, class Hash>
00036 Foam::label Foam::StaticHashTable<T, Key, Hash>::canonicalSize(const label size)
00037 {
00038 if (size < 1)
00039 {
00040 return 0;
00041 }
00042
00043
00044 unsigned int goodSize = size;
00045
00046 if (goodSize & (goodSize - 1))
00047 {
00048
00049 goodSize = 1;
00050 while (goodSize < unsigned(size))
00051 {
00052 goodSize <<= 1;
00053 }
00054 }
00055
00056 return goodSize;
00057 }
00058
00059
00060
00061
00062
00063 template<class T, class Key, class Hash>
00064 Foam::StaticHashTable<T, Key, Hash>::StaticHashTable(const label size)
00065 :
00066 StaticHashTableName(),
00067 keys_(canonicalSize(size)),
00068 objects_(keys_.size()),
00069 nElmts_(0),
00070 endIter_(*this, keys_.size(), 0),
00071 endConstIter_(*this, keys_.size(), 0)
00072 {
00073 if (size < 1)
00074 {
00075 FatalErrorIn
00076 (
00077 "StaticHashTable<T, Key, Hash>::StaticHashTable(const label size)"
00078 ) << "Illegal size " << size << " for StaticHashTable."
00079 << " Minimum size is 1" << abort(FatalError);
00080 }
00081 }
00082
00083
00084
00085 template<class T, class Key, class Hash>
00086 Foam::StaticHashTable<T, Key, Hash>::StaticHashTable
00087 (
00088 const StaticHashTable<T, Key, Hash>& ht
00089 )
00090 :
00091 StaticHashTableName(),
00092 keys_(ht.keys_),
00093 objects_(ht.objects_),
00094 nElmts_(ht.nElmts_),
00095 endIter_(*this, keys_.size(), 0),
00096 endConstIter_(*this, keys_.size(), 0)
00097 {}
00098
00099
00100
00101 template<class T, class Key, class Hash>
00102 Foam::StaticHashTable<T, Key, Hash>::StaticHashTable
00103 (
00104 const Xfer< StaticHashTable<T, Key, Hash> >& ht
00105 )
00106 :
00107 StaticHashTableName(),
00108 keys_(0),
00109 objects_(0),
00110 nElmts_(0),
00111 endIter_(*this, 0, 0),
00112 endConstIter_(*this, 0, 0)
00113 {
00114 transfer(ht());
00115 }
00116
00117
00118
00119
00120 template<class T, class Key, class Hash>
00121 Foam::StaticHashTable<T, Key, Hash>::~StaticHashTable()
00122 {}
00123
00124
00125
00126
00127 template<class T, class Key, class Hash>
00128 bool Foam::StaticHashTable<T, Key, Hash>::found(const Key& key) const
00129 {
00130 if (nElmts_)
00131 {
00132 const label hashIdx = hashKeyIndex(key);
00133 const List<Key>& localKeys = keys_[hashIdx];
00134
00135 forAll(localKeys, elemIdx)
00136 {
00137 if (key == localKeys[elemIdx])
00138 {
00139 return true;
00140 }
00141 }
00142 }
00143
00144 # ifdef FULLDEBUG
00145 if (debug)
00146 {
00147 Info<< "StaticHashTable<T, Key, Hash>::found(const Key&) : "
00148 << "Entry " << key << " not found in hash table\n";
00149 }
00150 # endif
00151
00152 return false;
00153 }
00154
00155
00156 template<class T, class Key, class Hash>
00157 typename Foam::StaticHashTable<T, Key, Hash>::iterator
00158 Foam::StaticHashTable<T, Key, Hash>::find
00159 (
00160 const Key& key
00161 )
00162 {
00163 if (nElmts_)
00164 {
00165 const label hashIdx = hashKeyIndex(key);
00166 const List<Key>& localKeys = keys_[hashIdx];
00167
00168 forAll(localKeys, elemIdx)
00169 {
00170 if (key == localKeys[elemIdx])
00171 {
00172 return iterator(*this, hashIdx, elemIdx);
00173 }
00174 }
00175 }
00176
00177 # ifdef FULLDEBUG
00178 if (debug)
00179 {
00180 Info<< "StaticHashTable<T, Key, Hash>::find(const Key&) : "
00181 << "Entry " << key << " not found in hash table\n";
00182 }
00183 # endif
00184
00185 return end();
00186 }
00187
00188
00189 template<class T, class Key, class Hash>
00190 typename Foam::StaticHashTable<T, Key, Hash>::const_iterator
00191 Foam::StaticHashTable<T, Key, Hash>::find
00192 (
00193 const Key& key
00194 ) const
00195 {
00196 if (nElmts_)
00197 {
00198 const label hashIdx = hashKeyIndex(key);
00199 const List<Key>& localKeys = keys_[hashIdx];
00200
00201 forAll(localKeys, elemIdx)
00202 {
00203 if (key == localKeys[elemIdx])
00204 {
00205 return const_iterator(*this, hashIdx, elemIdx);
00206 }
00207 }
00208 }
00209
00210 # ifdef FULLDEBUG
00211 if (debug)
00212 {
00213 Info<< "StaticHashTable<T, Key, Hash>::find(const Key&) const : "
00214 << "Entry " << key << " not found in hash table\n";
00215 }
00216 # endif
00217
00218 return cend();
00219 }
00220
00221
00222
00223 template<class T, class Key, class Hash>
00224 Foam::List<Key> Foam::StaticHashTable<T, Key, Hash>::toc() const
00225 {
00226 List<Key> tofc(nElmts_);
00227 label i = 0;
00228
00229 for (const_iterator iter = cbegin(); iter != cend(); ++iter)
00230 {
00231 tofc[i++] = iter.key();
00232 }
00233
00234 return tofc;
00235 }
00236
00237
00238 template<class T, class Key, class Hash>
00239 bool Foam::StaticHashTable<T, Key, Hash>::set
00240 (
00241 const Key& key,
00242 const T& newEntry,
00243 const bool protect
00244 )
00245 {
00246 const label hashIdx = hashKeyIndex(key);
00247 List<Key>& localKeys = keys_[hashIdx];
00248
00249 label existing = localKeys.size();
00250 forAll(localKeys, elemIdx)
00251 {
00252 if (key == localKeys[elemIdx])
00253 {
00254 existing = elemIdx;
00255 break;
00256 }
00257 }
00258
00259 if (existing == localKeys.size())
00260 {
00261
00262 List<T>& localObjects = objects_[hashIdx];
00263
00264 localKeys.setSize(existing+1);
00265 localObjects.setSize(existing+1);
00266
00267 localKeys[existing] = key;
00268 localObjects[existing] = newEntry;
00269
00270 nElmts_++;
00271 }
00272 else if (protect)
00273 {
00274
00275
00276 # ifdef FULLDEBUG
00277 if (debug)
00278 {
00279 Info<< "StaticHashTable<T, Key, Hash>::set"
00280 "(const Key& key, T newEntry, true) : "
00281 "Cannot insert " << key << " already in hash table\n";
00282 }
00283 # endif
00284 return false;
00285 }
00286 else
00287 {
00288
00289
00290 objects_[hashIdx][existing] = newEntry;
00291 }
00292
00293 return true;
00294 }
00295
00296
00297 template<class T, class Key, class Hash>
00298 bool Foam::StaticHashTable<T, Key, Hash>::erase(const iterator& cit)
00299 {
00300 if (cit != end())
00301 {
00302 List<Key>& localKeys = keys_[cit.hashIndex_];
00303 List<T>& localObjects = objects_[cit.hashIndex_];
00304
00305
00306 for (label i = cit.elemIndex_+1; i < localKeys.size(); i++)
00307 {
00308 localKeys[i-1] = localKeys[i];
00309 localObjects[i-1] = localObjects[i];
00310 }
00311 localKeys.setSize(localKeys.size()-1);
00312 localObjects.setSize(localObjects.size()-1);
00313
00314
00315 iterator& it = const_cast<iterator&>(cit);
00316
00317 it.elemIndex_--;
00318 if (it.elemIndex_ < 0)
00319 {
00320
00321
00322
00323 while (--it.hashIndex_ >= 0 && !objects_[it.hashIndex_].size())
00324 {}
00325
00326 if (it.hashIndex_ >= 0)
00327 {
00328
00329 it.elemIndex_ = objects_[it.hashIndex_].size() - 1;
00330 }
00331 else
00332 {
00333
00334
00335
00336 it.hashIndex_ = -1;
00337 it.elemIndex_ = 0;
00338 }
00339 }
00340
00341 nElmts_--;
00342
00343 # ifdef FULLDEBUG
00344 if (debug)
00345 {
00346 Info<< "StaticHashTable<T, Key, Hash>::erase(iterator&) : "
00347 << "hashedEntry removed.\n";
00348 }
00349 # endif
00350
00351 return true;
00352 }
00353 else
00354 {
00355 # ifdef FULLDEBUG
00356 if (debug)
00357 {
00358 Info<< "StaticHashTable<T, Key, Hash>::erase(iterator&) : "
00359 << "cannot remove hashedEntry from hash table\n";
00360 }
00361 # endif
00362
00363 return false;
00364 }
00365 }
00366
00367
00368 template<class T, class Key, class Hash>
00369 bool Foam::StaticHashTable<T, Key, Hash>::erase(const Key& key)
00370 {
00371 iterator it = find(key);
00372
00373 if (it != end())
00374 {
00375 return erase(it);
00376 }
00377 else
00378 {
00379 return false;
00380 }
00381 }
00382
00383
00384 template<class T, class Key, class Hash>
00385 Foam::label Foam::StaticHashTable<T, Key, Hash>::erase
00386 (
00387 const StaticHashTable<T, Key, Hash>& rhs
00388 )
00389 {
00390 label count = 0;
00391
00392
00393
00394 for (iterator iter = this->begin(); iter != this->end(); ++iter)
00395 {
00396 if (rhs.found(iter.key()) && erase(iter))
00397 {
00398 count++;
00399 }
00400 }
00401
00402 return count;
00403 }
00404
00405
00406 template<class T, class Key, class Hash>
00407 void Foam::StaticHashTable<T, Key, Hash>::resize(const label sz)
00408 {
00409 label newSize = canonicalSize(sz);
00410
00411 if (newSize == keys_.size())
00412 {
00413 # ifdef FULLDEBUG
00414 if (debug)
00415 {
00416 Info<< "StaticHashTable<T, Key, Hash>::resize(const label) : "
00417 << "new table size == old table size\n";
00418 }
00419 # endif
00420
00421 return;
00422 }
00423
00424 if (newSize < 1)
00425 {
00426 FatalErrorIn
00427 (
00428 "StaticHashTable<T, Key, Hash>::resize(const label)"
00429 ) << "Illegal size " << newSize << " for StaticHashTable."
00430 << " Minimum size is 1" << abort(FatalError);
00431 }
00432
00433
00434 StaticHashTable<T, Key, Hash> newTable(newSize);
00435
00436 for (const_iterator iter = cbegin(); iter != cend(); ++iter)
00437 {
00438 newTable.insert(iter.key(), *iter);
00439 }
00440
00441 transfer(newTable);
00442
00443
00444 endIter_.hashIndex_ = keys_.size();
00445 endConstIter_.hashIndex_ = keys_.size();
00446 }
00447
00448
00449 template<class T, class Key, class Hash>
00450 void Foam::StaticHashTable<T, Key, Hash>::clear()
00451 {
00452 forAll(keys_, hashIdx)
00453 {
00454 keys_[hashIdx].clear();
00455 objects_[hashIdx].clear();
00456 }
00457
00458 nElmts_ = 0;
00459 }
00460
00461
00462 template<class T, class Key, class Hash>
00463 void Foam::StaticHashTable<T, Key, Hash>::clearStorage()
00464 {
00465 clear();
00466 resize(1);
00467 }
00468
00469
00470
00471 template<class T, class Key, class Hash>
00472 void Foam::StaticHashTable<T, Key, Hash>::transfer
00473 (
00474 StaticHashTable<T, Key, Hash>& ht
00475 )
00476 {
00477
00478 clear();
00479
00480
00481 keys_.transfer(ht.keys_);
00482 objects_.transfer(ht.objects_);
00483
00484 nElmts_ = ht.nElmts_;
00485 ht.nElmts_ = 0;
00486
00487
00488 endIter_.hashIndex_ = keys_.size();
00489 endConstIter_.hashIndex_ = keys_.size();
00490
00491 ht.endIter_.hashIndex_ = 0;
00492 ht.endConstIter_.hashIndex_ = 0;
00493 }
00494
00495
00496
00497
00498 template<class T, class Key, class Hash>
00499 void Foam::StaticHashTable<T, Key, Hash>::operator=
00500 (
00501 const StaticHashTable<T, Key, Hash>& rhs
00502 )
00503 {
00504
00505 if (this == &rhs)
00506 {
00507 FatalErrorIn
00508 (
00509 "StaticHashTable<T, Key, Hash>::operator="
00510 "(const StaticHashTable<T, Key, Hash>&)"
00511 ) << "attempted assignment to self"
00512 << abort(FatalError);
00513 }
00514
00515
00516
00517 if (keys_.empty())
00518 {
00519 keys_.setSize(rhs.keys_.size());
00520 objects_.setSize(keys_.size());
00521
00522
00523 endIter_.hashIndex_ = keys_.size();
00524 endConstIter_.hashIndex_ = keys_.size();
00525 }
00526 else
00527 {
00528 clear();
00529
00530 }
00531
00532
00533 for (const_iterator iter = rhs.cbegin(); iter != rhs.cend(); ++iter)
00534 {
00535 insert(iter.key(), *iter);
00536 }
00537 }
00538
00539 template<class T, class Key, class Hash>
00540 bool Foam::StaticHashTable<T, Key, Hash>::operator==
00541 (
00542 const StaticHashTable<T, Key, Hash>& rhs
00543 ) const
00544 {
00545
00546 for (const_iterator iter = cbegin(); iter != cend(); ++iter)
00547 {
00548 const_iterator fnd = rhs.find(iter.key());
00549
00550 if (fnd == rhs.cend() || fnd() != iter())
00551 {
00552 return false;
00553 }
00554 }
00555
00556
00557 for (const_iterator iter = rhs.cbegin(); iter != rhs.cend(); ++iter)
00558 {
00559 const_iterator fnd = find(iter.key());
00560
00561 if (fnd == cend() || fnd() != iter())
00562 {
00563 return false;
00564 }
00565 }
00566 return true;
00567 }
00568
00569
00570 template<class T, class Key, class Hash>
00571 bool Foam::StaticHashTable<T, Key, Hash>::operator!=
00572 (
00573 const StaticHashTable<T, Key, Hash>& rhs
00574 ) const
00575 {
00576 return !(operator==(rhs));
00577 }
00578
00579
00580
00581
00582 #include "StaticHashTableIO.C"
00583
00584
00585
00586 #endif
00587
00588