HashTable.H
Go to the documentation of this file.
1 /*---------------------------------------------------------------------------*\
2  ========= |
3  \\ / F ield | OpenFOAM: The Open Source CFD Toolbox
4  \\ / O peration | Website: https://openfoam.org
5  \\ / A nd | Copyright (C) 2011-2019 OpenFOAM Foundation
6  \\/ M anipulation |
7 -------------------------------------------------------------------------------
8 License
9  This file is part of OpenFOAM.
10 
11  OpenFOAM is free software: you can redistribute it and/or modify it
12  under the terms of the GNU General Public License as published by
13  the Free Software Foundation, either version 3 of the License, or
14  (at your option) any later version.
15 
16  OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
17  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
18  FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19  for more details.
20 
21  You should have received a copy of the GNU General Public License
22  along with OpenFOAM. If not, see <http://www.gnu.org/licenses/>.
23 
24 Class
25  Foam::HashTable
26 
27 Description
28  An STL-conforming hash table.
29 
30 Note
31  Hashing index collisions are handled via chaining using a singly-linked
32  list with the colliding entry being added to the head of the linked
33  list. Thus copying the hash table (or indeed even resizing it) will
34  often result in a different hash order. Use a sorted table-of-contents
35  when the hash order is important.
36 
37 SourceFiles
38  HashTableI.H
39  HashTable.C
40  HashTableIO.C
41 
42 \*---------------------------------------------------------------------------*/
43 
44 #ifndef HashTable_H
45 #define HashTable_H
46 
47 #include "label.H"
48 #include "uLabel.H"
49 #include "word.H"
50 #include "className.H"
51 #include <initializer_list>
52 
53 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
54 
55 namespace Foam
56 {
57 
58 // Forward declaration of friend functions and operators
59 
60 template<class T> class List;
61 template<class T> class UList;
62 template<class T, class Key, class Hash> class HashTable;
63 template<class T, class Key, class Hash> class HashPtrTable;
64 
65 template<class Type1, class Type2>
66 class Tuple2;
67 
68 template<class T, class Key, class Hash>
69 void writeEntry(Ostream& os, const HashTable<T, Key, Hash>& ht);
70 
71 template<class T, class Key, class Hash>
73 
74 template<class T, class Key, class Hash>
75 Ostream& operator<<(Ostream&, const HashTable<T, Key, Hash>&);
76 
77 
78 /*---------------------------------------------------------------------------*\
79  Class HashTableCore Declaration
80 \*---------------------------------------------------------------------------*/
81 
82 //- Template-invariant bits for HashTable
83 struct HashTableCore
84 {
85  //- Return a canonical (power-of-two) size
86  static label canonicalSize(const label);
87 
88  //- Maximum allowable table size
89  static const label maxTableSize;
90 
91  //- Construct null
93  {}
94 
95  //- Define template name and debug
96  ClassName("HashTable");
97 
98  //- A zero-sized end iterator
99  struct iteratorEnd
100  {
101  //- Construct null
102  iteratorEnd()
103  {}
104  };
105 
106  //- iteratorEnd set to beyond the end of any HashTable
107  inline static iteratorEnd cend()
108  {
109  return iteratorEnd();
110  }
111 
112  //- iteratorEnd set to beyond the end of any HashTable
113  inline static iteratorEnd end()
114  {
115  return iteratorEnd();
116  }
117 };
118 
119 
120 /*---------------------------------------------------------------------------*\
121  Class HashTable Declaration
122 \*---------------------------------------------------------------------------*/
123 
124 template<class T, class Key=word, class Hash=string::hash>
125 class HashTable
126 :
127  public HashTableCore
128 {
129  // Private Data type for table entries
130 
131  //- Structure to hold a hashed entry with SLList for collisions
132  struct hashedEntry
133  {
134  //- The lookup key
135  Key key_;
136 
137  //- Pointer to next hashedEntry in sub-list
138  hashedEntry* next_;
139 
140  //- The data object
141  T obj_;
142 
143  //- Construct from key, next pointer and object
144  inline hashedEntry(const Key&, hashedEntry* next, const T&);
145 
146  //- Disallow default bitwise copy construction
147  hashedEntry(const hashedEntry&) = delete;
148 
149  //- Disallow default bitwise assignment
150  void operator=(const hashedEntry&) = delete;
151  };
152 
153 
154  // Private Data: size of table, the table and current number of elements
155 
156  //- The current number of elements in table
157  label nElmts_;
158 
159  //- Number of primary entries allocated in table
160  label tableSize_;
161 
162  //- The table of primary entries
163  hashedEntry** table_;
164 
165 
166  // Private Member Functions
167 
168  //- Return a canonical (power-of-two) size
169  static label canonicalSize(const label);
170 
171  //- Return the hash index of the Key within the current table size.
172  // No checks for zero-sized tables.
173  inline label hashKeyIndex(const Key&) const;
174 
175  //- Assign a new hashedEntry to a possibly already existing key
176  bool set(const Key&, const T& newElmt, bool protect);
177 
178 
179 public:
180 
181  // Forward declaration of iterators
182 
183  class iteratorBase;
184  class iterator;
185  class const_iterator;
186 
187  //- Declare friendship with the HashPtrTable class
188  template<class T2, class Key2, class Hash2>
189  friend class HashPtrTable;
190 
191  //- Declare friendship with the iteratorBase
192  friend class iteratorBase;
193 
194  //- Declare friendship with the iterator
195  friend class iterator;
196 
197  //- Declare friendship with the const_iterator
198  friend class const_iterator;
199 
200 
201  // Constructors
202 
203  //- Construct given initial table size
204  HashTable(const label size = 128);
205 
206  //- Construct from Istream
207  HashTable(Istream&, const label size = 128);
208 
209  //- Copy constructor
211 
212  //- More Constructor
214 
215  //- Construct from an initializer list
216  HashTable(std::initializer_list<Tuple2<Key, T>>);
217 
218 
219  //- Destructor
220  ~HashTable();
221 
222 
223  // Member Functions
224 
225  // Access
226 
227  //- The size of the underlying table
228  inline label capacity() const;
229 
230  //- Return number of elements in table
231  inline label size() const;
232 
233  //- Return true if the hash table is empty
234  inline bool empty() const;
235 
236  //- Return true if hashedEntry is found in table
237  bool found(const Key&) const;
238 
239  //- Find and return an iterator set at the hashedEntry
240  // If not found iterator = end()
241  iterator find(const Key&);
242 
243  //- Find and return an const_iterator set at the hashedEntry
244  // If not found iterator = end()
245  const_iterator find(const Key&) const;
246 
247  //- Return the table of contents
248  List<Key> toc() const;
249 
250  //- Return the table of contents as a sorted list
251  List<Key> sortedToc() const;
252 
253  //- Print information
254  Ostream& printInfo(Ostream&) const;
255 
256 
257  // Edit
258 
259  //- Insert a new hashedEntry
260  inline bool insert(const Key&, const T& newElmt);
261 
262  //- Assign a new hashedEntry, overwriting existing entries
263  inline bool set(const Key&, const T& newElmt);
264 
265  //- Erase a hashedEntry specified by given iterator
266  // This invalidates the iterator until the next operator++
267  bool erase(const iterator&);
268 
269  //- Erase a hashedEntry specified by the given key
270  bool erase(const Key&);
271 
272  //- Remove entries given by the listed keys from this HashTable
273  // Return the number of elements removed
274  label erase(const UList<Key>&);
275 
276  //- Remove entries given by the given keys from this HashTable
277  // Return the number of elements removed.
278  // The parameter HashTable needs the same type of key, but the
279  // type of values held and the hashing function are arbitrary.
280  template<class AnyType, class AnyHash>
282 
283  //- Resize the hash table for efficiency
284  void resize(const label newSize);
285 
286  //- Clear all entries from table
287  void clear();
288 
289  //- Clear the table entries and the table itself.
290  // Equivalent to clear() followed by resize(0)
291  void clearStorage();
292 
293  //- Shrink the allocated table to approx. twice number of elements
294  void shrink();
295 
296  //- Transfer the contents of the argument table into this table
297  // and annul the argument table.
298  void transfer(HashTable<T, Key, Hash>&);
299 
300 
301  // Member Operators
302 
303  //- Find and return a hashedEntry
304  inline T& operator[](const Key&);
305 
306  //- Find and return a hashedEntry
307  inline const T& operator[](const Key&) const;
308 
309  //- Find and return a hashedEntry, create it null if not present
310  inline T& operator()(const Key&);
311 
312  //- Assignment operator
313  void operator=(const HashTable<T, Key, Hash>&);
314 
315  //- Move assignment operator
316  void operator=(HashTable<T, Key, Hash>&&);
317 
318  //- Assignment to an initializer list
319  void operator=(std::initializer_list<Tuple2<Key, T>>);
320 
321  //- Equality. Hash tables are equal if the keys and values are equal.
322  // Independent of table storage size and table order.
323  bool operator==(const HashTable<T, Key, Hash>&) const;
324 
325  //- The opposite of the equality operation. Takes linear time.
326  bool operator!=(const HashTable<T, Key, Hash>&) const;
327 
328 
329 
330  // STL type definitions
331 
332  //- Type of values the HashTable contains.
333  typedef T value_type;
334 
335  //- Type that can be used for storing into HashTable::value_type
336  // objects. This type is usually List::value_type&.
337  typedef T& reference;
338 
339  //- Type that can be used for storing into constant
340  // HashTable::value_type objects. This type is usually const
341  // HashTable::value_type&.
342  typedef const T& const_reference;
343 
344  //- The type that can represent the size of a HashTable.
345  typedef label size_type;
346 
347 
348  // Iterators and helpers
349 
350  //- The iterator base for HashTable
351  // Note: data and functions are protected, to allow reuse by iterator
352  // and prevent most external usage.
353  // iterator and const_iterator have the same size, allowing
354  // us to reinterpret_cast between them (if desired)
355  class iteratorBase
356  {
357  // Private Data
358 
359  //- Pointer to the HashTable for which this is an iterator
360  // This also lets us use the default bitwise copy/assignment
361  HashTable<T, Key, Hash>* hashTable_;
362 
363  //- Current element
364  hashedEntry* entryPtr_;
365 
366  //- Current hash index
367  label hashIndex_;
368 
369 
370  protected:
371 
372  // Constructors
373 
374  //- Construct null - equivalent to an 'end' position
375  inline iteratorBase();
376 
377  //- Construct from hash table, moving to its 'begin' position
378  inline explicit iteratorBase
379  (
380  const HashTable<T, Key, Hash>* curHashTable
381  );
382 
383  //- Construct from hash table, element and hash index
384  inline iteratorBase
385  (
386  const HashTable<T, Key, Hash>* curHashTable,
387  const hashedEntry* elmt,
388  const label hashIndex
389  );
390 
391 
392  // Protected Member Functions
393 
394  //- Increment to the next position
395  inline void increment();
396 
397  //- Erase the HashTable element at the current position
398  bool erase();
399 
400  //- Return non-const access to referenced object
401  inline T& object();
402 
403  //- Return const access to referenced object
404  inline const T& cobject() const;
405 
406 
407  public:
408 
409  // Member Operators
410 
411  // Access
412 
413  //- Return the Key corresponding to the iterator
414  inline const Key& key() const;
415 
416  //- Compare hashedEntry element pointers
417  inline bool operator==(const iteratorBase&) const;
418  inline bool operator!=(const iteratorBase&) const;
419 
420  //- Compare hashedEntry to iteratorEnd pointers
421  inline bool operator==(const iteratorEnd& unused) const;
422  inline bool operator!=(const iteratorEnd& unused) const;
423  };
424 
425 
426  //- An STL-conforming iterator
427  class iterator
428  :
429  public iteratorBase
430  {
431  friend class HashTable;
432 
433  // Private Member Functions
434 
435  //- Construct from hash table, moving to its 'begin' position
436  inline explicit iterator
437  (
438  HashTable<T, Key, Hash>* curHashTable
439  );
440 
441  //- Construct from hash table, element and hash index
442  inline iterator
443  (
444  HashTable<T, Key, Hash>* curHashTable,
445  hashedEntry* elmt,
446  const label hashIndex
447  );
448 
449 
450  public:
451 
452  // Constructors
453 
454  //- Construct null (end iterator)
455  inline iterator();
456 
457  //- Construct end iterator
458  inline iterator(const iteratorEnd& unused);
459 
460 
461  // Member Operators
462 
463  //- Return referenced hash value
464  inline T& operator*();
465  inline T& operator()();
466 
467  //- Return referenced hash value
468  inline const T& operator*() const;
469  inline const T& operator()() const;
470 
471  inline iterator& operator++();
472  inline iterator operator++(int);
473  };
474 
475  //- Iterator set to the beginning of the HashTable
476  inline iterator begin();
477 
478 
479  // STL const_iterator
480 
481  //- An STL-conforming const_iterator
482  class const_iterator
483  :
484  public iteratorBase
485  {
486  friend class HashTable;
487 
488  // Private Member Functions
489 
490  //- Construct from hash table, moving to its 'begin' position
491  inline explicit const_iterator
492  (
493  const HashTable<T, Key, Hash>* curHashTable
494  );
495 
496  //- Construct from hash table, element and hash index
497  inline const_iterator
498  (
499  const HashTable<T, Key, Hash>* curHashTable,
500  const hashedEntry* elmt,
501  const label hashIndex
502  );
503 
504 
505  public:
506 
507  // Constructors
508 
509  //- Construct null (end iterator)
510  inline const_iterator();
511 
512  //- Construct from iterator
513  inline const_iterator(const iterator&);
514 
515  //- Construct end iterator
516  inline const_iterator(const iteratorEnd& unused);
517 
518 
519  // Member Operators
520 
521  //- Return referenced hash value
522  inline const T& operator*() const;
523  inline const T& operator()() const;
524 
525  inline const_iterator& operator++();
526  inline const_iterator operator++(int);
527 
528  };
529 
530 
531  //- const_iterator set to the beginning of the HashTable
532  inline const_iterator cbegin() const;
533 
534  //- const_iterator set to the beginning of the HashTable
535  inline const_iterator begin() const;
536 
537 
538  // IOstream Operator
539 
540  friend Istream& operator>> <T, Key, Hash>
541  (
542  Istream&,
544  );
545 
546  friend Ostream& operator<< <T, Key, Hash>
547  (
548  Ostream&,
550  );
551 };
552 
553 
554 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
555 
556 } // End namespace Foam
557 
558 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
559 
560  #include "HashTableI.H"
561 
562 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
563 
564 #ifndef NoHashTableC
565 #ifdef NoRepository
566  #include "HashTable.C"
567 #endif
568 #endif
569 
570 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
571 
572 #endif
573 
574 // ************************************************************************* //
A zero-sized end iterator.
Definition: HashTable.H:98
intWM_LABEL_SIZE_t label
A label is an int32_t or int64_t as specified by the pre-processor macro WM_LABEL_SIZE.
Definition: label.H:59
An STL-conforming const_iterator.
Definition: HashTable.H:481
static iteratorEnd end()
iteratorEnd set to beyond the end of any HashTable
Definition: HashTable.H:112
srcOptions erase("case")
A 2-tuple for storing two objects of different types.
Definition: HashTable.H:65
tUEqn clear()
A 1D array of objects of type <T>, where the size of the vector is known and used for subscript bound...
Definition: HashTable.H:59
ClassName("HashTable")
Define template name and debug.
An Istream is an abstract base class for all input systems (streams, files, token lists etc)...
Definition: Istream.H:57
A HashTable specialization for hashing pointers.
Definition: HashPtrTable.H:50
HashTableCore()
Construct null.
Definition: HashTable.H:91
An STL-conforming iterator.
Definition: HashTable.H:426
tmp< fvMatrix< Type > > operator*(const volScalarField::Internal &, const fvMatrix< Type > &)
tmp< fvMatrix< Type > > operator==(const fvMatrix< Type > &, const fvMatrix< Type > &)
Istream & operator>>(Istream &, directionInfo &)
timeIndices insert(timeIndex, timeDirs[timeI].value())
triSurfaceToAgglom resize(surfacesMesh.size())
static const label maxTableSize
Maximum allowable table size.
Definition: HashTable.H:88
An STL-conforming hash table.
Definition: HashTable.H:61
graph_traits< Graph >::vertices_size_type size_type
Definition: SloanRenumber.C:73
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:60
An Ostream is an abstract base class for all output systems (streams, files, token lists...
Definition: Ostream.H:53
void T(FieldField< Field, Type > &f1, const FieldField< Field, Type > &f2)
void writeEntry(Ostream &os, const HashTable< T, Key, Hash > &ht)
Definition: HashTableIO.C:96
Template-invariant bits for HashTable.
Definition: HashTable.H:82
static label canonicalSize(const label)
Return a canonical (power-of-two) size.
Definition: HashTableCore.C:47
Macro definitions for declaring ClassName(), NamespaceName(), etc.
Hash function class for primitives. All non-primitives used to hash entries on hash tables likely nee...
Definition: Hash.H:54
Single incompressible phase derived from the phase-fraction. Used as part of the multiPhaseMixture fo...
Definition: phase.H:52
iteratorEnd()
Construct null.
Definition: HashTable.H:101
bool operator!=(const particle &, const particle &)
Definition: particle.C:1223
bool found
The iterator base for HashTable.
Definition: HashTable.H:354
static iteratorEnd cend()
iteratorEnd set to beyond the end of any HashTable
Definition: HashTable.H:106
Namespace for OpenFOAM.