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