Chris@16: // -----------------------------------------------------------
Chris@16: //
Chris@16: //   Copyright (c) 2001-2002 Chuck Allison and Jeremy Siek
Chris@16: //        Copyright (c) 2003-2006, 2008 Gennaro Prota
Chris@16: //
Chris@101: // Copyright (c) 2014 Glen Joseph Fernandes
Chris@101: // glenfe at live dot com
Chris@101: //
Chris@16: // Distributed under the Boost Software License, Version 1.0.
Chris@16: //    (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: //          http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //
Chris@16: // -----------------------------------------------------------
Chris@16: 
Chris@16: #ifndef BOOST_DETAIL_DYNAMIC_BITSET_HPP
Chris@16: #define BOOST_DETAIL_DYNAMIC_BITSET_HPP
Chris@16: 
Chris@101: #include <memory>
Chris@16: #include <cstddef>
Chris@16: #include "boost/config.hpp"
Chris@16: #include "boost/detail/workaround.hpp"
Chris@16: 
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   namespace detail {
Chris@16:   namespace dynamic_bitset_impl {
Chris@16: 
Chris@16:     // Gives (read-)access to the object representation
Chris@16:     // of an object of type T (3.9p4). CANNOT be used
Chris@16:     // on a base sub-object
Chris@16:     //
Chris@16:     template <typename T>
Chris@16:     inline const unsigned char * object_representation (T* p)
Chris@16:     {
Chris@16:         return static_cast<const unsigned char *>(static_cast<const void *>(p));
Chris@16:     }
Chris@16: 
Chris@16:     template<typename T, int amount, int width /* = default */>
Chris@16:     struct shifter
Chris@16:     {
Chris@16:         static void left_shift(T & v) {
Chris@16:             amount >= width ? (v = 0)
Chris@16:                 : (v >>= BOOST_DYNAMIC_BITSET_WRAP_CONSTANT(amount));
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     // ------- count function implementation --------------
Chris@16: 
Chris@16:     typedef unsigned char byte_type;
Chris@16: 
Chris@16:     // These two entities
Chris@16:     //
Chris@16:     //     enum mode { access_by_bytes, access_by_blocks };
Chris@16:     //     template <mode> struct mode_to_type {};
Chris@16:     //
Chris@16:     // were removed, since the regression logs (as of 24 Aug 2008)
Chris@16:     // showed that several compilers had troubles with recognizing
Chris@16:     //
Chris@16:     //   const mode m = access_by_bytes
Chris@16:     //
Chris@16:     // as a constant expression
Chris@16:     //
Chris@16:     // * So, we'll use bool, instead of enum *.
Chris@16:     //
Chris@16:     template <bool value>
Chris@16:     struct value_to_type
Chris@16:     {
Chris@16:         value_to_type() {}
Chris@16:     };
Chris@16:     const bool access_by_bytes = true;
Chris@16:     const bool access_by_blocks = false;
Chris@16: 
Chris@16: 
Chris@16:     // the table: wrapped in a class template, so
Chris@16:     // that it is only instantiated if/when needed
Chris@16:     //
Chris@16:     template <bool dummy_name = true>
Chris@16:     struct count_table { static const byte_type table[]; };
Chris@16: 
Chris@16:     template <>
Chris@16:     struct count_table<false> { /* no table */ };
Chris@16: 
Chris@16: 
Chris@16:      const unsigned int table_width = 8;
Chris@16:      template <bool b>
Chris@16:      const byte_type count_table<b>::table[] =
Chris@16:      {
Chris@16:        // Automatically generated by GPTableGen.exe v.1.0
Chris@16:        //
Chris@16:      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,
Chris@16:      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,
Chris@16:      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,
Chris@16:      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,
Chris@16:      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,
Chris@16:      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,
Chris@16:      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,
Chris@16:      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
Chris@16:      };
Chris@16: 
Chris@16: 
Chris@16:      // overload for access by bytes
Chris@16:      //
Chris@16: 
Chris@16:      template <typename Iterator>
Chris@16:      inline std::size_t do_count(Iterator first, std::size_t length,
Chris@16:                                  int /*dummy param*/,
Chris@16:                                  value_to_type<access_by_bytes>* )
Chris@16:      {
Chris@16:          std::size_t num = 0;
Chris@16:          if (length)
Chris@16:          {
Chris@16:              const byte_type * p = object_representation(&*first);
Chris@16:              length *= sizeof(*first);
Chris@16: 
Chris@16:               do {
Chris@16:                  num += count_table<>::table[*p];
Chris@16:                  ++p;
Chris@16:                  --length;
Chris@16: 
Chris@16:              } while (length);
Chris@16:          }
Chris@16: 
Chris@16:          return num;
Chris@16:      }
Chris@16: 
Chris@16: 
Chris@16:      // overload for access by blocks
Chris@16:      //
Chris@16:      template <typename Iterator, typename ValueType>
Chris@16:      inline std::size_t do_count(Iterator first, std::size_t length, ValueType,
Chris@16:                                  value_to_type<access_by_blocks>*)
Chris@16:      {
Chris@16:          std::size_t num = 0;
Chris@16:          while (length){
Chris@16: 
Chris@16:              ValueType value = *first;
Chris@16:              while (value) {
Chris@16:                  num += count_table<>::table[value & ((1u<<table_width) - 1)];
Chris@16:                  value >>= table_width;
Chris@16:              }
Chris@16: 
Chris@16:              ++first;
Chris@16:              --length;
Chris@16:          }
Chris@16: 
Chris@16:          return num;
Chris@16:      }
Chris@16: 
Chris@16:     // -------------------------------------------------------
Chris@16: 
Chris@16: 
Chris@16:     // Some library implementations simply return a dummy
Chris@16:     // value such as
Chris@16:     //
Chris@16:     //   size_type(-1) / sizeof(T)
Chris@16:     //
Chris@16:     // from vector<>::max_size. This tries to get more
Chris@16:     // meaningful info.
Chris@16:     //
Chris@16:     template <typename T>
Chris@101:     inline typename T::size_type vector_max_size_workaround(const T & v)
Chris@101:         BOOST_NOEXCEPT
Chris@101:     {
Chris@101:         typedef typename T::allocator_type allocator_type;
Chris@16: 
Chris@101:         const allocator_type& alloc = v.get_allocator();
Chris@16: 
Chris@101: #if !defined(BOOST_NO_CXX11_ALLOCATOR)
Chris@101:         typedef std::allocator_traits<allocator_type> allocator_traits;
Chris@16: 
Chris@101:         const typename allocator_traits::size_type alloc_max =
Chris@101:             allocator_traits::max_size(alloc);
Chris@101: #else
Chris@101:         const typename allocator_type::size_type alloc_max = alloc.max_size();
Chris@101: #endif
Chris@101: 
Chris@101:         const typename T::size_type container_max = v.max_size();
Chris@101: 
Chris@101:         return alloc_max < container_max ? alloc_max : container_max;
Chris@16:     }
Chris@16: 
Chris@16:     // for static_asserts
Chris@16:     template <typename T>
Chris@16:     struct allowed_block_type {
Chris@16:         enum { value = T(-1) > 0 }; // ensure T has no sign
Chris@16:     };
Chris@16: 
Chris@16:     template <>
Chris@16:     struct allowed_block_type<bool> {
Chris@16:         enum { value = false };
Chris@16:     };
Chris@16: 
Chris@16: 
Chris@16:     template <typename T>
Chris@16:     struct is_numeric {
Chris@16:         enum { value = false };
Chris@16:     };
Chris@16: 
Chris@16: #   define BOOST_dynamic_bitset_is_numeric(x)       \
Chris@16:                 template<>                          \
Chris@16:                 struct is_numeric< x > {            \
Chris@16:                     enum { value = true };          \
Chris@16:                 }                                /**/
Chris@16: 
Chris@16:     BOOST_dynamic_bitset_is_numeric(bool);
Chris@16:     BOOST_dynamic_bitset_is_numeric(char);
Chris@16: 
Chris@16: #if !defined(BOOST_NO_INTRINSIC_WCHAR_T)
Chris@16:     BOOST_dynamic_bitset_is_numeric(wchar_t);
Chris@16: #endif
Chris@16: 
Chris@16:     BOOST_dynamic_bitset_is_numeric(signed char);
Chris@16:     BOOST_dynamic_bitset_is_numeric(short int);
Chris@16:     BOOST_dynamic_bitset_is_numeric(int);
Chris@16:     BOOST_dynamic_bitset_is_numeric(long int);
Chris@16: 
Chris@16:     BOOST_dynamic_bitset_is_numeric(unsigned char);
Chris@16:     BOOST_dynamic_bitset_is_numeric(unsigned short);
Chris@16:     BOOST_dynamic_bitset_is_numeric(unsigned int);
Chris@16:     BOOST_dynamic_bitset_is_numeric(unsigned long);
Chris@16: 
Chris@16: #if defined(BOOST_HAS_LONG_LONG)
Chris@16:     BOOST_dynamic_bitset_is_numeric(::boost::long_long_type);
Chris@16:     BOOST_dynamic_bitset_is_numeric(::boost::ulong_long_type);
Chris@16: #endif
Chris@16: 
Chris@16:     // intentionally omitted
Chris@16:     //BOOST_dynamic_bitset_is_numeric(float);
Chris@16:     //BOOST_dynamic_bitset_is_numeric(double);
Chris@16:     //BOOST_dynamic_bitset_is_numeric(long double);
Chris@16: 
Chris@16: #undef BOOST_dynamic_bitset_is_numeric
Chris@16: 
Chris@16:   } // dynamic_bitset_impl
Chris@16:   } // namespace detail
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif // include guard
Chris@16: