SHORE API
•All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
intpack.hpp
Go to the documentation of this file.
1 
2 /*
3  * Copyright 2008,2009,2010,2011,2012 Stephan Ossowski, Korbinian Schneeberger,
4  * Felix Ott, Joerg Hagmann, Alf Scotland, Sebastian Bender
5  *
6  * This file is part of SHORE.
7  *
8  * SHORE is free software: you can redistribute it and/or modify
9  * it under the terms of the GNU General Public License as published by
10  * the Free Software Foundation, either version 3 of the License, or
11  * (at your option) any later version.
12  *
13  * SHORE is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with SHORE. If not, see <http://www.gnu.org/licenses/>.
20  */
21 
25 
26 #ifndef SHORE_CONTAINER_INTPACK_HPP__
27 #define SHORE_CONTAINER_INTPACK_HPP__
28 
29 #include <algorithm>
30 #include <cstddef>
31 #include <iostream>
32 #include <iterator>
33 #include <limits>
34 #include <stdexcept>
35 #include <utility>
36 
37 #include <boost/iterator/iterator_facade.hpp>
38 #include <boost/utility/enable_if.hpp>
39 
40 #include "shore/base/memops.hpp"
41 #include "shore/base/stringops.hpp"
42 
43 namespace shore {
44 
45 struct refcore_base;
46 
48 class intpack
49 {
50  public:
51 
52  // \brief Lets the container grow by factor 2 on resize.
53  //static const size_t GROWTH_ATTENUATOR=0;
54 
56  static const size_t GROWTH_ATTENUATOR=1;
57 
59  typedef shore::uint64_t int_type;
60 
61 
62  class reference;
63  class const_reference;
64  class iterator;
65  class const_iterator;
66 
67  private:
68 
69 
71  char* m_data;
73  size_t m_bytecapacity;
74 
76  size_t m_size;
78  size_t m_bitsize;
80  size_t m_nbit;
81 
83  int_type m_mask;
84 
85 
87  static size_t significant_bits(int_type n);
88 
91  void reserve_bit(const size_t new_bitcapacity);
92 
96  static size_t nbyte(const size_t nbit,const bool exact=false);
97 
98  public:
99 
101  intpack(const size_t initialsize=0);
102 
104  intpack(const intpack &other);
105 
107  intpack &operator=(const intpack &other);
108 
110  ~intpack();
111 
113  void resize(const size_t new_size);
114 
116  void repack(size_t new_nbit=std::numeric_limits<size_t>::max());
117 
119  void repack_for(int_type v);
120 
123  void reserve(const size_t new_capacity);
124 
126  void clear();
127 
129  void push_back(const int_type n);
130 
132  void pop_back();
133 
135  template<typename Iter>
136  void append(Iter beg,Iter end)
137  {
138  typedef typename std::iterator_traits<Iter>::value_type value_type;
139  const size_t oldsize=m_size;
140  resize(m_size+(end-beg));
141  reference b(m_nbit,m_data,oldsize);
142 
143  for(Iter i=beg;i!=end;++i)
144  {
145  const value_type v=*i;
146  b=v;
147  b.to_next();
148  }
149  }
150 
152  reference operator[](const size_t idx);
153 
155  const_reference operator[](const size_t idx) const;
156 
158  reference front();
159 
161  const_reference front() const;
162 
164  reference back();
165 
167  const_reference back() const;
168 
170  size_t nbit() const;
171 
173  size_t size() const;
174 
176  bool empty() const;
177 
179  int_type max_value() const
180  {
181  return m_mask;
182  }
183 
185  const char* data_begin() const;
187  const char* data_end() const;
188 
190  void end_polish();
191 
193  iterator begin();
195  iterator end();
197  const_iterator begin() const;
199  const_iterator end() const;
200 
204  static const_iterator iter_at(const char*const data,
205  const size_t nbit,const size_t idx);
206 
208  class const_reference
209  {
210  private:
211 
212  friend class intpack;
213  friend class const_iterator;
214  friend class reference;
215 
216  const refcore_base* m_core;
217 
219  const char* m_data;
221  size_t m_ofs;
222 
223 
225  const_reference(
226  const size_t nbit,const char*const data,const size_t pos);
227 
229  void to_next();
231  void to_prev();
233  void move_by(const ptrdiff_t n);
234 
236  void clone(const const_reference& other);
237  void clone(const reference& other);
238 
239  public:
240 
242  const_reference(const const_reference& other);
244  const_reference(const reference& other);
245 
246 
248  operator int_type() const;
249  };
250 
252  class reference
253  {
254  private:
255 
256  friend class intpack;
257  friend class iterator;
258  friend class const_reference;
259 
260  const refcore_base* m_core;
261 
263  char* m_data;
265  size_t m_ofs;
266 
267 
269  reference(const size_t nbit,char*const data,const size_t pos);
270 
272  void to_next();
274  void to_prev();
276  void move_by(const ptrdiff_t n);
277 
279  void clone(const reference& other);
280 
281  public:
282 
284  reference(const reference& other);
285 
287  operator int_type() const;
288 
290  reference& operator=(int_type x);
291 
293  reference& operator=(const reference& x);
294  reference& operator=(const const_reference& x);
295 
296  reference& operator+=(const int_type x);
297  reference& operator-=(const int_type x);
298  reference& operator*=(const int_type x);
299  reference& operator/=(const int_type x);
300  reference& operator&=(const int_type x);
301  reference& operator|=(const int_type x);
302  reference& operator^=(const int_type x);
303  reference& operator++();
304  int_type operator++(int);
305  reference& operator--();
306  int_type operator--(int);
307  };
308 
310  class iterator
311  :public boost::iterator_facade<
312  iterator,int_type,boost::random_access_traversal_tag,reference>
313  {
314  private:
315 
316  friend class boost::iterator_core_access;
317  friend class intpack;
318  friend class const_iterator;
319 
320  reference m_ref;
321 
322 
323  iterator(const reference& ref);
324 
325  void increment();
326 
327  void decrement();
328 
329  void advance(difference_type n);
330 
331  difference_type distance_to(const iterator& other) const;
332 
333  bool equal(const iterator& other) const;
334 
335  reference dereference() const;
336 
337  public:
338 
339  iterator();
340 
341  iterator(const iterator& other);
342 
343  iterator& operator=(const iterator& other);
344 
345  reference operator[](difference_type n) const;
346  };
347 
349  class const_iterator
350  :public boost::iterator_facade<
351  const_iterator,int_type,boost::random_access_traversal_tag,const_reference>
352  {
353  private:
354 
355  friend class boost::iterator_core_access;
356  friend class intpack;
357  friend class iterator;
358 
359  intpack::const_reference m_ref;
360 
361 
362  const_iterator(const intpack::const_reference& ref);
363 
364  void increment();
365 
366  void decrement();
367 
368  void advance(difference_type n);
369 
370  difference_type distance_to(const const_iterator& other) const;
371 
372  bool equal(const const_iterator& other) const;
373 
374  const_reference dereference() const;
375 
376  public:
377 
378  const_iterator();
379 
380  const_iterator(const iterator& other);
381  const_iterator(const const_iterator& other);
382 
383  const_iterator& operator=(const const_iterator& other);
384 
385  const_reference operator[](difference_type n) const;
386  };
387 };
388 
390 struct refcore_base
391 {
392  typedef intpack::int_type int_type;
393  static const size_t MAX_NBIT=sizeof(int_type)<<3;
394  static const refcore_base*const CORES[MAX_NBIT+1];
395  static const shore::ptrkeeper CORECLEANER;
396 
397 
398  virtual void fwd(const char*& data,size_t& ofs,const size_t n) const=0;
399  virtual void rev(const char*& data,size_t& ofs,const size_t n) const=0;
400  virtual void inc(const char*& data,size_t& ofs) const=0;
401  virtual void dec(const char*& data,size_t& ofs) const=0;
402  virtual void fwd(char*& data,size_t& ofs,const size_t n) const=0;
403  virtual void rev(char*& data,size_t& ofs,const size_t n) const=0;
404  virtual void inc(char*& data,size_t& ofs) const=0;
405  virtual void dec(char*& data,size_t& ofs) const=0;
406  virtual int_type read(const char*const data,const size_t ofs) const=0;
407  virtual void write(char*const data,const size_t ofs,int_type v) const=0;
408 
409  virtual ptrdiff_t distance(
410  const char*const data1,const size_t ofs1,
411  const char*const data2,const size_t ofs2) const=0;
412 
413  virtual ~refcore_base() {}
414 };
415 
417 template<size_t NBIT>
418 struct refcore
419 :public refcore_base
420 {
421  enum { MAXVAL=~((~(int_type(0)))<<NBIT) };
422 
423  virtual void fwd(const char*& data,size_t& ofs,const size_t n) const
424  {
425  const size_t k=(n*NBIT)+ofs;
426  data+=(k>>3);
427  ofs=(k&7);
428  }
429 
430  virtual void rev(const char*& data,size_t& ofs,const size_t n) const
431  {
432  const size_t k=n*NBIT;
433  ofs+=8;
434  --data;
435  ofs-=(k&7);
436  data-=(k>>3);
437  data+=(ofs>>3);
438  ofs=(ofs&7);
439  }
440 
441  virtual void inc(const char*& data,size_t& ofs) const
442  {
443  ofs+=NBIT;
444  data+=(ofs>>3);
445  ofs&=7;
446  }
447 
448  virtual void dec(const char*& data,size_t& ofs) const
449  {
450  ofs+=(MAX_NBIT-NBIT);
451  data+=(ofs>>3);
452  data-=sizeof(int_type);
453  ofs&=7;
454  }
455 
456  virtual void fwd(char*& data,size_t& ofs,const size_t n) const
457  {
458  const size_t k=(n*NBIT)+ofs;
459  data+=(k>>3);
460  ofs=(k&7);
461  }
462 
463  virtual void rev(char*& data,size_t& ofs,const size_t n) const
464  {
465  const size_t k=n*NBIT;
466  ofs+=8;
467  --data;
468  ofs-=(k&7);
469  data-=(k>>3);
470  data+=(ofs>>3);
471  ofs=(ofs&7);
472  }
473 
474  virtual void inc(char*& data,size_t& ofs) const
475  {
476  ofs+=NBIT;
477  data+=(ofs>>3);
478  ofs&=7;
479  }
480 
481  virtual void dec(char*& data,size_t& ofs) const
482  {
483  ofs+=(MAX_NBIT-NBIT);
484  data+=(ofs>>3);
485  data-=sizeof(int_type);
486  ofs&=7;
487  }
488 
489  virtual int_type read(const char*const data,const size_t ofs) const
490  {
491  const size_t b=NBIT+ofs;
492 
493  if(b>MAX_NBIT)
494  {
495  int_type ret;
496  shore::bit_memcpy(&ret,data,NBIT,0,ofs);
497  ret=shore::ntoh64(&ret);
498  ret=(ret>>(MAX_NBIT-NBIT));
499 
500  return ret;
501  }
502 
503  return (shore::ntoh64(data)>>(MAX_NBIT-b))&MAXVAL;
504  }
505 
506  virtual void write(char*const data,const size_t ofs,int_type v) const
507  {
508  if(v!=(v&MAXVAL)) throw std::runtime_error(
509  "intpack: "+shore::to_string(v)+" does not fit into "
510  +shore::to_string(NBIT)+" bits");
511 
512  v=shore::hton64(&v);
513  const size_t xb=MAX_NBIT-NBIT;
514  const char*const bo=reinterpret_cast<const char*>(&v)+(xb>>3);
515 
516  shore::bit_memcpy(data,bo,NBIT,ofs,xb&7);
517  }
518 
519  virtual ptrdiff_t distance(
520  const char*const data1,const size_t ofs1,
521  const char*const data2,const size_t ofs2) const
522  {
523  const ptrdiff_t dist1=data2-data1;
524  const ptrdiff_t dist2=ptrdiff_t(ofs2)-ptrdiff_t(ofs1);
525  return ((dist1<<3)+dist2)/ptrdiff_t(NBIT);
526  }
527 };
528 
530 template<>
531 struct refcore<0>
532 :public refcore_base
533 {
534  virtual void fwd(const char*& data,size_t& ofs,const size_t n) const
535  {
536  ofs+=n;
537  }
538 
539  virtual void rev(const char*& data,size_t& ofs,const size_t n) const
540  {
541  ofs-=n;
542  }
543 
544  virtual void inc(const char*& data,size_t& ofs) const
545  {
546  ++ofs;
547  }
548 
549  virtual void dec(const char*& data,size_t& ofs) const
550  {
551  --ofs;
552  }
553 
554  virtual void fwd(char*& data,size_t& ofs,const size_t n) const
555  {
556  ofs+=n;
557  }
558 
559  virtual void rev(char*& data,size_t& ofs,const size_t n) const
560  {
561  ofs-=n;
562  }
563 
564  virtual void inc(char*& data,size_t& ofs) const
565  {
566  ++ofs;
567  }
568 
569  virtual void dec(char*& data,size_t& ofs) const
570  {
571  --ofs;
572  }
573 
574  virtual int_type read(const char*const data,const size_t ofs) const
575  {
576  return 0;
577  }
578 
579  virtual void write(char*const data,const size_t ofs,int_type v) const
580  {
581  if(v!=0) throw std::runtime_error("refcore<0> write");
582  }
583 
584  virtual ptrdiff_t distance(
585  const char*const data1,const size_t ofs1,
586  const char*const data2,const size_t ofs2) const
587  {
588  return ptrdiff_t(ofs2)-ptrdiff_t(ofs1);
589  }
590 };
591 
592 
593 template<>
594 inline refcore<1>::int_type refcore<1>::read(
595  const char*const data,const size_t ofs) const
596 {
597  const int_type ret=static_cast<shore::uint8_t>(*data);
598  return ((ret>>(7-ofs))&1);
599 }
600 
601 template<>
602 inline void refcore<1>::write(char*const data,const size_t ofs,int_type v) const
603 {
604  if(v>1) throw std::runtime_error("refcore<1> write");
605 
606  const shore::uint8_t sh=7-ofs;
607  (*data)&=(~shore::uint8_t(1<<sh));
608  (*data)|=(v<<sh);
609 }
610 
611 template<>
612 inline ptrdiff_t refcore<1>::distance(
613  const char*const data1,const size_t ofs1,
614  const char*const data2,const size_t ofs2) const
615 {
616  return ((data2-data1)<<3)+(ptrdiff_t(ofs2)-ptrdiff_t(ofs1));
617 }
618 
619 
620 
621 template<>
622 inline refcore<2>::int_type refcore<2>::read(
623  const char*const data,const size_t ofs) const
624 {
625  const int_type ret=static_cast<shore::uint8_t>(*data);
626  return ((ret>>(6-ofs))&3);
627 }
628 
629 template<>
630 inline void refcore<2>::write(char*const data,const size_t ofs,int_type v) const
631 {
632  if(v>3) throw std::runtime_error("refcore<2> write");
633 
634  const shore::uint8_t sh=(6-ofs);
635  (*data)&=(~shore::uint8_t(3<<sh));
636  (*data)|=(v<<sh);
637 }
638 
639 template<>
640 inline ptrdiff_t refcore<2>::distance(
641  const char*const data1,const size_t ofs1,
642  const char*const data2,const size_t ofs2) const
643 {
644  return ((data2-data1)<<2)+((ptrdiff_t(ofs2)-ptrdiff_t(ofs1))>>1);
645 }
646 
647 
648 
650 template<>
651 struct refcore<3>
652 :public refcore_base
653 {
654  virtual void fwd(const char*& data,size_t& ofs,const size_t n) const
655  {
656  const size_t k=(n<<1)+n+ofs;
657  data+=(k>>3);
658  ofs=(k&7);
659  }
660 
661  virtual void rev(const char*& data,size_t& ofs,const size_t n) const
662  {
663  const size_t k=(n<<1)+n;
664  ofs+=8;
665  --data;
666  ofs-=(k&7);
667  data-=(k>>3);
668  data+=(ofs>>3);
669  ofs=(ofs&7);
670  }
671 
672  virtual void inc(const char*& data,size_t& ofs) const
673  {
674  ofs+=3;
675  data+=(ofs>>3);
676  ofs&=7;
677  }
678 
679  virtual void dec(const char*& data,size_t& ofs) const
680  {
681  ofs+=5;
682  data+=(ofs>>3);
683  --data;
684  ofs&=7;
685  }
686 
687  virtual void fwd(char*& data,size_t& ofs,const size_t n) const
688  {
689  const size_t k=(n<<1)+n+ofs;
690  data+=(k>>3);
691  ofs=(k&7);
692  }
693 
694  virtual void rev(char*& data,size_t& ofs,const size_t n) const
695  {
696  const size_t k=(n<<1)+n;
697  ofs+=8;
698  --data;
699  ofs-=(k&7);
700  data-=(k>>3);
701  data+=(ofs>>3);
702  ofs=(ofs&7);
703  }
704 
705  virtual void inc(char*& data,size_t& ofs) const
706  {
707  ofs+=3;
708  data+=(ofs>>3);
709  ofs&=7;
710  }
711 
712  virtual void dec(char*& data,size_t& ofs) const
713  {
714  ofs+=5;
715  data+=(ofs>>3);
716  --data;
717  ofs&=7;
718  }
719 
720  virtual int_type read(const char*const data,const size_t ofs) const
721  {
722  if(ofs>5)
723  {
724  const int_type ret1=static_cast<shore::uint8_t>(*data)<<(ofs-5);
725  const int_type ret2=static_cast<shore::uint8_t>(*(data+1))>>(13-ofs);
726  return (ret1|ret2)&7;
727  }
728 
729  const int_type ret=static_cast<shore::uint8_t>(*data);
730  return ((ret>>(5-ofs))&7);
731  }
732 
733  virtual void write(char*const data,const size_t ofs,int_type v) const
734  {
735  if(ofs>5)
736  {
737  const shore::uint8_t sh1=(ofs-5);
738  const shore::uint8_t sh2=(13-ofs);
739  (*data)&=(~shore::uint8_t(7>>sh1));
740  (*data)|=(v>>sh1);
741  (*(data+1))&=(~shore::uint8_t(7<<sh2));
742  (*(data+1))|=(v<<sh2);
743  }
744  else
745  {
746  const shore::uint8_t sh=(5-ofs);
747  (*data)&=(~shore::uint8_t(7<<sh));
748  (*data)|=(v<<sh);
749  }
750  }
751 
752  virtual ptrdiff_t distance(
753  const char*const data1,const size_t ofs1,
754  const char*const data2,const size_t ofs2) const
755  {
756  const ptrdiff_t dist1=data2-data1;
757  const ptrdiff_t dist2=ptrdiff_t(ofs2)-ptrdiff_t(ofs1);
758  return ((dist1<<3)+dist2)/3;
759  }
760 };
761 
762 
764 template<>
765 inline refcore<4>::int_type refcore<4>::read(
766  const char*const data,const size_t ofs) const
767 {
768  const int_type ret=static_cast<shore::uint8_t>(*data);
769  if(ofs>0) return ret&15;
770  else return ret>>4;
771 }
772 
773 template<>
774 inline void refcore<4>::write(char*const data,const size_t ofs,int_type v) const
775 {
776  if(v>15) throw std::runtime_error("refcore<4> write");
777 
778  const shore::uint8_t cv=v;
779  if(ofs==0) (*data)=((*data)&15)|(cv<<4);
780  else (*data)=(((*data)&(15<<4))|cv);
781 }
782 
783 template<>
784 inline ptrdiff_t refcore<4>::distance(
785  const char*const data1,const size_t ofs1,
786  const char*const data2,const size_t ofs2) const
787 {
788  return ((data2-data1)<<1)+((ptrdiff_t(ofs2)-ptrdiff_t(ofs1))>>2);
789 }
790 
792 template<>
793 struct refcore<8>
794 :public refcore_base
795 {
796  virtual void fwd(const char*& data,size_t& ofs,const size_t n) const
797  {
798  data+=n;
799  }
800 
801  virtual void rev(const char*& data,size_t& ofs,const size_t n) const
802  {
803  data-=n;
804  }
805 
806  virtual void inc(const char*& data,size_t& ofs) const
807  {
808  ++data;
809  }
810 
811  virtual void dec(const char*& data,size_t& ofs) const
812  {
813  --data;
814  }
815 
816  virtual void fwd(char*& data,size_t& ofs,const size_t n) const
817  {
818  data+=n;
819  }
820 
821  virtual void rev(char*& data,size_t& ofs,const size_t n) const
822  {
823  data-=n;
824  }
825 
826  virtual void inc(char*& data,size_t& ofs) const
827  {
828  ++data;
829  }
830 
831  virtual void dec(char*& data,size_t& ofs) const
832  {
833  --data;
834  }
835 
836  virtual int_type read(const char*const data,const size_t ofs) const
837  {
838  return static_cast<shore::uint8_t>(*data);
839  }
840 
841  virtual void write(char*const data,const size_t ofs,int_type v) const
842  {
843  if(v>255) throw std::runtime_error("refcore<8> write");
844  (*data)=v;
845  }
846 
847  virtual ptrdiff_t distance(
848  const char*const data1,const size_t ofs1,
849  const char*const data2,const size_t ofs2) const
850  {
851  return (data2-data1);
852  }
853 };
854 
856 template<>
857 struct refcore<64>
858 :public refcore_base
859 {
860  virtual void fwd(const char*& data,size_t& ofs,const size_t n) const
861  {
862  data+=(n<<3);
863  }
864 
865  virtual void rev(const char*& data,size_t& ofs,const size_t n) const
866  {
867  data-=(n<<3);
868  }
869 
870  virtual void inc(const char*& data,size_t& ofs) const
871  {
872  data+=8;
873  }
874 
875  virtual void dec(const char*& data,size_t& ofs) const
876  {
877  data-=8;
878  }
879 
880  virtual void fwd(char*& data,size_t& ofs,const size_t n) const
881  {
882  data+=(n<<3);
883  }
884 
885  virtual void rev(char*& data,size_t& ofs,const size_t n) const
886  {
887  data-=(n<<3);
888  }
889 
890  virtual void inc(char*& data,size_t& ofs) const
891  {
892  data+=8;
893  }
894 
895  virtual void dec(char*& data,size_t& ofs) const
896  {
897  data-=8;
898  }
899 
900  virtual int_type read(const char*const data,const size_t ofs) const
901  {
902  return shore::ntoh64(data);
903  }
904 
905  virtual void write(char*const data,const size_t ofs,int_type v) const
906  {
907  v=shore::hton64(&v);
908  const char*const ptr=reinterpret_cast<const char*>(&v);
909  data[0]=ptr[0];
910  data[1]=ptr[1];
911  data[2]=ptr[2];
912  data[3]=ptr[3];
913  data[4]=ptr[4];
914  data[5]=ptr[5];
915  data[6]=ptr[6];
916  data[7]=ptr[7];
917  }
918 
919  virtual ptrdiff_t distance(
920  const char*const data1,const size_t ofs1,
921  const char*const data2,const size_t ofs2) const
922  {
923  return (data2-data1)>>3;
924  }
925 };
926 
927 } // namespace
928 
929 namespace std {
930 
932 template<>
933 inline void swap<shore::intpack::reference>(shore::intpack::reference & a,shore::intpack::reference & b)
934 {
935  const shore::intpack::int_type tmp=a;
936  a=b;
937  b=tmp;
938 }
939 
940 } // namespace std
941 
942 #endif // SHORE_CONTAINER_INTPACK_HPP__
943