FreeFOAM The Cross-Platform CFD Toolkit
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 | 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::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 <OpenFOAM/label.H>
48 #include <OpenFOAM/uLabel.H>
49 #include <OpenFOAM/word.H>
50 #include <OpenFOAM/Xfer.H>
51 #include <OpenFOAM/className.H>
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 T, class Key, class Hash>
66 Istream& operator>>(Istream&, HashTable<T, Key, Hash>&);
67 
68 template<class T, class Key, class Hash>
69 Ostream& operator<<(Ostream&, const HashTable<T, Key, Hash>&);
70 
71 
72 /*---------------------------------------------------------------------------*\
73  Class HashTableName Declaration
74 \*---------------------------------------------------------------------------*/
75 
76 TemplateName(HashTable);
77 
78 
79 /*---------------------------------------------------------------------------*\
80  Class HashTable Declaration
81 \*---------------------------------------------------------------------------*/
82 
83 template<class T, class Key=word, class Hash=string::hash>
84 class HashTable
85 :
86  public HashTableName
87 {
88  // Private data type for table entries
89 
90  struct hashedEntry
91  {
92  //- The lookup key
93  Key key_;
94 
95  //- Pointer to next hashedEntry in sub-list
96  hashedEntry* next_;
97 
98  //- The data object
99  T obj_;
100 
101  //- Constructors
102 
103  //- Construct given key, next pointer and object
104  inline hashedEntry
105  (
106  const Key&,
107  hashedEntry* next,
108  const T& newEntry
109  );
110 
111  //- Dissallow construction as copy
112  hashedEntry(const hashedEntry&);
113  };
114 
115 
116  // Private data: size of table, the table and current number of elements
117 
118  //- The current number of elements in table
119  label nElmts_;
120 
121  //- Number of primary entries allocated in table (not necessarily used)
122  label tableSize_;
123 
124  //- The table of primary entries
125  hashedEntry** table_;
126 
127 
128  // Private Member Functions
129 
130  //- Return a canonical (power-of-two) size
131  static label canonicalSize(const label);
132 
133  //- Return the hash index of the Key within the current table size.
134  // No checks for zero-sized tables.
135  inline label hashKeyIndex(const Key&) const;
136 
137  //- Assign a new hashedEntry to a possibly already existing key
138  bool set(const Key&, const T& newElmt, bool protect);
139 
140 
141 public:
142 
143  //- Declare friendship with the HashPtrTable class
144  template<class T2, class Key2, class Hash2>
145  friend class HashPtrTable;
146 
147 
148  // Forward declaration of STL iterators
149 
150  class iterator;
151  friend class iterator;
152 
154  friend class const_iterator;
155 
156 
157  // Constructors
158 
159  //- Construct given initial table size
160  HashTable(const label size = 128);
161 
162  //- Construct from Istream
163  HashTable(Istream&, const label size = 128);
164 
165  //- Construct as copy
167 
168  //- Construct by transferring the parameter contents
170 
171 
172  // Destructor
173 
174  ~HashTable();
175 
176 
177  // Member Functions
178 
179  // Access
180 
181  //- Return number of elements in table.
182  inline label size() const;
183 
184  //- Return true if the hash table is empty
185  inline bool empty() const;
186 
187  //- Return true if hashedEntry is found in table
188  bool found(const Key&) const;
189 
190  //- Find and return an iterator set at the hashedEntry
191  // If not found iterator = end()
192  iterator find(const Key&);
193 
194  //- Find and return an const_iterator set at the hashedEntry
195  // If not found iterator = end()
196  const_iterator find(const Key&) const;
197 
198  //- Return the table of contents
199  List<Key> toc() const;
200 
201  //- Return the table of contents as a sorted list
202  List<Key> sortedToc() const;
203 
204  //- Print information
205  Ostream& printInfo(Ostream&) const;
206 
207  // Edit
208 
209  //- Insert a new hashedEntry
210  inline bool insert(const Key&, const T& newElmt);
211 
212  //- Assign a new hashedEntry, overwriting existing entries
213  inline bool set(const Key&, const T& newElmt);
214 
215  //- Erase an hashedEntry specified by given iterator
216  bool erase(const iterator&);
217 
218  //- Erase an hashedEntry specified by given key if in table
219  bool erase(const Key&);
220 
221  //- Remove entries given by the listed keys from this HashTable
222  // Return the number of elements removed
223  label erase(const UList<Key>&);
224 
225  //- Remove entries given by the given keys from this HashTable
226  // Return the number of elements removed.
227  // The parameter HashTable needs the same type of key, but the
228  // type of values held and the hashing function are arbitrary.
229  template<class AnyType, class AnyHash>
231 
232  //- Resize the hash table for efficiency
233  void resize(const label newSize);
234 
235  //- Clear all entries from table
236  void clear();
237 
238  //- Clear the table entries and the table itself.
239  // Equivalent to clear() followed by resize(0)
240  void clearStorage();
241 
242  //- Transfer the contents of the argument table into this table
243  // and annull the argument table.
245 
246  //- Transfer contents to the Xfer container
248 
249 
250  // Member Operators
251 
252  //- Find and return an hashedEntry
253  inline T& operator[](const Key&);
254 
255  //- Find and return an hashedEntry
256  inline const T& operator[](const Key&) const;
257 
258  //- Find and return an hashedEntry, create it null if not present.
259  inline T& operator()(const Key&);
260 
261  //- Assignment
262  void operator=(const HashTable<T, Key, Hash>&);
263 
264  //- Equality. Two hash tables are equal if all contents of first are
265  // also in second and vice versa. So does not depend on table size or
266  // order!
267  bool operator==(const HashTable<T, Key, Hash>&) const;
268 
269  //- The opposite of the equality operation. Takes linear time.
270  bool operator!=(const HashTable<T, Key, Hash>&) const;
271 
272 
273  // STL type definitions
274 
275  //- Type of values the HashTable contains.
276  typedef T value_type;
277 
278  //- Type that can be used for storing into HashTable::value_type
279  // objects. This type is usually List::value_type&.
280  typedef T& reference;
281 
282  //- Type that can be used for storing into constant
283  // HashTable::value_type objects. This type is usually const
284  // HashTable::value_type&.
285  typedef const T& const_reference;
286 
287  //- The type that can represent the size of a HashTable.
288  typedef label size_type;
289 
290 
291  // STL iterator
292 
293  //- An STL-conforming iterator
294  class iterator
295  {
296  friend class HashTable;
297  friend class const_iterator;
298 
299  // Private data
300 
301  //- Reference to the HashTable this is an iterator for
302  HashTable<T, Key, Hash>& hashTable_;
303 
304  //- Current element
305  hashedEntry* elmtPtr_;
306 
307  //- Current hash index
308  label hashIndex_;
309 
310  public:
311 
312  // Constructors
313 
314  //- Construct from hash table, element and hash index
315  inline iterator
316  (
317  HashTable<T, Key, Hash>& curHashTable,
318  hashedEntry* elmt,
319  label hashIndex
320  );
321 
322  // Member operators
323 
324  inline void operator=(const iterator&);
325 
326  inline bool operator==(const iterator&) const;
327  inline bool operator!=(const iterator&) const;
328 
329  inline bool operator==(const const_iterator&) const;
330  inline bool operator!=(const const_iterator&) const;
331 
332  inline T& operator*();
333  inline T& operator()();
334 
335  inline const T& operator*() const;
336  inline const T& operator()() const;
337 
338  inline iterator& operator++();
339  inline iterator operator++(int);
340 
341  inline const Key& key() const;
342  };
343 
344 
345  //- iterator set to the begining of the HashTable
346  inline iterator begin();
347 
348  //- iterator set to beyond the end of the HashTable
349  inline const iterator& end();
350 
351 
352  // STL const_iterator
353 
354  //- An STL-conforming const_iterator
356  {
357  friend class iterator;
358 
359  // Private data
360 
361  //- Reference to the HashTable this is an iterator for
362  const HashTable<T, Key, Hash>& hashTable_;
363 
364  //- Current element
365  const hashedEntry* elmtPtr_;
366 
367  //- Current hash index
368  label hashIndex_;
369 
370 
371  public:
372 
373  // Constructors
374 
375  //- Construct from hash table, element and hash index
376  inline const_iterator
377  (
378  const HashTable<T, Key, Hash>& curHashTable,
379  const hashedEntry* elmt,
380  label hashIndex
381  );
382 
383  //- Construct from the non-const iterator
384  inline const_iterator(const iterator&);
385 
386 
387  // Member operators
388 
389  inline void operator=(const const_iterator&);
390 
391  inline bool operator==(const const_iterator&) const;
392  inline bool operator!=(const const_iterator&) const;
393 
394  inline bool operator==(const iterator&) const;
395  inline bool operator!=(const iterator&) const;
396 
397  inline const T& operator*() const;
398  inline const T& operator()() const;
399 
400  inline const_iterator& operator++();
401  inline const_iterator operator++(int);
402 
403  inline const Key& key() const;
404  };
405 
406 
407  //- const_iterator set to the beginning of the HashTable
408  inline const_iterator cbegin() const;
409 
410  //- const_iterator set to beyond the end of the HashTable
411  inline const const_iterator& cend() const;
412 
413  //- const_iterator set to the beginning of the HashTable
414  inline const_iterator begin() const;
415 
416  //- const_iterator set to beyond the end of the HashTable
417  inline const const_iterator& end() const;
418 
419 
420  // IOstream Operator
421 
422  friend Istream& operator>> <T, Key, Hash>
423  (
424  Istream&,
426  );
427 
428  friend Ostream& operator<< <T, Key, Hash>
429  (
430  Ostream&,
432  );
433 
434 
435 private:
436 
437  //- iterator returned by end()
438  iterator endIter_;
439 
440  //- const_iterator returned by end()
441  const_iterator endConstIter_;
442 };
443 
444 
445 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
446 
447 } // End namespace Foam
448 
449 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
450 
451 # include <OpenFOAM/HashTableI.H>
452 
453 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
454 
455 #ifndef NoHashTableC
456 #ifdef NoRepository
457 # include <OpenFOAM/HashTable.C>
458 #endif
459 #endif
460 
461 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
462 
463 #endif
464 
465 // ************************ vim: set sw=4 sts=4 et: ************************ //