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> object_representation(T * p)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 { left_shiftboost::detail::dynamic_bitset_impl::shifter38 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 { value_to_typeboost::detail::dynamic_bitset_impl::value_to_type65 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> do_count(Iterator first,std::size_t length,int,value_to_type<access_by_bytes> *)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> do_count(Iterator first,std::size_t length,ValueType,value_to_type<access_by_blocks> *)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> vector_max_size_workaround(const T & v)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 230