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