PackedList.C
Go to the documentation of this file.
1 /*---------------------------------------------------------------------------*\
2  ========= |
3  \\ / F ield | OpenFOAM: The Open Source CFD Toolbox
4  \\ / O peration | Website: https://openfoam.org
5  \\ / A nd | Copyright (C) 2011-2019 OpenFOAM Foundation
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 #include "IOstreams.H"
28 
29 
30 // * * * * * * * * * * * * * * * Member Functions * * * * * * * * * * * * * //
31 
32 #if (UINT_MAX == 0xFFFFFFFF)
33 // 32-bit counting, Hamming weight method
34 #define COUNT_PACKEDBITS(sum, x) \
35 { \
36  x -= (x >> 1) & 0x55555555; \
37  x = (x & 0x33333333) + ((x >> 2) & 0x33333333); \
38  sum += (((x + (x >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; \
39 }
40 #elif (UINT_MAX == 0xFFFFFFFFFFFFFFFF)
41 // 64-bit counting, Hamming weight method
42 #define COUNT_PACKEDBITS(sum, x) \
43 { \
44  x -= (x >> 1) & 0x5555555555555555; \
45  x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333); \
46  sum += (((x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F) * 0x0101010101010101) >> 56;\
47 }
48 #else
49 // Arbitrary number of bits, Brian Kernighan's method
50  #define COUNT_PACKEDBITS(sum, x) for (; x; ++sum) { x &= x - 1; }
51 #endif
52 
53 
54 template<unsigned nBits>
55 unsigned int Foam::PackedList<nBits>::count() const
56 {
57  unsigned int c = 0;
58 
59  if (size_)
60  {
61  const label packLen = packedLength();
62  for (label i = 0; i < packLen; ++i)
63  {
64  unsigned int bits = StorageList::operator[](i);
65  COUNT_PACKEDBITS(c, bits);
66  }
67  }
68 
69  return c;
70 }
71 
72 
73 template<unsigned nBits>
75 {
76  if (!size_)
77  {
78  return false;
79  }
80 
81  const label oldSize = size_;
82  for (label storeI = packedLength()-1; storeI >= 0; --storeI)
83  {
84  size_ = storeI * packing();
85  unsigned int bits = StorageList::operator[](storeI);
86 
87  // found some bits
88  if (bits)
89  {
90  while (bits)
91  {
92  bits >>= nBits;
93  ++size_;
94  }
95  break;
96  }
97  }
98 
99  return (size_ != oldSize);
100 }
101 
102 
103 template<unsigned nBits>
105 {
106  if (!size_)
107  {
108  return;
109  }
110 
111  // mask value for complete segments
112  const unsigned int mask = maskLower(packing());
113 
114  const label packLen = packedLength();
115  for (label i=0; i < packLen; ++i)
116  {
117  StorageList::operator[](i) = mask & ~StorageList::operator[](i);
118  }
119 
120  // mask off the final partial segment
121  {
122  const unsigned int off = size_ % packing();
123  if (off)
124  {
125  const unsigned int seg = size_ / packing();
126 
127  StorageList::operator[](seg) &= maskLower(off);
128  }
129  }
130 }
131 
132 
133 template<unsigned nBits>
135 {
136  labelList elems(size_);
137 
138  forAll(*this, i)
139  {
140  elems[i] = get(i);
141  }
142 
143  return elems;
144 }
145 
146 
147 template<unsigned nBits>
149 (
150  Ostream& os
151 ) const
152 {
153  os << "iterator<" << label(nBits) << "> ["
154  << this->index_ << "]"
155  << " segment:" << label(this->index_ / packing())
156  << " offset:" << label(this->index_ % packing())
157  << " value:" << this->get()
158  << nl;
159 
160  return os;
161 }
162 
163 
164 template<unsigned nBits>
166 (
167  Ostream& os,
168  const bool fullOutput
169 ) const
170 {
171  const label packLen = packedLength();
172 
173  // mask value for complete segments
174  unsigned int mask = maskLower(packing());
175  const label outputLen = fullOutput ? StorageList::size() : packLen;
176 
177  os << "(\n";
178  for (label i=0; i < outputLen; ++i)
179  {
180  const StorageType& rawBits = StorageList::operator[](i);
181 
182  // the final segment may not be full, modify mask accordingly
183  if (i == packLen-1)
184  {
185  const unsigned int off = size_ % packing();
186 
187  if (off)
188  {
189  mask = maskLower(off);
190  }
191  }
192  else if (i == packLen)
193  {
194  // no mask for unaddressed bit
195  mask = 0u;
196  }
197 
198 
199  for (unsigned int testBit = (1u << max_bits()); testBit; testBit >>= 1)
200  {
201  if (mask & testBit)
202  {
203  // addressable region
204  if (rawBits & testBit)
205  {
206  os << '1';
207  }
208  else
209  {
210  os << '-';
211  }
212  }
213  else
214  {
215  if (rawBits & testBit)
216  {
217  os << '!';
218  }
219  else
220  {
221  os << '.';
222  }
223  }
224  }
225  os << '\n';
226  }
227  os << ")\n";
228 
229  return os;
230 }
231 
232 
233 template<unsigned nBits>
235 (
236  Ostream& os,
237  const bool fullOutput
238 ) const
239 {
240  os << "PackedList<" << nBits << ">"
241  << " max_value:" << max_value()
242  << " packing:" << packing() << nl
243  << " count: " << count() << nl
244  << " size/capacity: " << size_ << "/" << capacity() << nl
245  << " storage/capacity: "
246  << packedLength() << "/" << StorageList::size()
247  << "\n";
248 
249  return printBits(os, fullOutput);
250 }
251 
252 
253 template<unsigned nBits>
255 {
256  PackedList<nBits>& lst = *this;
257 
258  lst.clear();
259  is.fatalCheck("PackedList<nBits>::read(Istream&)");
260 
261  token firstTok(is);
262  is.fatalCheck
263  (
264  "PackedList<nBits>::read(Istream&) : "
265  "reading first token"
266  );
267 
268  if (firstTok.isLabel())
269  {
270  const label sz = firstTok.labelToken();
271 
272  // Set list length to that read
273  lst.resize(sz);
274 
275  // Read list contents depending on data format
276  if (is.format() == IOstream::ASCII)
277  {
278  // Read beginning of contents
279  const char delimiter = is.readBeginList("PackedList<nBits>");
280 
281  if (sz)
282  {
283  if (delimiter == token::BEGIN_LIST)
284  {
285  for (label i=0; i<sz; ++i)
286  {
287  lst[i] = lst.readValue(is);
288 
289  is.fatalCheck
290  (
291  "PackedList<nBits>::read(Istream&) : "
292  "reading entry"
293  );
294  }
295  }
296  else if (delimiter == token::BEGIN_BLOCK)
297  {
298  // assign for all entries
299  lst = lst.readValue(is);
300 
301  is.fatalCheck
302  (
303  "PackedList<nBits>::read(Istream&) : "
304  "reading the single entry"
305  );
306  }
307  else
308  {
310  << "incorrect list token, expected '(' or '{', found "
311  << firstTok.info()
313  }
314  }
315 
316  // Read end of contents
317  is.readEndList("PackedList<nBits>");
318  }
319  else
320  {
321  if (sz)
322  {
323  is.read
324  (
325  reinterpret_cast<char*>(lst.storage().data()),
326  lst.byteSize()
327  );
328 
329  is.fatalCheck
330  (
331  "PackedList<nBits>::read(Istream&) : "
332  "reading the binary block"
333  );
334  }
335  }
336  }
337  else if (firstTok.isPunctuation())
338  {
339  if (firstTok.pToken() == token::BEGIN_LIST)
340  {
341  token nextTok(is);
342  is.fatalCheck("PackedList<nBits>::read(Istream&)");
343 
344  while
345  (
346  !( nextTok.isPunctuation()
347  && nextTok.pToken() == token::END_LIST
348  )
349  )
350  {
351  is.putBack(nextTok);
352  lst.append(lst.readValue(is));
353 
354  is >> nextTok;
355  is.fatalCheck("PackedList<nBits>::read(Istream&)");
356  }
357  }
358  else if (firstTok.pToken() == token::BEGIN_BLOCK)
359  {
360  token nextTok(is);
361  is.fatalCheck("PackedList<nBits>::read(Istream&)");
362 
363  while
364  (
365  !( nextTok.isPunctuation()
366  && nextTok.pToken() == token::END_BLOCK
367  )
368  )
369  {
370  is.putBack(nextTok);
371  lst.setPair(is);
372 
373  is >> nextTok;
374  is.fatalCheck("PackedList<nBits>::read(Istream&)");
375  }
376  }
377  else
378  {
380  << "incorrect first token, expected '(', found "
381  << firstTok.info()
382  << exit(FatalIOError);
383  }
384  }
385  else
386  {
388  << "incorrect first token, expected <int>, '(' or '{', found "
389  << firstTok.info()
390  << exit(FatalIOError);
391  }
392 
393  return is;
394 }
395 
396 
397 template<unsigned nBits>
399 (
400  Ostream& os,
401  const bool indexedOutput
402 ) const
403 {
404  const PackedList<nBits>& lst = *this;
405  const label sz = lst.size();
406 
407  // Write list contents depending on data format
408  if (os.format() == IOstream::ASCII)
409  {
410  bool uniform = false;
411 
412  if (sz > 1 && !indexedOutput)
413  {
414  uniform = true;
415 
416  forAll(lst, i)
417  {
418  if (lst[i] != lst[0])
419  {
420  uniform = false;
421  break;
422  }
423  }
424  }
425 
426  if (uniform)
427  {
428  // uniform values:
429  os << sz << token::BEGIN_BLOCK << lst[0] << token::END_BLOCK;
430  }
431  else if (indexedOutput)
432  {
433  // indexed output
434  os << nl << token::BEGIN_BLOCK << nl;
435 
436  for
437  (
438  typename PackedList<nBits>::const_iterator iter = lst.cbegin();
439  iter != lst.cend();
440  ++iter
441  )
442  {
443  if (iter.writeIfSet(os))
444  {
445  os << nl;
446  }
447  }
448 
449  os << token::END_BLOCK << nl;
450  }
451  else if (sz < 11)
452  {
453  // short list:
454  os << sz << token::BEGIN_LIST;
455  forAll(lst, i)
456  {
457  if (i)
458  {
459  os << token::SPACE;
460  }
461  os << lst[i];
462  }
463  os << token::END_LIST;
464  }
465  else
466  {
467  // longer list:
468  os << nl << sz << nl << token::BEGIN_LIST;
469  forAll(lst, i)
470  {
471  os << nl << lst[i];
472  }
473  os << nl << token::END_LIST << nl;
474  }
475  }
476  else
477  {
478  os << nl << sz << nl;
479  if (sz)
480  {
481  os.write
482  (
483  reinterpret_cast<const char*>(lst.storage().cdata()),
484  lst.byteSize()
485  );
486  }
487  }
488 
489  return os;
490 }
491 
492 
493 // * * * * * * * * * * * * * * * Member Operators * * * * * * * * * * * * * //
494 
495 template<unsigned nBits>
497 {
499  size_ = lst.size();
500 }
501 
502 
503 template<unsigned nBits>
505 {
506  transfer(lst);
507 }
508 
509 
510 template<unsigned nBits>
512 {
513  setCapacity(lst.size());
514  size_ = lst.size();
515 
516  forAll(lst, i)
517  {
518  set(i, lst[i]);
519  }
520 }
521 
522 
523 template<unsigned nBits>
525 {
526  setCapacity(lst.size());
527  size_ = lst.size();
528 
529  forAll(lst, i)
530  {
531  set(i, lst[i]);
532  }
533 }
534 
535 
536 // * * * * * * * * * * * * * * * IOstream Functions * * * * * * * * * * * * //
537 
538 template<unsigned nBits>
540 {
541  os << l;
542 }
543 
544 
545 // * * * * * * * * * * * * * * Friend Operators * * * * * * * * * * * * * * //
546 
547 template<unsigned nBits>
548 Foam::Istream& Foam::operator>>(Istream& is, PackedList<nBits>& lst)
549 {
550  return lst.read(is);
551 }
552 
553 
554 template<unsigned nBits>
555 Foam::Ostream& Foam::operator<<(Ostream& os, const PackedList<nBits>& lst)
556 {
557  return lst.write(os, false);
558 }
559 
560 
561 // ************************************************************************* //
Useful combination of include files which define Sin, Sout and Serr and the use of IO streams general...
#define COUNT_PACKEDBITS(sum, x)
Definition: PackedList.C:50
#define forAll(list, i)
Loop across all elements in list.
Definition: UList.H:434
streamFormat format() const
Return current stream format.
Definition: IOstream.H:374
void fatalCheck(const char *operation) const
Check IOstream status for given operation.
Definition: IOstream.C:105
An Istream is an abstract base class for all input systems (streams, files, token lists etc)....
Definition: Istream.H:60
char readEndList(const char *funcName)
Definition: Istream.C:148
virtual Istream & read(token &)=0
Return next token from stream.
char readBeginList(const char *funcName)
Definition: Istream.C:127
void putBack(const token &)
Put back token.
Definition: Istream.C:30
A 1D array of objects of type <T>, where the size of the vector is known and used for subscript bound...
Definition: List.H:91
label size() const
Return the number of elements in the UList.
Definition: ListI.H:171
void operator=(const UList< T > &)
Assignment to UList operator. Takes linear time.
Definition: List.C:376
An Ostream is an abstract base class for all output systems (streams, files, token lists,...
Definition: Ostream.H:57
virtual Ostream & write(const char)=0
Write character.
The const_iterator for PackedList.
Definition: PackedList.H:563
Ostream & printInfo(Ostream &) const
Print information and values.
Definition: PackedList.C:149
label index_
Element index.
Definition: PackedList.H:430
unsigned int get() const
Get value as unsigned, no range-checking.
Definition: PackedListI.H:290
A dynamically allocatable list of packed unsigned integers.
Definition: PackedList.H:153
static unsigned int max_value()
The max. value for an entry, which simultaneously the bit-mask.
Definition: PackedListI.H:38
void flip()
Invert the bits in the addressable region.
Definition: PackedList.C:104
List< unsigned int > & storage()
Return the underlying packed storage.
Definition: PackedListI.H:916
bool set(const label, const unsigned int val=~0u)
Set value at index I. Return true if value changed.
Definition: PackedListI.H:985
static unsigned int maskLower(unsigned offset)
Masking for all bits below the offset.
Definition: PackedListI.H:52
Istream & read(Istream &)
Clear list and read from stream.
Definition: PackedList.C:254
void resize(const label, const unsigned int &val=0u)
Reset addressable list size, does not shrink the allocated size.
Definition: PackedListI.H:726
void setCapacity(const label)
Alter the size of the underlying storage.
Definition: PackedListI.H:838
labelList values() const
Return the values as a list of labels.
Definition: PackedList.C:134
label size() const
Number of entries.
Definition: PackedListI.H:711
void transfer(PackedList< nBits > &)
Transfer the contents of the argument list into this list.
Definition: PackedListI.H:944
label capacity() const
The number of elements that can be stored before reallocating.
Definition: PackedListI.H:831
bool trim()
Trim any trailing zero elements.
Definition: PackedList.C:74
label packedLength() const
The list length when packed.
Definition: PackedListI.H:930
void setPair(Istream &)
Read an index/value pair and set accordingly.
Definition: PackedListI.H:120
static unsigned int packing()
The number of entries per packed storage element.
Definition: PackedListI.H:45
const_iterator cend() const
const_iterator set to beyond the end of the PackedList
Definition: PackedListI.H:702
static unsigned int max_bits()
The max. number of bits that can be templated.
Definition: PackedListI.H:31
const_iterator cbegin() const
const_iterator set to the beginning of the PackedList
Definition: PackedListI.H:678
void operator=(const unsigned int val)
Assignment of all entries to the given value. Takes linear time.
Definition: PackedListI.H:1059
std::streamsize byteSize() const
Return the binary size in number of characters.
Definition: PackedListI.H:937
static unsigned int readValue(Istream &)
Read a list entry (allows for specialisation)
Definition: PackedListI.H:103
PackedList< nBits > & append(const unsigned int val)
Append a value at the end of the list.
Definition: PackedListI.H:1022
void clear()
Clear the list, i.e. set addressable size to zero.
Definition: PackedListI.H:889
unsigned int count() const
Count number of bits set, O(log(n))
Definition: PackedList.C:55
Ostream & printInfo(Ostream &, const bool fullOutput=false) const
Print information and bit patterns (with printBits)
Definition: PackedList.C:235
Ostream & printBits(Ostream &, const bool fullOutput=false) const
Print bit patterns, optionally output unused elements.
Definition: PackedList.C:166
Ostream & write(Ostream &, const bool indexedOutput=false) const
Write, optionally with indexedOutput.
Definition: PackedList.C:399
unsigned int StorageType
Definition: PackedList.H:156
A List with indirect addressing.
Definition: UIndirectList.H:60
label size() const
Return the number of elements in the list.
label size() const
Return the number of elements in the UList.
Definition: UListI.H:311
T & operator[](const label)
Return element of UList.
Definition: UListI.H:167
const T * cdata() const
Return a const pointer to the first data element,.
Definition: UListI.H:142
T * data()
Return a pointer to the first data element,.
Definition: UListI.H:149
A token holds items read from Istream.
Definition: token.H:73
bool isLabel() const
Definition: tokenI.H:392
bool isPunctuation() const
Definition: tokenI.H:243
@ BEGIN_BLOCK
Definition: token.H:110
@ END_BLOCK
Definition: token.H:111
@ BEGIN_LIST
Definition: token.H:106
@ END_LIST
Definition: token.H:107
punctuationToken pToken() const
Definition: tokenI.H:248
label labelToken() const
Definition: tokenI.H:397
InfoProxy< token > info() const
Return info proxy.
Definition: token.H:391
#define FatalIOErrorInFunction(ios)
Report an error message using Foam::FatalIOError.
Definition: error.H:318
const dimensionedScalar c
Speed of light in a vacuum.
errorManipArg< error, int > exit(error &err, const int errNo=1)
Definition: errorManip.H:124
intWM_LABEL_SIZE_t label
A label is an int32_t or int64_t as specified by the pre-processor macro WM_LABEL_SIZE.
Definition: label.H:59
void writeEntry(Ostream &os, const HashTable< T, Key, Hash > &ht)
Definition: HashTableIO.C:96
Istream & operator>>(Istream &, directionInfo &)
IOerror FatalIOError
Ostream & operator<<(Ostream &, const ensightPart &)
static const char nl
Definition: Ostream.H:260