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 <cstddef> // 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 <typename T>
williamr@4:     inline const unsigned char * object_representation (T* p)
williamr@4:     {
williamr@4:         return static_cast<const unsigned char *>(static_cast<const void *>(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 <mode> 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 <bool dummy_name = true>
williamr@4:     struct count_table { static const byte_type table[]; };
williamr@2: 
williamr@4:     template <>
williamr@4:     struct count_table<false> { /* no table */ };
williamr@2: 
williamr@2: 
williamr@4:      const unsigned int table_width = 8;
williamr@4:      template <bool b>
williamr@4:      const byte_type count_table<b>::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 <typename Iterator>
williamr@4:      inline std::size_t do_count(Iterator first, std::size_t length,
williamr@4:                                  int /*dummy param*/,
williamr@4:                                  mode_to_type<access_by_bytes>* )
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 <typename Iterator, typename ValueType>
williamr@4:      inline std::size_t do_count(Iterator first, std::size_t length, ValueType,
williamr@4:                                  mode_to_type<access_by_blocks>*)
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) - 1)];
williamr@4:                  value >>= 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 <typename T>
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 <typename T>
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<bool> {
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: