src/OpenFOAM/containers/HashTables/HashTable/HashTable.C

   1 /*---------------------------------------------------------------------------*\
   2   =========                 |
   3   \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
   4    \\    /   O peration     |
   5     \\  /    A nd           | Copyright (C) 2004-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 "List.H"
  31
  32 // * * * * * * * * * * * * * * * * Constructors  * * * * * * * * * * * * * * //
  33
  34 template<class T, class Key, class Hash>
  35 Foam::HashTable<T, Key, Hash>::HashTable(const label size)
  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>
  55 Foam::HashTable<T, Key, Hash>::HashTable(const HashTable<T, Key, Hash>& ht)
  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>
  79 Foam::HashTable<T, Key, Hash>::HashTable
  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>
  96 Foam::HashTable<T, Key, Hash>::~HashTable()
  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>
 137 typename Foam::HashTable<T, Key, Hash>::iterator
 138 Foam::HashTable<T, Key, Hash>::find
 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>
 169 typename Foam::HashTable<T, Key, Hash>::const_iterator
 170 Foam::HashTable<T, Key, Hash>::find
 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>
 201 Foam::List<Key> Foam::HashTable<T, Key, Hash>::toc() const
 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>
 216 Foam::List<Key> Foam::HashTable<T, Key, Hash>::sortedToc() const
 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>
 226 bool Foam::HashTable<T, Key, Hash>::set
 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>
 311 bool Foam::HashTable<T, Key, Hash>::iteratorBase::erase()
 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>
 379 bool Foam::HashTable<T, Key, Hash>::erase(const iterator& iter)
 380 {
 381     // adjust iterator after erase
 382     return const_cast<iterator&>(iter).erase();
 383 }
 384
 385
 386 template<class T, class Key, class Hash>
 387 bool Foam::HashTable<T, Key, Hash>::erase(const Key& key)
 388 {
 389     return erase(find(key));
 390 }
 391
 392
 393 template<class T, class Key, class Hash>
 394 Foam::label Foam::HashTable<T, Key, Hash>::erase(const UList<Key>& keys)
 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>
 414 Foam::label Foam::HashTable<T, Key, Hash>::erase
 415 (
 416     const HashTable<AnyType, Key, AnyHash>& rhs
 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>
 436 void Foam::HashTable<T, Key, Hash>::resize(const label sz)
 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>
 473 void Foam::HashTable<T, Key, Hash>::clear()
 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>
 497 void Foam::HashTable<T, Key, Hash>::clearStorage()
 498 {
 499     clear();
 500     resize(0);
 501 }
 502
 503
 504 template<class T, class Key, class Hash>
 505 void Foam::HashTable<T, Key, Hash>::shrink()
 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>
 518 void Foam::HashTable<T, Key, Hash>::transfer(HashTable<T, Key, Hash>& ht)
 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     {
 549         FatalErrorIn
 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 // ************************************************************************* //