ceph/src/boost/libs/icl/example/large_bitset_/large_bitset.hpp

   1 /*-----------------------------------------------------------------------------+
   2 Author: Joachim Faulhaber
   3 Copyright (c) 2009-2009: Joachim Faulhaber
   4 +------------------------------------------------------------------------------+
   5    Distributed under the Boost Software License, Version 1.0.
   6       (See accompanying file LICENCE.txt or copy at
   7            http://www.boost.org/LICENSE_1_0.txt)
   8 +-----------------------------------------------------------------------------*/
   9 #ifndef BOOST_LIBS_ICL_EXAMPLE_LARGE_BITSET__LARGE_BITSET_HPP_JOFA_091019
  10 #define BOOST_LIBS_ICL_EXAMPLE_LARGE_BITSET__LARGE_BITSET_HPP_JOFA_091019
  11
  12 //[large_bitset_includes
  13 #include <iostream>                   // to organize output
  14 #include <limits>                     // limits and associated constants
  15 #include <boost/operators.hpp>        // to define operators with minimal effort
  16 #include "meta_log.hpp"               // a meta logarithm
  17 #include "bits.hpp"                   // a minimal bitset implementation
  18 #include <boost/icl/interval_map.hpp> // base of large bitsets
  19
  20 namespace mini // minimal implementations for example projects
  21 {
  22 //]
  23
  24 //[large_bitset_natural_typedefs
  25 typedef unsigned char      nat8; // nati i: number bits
  26 typedef unsigned short     nat16;
  27 typedef unsigned long      nat32;
  28 typedef unsigned long long nat64;
  29 typedef unsigned long      nat;
  30
  31 typedef bits<nat8>  bits8;
  32 typedef bits<nat16> bits16;
  33 typedef bits<nat32> bits32;
  34 typedef bits<nat64> bits64;
  35 //]
  36
  37 //[large_bitset_class_template_header
  38 template
  39 <
  40     typename    DomainT = nat64,
  41     typename    BitSetT = bits64,
  42     ICL_COMPARE Compare = ICL_COMPARE_INSTANCE(std::less, DomainT),
  43     ICL_INTERVAL(ICL_COMPARE) Interval = ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, DomainT, Compare),
  44     ICL_ALLOC   Alloc   = std::allocator
  45 >
  46 class large_bitset
  47     : boost::equality_comparable < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>
  48     , boost::less_than_comparable< large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>
  49
  50     , boost::addable       < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>
  51     , boost::orable        < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>
  52     , boost::subtractable  < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>
  53     , boost::andable       < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>
  54     , boost::xorable       < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>
  55
  56     , boost::addable2      < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, DomainT
  57     , boost::orable2       < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, DomainT
  58     , boost::subtractable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, DomainT
  59     , boost::andable2      < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, DomainT
  60     , boost::xorable2      < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, DomainT
  61
  62     , boost::addable2      < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, ICL_INTERVAL_TYPE(Interval,DomainT,Compare)
  63     , boost::orable2       < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, ICL_INTERVAL_TYPE(Interval,DomainT,Compare)
  64     , boost::subtractable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, ICL_INTERVAL_TYPE(Interval,DomainT,Compare)
  65     , boost::andable2      < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, ICL_INTERVAL_TYPE(Interval,DomainT,Compare)
  66     , boost::xorable2      < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, ICL_INTERVAL_TYPE(Interval,DomainT,Compare)
  67       > > > > > > > > > > > > > > > > >
  68     //^ & - | + ^ & - | + ^ & - | + < ==
  69     //segment   element   container
  70 //]
  71 {
  72 public:
  73     //[large_bitset_associated_types
  74     typedef boost::icl::interval_map
  75         <DomainT, BitSetT, boost::icl::partial_absorber,
  76          std::less, boost::icl::inplace_bit_add, boost::icl::inplace_bit_and> interval_bitmap_type;
  77
  78     typedef DomainT                                      domain_type;
  79     typedef DomainT                                      element_type;
  80     typedef BitSetT                                      bitset_type;
  81     typedef typename BitSetT::word_type                  word_type;
  82     typedef typename interval_bitmap_type::interval_type interval_type;
  83     typedef typename interval_bitmap_type::value_type    value_type;
  84     //]
  85 //[large_bitset_operators
  86 public:
  87     bool     operator ==(const large_bitset& rhs)const { return _map == rhs._map; }
  88     bool     operator < (const large_bitset& rhs)const { return _map <  rhs._map; }
  89
  90     large_bitset& operator +=(const large_bitset& rhs) {_map += rhs._map; return *this;}
  91     large_bitset& operator |=(const large_bitset& rhs) {_map |= rhs._map; return *this;}
  92     large_bitset& operator -=(const large_bitset& rhs) {_map -= rhs._map; return *this;}
  93     large_bitset& operator &=(const large_bitset& rhs) {_map &= rhs._map; return *this;}
  94     large_bitset& operator ^=(const large_bitset& rhs) {_map ^= rhs._map; return *this;}
  95
  96     large_bitset& operator +=(const element_type& rhs) {return add(interval_type(rhs));      }
  97     large_bitset& operator |=(const element_type& rhs) {return add(interval_type(rhs));      }
  98     large_bitset& operator -=(const element_type& rhs) {return subtract(interval_type(rhs)); }
  99     large_bitset& operator &=(const element_type& rhs) {return intersect(interval_type(rhs));}
 100     large_bitset& operator ^=(const element_type& rhs) {return flip(interval_type(rhs));     }
 101
 102     large_bitset& operator +=(const interval_type& rhs){return add(rhs);      }
 103     large_bitset& operator |=(const interval_type& rhs){return add(rhs);      }
 104     large_bitset& operator -=(const interval_type& rhs){return subtract(rhs); }
 105     large_bitset& operator &=(const interval_type& rhs){return intersect(rhs);}
 106     large_bitset& operator ^=(const interval_type& rhs){return flip(rhs);     }
 107     //]
 108     //[large_bitset_fundamental_functions
 109     large_bitset& add      (const interval_type& rhs){return segment_apply(&large_bitset::add_,      rhs);}
 110     large_bitset& subtract (const interval_type& rhs){return segment_apply(&large_bitset::subtract_, rhs);}
 111     large_bitset& intersect(const interval_type& rhs){return segment_apply(&large_bitset::intersect_,rhs);}
 112     large_bitset& flip     (const interval_type& rhs){return segment_apply(&large_bitset::flip_,     rhs);}
 113     //]
 114
 115     //[large_bitset_demo_functions
 116     size_t interval_count()const { return boost::icl::interval_count(_map); }
 117
 118     void show_segments()const
 119     {
 120         for(typename interval_bitmap_type::const_iterator it_ = _map.begin();
 121             it_ != _map.end(); ++it_)
 122         {
 123             interval_type   itv  = it_->first;
 124             bitset_type     bits = it_->second;
 125             std::cout << itv << "->" << bits.as_string("01") << std::endl;
 126         }
 127     }
 128
 129     void show_matrix(const char off_on[2] = " 1")const
 130     {
 131         using namespace boost;
 132         typename interval_bitmap_type::const_iterator iter = _map.begin();
 133         while(iter != _map.end())
 134         {
 135             element_type fst = icl::first(iter->first), lst = icl::last(iter->first);
 136             for(element_type chunk = fst; chunk <= lst; chunk++)
 137                 std::cout << iter->second.as_string(off_on) << std::endl;
 138             ++iter;
 139         }
 140     }
 141     //]
 142
 143 //[large_bitset_impl_constants
 144 private:                                      // Example value
 145     static const word_type                    //   8-bit case
 146         digits  = std::numeric_limits         // --------------------------------------------------------------
 147                   <word_type>::digits       , //   8           Size of the associated bitsets
 148         divisor = digits                    , //   8           Divisor to find intervals for values
 149         last    = digits-1                  , //   7           Last bit (0 based)
 150         shift   = log2_<divisor>::value     , //   3           To express the division as bit shift
 151         w1      = static_cast<word_type>(1) , //               Helps to avoid static_casts for long long
 152         mask    = divisor - w1              , //   7=11100000  Helps to express the modulo operation as bit_and
 153         all     = ~static_cast<word_type>(0), // 255=11111111  Helps to express a complete associated bitset
 154         top     = w1 << (digits-w1)      ;    // 128=00000001  Value of the most significant bit of associated bitsets
 155                                               //            !> Note: Most signigicant bit on the right.
 156     //]
 157     //[large_bitset_segment_combiner
 158     typedef void (large_bitset::*segment_combiner)(element_type, element_type, bitset_type);
 159     //]
 160
 161     //[large_bitset_bitset_filler
 162     static word_type from_lower_to(word_type bit){return bit==last ? all : (w1<<(bit+w1))-w1;}
 163     static word_type to_upper_from(word_type bit){return bit==last ? top : ~((w1<<bit)-w1); }
 164     //]
 165
 166     //[large_bitset_segment_apply
 167     large_bitset& segment_apply(segment_combiner combine, const interval_type& operand)
 168     {
 169         using namespace boost;
 170         if(icl::is_empty(operand))
 171             return *this;
 172                                                             // same as
 173         element_type   base = icl::first(operand) >> shift, // icl::first(operand) / divisor
 174                        ceil = icl::last (operand) >> shift; // icl::last (operand) / divisor
 175         word_type base_rest = icl::first(operand) &  mask , // icl::first(operand) % divisor
 176                   ceil_rest = icl::last (operand) &  mask ; // icl::last (operand) % divisor
 177
 178         if(base == ceil) // [first, last] are within one bitset (chunk)
 179             (this->*combine)(base, base+1, bitset_type(  to_upper_from(base_rest)
 180                                                        & from_lower_to(ceil_rest)));
 181         else // [first, last] spread over more than one bitset (chunk)
 182         {
 183             element_type mid_low = base_rest == 0   ? base   : base+1, // first element of mid part
 184                          mid_up  = ceil_rest == all ? ceil+1 : ceil  ; // last  element of mid part
 185
 186             if(base_rest > 0)    // Bitset of base interval has to be filled from base_rest to last
 187                 (this->*combine)(base, base+1, bitset_type(to_upper_from(base_rest)));
 188             if(ceil_rest < all)  // Bitset of ceil interval has to be filled from first to ceil_rest
 189                 (this->*combine)(ceil, ceil+1, bitset_type(from_lower_to(ceil_rest)));
 190             if(mid_low < mid_up) // For the middle part all bits have to set.
 191                 (this->*combine)(mid_low, mid_up, bitset_type(all));
 192         }
 193         return *this;
 194     }
 195     //]
 196
 197     //[large_bitmap_combiners
 198     void       add_(DomainT lo, DomainT up, BitSetT bits){_map += value_type(interval_type::right_open(lo,up), bits);}
 199     void  subtract_(DomainT lo, DomainT up, BitSetT bits){_map -= value_type(interval_type::right_open(lo,up), bits);}
 200     void intersect_(DomainT lo, DomainT up, BitSetT bits){_map &= value_type(interval_type::right_open(lo,up), bits);}
 201     void      flip_(DomainT lo, DomainT up, BitSetT bits){_map ^= value_type(interval_type::right_open(lo,up), bits);}
 202     //]
 203
 204 //[large_bitmap_impl_map
 205 private:
 206     interval_bitmap_type _map;
 207 //]
 208 };
 209
 210 } // mini
 211 #endif
 212
 213