HashTableI.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 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 \*---------------------------------------------------------------------------*/
25 
26 #include "error.H"
27 
28 // * * * * * * * * * * * * * Private Member Classes * * * * * * * * * * * * //
29 
30 template<class T, class Key, class Hash>
32 (
33  const Key& key,
34  hashedEntry* next,
35  const T& obj
36 )
37 :
38  key_(key),
39  next_(next),
40  obj_(obj)
41 {}
42 
43 
44 // * * * * * * * * * * * * Private Member Functions * * * * * * * * * * * * //
45 
46 template<class T, class Key, class Hash>
47 inline Foam::label
49 {
50  // size is power of two - this is the modulus
51  return Hash()(key) & (tableSize_ - 1);
52 }
53 
54 
55 // * * * * * * * * * * * * * * * Member Functions * * * * * * * * * * * * * //
56 
57 template<class T, class Key, class Hash>
59 {
60  return tableSize_;
61 }
62 
63 
64 template<class T, class Key, class Hash>
66 {
67  return nElmts_;
68 }
69 
70 
71 template<class T, class Key, class Hash>
73 {
74  return !nElmts_;
75 }
76 
77 
78 template<class T, class Key, class Hash>
80 (
81  const Key& key,
82  const T& newEntry
83 )
84 {
85  return this->set(key, newEntry, true);
86 }
87 
88 
89 template<class T, class Key, class Hash>
91 (
92  const Key& key,
93  const T& newEntry
94 )
95 {
96  return this->set(key, newEntry, false);
97 }
98 
99 
100 template<class T, class Key, class Hash>
103 {
104  return xferMove(*this);
105 }
106 
107 
108 // * * * * * * * * * * * * * * * Member Operators * * * * * * * * * * * * * //
109 
110 template<class T, class Key, class Hash>
112 {
113  iterator iter = this->find(key);
114 
115  if (iter == this->end())
116  {
117  FatalErrorIn("HashTable<T, Key, Hash>::operator[](const Key&)")
118  << key << " not found in table. Valid entries: "
119  << toc()
120  << exit(FatalError);
121  }
122 
123  return *iter;
124 }
125 
126 
127 template<class T, class Key, class Hash>
128 inline const T& Foam::HashTable<T, Key, Hash>::operator[](const Key& key) const
129 {
130  const_iterator iter = this->find(key);
131 
132  if (iter == this->cend())
133  {
134  FatalErrorIn("HashTable<T, Key, Hash>::operator[](const Key&) const")
135  << key << " not found in table. Valid entries: "
136  << toc()
137  << exit(FatalError);
138  }
139 
140  return *iter;
141 }
142 
143 
144 template<class T, class Key, class Hash>
146 {
147  iterator iter = this->find(key);
148 
149  if (iter == this->end())
150  {
151  this->insert(key, T());
152  return *find(key);
153  }
154  else
155  {
156  return *iter;
157  }
158 }
159 
160 
161 // * * * * * * * * * * * * * * * iterator base * * * * * * * * * * * * * * * //
162 
163 template<class T, class Key, class Hash>
165 :
166  hashTable_(0),
167  entryPtr_(0),
168  hashIndex_(0)
169 {}
170 
171 
172 template<class T, class Key, class Hash>
174 (
175  const HashTable<T, Key, Hash>* hashTbl
176 )
177 :
178  hashTable_(const_cast<HashTable<T, Key, Hash>*>(hashTbl)),
179  entryPtr_(0),
180  hashIndex_(0)
181 {
182  if (hashTable_->nElmts_)
183  {
184  // find first non-NULL table entry
185  while
186  (
187  !(entryPtr_ = hashTable_->table_[hashIndex_])
188  && ++hashIndex_ < hashTable_->tableSize_
189  )
190  {}
191 
192  if (hashIndex_ >= hashTable_->tableSize_)
193  {
194  // make into an end iterator
195  entryPtr_ = 0;
196  hashIndex_ = 0;
197  }
198  }
199 }
200 
201 
202 template<class T, class Key, class Hash>
204 (
205  const HashTable<T, Key, Hash>* hashTbl,
206  const hashedEntry* elmt,
207  const label hashIndex
208 )
209 :
210  hashTable_(const_cast<HashTable<T, Key, Hash>*>(hashTbl)),
211  entryPtr_(const_cast<hashedEntry*>(elmt)),
212  hashIndex_(hashIndex)
213 {}
214 
215 
216 template<class T, class Key, class Hash>
217 inline void
219 {
220  // A negative index is a special value from erase
221  if (hashIndex_ < 0)
222  {
223  // the markPos='-curPos-1', but we wish to continue at 'curPos-1'
224  // thus use '-(markPos+1) -1'
225  hashIndex_ = -(hashIndex_+1) - 1;
226  }
227  else if (entryPtr_)
228  {
229  if (entryPtr_->next_)
230  {
231  // Move to next element on the SLList
232  entryPtr_ = entryPtr_->next_;
233  return;
234  }
235  }
236  // else
237  // {
238  // // if we reach here (entryPtr_ is NULL) it is already at the end()
239  // // we should probably stop
240  // }
241 
242 
243  // Step to the next table entry
244  while
245  (
246  ++hashIndex_ < hashTable_->tableSize_
247  && !(entryPtr_ = hashTable_->table_[hashIndex_])
248  )
249  {}
250 
251  if (hashIndex_ >= hashTable_->tableSize_)
252  {
253  // make into an end iterator
254  entryPtr_ = 0;
255  hashIndex_ = 0;
256  }
257 }
258 
259 
260 template<class T, class Key, class Hash>
261 inline
263 {
264  return entryPtr_->key_;
265 }
266 
267 
268 template<class T, class Key, class Hash>
269 inline T&
271 {
272  return entryPtr_->obj_;
273 }
274 
275 
276 template<class T, class Key, class Hash>
277 inline const T&
279 {
280  return entryPtr_->obj_;
281 }
282 
283 
284 template<class T, class Key, class Hash>
285 inline bool Foam::HashTable<T, Key, Hash>::iteratorBase::operator==
286 (
287  const iteratorBase& iter
288 ) const
289 {
290  return entryPtr_ == iter.entryPtr_;
291 }
292 
293 
294 template<class T, class Key, class Hash>
295 inline bool Foam::HashTable<T, Key, Hash>::iteratorBase::operator!=
296 (
297  const iteratorBase& iter
298 ) const
299 {
300  return entryPtr_ != iter.entryPtr_;
301 }
302 
303 
304 template<class T, class Key, class Hash>
305 inline bool Foam::HashTable<T, Key, Hash>::iteratorBase::operator==
306 (
307  const iteratorEnd&
308 ) const
309 {
310  return !entryPtr_;
311 }
312 
313 
314 template<class T, class Key, class Hash>
315 inline bool Foam::HashTable<T, Key, Hash>::iteratorBase::operator!=
316 (
317  const iteratorEnd&
318 ) const
319 {
320  return entryPtr_;
321 }
322 
323 
324 // * * * * * * * * * * * * * * * * STL iterator * * * * * * * * * * * * * * //
325 
326 template<class T, class Key, class Hash>
328 :
329  iteratorBase()
330 {}
331 
332 
333 template<class T, class Key, class Hash>
335 (
336  const iteratorEnd&
337 )
338 :
339  iteratorBase()
340 {}
341 
342 
343 template<class T, class Key, class Hash>
345 (
346  HashTable<T, Key, Hash>* hashTbl
347 )
348 :
349  iteratorBase(hashTbl)
350 {}
351 
352 
353 template<class T, class Key, class Hash>
355 (
356  HashTable<T, Key, Hash>* hashTbl,
357  hashedEntry* elmt,
358  const label hashIndex
359 )
360 :
361  iteratorBase(hashTbl, elmt, hashIndex)
362 {}
363 
364 
365 template<class T, class Key, class Hash>
366 inline T&
368 {
369  return this->object();
370 }
371 
372 
373 template<class T, class Key, class Hash>
374 inline T&
376 {
377  return this->object();
378 }
379 
380 
381 template<class T, class Key, class Hash>
382 inline const T&
384 {
385  return this->cobject();
386 }
387 
388 
389 template<class T, class Key, class Hash>
390 inline const T&
392 {
393  return this->cobject();
394 }
395 
396 
397 template<class T, class Key, class Hash>
398 inline
401 {
402  this->increment();
403  return *this;
404 }
405 
406 
407 template<class T, class Key, class Hash>
410 {
411  iterator old = *this;
412  this->increment();
413  return old;
414 }
415 
416 
417 template<class T, class Key, class Hash>
420 {
421  return iterator(this);
422 }
423 
424 
425 // * * * * * * * * * * * * * * * STL const_iterator * * * * * * * * * * * * * //
426 
427 template<class T, class Key, class Hash>
429 :
430  iteratorBase()
431 {}
432 
433 
434 template<class T, class Key, class Hash>
436 (
438 )
439 :
440  iteratorBase(iter)
441 {}
442 
443 
444 template<class T, class Key, class Hash>
446 (
447  const iteratorEnd&
448 )
449 :
450  iteratorBase()
451 {}
452 
453 
454 template<class T, class Key, class Hash>
456 (
457  const HashTable<T, Key, Hash>* hashTbl
458 )
459 :
460  iteratorBase(hashTbl)
461 {}
462 
463 
464 template<class T, class Key, class Hash>
466 (
467  const HashTable<T, Key, Hash>* hashTbl,
468  const hashedEntry* elmt,
469  const label hashIndex
470 )
471 :
472  iteratorBase(hashTbl, elmt, hashIndex)
473 {}
474 
475 
476 template<class T, class Key, class Hash>
477 inline const T&
479 {
480  return this->cobject();
481 }
482 
483 
484 template<class T, class Key, class Hash>
485 inline const T&
487 {
488  return this->cobject();
489 }
490 
491 
492 template<class T, class Key, class Hash>
493 inline
496 {
497  this->increment();
498  return *this;
499 }
500 
501 
502 template<class T, class Key, class Hash>
505 {
506  const_iterator old = *this;
507  this->increment();
508  return old;
509 }
510 
511 
512 template<class T, class Key, class Hash>
515 {
516  return const_iterator(this);
517 }
518 
519 
520 template<class T, class Key, class Hash>
523 {
524  return this->cbegin();
525 }
526 
527 
528 // ************************************************************************* //
label capacity() const
The size of the underlying table.
Definition: HashTableI.H:58
const_iterator cbegin() const
const_iterator set to the beginning of the HashTable
Definition: HashTableI.H:514
An STL-conforming const_iterator.
Definition: HashTable.H:470
void T(FieldField< Field, Type > &f1, const FieldField< Field, Type > &f2)
bool insert(const Key &, const T &newElmt)
Insert a new hashedEntry.
Definition: HashTableI.H:80
An STL-conforming iterator.
Definition: HashTable.H:415
An STL-conforming hash table.
Definition: HashTable.H:61
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
iteratorBase()
Construct null - equivalent to an &#39;end&#39; position.
Definition: HashTableI.H:164
The iterator base for HashTable.
Definition: HashTable.H:343
errorManipArg< error, int > exit(error &err, const int errNo=1)
Definition: errorManip.H:124
const T & operator*() const
Return referenced hash value.
Definition: HashTableI.H:478
Xfer< T > xferMove(T &)
const volScalarField & T
Definition: createFields.H:25
const T & cobject() const
Return const access to referenced object.
Definition: HashTableI.H:278
T & operator()(const Key &)
Find and return a hashedEntry, create it null if not present.
Definition: HashTableI.H:145
static iteratorEnd cend()
iteratorEnd set to beyond the end of any HashTable
Definition: HashTable.H:100
iterator()
Construct null (end iterator)
Definition: HashTableI.H:327
label size() const
Return number of elements in table.
Definition: HashTableI.H:65
List< Key > toc() const
Return the table of contents.
Definition: HashTable.C:201
#define FatalErrorIn(functionName)
Report an error message using Foam::FatalError.
Definition: error.H:314
T & operator[](const Key &)
Find and return a hashedEntry.
Definition: HashTableI.H:111
A zero-sized end iterator.
Definition: HashTable.H:92
error FatalError
Xfer< HashTable< T, Key, Hash > > xfer()
Transfer contents to the Xfer container.
Definition: HashTableI.H:102
const_iterator & operator++()
Definition: HashTableI.H:495
static iteratorEnd end()
iteratorEnd set to beyond the end of any HashTable
Definition: HashTable.H:106
const_iterator()
Construct null (end iterator)
Definition: HashTableI.H:428
T & operator*()
Return referenced hash value.
Definition: HashTableI.H:367
iterator begin()
Iterator set to the beginning of the HashTable.
Definition: HashTableI.H:419
iterator find(const Key &)
Find and return an iterator set at the hashedEntry.
Definition: HashTable.C:139
bool empty() const
Return true if the hash table is empty.
Definition: HashTableI.H:72
const Key & key() const
Return the Key corresponding to the iterator.
Definition: HashTableI.H:262
void increment()
Increment to the next position.
Definition: HashTableI.H:218
T & object()
Return non-const access to referenced object.
Definition: HashTableI.H:270
const T & operator()() const
Definition: HashTableI.H:486