HashTable.H
Go to the documentation of this file.
1 /*---------------------------------------------------------------------------*\
2  ========= |
3  \\ / F ield | OpenFOAM: The Open Source CFD Toolbox
4  \\ / O peration |
5  \\ / A nd | www.openfoam.com
6  \\/ M anipulation |
7 -------------------------------------------------------------------------------
8  Copyright (C) 2011-2016 OpenFOAM Foundation
9  Copyright (C) 2017-2021 OpenCFD Ltd.
10 -------------------------------------------------------------------------------
11 License
12  This file is part of OpenFOAM.
13 
14  OpenFOAM is free software: you can redistribute it and/or modify it
15  under the terms of the GNU General Public License as published by
16  the Free Software Foundation, either version 3 of the License, or
17  (at your option) any later version.
18 
19  OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
20  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
21  FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
22  for more details.
23 
24  You should have received a copy of the GNU General Public License
25  along with OpenFOAM. If not, see <http://www.gnu.org/licenses/>.
26 
27 Class
28  Foam::HashTable
29 
30 Description
31  A HashTable similar to \c std::unordered_map.
32 
33  The entries are considered \a unordered since their placement
34  depends on the method used to generate the hash key index, the
35  table capacity, insertion order etc. When the key order is
36  important, use the sortedToc() method to obtain a list of sorted
37  keys and use that for further access.
38 
39  Internally the table uses closed addressing into a flat storage space
40  with collisions handled by linked-list chaining.
41 
42  The end iterator of all hash-tables has a nullptr to the hash entry.
43  Thus avoid separate allocation for each table and use a single one with
44  a nullptr. The hash-table iterators always have an entry-pointer as the
45  first member data, which allows reinterpret_cast from anything else with
46  a nullptr as its first data member.
47  The nullObject is such an item (with a nullptr data member).
48 
49 Note
50  For historical reasons, dereferencing the table iterator
51  (eg, \a *iter) returns a reference to the stored object value
52  rather than the stored key/val pair like std::unordered_map does.
53 
54  The HashTable iterator:
55  \code
56  forAllConstIters(table, iter)
57  {
58  Info<< "val:" << *iter << nl
59  << "key:" << iter.key() << nl;
60  << "val:" << iter.val() << nl;
61  }
62  \endcode
63  whereas for the \c std::unordered_map iterator:
64  \code
65  forAllConstIters(stdmap, iter)
66  {
67  Info<< "key/val:" << *iter << nl
68  << "key:" << iter->first << nl
69  << "val:" << iter->second << nl;
70  }
71  \endcode
72  This difference is most evident when using range-for syntax.
73 
74 SourceFiles
75  HashTableI.H
76  HashTableIterI.H
77  HashTable.C
78  HashTableIO.C
79  HashTableIter.C
80 
81 \*---------------------------------------------------------------------------*/
82 
83 #ifndef HashTable_H
84 #define HashTable_H
85 
86 #include "word.H"
87 #include "zero.H"
88 #include "Hash.H"
89 #include "HashTableDetail.H"
90 #include "HashTableCore.H"
91 
92 #include <initializer_list>
93 #include <iterator>
94 #include <utility>
95 
96 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
97 
98 namespace Foam
99 {
100 
101 // Forward Declarations
102 
103 template<class T> class List;
104 template<class T> class UList;
105 template<class T, unsigned N> class FixedList;
106 template<class T, class Key, class Hash> class HashTable;
107 
108 template<class T, class Key, class Hash>
110 
111 template<class T, class Key, class Hash>
113 
114 /*---------------------------------------------------------------------------*\
115  Class HashTable Declaration
116 \*---------------------------------------------------------------------------*/
117 
118 template<class T, class Key=word, class Hash=Foam::Hash<Key>>
119 class HashTable
120 :
121  public HashTableCore
122 {
123  // Types
124 
125  //- Table entry. A hashed node with a linked-list for collisions
126  typedef typename std::conditional
127  <
131  >::type node_type;
132 
133 
134  // Private Data
135 
136  //- The number of nodes currently stored in table
137  label size_;
138 
139  //- Number of nodes allocated in table
140  label capacity_;
141 
142  //- The table of primary nodes
143  node_type** table_;
144 
145 
146  // Private Member Functions
147 
148  //- Return the hash index of the Key within the current table size.
149  // No checks for zero-sized tables.
150  inline label hashKeyIndex(const Key& key) const;
151 
152  //- Assign a new hash-entry to a possibly already existing key.
153  // \return True if the new entry was set.
154  template<class... Args>
155  bool setEntry(const bool overwrite, const Key& key, Args&&... args);
156 
157  //- Read hash table
158  Istream& readTable(Istream& is);
159 
160  //- Write hash table
161  Ostream& writeTable(Ostream& os) const;
162 
163 
164 public:
165 
166  //- The template instance used for this HashTable
168 
169 
170  // STL type definitions
171 
172  //- The second template parameter, type of keys used.
173  typedef Key key_type;
174 
175  //- The first template parameter, type of objects contained.
176  typedef T mapped_type;
177 
178  //- Same as mapped_type for OpenFOAM HashTables
179  // Note that this is different than the std::map definition.
180  typedef T value_type;
181 
182  //- The third template parameter, the hash index method.
183  typedef Hash hasher;
184 
185  //- Pointer type for storing into value_type objects.
186  // This type is usually 'value_type*'.
187  typedef T* pointer;
188 
189  //- Reference to the stored value_type.
190  // This type is usually 'value_type&'.
191  typedef T& reference;
192 
193  //- Const pointer type for the stored value_type.
194  typedef const T* const_pointer;
195 
196  //- Const reference to the stored value_type.
197  typedef const T& const_reference;
198 
199  //- The type to represent the difference between two iterators
200  typedef label difference_type;
201 
202  //- The type that can represent the size of a HashTable.
203  typedef label size_type;
204 
205 
206  //- Forward iterator with non-const access
207  class iterator;
208 
209  //- Forward iterator with const access
210  class const_iterator;
211 
212 protected:
213 
214  //- Internally used base for iterator and const_iterator
215  template<bool Const> class Iterator;
216 
217  //- An iterator with const access to HashTable internals.
218  friend class Iterator<true>;
219 
220  //- An iterator with non-const access to HashTable internals.
221  friend class Iterator<false>;
222 
223 public:
224 
225  // Constructors
226 
227  //- Default construct with default (128) table capacity
228  HashTable();
229 
230  //- Construct given initial table capacity
231  explicit HashTable(const label size);
232 
233  //- Construct from Istream with default table capacity
234  HashTable(Istream& is, const label size = 128);
235 
236  //- Copy construct
237  HashTable(const this_type& ht);
238 
239  //- Move construct
240  HashTable(this_type&& rhs);
241 
242  //- Construct from an initializer list
243  // Duplicate entries are handled by overwriting
244  HashTable(std::initializer_list<std::pair<Key, T>> list);
245 
246 
247  //- Destructor
248  ~HashTable();
249 
250 
251  // Member Functions
252 
253  // Access
254 
255  //- The size of the underlying table
256  inline label capacity() const noexcept;
257 
258  //- The number of elements in table
259  inline label size() const noexcept;
260 
261  //- True if the hash table is empty
262  inline bool empty() const noexcept;
263 
264  //- Find and return a hashed entry. FatalError if it does not exist.
265  inline T& at(const Key& key);
266 
267  //- Find and return a hashed entry. FatalError if it does not exist.
268  inline const T& at(const Key& key) const;
269 
270  //- Return true if hashed entry is found in table
271  inline bool found(const Key& key) const;
272 
273  //- Find and return an iterator set at the hashed entry
274  // If not found iterator = end()
275  inline iterator find(const Key& key);
276 
277  //- Find and return an const_iterator set at the hashed entry
278  // If not found iterator = end()
279  inline const_iterator find(const Key& key) const;
280 
281  //- Find and return an const_iterator set at the hashed entry
282  // If not found iterator = end()
283  inline const_iterator cfind(const Key& key) const;
284 
285  //- Return hashed entry if it exists, or return the given default
286  inline const T& lookup(const Key& key, const T& deflt) const;
287 
288 
289  // Table of contents
290 
291  //- The table of contents (the keys) in unsorted order.
292  List<Key> toc() const;
293 
294  //- The table of contents (the keys) in sorted order
295  List<Key> sortedToc() const;
296 
297  //- The table of contents (the keys) sorted according to the
298  //- specified comparator
299  template<class Compare>
300  List<Key> sortedToc(const Compare& comp) const;
301 
302  //- The table of contents (the keys) selected according to the
303  //- unary predicate applied to the \b keys.
304  // \param invert changes the logic to select when the predicate
305  // is false
306  // \return sorted list of selected keys
307  template<class UnaryPredicate>
308  List<Key> tocKeys
309  (
310  const UnaryPredicate& pred,
311  const bool invert = false
312  ) const;
313 
314  //- The table of contents (the keys) selected according to the
315  //- unary predicate applied to the \b values.
316  // \param invert changes the logic to select when the predicate
317  // is false
318  // \return sorted list of selected keys
319  template<class UnaryPredicate>
320  List<Key> tocValues
321  (
322  const UnaryPredicate& pred,
323  const bool invert = false
324  ) const;
325 
326  //- The table of contents (the keys) selected according to the
327  //- binary predicate applied to the \b keys and \b values.
328  // \param invert changes the logic to select when the predicate
329  // is false
330  // \return sorted list of selected keys
331  template<class BinaryPredicate>
332  List<Key> tocEntries
333  (
334  const BinaryPredicate& pred,
335  const bool invert = false
336  ) const;
337 
338 
339  // Counting
340 
341  //- Count the number of keys that satisfy the unary predicate
342  // \param invert changes the logic to select when the predicate
343  // is false
344  template<class UnaryPredicate>
345  label countKeys
346  (
347  const UnaryPredicate& pred,
348  const bool invert = false
349  ) const;
350 
351  //- Count the number of values that satisfy the unary predicate
352  // \param invert changes the logic to select when the predicate
353  // is false
354  template<class UnaryPredicate>
355  label countValues
356  (
357  const UnaryPredicate& pred,
358  const bool invert = false
359  ) const;
360 
361  //- Count the number of entries that satisfy the binary predicate.
362  // \param invert changes the logic to select when the predicate
363  // is false
364  template<class BinaryPredicate>
365  label countEntries
366  (
367  const BinaryPredicate& pred,
368  const bool invert = false
369  ) const;
370 
371 
372  // Edit
373 
374  //- Emplace insert a new entry, not overwriting existing entries.
375  // \return True if the entry did not previously exist in the table.
376  template<class... Args>
377  inline bool emplace(const Key& key, Args&&... args);
378 
379  //- Emplace set an entry, overwriting any existing entries.
380  // \return True, since it always overwrites any entries.
381  template<class... Args>
382  inline bool emplace_set(const Key& key, Args&&... args);
383 
384  //- Copy insert a new entry, not overwriting existing entries.
385  // \return True if the entry did not previously exist in the table.
386  inline bool insert(const Key& key, const T& obj);
387 
388  //- Move insert a new entry, not overwriting existing entries.
389  // \return True if the entry did not previously exist in the table.
390  inline bool insert(const Key& key, T&& obj);
391 
392  //- Copy assign a new entry, overwriting existing entries.
393  // \return True, since it always overwrites any entries.
394  inline bool set(const Key& key, const T& obj);
395 
396  //- Move assign a new entry, overwriting existing entries.
397  // \return True, since it always overwrites any entries.
398  inline bool set(const Key& key, T&& obj);
399 
400  //- Erase an entry specified by given iterator
401  // This invalidates the iterator until the next ++ operation.
402  //
403  // Includes a safeguard against the end-iterator such that the
404  // following is safe:
405  // \code
406  // auto iter = table.find(unknownKey);
407  // table.erase(iter);
408  // \endcode
409  // which is what \code table.erase(unknownKey) \endcode does anyhow.
410  //
411  // \return True if the corresponding entry existed and was removed
412  bool erase(const iterator& iter);
413 
414  //- Erase an entry specified by the given key
415  // \return True if the entry existed and was removed
416  bool erase(const Key& key);
417 
418  //- Remove table entries given by keys of the other hash-table.
419  //
420  // The other hash-table must have the same type of key, but the
421  // type of values held and the hashing function are arbitrary.
422  //
423  // \return The number of items removed
424  template<class AnyType, class AnyHash>
425  label erase(const HashTable<AnyType, Key, AnyHash>& other);
426 
427  //- Remove table entries given by the listed keys
428  // \return The number of items removed
429  inline label erase(std::initializer_list<Key> keys);
430 
431  //- Remove multiple entries using an iterator range of keys
432  template<class InputIter>
433  inline label erase(InputIter first, InputIter last);
434 
435  //- Remove table entries given by the listed keys
436  // \return The number of items removed
437  template<unsigned N>
438  inline label erase(const FixedList<Key, N>& keys);
439 
440  //- Remove table entries given by the listed keys
441  // \return The number of items removed
442  inline label erase(const UList<Key>& keys);
443 
444  //- Retain table entries given by keys of the other hash-table.
445  //
446  // The other hash-table must have the same type of key, but the
447  // type of values held and the hashing function are arbitrary.
448  //
449  // \return The number of items changed (removed)
450  template<class AnyType, class AnyHash>
451  label retain(const HashTable<AnyType, Key, AnyHash>& other);
452 
453  //- Generalized means to filter table entries based on their keys.
454  // Keep (or optionally prune) entries with keys that satisfy
455  // the unary predicate, which has the following signature:
456  // \code
457  // bool operator()(const Key& k);
458  // \endcode
459  //
460  // For example,
461  // \code
462  // wordRes goodFields = ...;
463  // allFieldNames.filterKeys
464  // (
465  // [&goodFields](const word& k){ return goodFields.match(k); }
466  // );
467  // \endcode
468  //
469  // \return The number of items changed (removed)
470  template<class UnaryPredicate>
471  label filterKeys
472  (
473  const UnaryPredicate& pred,
474  const bool pruning = false
475  );
476 
477  //- Generalized means to filter table entries based on their values.
478  // Keep (or optionally prune) entries with values that satisfy
479  // the unary predicate, which has the following signature:
480  // \code
481  // bool operator()(const T& v);
482  // \endcode
483  //
484  // \return The number of items changed (removed)
485  template<class UnaryPredicate>
486  label filterValues
487  (
488  const UnaryPredicate& pred,
489  const bool pruning = false
490  );
491 
492  //- Generalized means to filter table entries based on their key/value.
493  // Keep (or optionally prune) entries with keys/values that satisfy
494  // the binary predicate, which has the following signature:
495  // \code
496  // bool operator()(const Key& k, const T& v);
497  // \endcode
498  //
499  // \return The number of items changed (removed)
500  template<class BinaryPredicate>
501  label filterEntries
502  (
503  const BinaryPredicate& pred,
504  const bool pruning = false
505  );
506 
507 
508  //- Resize the hash table for efficiency
509  void resize(const label sz);
510 
511  //- Clear all entries from table
512  void clear();
513 
514  //- Clear the table entries and the table itself.
515  // Equivalent to clear() followed by resize(0)
516  void clearStorage();
517 
518  //- Swap contents into this table
519  void swap(HashTable<T, Key, Hash>& rhs);
520 
521  //- Transfer contents into this table.
522  void transfer(HashTable<T, Key, Hash>& rhs);
523 
524 
525  // Member Operators
526 
527  //- Find and return a hashed entry. FatalError if it does not exist.
528  inline T& operator[](const Key& key);
529 
530  //- Find and return a hashed entry. FatalError if it does not exist.
531  inline const T& operator[](const Key& key) const;
532 
533  //- Return existing entry or create a new entry.
534  // A newly created entry is created as a nameless T() and is thus
535  // value-initialized. For primitives, this will be zero.
536  inline T& operator()(const Key& key);
537 
538  //- Return existing entry or insert a new entry.
539  inline T& operator()(const Key& key, const T& deflt);
540 
541  //- Copy assign
542  void operator=(const this_type& rhs);
543 
544  //- Copy assign from an initializer list
545  // Duplicate entries are handled by overwriting
546  void operator=(std::initializer_list<std::pair<Key, T>> rhs);
547 
548  //- Move assign
549  void operator=(this_type&& rhs);
550 
551  //- Equality. Tables are equal if all keys and values are equal,
552  //- independent of order or underlying storage size.
553  bool operator==(const this_type& rhs) const;
554 
555  //- The opposite of the equality operation.
556  bool operator!=(const this_type& rhs) const;
557 
558  //- Add entries into this HashTable
559  this_type& operator+=(const this_type& rhs);
560 
561 
562 protected:
563 
564  // Iterators and helpers
565 
566  //- The iterator base for HashTable (internal use only).
567  // Note: data and functions are protected, to allow reuse by iterator
568  // and prevent most external usage.
569  // iterator and const_iterator have the same size, allowing
570  // us to reinterpret_cast between them (if desired)
571 
572  template<bool Const>
573  class Iterator
574  {
575  public:
576 
577  // Typedefs
578  using iterator_category = std::forward_iterator_tag;
580 
581  //- The HashTable container type
582  using table_type = typename std::conditional
583  <
584  Const,
585  const this_type,
587  >::type;
588 
589  //- The node-type being addressed
590  using node_type = typename std::conditional
591  <
592  Const,
593  const this_type::node_type,
594  this_type::node_type
595  >::type;
596 
597  //- The key type
599 
600  //- The object type being addressed
601  using mapped_type = typename std::conditional
602  <
603  Const,
606  >::type;
607 
608 
609  // Member Functions
610 
611  //- True if iterator points to an entry
612  // This can be used directly instead of comparing to end()
613  inline bool good() const noexcept;
614 
615  //- True if iterator points to an entry - same as good()
616  inline bool found() const noexcept;
617 
618  //- The key associated with the iterator
619  inline const Key& key() const;
620 
621  //- Write the (key, val) pair
622  inline Ostream& print(Ostream& os) const;
623 
624 
625  // Member Operators
626 
627  //- True if iterator points to an entry
628  // This can be used directly instead of comparing to end()
629  explicit inline operator bool() const noexcept;
630 
631  //- Compare hash-entry element pointers.
632  // Independent of const/non-const access
633  template<bool Any>
634  inline bool operator==(const Iterator<Any>& iter) const noexcept;
635 
636  template<bool Any>
637  inline bool operator!=(const Iterator<Any>& iter) const noexcept;
638 
639 
640  protected:
641  friend class HashTable; // For begin/find constructors
642 
643  // Protected Data
644 
645  //- The selected entry.
646  // MUST be the first member for easy comparison between iterators
647  // and to support reinterpret_cast from nullObject
648  node_type* entry_;
649 
650  //- The hash-table container being iterated on.
651  // Uses pointer for default copy/assignment
652  table_type* container_;
653 
654  //- Index within the hash-table data.
655  // A signed value, since iterator_erase() needs a negative value
656  // to mark the position.
657  label index_;
658 
659 
660  // Protected Constructors
661 
662  //- Default construct (end iterator)
663  inline constexpr Iterator() noexcept;
664 
665  //- Construct from begin of hash-table
666  inline explicit Iterator(table_type* tbl);
667 
668  //- Construct by finding key in hash table
669  Iterator(table_type* tbl, const Key& key);
670 
671 
672  // Protected Member Functions
673 
674  //- Increment to the next position
675  inline void increment();
676 
677  //- Permit explicit cast to the other (const/non-const) iterator
678  template<bool Any>
679  explicit operator const Iterator<Any>&() const
680  {
681  return *reinterpret_cast<const Iterator<Any>*>(this);
682  }
683  };
684 
685 
686  //- Low-level entry erasure using iterator internals.
687  // This invalidates the iterator until the next ++ operation.
688  // \return True if the corresponding entry existed and was removed
689  bool iterator_erase(node_type*& entry, label& index);
690 
691 public:
692 
693  //- Forward iterator with non-const access
694  class iterator
695  :
696  public Iterator<false>
697  {
698  public:
699 
700  // Typedefs
701  using iterator_category = std::forward_iterator_tag;
703 
711 
712 
713  // Constructors
714 
715  //- Default construct (end iterator)
716  iterator() = default;
717 
718  //- Copy construct from similar access type
719  explicit iterator(const Iterator<false>& iter)
720  :
721  Iterator<false>(iter)
722  {}
723 
724 
725  // Member Functions/Operators
726 
727  //- Const access to referenced object (value)
728  inline const_reference val() const
729  {
730  return Iterator<false>::entry_->cval();
731  }
732 
733  //- Non-const access to referenced object (value)
734  inline reference val()
735  {
736  return Iterator<false>::entry_->val();
737  }
738 
739  //- Const access to referenced object (value)
740  inline const_reference operator*() const { return this->val(); }
741  inline const_reference operator()() const { return this->val(); }
742 
743  //- Non-const access to referenced object (value)
744  inline reference operator*() { return this->val(); }
745  inline reference operator()() { return this->val(); }
746 
747  inline iterator& operator++();
748  inline iterator operator++(int);
749  };
750 
751 
752  // STL const_iterator
753 
754  //- Forward iterator with const access
755  class const_iterator
756  :
757  public Iterator<true>
758  {
759  public:
760 
761  // Typedefs
762  using iterator_category = std::forward_iterator_tag;
764 
770 
771 
772  // Generated Methods
773 
774  //- Default construct (end iterator)
775  const_iterator() = default;
776 
777  //- Copy construct
778  const_iterator(const const_iterator&) = default;
779 
780  //- Copy assignment
781  const_iterator& operator=(const const_iterator&) = default;
782 
783 
784  // Constructors
785 
786  //- Copy construct from any access type
787  template<bool Any>
788  const_iterator(const Iterator<Any>& iter)
789  :
790  Iterator<true>(static_cast<const Iterator<Any>&>(iter))
791  {}
792 
793  //- Implicit conversion from dissimilar access type
794  const_iterator(const iterator& iter)
795  :
796  const_iterator(reinterpret_cast<const const_iterator&>(iter))
797  {}
798 
799 
800  // Member Functions/Operators
801 
802  //- Const access to referenced object (value)
803  inline reference val() const
804  {
805  return Iterator<true>::entry_->cval();
806  }
807 
808  //- Const access to referenced object (value)
809  inline reference operator*() const { return this->val(); }
810  inline reference operator()() const { return this->val(); }
811 
812  inline const_iterator& operator++();
813  inline const_iterator operator++(int);
814 
815 
816  // Assignment
817 
818  // Allow assign from iterator to const_iterator
819  const_iterator& operator=(const iterator& iter)
820  {
821  return this->operator=
822  (
823  reinterpret_cast<const const_iterator&>(iter)
824  );
825  }
826  };
827 
828 
829  // Iterator (keys)
830 
831  //- An iterator wrapper for returning a reference to the key
832  template<class Iter>
833  class key_iterator_base
834  :
835  public Iter
836  {
837  public:
838 
840  using pointer = const Key*;
841  using reference = const Key&;
842 
843  //- Default construct (end iterator)
844  constexpr key_iterator_base() noexcept
845  :
846  Iter()
847  {}
848 
849  //- Copy construct with implicit conversion
850  explicit key_iterator_base(const Iter& iter)
851  :
852  Iter(iter)
853  {}
854 
855  //- Return the key
856  inline reference operator*() const { return this->key(); }
857  inline reference operator()() const { return this->key(); }
858 
859  inline key_iterator_base& operator++()
860  {
861  this->increment();
862  return *this;
863  }
864 
865  inline key_iterator_base operator++(int)
866  {
867  key_iterator_base iter(*this);
868  this->increment();
869  return iter;
870  }
871  };
872 
873 
874  //- Forward iterator returning the key
875  using key_iterator = key_iterator_base<iterator>;
876 
877  //- Forward const iterator returning the key
878  using const_key_iterator = key_iterator_base<const_iterator>;
879 
880  //- A const iterator begin/end pair for iterating over keys
881  const_iterator_pair<const_key_iterator, this_type> keys() const
882  {
883  return const_iterator_pair<const_key_iterator, this_type>(*this);
884  }
885 
886 
887  // Iterator access
888 
889  //- iterator set to the beginning of the HashTable
890  inline iterator begin();
891 
892  //- const_iterator set to the beginning of the HashTable
893  inline const_iterator begin() const;
894 
895  //- const_iterator set to the beginning of the HashTable
896  inline const_iterator cbegin() const;
897 
898  //- iterator to signal the end (for any HashTable)
899  inline iterator end() noexcept;
900 
901  //- const_iterator to signal the end (for any HashTable)
902  inline const_iterator end() const noexcept;
903 
904  //- const_iterator to signal the end (for any HashTable)
905  inline constexpr const_iterator cend() const noexcept;
906 
907 
908  // Reading/writing
909 
910  //- Print information
911  Ostream& printInfo(Ostream& os) const;
912 
913  //- Write unordered keys (list), with line-breaks
914  //- when length exceeds shortLen.
915  // Using '0' suppresses line-breaks entirely.
916  Ostream& writeKeys(Ostream& os, const label shortLen=0) const;
917 
918 
919  // IOstream Operators
920 
921  friend Istream& operator>> <T, Key, Hash>
922  (
923  Istream&,
924  HashTable<T, Key, Hash>& tbl
925  );
926 
927  friend Ostream& operator<< <T, Key, Hash>
928  (
929  Ostream&,
930  const HashTable<T, Key, Hash>& tbl
931  );
932 };
933 
934 
935 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
936 
937 } // End namespace Foam
938 
939 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
940 
941 #include "HashTableI.H"
942 #include "HashTableIterI.H"
943 
944 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
945 
946 #ifndef NoHashTableC // Excluded from token.H
947 #ifdef NoRepository
948  #include "HashTable.C"
949 #endif
950 #endif
951 
952 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
953 
954 #endif
955 
956 // ************************************************************************* //
Foam::HashTable::iterator::val
const_reference val() const
Const access to referenced object (value)
Definition: HashTable.H:727
Foam::entry
A keyword and a list of tokens is an 'entry'.
Definition: entry.H:67
Foam::HashTable::key_iterator_base::reference
const Key & reference
Definition: HashTable.H:840
Foam::HashTable::size
label size() const noexcept
The number of elements in table.
Definition: HashTableI.H:52
Foam::HashTable::const_iterator::val
reference val() const
Const access to referenced object (value)
Definition: HashTable.H:802
Foam::HashTable::reference
T & reference
Reference to the stored value_type.
Definition: HashTable.H:190
Foam::HashTable::iterator::reference
this_type::reference reference
Definition: HashTable.H:707
HashTableCore.H
Foam::HashTable::const_iterator::iterator_category
std::forward_iterator_tag iterator_category
Definition: HashTable.H:761
Foam::HashTable::iterator::iterator
iterator(const Iterator< false > &iter)
Copy construct from similar access type.
Definition: HashTable.H:718
Foam::HashTable::iterator
Forward iterator with non-const access.
Definition: HashTable.H:693
Foam::HashTable::emplace_set
bool emplace_set(const Key &key, Args &&... args)
Emplace set an entry, overwriting any existing entries.
Definition: HashTableI.H:169
Foam::HashTable::toc
List< Key > toc() const
The table of contents (the keys) in unsorted order.
Definition: HashTable.C:121
HashTableIterI.H
Foam::HashTable::key_iterator_base::operator()
reference operator()() const
Definition: HashTable.H:856
Foam::HashTable::end
iterator end() noexcept
iterator to signal the end (for any HashTable)
Definition: HashTableIterI.H:256
Foam::HashTable::iterator::operator++
iterator & operator++()
Definition: HashTableIterI.H:190
Foam::HashTable::iterator::val
reference val()
Non-const access to referenced object (value)
Definition: HashTable.H:733
Foam::HashTable< Foam::autoPtr< Foam::interfaceCompositionModel > >::key_iterator
key_iterator_base< iterator > key_iterator
Forward iterator returning the key.
Definition: HashTable.H:874
Foam::HashTable::cbegin
const_iterator cbegin() const
const_iterator set to the beginning of the HashTable
Definition: HashTableIterI.H:248
Foam::HashTable::iterator::mapped_type
this_type::mapped_type mapped_type
Definition: HashTable.H:704
Foam::HashTable::countEntries
label countEntries(const BinaryPredicate &pred, const bool invert=false) const
Count the number of entries that satisfy the binary predicate.
HashTable.C
Foam::HashTable::iterator::operator()
reference operator()()
Definition: HashTable.H:744
Foam::HashTable::const_iterator
Forward iterator with const access.
Definition: HashTable.H:754
Foam::glTF::key
auto key(const Type &t) -> typename std::enable_if< std::is_enum< Type >::value, typename std::underlying_type< Type >::type >::type
Definition: foamGltfBase.H:108
Foam::HashTable::insert
bool insert(const Key &key, const T &obj)
Copy insert a new entry, not overwriting existing entries.
Definition: HashTableI.H:180
Foam::HashTable::emplace
bool emplace(const Key &key, Args &&... args)
Emplace insert a new entry, not overwriting existing entries.
Definition: HashTableI.H:157
Foam::HashTable::cend
constexpr const_iterator cend() const noexcept
const_iterator to signal the end (for any HashTable)
Definition: HashTableIterI.H:272
Foam::HashTable::const_iterator::operator*
reference operator*() const
Const access to referenced object (value)
Definition: HashTable.H:808
Foam::Detail::HashTableSingle
Internal storage type for HashSet entries.
Definition: HashTableDetail.H:194
Foam::operator>>
Istream & operator>>(Istream &, directionInfo &)
Definition: directionInfo.C:230
Foam::HashTable::key_iterator_base
An iterator wrapper for returning a reference to the key.
Definition: HashTable.H:832
Foam::HashTable::countValues
label countValues(const UnaryPredicate &pred, const bool invert=false) const
Count the number of values that satisfy the unary predicate.
Foam::HashTable::key_iterator_base::key_iterator_base
key_iterator_base(const Iter &iter)
Copy construct with implicit conversion.
Definition: HashTable.H:849
Foam::HashTable::filterValues
label filterValues(const UnaryPredicate &pred, const bool pruning=false)
Generalized means to filter table entries based on their values.
Foam::HashTable::tocKeys
List< Key > tocKeys(const UnaryPredicate &pred, const bool invert=false) const
Foam::HashTable::iterator::operator*
reference operator*()
Non-const access to referenced object (value)
Definition: HashTable.H:743
Foam::HashTable::retain
label retain(const HashTable< AnyType, Key, AnyHash > &other)
Retain table entries given by keys of the other hash-table.
Foam::HashTable::countKeys
label countKeys(const UnaryPredicate &pred, const bool invert=false) const
Count the number of keys that satisfy the unary predicate.
Foam::HashTable::iterator::value_type
this_type::value_type value_type
Definition: HashTable.H:705
Foam::HashTable::Iterator< true >::key_type
this_type::key_type key_type
The key type.
Definition: HashTable.H:597
Foam::HashTable::key_iterator_base::pointer
const Key * pointer
Definition: HashTable.H:839
Foam::HashTable::const_iterator::const_iterator
const_iterator()=default
Default construct (end iterator)
Foam::HashTable::const_iterator::key_type
this_type::key_type key_type
Definition: HashTable.H:764
Foam::HashTable::Iterator< true >::mapped_type
typename std::conditional< Const, const this_type::mapped_type, this_type::mapped_type >::type mapped_type
The object type being addressed.
Definition: HashTable.H:605
Foam::HashTable::const_iterator::pointer
this_type::const_pointer pointer
Definition: HashTable.H:767
Foam::invert
labelList invert(const label len, const labelUList &map)
Create an inverse one-to-one mapping.
Definition: ListOps.C:36
Foam::HashTable::filterEntries
label filterEntries(const BinaryPredicate &pred, const bool pruning=false)
Generalized means to filter table entries based on their key/value.
Foam::HashTable::const_iterator::operator++
const_iterator & operator++()
Definition: HashTableIterI.H:211
Foam::HashTable::iterator::iterator
iterator()=default
Default construct (end iterator)
Foam::HashTable::value_type
T value_type
Same as mapped_type for OpenFOAM HashTables.
Definition: HashTable.H:179
Foam::HashTable::key_iterator_base::value_type
this_type::key_type value_type
Definition: HashTable.H:838
Foam::HashTable::Iterator< true >::iterator_category
std::forward_iterator_tag iterator_category
Definition: HashTable.H:577
Foam::operator<<
Ostream & operator<<(Ostream &, const boundaryPatch &p)
Write boundaryPatch as dictionary entries (without surrounding braces)
Definition: boundaryPatch.C:83
Foam::HashTable::iterator::const_pointer
this_type::const_pointer const_pointer
Definition: HashTable.H:708
Foam::HashTable::mapped_type
T mapped_type
The first template parameter, type of objects contained.
Definition: HashTable.H:175
Foam::HashTable::iterator::pointer
this_type::pointer pointer
Definition: HashTable.H:706
Foam::HashTable::const_iterator::const_iterator
const_iterator(const iterator &iter)
Implicit conversion from dissimilar access type.
Definition: HashTable.H:793
Foam::HashTable::hasher
Hash hasher
The third template parameter, the hash index method.
Definition: HashTable.H:182
Foam::Hash
Hash function class. The default definition is for primitives. Non-primitives used to hash entries on...
Definition: Hash.H:53
Foam::HashTable::const_iterator::operator()
reference operator()() const
Definition: HashTable.H:809
Foam::HashTable::const_iterator::const_iterator
const_iterator(const Iterator< Any > &iter)
Copy construct from any access type.
Definition: HashTable.H:787
Foam::Istream
An Istream is an abstract base class for all input systems (streams, files, token lists etc)....
Definition: Istream.H:61
Foam::HashTable::erase
bool erase(const iterator &iter)
Erase an entry specified by given iterator.
Definition: HashTable.C:392
Foam::HashTable< Foam::autoPtr< Foam::interfaceCompositionModel > >::const_key_iterator
key_iterator_base< const_iterator > const_key_iterator
Forward const iterator returning the key.
Definition: HashTable.H:877
Foam::HashTable::Iterator< true >::node_type
typename std::conditional< Const, const this_type::node_type, this_type::node_type >::type node_type
The node-type being addressed.
Definition: HashTable.H:594
Foam::HashTable::const_pointer
const typedef T * const_pointer
Const pointer type for the stored value_type.
Definition: HashTable.H:193
Foam::HashTable::const_iterator::value_type
const this_type::value_type value_type
Definition: HashTable.H:766
Foam::HashTable::key_type
Key key_type
The second template parameter, type of keys used.
Definition: HashTable.H:172
Foam::T
void T(FieldField< Field, Type > &f1, const FieldField< Field, Type > &f2)
Definition: FieldFieldFunctions.C:58
Foam::HashTable::resize
void resize(const label sz)
Resize the hash table for efficiency.
Definition: HashTable.C:553
Foam::HashTable::HashTable
HashTable()
Default construct with default (128) table capacity.
Definition: HashTable.C:39
Foam::HashTable::~HashTable
~HashTable()
Destructor.
Definition: HashTable.C:108
Foam::HashTable::tocEntries
List< Key > tocEntries(const BinaryPredicate &pred, const bool invert=false) const
Foam::HashTableCore
Bits that are independent of HashTable template parameters.
Definition: HashTableCore.H:56
zero.H
Foam::radiation::lookup
Lookup type of boundary radiation properties.
Definition: lookup.H:63
Foam::HashTable::filterKeys
label filterKeys(const UnaryPredicate &pred, const bool pruning=false)
Generalized means to filter table entries based on their keys.
Foam::HashTable::iterator_erase
bool iterator_erase(node_type *&entry, label &index)
Low-level entry erasure using iterator internals.
Definition: HashTableIter.C:66
Foam::HashTable::const_iterator::mapped_type
const this_type::mapped_type mapped_type
Definition: HashTable.H:765
Foam::HashTable::iterator::operator*
const_reference operator*() const
Const access to referenced object (value)
Definition: HashTable.H:739
Foam::HashTable::key_iterator_base::key_iterator_base
constexpr key_iterator_base() noexcept
Default construct (end iterator)
Definition: HashTable.H:843
os
OBJstream os(runTime.globalPath()/outputName)
Foam
Namespace for OpenFOAM.
Definition: atmBoundaryLayer.C:33
Foam::HashTable::pointer
T * pointer
Pointer type for storing into value_type objects.
Definition: HashTable.H:186
Foam::HashTable::writeKeys
Ostream & writeKeys(Ostream &os, const label shortLen=0) const
Definition: HashTableIO.C:97
Foam::HashTable::sortedToc
List< Key > sortedToc() const
The table of contents (the keys) in sorted order.
Definition: HashTable.C:136
Foam::HashTable::find
iterator find(const Key &key)
Find and return an iterator set at the hashed entry.
Definition: HashTableI.H:114
Foam::HashTable::transfer
void transfer(HashTable< T, Key, Hash > &rhs)
Transfer contents into this table.
Definition: HashTable.C:671
Foam::HashTable::swap
void swap(HashTable< T, Key, Hash > &rhs)
Swap contents into this table.
Definition: HashTable.C:657
Foam::HashTable::Iterator< true >::difference_type
this_type::difference_type difference_type
Definition: HashTable.H:578
Foam::HashTable
A HashTable similar to std::unordered_map.
Definition: HashTable.H:105
Foam::HashTable::keys
const_iterator_pair< const_key_iterator, this_type > keys() const
A const iterator begin/end pair for iterating over keys.
Definition: HashTable.H:880
Foam::Detail::HashTablePair
Internal storage type for HashTable entries.
Definition: HashTableDetail.H:79
Foam::HashTable::difference_type
label difference_type
The type to represent the difference between two iterators.
Definition: HashTable.H:199
Foam::HashTable::iterator::difference_type
this_type::difference_type difference_type
Definition: HashTable.H:701
Foam::HashTable::begin
iterator begin()
iterator set to the beginning of the HashTable
Definition: HashTableIterI.H:232
Foam::HashTable::capacity
label capacity() const noexcept
The size of the underlying table.
Definition: HashTableI.H:45
Foam::HashTable::cfind
const_iterator cfind(const Key &key) const
Find and return an const_iterator set at the hashed entry.
Definition: HashTableI.H:141
Foam::HashTable::iterator::key_type
this_type::key_type key_type
Definition: HashTable.H:703
Foam::HashTable::clearStorage
void clearStorage()
Clear the table entries and the table itself.
Definition: HashTable.C:649
Foam::HashTable::printInfo
Ostream & printInfo(Ostream &os) const
Print information.
Definition: HashTableIO.C:60
Foam::HashTable::const_iterator::operator=
const_iterator & operator=(const const_iterator &)=default
Copy assignment.
Foam::HashTable::clear
void clear()
Clear all entries from table.
Definition: HashTable.C:630
Foam::HashTable::const_iterator::reference
this_type::const_reference reference
Definition: HashTable.H:768
Foam::List
A 1D array of objects of type <T>, where the size of the vector is known and used for subscript bound...
Definition: BitOps.H:63
Foam::HashTable::Iterator< true >::table_type
typename std::conditional< Const, const this_type, this_type >::type table_type
The HashTable container type.
Definition: HashTable.H:586
Foam::HashTable::const_iterator::operator=
const_iterator & operator=(const iterator &iter)
Definition: HashTable.H:818
Foam::HashTable::iterator::const_reference
this_type::const_reference const_reference
Definition: HashTable.H:709
Foam::HashTable::key_iterator_base::operator++
key_iterator_base & operator++()
Definition: HashTable.H:858
Foam::type
fileName::Type type(const fileName &name, const bool followLink=true)
Return the file type: DIRECTORY or FILE, normally following symbolic links.
Definition: MSwindows.C:590
Foam::FixedList
A 1D vector of objects of type <T> with a fixed length <N>.
Definition: HashTable.H:104
Foam::BitOps::print
Ostream & print(Ostream &os, UIntType value, char off='0', char on='1')
Print 0/1 bits in the (unsigned) integral type.
Definition: BitOps.H:199
Foam::UList
A 1D vector of objects of type <T>, where the size of the vector is known and can be used for subscri...
Definition: HashTable.H:103
Foam::HashTable::iterator::operator()
const_reference operator()() const
Definition: HashTable.H:740
Hash.H
Foam::HashTable::Iterator
Internally used base for iterator and const_iterator.
Definition: HashTable.H:214
Foam::HashTable::set
bool set(const Key &key, const T &obj)
Copy assign a new entry, overwriting existing entries.
Definition: HashTableI.H:202
Foam::roots::type
type
Types of root.
Definition: Roots.H:54
Foam::HashTable::tocValues
List< Key > tocValues(const UnaryPredicate &pred, const bool invert=false) const
Foam::HashTable::const_iterator::difference_type
this_type::difference_type difference_type
Definition: HashTable.H:762
Foam::HashTable::empty
bool empty() const noexcept
True if the hash table is empty.
Definition: HashTableI.H:59
Foam::Ostream
An Ostream is an abstract base class for all output systems (streams, files, token lists,...
Definition: Ostream.H:56
N
const Vector< label > N(dict.get< Vector< label >>("N"))
word.H
Foam::HashTable::found
bool found(const Key &key) const
Return true if hashed entry is found in table.
Definition: HashTableI.H:100
args
Foam::argList args(argc, argv)
Foam::HashTable::key_iterator_base::operator*
reference operator*() const
Return the key.
Definition: HashTable.H:855
Foam::HashTable::const_reference
const typedef T & const_reference
Const reference to the stored value_type.
Definition: HashTable.H:196
Foam::HashTable::key_iterator_base::operator++
key_iterator_base operator++(int)
Definition: HashTable.H:864
Foam::HashTable::operator
friend Ostream & operator(Ostream &, const HashTable< T, Key, Hash > &tbl)
HashTableDetail.H
Foam::HashTable::iterator::iterator_category
std::forward_iterator_tag iterator_category
Definition: HashTable.H:700
Foam::HashTable::size_type
label size_type
The type that can represent the size of a HashTable.
Definition: HashTable.H:202
Foam::HashTable::this_type
HashTable< T, Key, Hash > this_type
The template instance used for this HashTable.
Definition: HashTable.H:166
Foam::HashTable::at
T & at(const Key &key)
Find and return a hashed entry. FatalError if it does not exist.
Definition: HashTableI.H:66