34 template<
class T,
class Key,
class Hash>
43 unsigned int goodSize = size;
45 if (goodSize & (goodSize - 1))
49 while (goodSize <
unsigned(size))
61 template<
class T,
class Key,
class Hash>
66 tableSize_(canonicalSize(size)),
68 endIter_(*this, NULL, 0),
69 endConstIter_(*this, NULL, 0)
73 table_ =
new hashedEntry*[tableSize_];
75 for (label hashIdx = 0; hashIdx < tableSize_; hashIdx++)
83 template<
class T,
class Key,
class Hash>
88 tableSize_(ht.tableSize_),
90 endIter_(*this, NULL, 0),
91 endConstIter_(*this, NULL, 0)
95 table_ =
new hashedEntry*[tableSize_];
97 for (label hashIdx = 0; hashIdx < tableSize_; hashIdx++)
104 insert(iter.key(), *iter);
109 template<
class T,
class Key,
class Hash>
119 endIter_(*
this, NULL, 0),
120 endConstIter_(*
this, NULL, 0)
128 template<
class T,
class Key,
class Hash>
141 template<
class T,
class Key,
class Hash>
146 const label hashIdx = hashKeyIndex(key);
148 for (hashedEntry* ep = table_[hashIdx]; ep; ep = ep->next_)
160 Info<<
"HashTable<T, Key, Hash>::found(const Key& key) : "
161 <<
"Entry " << key <<
" not found in hash table\n";
169 template<
class T,
class Key,
class Hash>
178 const label hashIdx = hashKeyIndex(key);
180 for (hashedEntry* ep = table_[hashIdx]; ep; ep = ep->next_)
184 return iterator(*
this, ep, hashIdx);
192 Info<<
"HashTable<T, Key, Hash>::find(const Key& key) : "
193 <<
"Entry " << key <<
" not found in hash table\n";
201 template<
class T,
class Key,
class Hash>
210 const label hashIdx = hashKeyIndex(key);
212 for (hashedEntry* ep = table_[hashIdx]; ep; ep = ep->next_)
224 Info<<
"HashTable<T, Key, Hash>::find(const Key& key) const : "
225 <<
"Entry " << key <<
" not found in hash table\n";
234 template<
class T,
class Key,
class Hash>
242 tofc[i++] = iter.key();
249 template<
class T,
class Key,
class Hash>
259 template<
class T,
class Key,
class Hash>
272 const label hashIdx = hashKeyIndex(key);
274 hashedEntry* existing = 0;
275 hashedEntry* prev = 0;
277 for (hashedEntry* ep = table_[hashIdx]; ep; ep = ep->next_)
290 table_[hashIdx] =
new hashedEntry(key, table_[hashIdx], newEntry);
293 if (
double(nElmts_)/tableSize_ > 0.8)
298 Info<<
"HashTable<T, Key, Hash>::set"
299 "(const Key& key, T newEntry) : "
300 "Doubling table size\n";
304 resize(2*tableSize_);
314 Info<<
"HashTable<T, Key, Hash>::set"
315 "(const Key& key, T newEntry, true) : "
316 "Cannot insert " << key <<
" already in hash table\n";
325 hashedEntry* ep =
new hashedEntry(key, existing->next_, newEntry);
334 table_[hashIdx] = ep;
344 template<
class T,
class Key,
class Hash>
352 hashedEntry* prev = 0;
354 for (hashedEntry* ep = table_[it.hashIndex_]; ep; ep = ep->next_)
356 if (ep == it.elmtPtr_)
366 prev->next_ = it.elmtPtr_->next_;
373 table_[it.hashIndex_] = it.elmtPtr_->next_;
377 while (--it.hashIndex_ >= 0 && !table_[it.hashIndex_])
380 if (it.hashIndex_ >= 0)
383 it.elmtPtr_ = table_[it.hashIndex_];
385 while (it.elmtPtr_ && it.elmtPtr_->next_)
387 it.elmtPtr_ = it.elmtPtr_->next_;
395 it.elmtPtr_ =
reinterpret_cast<hashedEntry*
>(
this);
405 Info<<
"HashTable<T, Key, Hash>::erase(iterator&) : "
406 <<
"hashedEntry " << it.elmtPtr_->key_ <<
" removed.\n";
417 Info<<
"HashTable<T, Key, Hash>::erase(iterator&) : "
418 <<
"cannot remove hashedEntry from hash table\n";
427 template<
class T,
class Key,
class Hash>
443 template<
class T,
class Key,
class Hash>
453 if (erase(keys[keyI]))
464 template<
class T,
class Key,
class Hash>
465 template<
class AnyType,
class AnyHash>
475 for (
iterator iter = begin(); iter != end(); ++iter)
477 if (rhs.
found(iter.key()) && erase(iter))
487 template<
class T,
class Key,
class Hash>
490 label newSize = canonicalSize(sz);
492 if (newSize == tableSize_)
497 Info<<
"HashTable<T, Key, Hash>::resize(const label) : "
498 <<
"new table size == old table size\n";
509 newTable->
insert(iter.key(), *iter);
512 label oldTableSize = tableSize_;
513 tableSize_ = newTable->tableSize_;
514 newTable->tableSize_ = oldTableSize;
516 hashedEntry** oldTable = table_;
517 table_ = newTable->table_;
518 newTable->table_ = oldTable;
524 template<
class T,
class Key,
class Hash>
529 for (label hashIdx = 0; hashIdx < tableSize_; hashIdx++)
533 hashedEntry* ep = table_[hashIdx];
534 while (hashedEntry* next = ep->next_)
548 template<
class T,
class Key,
class Hash>
556 template<
class T,
class Key,
class Hash>
566 tableSize_ = ht.tableSize_;
572 nElmts_ = ht.nElmts_;
579 template<
class T,
class Key,
class Hash>
590 "HashTable<T, Key, Hash>::operator="
591 "(const HashTable<T, Key, Hash>&)"
592 ) <<
"attempted assignment to self"
599 resize(rhs.tableSize_);
608 insert(iter.key(), *iter);
613 template<
class T,
class Key,
class Hash>
614 bool Foam::HashTable<T, Key, Hash>::operator==
624 if (fnd == rhs.
cend() || fnd() != iter())
635 if (fnd == cend() || fnd() != iter())
644 template<
class T,
class Key,
class Hash>
645 bool Foam::HashTable<T, Key, Hash>::operator!=