HashTable.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-2019 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 HashTable_C
27 #define HashTable_C
28 
29 #include "HashTable.H"
30 #include "List.H"
31 #include "Tuple2.H"
32 
33 // * * * * * * * * * * * * * * * * Constructors * * * * * * * * * * * * * * //
34 
35 template<class T, class Key, class Hash>
37 :
38  HashTableCore(),
39  nElmts_(0),
40  tableSize_(HashTableCore::canonicalSize(size)),
41  table_(nullptr)
42 {
43  if (tableSize_)
44  {
45  table_ = new hashedEntry*[tableSize_];
46 
47  for (label hashIdx = 0; hashIdx < tableSize_; hashIdx++)
48  {
49  table_[hashIdx] = 0;
50  }
51  }
52 }
53 
54 
55 template<class T, class Key, class Hash>
57 :
58  HashTable<T, Key, Hash>(ht.tableSize_)
59 {
60  for (const_iterator iter = ht.cbegin(); iter != ht.cend(); ++iter)
61  {
62  insert(iter.key(), *iter);
63  }
64 }
65 
66 
67 template<class T, class Key, class Hash>
69 (
71 )
72 :
73  HashTableCore(),
74  nElmts_(0),
75  tableSize_(0),
76  table_(nullptr)
77 {
78  transfer(ht);
79 }
80 
81 
82 template<class T, class Key, class Hash>
84 (
85  std::initializer_list<Tuple2<Key, T>> lst
86 )
87 :
88  HashTable<T, Key, Hash>(lst.size())
89 {
90  for (const Tuple2<Key, T>& pair : lst)
91  {
92  insert(pair.first(), pair.second());
93  }
94 }
95 
96 
97 // * * * * * * * * * * * * * * * * Destructor * * * * * * * * * * * * * * * //
98 
99 template<class T, class Key, class Hash>
101 {
102  if (table_)
103  {
104  clear();
105  delete[] table_;
106  }
107 }
108 
109 
110 // * * * * * * * * * * * * * * * Member Functions * * * * * * * * * * * * * //
111 
112 template<class T, class Key, class Hash>
113 bool Foam::HashTable<T, Key, Hash>::found(const Key& key) const
114 {
115  if (nElmts_)
116  {
117  const label hashIdx = hashKeyIndex(key);
118 
119  for (hashedEntry* ep = table_[hashIdx]; ep; ep = ep->next_)
120  {
121  if (key == ep->key_)
122  {
123  return true;
124  }
125  }
126  }
127 
128  #ifdef FULLDEBUG
129  if (debug)
130  {
131  InfoInFunction << "Entry " << key << " not found in hash table\n";
132  }
133  #endif
134 
135  return false;
136 }
137 
138 
139 template<class T, class Key, class Hash>
142 (
143  const Key& key
144 )
145 {
146  if (nElmts_)
147  {
148  const label hashIdx = hashKeyIndex(key);
149 
150  for (hashedEntry* ep = table_[hashIdx]; ep; ep = ep->next_)
151  {
152  if (key == ep->key_)
153  {
154  return iterator(this, ep, hashIdx);
155  }
156  }
157  }
158 
159  #ifdef FULLDEBUG
160  if (debug)
161  {
162  InfoInFunction << "Entry " << key << " not found in hash table\n";
163  }
164  #endif
165 
166  return iterator();
167 }
168 
169 
170 template<class T, class Key, class Hash>
173 (
174  const Key& key
175 ) const
176 {
177  if (nElmts_)
178  {
179  const label hashIdx = hashKeyIndex(key);
180 
181  for (hashedEntry* ep = table_[hashIdx]; ep; ep = ep->next_)
182  {
183  if (key == ep->key_)
184  {
185  return const_iterator(this, ep, hashIdx);
186  }
187  }
188  }
189 
190  #ifdef FULLDEBUG
191  if (debug)
192  {
193  InfoInFunction << "Entry " << key << " not found in hash table\n";
194  }
195  #endif
196 
197  return const_iterator();
198 }
199 
200 
201 template<class T, class Key, class Hash>
203 {
204  List<Key> keys(nElmts_);
205  label keyI = 0;
206 
207  for (const_iterator iter = cbegin(); iter != cend(); ++iter)
208  {
209  keys[keyI++] = iter.key();
210  }
211 
212  return keys;
213 }
214 
215 
216 template<class T, class Key, class Hash>
218 {
219  List<Key> sortedLst = this->toc();
220  sort(sortedLst);
221 
222  return sortedLst;
223 }
224 
225 
226 template<class T, class Key, class Hash>
228 (
229  const Key& key,
230  const T& newEntry,
231  const bool protect
232 )
233 {
234  if (!tableSize_)
235  {
236  resize(2);
237  }
238 
239  const label hashIdx = hashKeyIndex(key);
240 
241  hashedEntry* existing = 0;
242  hashedEntry* prev = 0;
243 
244  for (hashedEntry* ep = table_[hashIdx]; ep; ep = ep->next_)
245  {
246  if (key == ep->key_)
247  {
248  existing = ep;
249  break;
250  }
251  prev = ep;
252  }
253 
254  // Not found, insert it at the head
255  if (!existing)
256  {
257  table_[hashIdx] = new hashedEntry(key, table_[hashIdx], newEntry);
258  nElmts_++;
259 
260  if (double(nElmts_)/tableSize_ > 0.8 && tableSize_ < maxTableSize)
261  {
262  #ifdef FULLDEBUG
263  if (debug)
264  {
265  InfoInFunction << "Doubling table size\n";
266  }
267  #endif
268 
269  resize(2*tableSize_);
270  }
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  {
280  << "Cannot insert " << key << " already in hash table\n";
281  }
282  #endif
283  return false;
284  }
285  else
286  {
287  // Found - overwrite existing entry
288  // this corresponds to the Perl convention
289  hashedEntry* ep = new hashedEntry(key, existing->next_, newEntry);
290 
291  // Replace existing element - within list or insert at the head
292  if (prev)
293  {
294  prev->next_ = ep;
295  }
296  else
297  {
298  table_[hashIdx] = ep;
299  }
300 
301  delete existing;
302  }
303 
304  return true;
305 }
306 
307 
308 template<class T, class Key, class Hash>
310 {
311  // Note: entryPtr_ is nullptr for end(), so this catches that too
312  if (entryPtr_)
313  {
314  // Search element before entryPtr_
315  hashedEntry* prev = 0;
316 
317  for
318  (
319  hashedEntry* ep = hashTable_->table_[hashIndex_];
320  ep;
321  ep = ep->next_
322  )
323  {
324  if (ep == entryPtr_)
325  {
326  break;
327  }
328  prev = ep;
329  }
330 
331  if (prev)
332  {
333  // Has an element before entryPtr - reposition to there
334  prev->next_ = entryPtr_->next_;
335  delete entryPtr_;
336  entryPtr_ = prev;
337  }
338  else
339  {
340  // entryPtr was first element on SLList
341  hashTable_->table_[hashIndex_] = entryPtr_->next_;
342  delete entryPtr_;
343 
344  // Assign any non-nullptr value so it doesn't look
345  // like end()/cend()
346  entryPtr_ = reinterpret_cast<hashedEntry*>(this);
347 
348  // Mark with special hashIndex value to signal it has been rewound.
349  // The next increment will bring it back to the present location.
350  //
351  // From the current position 'curPos', we wish to continue at
352  // prevPos='curPos-1', which we mark as markPos='-curPos-1'.
353  // The negative lets us notice it is special, the extra '-1'
354  // is needed to avoid ambiguity for position '0'.
355  // To retrieve prevPos, we would later use '-(markPos+1) - 1'
356  hashIndex_ = -hashIndex_ - 1;
357  }
358 
359  hashTable_->nElmts_--;
360 
361  return true;
362  }
363  else
364  {
365  return false;
366  }
367 }
368 
369 
370 template<class T, class Key, class Hash>
371 bool Foam::HashTable<T, Key, Hash>::erase(const iterator& iter)
372 {
373  // NOTE: We use (const iterator&) here, but manipulate its contents anyhow.
374  // The parameter should be (iterator&), but then the compiler doesn't find
375  // it correctly and tries to call as (iterator) instead.
376  //
377  // Adjust iterator after erase
378  return const_cast<iterator&>(iter).erase();
379 }
380 
381 
382 template<class T, class Key, class Hash>
384 {
385  return erase(find(key));
386 }
387 
388 
389 template<class T, class Key, class Hash>
391 {
392  const label nTotal = nElmts_;
393  label count = 0;
394 
395  // Remove listed keys from this table - terminates early if possible
396  for (label keyI = 0; count < nTotal && keyI < keys.size(); ++keyI)
397  {
398  if (erase(keys[keyI]))
399  {
400  count++;
401  }
402  }
403 
404  return count;
405 }
406 
407 
408 template<class T, class Key, class Hash>
409 template<class AnyType, class AnyHash>
411 (
413 )
414 {
415  label count = 0;
416 
417  // Remove rhs keys from this table - terminates early if possible
418  // Could optimize depending on which hash is smaller ...
419  for (iterator iter = begin(); iter != end(); ++iter)
420  {
421  if (rhs.found(iter.key()) && erase(iter))
422  {
423  count++;
424  }
425  }
426 
427  return count;
428 }
429 
430 
431 template<class T, class Key, class Hash>
433 {
434  label newSize = HashTableCore::canonicalSize(sz);
435 
436  if (newSize == tableSize_)
437  {
438  #ifdef FULLDEBUG
439  if (debug)
440  {
441  InfoInFunction << "New table size == old table size\n";
442  }
443  #endif
444 
445  return;
446  }
447 
448  HashTable<T, Key, Hash>* tmpTable = new HashTable<T, Key, Hash>(newSize);
449 
450  for (const_iterator iter = cbegin(); iter != cend(); ++iter)
451  {
452  tmpTable->insert(iter.key(), *iter);
453  }
454 
455  label oldSize = tableSize_;
456  tableSize_ = tmpTable->tableSize_;
457  tmpTable->tableSize_ = oldSize;
458 
459  hashedEntry** oldTable = table_;
460  table_ = tmpTable->table_;
461  tmpTable->table_ = oldTable;
462 
463  delete tmpTable;
464 }
465 
466 
467 template<class T, class Key, class Hash>
469 {
470  if (nElmts_)
471  {
472  for (label hashIdx = 0; hashIdx < tableSize_; hashIdx++)
473  {
474  if (table_[hashIdx])
475  {
476  hashedEntry* ep = table_[hashIdx];
477  while (hashedEntry* next = ep->next_)
478  {
479  delete ep;
480  ep = next;
481  }
482  delete ep;
483  table_[hashIdx] = 0;
484  }
485  }
486  nElmts_ = 0;
487  }
488 }
489 
490 
491 template<class T, class Key, class Hash>
493 {
494  clear();
495  resize(0);
496 }
497 
498 
499 template<class T, class Key, class Hash>
501 {
502  const label newSize = HashTableCore::canonicalSize(nElmts_);
503 
504  if (newSize < tableSize_)
505  {
506  // Avoid having the table disappear on us
507  resize(newSize ? newSize : 2);
508  }
509 }
510 
511 
512 template<class T, class Key, class Hash>
514 {
515  // As per the Destructor
516  if (table_)
517  {
518  clear();
519  delete[] table_;
520  }
521 
522  tableSize_ = ht.tableSize_;
523  ht.tableSize_ = 0;
524 
525  table_ = ht.table_;
526  ht.table_ = nullptr;
527 
528  nElmts_ = ht.nElmts_;
529  ht.nElmts_ = 0;
530 }
531 
532 
533 // * * * * * * * * * * * * * * * Member Operators * * * * * * * * * * * * * //
534 
535 template<class T, class Key, class Hash>
536 void Foam::HashTable<T, Key, Hash>::operator=
537 (
538  const HashTable<T, Key, Hash>& rhs
539 )
540 {
541  // Check for assignment to self
542  if (this == &rhs)
543  {
545  << "attempted assignment to self"
546  << abort(FatalError);
547  }
548 
549  // Could be zero-sized from a previous transfer()
550  if (!tableSize_)
551  {
552  resize(rhs.tableSize_);
553  }
554  else
555  {
556  clear();
557  }
558 
559  for (const_iterator iter = rhs.cbegin(); iter != rhs.cend(); ++iter)
560  {
561  insert(iter.key(), *iter);
562  }
563 }
564 
565 
566 template<class T, class Key, class Hash>
567 void Foam::HashTable<T, Key, Hash>::operator=
568 (
570 )
571 {
572  // Check for assignment to self
573  if (this == &rhs)
574  {
576  << "attempted assignment to self"
577  << abort(FatalError);
578  }
579 
580  transfer(rhs);
581 }
582 
583 
584 template<class T, class Key, class Hash>
585 void Foam::HashTable<T, Key, Hash>::operator=
586 (
587  std::initializer_list<Tuple2<Key, T>> lst
588 )
589 {
590  // Could be zero-sized from a previous transfer()
591  if (!tableSize_)
592  {
593  resize(lst.size());
594  }
595  else
596  {
597  clear();
598  }
599 
600  for (const Tuple2<Key, T>& pair : lst)
601  {
602  insert(pair.first(), pair.second());
603  }
604 }
605 
606 
607 template<class T, class Key, class Hash>
608 bool Foam::HashTable<T, Key, Hash>::operator==
609 (
610  const HashTable<T, Key, Hash>& rhs
611 ) const
612 {
613  // Sizes (number of keys) must match
614  if (size() != rhs.size())
615  {
616  return false;
617  }
618 
619  for (const_iterator iter = rhs.cbegin(); iter != rhs.cend(); ++iter)
620  {
621  const_iterator fnd = find(iter.key());
622 
623  if (fnd == cend() || fnd() != iter())
624  {
625  return false;
626  }
627  }
628 
629  return true;
630 }
631 
632 
633 template<class T, class Key, class Hash>
634 bool Foam::HashTable<T, Key, Hash>::operator!=
635 (
636  const HashTable<T, Key, Hash>& rhs
637 ) const
638 {
639  return !(operator==(rhs));
640 }
641 
642 
643 // * * * * * * * * * * * * * * * Friend Operators * * * * * * * * * * * * * //
644 
645 #include "HashTableIO.C"
646 
647 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
648 
649 #endif
650 
651 // ************************************************************************* //
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
An STL-conforming const_iterator.
Definition: HashTable.H:481
srcOptions erase("case")
error FatalError
#define FatalErrorInFunction
Report an error message using Foam::FatalError.
Definition: error.H:319
A 2-tuple for storing two objects of different types.
Definition: HashTable.H:65
tUEqn clear()
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
HashTable(const label size=128)
Construct given initial table size.
Definition: HashTable.C:36
void transfer(HashTable< T, Key, Hash > &)
Transfer the contents of the argument table into this table.
Definition: HashTable.C:513
label size() const
Return number of elements in table.
Definition: HashTableI.H:65
bool erase(const iterator &)
Erase a hashedEntry specified by given iterator.
Definition: HashTable.C:371
~HashTable()
Destructor.
Definition: HashTable.C:100
bool insert(const Key &, const T &newElmt)
Insert a new hashedEntry.
Definition: HashTableI.H:80
iterator find(const Key &)
Find and return an iterator set at the hashedEntry.
Definition: HashTable.C:142
An STL-conforming iterator.
Definition: HashTable.H:426
bool found(const Key &) const
Return true if hashedEntry is found in table.
Definition: HashTable.C:113
tmp< fvMatrix< Type > > operator==(const fvMatrix< Type > &, const fvMatrix< Type > &)
void clear()
Clear all entries from table.
Definition: HashTable.C:468
void sort(UList< T > &)
Definition: UList.C:115
timeIndices insert(timeIndex, timeDirs[timeI].value())
triSurfaceToAgglom resize(surfacesMesh.size())
An STL-conforming hash table.
Definition: HashTable.H:61
errorManip< error > abort(error &err)
Definition: errorManip.H:131
A 1D vector of objects of type <T>, where the size of the vector is known and can be used for subscri...
Definition: HashTable.H:60
const volScalarField & T
Template-invariant bits for HashTable.
Definition: HashTable.H:82
List< Key > sortedToc() const
Return the table of contents as a sorted list.
Definition: HashTable.C:217
Hash function class for primitives. All non-primitives used to hash entries on hash tables likely nee...
Definition: Hash.H:54
void resize(const label newSize)
Resize the hash table for efficiency.
Definition: HashTable.C:432
List< Key > toc() const
Return the table of contents.
Definition: HashTable.C:202
label size() const
Return the number of elements in the UList.
Definition: UListI.H:299
const_iterator cbegin() const
const_iterator set to the beginning of the HashTable
Definition: HashTableI.H:506
bool erase()
Erase the HashTable element at the current position.
Definition: HashTable.C:309
static iteratorEnd cend()
iteratorEnd set to beyond the end of any HashTable
Definition: HashTable.H:106
void shrink()
Shrink the allocated table to approx. twice number of elements.
Definition: HashTable.C:500
void clearStorage()
Clear the table entries and the table itself.
Definition: HashTable.C:492
#define InfoInFunction
Report an information message using Foam::Info.