src/OpenFOAM/containers/Lists/PackedList/PackedList.C

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