src/OpenFOAM/containers/HashTables/HashTable/HashTableI.H

   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 #include "error.H"
  28
  29 // * * * * * * * * * * * * * Private Member Classes * * * * * * * * * * * * //
  30
  31 template<class T, class Key, class Hash>
  32 inline Foam::HashTable<T, Key, Hash>::hashedEntry::hashedEntry
  33 (
  34     const Key& key,
  35     hashedEntry* next,
  36     const T& newEntry
  37 )
  38 :
  39     key_(key),
  40     next_(next),
  41     obj_(newEntry)
  42 {}
  43
  44
  45 // * * * * * * * * * * * * Private Member Functions  * * * * * * * * * * * * //
  46
  47 template<class T, class Key, class Hash>
  48 inline Foam::label
  49 Foam::HashTable<T, Key, Hash>::hashKeyIndex(const Key& key) const
  50 {
  51     // size is power of two - this is the modulus
  52     return Hash()(key) & (tableSize_ - 1);
  53 }
  54
  55
  56 // * * * * * * * * * * * * * * * Member Functions * * * * * * * * * * * * * //
  57
  58 template<class T, class Key, class Hash>
  59 inline Foam::label Foam::HashTable<T, Key, Hash>::size() const
  60 {
  61     return nElmts_;
  62 }
  63
  64
  65 template<class T, class Key, class Hash>
  66 inline bool Foam::HashTable<T, Key, Hash>::empty() const
  67 {
  68     return !nElmts_;
  69 }
  70
  71
  72 template<class T, class Key, class Hash>
  73 inline bool Foam::HashTable<T, Key, Hash>::insert
  74 (
  75     const Key& key,
  76     const T& newEntry
  77 )
  78 {
  79     return set(key, newEntry, true);
  80 }
  81
  82
  83 template<class T, class Key, class Hash>
  84 inline bool Foam::HashTable<T, Key, Hash>::set
  85 (
  86     const Key& key,
  87     const T& newEntry
  88 )
  89 {
  90     return set(key, newEntry, false);
  91 }
  92
  93
  94 template<class T, class Key, class Hash>
  95 inline Foam::Xfer<Foam::HashTable<T, Key, Hash> >
  96 Foam::HashTable<T, Key, Hash>::xfer()
  97 {
  98     return xferMove(*this);
  99 }
 100
 101
 102 // * * * * * * * * * * * * * * * Member Operators  * * * * * * * * * * * * * //
 103
 104 template<class T, class Key, class Hash>
 105 inline T& Foam::HashTable<T, Key, Hash>::operator[](const Key& key)
 106 {
 107     iterator iter = find(key);
 108
 109     if (iter == end())
 110     {
 111         FatalErrorIn("HashTable<T, Key, Hash>::operator[](const Key&)")
 112             << key << " not found in table.  Valid entries: "
 113             << toc()
 114             << exit(FatalError);
 115     }
 116
 117     return *iter;
 118 }
 119
 120
 121 template<class T, class Key, class Hash>
 122 inline const T& Foam::HashTable<T, Key, Hash>::operator[](const Key& key) const
 123 {
 124     const_iterator iter = find(key);
 125
 126     if (iter == cend())
 127     {
 128         FatalErrorIn("HashTable<T, Key, Hash>::operator[](const Key&) const")
 129             << key << " not found in table.  Valid entries: "
 130             << toc()
 131             << exit(FatalError);
 132     }
 133
 134     return *iter;
 135 }
 136
 137
 138 template<class T, class Key, class Hash>
 139 inline T& Foam::HashTable<T, Key, Hash>::operator()(const Key& key)
 140 {
 141     iterator iter = find(key);
 142
 143     if (iter == end())
 144     {
 145         insert(key, T());
 146         return *find(key);
 147     }
 148     else
 149     {
 150         return *iter;
 151     }
 152 }
 153
 154
 155 // * * * * * * * * * * * * * * * * STL iterator  * * * * * * * * * * * * * * //
 156
 157 template<class T, class Key, class Hash>
 158 inline Foam::HashTable<T, Key, Hash>::iterator::iterator
 159 (
 160     HashTable<T, Key, Hash>& hashTbl,
 161     hashedEntry* elmt,
 162     label hashIndex
 163 )
 164 :
 165     hashTable_(hashTbl),
 166     elmtPtr_(elmt),
 167     hashIndex_(hashIndex)
 168 {}
 169
 170
 171 template<class T, class Key, class Hash>
 172 inline void Foam::HashTable<T, Key, Hash>::iterator::operator=
 173 (
 174     const iterator& iter
 175 )
 176 {
 177     elmtPtr_ = iter.elmtPtr_;
 178     hashIndex_ = iter.hashIndex_;
 179 }
 180
 181
 182 template<class T, class Key, class Hash>
 183 inline bool Foam::HashTable<T, Key, Hash>::iterator::operator==
 184 (
 185     const iterator& iter
 186 ) const
 187 {
 188     return elmtPtr_ == iter.elmtPtr_;
 189 }
 190
 191
 192 template<class T, class Key, class Hash>
 193 inline bool Foam::HashTable<T, Key, Hash>::iterator::operator!=
 194 (
 195     const iterator& iter
 196 ) const
 197 {
 198     return elmtPtr_ != iter.elmtPtr_;
 199 }
 200
 201
 202 template<class T, class Key, class Hash>
 203 inline bool Foam::HashTable<T, Key, Hash>::iterator::operator==
 204 (
 205     const const_iterator& iter
 206 ) const
 207 {
 208     return elmtPtr_ == iter.elmtPtr_;
 209 }
 210
 211
 212 template<class T, class Key, class Hash>
 213 inline bool Foam::HashTable<T, Key, Hash>::iterator::operator!=
 214 (
 215     const const_iterator& iter
 216 ) const
 217 {
 218     return elmtPtr_ != iter.elmtPtr_;
 219 }
 220
 221
 222 template<class T, class Key, class Hash>
 223 inline T&
 224 Foam::HashTable<T, Key, Hash>::iterator::operator*()
 225 {
 226     return elmtPtr_->obj_;
 227 }
 228
 229
 230 template<class T, class Key, class Hash>
 231 inline T&
 232 Foam::HashTable<T, Key, Hash>::iterator::operator()()
 233 {
 234     return elmtPtr_->obj_;
 235 }
 236
 237
 238 template<class T, class Key, class Hash>
 239 inline const T&
 240 Foam::HashTable<T, Key, Hash>::iterator::operator*() const
 241 {
 242     return elmtPtr_->obj_;
 243 }
 244
 245
 246 template<class T, class Key, class Hash>
 247 inline const T&
 248 Foam::HashTable<T, Key, Hash>::iterator::operator()() const
 249 {
 250     return elmtPtr_->obj_;
 251 }
 252
 253
 254 template<class T, class Key, class Hash>
 255 inline
 256 typename Foam::HashTable<T, Key, Hash>::iterator&
 257 Foam::HashTable<T, Key, Hash>::iterator::operator++()
 258 {
 259     // Check for special value from erase. (sets hashIndex to -1)
 260     if (hashIndex_ >= 0)
 261     {
 262         // Do we have additional elements on the SLList?
 263         if (elmtPtr_ && elmtPtr_->next_)
 264         {
 265             elmtPtr_ = elmtPtr_->next_;
 266             return *this;
 267         }
 268     }
 269
 270     // Step to the next table entry
 271     while
 272     (
 273         ++hashIndex_ < hashTable_.tableSize_
 274      && !(elmtPtr_ = hashTable_.table_[hashIndex_])
 275     )
 276     {}
 277
 278     if (hashIndex_ == hashTable_.tableSize_)
 279     {
 280         // make end iterator
 281         elmtPtr_ = 0;
 282         hashIndex_ = 0;
 283     }
 284     return *this;
 285 }
 286
 287
 288 template<class T, class Key, class Hash>
 289 inline typename Foam::HashTable<T, Key, Hash>::iterator
 290 Foam::HashTable<T, Key, Hash>::iterator::operator++
 291 (
 292     int
 293 )
 294 {
 295     iterator tmp = *this;
 296     ++*this;
 297     return tmp;
 298 }
 299
 300
 301 template<class T, class Key, class Hash>
 302 inline
 303 const Key& Foam::HashTable<T, Key, Hash>::iterator::key() const
 304 {
 305     return elmtPtr_->key_;
 306 }
 307
 308
 309 template<class T, class Key, class Hash>
 310 inline typename Foam::HashTable<T, Key, Hash>::iterator
 311 Foam::HashTable<T, Key, Hash>::begin()
 312 {
 313     label i = 0;
 314
 315     if (nElmts_)
 316     {
 317         while (table_ && !table_[i] && ++i < tableSize_)
 318         {}
 319     }
 320     else
 321     {
 322         i = tableSize_;
 323     }
 324
 325     if (i == tableSize_)
 326     {
 327 #       ifdef FULLDEBUG
 328         if (debug)
 329         {
 330             Info<< "HashTable is empty\n";
 331         }
 332 #       endif
 333
 334         return HashTable<T, Key, Hash>::endIter_;
 335     }
 336     else
 337     {
 338         return iterator(*this, table_[i], i);
 339     }
 340 }
 341
 342
 343 template<class T, class Key, class Hash>
 344 inline const typename Foam::HashTable<T, Key, Hash>::iterator&
 345 Foam::HashTable<T, Key, Hash>::end()
 346 {
 347     return HashTable<T, Key, Hash>::endIter_;
 348 }
 349
 350
 351 // * * * * * * * * * * * * * * * STL const_iterator * * * * * * * * * * * * * //
 352
 353 template<class T, class Key, class Hash>
 354 inline Foam::HashTable<T, Key, Hash>::const_iterator::const_iterator
 355 (
 356     const HashTable<T, Key, Hash>& hashTbl,
 357     const hashedEntry* elmt,
 358     label hashIndex
 359 )
 360 :
 361     hashTable_(hashTbl),
 362     elmtPtr_(elmt),
 363     hashIndex_(hashIndex)
 364 {}
 365
 366
 367 template<class T, class Key, class Hash>
 368 inline Foam::HashTable<T, Key, Hash>::const_iterator::const_iterator
 369 (
 370     const iterator& iter
 371 )
 372 :
 373     hashTable_(iter.hashTable_),
 374     elmtPtr_(iter.elmtPtr_),
 375     hashIndex_(iter.hashIndex_)
 376 {}
 377
 378
 379 template<class T, class Key, class Hash>
 380 inline void Foam::HashTable<T, Key, Hash>::const_iterator::operator=
 381 (
 382     const const_iterator& iter
 383 )
 384 {
 385     elmtPtr_ = iter.elmtPtr_;
 386     hashIndex_ = iter.hashIndex_;
 387 }
 388
 389
 390 template<class T, class Key, class Hash>
 391 inline bool Foam::HashTable<T, Key, Hash>::const_iterator::operator==
 392 (
 393     const const_iterator& iter
 394 ) const
 395 {
 396     return elmtPtr_ == iter.elmtPtr_;
 397 }
 398
 399
 400 template<class T, class Key, class Hash>
 401 inline bool Foam::HashTable<T, Key, Hash>::const_iterator::operator!=
 402 (
 403     const const_iterator& iter
 404 ) const
 405 {
 406     return elmtPtr_ != iter.elmtPtr_;
 407 }
 408
 409
 410 template<class T, class Key, class Hash>
 411 inline bool Foam::HashTable<T, Key, Hash>::const_iterator::operator==
 412 (
 413     const iterator& iter
 414 ) const
 415 {
 416     return elmtPtr_ == iter.elmtPtr_;
 417 }
 418
 419
 420 template<class T, class Key, class Hash>
 421 inline bool Foam::HashTable<T, Key, Hash>::const_iterator::operator!=
 422 (
 423     const iterator& iter
 424 ) const
 425 {
 426     return elmtPtr_ != iter.elmtPtr_;
 427 }
 428
 429
 430 template<class T, class Key, class Hash>
 431 inline const T&
 432 Foam::HashTable<T, Key, Hash>::const_iterator::operator*() const
 433 {
 434     return elmtPtr_->obj_;
 435 }
 436
 437 template<class T, class Key, class Hash>
 438 inline const T&
 439 Foam::HashTable<T, Key, Hash>::const_iterator::operator()() const
 440 {
 441     return elmtPtr_->obj_;
 442 }
 443
 444
 445 template<class T, class Key, class Hash>
 446 inline
 447 typename Foam::HashTable<T, Key, Hash>::const_iterator&
 448 Foam::HashTable<T, Key, Hash>::const_iterator::operator++()
 449 {
 450     if
 451     (
 452         !(elmtPtr_ = elmtPtr_->next_)
 453      && ++hashIndex_ < hashTable_.tableSize_
 454      && !(elmtPtr_ = hashTable_.table_[hashIndex_])
 455     )
 456     {
 457         while
 458         (
 459             ++hashIndex_ < hashTable_.tableSize_
 460          && !(elmtPtr_ = hashTable_.table_[hashIndex_])
 461         )
 462         {}
 463     }
 464
 465     return *this;
 466 }
 467
 468
 469 template<class T, class Key, class Hash>
 470 inline typename Foam::HashTable<T, Key, Hash>::const_iterator
 471 Foam::HashTable<T, Key, Hash>::const_iterator::operator++
 472 (
 473     int
 474 )
 475 {
 476     const_iterator tmp = *this;
 477     ++*this;
 478     return tmp;
 479 }
 480
 481
 482 template<class T, class Key, class Hash>
 483 inline
 484 const Key& Foam::HashTable<T, Key, Hash>::const_iterator::key() const
 485 {
 486     return elmtPtr_->key_;
 487 }
 488
 489
 490 template<class T, class Key, class Hash>
 491 inline typename Foam::HashTable<T, Key, Hash>::const_iterator
 492 Foam::HashTable<T, Key, Hash>::cbegin() const
 493 {
 494     label i = 0;
 495
 496     if (nElmts_)
 497     {
 498         while (table_ && !table_[i] && ++i < tableSize_)
 499         {}
 500     }
 501     else
 502     {
 503         i = tableSize_;
 504     }
 505
 506     if (i == tableSize_)
 507     {
 508 #       ifdef FULLDEBUG
 509         if (debug)
 510         {
 511             Info<< "HashTable is empty\n";
 512         }
 513 #       endif
 514
 515         return HashTable<T, Key, Hash>::endConstIter_;
 516     }
 517     else
 518     {
 519         return const_iterator(*this, table_[i], i);
 520     }
 521 }
 522
 523
 524 template<class T, class Key, class Hash>
 525 inline const typename Foam::HashTable<T, Key, Hash>::const_iterator&
 526 Foam::HashTable<T, Key, Hash>::cend() const
 527 {
 528     return HashTable<T, Key, Hash>::endConstIter_;
 529 }
 530
 531
 532 template<class T, class Key, class Hash>
 533 inline typename Foam::HashTable<T, Key, Hash>::const_iterator
 534 Foam::HashTable<T, Key, Hash>::begin() const
 535 {
 536     return this->cbegin();
 537 }
 538
 539
 540 template<class T, class Key, class Hash>
 541 inline const typename Foam::HashTable<T, Key, Hash>::const_iterator&
 542 Foam::HashTable<T, Key, Hash>::end() const
 543 {
 544     return HashTable<T, Key, Hash>::endConstIter_;
 545 }
 546
 547
 548 // ************************************************************************* //