boost/detail/dynamic_bitset.hpp

   1 // -----------------------------------------------------------
   2 //
   3 //   Copyright (c) 2001-2002 Chuck Allison and Jeremy Siek
   4 //        Copyright (c) 2003-2006, 2008 Gennaro Prota
   5 //
   6 // Distributed under the Boost Software License, Version 1.0.
   7 //    (See accompanying file LICENSE_1_0.txt or copy at
   8 //          http://www.boost.org/LICENSE_1_0.txt)
   9 //
  10 // -----------------------------------------------------------
  11
  12 #ifndef BOOST_DETAIL_DYNAMIC_BITSET_HPP
  13 #define BOOST_DETAIL_DYNAMIC_BITSET_HPP
  14
  15 #include <cstddef>
  16 #include "boost/config.hpp"
  17 #include "boost/detail/workaround.hpp"
  18
  19
  20 namespace boost {
  21
  22   namespace detail {
  23   namespace dynamic_bitset_impl {
  24
  25     // Gives (read-)access to the object representation
  26     // of an object of type T (3.9p4). CANNOT be used
  27     // on a base sub-object
  28     //
  29     template <typename T>
  30     inline const unsigned char * object_representation (T* p)
  31     {
  32         return static_cast<const unsigned char *>(static_cast<const void *>(p));
  33     }
  34
  35     template<typename T, int amount, int width /* = default */>
  36     struct shifter
  37     {
  38         static void left_shift(T & v) {
  39             amount >= width ? (v = 0)
  40                 : (v >>= BOOST_DYNAMIC_BITSET_WRAP_CONSTANT(amount));
  41         }
  42     };
  43
  44     // ------- count function implementation --------------
  45
  46     typedef unsigned char byte_type;
  47
  48     // These two entities
  49     //
  50     //     enum mode { access_by_bytes, access_by_blocks };
  51     //     template <mode> struct mode_to_type {};
  52     //
  53     // were removed, since the regression logs (as of 24 Aug 2008)
  54     // showed that several compilers had troubles with recognizing
  55     //
  56     //   const mode m = access_by_bytes
  57     //
  58     // as a constant expression
  59     //
  60     // * So, we'll use bool, instead of enum *.
  61     //
  62     template <bool value>
  63     struct value_to_type
  64     {
  65         value_to_type() {}
  66     };
  67     const bool access_by_bytes = true;
  68     const bool access_by_blocks = false;
  69
  70
  71     // the table: wrapped in a class template, so
  72     // that it is only instantiated if/when needed
  73     //
  74     template <bool dummy_name = true>
  75     struct count_table { static const byte_type table[]; };
  76
  77     template <>
  78     struct count_table<false> { /* no table */ };
  79
  80
  81      const unsigned int table_width = 8;
  82      template <bool b>
  83      const byte_type count_table<b>::table[] =
  84      {
  85        // Automatically generated by GPTableGen.exe v.1.0
  86        //
  87      0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  88      1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  89      1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  90      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  91      1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  92      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  93      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  94      3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
  95      };
  96
  97
  98      // overload for access by bytes
  99      //
 100
 101      template <typename Iterator>
 102      inline std::size_t do_count(Iterator first, std::size_t length,
 103                                  int /*dummy param*/,
 104                                  value_to_type<access_by_bytes>* )
 105      {
 106          std::size_t num = 0;
 107          if (length)
 108          {
 109              const byte_type * p = object_representation(&*first);
 110              length *= sizeof(*first);
 111
 112               do {
 113                  num += count_table<>::table[*p];
 114                  ++p;
 115                  --length;
 116
 117              } while (length);
 118          }
 119
 120          return num;
 121      }
 122
 123
 124      // overload for access by blocks
 125      //
 126      template <typename Iterator, typename ValueType>
 127      inline std::size_t do_count(Iterator first, std::size_t length, ValueType,
 128                                  value_to_type<access_by_blocks>*)
 129      {
 130          std::size_t num = 0;
 131          while (length){
 132
 133              ValueType value = *first;
 134              while (value) {
 135                  num += count_table<>::table[value & ((1u<<table_width) - 1)];
 136                  value >>= table_width;
 137              }
 138
 139              ++first;
 140              --length;
 141          }
 142
 143          return num;
 144      }
 145
 146     // -------------------------------------------------------
 147
 148
 149     // Some library implementations simply return a dummy
 150     // value such as
 151     //
 152     //   size_type(-1) / sizeof(T)
 153     //
 154     // from vector<>::max_size. This tries to get more
 155     // meaningful info.
 156     //
 157     template <typename T>
 158     typename T::size_type vector_max_size_workaround(const T & v) {
 159
 160       typedef typename T::allocator_type allocator_type;
 161
 162       const typename allocator_type::size_type alloc_max =
 163                                                   v.get_allocator().max_size();
 164       const typename T::size_type container_max = v.max_size();
 165
 166       return alloc_max < container_max?
 167                     alloc_max :
 168                     container_max;
 169     }
 170
 171     // for static_asserts
 172     template <typename T>
 173     struct allowed_block_type {
 174         enum { value = T(-1) > 0 }; // ensure T has no sign
 175     };
 176
 177     template <>
 178     struct allowed_block_type<bool> {
 179         enum { value = false };
 180     };
 181
 182
 183     template <typename T>
 184     struct is_numeric {
 185         enum { value = false };
 186     };
 187
 188 #   define BOOST_dynamic_bitset_is_numeric(x)       \
 189                 template<>                          \
 190                 struct is_numeric< x > {            \
 191                     enum { value = true };          \
 192                 }                                /**/
 193
 194     BOOST_dynamic_bitset_is_numeric(bool);
 195     BOOST_dynamic_bitset_is_numeric(char);
 196
 197 #if !defined(BOOST_NO_INTRINSIC_WCHAR_T)
 198     BOOST_dynamic_bitset_is_numeric(wchar_t);
 199 #endif
 200
 201     BOOST_dynamic_bitset_is_numeric(signed char);
 202     BOOST_dynamic_bitset_is_numeric(short int);
 203     BOOST_dynamic_bitset_is_numeric(int);
 204     BOOST_dynamic_bitset_is_numeric(long int);
 205
 206     BOOST_dynamic_bitset_is_numeric(unsigned char);
 207     BOOST_dynamic_bitset_is_numeric(unsigned short);
 208     BOOST_dynamic_bitset_is_numeric(unsigned int);
 209     BOOST_dynamic_bitset_is_numeric(unsigned long);
 210
 211 #if defined(BOOST_HAS_LONG_LONG)
 212     BOOST_dynamic_bitset_is_numeric(::boost::long_long_type);
 213     BOOST_dynamic_bitset_is_numeric(::boost::ulong_long_type);
 214 #endif
 215
 216     // intentionally omitted
 217     //BOOST_dynamic_bitset_is_numeric(float);
 218     //BOOST_dynamic_bitset_is_numeric(double);
 219     //BOOST_dynamic_bitset_is_numeric(long double);
 220
 221 #undef BOOST_dynamic_bitset_is_numeric
 222
 223   } // dynamic_bitset_impl
 224   } // namespace detail
 225
 226 } // namespace boost
 227
 228 #endif // include guard
 229