src/OpenFOAM/containers/HashTables/StaticHashTable/StaticHashTable.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 StaticHashTable_C
  28 #define StaticHashTable_C
  29
  30 #include "StaticHashTable.H"
  31 #include "List.H"
  32 #include "IOstreams.H"
  33
  34 // * * * * * * * * * * * * Private Member Functions  * * * * * * * * * * * * //
  35
  36 template<class T, class Key, class Hash>
  37 Foam::label Foam::StaticHashTable<T, Key, Hash>::canonicalSize(const label size)
  38 {
  39     if (size < 1)
  40     {
  41         return 0;
  42     }
  43
  44     // enforce power of two
  45     unsigned int goodSize = size;
  46
  47     if (goodSize & (goodSize - 1))
  48     {
  49         // brute-force is fast enough
  50         goodSize = 1;
  51         while (goodSize < unsigned(size))
  52         {
  53             goodSize <<= 1;
  54         }
  55     }
  56
  57     return goodSize;
  58 }
  59
  60
  61 // * * * * * * * * * * * * * * * * Constructors  * * * * * * * * * * * * * * //
  62
  63 // Construct given initial table size
  64 template<class T, class Key, class Hash>
  65 Foam::StaticHashTable<T, Key, Hash>::StaticHashTable(const label size)
  66 :
  67     StaticHashTableName(),
  68     keys_(canonicalSize(size)),
  69     objects_(keys_.size()),
  70     nElmts_(0),
  71     endIter_(*this, keys_.size(), 0),
  72     endConstIter_(*this, keys_.size(), 0)
  73 {
  74     if (size < 1)
  75     {
  76         FatalErrorIn
  77         (
  78             "StaticHashTable<T, Key, Hash>::StaticHashTable(const label size)"
  79         )   << "Illegal size " << size << " for StaticHashTable."
  80             << " Minimum size is 1" << abort(FatalError);
  81     }
  82 }
  83
  84
  85 // Construct as copy
  86 template<class T, class Key, class Hash>
  87 Foam::StaticHashTable<T, Key, Hash>::StaticHashTable
  88 (
  89     const StaticHashTable<T, Key, Hash>& ht
  90 )
  91 :
  92     StaticHashTableName(),
  93     keys_(ht.keys_),
  94     objects_(ht.objects_),
  95     nElmts_(ht.nElmts_),
  96     endIter_(*this, keys_.size(), 0),
  97     endConstIter_(*this, keys_.size(), 0)
  98 {}
  99
 100
 101
 102 template<class T, class Key, class Hash>
 103 Foam::StaticHashTable<T, Key, Hash>::StaticHashTable
 104 (
 105     const Xfer< StaticHashTable<T, Key, Hash> >& ht
 106 )
 107 :
 108     StaticHashTableName(),
 109     keys_(0),
 110     objects_(0),
 111     nElmts_(0),
 112     endIter_(*this, 0, 0),
 113     endConstIter_(*this, 0, 0)
 114 {
 115     transfer(ht());
 116 }
 117
 118
 119 // * * * * * * * * * * * * * * * * Destructor  * * * * * * * * * * * * * * * //
 120
 121 template<class T, class Key, class Hash>
 122 Foam::StaticHashTable<T, Key, Hash>::~StaticHashTable()
 123 {}
 124
 125
 126 // * * * * * * * * * * * * * * * Member Functions  * * * * * * * * * * * * * //
 127
 128 template<class T, class Key, class Hash>
 129 bool Foam::StaticHashTable<T, Key, Hash>::found(const Key& key) const
 130 {
 131     if (nElmts_)
 132     {
 133         const label hashIdx = hashKeyIndex(key);
 134         const List<Key>& localKeys = keys_[hashIdx];
 135
 136         forAll(localKeys, elemIdx)
 137         {
 138             if (key == localKeys[elemIdx])
 139             {
 140                 return true;
 141             }
 142         }
 143     }
 144
 145 #   ifdef FULLDEBUG
 146     if (debug)
 147     {
 148         Info<< "StaticHashTable<T, Key, Hash>::found(const Key&) : "
 149             << "Entry " << key << " not found in hash table\n";
 150     }
 151 #   endif
 152
 153     return false;
 154 }
 155
 156
 157 template<class T, class Key, class Hash>
 158 typename Foam::StaticHashTable<T, Key, Hash>::iterator
 159 Foam::StaticHashTable<T, Key, Hash>::find
 160 (
 161     const Key& key
 162 )
 163 {
 164     if (nElmts_)
 165     {
 166         const label hashIdx = hashKeyIndex(key);
 167         const List<Key>& localKeys = keys_[hashIdx];
 168
 169         forAll(localKeys, elemIdx)
 170         {
 171             if (key == localKeys[elemIdx])
 172             {
 173                 return iterator(*this, hashIdx, elemIdx);
 174             }
 175         }
 176     }
 177
 178 #   ifdef FULLDEBUG
 179     if (debug)
 180     {
 181         Info<< "StaticHashTable<T, Key, Hash>::find(const Key&) : "
 182             << "Entry " << key << " not found in hash table\n";
 183     }
 184 #   endif
 185
 186     return end();
 187 }
 188
 189
 190 template<class T, class Key, class Hash>
 191 typename Foam::StaticHashTable<T, Key, Hash>::const_iterator
 192 Foam::StaticHashTable<T, Key, Hash>::find
 193 (
 194     const Key& key
 195 ) const
 196 {
 197     if (nElmts_)
 198     {
 199         const label hashIdx = hashKeyIndex(key);
 200         const List<Key>& localKeys = keys_[hashIdx];
 201
 202         forAll(localKeys, elemIdx)
 203         {
 204             if (key == localKeys[elemIdx])
 205             {
 206                 return const_iterator(*this, hashIdx, elemIdx);
 207             }
 208         }
 209     }
 210
 211 #   ifdef FULLDEBUG
 212     if (debug)
 213     {
 214         Info<< "StaticHashTable<T, Key, Hash>::find(const Key&) const : "
 215             << "Entry " << key << " not found in hash table\n";
 216     }
 217 #   endif
 218
 219     return cend();
 220 }
 221
 222
 223 // Return the table of contents
 224 template<class T, class Key, class Hash>
 225 Foam::List<Key> Foam::StaticHashTable<T, Key, Hash>::toc() const
 226 {
 227     List<Key> tofc(nElmts_);
 228     label i = 0;
 229
 230     for (const_iterator iter = cbegin(); iter != cend(); ++iter)
 231     {
 232         tofc[i++] = iter.key();
 233     }
 234
 235     return tofc;
 236 }
 237
 238
 239 template<class T, class Key, class Hash>
 240 bool Foam::StaticHashTable<T, Key, Hash>::set
 241 (
 242     const Key& key,
 243     const T& newEntry,
 244     const bool protect
 245 )
 246 {
 247     const label hashIdx = hashKeyIndex(key);
 248     List<Key>& localKeys = keys_[hashIdx];
 249
 250     label existing = localKeys.size();
 251     forAll(localKeys, elemIdx)
 252     {
 253         if (key == localKeys[elemIdx])
 254         {
 255             existing = elemIdx;
 256             break;
 257         }
 258     }
 259
 260     if (existing == localKeys.size())
 261     {
 262         // not found, append
 263         List<T>& localObjects = objects_[hashIdx];
 264
 265         localKeys.setSize(existing+1);
 266         localObjects.setSize(existing+1);
 267
 268         localKeys[existing] = key;
 269         localObjects[existing] = newEntry;
 270
 271         nElmts_++;
 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<< "StaticHashTable<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         objects_[hashIdx][existing] = newEntry;
 292     }
 293
 294     return true;
 295 }
 296
 297
 298 template<class T, class Key, class Hash>
 299 bool Foam::StaticHashTable<T, Key, Hash>::erase(const iterator& cit)
 300 {
 301     if (cit != end())
 302     {
 303         List<Key>& localKeys = keys_[cit.hashIndex_];
 304         List<T>& localObjects = objects_[cit.hashIndex_];
 305
 306         // Copy down
 307         for (label i = cit.elemIndex_+1; i < localKeys.size(); i++)
 308         {
 309             localKeys[i-1] = localKeys[i];
 310             localObjects[i-1] = localObjects[i];
 311         }
 312         localKeys.setSize(localKeys.size()-1);
 313         localObjects.setSize(localObjects.size()-1);
 314
 315         // adjust iterator after erase
 316         iterator& it = const_cast<iterator&>(cit);
 317
 318         it.elemIndex_--;
 319         if (it.elemIndex_ < 0)
 320         {
 321             // No previous element in the local list
 322
 323             // Search back for previous non-zero table entry
 324             while (--it.hashIndex_ >= 0 && !objects_[it.hashIndex_].size())
 325             {}
 326
 327             if (it.hashIndex_ >= 0)
 328             {
 329                 // The last element in the local list
 330                 it.elemIndex_ = objects_[it.hashIndex_].size() - 1;
 331             }
 332             else
 333             {
 334                 // No previous found. Mark with special value which is
 335                 // - not end()
 336                 // - handled by operator++
 337                 it.hashIndex_ = -1;
 338                 it.elemIndex_ = 0;
 339             }
 340         }
 341
 342         nElmts_--;
 343
 344 #       ifdef FULLDEBUG
 345         if (debug)
 346         {
 347             Info<< "StaticHashTable<T, Key, Hash>::erase(iterator&) : "
 348                 << "hashedEntry removed.\n";
 349         }
 350 #       endif
 351
 352         return true;
 353     }
 354     else
 355     {
 356 #       ifdef FULLDEBUG
 357         if (debug)
 358         {
 359             Info<< "StaticHashTable<T, Key, Hash>::erase(iterator&) : "
 360                 << "cannot remove hashedEntry from hash table\n";
 361         }
 362 #       endif
 363
 364         return false;
 365     }
 366 }
 367
 368
 369 template<class T, class Key, class Hash>
 370 bool Foam::StaticHashTable<T, Key, Hash>::erase(const Key& key)
 371 {
 372     iterator it = find(key);
 373
 374     if (it != end())
 375     {
 376         return erase(it);
 377     }
 378     else
 379     {
 380         return false;
 381     }
 382 }
 383
 384
 385 template<class T, class Key, class Hash>
 386 Foam::label Foam::StaticHashTable<T, Key, Hash>::erase
 387 (
 388     const StaticHashTable<T, Key, Hash>& rhs
 389 )
 390 {
 391     label count = 0;
 392
 393     // Remove rhs elements from this table
 394     // NOTE: could optimize depending on which hash is smaller
 395     for (iterator iter = this->begin(); iter != this->end(); ++iter)
 396     {
 397         if (rhs.found(iter.key()) && erase(iter))
 398         {
 399             count++;
 400         }
 401     }
 402
 403    return count;
 404 }
 405
 406
 407 template<class T, class Key, class Hash>
 408 void Foam::StaticHashTable<T, Key, Hash>::resize(const label sz)
 409 {
 410     label newSize = canonicalSize(sz);
 411
 412     if (newSize == keys_.size())
 413     {
 414 #       ifdef FULLDEBUG
 415         if (debug)
 416         {
 417             Info<< "StaticHashTable<T, Key, Hash>::resize(const label) : "
 418                 << "new table size == old table size\n";
 419         }
 420 #       endif
 421
 422         return;
 423     }
 424
 425     if (newSize < 1)
 426     {
 427         FatalErrorIn
 428         (
 429             "StaticHashTable<T, Key, Hash>::resize(const label)"
 430         )   << "Illegal size " << newSize << " for StaticHashTable."
 431             << " Minimum size is 1" << abort(FatalError);
 432     }
 433
 434
 435     StaticHashTable<T, Key, Hash> newTable(newSize);
 436
 437     for (const_iterator iter = cbegin(); iter != cend(); ++iter)
 438     {
 439         newTable.insert(iter.key(), *iter);
 440     }
 441
 442     transfer(newTable);
 443
 444     // Adapt end() iterators
 445     endIter_.hashIndex_ = keys_.size();
 446     endConstIter_.hashIndex_ = keys_.size();
 447 }
 448
 449
 450 template<class T, class Key, class Hash>
 451 void Foam::StaticHashTable<T, Key, Hash>::clear()
 452 {
 453     forAll(keys_, hashIdx)
 454     {
 455         keys_[hashIdx].clear();
 456         objects_[hashIdx].clear();
 457     }
 458
 459     nElmts_ = 0;
 460 }
 461
 462
 463 template<class T, class Key, class Hash>
 464 void Foam::StaticHashTable<T, Key, Hash>::clearStorage()
 465 {
 466     clear();
 467     resize(1);
 468 }
 469
 470
 471
 472 template<class T, class Key, class Hash>
 473 void Foam::StaticHashTable<T, Key, Hash>::transfer
 474 (
 475     StaticHashTable<T, Key, Hash>& ht
 476 )
 477 {
 478     // Remove existing elements
 479     clear();
 480
 481     // Copy data from ht
 482     keys_.transfer(ht.keys_);
 483     objects_.transfer(ht.objects_);
 484
 485     nElmts_ = ht.nElmts_;
 486     ht.nElmts_ = 0;
 487
 488     // Adapt end() iterators
 489     endIter_.hashIndex_ = keys_.size();
 490     endConstIter_.hashIndex_ = keys_.size();
 491
 492     ht.endIter_.hashIndex_ = 0;
 493     ht.endConstIter_.hashIndex_ = 0;
 494 }
 495
 496
 497 // * * * * * * * * * * * * * * * Member Operators  * * * * * * * * * * * * * //
 498
 499 template<class T, class Key, class Hash>
 500 void Foam::StaticHashTable<T, Key, Hash>::operator=
 501 (
 502     const StaticHashTable<T, Key, Hash>& rhs
 503 )
 504 {
 505     // Check for assignment to self
 506     if (this == &rhs)
 507     {
 508         FatalErrorIn
 509         (
 510             "StaticHashTable<T, Key, Hash>::operator="
 511             "(const StaticHashTable<T, Key, Hash>&)"
 512         )   << "attempted assignment to self"
 513             << abort(FatalError);
 514     }
 515
 516
 517     // keys could be empty from a previous transfer()
 518     if (keys_.empty())
 519     {
 520         keys_.setSize(rhs.keys_.size());
 521         objects_.setSize(keys_.size());
 522
 523         // Adapt end() iterators
 524         endIter_.hashIndex_ = keys_.size();
 525         endConstIter_.hashIndex_ = keys_.size();
 526     }
 527     else
 528     {
 529         clear();
 530         // keys_.size() does not change so neither does end() iterator.
 531     }
 532
 533
 534     for (const_iterator iter = rhs.cbegin(); iter != rhs.cend(); ++iter)
 535     {
 536         insert(iter.key(), *iter);
 537     }
 538 }
 539
 540 template<class T, class Key, class Hash>
 541 bool Foam::StaticHashTable<T, Key, Hash>::operator==
 542 (
 543     const StaticHashTable<T, Key, Hash>& rhs
 544 ) const
 545 {
 546     // Are all my elements in rhs?
 547     for (const_iterator iter = cbegin(); iter != cend(); ++iter)
 548     {
 549         const_iterator fnd = rhs.find(iter.key());
 550
 551         if (fnd == rhs.cend() || fnd() != iter())
 552         {
 553             return false;
 554         }
 555     }
 556
 557     // Are all rhs elements in me?
 558     for (const_iterator iter = rhs.cbegin(); iter != rhs.cend(); ++iter)
 559     {
 560         const_iterator fnd = find(iter.key());
 561
 562         if (fnd == cend() || fnd() != iter())
 563         {
 564             return false;
 565         }
 566     }
 567     return true;
 568 }
 569
 570
 571 template<class T, class Key, class Hash>
 572 bool Foam::StaticHashTable<T, Key, Hash>::operator!=
 573 (
 574     const StaticHashTable<T, Key, Hash>& rhs
 575 ) const
 576 {
 577     return !(operator==(rhs));
 578 }
 579
 580
 581 // * * * * * * * * * * * * * * * Friend Operators  * * * * * * * * * * * * * //
 582
 583 #include "StaticHashTableIO.C"
 584
 585 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
 586
 587 #endif
 588
 589 // ************************************************************************* //