FreeFOAM The Cross-Platform CFD Toolkit
PackedListI.H
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 
27 #include <OpenFOAM/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>
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>
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>
90 :
91  StorageList(lst),
92  size_(lst.size_)
93 {}
94 
95 
96 template<unsigned nBits>
98 {
99  transfer(lst());
100 }
101 
102 
103 template<unsigned nBits>
106 {
107  return autoPtr<PackedList<nBits> >(new PackedList<nBits>(*this));
108 }
109 
110 
111 // * * * * * * * * * * * * * * * * Iterators * * * * * * * * * * * * * * * * //
112 
113 // iteratorBase
114 
115 template<unsigned nBits>
117 :
118  list_(0),
119  index_(0)
120 {}
121 
122 
123 template<unsigned nBits>
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
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
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>
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
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
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>
238 :
239  iteratorBase()
240 {}
241 
242 
243 template<unsigned nBits>
245 :
246  iteratorBase()
247 {}
248 
249 
250 template<unsigned nBits>
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>
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>
286 (
287  const PackedList<nBits>* lst,
288  const label i
289 )
290 :
291  iteratorBase(lst, i)
292 {}
293 
294 
295 template<unsigned nBits>
297 (
298  const PackedList<nBits>* lst,
299  const label i
300 )
301 :
302  iteratorBase(lst, i)
303 {}
304 
305 
306 template<unsigned nBits>
308 (
309  const iterator& iter
310 )
311 :
312  iteratorBase(static_cast<const iteratorBase&>(iter))
313 {}
314 
315 
316 template<unsigned nBits>
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>
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&
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>
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&
397 {
398  ++this->index_;
399  return *this;
400 }
401 
402 
403 template<unsigned nBits>
406 {
407  ++this->index_;
408  return *this;
409 }
410 
411 
412 template<unsigned nBits>
413 inline typename Foam::PackedList<nBits>::iterator
415 {
416  iterator old = *this;
417  ++this->index_;
418  return old;
419 }
420 
421 
422 template<unsigned nBits>
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&
435 {
436  --this->index_;
437  return *this;
438 }
439 
440 
441 template<unsigned nBits>
444 {
445  --this->index_;
446  return *this;
447 }
448 
449 
450 template<unsigned nBits>
451 inline typename Foam::PackedList<nBits>::iterator
453 {
454  iterator old = *this;
455  --this->index_;
456  return old;
457 }
458 
459 
460 template<unsigned nBits>
463 {
464  const_iterator old = *this;
465  --this->index_;
466  return old;
467 }
468 
469 
470 template<unsigned nBits>
473 {
474  return static_cast<iteratorBase&>(*this);
475 }
476 
477 
478 template<unsigned nBits>
481 {
482  return static_cast<iteratorBase&>(*this);
483 }
484 
485 
486 template<unsigned nBits>
487 inline unsigned int
489 {
490  return this->get();
491 }
492 
493 
494 template<unsigned nBits>
495 inline unsigned int
497 {
498  return this->get();
499 }
500 
501 
502 template<unsigned nBits>
503 inline typename Foam::PackedList<nBits>::iterator
505 {
506  return iterator(this, 0);
507 }
508 
509 
510 template<unsigned nBits>
513 {
514  return const_iterator(this, 0);
515 }
516 
517 
518 template<unsigned nBits>
521 {
522  return const_iterator(this, 0);
523 }
524 
525 
526 template<unsigned nBits>
527 inline typename Foam::PackedList<nBits>::iterator
529 {
530  return iterator(this, size_);
531 }
532 
533 
534 template<unsigned nBits>
537 {
538  return const_iterator(this, size_);
539 }
540 
541 
542 template<unsigned nBits>
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>
561 {
562  return !size_;
563 }
564 
565 
566 template<unsigned nBits>
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>
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>
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
674  (
675  max
676  (
677  len,
679  ),
680  0u
681  );
682  }
683 }
684 
685 
686 template<unsigned nBits>
688 {
689  size_ = 0;
690 }
691 
692 
693 template<unsigned nBits>
695 {
697  size_ = 0;
698 }
699 
700 
701 template<unsigned nBits>
703 {
704  label len = packedLength(size_);
705 
706  // we have unused space?
707  if (len < StorageList::size())
708  {
710  }
711 }
712 
713 template<unsigned nBits>
716 {
717  return static_cast<StorageList&>(*this);
718 }
719 
720 
721 template<unsigned nBits>
722 inline const Foam::List<unsigned int>&
724 {
725  return static_cast<const StorageList&>(*this);
726 }
727 
728 
729 template<unsigned nBits>
731 {
732  size_ = lst.size_;
733  lst.size_ = 0;
734 
736 }
737 
738 
739 template<unsigned nBits>
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>
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  {
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>
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  {
872  }
873  else
874  {
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 
902  }
903  else
904  {
906  }
907 }
908 
909 
910 // ************************ vim: set sw=4 sts=4 et: ************************ //