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) 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 #ifndef StaticHashTable_C
27 #define StaticHashTable_C
28 
29 #include "StaticHashTable.H"
30 #include "List.H"
31 #include "IOstreams.H"
32 
33 // * * * * * * * * * * * * Private Member Functions * * * * * * * * * * * * //
34 
36 {
37  if (size < 1)
38  {
39  return 0;
40  }
41 
42  // enforce power of two
43  unsigned int goodSize = size;
44 
45  if (goodSize & (goodSize - 1))
46  {
47  // brute-force is fast enough
48  goodSize = 1;
49  while (goodSize < unsigned(size))
50  {
51  goodSize <<= 1;
52  }
53  }
54 
55  return goodSize;
56 }
57 
58 
59 // * * * * * * * * * * * * * * * * Constructors * * * * * * * * * * * * * * //
60 
61 // Construct given initial table size
62 template<class T, class Key, class Hash>
64 :
66  keys_(StaticHashTableCore::canonicalSize(size)),
67  objects_(keys_.size()),
68  nElmts_(0),
69  endIter_(*this, keys_.size(), 0),
70  endConstIter_(*this, keys_.size(), 0)
71 {
72  if (size < 1)
73  {
75  (
76  "StaticHashTable<T, Key, Hash>::StaticHashTable(const label size)"
77  ) << "Illegal size " << size << " for StaticHashTable."
78  << " Minimum size is 1" << abort(FatalError);
79  }
80 }
81 
82 
83 // Construct as copy
84 template<class T, class Key, class Hash>
86 (
88 )
89 :
91  keys_(ht.keys_),
92  objects_(ht.objects_),
93  nElmts_(ht.nElmts_),
94  endIter_(*this, keys_.size(), 0),
95  endConstIter_(*this, keys_.size(), 0)
96 {}
97 
98 
99 template<class T, class Key, class Hash>
101 (
103 )
104 :
106  keys_(0),
107  objects_(0),
108  nElmts_(0),
109  endIter_(*this, 0, 0),
110  endConstIter_(*this, 0, 0)
111 {
112  transfer(ht());
113 }
114 
115 
116 // * * * * * * * * * * * * * * * * Destructor * * * * * * * * * * * * * * * //
117 
118 template<class T, class Key, class Hash>
120 {}
121 
122 
123 // * * * * * * * * * * * * * * * Member Functions * * * * * * * * * * * * * //
124 
125 template<class T, class Key, class Hash>
127 {
128  if (nElmts_)
129  {
130  const label hashIdx = hashKeyIndex(key);
131  const List<Key>& localKeys = keys_[hashIdx];
132 
133  forAll(localKeys, elemIdx)
134  {
135  if (key == localKeys[elemIdx])
136  {
137  return true;
138  }
139  }
140  }
141 
142 # ifdef FULLDEBUG
143  if (debug)
144  {
145  Info<< "StaticHashTable<T, Key, Hash>::found(const Key&) : "
146  << "Entry " << key << " not found in hash table\n";
147  }
148 # endif
149 
150  return false;
151 }
152 
153 
154 template<class T, class Key, class Hash>
157 (
158  const Key& key
159 )
160 {
161  if (nElmts_)
162  {
163  const label hashIdx = hashKeyIndex(key);
164  const List<Key>& localKeys = keys_[hashIdx];
165 
166  forAll(localKeys, elemIdx)
167  {
168  if (key == localKeys[elemIdx])
169  {
170  return iterator(*this, hashIdx, elemIdx);
171  }
172  }
173  }
174 
175 # ifdef FULLDEBUG
176  if (debug)
177  {
178  Info<< "StaticHashTable<T, Key, Hash>::find(const Key&) : "
179  << "Entry " << key << " not found in hash table\n";
180  }
181 # endif
182 
183  return end();
184 }
185 
186 
187 template<class T, class Key, class Hash>
190 (
191  const Key& key
192 ) const
193 {
194  if (nElmts_)
195  {
196  const label hashIdx = hashKeyIndex(key);
197  const List<Key>& localKeys = keys_[hashIdx];
198 
199  forAll(localKeys, elemIdx)
200  {
201  if (key == localKeys[elemIdx])
202  {
203  return const_iterator(*this, hashIdx, elemIdx);
204  }
205  }
206  }
207 
208 # ifdef FULLDEBUG
209  if (debug)
210  {
211  Info<< "StaticHashTable<T, Key, Hash>::find(const Key&) const : "
212  << "Entry " << key << " not found in hash table\n";
213  }
214 # endif
215 
216  return cend();
217 }
218 
219 
220 // Return the table of contents
221 template<class T, class Key, class Hash>
223 {
224  List<Key> keys(nElmts_);
225  label keyI = 0;
226 
227  for (const_iterator iter = cbegin(); iter != cend(); ++iter)
228  {
229  keys[keyI++] = iter.key();
230  }
231 
232  return keys;
233 }
234 
235 
236 template<class T, class Key, class Hash>
238 (
239  const Key& key,
240  const T& newEntry,
241  const bool protect
242 )
243 {
244  const label hashIdx = hashKeyIndex(key);
245  List<Key>& localKeys = keys_[hashIdx];
246 
247  label existing = localKeys.size();
248  forAll(localKeys, elemIdx)
249  {
250  if (key == localKeys[elemIdx])
251  {
252  existing = elemIdx;
253  break;
254  }
255  }
256 
257  if (existing == localKeys.size())
258  {
259  // not found, append
260  List<T>& localObjects = objects_[hashIdx];
261 
262  localKeys.setSize(existing+1);
263  localObjects.setSize(existing+1);
264 
265  localKeys[existing] = key;
266  localObjects[existing] = newEntry;
267 
268  nElmts_++;
269  }
270  else if (protect)
271  {
272  // found - but protected from overwriting
273  // this corresponds to the STL 'insert' convention
274 # ifdef FULLDEBUG
275  if (debug)
276  {
277  Info<< "StaticHashTable<T, Key, Hash>::set"
278  "(const Key& key, T newEntry, true) : "
279  "Cannot insert " << key << " already in hash table\n";
280  }
281 # endif
282  return false;
283  }
284  else
285  {
286  // found - overwrite existing entry
287  // this corresponds to the Perl convention
288  objects_[hashIdx][existing] = newEntry;
289  }
290 
291  return true;
292 }
293 
294 
295 template<class T, class Key, class Hash>
297 {
298  if (cit != end())
299  {
300  List<Key>& localKeys = keys_[cit.hashIndex_];
301  List<T>& localObjects = objects_[cit.hashIndex_];
302 
303  // Copy down
304  for (label i = cit.elemIndex_+1; i < localKeys.size(); i++)
305  {
306  localKeys[i-1] = localKeys[i];
307  localObjects[i-1] = localObjects[i];
308  }
309  localKeys.setSize(localKeys.size()-1);
310  localObjects.setSize(localObjects.size()-1);
311 
312  // adjust iterator after erase
313  iterator& it = const_cast<iterator&>(cit);
314 
315  it.elemIndex_--;
316  if (it.elemIndex_ < 0)
317  {
318  // No previous element in the local list
319  // Mark with as special value (see notes in HashTable)
320  it.hashIndex_ = -it.hashIndex_ - 1;
321  it.elemIndex_ = 0;
322  }
323 
324  nElmts_--;
325 
326 # ifdef FULLDEBUG
327  if (debug)
328  {
329  Info<< "StaticHashTable<T, Key, Hash>::erase(iterator&) : "
330  << "hashedEntry removed.\n";
331  }
332 # endif
333 
334  return true;
335  }
336  else
337  {
338 # ifdef FULLDEBUG
339  if (debug)
340  {
341  Info<< "StaticHashTable<T, Key, Hash>::erase(iterator&) : "
342  << "cannot remove hashedEntry from hash table\n";
343  }
344 # endif
345 
346  return false;
347  }
348 }
349 
350 
351 template<class T, class Key, class Hash>
353 {
354  iterator it = find(key);
355 
356  if (it != end())
357  {
358  return erase(it);
359  }
360  else
361  {
362  return false;
363  }
364 }
365 
366 
367 template<class T, class Key, class Hash>
369 (
371 )
372 {
373  label count = 0;
374 
375  // Remove rhs elements from this table
376  // NOTE: could optimize depending on which hash is smaller
377  for (iterator iter = this->begin(); iter != this->end(); ++iter)
378  {
379  if (rhs.found(iter.key()) && erase(iter))
380  {
381  count++;
382  }
383  }
384 
385  return count;
386 }
387 
388 
389 template<class T, class Key, class Hash>
391 {
393 
394  if (newSize == keys_.size())
395  {
396 # ifdef FULLDEBUG
397  if (debug)
398  {
399  Info<< "StaticHashTable<T, Key, Hash>::resize(const label) : "
400  << "new table size == old table size\n";
401  }
402 # endif
403 
404  return;
405  }
406 
407  if (newSize < 1)
408  {
410  (
411  "StaticHashTable<T, Key, Hash>::resize(const label)"
412  ) << "Illegal size " << newSize << " for StaticHashTable."
413  << " Minimum size is 1" << abort(FatalError);
414  }
415 
416 
417  StaticHashTable<T, Key, Hash> newTable(newSize);
418 
419  for (const_iterator iter = cbegin(); iter != cend(); ++iter)
420  {
421  newTable.insert(iter.key(), *iter);
422  }
423 
424  transfer(newTable);
425 
426  // Adapt end() iterators
427  endIter_.hashIndex_ = keys_.size();
428  endConstIter_.hashIndex_ = keys_.size();
429 }
430 
431 
432 template<class T, class Key, class Hash>
434 {
435  forAll(keys_, hashIdx)
436  {
437  keys_[hashIdx].clear();
438  objects_[hashIdx].clear();
439  }
440 
441  nElmts_ = 0;
442 }
443 
444 
445 template<class T, class Key, class Hash>
447 {
448  clear();
449  resize(1);
450 }
451 
452 
453 template<class T, class Key, class Hash>
455 (
457 )
458 {
459  // Remove existing elements
460  clear();
461 
462  // Copy data from ht
463  keys_.transfer(ht.keys_);
464  objects_.transfer(ht.objects_);
465 
466  nElmts_ = ht.nElmts_;
467  ht.nElmts_ = 0;
468 
469  // Adapt end() iterators
470  endIter_.hashIndex_ = keys_.size();
471  endConstIter_.hashIndex_ = keys_.size();
472 
473  ht.endIter_.hashIndex_ = 0;
474  ht.endConstIter_.hashIndex_ = 0;
475 }
476 
477 
478 // * * * * * * * * * * * * * * * Member Operators * * * * * * * * * * * * * //
479 
480 template<class T, class Key, class Hash>
481 void Foam::StaticHashTable<T, Key, Hash>::operator=
482 (
484 )
485 {
486  // Check for assignment to self
487  if (this == &rhs)
488  {
490  (
491  "StaticHashTable<T, Key, Hash>::operator="
492  "(const StaticHashTable<T, Key, Hash>&)"
493  ) << "attempted assignment to self"
494  << abort(FatalError);
495  }
496 
497 
498  // keys could be empty from a previous transfer()
499  if (keys_.empty())
500  {
501  keys_.setSize(rhs.keys_.size());
502  objects_.setSize(keys_.size());
503 
504  // Adapt end() iterators
505  endIter_.hashIndex_ = keys_.size();
506  endConstIter_.hashIndex_ = keys_.size();
507  }
508  else
509  {
510  clear();
511  // keys_.size() does not change so neither does end() iterator.
512  }
513 
514 
515  for (const_iterator iter = rhs.cbegin(); iter != rhs.cend(); ++iter)
516  {
517  insert(iter.key(), *iter);
518  }
519 }
520 
521 template<class T, class Key, class Hash>
522 bool Foam::StaticHashTable<T, Key, Hash>::operator==
523 (
525 ) const
526 {
527  // sizes (number of keys) must match
528 
529  for (const_iterator iter = rhs.cbegin(); iter != rhs.cend(); ++iter)
530  {
531  const_iterator fnd = find(iter.key());
532 
533  if (fnd == cend() || fnd() != iter())
534  {
535  return false;
536  }
537  }
538 
539  return true;
540 }
541 
542 
543 template<class T, class Key, class Hash>
544 bool Foam::StaticHashTable<T, Key, Hash>::operator!=
545 (
547 ) const
548 {
549  return !(operator==(rhs));
550 }
551 
552 
553 // * * * * * * * * * * * * * * * Friend Operators * * * * * * * * * * * * * //
554 
555 #include "StaticHashTableIO.C"
556 
557 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
558 
559 #endif
560 
561 // ************************************************************************* //
STL conforming hash table.
static label canonicalSize(const label)
Return a canonical (power-of-two) size.
Iterator< const T &, const StaticHashTable< T, Key, Hash > & > const_iterator
iterator begin()
Iterator set to the beginning of the StaticHashTable.
iterator find(const Key &key)
Find and return an iterator set at the hashed entry.
Iterator< T &, StaticHashTable< T, Key, Hash > & > iterator
void T(FieldField< Field, Type > &f1, const FieldField< Field, Type > &f2)
StaticHashTableCore()
Construct null.
bool operator==(const StaticHashTable< T, Key, Hash > &) const
Equality. Two hash tables are equal if all contents of first are.
A simple container for copying or transferring objects of type <T>.
Definition: Xfer.H:85
StaticHashTable(const label size=128)
Construct given initial table size.
~StaticHashTable()
Destructor.
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
void size(const label)
Override size to be inconsistent with allocated storage.
Definition: ListI.H:76
bool insert(const Key &key, const T &newElmt)
Insert a new hashed entry.
messageStream Info
A 1D array of objects of type <T>, where the size of the vector is known and used for subscript bound...
Definition: HashTable.H:59
Useful combination of include files which define Sin, Sout and Serr and the use of IO streams general...
void setSize(const label)
Reset size of List.
Definition: List.C:318
#define forAll(list, i)
Definition: UList.H:421
List< Key > toc() const
Return the table of contents.
const iterator & end()
Iterator set to beyond the end of the StaticHashTable.
void clear()
Clear all entries from table.
errorManip< error > abort(error &err)
Definition: errorManip.H:131
#define FatalErrorIn(functionName)
Report an error message using Foam::FatalError.
Definition: error.H:314
Template-invariant bits for StaticHashTable.
error FatalError
void resize(const label newSize)
Resize the hash table for efficiency.
bool found(const Key &key) const
Return true if hashed entry is found in table.
void clearStorage()
Clear the table entries and the table itself.
void transfer(StaticHashTable< T, Key, Hash > &)
Transfer the contents of the argument table into this table.
const const_iterator & cend() const
const_iterator set to beyond the end of the StaticHashTable
bool erase(const iterator &it)
Erase an hashed entry specified by given iterator.
const_iterator cbegin() const
const_iterator set to the beginning of the StaticHashTable