1// -----------------------------------------------------------
2//
3// Copyright (c) 2001-2002 Chuck Allison and Jeremy Siek
4// Copyright (c) 2003-2006, 2008 Gennaro Prota
5// Copyright (c) 2014 Glen Joseph Fernandes
6// (glenjofe@gmail.com)
7// Copyright (c) 2018 Evgeny Shulgin
8// Copyright (c) 2019 Andrey Semashev
9//
10// Distributed under the Boost Software License, Version 1.0.
11// (See accompanying file LICENSE_1_0.txt or copy at
12// http://www.boost.org/LICENSE_1_0.txt)
13//
14// -----------------------------------------------------------
15
16#ifndef BOOST_DETAIL_DYNAMIC_BITSET_HPP
17#define BOOST_DETAIL_DYNAMIC_BITSET_HPP
18
19#include <memory>
20#include <cstddef>
21#include "boost/config.hpp"
22#include "boost/detail/workaround.hpp"
23#include <boost/core/allocator_access.hpp>
24
25#if ((defined(BOOST_MSVC) && (BOOST_MSVC >= 1600)) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64))
26#include <intrin.h>
27#endif
28
29namespace boost {
30
31 namespace detail {
32 namespace dynamic_bitset_impl {
33
34 template<class T>
35 struct max_limit {
36 BOOST_STATIC_CONSTEXPR T value = static_cast<T>(-1);
37 };
38
39 template<class T>
40 BOOST_CONSTEXPR_OR_CONST T max_limit<T>::value;
41
42 // Gives (read-)access to the object representation
43 // of an object of type T (3.9p4). CANNOT be used
44 // on a base sub-object
45 //
46 template <typename T>
47 inline const unsigned char * object_representation (T* p)
48 {
49 return static_cast<const unsigned char *>(static_cast<const void *>(p));
50 }
51
52 template<typename T, int amount, int width /* = default */>
53 struct shifter
54 {
55 static void left_shift(T & v) {
56 amount >= width ? (v = 0)
57 : (v >>= BOOST_DYNAMIC_BITSET_WRAP_CONSTANT(amount));
58 }
59 };
60
61 // ------- count function implementation --------------
62
63 typedef unsigned char byte_type;
64
65 // These two entities
66 //
67 // enum mode { access_by_bytes, access_by_blocks };
68 // template <mode> struct mode_to_type {};
69 //
70 // were removed, since the regression logs (as of 24 Aug 2008)
71 // showed that several compilers had troubles with recognizing
72 //
73 // const mode m = access_by_bytes
74 //
75 // as a constant expression
76 //
77 // * So, we'll use bool, instead of enum *.
78 //
79 template <bool value>
80 struct value_to_type
81 {
82 value_to_type() {}
83 };
84 const bool access_by_bytes = true;
85 const bool access_by_blocks = false;
86
87
88 // the table: wrapped in a class template, so
89 // that it is only instantiated if/when needed
90 //
91 template <bool dummy_name = true>
92 struct count_table { static const byte_type table[]; };
93
94 template <>
95 struct count_table<false> { /* no table */ };
96
97
98 const unsigned int table_width = 8;
99 template <bool b>
100 const byte_type count_table<b>::table[] =
101 {
102 // Automatically generated by GPTableGen.exe v.1.0
103 //
104 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,
105 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,
106 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,
107 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,
108 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,
109 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,
110 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,
111 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
112 };
113
114
115 // Some platforms have fast popcount operation, that allow us to implement
116 // counting bits much more efficiently
117 //
118 template <typename ValueType>
119 BOOST_FORCEINLINE std::size_t popcount(ValueType value) BOOST_NOEXCEPT
120 {
121 std::size_t num = 0u;
122 while (value) {
123 num += count_table<>::table[value & ((1u<<table_width) - 1)];
124 value >>= table_width;
125 }
126 return num;
127 }
128
129#if (((defined(BOOST_MSVC) && (BOOST_MSVC >= 1600)) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64))) \
130 && (defined(__POPCNT__) || defined(__AVX__))
131
132 template <>
133 BOOST_FORCEINLINE std::size_t popcount<unsigned short>(unsigned short value) BOOST_NOEXCEPT
134 {
135 return static_cast<std::size_t>(__popcnt16(value));
136 }
137
138 template <>
139 BOOST_FORCEINLINE std::size_t popcount<unsigned int>(unsigned int value) BOOST_NOEXCEPT
140 {
141 return static_cast<std::size_t>(__popcnt(value));
142 }
143
144 template <>
145 BOOST_FORCEINLINE std::size_t popcount<unsigned __int64>(unsigned __int64 value) BOOST_NOEXCEPT
146 {
147#if defined(_M_X64)
148 return static_cast<std::size_t>(__popcnt64(value));
149#else
150 return static_cast<std::size_t>(__popcnt(static_cast< unsigned int >(value))) + static_cast<std::size_t>(__popcnt(static_cast< unsigned int >(value >> 32)));
151#endif
152 }
153
154#elif defined(BOOST_GCC) || defined(__clang__) || (defined(BOOST_INTEL) && defined(__GNUC__))
155
156 // Note: gcc builtins are implemented by compiler runtime when the target CPU may not support the necessary instructions
157 template <>
158 BOOST_FORCEINLINE std::size_t popcount<unsigned short>(unsigned short value) BOOST_NOEXCEPT
159 {
160 return static_cast<unsigned int>(__builtin_popcount(static_cast<unsigned int>(value)));
161 }
162
163 template <>
164 BOOST_FORCEINLINE std::size_t popcount<unsigned int>(unsigned int value) BOOST_NOEXCEPT
165 {
166 return static_cast<unsigned int>(__builtin_popcount(value));
167 }
168
169 template <>
170 BOOST_FORCEINLINE std::size_t popcount<unsigned long>(unsigned long value) BOOST_NOEXCEPT
171 {
172 return static_cast<unsigned int>(__builtin_popcountl(value));
173 }
174
175 template <>
176 BOOST_FORCEINLINE std::size_t popcount<boost::ulong_long_type>(boost::ulong_long_type value) BOOST_NOEXCEPT
177 {
178 return static_cast<unsigned int>(__builtin_popcountll(value));
179 }
180
181#endif
182
183 // overload for access by blocks
184 //
185 template <typename Iterator, typename ValueType>
186 inline std::size_t do_count(Iterator first, std::size_t length, ValueType,
187 value_to_type<access_by_blocks>*)
188 {
189 std::size_t num1 = 0u, num2 = 0u;
190 while (length >= 2u) {
191 num1 += popcount<ValueType>(*first);
192 ++first;
193 num2 += popcount<ValueType>(*first);
194 ++first;
195 length -= 2u;
196 }
197
198 if (length > 0u)
199 num1 += popcount<ValueType>(*first);
200
201 return num1 + num2;
202 }
203
204 // overload for access by bytes
205 //
206 template <typename Iterator>
207 inline std::size_t do_count(Iterator first, std::size_t length,
208 int /*dummy param*/,
209 value_to_type<access_by_bytes>*)
210 {
211 if (length > 0u) {
212 const byte_type* p = object_representation(&*first);
213 length *= sizeof(*first);
214
215 return do_count(first: p, length, static_cast<byte_type>(0u),
216 static_cast< value_to_type<access_by_blocks>* >(0));
217 }
218
219 return 0u;
220 }
221
222 // -------------------------------------------------------
223
224
225 // Some library implementations simply return a dummy
226 // value such as
227 //
228 // size_type(-1) / sizeof(T)
229 //
230 // from vector<>::max_size. This tries to get more
231 // meaningful info.
232 //
233 template <typename T>
234 inline typename T::size_type vector_max_size_workaround(const T & v)
235 BOOST_NOEXCEPT
236 {
237 typedef typename T::allocator_type allocator_type;
238
239 const allocator_type& alloc = v.get_allocator();
240
241 typename boost::allocator_size_type<allocator_type>::type alloc_max =
242 boost::allocator_max_size(alloc);
243
244 const typename T::size_type container_max = v.max_size();
245
246 return alloc_max < container_max ? alloc_max : container_max;
247 }
248
249 // for static_asserts
250 template <typename T>
251 struct allowed_block_type {
252 enum { value = T(-1) > 0 }; // ensure T has no sign
253 };
254
255 template <>
256 struct allowed_block_type<bool> {
257 enum { value = false };
258 };
259
260
261 template <typename T>
262 struct is_numeric {
263 enum { value = false };
264 };
265
266# define BOOST_dynamic_bitset_is_numeric(x) \
267 template<> \
268 struct is_numeric< x > { \
269 enum { value = true }; \
270 } /**/
271
272 BOOST_dynamic_bitset_is_numeric(bool);
273 BOOST_dynamic_bitset_is_numeric(char);
274
275#if !defined(BOOST_NO_INTRINSIC_WCHAR_T)
276 BOOST_dynamic_bitset_is_numeric(wchar_t);
277#endif
278
279 BOOST_dynamic_bitset_is_numeric(signed char);
280 BOOST_dynamic_bitset_is_numeric(short int);
281 BOOST_dynamic_bitset_is_numeric(int);
282 BOOST_dynamic_bitset_is_numeric(long int);
283
284 BOOST_dynamic_bitset_is_numeric(unsigned char);
285 BOOST_dynamic_bitset_is_numeric(unsigned short);
286 BOOST_dynamic_bitset_is_numeric(unsigned int);
287 BOOST_dynamic_bitset_is_numeric(unsigned long);
288
289#if defined(BOOST_HAS_LONG_LONG)
290 BOOST_dynamic_bitset_is_numeric(::boost::long_long_type);
291 BOOST_dynamic_bitset_is_numeric(::boost::ulong_long_type);
292#endif
293
294 // intentionally omitted
295 //BOOST_dynamic_bitset_is_numeric(float);
296 //BOOST_dynamic_bitset_is_numeric(double);
297 //BOOST_dynamic_bitset_is_numeric(long double);
298
299#undef BOOST_dynamic_bitset_is_numeric
300
301 } // dynamic_bitset_impl
302 } // namespace detail
303
304} // namespace boost
305
306#endif // include guard
307
308

source code of include/boost/dynamic_bitset/detail/dynamic_bitset.hpp