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