dynamic_bitset/detail/dynamic_bitset.hpp

0001 // -----------------------------------------------------------
0002 //
0003 //   Copyright (c) 2001-2002 Chuck Allison and Jeremy Siek
0004 //   Copyright (c) 2003-2006, 2008 Gennaro Prota
0005 //   Copyright (c) 2014 Glen Joseph Fernandes
0006 //       (glenjofe@gmail.com)
0007 //   Copyright (c) 2018 Evgeny Shulgin
0008 //   Copyright (c) 2019 Andrey Semashev
0009 //
0010 // Distributed under the Boost Software License, Version 1.0.
0011 //    (See accompanying file LICENSE_1_0.txt or copy at
0012 //          http://www.boost.org/LICENSE_1_0.txt)
0013 //
0014 // -----------------------------------------------------------
0015
0016 #ifndef BOOST_DETAIL_DYNAMIC_BITSET_HPP
0017 #define BOOST_DETAIL_DYNAMIC_BITSET_HPP
0018
0019 #include <memory>
0020 #include <cstddef>
0021 #include "boost/config.hpp"
0022 #include "boost/detail/workaround.hpp"
0023 #include <boost/core/allocator_access.hpp>
0024
0025 #if ((defined(BOOST_MSVC) && (BOOST_MSVC >= 1600)) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64))
0026 #include <intrin.h>
0027 #endif
0028
0029 namespace boost {
0030
0031   namespace detail {
0032   namespace dynamic_bitset_impl {
0033
0034     template<class T>
0035     struct max_limit {
0036         BOOST_STATIC_CONSTEXPR T value = static_cast<T>(-1);
0037     };
0038
0039     template<class T>
0040     BOOST_CONSTEXPR_OR_CONST T max_limit<T>::value;
0041
0042     // Gives (read-)access to the object representation
0043     // of an object of type T (3.9p4). CANNOT be used
0044     // on a base sub-object
0045     //
0046     template <typename T>
0047     inline const unsigned char * object_representation (T* p)
0048     {
0049         return static_cast<const unsigned char *>(static_cast<const void *>(p));
0050     }
0051
0052     template<typename T, int amount, int width /* = default */>
0053     struct shifter
0054     {
0055         static void left_shift(T & v) {
0056             amount >= width ? (v = 0)
0057                 : (v >>= BOOST_DYNAMIC_BITSET_WRAP_CONSTANT(amount));
0058         }
0059     };
0060
0061     // ------- count function implementation --------------
0062
0063     typedef unsigned char byte_type;
0064
0065     // These two entities
0066     //
0067     //     enum mode { access_by_bytes, access_by_blocks };
0068     //     template <mode> struct mode_to_type {};
0069     //
0070     // were removed, since the regression logs (as of 24 Aug 2008)
0071     // showed that several compilers had troubles with recognizing
0072     //
0073     //   const mode m = access_by_bytes
0074     //
0075     // as a constant expression
0076     //
0077     // * So, we'll use bool, instead of enum *.
0078     //
0079     template <bool value>
0080     struct value_to_type
0081     {
0082         value_to_type() {}
0083     };
0084     const bool access_by_bytes = true;
0085     const bool access_by_blocks = false;
0086
0087
0088     // the table: wrapped in a class template, so
0089     // that it is only instantiated if/when needed
0090     //
0091     template <bool dummy_name = true>
0092     struct count_table { static const byte_type table[]; };
0093
0094     template <>
0095     struct count_table<false> { /* no table */ };
0096
0097
0098     const unsigned int table_width = 8;
0099     template <bool b>
0100     const byte_type count_table<b>::table[] =
0101     {
0102         // Automatically generated by GPTableGen.exe v.1.0
0103         //
0104         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,
0105         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,
0106         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,
0107         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,
0108         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,
0109         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,
0110         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,
0111         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
0112     };
0113
0114
0115     // Some platforms have fast popcount operation, that allow us to implement
0116     // counting bits much more efficiently
0117     //
0118     template <typename ValueType>
0119     BOOST_FORCEINLINE std::size_t popcount(ValueType value) BOOST_NOEXCEPT
0120     {
0121         std::size_t num = 0u;
0122         while (value) {
0123             num += count_table<>::table[value & ((1u<<table_width) - 1)];
0124             value >>= table_width;
0125         }
0126         return num;
0127     }
0128
0129 #if (((defined(BOOST_MSVC) && (BOOST_MSVC >= 1600)) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64))) \
0130     && (defined(__POPCNT__) || defined(__AVX__))
0131
0132     template <>
0133     BOOST_FORCEINLINE std::size_t popcount<unsigned short>(unsigned short value) BOOST_NOEXCEPT
0134     {
0135         return static_cast<std::size_t>(__popcnt16(value));
0136     }
0137
0138     template <>
0139     BOOST_FORCEINLINE std::size_t popcount<unsigned int>(unsigned int value) BOOST_NOEXCEPT
0140     {
0141         return static_cast<std::size_t>(__popcnt(value));
0142     }
0143
0144     template <>
0145     BOOST_FORCEINLINE std::size_t popcount<unsigned __int64>(unsigned __int64 value) BOOST_NOEXCEPT
0146     {
0147 #if defined(_M_X64)
0148         return static_cast<std::size_t>(__popcnt64(value));
0149 #else
0150         return static_cast<std::size_t>(__popcnt(static_cast< unsigned int >(value))) + static_cast<std::size_t>(__popcnt(static_cast< unsigned int >(value >> 32)));
0151 #endif
0152     }
0153
0154 #elif defined(BOOST_GCC) || defined(__clang__) || (defined(BOOST_INTEL) && defined(__GNUC__))
0155
0156     // Note: gcc builtins are implemented by compiler runtime when the target CPU may not support the necessary instructions
0157     template <>
0158     BOOST_FORCEINLINE std::size_t popcount<unsigned short>(unsigned short value) BOOST_NOEXCEPT
0159     {
0160         return static_cast<unsigned int>(__builtin_popcount(static_cast<unsigned int>(value)));
0161     }
0162
0163     template <>
0164     BOOST_FORCEINLINE std::size_t popcount<unsigned int>(unsigned int value) BOOST_NOEXCEPT
0165     {
0166         return static_cast<unsigned int>(__builtin_popcount(value));
0167     }
0168
0169     template <>
0170     BOOST_FORCEINLINE std::size_t popcount<unsigned long>(unsigned long value) BOOST_NOEXCEPT
0171     {
0172         return static_cast<unsigned int>(__builtin_popcountl(value));
0173     }
0174
0175     template <>
0176     BOOST_FORCEINLINE std::size_t popcount<boost::ulong_long_type>(boost::ulong_long_type value) BOOST_NOEXCEPT
0177     {
0178         return static_cast<unsigned int>(__builtin_popcountll(value));
0179     }
0180
0181 #endif
0182
0183     // overload for access by blocks
0184     //
0185     template <typename Iterator, typename ValueType>
0186     inline std::size_t do_count(Iterator first, std::size_t length, ValueType,
0187                                 value_to_type<access_by_blocks>*)
0188     {
0189         std::size_t num1 = 0u, num2 = 0u;
0190         while (length >= 2u) {
0191             num1 += popcount<ValueType>(*first);
0192             ++first;
0193             num2 += popcount<ValueType>(*first);
0194             ++first;
0195             length -= 2u;
0196         }
0197
0198         if (length > 0u)
0199             num1 += popcount<ValueType>(*first);
0200
0201         return num1 + num2;
0202     }
0203
0204     // overload for access by bytes
0205     //
0206     template <typename Iterator>
0207     inline std::size_t do_count(Iterator first, std::size_t length,
0208                                 int /*dummy param*/,
0209                                 value_to_type<access_by_bytes>*)
0210     {
0211         if (length > 0u) {
0212             const byte_type* p = object_representation(&*first);
0213             length *= sizeof(*first);
0214
0215             return do_count(p, length, static_cast<byte_type>(0u),
0216                 static_cast< value_to_type<access_by_blocks>* >(0));
0217         }
0218
0219         return 0u;
0220     }
0221
0222     // -------------------------------------------------------
0223
0224
0225     // Some library implementations simply return a dummy
0226     // value such as
0227     //
0228     //   size_type(-1) / sizeof(T)
0229     //
0230     // from vector<>::max_size. This tries to get more
0231     // meaningful info.
0232     //
0233     template <typename T>
0234     inline typename T::size_type vector_max_size_workaround(const T & v)
0235         BOOST_NOEXCEPT
0236     {
0237         typedef typename T::allocator_type allocator_type;
0238
0239         const allocator_type& alloc = v.get_allocator();
0240
0241         typename boost::allocator_size_type<allocator_type>::type alloc_max =
0242             boost::allocator_max_size(alloc);
0243
0244         const typename T::size_type container_max = v.max_size();
0245
0246         return alloc_max < container_max ? alloc_max : container_max;
0247     }
0248
0249     // for static_asserts
0250     template <typename T>
0251     struct allowed_block_type {
0252         enum { value = T(-1) > 0 }; // ensure T has no sign
0253     };
0254
0255     template <>
0256     struct allowed_block_type<bool> {
0257         enum { value = false };
0258     };
0259
0260
0261     template <typename T>
0262     struct is_numeric {
0263         enum { value = false };
0264     };
0265
0266 #   define BOOST_dynamic_bitset_is_numeric(x)       \
0267                 template<>                          \
0268                 struct is_numeric< x > {            \
0269                     enum { value = true };          \
0270                 }                                /**/
0271
0272     BOOST_dynamic_bitset_is_numeric(bool);
0273     BOOST_dynamic_bitset_is_numeric(char);
0274
0275 #if !defined(BOOST_NO_INTRINSIC_WCHAR_T)
0276     BOOST_dynamic_bitset_is_numeric(wchar_t);
0277 #endif
0278
0279     BOOST_dynamic_bitset_is_numeric(signed char);
0280     BOOST_dynamic_bitset_is_numeric(short int);
0281     BOOST_dynamic_bitset_is_numeric(int);
0282     BOOST_dynamic_bitset_is_numeric(long int);
0283
0284     BOOST_dynamic_bitset_is_numeric(unsigned char);
0285     BOOST_dynamic_bitset_is_numeric(unsigned short);
0286     BOOST_dynamic_bitset_is_numeric(unsigned int);
0287     BOOST_dynamic_bitset_is_numeric(unsigned long);
0288
0289 #if defined(BOOST_HAS_LONG_LONG)
0290     BOOST_dynamic_bitset_is_numeric(::boost::long_long_type);
0291     BOOST_dynamic_bitset_is_numeric(::boost::ulong_long_type);
0292 #endif
0293
0294     // intentionally omitted
0295     //BOOST_dynamic_bitset_is_numeric(float);
0296     //BOOST_dynamic_bitset_is_numeric(double);
0297     //BOOST_dynamic_bitset_is_numeric(long double);
0298
0299 #undef BOOST_dynamic_bitset_is_numeric
0300
0301   } // dynamic_bitset_impl
0302   } // namespace detail
0303
0304 } // namespace boost
0305
0306 #endif // include guard
0307