ListHashTable.C
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-2021 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 ListHashTable_C
27 #define ListHashTable_C
28 
29 #include "ListHashTable.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_(ListHashTableCore::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 ListHashTable."
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 (
360  const ListHashTable<T, Key, Hash>& rhs
361 )
362 {
363  label count = 0;
364 
365  // Remove rhs elements from this table
366  // NOTE: could optimise 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 ListHashTable."
400  << " Minimum size is 1" << abort(FatalError);
401  }
402 
403 
404  ListHashTable<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::ListHashTable<T, Key, Hash>::operator=
469 (
470  const ListHashTable<T, Key, Hash>& rhs
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 
506 template<class T, class Key, class Hash>
507 void Foam::ListHashTable<T, Key, Hash>::operator=
508 (
510 )
511 {
512  // Check for assignment to self
513  if (this == &rhs)
514  {
516  << "attempted assignment to self"
517  << abort(FatalError);
518  }
519 
520  transfer(rhs);
521 }
522 
523 
524 template<class T, class Key, class Hash>
525 bool Foam::ListHashTable<T, Key, Hash>::operator==
526 (
527  const ListHashTable<T, Key, Hash>& rhs
528 ) const
529 {
530  // Sizes (number of keys) must match
531 
532  for (const_iterator iter = rhs.cbegin(); iter != rhs.cend(); ++iter)
533  {
534  const_iterator fnd = find(iter.key());
535 
536  if (fnd == cend() || fnd() != iter())
537  {
538  return false;
539  }
540  }
541 
542  return true;
543 }
544 
545 
546 template<class T, class Key, class Hash>
547 bool Foam::ListHashTable<T, Key, Hash>::operator!=
548 (
549  const ListHashTable<T, Key, Hash>& rhs
550 ) const
551 {
552  return !(operator==(rhs));
553 }
554 
555 
556 // * * * * * * * * * * * * * * * Friend Operators * * * * * * * * * * * * * //
557 
558 #include "ListHashTableIO.C"
559 
560 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
561 
562 #endif
563 
564 // ************************************************************************* //
Iterator< const T &, const ListHashTable< T, Key, Hash > &> const_iterator
#define forAll(list, i)
Loop across all elements in list.
Definition: UList.H:434
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
Template-invariant bits for ListHashTable.
Definition: ListHashTable.H:76
error FatalError
#define FatalErrorInFunction
Report an error message using Foam::FatalError.
Definition: error.H:323
const iterator & end()
Iterator set to beyond the end of the ListHashTable.
bool operator==(const ListHashTable< T, Key, Hash > &) const
Equality. Two hash tables are equal if all contents of first are.
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
void size(const label)
Override size to be inconsistent with allocated storage.
Definition: ListI.H:164
label count(const ListType &l, typename ListType::const_reference x)
Count the number of occurrences of a value in a list.
ListHashTableCore()
Construct null.
Definition: ListHashTable.H:82
void transfer(ListHashTable< T, Key, Hash > &)
Transfer the contents of the argument table into this table.
static label canonicalSize(const label)
Return a canonical (power-of-two) size.
Definition: ListHashTable.C:35
iterator begin()
Iterator set to the beginning of the ListHashTable.
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.
~ListHashTable()
Destructor.
errorManip< error > abort(error &err)
Definition: errorManip.H:131
ListHashTable(const label size=128)
Construct given initial table size.
Definition: ListHashTable.C:62
void T(FieldField< Field, Type > &f1, const FieldField< Field, Type > &f2)
STL conforming hash table using contiguous lists rather than linked lists.
Definition: ListHashTable.H:56
bool insert(const Key &key, const T &newElmt)
Insert a new hashed entry.
void setSize(const label)
Reset size of List.
Definition: List.C:281
Iterator< T &, ListHashTable< T, Key, Hash > &> iterator
iterator find(const Key &key)
Find and return an iterator set at the hashed entry.
const const_iterator & cend() const
const_iterator set to beyond the end of the ListHashTable
void clearStorage()
Clear the table entries and the table itself.
List< Key > toc() const
Return the table of contents.
const_iterator cbegin() const
const_iterator set to the beginning of the ListHashTable
void resize(const label newSize)
Resize the hash table for efficiency.
void clear()
Clear all entries from table.
bool found(const Key &key) const
Return true if hashed entry is found in table.
#define InfoInFunction
Report an information message using Foam::Info.