1 /*---------------------------------------------------------------------------*\
3 \\ / F ield | OpenFOAM: The Open Source CFD Toolbox
5 \\ / A nd | Copyright held by original author
7 -------------------------------------------------------------------------------
9 This file is part of OpenFOAM.
11 OpenFOAM is free software; you can redistribute it and/or modify it
12 under the terms of the GNU General Public License as published by the
13 Free Software Foundation; either version 2 of the License, or (at your
14 option) any later version.
16 OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
17 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
18 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
21 You should have received a copy of the GNU General Public License
22 along with OpenFOAM; if not, write to the Free Software Foundation,
23 Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
25 \*---------------------------------------------------------------------------*/
27 #ifndef StaticHashTable_C
28 #define StaticHashTable_C
30 #include "StaticHashTable.H"
32 #include "IOstreams.H"
34 // * * * * * * * * * * * * Private Member Functions * * * * * * * * * * * * //
36 template<class T, class Key, class Hash>
37 Foam::label Foam::StaticHashTable<T, Key, Hash>::canonicalSize(const label size)
44 // enforce power of two
45 unsigned int goodSize = size;
47 if (goodSize & (goodSize - 1))
49 // brute-force is fast enough
51 while (goodSize < unsigned(size))
61 // * * * * * * * * * * * * * * * * Constructors * * * * * * * * * * * * * * //
63 // Construct given initial table size
64 template<class T, class Key, class Hash>
65 Foam::StaticHashTable<T, Key, Hash>::StaticHashTable(const label size)
67 StaticHashTableName(),
68 keys_(canonicalSize(size)),
69 objects_(keys_.size()),
71 endIter_(*this, keys_.size(), 0),
72 endConstIter_(*this, keys_.size(), 0)
78 "StaticHashTable<T, Key, Hash>::StaticHashTable(const label size)"
79 ) << "Illegal size " << size << " for StaticHashTable."
80 << " Minimum size is 1" << abort(FatalError);
86 template<class T, class Key, class Hash>
87 Foam::StaticHashTable<T, Key, Hash>::StaticHashTable
89 const StaticHashTable<T, Key, Hash>& ht
92 StaticHashTableName(),
94 objects_(ht.objects_),
96 endIter_(*this, keys_.size(), 0),
97 endConstIter_(*this, keys_.size(), 0)
102 template<class T, class Key, class Hash>
103 Foam::StaticHashTable<T, Key, Hash>::StaticHashTable
105 const Xfer< StaticHashTable<T, Key, Hash> >& ht
108 StaticHashTableName(),
112 endIter_(*this, 0, 0),
113 endConstIter_(*this, 0, 0)
119 // * * * * * * * * * * * * * * * * Destructor * * * * * * * * * * * * * * * //
121 template<class T, class Key, class Hash>
122 Foam::StaticHashTable<T, Key, Hash>::~StaticHashTable()
126 // * * * * * * * * * * * * * * * Member Functions * * * * * * * * * * * * * //
128 template<class T, class Key, class Hash>
129 bool Foam::StaticHashTable<T, Key, Hash>::found(const Key& key) const
133 const label hashIdx = hashKeyIndex(key);
134 const List<Key>& localKeys = keys_[hashIdx];
136 forAll(localKeys, elemIdx)
138 if (key == localKeys[elemIdx])
148 Info<< "StaticHashTable<T, Key, Hash>::found(const Key&) : "
149 << "Entry " << key << " not found in hash table\n";
157 template<class T, class Key, class Hash>
158 typename Foam::StaticHashTable<T, Key, Hash>::iterator
159 Foam::StaticHashTable<T, Key, Hash>::find
166 const label hashIdx = hashKeyIndex(key);
167 const List<Key>& localKeys = keys_[hashIdx];
169 forAll(localKeys, elemIdx)
171 if (key == localKeys[elemIdx])
173 return iterator(*this, hashIdx, elemIdx);
181 Info<< "StaticHashTable<T, Key, Hash>::find(const Key&) : "
182 << "Entry " << key << " not found in hash table\n";
190 template<class T, class Key, class Hash>
191 typename Foam::StaticHashTable<T, Key, Hash>::const_iterator
192 Foam::StaticHashTable<T, Key, Hash>::find
199 const label hashIdx = hashKeyIndex(key);
200 const List<Key>& localKeys = keys_[hashIdx];
202 forAll(localKeys, elemIdx)
204 if (key == localKeys[elemIdx])
206 return const_iterator(*this, hashIdx, elemIdx);
214 Info<< "StaticHashTable<T, Key, Hash>::find(const Key&) const : "
215 << "Entry " << key << " not found in hash table\n";
223 // Return the table of contents
224 template<class T, class Key, class Hash>
225 Foam::List<Key> Foam::StaticHashTable<T, Key, Hash>::toc() const
227 List<Key> tofc(nElmts_);
230 for (const_iterator iter = cbegin(); iter != cend(); ++iter)
232 tofc[i++] = iter.key();
239 template<class T, class Key, class Hash>
240 bool Foam::StaticHashTable<T, Key, Hash>::set
247 const label hashIdx = hashKeyIndex(key);
248 List<Key>& localKeys = keys_[hashIdx];
250 label existing = localKeys.size();
251 forAll(localKeys, elemIdx)
253 if (key == localKeys[elemIdx])
260 if (existing == localKeys.size())
263 List<T>& localObjects = objects_[hashIdx];
265 localKeys.setSize(existing+1);
266 localObjects.setSize(existing+1);
268 localKeys[existing] = key;
269 localObjects[existing] = newEntry;
275 // found - but protected from overwriting
276 // this corresponds to the STL 'insert' convention
280 Info<< "StaticHashTable<T, Key, Hash>::set"
281 "(const Key& key, T newEntry, true) : "
282 "Cannot insert " << key << " already in hash table\n";
289 // found - overwrite existing entry
290 // this corresponds to the Perl convention
291 objects_[hashIdx][existing] = newEntry;
298 template<class T, class Key, class Hash>
299 bool Foam::StaticHashTable<T, Key, Hash>::erase(const iterator& cit)
303 List<Key>& localKeys = keys_[cit.hashIndex_];
304 List<T>& localObjects = objects_[cit.hashIndex_];
307 for (label i = cit.elemIndex_+1; i < localKeys.size(); i++)
309 localKeys[i-1] = localKeys[i];
310 localObjects[i-1] = localObjects[i];
312 localKeys.setSize(localKeys.size()-1);
313 localObjects.setSize(localObjects.size()-1);
315 // adjust iterator after erase
316 iterator& it = const_cast<iterator&>(cit);
319 if (it.elemIndex_ < 0)
321 // No previous element in the local list
323 // Search back for previous non-zero table entry
324 while (--it.hashIndex_ >= 0 && !objects_[it.hashIndex_].size())
327 if (it.hashIndex_ >= 0)
329 // The last element in the local list
330 it.elemIndex_ = objects_[it.hashIndex_].size() - 1;
334 // No previous found. Mark with special value which is
336 // - handled by operator++
347 Info<< "StaticHashTable<T, Key, Hash>::erase(iterator&) : "
348 << "hashedEntry removed.\n";
359 Info<< "StaticHashTable<T, Key, Hash>::erase(iterator&) : "
360 << "cannot remove hashedEntry from hash table\n";
369 template<class T, class Key, class Hash>
370 bool Foam::StaticHashTable<T, Key, Hash>::erase(const Key& key)
372 iterator it = find(key);
385 template<class T, class Key, class Hash>
386 Foam::label Foam::StaticHashTable<T, Key, Hash>::erase
388 const StaticHashTable<T, Key, Hash>& rhs
393 // Remove rhs elements from this table
394 // NOTE: could optimize depending on which hash is smaller
395 for (iterator iter = this->begin(); iter != this->end(); ++iter)
397 if (rhs.found(iter.key()) && erase(iter))
407 template<class T, class Key, class Hash>
408 void Foam::StaticHashTable<T, Key, Hash>::resize(const label sz)
410 label newSize = canonicalSize(sz);
412 if (newSize == keys_.size())
417 Info<< "StaticHashTable<T, Key, Hash>::resize(const label) : "
418 << "new table size == old table size\n";
429 "StaticHashTable<T, Key, Hash>::resize(const label)"
430 ) << "Illegal size " << newSize << " for StaticHashTable."
431 << " Minimum size is 1" << abort(FatalError);
435 StaticHashTable<T, Key, Hash> newTable(newSize);
437 for (const_iterator iter = cbegin(); iter != cend(); ++iter)
439 newTable.insert(iter.key(), *iter);
444 // Adapt end() iterators
445 endIter_.hashIndex_ = keys_.size();
446 endConstIter_.hashIndex_ = keys_.size();
450 template<class T, class Key, class Hash>
451 void Foam::StaticHashTable<T, Key, Hash>::clear()
453 forAll(keys_, hashIdx)
455 keys_[hashIdx].clear();
456 objects_[hashIdx].clear();
463 template<class T, class Key, class Hash>
464 void Foam::StaticHashTable<T, Key, Hash>::clearStorage()
472 template<class T, class Key, class Hash>
473 void Foam::StaticHashTable<T, Key, Hash>::transfer
475 StaticHashTable<T, Key, Hash>& ht
478 // Remove existing elements
482 keys_.transfer(ht.keys_);
483 objects_.transfer(ht.objects_);
485 nElmts_ = ht.nElmts_;
488 // Adapt end() iterators
489 endIter_.hashIndex_ = keys_.size();
490 endConstIter_.hashIndex_ = keys_.size();
492 ht.endIter_.hashIndex_ = 0;
493 ht.endConstIter_.hashIndex_ = 0;
497 // * * * * * * * * * * * * * * * Member Operators * * * * * * * * * * * * * //
499 template<class T, class Key, class Hash>
500 void Foam::StaticHashTable<T, Key, Hash>::operator=
502 const StaticHashTable<T, Key, Hash>& rhs
505 // Check for assignment to self
510 "StaticHashTable<T, Key, Hash>::operator="
511 "(const StaticHashTable<T, Key, Hash>&)"
512 ) << "attempted assignment to self"
513 << abort(FatalError);
517 // keys could be empty from a previous transfer()
520 keys_.setSize(rhs.keys_.size());
521 objects_.setSize(keys_.size());
523 // Adapt end() iterators
524 endIter_.hashIndex_ = keys_.size();
525 endConstIter_.hashIndex_ = keys_.size();
530 // keys_.size() does not change so neither does end() iterator.
534 for (const_iterator iter = rhs.cbegin(); iter != rhs.cend(); ++iter)
536 insert(iter.key(), *iter);
540 template<class T, class Key, class Hash>
541 bool Foam::StaticHashTable<T, Key, Hash>::operator==
543 const StaticHashTable<T, Key, Hash>& rhs
546 // Are all my elements in rhs?
547 for (const_iterator iter = cbegin(); iter != cend(); ++iter)
549 const_iterator fnd = rhs.find(iter.key());
551 if (fnd == rhs.cend() || fnd() != iter())
557 // Are all rhs elements in me?
558 for (const_iterator iter = rhs.cbegin(); iter != rhs.cend(); ++iter)
560 const_iterator fnd = find(iter.key());
562 if (fnd == cend() || fnd() != iter())
571 template<class T, class Key, class Hash>
572 bool Foam::StaticHashTable<T, Key, Hash>::operator!=
574 const StaticHashTable<T, Key, Hash>& rhs
577 return !(operator==(rhs));
581 // * * * * * * * * * * * * * * * Friend Operators * * * * * * * * * * * * * //
583 #include "StaticHashTableIO.C"
585 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
589 // ************************************************************************* //