FreeFOAM The Cross-Platform CFD Toolkit
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) 1991-2010 OpenCFD Ltd.
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 <OpenFOAM/List.H>
31 
32 // * * * * * * * * * * * * Private Member Functions * * * * * * * * * * * * //
33 
34 template<class T, class Key, class Hash>
35 Foam::label Foam::HashTable<T, Key, Hash>::canonicalSize(const label size)
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 :
64  HashTableName(),
65  nElmts_(0),
66  tableSize_(canonicalSize(size)),
67  table_(NULL),
68  endIter_(*this, NULL, 0),
69  endConstIter_(*this, NULL, 0)
70 {
71  if (tableSize_)
72  {
73  table_ = new hashedEntry*[tableSize_];
74 
75  for (label hashIdx = 0; hashIdx < tableSize_; hashIdx++)
76  {
77  table_[hashIdx] = 0;
78  }
79  }
80 }
81 
82 
83 template<class T, class Key, class Hash>
85 :
86  HashTableName(),
87  nElmts_(0),
88  tableSize_(ht.tableSize_),
89  table_(NULL),
90  endIter_(*this, NULL, 0),
91  endConstIter_(*this, NULL, 0)
92 {
93  if (tableSize_)
94  {
95  table_ = new hashedEntry*[tableSize_];
96 
97  for (label hashIdx = 0; hashIdx < tableSize_; hashIdx++)
98  {
99  table_[hashIdx] = 0;
100  }
101 
102  for (const_iterator iter = ht.cbegin(); iter != ht.cend(); ++iter)
103  {
104  insert(iter.key(), *iter);
105  }
106  }
107 }
108 
109 template<class T, class Key, class Hash>
111 (
112  const Xfer<HashTable<T, Key, Hash> >& ht
113 )
114 :
115  HashTableName(),
116  nElmts_(0),
117  tableSize_(0),
118  table_(NULL),
119  endIter_(*this, NULL, 0),
120  endConstIter_(*this, NULL, 0)
121 {
122  transfer(ht());
123 }
124 
125 
126 // * * * * * * * * * * * * * * * * Destructor * * * * * * * * * * * * * * * //
127 
128 template<class T, class Key, class Hash>
130 {
131  if (table_)
132  {
133  clear();
134  delete[] table_;
135  }
136 }
137 
138 
139 // * * * * * * * * * * * * * * * Member Functions * * * * * * * * * * * * * //
140 
141 template<class T, class Key, class Hash>
142 bool Foam::HashTable<T, Key, Hash>::found(const Key& key) const
143 {
144  if (nElmts_)
145  {
146  const label hashIdx = hashKeyIndex(key);
147 
148  for (hashedEntry* ep = table_[hashIdx]; ep; ep = ep->next_)
149  {
150  if (key == ep->key_)
151  {
152  return true;
153  }
154  }
155  }
156 
157 # ifdef FULLDEBUG
158  if (debug)
159  {
160  Info<< "HashTable<T, Key, Hash>::found(const Key& key) : "
161  << "Entry " << key << " not found in hash table\n";
162  }
163 # endif
164 
165  return false;
166 }
167 
168 
169 template<class T, class Key, class Hash>
172 (
173  const Key& key
174 )
175 {
176  if (nElmts_)
177  {
178  const label hashIdx = hashKeyIndex(key);
179 
180  for (hashedEntry* ep = table_[hashIdx]; ep; ep = ep->next_)
181  {
182  if (key == ep->key_)
183  {
184  return iterator(*this, ep, hashIdx);
185  }
186  }
187  }
188 
189 # ifdef FULLDEBUG
190  if (debug)
191  {
192  Info<< "HashTable<T, Key, Hash>::find(const Key& key) : "
193  << "Entry " << key << " not found in hash table\n";
194  }
195 # endif
196 
197  return end();
198 }
199 
200 
201 template<class T, class Key, class Hash>
204 (
205  const Key& key
206 ) const
207 {
208  if (nElmts_)
209  {
210  const label hashIdx = hashKeyIndex(key);
211 
212  for (hashedEntry* ep = table_[hashIdx]; ep; ep = ep->next_)
213  {
214  if (key == ep->key_)
215  {
216  return const_iterator(*this, ep, hashIdx);
217  }
218  }
219  }
220 
221 # ifdef FULLDEBUG
222  if (debug)
223  {
224  Info<< "HashTable<T, Key, Hash>::find(const Key& key) const : "
225  << "Entry " << key << " not found in hash table\n";
226  }
227 # endif
228 
229  return cend();
230 }
231 
232 
233 // Return the table of contents
234 template<class T, class Key, class Hash>
236 {
237  List<Key> tofc(nElmts_);
238  label i = 0;
239 
240  for (const_iterator iter = cbegin(); iter != cend(); ++iter)
241  {
242  tofc[i++] = iter.key();
243  }
244 
245  return tofc;
246 }
247 
248 
249 template<class T, class Key, class Hash>
251 {
252  List<Key> sortedLst = this->toc();
253  sort(sortedLst);
254 
255  return sortedLst;
256 }
257 
258 
259 template<class T, class Key, class Hash>
261 (
262  const Key& key,
263  const T& newEntry,
264  const bool protect
265 )
266 {
267  if (!tableSize_)
268  {
269  resize(2);
270  }
271 
272  const label hashIdx = hashKeyIndex(key);
273 
274  hashedEntry* existing = 0;
275  hashedEntry* prev = 0;
276 
277  for (hashedEntry* ep = table_[hashIdx]; ep; ep = ep->next_)
278  {
279  if (key == ep->key_)
280  {
281  existing = ep;
282  break;
283  }
284  prev = ep;
285  }
286 
287  // not found, insert it at the head
288  if (!existing)
289  {
290  table_[hashIdx] = new hashedEntry(key, table_[hashIdx], newEntry);
291  nElmts_++;
292 
293  if (double(nElmts_)/tableSize_ > 0.8)
294  {
295 # ifdef FULLDEBUG
296  if (debug)
297  {
298  Info<< "HashTable<T, Key, Hash>::set"
299  "(const Key& key, T newEntry) : "
300  "Doubling table size\n";
301  }
302 # endif
303 
304  resize(2*tableSize_);
305  }
306  }
307  else if (protect)
308  {
309  // found - but protected from overwriting
310  // this corresponds to the STL 'insert' convention
311 # ifdef FULLDEBUG
312  if (debug)
313  {
314  Info<< "HashTable<T, Key, Hash>::set"
315  "(const Key& key, T newEntry, true) : "
316  "Cannot insert " << key << " already in hash table\n";
317  }
318 # endif
319  return false;
320  }
321  else
322  {
323  // found - overwrite existing entry
324  // this corresponds to the Perl convention
325  hashedEntry* ep = new hashedEntry(key, existing->next_, newEntry);
326 
327  // replace existing element - within list or insert at the head
328  if (prev)
329  {
330  prev->next_ = ep;
331  }
332  else
333  {
334  table_[hashIdx] = ep;
335  }
336 
337  delete existing;
338  }
339 
340  return true;
341 }
342 
343 
344 template<class T, class Key, class Hash>
346 {
347  if (cit.elmtPtr_) // note: endIter_ also has 0 elmtPtr_
348  {
349  iterator& it = const_cast<iterator&>(cit);
350 
351  // Search element before elmtPtr_
352  hashedEntry* prev = 0;
353 
354  for (hashedEntry* ep = table_[it.hashIndex_]; ep; ep = ep->next_)
355  {
356  if (ep == it.elmtPtr_)
357  {
358  break;
359  }
360  prev = ep;
361  }
362 
363  if (prev)
364  {
365  // Have element before elmtPtr
366  prev->next_ = it.elmtPtr_->next_;
367  delete it.elmtPtr_;
368  it.elmtPtr_ = prev;
369  }
370  else
371  {
372  // elmtPtr is first element on SLList
373  table_[it.hashIndex_] = it.elmtPtr_->next_;
374  delete it.elmtPtr_;
375 
376  // Search back for previous non-zero table entry
377  while (--it.hashIndex_ >= 0 && !table_[it.hashIndex_])
378  {}
379 
380  if (it.hashIndex_ >= 0)
381  {
382  // In table entry search for last element
383  it.elmtPtr_ = table_[it.hashIndex_];
384 
385  while (it.elmtPtr_ && it.elmtPtr_->next_)
386  {
387  it.elmtPtr_ = it.elmtPtr_->next_;
388  }
389  }
390  else
391  {
392  // No previous found. Mark with special value which is
393  // - not end()/cend()
394  // - handled by operator++
395  it.elmtPtr_ = reinterpret_cast<hashedEntry*>(this);
396  it.hashIndex_ = -1;
397  }
398  }
399 
400  nElmts_--;
401 
402 # ifdef FULLDEBUG
403  if (debug)
404  {
405  Info<< "HashTable<T, Key, Hash>::erase(iterator&) : "
406  << "hashedEntry " << it.elmtPtr_->key_ << " removed.\n";
407  }
408 # endif
409 
410  return true;
411  }
412  else
413  {
414 # ifdef FULLDEBUG
415  if (debug)
416  {
417  Info<< "HashTable<T, Key, Hash>::erase(iterator&) : "
418  << "cannot remove hashedEntry from hash table\n";
419  }
420 # endif
421 
422  return false;
423  }
424 }
425 
426 
427 template<class T, class Key, class Hash>
429 {
430  iterator fnd = find(key);
431 
432  if (fnd != end())
433  {
434  return erase(fnd);
435  }
436  else
437  {
438  return false;
439  }
440 }
441 
442 
443 template<class T, class Key, class Hash>
445 {
446  label count = 0;
447 
448  // Remove listed keys from this table
449  if (this->size())
450  {
451  forAll(keys, keyI)
452  {
453  if (erase(keys[keyI]))
454  {
455  count++;
456  }
457  }
458  }
459 
460  return count;
461 }
462 
463 
464 template<class T, class Key, class Hash>
465 template<class AnyType, class AnyHash>
467 (
469 )
470 {
471  label count = 0;
472 
473  // Remove rhs keys from this table - terminates early if possible
474  // Could optimize depending on which hash is smaller ...
475  for (iterator iter = begin(); iter != end(); ++iter)
476  {
477  if (rhs.found(iter.key()) && erase(iter))
478  {
479  count++;
480  }
481  }
482 
483  return count;
484 }
485 
486 
487 template<class T, class Key, class Hash>
489 {
490  label newSize = canonicalSize(sz);
491 
492  if (newSize == tableSize_)
493  {
494 # ifdef FULLDEBUG
495  if (debug)
496  {
497  Info<< "HashTable<T, Key, Hash>::resize(const label) : "
498  << "new table size == old table size\n";
499  }
500 # endif
501 
502  return;
503  }
504 
505  HashTable<T, Key, Hash>* newTable = new HashTable<T, Key, Hash>(newSize);
506 
507  for (const_iterator iter = cbegin(); iter != cend(); ++iter)
508  {
509  newTable->insert(iter.key(), *iter);
510  }
511 
512  label oldTableSize = tableSize_;
513  tableSize_ = newTable->tableSize_;
514  newTable->tableSize_ = oldTableSize;
515 
516  hashedEntry** oldTable = table_;
517  table_ = newTable->table_;
518  newTable->table_ = oldTable;
519 
520  delete newTable;
521 }
522 
523 
524 template<class T, class Key, class Hash>
526 {
527  if (nElmts_)
528  {
529  for (label hashIdx = 0; hashIdx < tableSize_; hashIdx++)
530  {
531  if (table_[hashIdx])
532  {
533  hashedEntry* ep = table_[hashIdx];
534  while (hashedEntry* next = ep->next_)
535  {
536  delete ep;
537  ep = next;
538  }
539  delete ep;
540  table_[hashIdx] = 0;
541  }
542  }
543  nElmts_ = 0;
544  }
545 }
546 
547 
548 template<class T, class Key, class Hash>
550 {
551  clear();
552  resize(0);
553 }
554 
555 
556 template<class T, class Key, class Hash>
558 {
559  // as per the Destructor
560  if (table_)
561  {
562  clear();
563  delete[] table_;
564  }
565 
566  tableSize_ = ht.tableSize_;
567  ht.tableSize_ = 0;
568 
569  table_ = ht.table_;
570  ht.table_ = NULL;
571 
572  nElmts_ = ht.nElmts_;
573  ht.nElmts_ = 0;
574 }
575 
576 
577 // * * * * * * * * * * * * * * * Member Operators * * * * * * * * * * * * * //
578 
579 template<class T, class Key, class Hash>
581 (
582  const HashTable<T, Key, Hash>& rhs
583 )
584 {
585  // Check for assignment to self
586  if (this == &rhs)
587  {
589  (
590  "HashTable<T, Key, Hash>::operator="
591  "(const HashTable<T, Key, Hash>&)"
592  ) << "attempted assignment to self"
593  << abort(FatalError);
594  }
595 
596  // could be zero-sized from a previous transfer()
597  if (!tableSize_)
598  {
599  resize(rhs.tableSize_);
600  }
601  else
602  {
603  clear();
604  }
605 
606  for (const_iterator iter = rhs.cbegin(); iter != rhs.cend(); ++iter)
607  {
608  insert(iter.key(), *iter);
609  }
610 }
611 
612 
613 template<class T, class Key, class Hash>
614 bool Foam::HashTable<T, Key, Hash>::operator==
615 (
616  const HashTable<T, Key, Hash>& rhs
617 ) const
618 {
619  // Are all my elements in rhs?
620  for (const_iterator iter = cbegin(); iter != cend(); ++iter)
621  {
622  const_iterator fnd = rhs.find(iter.key());
623 
624  if (fnd == rhs.cend() || fnd() != iter())
625  {
626  return false;
627  }
628  }
629 
630  // Are all rhs elements in me?
631  for (const_iterator iter = rhs.cbegin(); iter != rhs.cend(); ++iter)
632  {
633  const_iterator fnd = find(iter.key());
634 
635  if (fnd == cend() || fnd() != iter())
636  {
637  return false;
638  }
639  }
640  return true;
641 }
642 
643 
644 template<class T, class Key, class Hash>
645 bool Foam::HashTable<T, Key, Hash>::operator!=
646 (
647  const HashTable<T, Key, Hash>& rhs
648 ) const
649 {
650  return !(operator==(rhs));
651 }
652 
653 
654 // * * * * * * * * * * * * * * * Friend Operators * * * * * * * * * * * * * //
655 
656 #include <OpenFOAM/HashTableIO.C>
657 
658 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
659 
660 #endif
661 
662 // ************************ vim: set sw=4 sts=4 et: ************************ //