1 // -----------------------------------------------------------
3 // Copyright (c) 2001-2002 Chuck Allison and Jeremy Siek
4 // Copyright (c) 2003-2006, 2008 Gennaro Prota
6 // Copyright (c) 2014 Glen Joseph Fernandes
7 // glenfe at live dot com
9 // Distributed under the Boost Software License, Version 1.0.
10 // (See accompanying file LICENSE_1_0.txt or copy at
11 // http://www.boost.org/LICENSE_1_0.txt)
13 // -----------------------------------------------------------
15 #ifndef BOOST_DETAIL_DYNAMIC_BITSET_HPP
16 #define BOOST_DETAIL_DYNAMIC_BITSET_HPP
20 #include "boost/config.hpp"
21 #include "boost/detail/workaround.hpp"
27 namespace dynamic_bitset_impl {
29 // Gives (read-)access to the object representation
30 // of an object of type T (3.9p4). CANNOT be used
31 // on a base sub-object
34 inline const unsigned char * object_representation (T* p)
36 return static_cast<const unsigned char *>(static_cast<const void *>(p));
39 template<typename T, int amount, int width /* = default */>
42 static void left_shift(T & v) {
43 amount >= width ? (v = 0)
44 : (v >>= BOOST_DYNAMIC_BITSET_WRAP_CONSTANT(amount));
48 // ------- count function implementation --------------
50 typedef unsigned char byte_type;
54 // enum mode { access_by_bytes, access_by_blocks };
55 // template <mode> struct mode_to_type {};
57 // were removed, since the regression logs (as of 24 Aug 2008)
58 // showed that several compilers had troubles with recognizing
60 // const mode m = access_by_bytes
62 // as a constant expression
64 // * So, we'll use bool, instead of enum *.
71 const bool access_by_bytes = true;
72 const bool access_by_blocks = false;
75 // the table: wrapped in a class template, so
76 // that it is only instantiated if/when needed
78 template <bool dummy_name = true>
79 struct count_table { static const byte_type table[]; };
82 struct count_table<false> { /* no table */ };
85 const unsigned int table_width = 8;
87 const byte_type count_table<b>::table[] =
89 // Automatically generated by GPTableGen.exe v.1.0
91 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,
92 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,
93 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,
94 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,
95 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,
96 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,
97 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,
98 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
102 // overload for access by bytes
105 template <typename Iterator>
106 inline std::size_t do_count(Iterator first, std::size_t length,
108 value_to_type<access_by_bytes>* )
113 const byte_type * p = object_representation(&*first);
114 length *= sizeof(*first);
117 num += count_table<>::table[*p];
128 // overload for access by blocks
130 template <typename Iterator, typename ValueType>
131 inline std::size_t do_count(Iterator first, std::size_t length, ValueType,
132 value_to_type<access_by_blocks>*)
137 ValueType value = *first;
139 num += count_table<>::table[value & ((1u<<table_width) - 1)];
140 value >>= table_width;
150 // -------------------------------------------------------
153 // Some library implementations simply return a dummy
156 // size_type(-1) / sizeof(T)
158 // from vector<>::max_size. This tries to get more
161 template <typename T>
162 inline typename T::size_type vector_max_size_workaround(const T & v)
165 typedef typename T::allocator_type allocator_type;
167 const allocator_type& alloc = v.get_allocator();
169 #if !defined(BOOST_NO_CXX11_ALLOCATOR)
170 typedef std::allocator_traits<allocator_type> allocator_traits;
172 const typename allocator_traits::size_type alloc_max =
173 allocator_traits::max_size(alloc);
175 const typename allocator_type::size_type alloc_max = alloc.max_size();
178 const typename T::size_type container_max = v.max_size();
180 return alloc_max < container_max ? alloc_max : container_max;
183 // for static_asserts
184 template <typename T>
185 struct allowed_block_type {
186 enum { value = T(-1) > 0 }; // ensure T has no sign
190 struct allowed_block_type<bool> {
191 enum { value = false };
195 template <typename T>
197 enum { value = false };
200 # define BOOST_dynamic_bitset_is_numeric(x) \
202 struct is_numeric< x > { \
203 enum { value = true }; \
206 BOOST_dynamic_bitset_is_numeric(bool);
207 BOOST_dynamic_bitset_is_numeric(char);
209 #if !defined(BOOST_NO_INTRINSIC_WCHAR_T)
210 BOOST_dynamic_bitset_is_numeric(wchar_t);
213 BOOST_dynamic_bitset_is_numeric(signed char);
214 BOOST_dynamic_bitset_is_numeric(short int);
215 BOOST_dynamic_bitset_is_numeric(int);
216 BOOST_dynamic_bitset_is_numeric(long int);
218 BOOST_dynamic_bitset_is_numeric(unsigned char);
219 BOOST_dynamic_bitset_is_numeric(unsigned short);
220 BOOST_dynamic_bitset_is_numeric(unsigned int);
221 BOOST_dynamic_bitset_is_numeric(unsigned long);
223 #if defined(BOOST_HAS_LONG_LONG)
224 BOOST_dynamic_bitset_is_numeric(::boost::long_long_type);
225 BOOST_dynamic_bitset_is_numeric(::boost::ulong_long_type);
228 // intentionally omitted
229 //BOOST_dynamic_bitset_is_numeric(float);
230 //BOOST_dynamic_bitset_is_numeric(double);
231 //BOOST_dynamic_bitset_is_numeric(long double);
233 #undef BOOST_dynamic_bitset_is_numeric
235 } // dynamic_bitset_impl
236 } // namespace detail
240 #endif // include guard