29 #ifndef Foam_HashTable_C 30 #define Foam_HashTable_C 39 template<
class T,
class Key,
class Hash>
49 template<
class T,
class Key,
class Hash>
56 template<
class T,
class Key,
class Hash>
61 if (initialCapacity > 0)
64 capacity_ = HashTableCore::canonicalSize(initialCapacity);
65 table_ =
new node_type*[capacity_];
66 std::fill_n(table_, capacity_, static_cast<node_type*>(
nullptr));
71 template<
class T,
class Key,
class Hash>
74 HashTable<
T, Key, Hash>(2*ht.size())
76 for (const_iterator iter = ht.cbegin(); iter != ht.cend(); ++iter)
78 insert(iter.key(), iter.val());
83 template<
class T,
class Key,
class Hash>
88 capacity_(rhs.capacity_),
98 template<
class T,
class Key,
class Hash>
101 std::initializer_list<std::pair<Key, T>> list
106 for (
const auto& keyval : list)
108 set(keyval.first, keyval.second);
115 template<
class T,
class Key,
class Hash>
130 template<
class T,
class Key,
class Hash>
136 for (const_iterator iter =
cbegin(); iter !=
cend(); ++iter)
138 list[
count++] = iter.key();
145 template<
class T,
class Key,
class Hash>
148 List<Key> list(this->
toc());
155 template<
class T,
class Key,
class Hash>
156 template<
class Compare>
169 template<
class T,
class Key,
class Hash>
177 for (const_iterator iter =
cbegin(); iter !=
cend(); ++iter)
188 template<
class T,
class Key,
class Hash>
196 for (iterator iter =
begin(); iter !=
end(); ++iter)
208 template<
class T,
class Key,
class Hash>
209 template<
class UnaryPredicate>
212 const UnaryPredicate& pred,
219 for (const_iterator iter =
cbegin(); iter !=
cend(); ++iter)
223 list[
count++] = iter.key();
234 template<
class T,
class Key,
class Hash>
235 template<
class UnaryPredicate>
238 const UnaryPredicate& pred,
245 for (const_iterator iter =
cbegin(); iter !=
cend(); ++iter)
249 list[
count++] = iter.key();
260 template<
class T,
class Key,
class Hash>
261 template<
class BinaryPredicate>
264 const BinaryPredicate& pred,
271 for (const_iterator iter =
cbegin(); iter !=
cend(); ++iter)
275 list[
count++] = iter.key();
286 template<
class T,
class Key,
class Hash>
287 template<
class UnaryPredicate>
290 const UnaryPredicate& pred,
296 for (const_iterator iter =
cbegin(); iter !=
cend(); ++iter)
308 template<
class T,
class Key,
class Hash>
309 template<
class UnaryPredicate>
312 const UnaryPredicate& pred,
318 for (const_iterator iter =
cbegin(); iter !=
cend(); ++iter)
330 template<
class T,
class Key,
class Hash>
331 template<
class BinaryPredicate>
334 const BinaryPredicate& pred,
340 for (const_iterator iter =
cbegin(); iter !=
cend(); ++iter)
352 template<
class T,
class Key,
class Hash>
353 template<
class... Args>
356 const bool overwrite,
366 const label index = hashKeyIndex(
key);
368 node_type* curr =
nullptr;
369 node_type* prev =
nullptr;
371 for (node_type* ep = table_[index]; ep; ep = ep->next_)
373 if (
key == ep->key())
385 new node_type(table_[index],
key, std::forward<Args>(
args)...);
388 if (0.8*capacity_ < size_)
390 if (capacity_ < maxTableSize) setCapacity(2*capacity_);
399 if (!node_type::stores_value())
404 node_type* ep = curr->next_;
411 ep =
new node_type(ep,
key, std::forward<Args>(
args)...);
433 template<
class T,
class Key,
class Hash>
443 const label index = hashKeyIndex(entry->key());
445 node_type* curr =
nullptr;
448 for (node_type* ep = table_[index]; ep; ep = ep->next_)
450 if (entry->key() == ep->key())
461 table_[index] = entry;
464 if (0.8*capacity_ < size_)
466 if (capacity_ < maxTableSize) setCapacity(2*capacity_);
472 <<
"Not inserting " <<
entry->key() <<
": already in table\n" 478 template<
class T,
class Key,
class Hash>
486 return iterator_erase(const_cast<iterator&>(iter));
490 template<
class T,
class Key,
class Hash>
496 if (iter.good())
return iterator_erase(iter);
502 template<
class T,
class Key,
class Hash>
503 template<
class InputIter>
514 const label nTotal = this->size();
515 changed < nTotal && first != last;
519 if (this->
erase(*first))
529 template<
class T,
class Key,
class Hash>
532 std::initializer_list<Key> keys
535 return erase(keys.begin(), keys.end());
539 template<
class T,
class Key,
class Hash>
550 template<
class T,
class Key,
class Hash>
560 template<
class T,
class Key,
class Hash>
561 template<
class AnyType,
class AnyHash>
567 const label nTotal = this->size();
570 if (other.
size() <= nTotal)
576 auto iter = other.
cbegin();
577 changed < nTotal && iter != other.
cend();
581 if (
erase(iter.key()))
592 iterator iter =
begin();
593 changed < nTotal && iter !=
end();
608 template<
class T,
class Key,
class Hash>
609 template<
class AnyType,
class AnyHash>
615 const label nTotal = this->size();
628 for (iterator iter =
begin(); iter !=
end(); ++iter)
641 template<
class T,
class Key,
class Hash>
644 newCapacity = HashTableCore::canonicalSize(newCapacity);
646 if (newCapacity == capacity_)
665 <<
"HashTable contains " << size_
666 <<
" elements, cannot set capacity to 0 buckets!" <<
nl;
673 auto oldTable = table_;
674 const label oldCapacity = capacity_;
676 capacity_ = newCapacity;
677 table_ =
new node_type*[capacity_];
678 std::fill_n(table_, capacity_, static_cast<node_type*>(
nullptr));
687 for (label i = 0, pending = size_; pending && i < oldCapacity; ++i)
689 for (node_type* ep = oldTable[i]; ep; )
691 node_type* next = ep->next_;
695 const label newIdx = hashKeyIndex(ep->key());
697 ep->next_ = table_[newIdx];
704 oldTable[i] =
nullptr;
711 template<
class T,
class Key,
class Hash>
714 setCapacity(newCapacity);
718 template<
class T,
class Key,
class Hash>
721 if (numEntries > size_)
726 if (numEntries > capacity_) setCapacity(numEntries);
731 template<
class T,
class Key,
class Hash>
739 for (label i = 0, pending = size_; pending && i < capacity_; ++i)
741 for (node_type* ep = table_[i]; ep; )
743 node_type* next = ep->next_;
756 template<
class T,
class Key,
class Hash>
769 template<
class T,
class Key,
class Hash>
777 std::swap(size_, rhs.size_);
778 std::swap(capacity_, rhs.capacity_);
779 std::swap(table_, rhs.table_);
783 template<
class T,
class Key,
class Hash>
796 template<
class T,
class Key,
class Hash>
797 template<
class UnaryPredicate>
800 const UnaryPredicate& pred,
806 for (iterator iter =
begin(); iter !=
end(); ++iter)
811 (pred(iter.key()) ? pruning : !pruning)
823 template<
class T,
class Key,
class Hash>
824 template<
class UnaryPredicate>
827 const UnaryPredicate& pred,
833 for (iterator iter =
begin(); iter !=
end(); ++iter)
838 (pred(iter.val()) ? pruning : !pruning)
850 template<
class T,
class Key,
class Hash>
851 template<
class BinaryPredicate>
854 const BinaryPredicate& pred,
860 for (iterator iter =
begin(); iter !=
end(); ++iter)
865 (pred(iter.key(), iter.val()) ? pruning : !pruning)
877 template<
class T,
class Key,
class Hash>
882 if (node_type::stores_value())
885 for (iterator iter = source.begin(); iter != source.end(); ++iter)
887 if (!contains(iter.key()))
889 node_type* entry = source.iterator_extract(iter);
890 this->insert_node(entry);
899 for (iterator iter = source.begin(); iter != source.end(); ++iter)
901 if (emplace(iter.key()))
910 template<
class T,
class Key,
class Hash>
919 template<
class T,
class Key,
class Hash>
922 const HashTable<T, Key, Hash>& rhs
933 for (const_iterator iter = rhs.
cbegin(); iter != rhs.
cend(); ++iter)
940 template<
class T,
class Key,
class Hash>
943 std::initializer_list<std::pair<Key, T>> rhs
949 for (
const auto& keyval : rhs)
951 set(keyval.first, keyval.second);
956 template<
class T,
class Key,
class Hash>
959 HashTable<T, Key, Hash>&& rhs
966 template<
class T,
class Key,
class Hash>
973 if (size() != rhs.
size())
978 for (const_iterator iter = rhs.
cbegin(); iter != rhs.
cend(); ++iter)
980 const const_iterator other(this->cfind(iter.key()));
982 if (!other.good() || other.val() != iter.val())
992 template<
class T,
class Key,
class Hash>
1002 template<
class T,
class Key,
class Hash>
1009 if (rhs.
size() && (
this != &rhs))
1013 for (const_iterator iter = rhs.
cbegin(); iter != rhs.
cend(); ++iter)
1015 insert(iter.key(), iter.val());
label countValues(const UnaryPredicate &pred, const bool invert=false) const
Count the number of values that satisfy the unary predicate.
label find(const ListType &input, const UnaryPredicate &pred, const label start=0)
Same as ListOps::find_if.
List< Key > tocKeys(const UnaryPredicate &pred, const bool invert=false) const
The table of contents (the keys) selected according to the unary predicate applied to the keys...
const_iterator cend() const noexcept
Return const_iterator to end traversing the constant UList.
errorManipArg< error, int > exit(error &err, const int errNo=1)
label filterValues(const UnaryPredicate &pred, const bool pruning=false)
Generalized means to filter table entries based on their values.
A 1D vector of objects of type <T> with a fixed length <N>.
void resize(const label len)
Adjust allocated size of list.
error FatalError
Error stream (stdout output on all processes), with additional 'FOAM FATAL ERROR' header text and sta...
#define FatalErrorInFunction
Report an error message using Foam::FatalError.
label retain(const HashTable< AnyType, Key, AnyHash > &other)
Retain table entries given by keys of the other hash-table.
A 1D array of objects of type <T>, where the size of the vector is known and used for subscript bound...
srcOptions insert("case", fileName(rootDirSource/caseDirSource))
constexpr char nl
The newline '\n' character (0x0a)
UPtrList< const node_type > csorted() const
Const access to the hash-table contents in sorted order (sorted by keys).
void setCapacity(label newCapacity)
Change the hash table capacity (number of buckets).
HashTable() noexcept
Default construct: empty without allocation (capacity=0)
UPtrList< node_type > sorted()
Non-const access to the hash-table contents in sorted order (sorted by keys).
List< Key > tocEntries(const BinaryPredicate &pred, const bool invert=false) const
The table of contents (the keys) selected according to the binary predicate applied to the keys and v...
label size() const noexcept
The number of elements in table.
label countEntries(const BinaryPredicate &pred, const bool invert=false) const
Count the number of entries that satisfy the binary predicate.
unsigned int count(const UList< bool > &bools, const bool val=true)
Count number of 'true' entries.
bool contains(const Key &key) const
True if hashed key is contained (found) in table.
label filterEntries(const BinaryPredicate &pred, const bool pruning=false)
Generalized means to filter table entries based on their key/value.
void sort(UList< T > &list)
Sort the list.
void clear()
Remove all entries from table.
constexpr auto cend(const C &c) -> decltype(c.end())
Return const_iterator to the end of the container c.
label countKeys(const UnaryPredicate &pred, const bool invert=false) const
Count the number of keys that satisfy the unary predicate.
A HashTable similar to std::unordered_map.
A list of pointers to objects of type <T>, without allocation/deallocation management of the pointers...
A 1D vector of objects of type <T>, where the size of the vector is known and can be used for subscri...
void resize(label newCapacity)
Rehash the hash table with new number of buckets. Currently identical to setCapacity() ...
bool empty() const noexcept
True if the hash table is empty.
constexpr auto end(C &c) -> decltype(c.end())
Return iterator to the end of the container c.
constexpr auto cbegin(const C &c) -> decltype(c.begin())
Return const_iterator to the beginning of the container c.
const_iterator cbegin() const noexcept
Return const_iterator to begin traversing the constant FixedList.
bool erase(const iterator &iter)
Erase an entry specified by given iterator.
labelList invert(const label len, const labelUList &map)
Create an inverse one-to-one mapping.
Bits that are independent of HashTable template parameters.
#define WarningInFunction
Report a warning using Foam::Warning.
Hash function class. The default definition is for primitives. Non-primitives used to hash entries on...
auto key(const Type &t) -> typename std::enable_if< std::is_enum< Type >::value, typename std::underlying_type< Type >::type >::type
void merge(HashTable< T, Key, Hash > &source)
Attempts to extract entries from source parameter and insert them into this, does not overwrite exist...
List< Key > sortedToc() const
The table of contents (the keys) in sorted order.
void reserve(label numEntries)
Reserve space for at least the specified number of elements (not the number of buckets) and regenerat...
void transfer(HashTable< T, Key, Hash > &rhs)
Transfer contents into this table.
triangles reserve(surf.size())
label filterKeys(const UnaryPredicate &pred, const bool pruning=false)
Generalized means to filter table entries based on their keys.
void swap(HashTable< T, Key, Hash > &rhs) noexcept
Swap contents into this table.
A class representing the concept of 0 (zero) that can be used to avoid manipulating objects known to ...
const_iterator cbegin() const noexcept
Return const_iterator to begin traversing the constant UList.
const_iterator cend() const noexcept
Return const_iterator to end traversing the constant FixedList.
List< Key > toc() const
The table of contents (the keys) in unsorted order.
tmp< faMatrix< Type > > operator==(const faMatrix< Type > &, const faMatrix< Type > &)
const_iterator cbegin() const
const_iterator set to the beginning of the HashTable
Foam::argList args(argc, argv)
constexpr auto begin(C &c) -> decltype(c.begin())
Return iterator to the beginning of the container c.
List< label > toc(const UList< bool > &bools)
Return the (sorted) values corresponding to 'true' entries.
constexpr const_iterator cend() const noexcept
const_iterator to signal the end (for any HashTable)
A keyword and a list of tokens is an 'entry'.
void clearStorage()
Remove all entries from table and the table itself.
const T * set(const label i) const
Return const pointer to element (can be nullptr), or nullptr for out-of-range access (ie...
List< Key > tocValues(const UnaryPredicate &pred, const bool invert=false) const
The table of contents (the keys) selected according to the unary predicate applied to the values...