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