src/foam/containers/Lists/PackedList/PackedListI.H

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