src/foam/containers/Lists/PackedList/PackedList.C

   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 #include "PackedList.H"
  27
  28 // * * * * * * * * * * * * * * * * Constructors  * * * * * * * * * * * * * * //
  29
  30 template<unsigned nBits>
  31 Foam::PackedList<nBits>::PackedList(const label size, const unsigned int val)
  32 :
  33     StorageList(packedLength(size), 0u),
  34     size_(size)
  35 {
  36     operator=(val);
  37 }
  38
  39
  40 template<unsigned nBits>
  41 Foam::PackedList<nBits>::PackedList(const UList<label>& lst)
  42 :
  43     StorageList(packedLength(lst.size()), 0u),
  44     size_(lst.size())
  45 {
  46     forAll(lst, i)
  47     {
  48         set(i, lst[i]);
  49     }
  50 }
  51
  52
  53 // * * * * * * * * * * * * * * * Member Functions  * * * * * * * * * * * * * //
  54
  55
  56 #if (UINT_MAX == 0xFFFFFFFF)
  57 // 32-bit counting, Hamming weight method
  58 #   define COUNT_PACKEDBITS(sum, x)                                           \
  59 {                                                                             \
  60     x -= (x >> 1) & 0x55555555;                                               \
  61     x = (x & 0x33333333) + ((x >> 2) & 0x33333333);                           \
  62     sum += (((x + (x >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;                \
  63 }
  64 #elif (UINT_MAX == 0xFFFFFFFFFFFFFFFF)
  65 // 64-bit counting, Hamming weight method
  66 #   define COUNT_PACKEDBITS(sum, x)                                           \
  67 {                                                                             \
  68     x -= (x >> 1) & 0x5555555555555555;                                       \
  69     x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);           \
  70     sum += (((x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F) * 0x0101010101010101) >> 56;\
  71 }
  72 #else
  73 // Arbitrary number of bits, Brian Kernighan's method
  74 #   define COUNT_PACKEDBITS(sum, x)    for (; x; ++sum) { x &= x - 1; }
  75 #endif
  76
  77
  78 template<unsigned nBits>
  79 unsigned int Foam::PackedList<nBits>::count() const
  80 {
  81     register unsigned int c = 0;
  82
  83     if (size_)
  84     {
  85         // mask value for complete segments
  86         unsigned int mask = maskLower(packing());
  87
  88         const unsigned int endSeg = size_ / packing();
  89         const unsigned int endOff = size_ % packing();
  90
  91         // count bits in complete segments
  92         for (unsigned i = 0; i < endSeg; ++i)
  93         {
  94             register unsigned int bits = StorageList::operator[](i) & mask;
  95             COUNT_PACKEDBITS(c, bits);
  96         }
  97
  98         // count bits in partial segment
  99         if (endOff)
 100         {
 101             mask = maskLower(endOff);
 102
 103             register unsigned int bits = StorageList::operator[](endSeg) & mask;
 104             COUNT_PACKEDBITS(c, bits);
 105         }
 106     }
 107
 108     return c;
 109 }
 110
 111
 112 template<unsigned nBits>
 113 bool Foam::PackedList<nBits>::trim()
 114 {
 115     if (!size_)
 116     {
 117         return false;
 118     }
 119
 120     // mask value for complete segments
 121     unsigned int mask = maskLower(packing());
 122
 123     label currElem = packedLength(size_) - 1;
 124     unsigned int endOff = size_ % packing();
 125
 126     // clear trailing bits on final segment
 127     if (endOff)
 128     {
 129         StorageList::operator[](currElem) &= maskLower(endOff);
 130     }
 131
 132     // test entire segment
 133     while (currElem > 0 && !(StorageList::operator[](currElem) &= mask))
 134     {
 135         currElem--;
 136     }
 137
 138     // test segment
 139     label newsize = (currElem + 1) * packing();
 140
 141     // mask for the final segment
 142     mask = max_value() << (nBits * (packing() - 1));
 143
 144     for (endOff = packing(); endOff >= 1; --endOff, --newsize)
 145     {
 146         if (StorageList::operator[](currElem) & mask)
 147         {
 148             break;
 149         }
 150
 151         mask >>= nBits;
 152     }
 153
 154     if (size_ == newsize)
 155     {
 156         return false;
 157     }
 158
 159     size_ = newsize;
 160     return false;
 161 }
 162
 163
 164 template<unsigned nBits>
 165 void Foam::PackedList<nBits>::flip()
 166 {
 167     label packLen = packedLength(size_);
 168
 169     for (label i=0; i < packLen; i++)
 170     {
 171         StorageList::operator[](i) = ~StorageList::operator[](i);
 172     }
 173 }
 174
 175
 176 template<unsigned nBits>
 177 Foam::labelList Foam::PackedList<nBits>::values() const
 178 {
 179     labelList elems(size_);
 180
 181     forAll(*this, i)
 182     {
 183         elems[i] = get(i);
 184     }
 185     return elems;
 186 }
 187
 188
 189 template<unsigned nBits>
 190 Foam::Ostream& Foam::PackedList<nBits>::iteratorBase::print(Ostream& os) const
 191 {
 192     os  << "iterator<"  << label(nBits) << "> ["
 193         << this->index_ << "]"
 194         << " segment:"  << label(this->index_ / packing())
 195         << " offset:"   << label(this->index_ % packing())
 196         << " value:"    << this->get()
 197         << nl;
 198
 199     return os;
 200 }
 201
 202
 203 template<unsigned nBits>
 204 Foam::Ostream& Foam::PackedList<nBits>::print(Ostream& os) const
 205 {
 206     const label packLen = packedLength(size_);
 207
 208     os  << "PackedList<" << nBits << ">"
 209         << " max_value:" << max_value()
 210         << " packing:"   << packing() << nl
 211         << " count: "     << count() << nl
 212         << " size/capacity: " << size_ << "/" << capacity() << nl
 213         << " storage/capacity: " << packLen << "/" << StorageList::size()
 214         << "\n(\n";
 215
 216     // mask value for complete segments
 217     unsigned int mask = maskLower(packing());
 218
 219     for (label i=0; i < packLen; i++)
 220     {
 221         const StorageType& rawBits = StorageList::operator[](i);
 222
 223         // the final segment may not be full, modify mask accordingly
 224         if (i+1 == packLen)
 225         {
 226             unsigned int endOff = size_ % packing();
 227
 228             if (endOff)
 229             {
 230                 mask = maskLower(endOff);
 231             }
 232             else
 233             {
 234                 continue;
 235             }
 236         }
 237
 238         for (unsigned int testBit = (1u << max_bits()); testBit; testBit >>= 1)
 239         {
 240             if (mask & testBit)
 241             {
 242                 if (rawBits & testBit)
 243                 {
 244                     os << '1';
 245                 }
 246                 else
 247                 {
 248                     os << '-';
 249                 }
 250             }
 251             else
 252             {
 253                 os << 'x';
 254             }
 255         }
 256         os << '\n';
 257     }
 258     os << ")\n";
 259
 260     return os;
 261 }
 262
 263
 264 // * * * * * * * * * * * * * * * Member Operators  * * * * * * * * * * * * * //
 265
 266 template<unsigned nBits>
 267 void Foam::PackedList<nBits>::operator=(const PackedList<nBits>& lst)
 268 {
 269     StorageList::operator=(lst);
 270     size_ = lst.size();
 271 }
 272
 273
 274 template<unsigned nBits>
 275 void Foam::PackedList<nBits>::operator=(const UList<label>& lst)
 276 {
 277     setCapacity(lst.size());
 278     size_ = lst.size();
 279
 280     forAll(lst, i)
 281     {
 282         set(i, lst[i]);
 283     }
 284 }
 285
 286
 287 // * * * * * * * * * * * * * * * Ostream Operator *  * * * * * * * * * * * * //
 288
 289 //template<unsigned nBits>
 290 //Foam::Ostream& ::Foam::operator<<(Ostream& os, const PackedList<nBits>& lst)
 291 //{
 292 //    os << lst();
 293 //    return os;
 294 //}
 295
 296
 297 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
 298
 299 // ************************************************************************* //