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