// ----------------------------------------------------------- | |
// | |
// Copyright (c) 2001-2002 Chuck Allison and Jeremy Siek | |
// Copyright (c) 2003-2006, 2008 Gennaro Prota | |
// | |
// 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 <cstddef> | |
#include "boost/config.hpp" | |
#include "boost/detail/workaround.hpp" | |
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 | |
}; | |
// 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>* ) | |
{ | |
std::size_t num = 0; | |
if (length) | |
{ | |
const byte_type * p = object_representation(&*first); | |
length *= sizeof(*first); | |
do { | |
num += count_table<>::table[*p]; | |
++p; | |
--length; | |
} while (length); | |
} | |
return num; | |
} | |
// 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 num = 0; | |
while (length){ | |
ValueType value = *first; | |
while (value) { | |
num += count_table<>::table[value & ((1u<<table_width) - 1)]; | |
value >>= table_width; | |
} | |
++first; | |
--length; | |
} | |
return num; | |
} | |
// ------------------------------------------------------- | |
// 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> | |
typename T::size_type vector_max_size_workaround(const T & v) { | |
typedef typename T::allocator_type allocator_type; | |
const typename allocator_type::size_type alloc_max = | |
v.get_allocator().max_size(); | |
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 | |