FreeFOAM The Cross-Platform CFD Toolkit
Hosted by SourceForge:
Get FreeFOAM at SourceForge.net.
            Fast, secure and Free Open Source software downloads

StaticHashTable.C

Go to the documentation of this file.
00001 /*---------------------------------------------------------------------------*\
00002   =========                 |
00003   \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
00004    \\    /   O peration     |
00005     \\  /    A nd           | Copyright (C) 1991-2010 OpenCFD Ltd.
00006      \\/     M anipulation  |
00007 -------------------------------------------------------------------------------
00008 License
00009     This file is part of OpenFOAM.
00010 
00011     OpenFOAM is free software: you can redistribute it and/or modify it
00012     under the terms of the GNU General Public License as published by
00013     the Free Software Foundation, either version 3 of the License, or
00014     (at your option) any later version.
00015 
00016     OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
00017     ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
00018     FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
00019     for more details.
00020 
00021     You should have received a copy of the GNU General Public License
00022     along with OpenFOAM.  If not, see <http://www.gnu.org/licenses/>.
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 // * * * * * * * * * * * * Private Member Functions  * * * * * * * * * * * * //
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     // enforce power of two
00044     unsigned int goodSize = size;
00045 
00046     if (goodSize & (goodSize - 1))
00047     {
00048         // brute-force is fast enough
00049         goodSize = 1;
00050         while (goodSize < unsigned(size))
00051         {
00052             goodSize <<= 1;
00053         }
00054     }
00055 
00056     return goodSize;
00057 }
00058 
00059 
00060 // * * * * * * * * * * * * * * * * Constructors  * * * * * * * * * * * * * * //
00061 
00062 // Construct given initial table size
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 // Construct as copy
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 // * * * * * * * * * * * * * * * * Destructor  * * * * * * * * * * * * * * * //
00119 
00120 template<class T, class Key, class Hash>
00121 Foam::StaticHashTable<T, Key, Hash>::~StaticHashTable()
00122 {}
00123 
00124 
00125 // * * * * * * * * * * * * * * * Member Functions  * * * * * * * * * * * * * //
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 // Return the table of contents
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         // not found, append
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         // found - but protected from overwriting
00275         // this corresponds to the STL 'insert' convention
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         // found - overwrite existing entry
00289         // this corresponds to the Perl convention
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         // Copy down
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         // adjust iterator after erase
00315         iterator& it = const_cast<iterator&>(cit);
00316 
00317         it.elemIndex_--;
00318         if (it.elemIndex_ < 0)
00319         {
00320             // No previous element in the local list
00321 
00322             // Search back for previous non-zero table entry
00323             while (--it.hashIndex_ >= 0 && !objects_[it.hashIndex_].size())
00324             {}
00325 
00326             if (it.hashIndex_ >= 0)
00327             {
00328                 // The last element in the local list
00329                 it.elemIndex_ = objects_[it.hashIndex_].size() - 1;
00330             }
00331             else
00332             {
00333                 // No previous found. Mark with special value which is
00334                 // - not end()
00335                 // - handled by operator++
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     // Remove rhs elements from this table
00393     // NOTE: could optimize depending on which hash is smaller
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     // Adapt end() iterators
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     // Remove existing elements
00478     clear();
00479 
00480     // Copy data from ht
00481     keys_.transfer(ht.keys_);
00482     objects_.transfer(ht.objects_);
00483 
00484     nElmts_ = ht.nElmts_;
00485     ht.nElmts_ = 0;
00486 
00487     // Adapt end() iterators
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 // * * * * * * * * * * * * * * * Member Operators  * * * * * * * * * * * * * //
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     // Check for assignment to self
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     // keys could be empty from a previous transfer()
00517     if (keys_.empty())
00518     {
00519         keys_.setSize(rhs.keys_.size());
00520         objects_.setSize(keys_.size());
00521 
00522         // Adapt end() iterators
00523         endIter_.hashIndex_ = keys_.size();
00524         endConstIter_.hashIndex_ = keys_.size();
00525     }
00526     else
00527     {
00528         clear();
00529         // keys_.size() does not change so neither does end() iterator.
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     // Are all my elements in rhs?
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     // Are all rhs elements in me?
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 // * * * * * * * * * * * * * * * Friend Operators  * * * * * * * * * * * * * //
00581 
00582 #include "StaticHashTableIO.C"
00583 
00584 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
00585 
00586 #endif
00587 
00588 // ************************ vim: set sw=4 sts=4 et: ************************ //
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines