FreeFOAM The Cross-Platform CFD Toolkit
StaticHashTable.C
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 #ifndef StaticHashTable_C
27 #define StaticHashTable_C
28 
29 #include "StaticHashTable.H"
30 #include <OpenFOAM/List.H>
31 #include <OpenFOAM/IOstreams.H>
32 
33 // * * * * * * * * * * * * Private Member Functions * * * * * * * * * * * * //
34 
35 template<class T, class Key, class Hash>
36 Foam::label Foam::StaticHashTable<T, Key, Hash>::canonicalSize(const label size)
37 {
38  if (size < 1)
39  {
40  return 0;
41  }
42 
43  // enforce power of two
44  unsigned int goodSize = size;
45 
46  if (goodSize & (goodSize - 1))
47  {
48  // brute-force is fast enough
49  goodSize = 1;
50  while (goodSize < unsigned(size))
51  {
52  goodSize <<= 1;
53  }
54  }
55 
56  return goodSize;
57 }
58 
59 
60 // * * * * * * * * * * * * * * * * Constructors * * * * * * * * * * * * * * //
61 
62 // Construct given initial table size
63 template<class T, class Key, class Hash>
65 :
66  StaticHashTableName(),
67  keys_(canonicalSize(size)),
68  objects_(keys_.size()),
69  nElmts_(0),
70  endIter_(*this, keys_.size(), 0),
71  endConstIter_(*this, keys_.size(), 0)
72 {
73  if (size < 1)
74  {
76  (
77  "StaticHashTable<T, Key, Hash>::StaticHashTable(const label size)"
78  ) << "Illegal size " << size << " for StaticHashTable."
79  << " Minimum size is 1" << abort(FatalError);
80  }
81 }
82 
83 
84 // Construct as copy
85 template<class T, class Key, class Hash>
87 (
89 )
90 :
91  StaticHashTableName(),
92  keys_(ht.keys_),
93  objects_(ht.objects_),
94  nElmts_(ht.nElmts_),
95  endIter_(*this, keys_.size(), 0),
96  endConstIter_(*this, keys_.size(), 0)
97 {}
98 
99 
100 
101 template<class T, class Key, class Hash>
103 (
105 )
106 :
107  StaticHashTableName(),
108  keys_(0),
109  objects_(0),
110  nElmts_(0),
111  endIter_(*this, 0, 0),
112  endConstIter_(*this, 0, 0)
113 {
114  transfer(ht());
115 }
116 
117 
118 // * * * * * * * * * * * * * * * * Destructor * * * * * * * * * * * * * * * //
119 
120 template<class T, class Key, class Hash>
122 {}
123 
124 
125 // * * * * * * * * * * * * * * * Member Functions * * * * * * * * * * * * * //
126 
127 template<class T, class Key, class Hash>
129 {
130  if (nElmts_)
131  {
132  const label hashIdx = hashKeyIndex(key);
133  const List<Key>& localKeys = keys_[hashIdx];
134 
135  forAll(localKeys, elemIdx)
136  {
137  if (key == localKeys[elemIdx])
138  {
139  return true;
140  }
141  }
142  }
143 
144 # ifdef FULLDEBUG
145  if (debug)
146  {
147  Info<< "StaticHashTable<T, Key, Hash>::found(const Key&) : "
148  << "Entry " << key << " not found in hash table\n";
149  }
150 # endif
151 
152  return false;
153 }
154 
155 
156 template<class T, class Key, class Hash>
159 (
160  const Key& key
161 )
162 {
163  if (nElmts_)
164  {
165  const label hashIdx = hashKeyIndex(key);
166  const List<Key>& localKeys = keys_[hashIdx];
167 
168  forAll(localKeys, elemIdx)
169  {
170  if (key == localKeys[elemIdx])
171  {
172  return iterator(*this, hashIdx, elemIdx);
173  }
174  }
175  }
176 
177 # ifdef FULLDEBUG
178  if (debug)
179  {
180  Info<< "StaticHashTable<T, Key, Hash>::find(const Key&) : "
181  << "Entry " << key << " not found in hash table\n";
182  }
183 # endif
184 
185  return end();
186 }
187 
188 
189 template<class T, class Key, class Hash>
192 (
193  const Key& key
194 ) const
195 {
196  if (nElmts_)
197  {
198  const label hashIdx = hashKeyIndex(key);
199  const List<Key>& localKeys = keys_[hashIdx];
200 
201  forAll(localKeys, elemIdx)
202  {
203  if (key == localKeys[elemIdx])
204  {
205  return const_iterator(*this, hashIdx, elemIdx);
206  }
207  }
208  }
209 
210 # ifdef FULLDEBUG
211  if (debug)
212  {
213  Info<< "StaticHashTable<T, Key, Hash>::find(const Key&) const : "
214  << "Entry " << key << " not found in hash table\n";
215  }
216 # endif
217 
218  return cend();
219 }
220 
221 
222 // Return the table of contents
223 template<class T, class Key, class Hash>
225 {
226  List<Key> tofc(nElmts_);
227  label i = 0;
228 
229  for (const_iterator iter = cbegin(); iter != cend(); ++iter)
230  {
231  tofc[i++] = iter.key();
232  }
233 
234  return tofc;
235 }
236 
237 
238 template<class T, class Key, class Hash>
240 (
241  const Key& key,
242  const T& newEntry,
243  const bool protect
244 )
245 {
246  const label hashIdx = hashKeyIndex(key);
247  List<Key>& localKeys = keys_[hashIdx];
248 
249  label existing = localKeys.size();
250  forAll(localKeys, elemIdx)
251  {
252  if (key == localKeys[elemIdx])
253  {
254  existing = elemIdx;
255  break;
256  }
257  }
258 
259  if (existing == localKeys.size())
260  {
261  // not found, append
262  List<T>& localObjects = objects_[hashIdx];
263 
264  localKeys.setSize(existing+1);
265  localObjects.setSize(existing+1);
266 
267  localKeys[existing] = key;
268  localObjects[existing] = newEntry;
269 
270  nElmts_++;
271  }
272  else if (protect)
273  {
274  // found - but protected from overwriting
275  // this corresponds to the STL 'insert' convention
276 # ifdef FULLDEBUG
277  if (debug)
278  {
279  Info<< "StaticHashTable<T, Key, Hash>::set"
280  "(const Key& key, T newEntry, true) : "
281  "Cannot insert " << key << " already in hash table\n";
282  }
283 # endif
284  return false;
285  }
286  else
287  {
288  // found - overwrite existing entry
289  // this corresponds to the Perl convention
290  objects_[hashIdx][existing] = newEntry;
291  }
292 
293  return true;
294 }
295 
296 
297 template<class T, class Key, class Hash>
299 {
300  if (cit != end())
301  {
302  List<Key>& localKeys = keys_[cit.hashIndex_];
303  List<T>& localObjects = objects_[cit.hashIndex_];
304 
305  // Copy down
306  for (label i = cit.elemIndex_+1; i < localKeys.size(); i++)
307  {
308  localKeys[i-1] = localKeys[i];
309  localObjects[i-1] = localObjects[i];
310  }
311  localKeys.setSize(localKeys.size()-1);
312  localObjects.setSize(localObjects.size()-1);
313 
314  // adjust iterator after erase
315  iterator& it = const_cast<iterator&>(cit);
316 
317  it.elemIndex_--;
318  if (it.elemIndex_ < 0)
319  {
320  // No previous element in the local list
321 
322  // Search back for previous non-zero table entry
323  while (--it.hashIndex_ >= 0 && !objects_[it.hashIndex_].size())
324  {}
325 
326  if (it.hashIndex_ >= 0)
327  {
328  // The last element in the local list
329  it.elemIndex_ = objects_[it.hashIndex_].size() - 1;
330  }
331  else
332  {
333  // No previous found. Mark with special value which is
334  // - not end()
335  // - handled by operator++
336  it.hashIndex_ = -1;
337  it.elemIndex_ = 0;
338  }
339  }
340 
341  nElmts_--;
342 
343 # ifdef FULLDEBUG
344  if (debug)
345  {
346  Info<< "StaticHashTable<T, Key, Hash>::erase(iterator&) : "
347  << "hashedEntry removed.\n";
348  }
349 # endif
350 
351  return true;
352  }
353  else
354  {
355 # ifdef FULLDEBUG
356  if (debug)
357  {
358  Info<< "StaticHashTable<T, Key, Hash>::erase(iterator&) : "
359  << "cannot remove hashedEntry from hash table\n";
360  }
361 # endif
362 
363  return false;
364  }
365 }
366 
367 
368 template<class T, class Key, class Hash>
370 {
371  iterator it = find(key);
372 
373  if (it != end())
374  {
375  return erase(it);
376  }
377  else
378  {
379  return false;
380  }
381 }
382 
383 
384 template<class T, class Key, class Hash>
386 (
388 )
389 {
390  label count = 0;
391 
392  // Remove rhs elements from this table
393  // NOTE: could optimize depending on which hash is smaller
394  for (iterator iter = this->begin(); iter != this->end(); ++iter)
395  {
396  if (rhs.found(iter.key()) && erase(iter))
397  {
398  count++;
399  }
400  }
401 
402  return count;
403 }
404 
405 
406 template<class T, class Key, class Hash>
408 {
409  label newSize = canonicalSize(sz);
410 
411  if (newSize == keys_.size())
412  {
413 # ifdef FULLDEBUG
414  if (debug)
415  {
416  Info<< "StaticHashTable<T, Key, Hash>::resize(const label) : "
417  << "new table size == old table size\n";
418  }
419 # endif
420 
421  return;
422  }
423 
424  if (newSize < 1)
425  {
427  (
428  "StaticHashTable<T, Key, Hash>::resize(const label)"
429  ) << "Illegal size " << newSize << " for StaticHashTable."
430  << " Minimum size is 1" << abort(FatalError);
431  }
432 
433 
434  StaticHashTable<T, Key, Hash> newTable(newSize);
435 
436  for (const_iterator iter = cbegin(); iter != cend(); ++iter)
437  {
438  newTable.insert(iter.key(), *iter);
439  }
440 
441  transfer(newTable);
442 
443  // Adapt end() iterators
444  endIter_.hashIndex_ = keys_.size();
445  endConstIter_.hashIndex_ = keys_.size();
446 }
447 
448 
449 template<class T, class Key, class Hash>
451 {
452  forAll(keys_, hashIdx)
453  {
454  keys_[hashIdx].clear();
455  objects_[hashIdx].clear();
456  }
457 
458  nElmts_ = 0;
459 }
460 
461 
462 template<class T, class Key, class Hash>
464 {
465  clear();
466  resize(1);
467 }
468 
469 
470 
471 template<class T, class Key, class Hash>
473 (
475 )
476 {
477  // Remove existing elements
478  clear();
479 
480  // Copy data from ht
481  keys_.transfer(ht.keys_);
482  objects_.transfer(ht.objects_);
483 
484  nElmts_ = ht.nElmts_;
485  ht.nElmts_ = 0;
486 
487  // Adapt end() iterators
488  endIter_.hashIndex_ = keys_.size();
489  endConstIter_.hashIndex_ = keys_.size();
490 
491  ht.endIter_.hashIndex_ = 0;
492  ht.endConstIter_.hashIndex_ = 0;
493 }
494 
495 
496 // * * * * * * * * * * * * * * * Member Operators * * * * * * * * * * * * * //
497 
498 template<class T, class Key, class Hash>
500 (
502 )
503 {
504  // Check for assignment to self
505  if (this == &rhs)
506  {
508  (
509  "StaticHashTable<T, Key, Hash>::operator="
510  "(const StaticHashTable<T, Key, Hash>&)"
511  ) << "attempted assignment to self"
512  << abort(FatalError);
513  }
514 
515 
516  // keys could be empty from a previous transfer()
517  if (keys_.empty())
518  {
519  keys_.setSize(rhs.keys_.size());
520  objects_.setSize(keys_.size());
521 
522  // Adapt end() iterators
523  endIter_.hashIndex_ = keys_.size();
524  endConstIter_.hashIndex_ = keys_.size();
525  }
526  else
527  {
528  clear();
529  // keys_.size() does not change so neither does end() iterator.
530  }
531 
532 
533  for (const_iterator iter = rhs.cbegin(); iter != rhs.cend(); ++iter)
534  {
535  insert(iter.key(), *iter);
536  }
537 }
538 
539 template<class T, class Key, class Hash>
540 bool Foam::StaticHashTable<T, Key, Hash>::operator==
541 (
543 ) const
544 {
545  // Are all my elements in rhs?
546  for (const_iterator iter = cbegin(); iter != cend(); ++iter)
547  {
548  const_iterator fnd = rhs.find(iter.key());
549 
550  if (fnd == rhs.cend() || fnd() != iter())
551  {
552  return false;
553  }
554  }
555 
556  // Are all rhs elements in me?
557  for (const_iterator iter = rhs.cbegin(); iter != rhs.cend(); ++iter)
558  {
559  const_iterator fnd = find(iter.key());
560 
561  if (fnd == cend() || fnd() != iter())
562  {
563  return false;
564  }
565  }
566  return true;
567 }
568 
569 
570 template<class T, class Key, class Hash>
571 bool Foam::StaticHashTable<T, Key, Hash>::operator!=
572 (
574 ) const
575 {
576  return !(operator==(rhs));
577 }
578 
579 
580 // * * * * * * * * * * * * * * * Friend Operators * * * * * * * * * * * * * //
581 
582 #include "StaticHashTableIO.C"
583 
584 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
585 
586 #endif
587 
588 // ************************ vim: set sw=4 sts=4 et: ************************ //