1 // --------------------------------------------------
3 // (C) Copyright Chuck Allison and Jeremy Siek 2001 - 2002.
4 // (C) Copyright Gennaro Prota 2003 - 2004.
6 // Distributed under the Boost Software License, Version 1.0.
7 // (See accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
10 // -----------------------------------------------------------
12 // See http://www.boost.org/libs/dynamic_bitset for documentation.
15 #ifndef BOOST_DETAIL_DYNAMIC_BITSET_HPP
16 #define BOOST_DETAIL_DYNAMIC_BITSET_HPP
18 #include <cstddef> // for std::size_t
19 #include "boost/config.hpp"
20 #include "boost/detail/workaround.hpp"
21 //#include "boost/static_assert.hpp" // gps
28 // Gives (read-)access to the object representation
29 // of an object of type T (3.9p4). CANNOT be used
30 // on a base sub-object
33 inline const unsigned char * object_representation (T* p)
35 return static_cast<const unsigned char *>(static_cast<const void *>(p));
39 // ------- count function implementation --------------
41 namespace dynamic_bitset_count_impl {
43 typedef unsigned char byte_type;
45 enum mode { access_by_bytes, access_by_blocks };
47 template <mode> struct mode_to_type {};
49 // the table: wrapped in a class template, so
50 // that it is only instantiated if/when needed
52 template <bool dummy_name = true>
53 struct count_table { static const byte_type table[]; };
56 struct count_table<false> { /* no table */ };
59 const unsigned int table_width = 8;
61 const byte_type count_table<b>::table[] =
63 // Automatically generated by GPTableGen.exe v.1.0
65 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,
66 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,
67 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,
68 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,
69 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,
70 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,
71 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,
72 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
76 // overload for access by bytes
79 template <typename Iterator>
80 inline std::size_t do_count(Iterator first, std::size_t length,
82 mode_to_type<access_by_bytes>* )
87 const byte_type * p = object_representation(&*first);
88 length *= sizeof(*first);
91 num += count_table<>::table[*p];
102 // overload for access by blocks
104 template <typename Iterator, typename ValueType>
105 inline std::size_t do_count(Iterator first, std::size_t length, ValueType,
106 mode_to_type<access_by_blocks>*)
111 ValueType value = *first;
113 num += count_table<>::table[value & ((1u<<table_width) - 1)];
114 value >>= table_width;
125 } // dynamic_bitset_count_impl
126 // -------------------------------------------------------
129 // Some library implementations simply return a dummy
132 // size_type(-1) / sizeof(T)
134 // from vector<>::max_size. This tries to get out more
137 template <typename T>
138 typename T::size_type vector_max_size_workaround(const T & v) {
140 typedef typename T::allocator_type allocator_type;
142 const typename allocator_type::size_type alloc_max =
143 v.get_allocator().max_size();
144 const typename T::size_type container_max = v.max_size();
146 return alloc_max < container_max?
151 // for static_asserts
152 template <typename T>
153 struct dynamic_bitset_allowed_block_type {
154 enum { value = (T(-1) > 0) }; // ensure T has no sign
158 struct dynamic_bitset_allowed_block_type<bool> {
159 enum { value = false };
163 } // namespace detail
167 #endif // include guard