FreeFOAM The Cross-Platform CFD Toolkit
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) 1991-2010 OpenCFD Ltd.
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 <OpenFOAM/label.H>
46 #include <OpenFOAM/uLabel.H>
47 #include <OpenFOAM/word.H>
48 #include <OpenFOAM/Xfer.H>
49 #include <OpenFOAM/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&,
64  StaticHashTable<T, Key, Hash>&
65 );
66 
67 template<class T, class Key, class Hash> Ostream& operator<<
68 (
69  Ostream&,
70  const StaticHashTable<T, Key, Hash>&
71 );
72 
73 
74 /*---------------------------------------------------------------------------*\
75  Class StaticHashTableName Declaration
76 \*---------------------------------------------------------------------------*/
77 
78 TemplateName(StaticHashTable);
79 
80 
81 /*---------------------------------------------------------------------------*\
82  Class StaticHashTable Declaration
83 \*---------------------------------------------------------------------------*/
84 
85 template<class T, class Key=word, class Hash=string::hash>
87 :
88  public StaticHashTableName
89 {
90  // Private data type for table entries
91 
92  //- The lookup keys, ordered per hash value
93  List<List<Key> > keys_;
94 
95  //- For each key the corresponding object.
96  List<List<T> > objects_;
97 
98  //- The current number of elements in table
99  label nElmts_;
100 
101  //- Return a canonical (power-of-two) size
102  static label canonicalSize(const label);
103 
104  //- Return the hash index of the Key within the current table size.
105  // No checks for zero-sized tables.
106  inline label hashKeyIndex(const Key&) const;
107 
108  //- Assign a new hashed entry to a possibly already existing key
109  bool set(const Key&, const T& newElmt, bool protect);
110 
111 public:
112 
113 
114  // Forward declaration of STL iterators
115 
116  template<class TRef, class TableRef>
117  class Iterator;
118 
119  typedef Iterator
120  <
121  T&,
123  > iterator;
124 
125  typedef Iterator
126  <
127  const T&,
130 
131 
132  // Declare friendship with the iterators
133 
134  friend class Iterator
135  <
136  T&,
138  >;
139 
140  friend class Iterator
141  <
142  const T&,
144  >;
145 
146 
147  // Constructors
148 
149  //- Construct given initial table size
150  StaticHashTable(const label size = 128);
151 
152  //- Construct from Istream
153  StaticHashTable(Istream&, const label size = 128);
154 
155  //- Construct as copy
157 
158  //- Construct by transferring the parameter contents
160 
161  // Destructor
162 
164 
165 
166  // Member Functions
167 
168  // Access
169 
170  //- Return number of elements in table.
171  inline label size() const;
172 
173  //- Return true if the hash table is empty
174  inline bool empty() const;
175 
176  //- Return true if hashed entry is found in table
177  bool found(const Key& key) const;
178 
179  //- Find and return an iterator set at the hashed entry
180  // If not found iterator = end()
181  iterator find(const Key& key);
182 
183  //- Find and return an const_iterator set at the hashed entry
184  // If not found iterator = end()
185  const_iterator find(const Key& key) const;
186 
187  //- Return the table of contents
188  List<Key> toc() const;
189 
190  //- Print information
191  Ostream& printInfo(Ostream&) const;
192 
193 
194  // Edit
195 
196  //- Insert a new hashed entry
197  bool insert(const Key& key, const T& newElmt);
198 
199  //- Assign a new hashed entry, overwriting existing entries
200  inline bool set(const Key&, const T& newElmt);
201 
202  //- Erase an hashed entry specified by given iterator
203  bool erase(const iterator& it);
204 
205  //- Erase an hashed entry specified by given key if in table
206  bool erase(const Key& key);
207 
208  //- Resize the hash table for efficiency
209  void resize(const label newSize);
210 
211  //- Remove entries in the given hash table from this hash table
212  // Return the number of elements removed
213  label erase(const StaticHashTable<T, Key, Hash>&);
214 
215  //- Clear all entries from table
216  void clear();
217 
218  //- Clear the table entries and the table itself.
219  // Equivalent to clear() followed by resize(1)
220  void clearStorage();
221 
222  //- Transfer the contents of the argument table into this table
223  // and annull the argument table.
225 
226  //- Transfer contents to the Xfer container
228 
229 
230  // Member Operators
231 
232  //- Find and return an hashed entry
233  inline T& operator[](const Key&);
234 
235  //- Find and return an hashed entry
236  inline const T& operator[](const Key&) const;
237 
238  //- Find and return an hashed entry, create it null if not present.
239  inline T& operator()(const Key&);
240 
241  //- Assignment
243 
244  //- Equality. Two hash tables are equal if all contents of first are
245  // also in second and vice versa.
246  bool operator==(const StaticHashTable<T, Key, Hash>&) const;
247 
248  //- The opposite of the equality operation.
249  bool operator!=(const StaticHashTable<T, Key, Hash>&) const;
250 
251  // STL type definitions
252 
253  //- Type of values the StaticHashTable contains.
254  typedef T value_type;
255 
256  //- Type that can be used for storing into StaticHashTable::value_type
257  // objects. This type is usually List::value_type&.
258  typedef T& reference;
259 
260  //- Type that can be used for storing into constant
261  // StaticHashTable::value_type objects. This type is usually const
262  // StaticHashTable::value_type&.
263  typedef const T& const_reference;
264 
265  //- The type that can represent the size of a StaticHashTable.
266  typedef label size_type;
267 
268 
269  // STL iterator
270 
271  //- An STL iterator
272  template<class TRef, class TableRef>
273  class Iterator
274  {
275  friend class StaticHashTable;
276 
277 # ifndef __INTEL_COMPILER
278  template<class TRef2, class TableRef2>
279  friend class Iterator;
280 # endif
281 
282  // Private data
283 
284  //- Reference to the StaticHashTable this is an iterator for
285  TableRef hashTable_;
286 
287  //- Current hash index
288  label hashIndex_;
289 
290  //- Index of current element at hashIndex
291  label elemIndex_;
292 
293  public:
294 
295  // Constructors
296 
297  //- Construct from hash table, hash index and element index
298  inline Iterator
299  (
300  TableRef,
301  label hashIndex_,
302  label elemIndex_
303  );
304 
305  //- Construct from the non-const iterator
306  inline Iterator(const iterator&);
307 
308 
309  // Member operators
310 
311  inline void operator=(const iterator&);
312 
313  inline bool operator==(const iterator&) const;
314  inline bool operator==(const const_iterator&) const;
315 
316  inline bool operator!=(const iterator&) const;
317  inline bool operator!=(const const_iterator&) const;
318 
319  inline TRef operator*();
320  inline TRef operator()();
321 
322  inline Iterator& operator++();
323  inline Iterator operator++(int);
324 
325  inline const Key& key() const;
326  };
327 
328 
329  //- iterator set to the beginning of the StaticHashTable
330  inline iterator begin();
331 
332  //- iterator set to beyond the end of the StaticHashTable
333  inline const iterator& end();
334 
335  //- const_iterator set to the beginning of the StaticHashTable
336  inline const_iterator cbegin() const;
337 
338  //- const_iterator set to beyond the end of the StaticHashTable
339  inline const const_iterator& cend() const;
340 
341  //- const_iterator set to the beginning of the StaticHashTable
342  inline const_iterator begin() const;
343 
344  //- const_iterator set to beyond the end of the StaticHashTable
345  inline const const_iterator& end() const;
346 
347  // IOstream Operator
348 
349  friend Istream& operator>> <T, Key, Hash>
350  (
351  Istream&,
353  );
354 
355  friend Ostream& operator<< <T, Key, Hash>
356  (
357  Ostream&,
359  );
360 
361 
362 private:
363 
364  //- iterator returned by end()
365  iterator endIter_;
366 
367  //- const_iterator returned by end()
368  const_iterator endConstIter_;
369 };
370 
371 
372 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
373 
374 } // End namespace Foam
375 
376 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
377 
378 # include "StaticHashTableI.H"
379 
380 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
381 
382 #ifndef NoStaticHashTableC
383 #ifdef NoRepository
384 # include "StaticHashTable.C"
385 #endif
386 #endif
387 
388 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
389 
390 #endif
391 
392 // ************************ vim: set sw=4 sts=4 et: ************************ //