williamr@2: // -------------------------------------------------- williamr@2: // williamr@2: // (C) Copyright Chuck Allison and Jeremy Siek 2001 - 2002. williamr@2: // (C) Copyright Gennaro Prota 2003 - 2004. williamr@2: // williamr@2: // Distributed under the Boost Software License, Version 1.0. williamr@2: // (See accompanying file LICENSE_1_0.txt or copy at williamr@2: // http://www.boost.org/LICENSE_1_0.txt) williamr@2: // williamr@2: // ----------------------------------------------------------- williamr@2: williamr@2: // See http://www.boost.org/libs/dynamic_bitset for documentation. williamr@2: williamr@2: williamr@4: #ifndef BOOST_DETAIL_DYNAMIC_BITSET_HPP williamr@4: #define BOOST_DETAIL_DYNAMIC_BITSET_HPP williamr@2: williamr@4: #include // for std::size_t williamr@4: #include "boost/config.hpp" williamr@4: #include "boost/detail/workaround.hpp" williamr@4: //#include "boost/static_assert.hpp" // gps williamr@2: williamr@2: williamr@2: namespace boost { williamr@2: williamr@4: namespace detail { williamr@2: williamr@4: // Gives (read-)access to the object representation williamr@4: // of an object of type T (3.9p4). CANNOT be used williamr@4: // on a base sub-object williamr@4: // williamr@4: template williamr@4: inline const unsigned char * object_representation (T* p) williamr@4: { williamr@4: return static_cast(static_cast(p)); williamr@4: } williamr@2: williamr@2: williamr@4: // ------- count function implementation -------------- williamr@2: williamr@4: namespace dynamic_bitset_count_impl { williamr@2: williamr@4: typedef unsigned char byte_type; williamr@2: williamr@4: enum mode { access_by_bytes, access_by_blocks }; williamr@2: williamr@4: template struct mode_to_type {}; williamr@2: williamr@4: // the table: wrapped in a class template, so williamr@4: // that it is only instantiated if/when needed williamr@2: // williamr@4: template williamr@4: struct count_table { static const byte_type table[]; }; williamr@2: williamr@4: template <> williamr@4: struct count_table { /* no table */ }; williamr@2: williamr@2: williamr@4: const unsigned int table_width = 8; williamr@4: template williamr@4: const byte_type count_table::table[] = williamr@4: { williamr@4: // Automatically generated by GPTableGen.exe v.1.0 williamr@4: // williamr@4: 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, williamr@4: 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, williamr@4: 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, williamr@4: 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, williamr@4: 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, williamr@4: 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, williamr@4: 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, williamr@4: 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 williamr@4: }; williamr@2: williamr@2: williamr@4: // overload for access by bytes williamr@4: // williamr@2: williamr@4: template williamr@4: inline std::size_t do_count(Iterator first, std::size_t length, williamr@4: int /*dummy param*/, williamr@4: mode_to_type* ) williamr@4: { williamr@4: std::size_t num = 0; williamr@4: if (length) williamr@4: { williamr@4: const byte_type * p = object_representation(&*first); williamr@4: length *= sizeof(*first); williamr@2: williamr@4: do { williamr@4: num += count_table<>::table[*p]; williamr@4: ++p; williamr@4: --length; williamr@2: williamr@4: } while (length); williamr@4: } williamr@2: williamr@4: return num; williamr@4: } williamr@2: williamr@2: williamr@4: // overload for access by blocks williamr@4: // williamr@4: template williamr@4: inline std::size_t do_count(Iterator first, std::size_t length, ValueType, williamr@4: mode_to_type*) williamr@4: { williamr@4: std::size_t num = 0; williamr@4: while (length){ williamr@4: williamr@4: ValueType value = *first; williamr@4: while (value) { williamr@4: num += count_table<>::table[value & ((1u<>= table_width; williamr@4: } williamr@4: williamr@4: ++first; williamr@4: --length; williamr@4: } williamr@4: williamr@4: return num; williamr@4: } williamr@4: williamr@4: williamr@4: } // dynamic_bitset_count_impl williamr@4: // ------------------------------------------------------- williamr@4: williamr@4: williamr@4: // Some library implementations simply return a dummy williamr@4: // value such as williamr@4: // williamr@4: // size_type(-1) / sizeof(T) williamr@4: // williamr@4: // from vector<>::max_size. This tries to get out more williamr@4: // meaningful info. williamr@4: // williamr@4: template williamr@4: typename T::size_type vector_max_size_workaround(const T & v) { williamr@4: williamr@4: typedef typename T::allocator_type allocator_type; williamr@4: williamr@4: const typename allocator_type::size_type alloc_max = williamr@4: v.get_allocator().max_size(); williamr@4: const typename T::size_type container_max = v.max_size(); williamr@4: williamr@4: return alloc_max < container_max? williamr@4: alloc_max : williamr@4: container_max; williamr@4: } williamr@4: williamr@4: // for static_asserts williamr@4: template williamr@4: struct dynamic_bitset_allowed_block_type { williamr@4: enum { value = (T(-1) > 0) }; // ensure T has no sign williamr@2: }; williamr@2: williamr@4: template <> williamr@4: struct dynamic_bitset_allowed_block_type { williamr@4: enum { value = false }; williamr@2: }; williamr@2: williamr@2: williamr@4: } // namespace detail williamr@2: williamr@2: } // namespace boost williamr@2: williamr@2: #endif // include guard williamr@2: