StaticHashTable.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 | Copyright (C) 2011-2015 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::StaticHashTable
26 
27 Description
28  STL conforming hash table.
29 
30 Note
31  Uses straight lists as underlying type.
32  Is slower to insert than the standard HashTable, but should be more
33  memory efficient and faster to access.
34 
35 SourceFiles
36  StaticHashTableI.H
37  StaticHashTable.C
38  StaticHashTableIO.C
39 
40 \*---------------------------------------------------------------------------*/
41 
42 #ifndef StaticHashTable_H
43 #define StaticHashTable_H
44 
45 #include "label.H"
46 #include "uLabel.H"
47 #include "word.H"
48 #include "Xfer.H"
49 #include "className.H"
50 
51 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
52 
53 namespace Foam
54 {
55 
56 // Forward declaration of friend functions and operators
57 
58 template<class T> class List;
59 template<class T, class Key, class Hash> class StaticHashTable;
60 
61 template<class T, class Key, class Hash> Istream& operator>>
62 (
63  Istream&,
65 );
66 
67 template<class T, class Key, class Hash> Ostream& operator<<
68 (
69  Ostream&,
71 );
72 
73 
74 /*---------------------------------------------------------------------------*\
75  Class StaticHashTableCore Declaration
76 \*---------------------------------------------------------------------------*/
77 
78 //- Template-invariant bits for StaticHashTable
80 {
81  //- Return a canonical (power-of-two) size
82  static label canonicalSize(const label);
83 
84  //- Construct null
86  {}
87 
88  //- Define template name and debug
89  ClassName("StaticHashTable");
90 
91  //- A zero-sized end iterator
92  struct iteratorEnd
93  {
94  //- Construct null
95  iteratorEnd()
96  {}
97  };
98 };
99 
100 
101 
102 /*---------------------------------------------------------------------------*\
103  Class StaticHashTable Declaration
104 \*---------------------------------------------------------------------------*/
105 
106 template<class T, class Key=word, class Hash=string::hash>
107 class StaticHashTable
108 :
109  public StaticHashTableCore
110 {
111  // Private data type for table entries
112 
113  //- The lookup keys, ordered per hash value
114  List<List<Key> > keys_;
115 
116  //- For each key the corresponding object.
117  List<List<T> > objects_;
118 
119  //- The current number of elements in table
120  label nElmts_;
121 
122  //- Return a canonical (power-of-two) size
123  static label canonicalSize(const label);
124 
125  //- Return the hash index of the Key within the current table size.
126  // No checks for zero-sized tables.
127  inline label hashKeyIndex(const Key&) const;
128 
129  //- Assign a new hashed entry to a possibly already existing key
130  bool set(const Key&, const T& newElmt, bool protect);
131 
132 
133 public:
134 
135 
136  // Forward declaration of STL iterators
137 
138  template<class TRef, class TableRef>
139  class Iterator;
140 
141  typedef Iterator
142  <
143  T&,
145  > iterator;
146 
147  typedef Iterator
148  <
149  const T&,
151  > const_iterator;
152 
153 
154  // Declare friendship with the iterators
155 
156  friend class Iterator
157  <
158  T&,
160  >;
161 
162  friend class Iterator
163  <
164  const T&,
166  >;
167 
168 
169  // Constructors
170 
171  //- Construct given initial table size
172  StaticHashTable(const label size = 128);
173 
174  //- Construct from Istream
175  StaticHashTable(Istream&, const label size = 128);
176 
177  //- Construct as copy
179 
180  //- Construct by transferring the parameter contents
182 
183 
184  //- Destructor
185  ~StaticHashTable();
186 
187 
188  // Member Functions
189 
190  // Access
191 
192  //- Return number of elements in table.
193  inline label size() const;
194 
195  //- Return true if the hash table is empty
196  inline bool empty() const;
197 
198  //- Return true if hashed entry is found in table
199  bool found(const Key& key) const;
200 
201  //- Find and return an iterator set at the hashed entry
202  // If not found iterator = end()
203  iterator find(const Key& key);
204 
205  //- Find and return an const_iterator set at the hashed entry
206  // If not found iterator = end()
207  const_iterator find(const Key& key) const;
208 
209  //- Return the table of contents
210  List<Key> toc() const;
211 
212  //- Print information
213  Ostream& printInfo(Ostream&) const;
214 
215 
216  // Edit
217 
218  //- Insert a new hashed entry
219  bool insert(const Key& key, const T& newElmt);
220 
221  //- Assign a new hashed entry, overwriting existing entries
222  inline bool set(const Key&, const T& newElmt);
223 
224  //- Erase an hashed entry specified by given iterator
225  bool erase(const iterator& it);
226 
227  //- Erase an hashed entry specified by given key if in table
228  bool erase(const Key& key);
229 
230  //- Resize the hash table for efficiency
231  void resize(const label newSize);
232 
233  //- Remove entries in the given hash table from this hash table
234  // Return the number of elements removed
236 
237  //- Clear all entries from table
238  void clear();
239 
240  //- Clear the table entries and the table itself.
241  // Equivalent to clear() followed by resize(1)
242  void clearStorage();
243 
244  //- Transfer the contents of the argument table into this table
245  // and annul the argument table.
246  void transfer(StaticHashTable<T, Key, Hash>&);
247 
248  //- Transfer contents to the Xfer container
249  inline Xfer<StaticHashTable<T, Key, Hash> > xfer();
250 
251 
252  // Member Operators
253 
254  //- Find and return an hashed entry
255  inline T& operator[](const Key&);
256 
257  //- Find and return an hashed entry
258  inline const T& operator[](const Key&) const;
259 
260  //- Find and return an hashed entry, create it null if not present.
261  inline T& operator()(const Key&);
262 
263  //- Assignment
264  void operator=(const StaticHashTable<T, Key, Hash>&);
265 
266  //- Equality. Two hash tables are equal if all contents of first are
267  // also in second and vice versa.
268  bool operator==(const StaticHashTable<T, Key, Hash>&) const;
269 
270  //- The opposite of the equality operation.
271  bool operator!=(const StaticHashTable<T, Key, Hash>&) const;
272 
273 
274  // STL type definitions
275 
276  //- Type of values the StaticHashTable contains.
277  typedef T value_type;
278 
279  //- Type that can be used for storing into StaticHashTable::value_type
280  // objects. This type is usually List::value_type&.
281  typedef T& reference;
282 
283  //- Type that can be used for storing into constant
284  // StaticHashTable::value_type objects. This type is usually const
285  // StaticHashTable::value_type&.
286  typedef const T& const_reference;
287 
288  //- The type that can represent the size of a StaticHashTable.
289  typedef label size_type;
290 
291 
292  // STL iterator
293 
294  //- An STL iterator
295  template<class TRef, class TableRef>
296  class Iterator
297  {
298  friend class StaticHashTable;
299 
300  template<class TRef2, class TableRef2>
301  friend class Iterator;
302 
303  // Private data
304 
305  //- Reference to the StaticHashTable this is an iterator for
306  TableRef hashTable_;
307 
308  //- Current hash index
309  label hashIndex_;
310 
311  //- Index of current element at hashIndex
312  label elemIndex_;
313 
314 
315  public:
316 
317  // Constructors
318 
319  //- Construct from hash table, hash index and element index
320  inline Iterator
321  (
322  TableRef,
323  label hashIndex_,
324  label elemIndex_
325  );
326 
327  //- Construct from the non-const iterator
328  inline Iterator(const iterator&);
329 
330 
331  // Member operators
332 
333  inline void operator=(const iterator&);
334 
335  inline bool operator==(const iterator&) const;
336  inline bool operator==(const const_iterator&) const;
337 
338  inline bool operator!=(const iterator&) const;
339  inline bool operator!=(const const_iterator&) const;
340 
341  inline TRef operator*();
342  inline TRef operator()();
343 
344  inline Iterator& operator++();
345  inline Iterator operator++(int);
346 
347  inline const Key& key() const;
348  };
349 
350 
351  //- Iterator set to the beginning of the StaticHashTable
352  inline iterator begin();
353 
354  //- Iterator set to beyond the end of the StaticHashTable
355  inline const iterator& end();
356 
357  //- const_iterator set to the beginning of the StaticHashTable
358  inline const_iterator cbegin() const;
359 
360  //- const_iterator set to beyond the end of the StaticHashTable
361  inline const const_iterator& cend() const;
362 
363  //- const_iterator set to the beginning of the StaticHashTable
364  inline const_iterator begin() const;
365 
366  //- const_iterator set to beyond the end of the StaticHashTable
367  inline const const_iterator& end() const;
368 
369  // IOstream Operator
370 
371  friend Istream& operator>> <T, Key, Hash>
372  (
373  Istream&,
375  );
376 
377  friend Ostream& operator<< <T, Key, Hash>
378  (
379  Ostream&,
381  );
382 
383 
384 private:
385 
386  //- Iterator returned by end()
387  iterator endIter_;
388 
389  //- const_iterator returned by end()
390  const_iterator endConstIter_;
391 };
392 
393 
394 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
395 
396 } // End namespace Foam
397 
398 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
399 
400 # include "StaticHashTableI.H"
401 
402 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
403 
404 #ifndef NoStaticHashTableC
405 #ifdef NoRepository
406 # include "StaticHashTable.C"
407 #endif
408 #endif
409 
410 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
411 
412 #endif
413 
414 // ************************************************************************* //
tmp< fvMatrix< Type > > operator*(const DimensionedField< scalar, volMesh > &, const fvMatrix< Type > &)
STL conforming hash table.
static label canonicalSize(const label)
Return a canonical (power-of-two) size.
tmp< fvMatrix< Type > > operator==(const fvMatrix< Type > &, const fvMatrix< Type > &)
void T(FieldField< Field, Type > &f1, const FieldField< Field, Type > &f2)
StaticHashTableCore()
Construct null.
An Istream is an abstract base class for all input systems (streams, files, token lists etc)...
Definition: Istream.H:57
A simple container for copying or transferring objects of type <T>.
Definition: Xfer.H:85
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
T value_type
Type of values the StaticHashTable contains.
timeIndices insert(timeIndex, timeDirs[timeI].value())
Namespace for OpenFOAM.
ClassName("StaticHashTable")
Define template name and debug.
T & reference
Type that can be used for storing into StaticHashTable::value_type.
graph_traits< Graph >::vertices_size_type size_type
Definition: SloanRenumber.C:73
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
Hash function class for primitives. All non-primitives used to hash entries on hash tables likely nee...
Definition: Hash.H:54
Macro definitions for declaring ClassName(), NamespaceName(), etc.
A zero-sized end iterator.
bool operator!=(const particle &, const particle &)
Definition: particle.C:147
bool found
Template-invariant bits for StaticHashTable.
const T & const_reference
Type that can be used for storing into constant.
srcOptions erase("case")
dimensionedScalar TRef("TRef", dimTemperature, laminarTransport)
An Ostream is an abstract base class for all output systems (streams, files, token lists...
Definition: Ostream.H:53
UEqn clear()
triSurfaceToAgglom resize(surfacesMesh.size())