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