35 template<
class T,
class Key,
class Hash>
45 table_ =
new hashedEntry*[tableSize_];
47 for (
label hashIdx = 0; hashIdx < tableSize_; hashIdx++)
55 template<
class T,
class Key,
class Hash>
67 template<
class T,
class Key,
class Hash>
82 template<
class T,
class Key,
class Hash>
92 insert(pair.first(), pair.second());
99 template<
class T,
class Key,
class Hash>
112 template<
class T,
class Key,
class Hash>
117 const label hashIdx = hashKeyIndex(key);
119 for (hashedEntry* ep = table_[hashIdx]; ep; ep = ep->next_)
131 InfoInFunction <<
"Entry " << key <<
" not found in hash table\n";
139 template<
class T,
class Key,
class Hash>
148 const label hashIdx = hashKeyIndex(key);
150 for (hashedEntry* ep = table_[hashIdx]; ep; ep = ep->next_)
162 InfoInFunction <<
"Entry " << key <<
" not found in hash table\n";
170 template<
class T,
class Key,
class Hash>
179 const label hashIdx = hashKeyIndex(key);
181 for (hashedEntry* ep = table_[hashIdx]; ep; ep = ep->next_)
193 InfoInFunction <<
"Entry " << key <<
" not found in hash table\n";
201 template<
class T,
class Key,
class Hash>
207 for (const_iterator iter = cbegin(); iter != cend(); ++iter)
209 keys[keyI++] = iter.key();
216 template<
class T,
class Key,
class Hash>
226 template<
class T,
class Key,
class Hash>
239 const label hashIdx = hashKeyIndex(key);
241 hashedEntry* existing = 0;
242 hashedEntry* prev = 0;
244 for (hashedEntry* ep = table_[hashIdx]; ep; ep = ep->next_)
257 table_[hashIdx] =
new hashedEntry(key, table_[hashIdx], newEntry);
260 if (
double(nElmts_)/tableSize_ > 0.8 && tableSize_ < maxTableSize)
280 <<
"Cannot insert " << key <<
" already in hash table\n";
289 hashedEntry* ep =
new hashedEntry(key, existing->next_, newEntry);
298 table_[hashIdx] = ep;
308 template<
class T,
class Key,
class Hash>
315 hashedEntry* prev = 0;
319 hashedEntry* ep = hashTable_->table_[hashIndex_];
334 prev->next_ = entryPtr_->next_;
341 hashTable_->table_[hashIndex_] = entryPtr_->next_;
346 entryPtr_ =
reinterpret_cast<hashedEntry*
>(
this);
356 hashIndex_ = -hashIndex_ - 1;
359 hashTable_->nElmts_--;
370 template<
class T,
class Key,
class Hash>
382 template<
class T,
class Key,
class Hash>
385 return erase(find(key));
389 template<
class T,
class Key,
class Hash>
392 const label nTotal = nElmts_;
396 for (
label keyI = 0;
count < nTotal && keyI < keys.
size(); ++keyI)
398 if (
erase(keys[keyI]))
408 template<
class T,
class Key,
class Hash>
409 template<
class AnyType,
class AnyHash>
419 for (
iterator iter = begin(); iter != end(); ++iter)
431 template<
class T,
class Key,
class Hash>
436 if (newSize == tableSize_)
452 tmpTable->
insert(iter.key(), *iter);
455 label oldSize = tableSize_;
456 tableSize_ = tmpTable->tableSize_;
457 tmpTable->tableSize_ = oldSize;
459 hashedEntry** oldTable = table_;
460 table_ = tmpTable->table_;
461 tmpTable->table_ = oldTable;
467 template<
class T,
class Key,
class Hash>
472 for (
label hashIdx = 0; hashIdx < tableSize_; hashIdx++)
476 hashedEntry* ep = table_[hashIdx];
477 while (hashedEntry* next = ep->next_)
491 template<
class T,
class Key,
class Hash>
499 template<
class T,
class Key,
class Hash>
504 if (newSize < tableSize_)
507 resize(newSize ? newSize : 2);
512 template<
class T,
class Key,
class Hash>
522 tableSize_ = ht.tableSize_;
528 nElmts_ = ht.nElmts_;
535 template<
class T,
class Key,
class Hash>
545 <<
"attempted assignment to self"
559 for (
const_iterator iter = rhs.cbegin(); iter != rhs.cend(); ++iter)
561 insert(iter.key(), *iter);
566 template<
class T,
class Key,
class Hash>
576 <<
"attempted assignment to self"
584 template<
class T,
class Key,
class Hash>
587 std::initializer_list<Tuple2<Key, T>> lst
602 insert(pair.first(), pair.second());
607 template<
class T,
class Key,
class Hash>
614 if (size() != rhs.size())
619 for (
const_iterator iter = rhs.cbegin(); iter != rhs.cend(); ++iter)
623 if (fnd == cend() || fnd() != iter())
633 template<
class T,
class Key,
class Hash>
An STL-conforming const_iterator.
bool erase()
Erase the HashTable element at the current position.
An STL-conforming iterator.
An STL-conforming hash table.
List< Key > sortedToc() const
Return the table of contents as a sorted list.
bool erase(const iterator &)
Erase a hashedEntry specified by given iterator.
void shrink()
Shrink the allocated table to approx. twice number of elements.
List< Key > toc() const
Return the table of contents.
void transfer(HashTable< T, Key, Hash > &)
Transfer the contents of the argument table into this table.
const_iterator cbegin() const
const_iterator set to the beginning of the HashTable
bool insert(const Key &, const T &newElmt)
Insert a new hashedEntry.
iterator find(const Key &)
Find and return an iterator set at the hashedEntry.
void clearStorage()
Clear the table entries and the table itself.
bool found(const Key &) const
Return true if hashedEntry is found in table.
void clear()
Clear all entries from table.
HashTable(const label size=128)
Construct given initial table size.
void resize(const label newSize)
Resize the hash table for efficiency.
Hash function class for primitives. All non-primitives used to hash entries on hash tables likely nee...
A 1D array of objects of type <T>, where the size of the vector is known and used for subscript bound...
A 2-tuple for storing two objects of different types.
A 1D vector of objects of type <T>, where the size of the vector is known and can be used for subscri...
label size() const
Return the number of elements in the UList.
#define FatalErrorInFunction
Report an error message using Foam::FatalError.
#define InfoInFunction
Report an information message using Foam::Info.
void insert(const scalar, DynamicList< floatScalar > &)
Append scalar to given DynamicList.
intWM_LABEL_SIZE_t label
A label is an int32_t or int64_t as specified by the pre-processor macro WM_LABEL_SIZE.
tmp< fvMatrix< Type > > operator==(const fvMatrix< Type > &, const fvMatrix< Type > &)
errorManip< error > abort(error &err)
label count(const ListType &l, typename ListType::const_reference x)
Count the number of occurrences of a value in a list.
void T(FieldField< Field, Type > &f1, const FieldField< Field, Type > &f2)
triSurfaceToAgglom resize(surfacesMesh.size())
Template-invariant bits for HashTable.
static label canonicalSize(const label)
Return a canonical (power-of-two) size.
static iteratorEnd cend()
iteratorEnd set to beyond the end of any HashTable