FreeFOAM The Cross-Platform CFD Toolkit
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) 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 \*---------------------------------------------------------------------------*/
25 
26 #include <OpenFOAM/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& newEntry
36 )
37 :
38  key_(key),
39  next_(next),
40  obj_(newEntry)
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>
58 inline Foam::label Foam::HashTable<T, Key, Hash>::size() const
59 {
60  return nElmts_;
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  const Key& key,
75  const T& newEntry
76 )
77 {
78  return set(key, newEntry, true);
79 }
80 
81 
82 template<class T, class Key, class Hash>
84 (
85  const Key& key,
86  const T& newEntry
87 )
88 {
89  return set(key, newEntry, false);
90 }
91 
92 
93 template<class T, class Key, class Hash>
96 {
97  return xferMove(*this);
98 }
99 
100 
101 // * * * * * * * * * * * * * * * Member Operators * * * * * * * * * * * * * //
102 
103 template<class T, class Key, class Hash>
105 {
106  iterator iter = find(key);
107 
108  if (iter == end())
109  {
110  FatalErrorIn("HashTable<T, Key, Hash>::operator[](const Key&)")
111  << key << " not found in table. Valid entries: "
112  << toc()
113  << exit(FatalError);
114  }
115 
116  return *iter;
117 }
118 
119 
120 template<class T, class Key, class Hash>
121 inline const T& Foam::HashTable<T, Key, Hash>::operator[](const Key& key) const
122 {
123  const_iterator iter = find(key);
124 
125  if (iter == cend())
126  {
127  FatalErrorIn("HashTable<T, Key, Hash>::operator[](const Key&) const")
128  << key << " not found in table. Valid entries: "
129  << toc()
130  << exit(FatalError);
131  }
132 
133  return *iter;
134 }
135 
136 
137 template<class T, class Key, class Hash>
139 {
140  iterator iter = find(key);
141 
142  if (iter == end())
143  {
144  insert(key, T());
145  return *find(key);
146  }
147  else
148  {
149  return *iter;
150  }
151 }
152 
153 
154 // * * * * * * * * * * * * * * * * STL iterator * * * * * * * * * * * * * * //
155 
156 template<class T, class Key, class Hash>
158 (
159  HashTable<T, Key, Hash>& hashTbl,
160  hashedEntry* elmt,
161  label hashIndex
162 )
163 :
164  hashTable_(hashTbl),
165  elmtPtr_(elmt),
166  hashIndex_(hashIndex)
167 {}
168 
169 
170 template<class T, class Key, class Hash>
172 (
173  const iterator& iter
174 )
175 {
176  elmtPtr_ = iter.elmtPtr_;
177  hashIndex_ = iter.hashIndex_;
178 }
179 
180 
181 template<class T, class Key, class Hash>
182 inline bool Foam::HashTable<T, Key, Hash>::iterator::operator==
183 (
184  const iterator& iter
185 ) const
186 {
187  return elmtPtr_ == iter.elmtPtr_;
188 }
189 
190 
191 template<class T, class Key, class Hash>
192 inline bool Foam::HashTable<T, Key, Hash>::iterator::operator!=
193 (
194  const iterator& iter
195 ) const
196 {
197  return elmtPtr_ != iter.elmtPtr_;
198 }
199 
200 
201 template<class T, class Key, class Hash>
202 inline bool Foam::HashTable<T, Key, Hash>::iterator::operator==
203 (
204  const const_iterator& iter
205 ) const
206 {
207  return elmtPtr_ == iter.elmtPtr_;
208 }
209 
210 
211 template<class T, class Key, class Hash>
212 inline bool Foam::HashTable<T, Key, Hash>::iterator::operator!=
213 (
214  const const_iterator& iter
215 ) const
216 {
217  return elmtPtr_ != iter.elmtPtr_;
218 }
219 
220 
221 template<class T, class Key, class Hash>
222 inline T&
224 {
225  return elmtPtr_->obj_;
226 }
227 
228 
229 template<class T, class Key, class Hash>
230 inline T&
232 {
233  return elmtPtr_->obj_;
234 }
235 
236 
237 template<class T, class Key, class Hash>
238 inline const T&
240 {
241  return elmtPtr_->obj_;
242 }
243 
244 
245 template<class T, class Key, class Hash>
246 inline const T&
248 {
249  return elmtPtr_->obj_;
250 }
251 
252 
253 template<class T, class Key, class Hash>
254 inline
257 {
258  // Check for special value from erase. (sets hashIndex to -1)
259  if (hashIndex_ >= 0)
260  {
261  // Do we have additional elements on the SLList?
262  if (elmtPtr_ && elmtPtr_->next_)
263  {
264  elmtPtr_ = elmtPtr_->next_;
265  return *this;
266  }
267  }
268 
269  // Step to the next table entry
270  while
271  (
272  ++hashIndex_ < hashTable_.tableSize_
273  && !(elmtPtr_ = hashTable_.table_[hashIndex_])
274  )
275  {}
276 
277  if (hashIndex_ == hashTable_.tableSize_)
278  {
279  // make end iterator
280  elmtPtr_ = 0;
281  hashIndex_ = 0;
282  }
283  return *this;
284 }
285 
286 
287 template<class T, class Key, class Hash>
289 Foam::HashTable<T, Key, Hash>::iterator::operator++
290 (
291  int
292 )
293 {
294  iterator tmp = *this;
295  ++*this;
296  return tmp;
297 }
298 
299 
300 template<class T, class Key, class Hash>
301 inline
303 {
304  return elmtPtr_->key_;
305 }
306 
307 
308 template<class T, class Key, class Hash>
311 {
312  label i = 0;
313 
314  if (nElmts_)
315  {
316  while (table_ && !table_[i] && ++i < tableSize_)
317  {}
318  }
319  else
320  {
321  i = tableSize_;
322  }
323 
324  if (i == tableSize_)
325  {
326 # ifdef FULLDEBUG
327  if (debug)
328  {
329  Info<< "HashTable is empty\n";
330  }
331 # endif
332 
334  }
335  else
336  {
337  return iterator(*this, table_[i], i);
338  }
339 }
340 
341 
342 template<class T, class Key, class Hash>
343 inline const typename Foam::HashTable<T, Key, Hash>::iterator&
345 {
347 }
348 
349 
350 // * * * * * * * * * * * * * * * STL const_iterator * * * * * * * * * * * * * //
351 
352 template<class T, class Key, class Hash>
354 (
355  const HashTable<T, Key, Hash>& hashTbl,
356  const hashedEntry* elmt,
357  label hashIndex
358 )
359 :
360  hashTable_(hashTbl),
361  elmtPtr_(elmt),
362  hashIndex_(hashIndex)
363 {}
364 
365 
366 template<class T, class Key, class Hash>
368 (
369  const iterator& iter
370 )
371 :
372  hashTable_(iter.hashTable_),
373  elmtPtr_(iter.elmtPtr_),
374  hashIndex_(iter.hashIndex_)
375 {}
376 
377 
378 template<class T, class Key, class Hash>
380 (
381  const const_iterator& iter
382 )
383 {
384  elmtPtr_ = iter.elmtPtr_;
385  hashIndex_ = iter.hashIndex_;
386 }
387 
388 
389 template<class T, class Key, class Hash>
390 inline bool Foam::HashTable<T, Key, Hash>::const_iterator::operator==
391 (
392  const const_iterator& iter
393 ) const
394 {
395  return elmtPtr_ == iter.elmtPtr_;
396 }
397 
398 
399 template<class T, class Key, class Hash>
400 inline bool Foam::HashTable<T, Key, Hash>::const_iterator::operator!=
401 (
402  const const_iterator& iter
403 ) const
404 {
405  return elmtPtr_ != iter.elmtPtr_;
406 }
407 
408 
409 template<class T, class Key, class Hash>
410 inline bool Foam::HashTable<T, Key, Hash>::const_iterator::operator==
411 (
412  const iterator& iter
413 ) const
414 {
415  return elmtPtr_ == iter.elmtPtr_;
416 }
417 
418 
419 template<class T, class Key, class Hash>
420 inline bool Foam::HashTable<T, Key, Hash>::const_iterator::operator!=
421 (
422  const iterator& iter
423 ) const
424 {
425  return elmtPtr_ != iter.elmtPtr_;
426 }
427 
428 
429 template<class T, class Key, class Hash>
430 inline const T&
432 {
433  return elmtPtr_->obj_;
434 }
435 
436 template<class T, class Key, class Hash>
437 inline const T&
439 {
440  return elmtPtr_->obj_;
441 }
442 
443 
444 template<class T, class Key, class Hash>
445 inline
448 {
449  if
450  (
451  !(elmtPtr_ = elmtPtr_->next_)
452  && ++hashIndex_ < hashTable_.tableSize_
453  && !(elmtPtr_ = hashTable_.table_[hashIndex_])
454  )
455  {
456  while
457  (
458  ++hashIndex_ < hashTable_.tableSize_
459  && !(elmtPtr_ = hashTable_.table_[hashIndex_])
460  )
461  {}
462  }
463 
464  return *this;
465 }
466 
467 
468 template<class T, class Key, class Hash>
470 Foam::HashTable<T, Key, Hash>::const_iterator::operator++
471 (
472  int
473 )
474 {
475  const_iterator tmp = *this;
476  ++*this;
477  return tmp;
478 }
479 
480 
481 template<class T, class Key, class Hash>
482 inline
484 {
485  return elmtPtr_->key_;
486 }
487 
488 
489 template<class T, class Key, class Hash>
492 {
493  label i = 0;
494 
495  if (nElmts_)
496  {
497  while (table_ && !table_[i] && ++i < tableSize_)
498  {}
499  }
500  else
501  {
502  i = tableSize_;
503  }
504 
505  if (i == tableSize_)
506  {
507 # ifdef FULLDEBUG
508  if (debug)
509  {
510  Info<< "HashTable is empty\n";
511  }
512 # endif
513 
515  }
516  else
517  {
518  return const_iterator(*this, table_[i], i);
519  }
520 }
521 
522 
523 template<class T, class Key, class Hash>
526 {
528 }
529 
530 
531 template<class T, class Key, class Hash>
534 {
535  return this->cbegin();
536 }
537 
538 
539 template<class T, class Key, class Hash>
542 {
544 }
545 
546 
547 // ************************ vim: set sw=4 sts=4 et: ************************ //