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