src/OpenFOAM/containers/Lists/PackedList/PackedListI.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
  28 #include "error.H"
  29 #include <climits>
  30
  31 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
  32
  33 template<unsigned nBits>
  34 inline unsigned int Foam::PackedList<nBits>::max_bits()
  35 {
  36     return sizeof(StorageType)*CHAR_BIT - 1;
  37 }
  38
  39
  40 template<unsigned nBits>
  41 inline unsigned int Foam::PackedList<nBits>::max_value()
  42 {
  43     return (1u << nBits) - 1;
  44 }
  45
  46
  47 template<unsigned nBits>
  48 inline unsigned int Foam::PackedList<nBits>::packing()
  49 {
  50     return sizeof(StorageType)*CHAR_BIT / nBits;
  51 }
  52
  53
  54 template<unsigned nBits>
  55 inline unsigned int Foam::PackedList<nBits>::maskLower(unsigned offset)
  56 {
  57     // return (1u << (nBits * offset)) - 1;
  58     // The next one works more reliably with overflows
  59     // eg, when compiled without optimization
  60     return (~0u >> ( sizeof(StorageType)*CHAR_BIT - nBits * offset));
  61 }
  62
  63
  64 template<unsigned nBits>
  65 inline Foam::label Foam::PackedList<nBits>::packedLength(const label nElem)
  66 {
  67     return (nElem + packing() - 1) / packing();
  68 }
  69
  70
  71 // * * * * * * * * * * * * * * * * Constructors  * * * * * * * * * * * * * * //
  72
  73 template<unsigned nBits>
  74 inline Foam::PackedList<nBits>::PackedList()
  75 :
  76     StorageList(),
  77     size_(0)
  78 {}
  79
  80
  81 template<unsigned nBits>
  82 inline Foam::PackedList<nBits>::PackedList(const label size)
  83 :
  84     StorageList(packedLength(size), 0u),
  85     size_(size)
  86 {}
  87
  88
  89 template<unsigned nBits>
  90 inline Foam::PackedList<nBits>::PackedList(const PackedList<nBits>& lst)
  91 :
  92     StorageList(lst),
  93     size_(lst.size_)
  94 {}
  95
  96
  97 template<unsigned nBits>
  98 inline Foam::PackedList<nBits>::PackedList(const Xfer<PackedList<nBits> >& lst)
  99 {
 100     transfer(lst());
 101 }
 102
 103
 104 template<unsigned nBits>
 105 inline Foam::autoPtr<Foam::PackedList<nBits> >
 106 Foam::PackedList<nBits>::clone() const
 107 {
 108     return autoPtr<PackedList<nBits> >(new PackedList<nBits>(*this));
 109 }
 110
 111
 112 // * * * * * * * * * * * * * * * * Iterators * * * * * * * * * * * * * * * * //
 113
 114 // iteratorBase
 115
 116 template<unsigned nBits>
 117 inline Foam::PackedList<nBits>::iteratorBase::iteratorBase()
 118 :
 119     list_(0),
 120     index_(0)
 121 {}
 122
 123
 124 template<unsigned nBits>
 125 inline Foam::PackedList<nBits>::iteratorBase::iteratorBase
 126 (
 127     const PackedList<nBits>* lst,
 128     const label i
 129 )
 130 :
 131     list_(const_cast<PackedList<nBits>*>(lst)),
 132     index_(i)
 133 {}
 134
 135
 136 template<unsigned nBits>
 137 inline unsigned int
 138 Foam::PackedList<nBits>::iteratorBase::get() const
 139 {
 140     const unsigned int seg = index_ / packing();
 141     const unsigned int off = index_ % packing();
 142
 143     const unsigned int& stored = list_->StorageList::operator[](seg);
 144     return (stored >> (nBits * off)) & max_value();
 145 }
 146
 147
 148 template<unsigned nBits>
 149 inline bool
 150 Foam::PackedList<nBits>::iteratorBase::set(const unsigned int val)
 151 {
 152     const unsigned int seg = index_ / packing();
 153     const unsigned int off = index_ % packing();
 154
 155     unsigned int& stored = list_->StorageList::operator[](seg);
 156     const unsigned int prev = stored;
 157
 158     const unsigned int startBit = nBits * off;
 159     const unsigned int maskNew  = max_value() << startBit;
 160
 161     if (val & ~max_value())
 162     {
 163         // overflow is max_value, fill everything
 164         stored |= maskNew;
 165     }
 166     else
 167     {
 168         stored &= ~maskNew;
 169         stored |= maskNew & (val << startBit);
 170     }
 171
 172     return prev != stored;
 173 }
 174
 175
 176 template<unsigned nBits>
 177 inline bool Foam::PackedList<nBits>::iteratorBase::operator==
 178 (
 179     const iteratorBase& iter
 180 ) const
 181 {
 182     return this->get() == iter.get();
 183 }
 184
 185
 186 template<unsigned nBits>
 187 inline bool Foam::PackedList<nBits>::iteratorBase::operator!=
 188 (
 189     const iteratorBase& iter
 190 ) const
 191 {
 192     return this->get() != iter.get();
 193 }
 194
 195
 196 template<unsigned nBits>
 197 inline unsigned int
 198 Foam::PackedList<nBits>::iteratorBase::operator=(const iteratorBase& iter)
 199 {
 200     const unsigned int val = iter.get();
 201     this->set(val);
 202     return val;
 203 }
 204
 205
 206 template<unsigned nBits>
 207 inline unsigned int
 208 Foam::PackedList<nBits>::iteratorBase::operator=(const unsigned int val)
 209 {
 210     // lazy evaluation - increase size on assigment
 211     if (index_ >= list_->size_)
 212     {
 213         list_->resize(index_ + 1);
 214     }
 215
 216     this->set(val);
 217     return val;
 218 }
 219
 220
 221 template<unsigned nBits>
 222 inline Foam::PackedList<nBits>::iteratorBase::operator
 223 unsigned int () const
 224 {
 225     // lazy evaluation - return 0 for out-of-range
 226     if (index_ >= list_->size_)
 227     {
 228         return 0;
 229     }
 230
 231     return this->get();
 232 }
 233
 234
 235 // const_iterator, iterator
 236
 237 template<unsigned nBits>
 238 inline Foam::PackedList<nBits>::iterator::iterator()
 239 :
 240     iteratorBase()
 241 {}
 242
 243
 244 template<unsigned nBits>
 245 inline Foam::PackedList<nBits>::const_iterator::const_iterator()
 246 :
 247     iteratorBase()
 248 {}
 249
 250
 251 template<unsigned nBits>
 252 inline Foam::PackedList<nBits>::iterator::iterator
 253 (
 254     const iteratorBase& iter
 255 )
 256 :
 257     iteratorBase(iter)
 258 {
 259     // avoid going past end()
 260     // eg, iter = iterator(list, Inf)
 261     if (this->index_ > this->list_->size_)
 262     {
 263         this->index_ = this->list_->size_;
 264     }
 265 }
 266
 267
 268 template<unsigned nBits>
 269 inline Foam::PackedList<nBits>::const_iterator::const_iterator
 270 (
 271     const iteratorBase& iter
 272 )
 273 :
 274     iteratorBase(iter)
 275 {
 276     // avoid going past end()
 277     // eg, iter = iterator(list, Inf)
 278     if (this->index_ > this->list_->size_)
 279     {
 280         this->index_ = this->list_->size_;
 281     }
 282 }
 283
 284
 285 template<unsigned nBits>
 286 inline Foam::PackedList<nBits>::iterator::iterator
 287 (
 288     const PackedList<nBits>* lst,
 289     const label i
 290 )
 291 :
 292     iteratorBase(lst, i)
 293 {}
 294
 295
 296 template<unsigned nBits>
 297 inline Foam::PackedList<nBits>::const_iterator::const_iterator
 298 (
 299     const PackedList<nBits>* lst,
 300     const label i
 301 )
 302 :
 303     iteratorBase(lst, i)
 304 {}
 305
 306
 307 template<unsigned nBits>
 308 inline Foam::PackedList<nBits>::const_iterator::const_iterator
 309 (
 310     const iterator& iter
 311 )
 312 :
 313     iteratorBase(static_cast<const iteratorBase&>(iter))
 314 {}
 315
 316
 317 template<unsigned nBits>
 318 inline bool Foam::PackedList<nBits>::iterator::operator==
 319 (
 320     const iteratorBase& iter
 321 ) const
 322 {
 323     return this->index_ == iter.index_;
 324 }
 325
 326
 327 template<unsigned nBits>
 328 inline bool Foam::PackedList<nBits>::iterator::operator!=
 329 (
 330     const iteratorBase& iter
 331 ) const
 332 {
 333     return this->index_ != iter.index_;
 334 }
 335
 336
 337
 338 template<unsigned nBits>
 339 inline bool Foam::PackedList<nBits>::const_iterator::operator==
 340 (
 341     const iteratorBase& iter
 342 ) const
 343 {
 344     return this->index_ == iter.index_;
 345 }
 346
 347
 348 template<unsigned nBits>
 349 inline bool Foam::PackedList<nBits>::const_iterator::operator!=
 350 (
 351     const iteratorBase& iter
 352 ) const
 353 {
 354     return this->index_ != iter.index_;
 355 }
 356
 357
 358
 359 template<unsigned nBits>
 360 inline typename Foam::PackedList<nBits>::iterator&
 361 Foam::PackedList<nBits>::iterator::operator=(const iteratorBase& iter)
 362 {
 363     this->list_  = iter.list_;
 364     this->index_ = iter.index_;
 365
 366     // avoid going past end()
 367     // eg, iter = iterator(list, Inf)
 368     if (this->index_ > this->list_->size_)
 369     {
 370         this->index_ = this->list_->size_;
 371     }
 372
 373     return *this;
 374 }
 375
 376
 377 template<unsigned nBits>
 378 inline typename Foam::PackedList<nBits>::const_iterator&
 379 Foam::PackedList<nBits>::const_iterator::operator=(const iteratorBase& iter)
 380 {
 381     this->list_  = iter.list_;
 382     this->index_ = iter.index_;
 383
 384     // avoid going past end()
 385     // eg, iter = iterator(list, Inf)
 386     if (this->index_ > this->list_->size_)
 387     {
 388         this->index_ = this->list_->size_;
 389     }
 390
 391     return *this;
 392 }
 393
 394
 395 template<unsigned nBits>
 396 inline typename Foam::PackedList<nBits>::iterator&
 397 Foam::PackedList<nBits>::iterator::operator++()
 398 {
 399     ++this->index_;
 400     return *this;
 401 }
 402
 403
 404 template<unsigned nBits>
 405 inline typename Foam::PackedList<nBits>::const_iterator&
 406 Foam::PackedList<nBits>::const_iterator::operator++()
 407 {
 408     ++this->index_;
 409     return *this;
 410 }
 411
 412
 413 template<unsigned nBits>
 414 inline typename Foam::PackedList<nBits>::iterator
 415 Foam::PackedList<nBits>::iterator::operator++(int)
 416 {
 417     iterator old = *this;
 418     ++this->index_;
 419     return old;
 420 }
 421
 422
 423 template<unsigned nBits>
 424 inline typename Foam::PackedList<nBits>::const_iterator
 425 Foam::PackedList<nBits>::const_iterator::operator++(int)
 426 {
 427     const_iterator old = *this;
 428     ++this->index_;
 429     return old;
 430 }
 431
 432
 433 template<unsigned nBits>
 434 inline typename Foam::PackedList<nBits>::iterator&
 435 Foam::PackedList<nBits>::iterator::operator--()
 436 {
 437     --this->index_;
 438     return *this;
 439 }
 440
 441
 442 template<unsigned nBits>
 443 inline typename Foam::PackedList<nBits>::const_iterator&
 444 Foam::PackedList<nBits>::const_iterator::operator--()
 445 {
 446     --this->index_;
 447     return *this;
 448 }
 449
 450
 451 template<unsigned nBits>
 452 inline typename Foam::PackedList<nBits>::iterator
 453 Foam::PackedList<nBits>::iterator::operator--(int)
 454 {
 455     iterator old = *this;
 456     --this->index_;
 457     return old;
 458 }
 459
 460
 461 template<unsigned nBits>
 462 inline typename Foam::PackedList<nBits>::const_iterator
 463 Foam::PackedList<nBits>::const_iterator::operator--(int)
 464 {
 465     const_iterator old = *this;
 466     --this->index_;
 467     return old;
 468 }
 469
 470
 471 template<unsigned nBits>
 472 inline typename Foam::PackedList<nBits>::iteratorBase&
 473 Foam::PackedList<nBits>::iterator::operator*()
 474 {
 475     return static_cast<iteratorBase&>(*this);
 476 }
 477
 478
 479 template<unsigned nBits>
 480 inline typename Foam::PackedList<nBits>::iteratorBase&
 481 Foam::PackedList<nBits>::iterator::operator()()
 482 {
 483     return static_cast<iteratorBase&>(*this);
 484 }
 485
 486
 487 template<unsigned nBits>
 488 inline unsigned int
 489 Foam::PackedList<nBits>::const_iterator::operator*() const
 490 {
 491     return this->get();
 492 }
 493
 494
 495 template<unsigned nBits>
 496 inline unsigned int
 497 Foam::PackedList<nBits>::const_iterator::operator()() const
 498 {
 499     return this->get();
 500 }
 501
 502
 503 template<unsigned nBits>
 504 inline typename Foam::PackedList<nBits>::iterator
 505 Foam::PackedList<nBits>::begin()
 506 {
 507     return iterator(this, 0);
 508 }
 509
 510
 511 template<unsigned nBits>
 512 inline typename Foam::PackedList<nBits>::const_iterator
 513 Foam::PackedList<nBits>::begin() const
 514 {
 515     return const_iterator(this, 0);
 516 }
 517
 518
 519 template<unsigned nBits>
 520 inline typename Foam::PackedList<nBits>::const_iterator
 521 Foam::PackedList<nBits>::cbegin() const
 522 {
 523     return const_iterator(this, 0);
 524 }
 525
 526
 527 template<unsigned nBits>
 528 inline typename Foam::PackedList<nBits>::iterator
 529 Foam::PackedList<nBits>::end()
 530 {
 531     return iterator(this, size_);
 532 }
 533
 534
 535 template<unsigned nBits>
 536 inline typename Foam::PackedList<nBits>::const_iterator
 537 Foam::PackedList<nBits>::end() const
 538 {
 539     return const_iterator(this, size_);
 540 }
 541
 542
 543 template<unsigned nBits>
 544 inline typename Foam::PackedList<nBits>::const_iterator
 545 Foam::PackedList<nBits>::cend() const
 546 {
 547     return const_iterator(this, size_);
 548 }
 549
 550
 551 // * * * * * * * * * * * * * * * Member Functions  * * * * * * * * * * * * * //
 552
 553 template<unsigned nBits>
 554 inline Foam::label Foam::PackedList<nBits>::size() const
 555 {
 556     return size_;
 557 }
 558
 559
 560 template<unsigned nBits>
 561 inline bool Foam::PackedList<nBits>::empty() const
 562 {
 563     return !size_;
 564 }
 565
 566
 567 template<unsigned nBits>
 568 inline void Foam::PackedList<nBits>::resize
 569 (
 570     const label nElem,
 571     const unsigned int& val
 572 )
 573 {
 574     reserve(nElem);
 575
 576     if (nElem > size_)
 577     {
 578         // fill new elements or newly exposed elements
 579         if (size_)
 580         {
 581             // fill value for complete segments
 582             unsigned int fill = val;
 583
 584             if (fill & ~max_value())
 585             {
 586                 // overflow is max_value, fill everything
 587                 fill = ~0u;
 588             }
 589             else
 590             {
 591                 for (unsigned int i = 1; i < packing(); ++i)
 592                 {
 593                     fill |= (fill << nBits);
 594                 }
 595             }
 596
 597             unsigned int seg = size_ / packing();
 598             unsigned int off = size_ % packing();
 599
 600             // partial segment, preserve existing value
 601             if (off)
 602             {
 603                 unsigned int maskOld = maskLower(off);
 604
 605                 StorageList::operator[](seg) &= maskOld;
 606                 StorageList::operator[](seg) |= ~maskOld & fill;
 607
 608                 // continue with the next segment
 609                 seg++;
 610             }
 611
 612             unsigned int endSeg = nElem / packing();
 613             // fill in complete elements
 614             while (seg < endSeg)
 615             {
 616                 StorageList::operator[](seg++) = fill;
 617             }
 618         }
 619         else
 620         {
 621             // no original size - simply flood-fill
 622             operator=(val);
 623         }
 624     }
 625
 626     size_ = nElem;
 627 }
 628
 629
 630 template<unsigned nBits>
 631 inline void Foam::PackedList<nBits>::setSize
 632 (
 633     const label newSize,
 634     const unsigned int& val
 635 )
 636 {
 637     resize(newSize, val);
 638 }
 639
 640
 641
 642 template<unsigned nBits>
 643 inline Foam::label Foam::PackedList<nBits>::capacity() const
 644 {
 645     return packing() * StorageList::size();
 646 }
 647
 648
 649 template<unsigned nBits>
 650 inline void Foam::PackedList<nBits>::setCapacity(const label nElem)
 651 {
 652     StorageList::setSize(packedLength(nElem), 0u);
 653
 654     // truncate addressed size too?
 655     if (size_ > nElem)
 656     {
 657         size_ = nElem;
 658     }
 659 }
 660
 661
 662 template<unsigned nBits>
 663 inline void Foam::PackedList<nBits>::reserve
 664 (
 665     const label nElem
 666 )
 667 {
 668     label len = packedLength(nElem);
 669
 670     // need more capacity?
 671     if (len > StorageList::size())
 672     {
 673         // Like DynamicList with SizeInc=0, SizeMult=2, SizeDiv=1
 674         StorageList::setSize
 675         (
 676             max
 677             (
 678                 len,
 679                 StorageList::size()*2
 680             ),
 681             0u
 682         );
 683     }
 684 }
 685
 686
 687 template<unsigned nBits>
 688 inline void Foam::PackedList<nBits>::clear()
 689 {
 690     size_ = 0;
 691 }
 692
 693
 694 template<unsigned nBits>
 695 inline void Foam::PackedList<nBits>::clearStorage()
 696 {
 697     StorageList::clear();
 698     size_ = 0;
 699 }
 700
 701
 702 template<unsigned nBits>
 703 inline void Foam::PackedList<nBits>::shrink()
 704 {
 705     label len = packedLength(size_);
 706
 707     // we have unused space?
 708     if (len < StorageList::size())
 709     {
 710         StorageList::setSize(len);
 711     }
 712 }
 713
 714 template<unsigned nBits>
 715 inline Foam::List<unsigned int>&
 716 Foam::PackedList<nBits>::storage()
 717 {
 718     return static_cast<StorageList&>(*this);
 719 }
 720
 721
 722 template<unsigned nBits>
 723 inline const Foam::List<unsigned int>&
 724 Foam::PackedList<nBits>::storage() const
 725 {
 726     return static_cast<const StorageList&>(*this);
 727 }
 728
 729
 730 template<unsigned nBits>
 731 inline void Foam::PackedList<nBits>::transfer(PackedList<nBits>& lst)
 732 {
 733     size_ = lst.size_;
 734     lst.size_ = 0;
 735
 736     StorageList::transfer(lst);
 737 }
 738
 739
 740 template<unsigned nBits>
 741 inline Foam::Xfer< Foam::PackedList<nBits> >
 742 Foam::PackedList<nBits>::xfer()
 743 {
 744     return xferMove(*this);
 745 }
 746
 747
 748 template<unsigned nBits>
 749 inline unsigned int Foam::PackedList<nBits>::get(const label i) const
 750 {
 751 #   ifdef FULLDEBUG
 752     if (i < 0)
 753     {
 754         FatalErrorIn("PackedList<nBits>::get(const label)")
 755             << "negative index " << i << " max=" << size_-1
 756             << abort(FatalError);
 757     }
 758 #   endif
 759
 760     // lazy evaluation - return 0 for out-of-range
 761     if (i < size_)
 762     {
 763         return iteratorBase(this, i).get();
 764     }
 765     else
 766     {
 767         return 0;
 768     }
 769 }
 770
 771
 772 template<unsigned nBits>
 773 inline unsigned int Foam::PackedList<nBits>::operator[](const label i) const
 774 {
 775     // lazy evaluation - return 0 for out-of-range
 776     if (i < size_)
 777     {
 778         return iteratorBase(this, i).get();
 779     }
 780     else
 781     {
 782         return 0;
 783     }
 784 }
 785
 786
 787 template<unsigned nBits>
 788 inline bool Foam::PackedList<nBits>::set
 789 (
 790     const label i,
 791     const unsigned int val
 792 )
 793 {
 794 #   ifdef FULLDEBUG
 795     if (i < 0)
 796     {
 797         FatalErrorIn("PackedList<nBits>::set(const label)")
 798             << "negative index " << i << " max=" << size_-1
 799             << abort(FatalError);
 800     }
 801 #   endif
 802
 803     // lazy evaluation - increase size on assigment
 804     if (i >= size_)
 805     {
 806         resize(i + 1);
 807     }
 808
 809     return iteratorBase(this, i).set(val);
 810 }
 811
 812
 813 template<unsigned nBits>
 814 inline bool Foam::PackedList<nBits>::unset(const label i)
 815 {
 816     // lazy - ignore out-of-bounds
 817     if (i < 0 || i >= size_)
 818     {
 819         return false;
 820     }
 821
 822     return iteratorBase(this, i).set(0u);
 823 }
 824
 825
 826 template<unsigned nBits>
 827 inline void Foam::PackedList<nBits>::append(const unsigned int val)
 828 {
 829     label elemI = size_;
 830     reserve(elemI + 1);
 831     size_++;
 832
 833     iteratorBase(this, elemI).set(val);
 834 }
 835
 836
 837 template<unsigned nBits>
 838 inline unsigned int Foam::PackedList<nBits>::remove()
 839 {
 840     if (!size_)
 841     {
 842         FatalErrorIn
 843         (
 844             "Foam::PackedList<nBits>::remove()"
 845         )   << "List is empty" << abort(FatalError);
 846     }
 847
 848     label elemI = size_ - 1;
 849     const unsigned int val = iteratorBase(this, elemI).get();
 850     resize(elemI);
 851
 852     return val;
 853 }
 854
 855
 856 template<unsigned nBits>
 857 inline typename Foam::PackedList<nBits>::iteratorBase
 858 Foam::PackedList<nBits>::operator[](const label i)
 859 {
 860     return iteratorBase(this, i);
 861 }
 862
 863
 864 namespace Foam
 865 {
 866     // specialization for nBits=1
 867     template<>
 868     inline void Foam::PackedList<1>::operator=(const unsigned int val)
 869     {
 870         if (val)
 871         {
 872             StorageList::operator=(~0u);
 873         }
 874         else
 875         {
 876             StorageList::operator=(0u);
 877         }
 878     }
 879 }
 880
 881
 882 template<unsigned nBits>
 883 inline void Foam::PackedList<nBits>::operator=(const unsigned int val)
 884 {
 885     if (val)
 886     {
 887         unsigned int fill = val;
 888
 889         if (fill & ~max_value())
 890         {
 891             // treat overflow as max_value
 892             fill = ~0u;
 893         }
 894         else
 895         {
 896             for (unsigned int i = 1; i < packing(); ++i)
 897             {
 898                 fill |= (fill << nBits);
 899             }
 900         }
 901
 902         StorageList::operator=(fill);
 903     }
 904     else
 905     {
 906         StorageList::operator=(0u);
 907     }
 908 }
 909
 910
 911 // ************************************************************************* //