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