| // ----------------------------------------------------------- |
| // |
| // 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 |
| |