FreeFOAM The Cross-Platform CFD Toolkit
PackedList.C
Go to the documentation of this file.
1 /*---------------------------------------------------------------------------*\
2  ========= |
3  \\ / F ield | OpenFOAM: The Open Source CFD Toolbox
4  \\ / O peration |
5  \\ / A nd | Copyright (C) 1991-2010 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 "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>
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>
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>
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>
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>
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>
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>
268 {
269  StorageList::operator=(lst);
270  size_ = lst.size();
271 }
272 
273 
274 template<unsigned nBits>
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 // ************************ vim: set sw=4 sts=4 et: ************************ //