Differential D1905 Diff 10430 libraries/win32/boost/include/boost/dynamic_bitset/detail/dynamic_bitset.hpp
Changeset View
Changeset View
Standalone View
Standalone View
libraries/win32/boost/include/boost/dynamic_bitset/detail/dynamic_bitset.hpp
- This file was added.
// ----------------------------------------------------------- | |||||
// | |||||
// Copyright (c) 2001-2002 Chuck Allison and Jeremy Siek | |||||
// Copyright (c) 2003-2006, 2008 Gennaro Prota | |||||
// Copyright (c) 2014 Glen Joseph Fernandes | |||||
// (glenjofe@gmail.com) | |||||
// Copyright (c) 2018 Evgeny Shulgin | |||||
// Copyright (c) 2019 Andrey Semashev | |||||
// | |||||
// Distributed under the Boost Software License, Version 1.0. | |||||
// (See accompanying file LICENSE_1_0.txt or copy at | |||||
// http://www.boost.org/LICENSE_1_0.txt) | |||||
// | |||||
// ----------------------------------------------------------- | |||||
#ifndef BOOST_DETAIL_DYNAMIC_BITSET_HPP | |||||
#define BOOST_DETAIL_DYNAMIC_BITSET_HPP | |||||
#include <memory> | |||||
#include <cstddef> | |||||
#include "boost/config.hpp" | |||||
#include "boost/detail/workaround.hpp" | |||||
#if ((defined(BOOST_MSVC) && (BOOST_MSVC >= 1600)) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64)) | |||||
#include <intrin.h> | |||||
#endif | |||||
namespace boost { | |||||
namespace detail { | |||||
namespace dynamic_bitset_impl { | |||||
// Gives (read-)access to the object representation | |||||
// of an object of type T (3.9p4). CANNOT be used | |||||
// on a base sub-object | |||||
// | |||||
template <typename T> | |||||
inline const unsigned char * object_representation (T* p) | |||||
{ | |||||
return static_cast<const unsigned char *>(static_cast<const void *>(p)); | |||||
} | |||||
template<typename T, int amount, int width /* = default */> | |||||
struct shifter | |||||
{ | |||||
static void left_shift(T & v) { | |||||
amount >= width ? (v = 0) | |||||
: (v >>= BOOST_DYNAMIC_BITSET_WRAP_CONSTANT(amount)); | |||||
} | |||||
}; | |||||
// ------- count function implementation -------------- | |||||
typedef unsigned char byte_type; | |||||
// These two entities | |||||
// | |||||
// enum mode { access_by_bytes, access_by_blocks }; | |||||
// template <mode> struct mode_to_type {}; | |||||
// | |||||
// were removed, since the regression logs (as of 24 Aug 2008) | |||||
// showed that several compilers had troubles with recognizing | |||||
// | |||||
// const mode m = access_by_bytes | |||||
// | |||||
// as a constant expression | |||||
// | |||||
// * So, we'll use bool, instead of enum *. | |||||
// | |||||
template <bool value> | |||||
struct value_to_type | |||||
{ | |||||
value_to_type() {} | |||||
}; | |||||
const bool access_by_bytes = true; | |||||
const bool access_by_blocks = false; | |||||
// the table: wrapped in a class template, so | |||||
// that it is only instantiated if/when needed | |||||
// | |||||
template <bool dummy_name = true> | |||||
struct count_table { static const byte_type table[]; }; | |||||
template <> | |||||
struct count_table<false> { /* no table */ }; | |||||
const unsigned int table_width = 8; | |||||
template <bool b> | |||||
const byte_type count_table<b>::table[] = | |||||
{ | |||||
// Automatically generated by GPTableGen.exe v.1.0 | |||||
// | |||||
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, | |||||
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, | |||||
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, | |||||
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, | |||||
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, | |||||
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, | |||||
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, | |||||
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 | |||||
}; | |||||
// Some platforms have fast popcount operation, that allow us to implement | |||||
// counting bits much more efficiently | |||||
// | |||||
template <typename ValueType> | |||||
BOOST_FORCEINLINE std::size_t popcount(ValueType value) BOOST_NOEXCEPT | |||||
{ | |||||
std::size_t num = 0u; | |||||
while (value) { | |||||
num += count_table<>::table[value & ((1u<<table_width) - 1)]; | |||||
value >>= table_width; | |||||
} | |||||
return num; | |||||
} | |||||
#if (((defined(BOOST_MSVC) && (BOOST_MSVC >= 1600)) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64))) \ | |||||
&& (defined(__POPCNT__) || defined(__AVX__)) | |||||
template <> | |||||
BOOST_FORCEINLINE std::size_t popcount<unsigned short>(unsigned short value) BOOST_NOEXCEPT | |||||
{ | |||||
return static_cast<std::size_t>(__popcnt16(value)); | |||||
} | |||||
template <> | |||||
BOOST_FORCEINLINE std::size_t popcount<unsigned int>(unsigned int value) BOOST_NOEXCEPT | |||||
{ | |||||
return static_cast<std::size_t>(__popcnt(value)); | |||||
} | |||||
template <> | |||||
BOOST_FORCEINLINE std::size_t popcount<unsigned __int64>(unsigned __int64 value) BOOST_NOEXCEPT | |||||
{ | |||||
#if defined(_M_X64) | |||||
return static_cast<std::size_t>(__popcnt64(value)); | |||||
#else | |||||
return static_cast<std::size_t>(__popcnt(static_cast< unsigned int >(value))) + static_cast<std::size_t>(__popcnt(static_cast< unsigned int >(value >> 32))); | |||||
#endif | |||||
} | |||||
#elif defined(BOOST_GCC) || defined(__clang__) || (defined(BOOST_INTEL) && defined(__GNUC__)) | |||||
// Note: gcc builtins are implemented by compiler runtime when the target CPU may not support the necessary instructions | |||||
template <> | |||||
BOOST_FORCEINLINE std::size_t popcount<unsigned short>(unsigned short value) BOOST_NOEXCEPT | |||||
{ | |||||
return static_cast<unsigned int>(__builtin_popcount(static_cast<unsigned int>(value))); | |||||
} | |||||
template <> | |||||
BOOST_FORCEINLINE std::size_t popcount<unsigned int>(unsigned int value) BOOST_NOEXCEPT | |||||
{ | |||||
return static_cast<unsigned int>(__builtin_popcount(value)); | |||||
} | |||||
template <> | |||||
BOOST_FORCEINLINE std::size_t popcount<unsigned long>(unsigned long value) BOOST_NOEXCEPT | |||||
{ | |||||
return static_cast<unsigned int>(__builtin_popcountl(value)); | |||||
} | |||||
template <> | |||||
BOOST_FORCEINLINE std::size_t popcount<boost::ulong_long_type>(boost::ulong_long_type value) BOOST_NOEXCEPT | |||||
{ | |||||
return static_cast<unsigned int>(__builtin_popcountll(value)); | |||||
} | |||||
#endif | |||||
// overload for access by blocks | |||||
// | |||||
template <typename Iterator, typename ValueType> | |||||
inline std::size_t do_count(Iterator first, std::size_t length, ValueType, | |||||
value_to_type<access_by_blocks>*) | |||||
{ | |||||
std::size_t num1 = 0u, num2 = 0u; | |||||
while (length >= 2u) { | |||||
num1 += popcount<ValueType>(*first); | |||||
++first; | |||||
num2 += popcount<ValueType>(*first); | |||||
++first; | |||||
length -= 2u; | |||||
} | |||||
if (length > 0u) | |||||
num1 += popcount<ValueType>(*first); | |||||
return num1 + num2; | |||||
} | |||||
// overload for access by bytes | |||||
// | |||||
template <typename Iterator> | |||||
inline std::size_t do_count(Iterator first, std::size_t length, | |||||
int /*dummy param*/, | |||||
value_to_type<access_by_bytes>*) | |||||
{ | |||||
if (length > 0u) { | |||||
const byte_type* p = object_representation(&*first); | |||||
length *= sizeof(*first); | |||||
return do_count(p, length, static_cast<byte_type>(0u), | |||||
static_cast< value_to_type<access_by_blocks>* >(0)); | |||||
} | |||||
return 0u; | |||||
} | |||||
// ------------------------------------------------------- | |||||
// Some library implementations simply return a dummy | |||||
// value such as | |||||
// | |||||
// size_type(-1) / sizeof(T) | |||||
// | |||||
// from vector<>::max_size. This tries to get more | |||||
// meaningful info. | |||||
// | |||||
template <typename T> | |||||
inline typename T::size_type vector_max_size_workaround(const T & v) | |||||
BOOST_NOEXCEPT | |||||
{ | |||||
typedef typename T::allocator_type allocator_type; | |||||
const allocator_type& alloc = v.get_allocator(); | |||||
#if !defined(BOOST_NO_CXX11_ALLOCATOR) | |||||
typedef std::allocator_traits<allocator_type> allocator_traits; | |||||
const typename allocator_traits::size_type alloc_max = | |||||
allocator_traits::max_size(alloc); | |||||
#else | |||||
const typename allocator_type::size_type alloc_max = alloc.max_size(); | |||||
#endif | |||||
const typename T::size_type container_max = v.max_size(); | |||||
return alloc_max < container_max ? alloc_max : container_max; | |||||
} | |||||
// for static_asserts | |||||
template <typename T> | |||||
struct allowed_block_type { | |||||
enum { value = T(-1) > 0 }; // ensure T has no sign | |||||
}; | |||||
template <> | |||||
struct allowed_block_type<bool> { | |||||
enum { value = false }; | |||||
}; | |||||
template <typename T> | |||||
struct is_numeric { | |||||
enum { value = false }; | |||||
}; | |||||
# define BOOST_dynamic_bitset_is_numeric(x) \ | |||||
template<> \ | |||||
struct is_numeric< x > { \ | |||||
enum { value = true }; \ | |||||
} /**/ | |||||
BOOST_dynamic_bitset_is_numeric(bool); | |||||
BOOST_dynamic_bitset_is_numeric(char); | |||||
#if !defined(BOOST_NO_INTRINSIC_WCHAR_T) | |||||
BOOST_dynamic_bitset_is_numeric(wchar_t); | |||||
#endif | |||||
BOOST_dynamic_bitset_is_numeric(signed char); | |||||
BOOST_dynamic_bitset_is_numeric(short int); | |||||
BOOST_dynamic_bitset_is_numeric(int); | |||||
BOOST_dynamic_bitset_is_numeric(long int); | |||||
BOOST_dynamic_bitset_is_numeric(unsigned char); | |||||
BOOST_dynamic_bitset_is_numeric(unsigned short); | |||||
BOOST_dynamic_bitset_is_numeric(unsigned int); | |||||
BOOST_dynamic_bitset_is_numeric(unsigned long); | |||||
#if defined(BOOST_HAS_LONG_LONG) | |||||
BOOST_dynamic_bitset_is_numeric(::boost::long_long_type); | |||||
BOOST_dynamic_bitset_is_numeric(::boost::ulong_long_type); | |||||
#endif | |||||
// intentionally omitted | |||||
//BOOST_dynamic_bitset_is_numeric(float); | |||||
//BOOST_dynamic_bitset_is_numeric(double); | |||||
//BOOST_dynamic_bitset_is_numeric(long double); | |||||
#undef BOOST_dynamic_bitset_is_numeric | |||||
} // dynamic_bitset_impl | |||||
} // namespace detail | |||||
} // namespace boost | |||||
#endif // include guard | |||||
Wildfire Games · Phabricator