dynamic_bitset.hpp

Go to the documentation of this file.

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