1 // -----------------------------------------------------------
2 //
3 //   Copyright (c) 2001-2002 Chuck Allison and Jeremy Siek
4 //        Copyright (c) 2003-2006, 2008 Gennaro Prota
5 //
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)
9 //
10 // -----------------------------------------------------------
11 
12 #ifndef BOOST_DETAIL_DYNAMIC_BITSET_HPP
13 #define BOOST_DETAIL_DYNAMIC_BITSET_HPP
14 
15 #include <cstddef>
16 #include "boost/config.hpp"
17 #include "boost/detail/workaround.hpp"
18 
19 
20 namespace boost {
21 
22   namespace detail {
23   namespace dynamic_bitset_impl {
24 
25     // Gives (read-)access to the object representation
26     // of an object of type T (3.9p4). CANNOT be used
27     // on a base sub-object
28     //
29     template <typename T>
object_representation(T * p)30     inline const unsigned char * object_representation (T* p)
31     {
32         return static_cast<const unsigned char *>(static_cast<const void *>(p));
33     }
34 
35     template<typename T, int amount, int width /* = default */>
36     struct shifter
37     {
left_shiftboost::detail::dynamic_bitset_impl::shifter38         static void left_shift(T & v) {
39             amount >= width ? (v = 0)
40                 : (v >>= BOOST_DYNAMIC_BITSET_WRAP_CONSTANT(amount));
41         }
42     };
43 
44     // ------- count function implementation --------------
45 
46     typedef unsigned char byte_type;
47 
48     // These two entities
49     //
50     //     enum mode { access_by_bytes, access_by_blocks };
51     //     template <mode> struct mode_to_type {};
52     //
53     // were removed, since the regression logs (as of 24 Aug 2008)
54     // showed that several compilers had troubles with recognizing
55     //
56     //   const mode m = access_by_bytes
57     //
58     // as a constant expression
59     //
60     // * So, we'll use bool, instead of enum *.
61     //
62     template <bool value>
63     struct value_to_type
64     {
value_to_typeboost::detail::dynamic_bitset_impl::value_to_type65         value_to_type() {}
66     };
67     const bool access_by_bytes = true;
68     const bool access_by_blocks = false;
69 
70 
71     // the table: wrapped in a class template, so
72     // that it is only instantiated if/when needed
73     //
74     template <bool dummy_name = true>
75     struct count_table { static const byte_type table[]; };
76 
77     template <>
78     struct count_table<false> { /* no table */ };
79 
80 
81      const unsigned int table_width = 8;
82      template <bool b>
83      const byte_type count_table<b>::table[] =
84      {
85        // Automatically generated by GPTableGen.exe v.1.0
86        //
87      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,
88      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,
89      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,
90      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,
91      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,
92      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,
93      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,
94      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
95      };
96 
97 
98      // overload for access by bytes
99      //
100 
101      template <typename Iterator>
do_count(Iterator first,std::size_t length,int,value_to_type<access_by_bytes> *)102      inline std::size_t do_count(Iterator first, std::size_t length,
103                                  int /*dummy param*/,
104                                  value_to_type<access_by_bytes>* )
105      {
106          std::size_t num = 0;
107          if (length)
108          {
109              const byte_type * p = object_representation(&*first);
110              length *= sizeof(*first);
111 
112               do {
113                  num += count_table<>::table[*p];
114                  ++p;
115                  --length;
116 
117              } while (length);
118          }
119 
120          return num;
121      }
122 
123 
124      // overload for access by blocks
125      //
126      template <typename Iterator, typename ValueType>
do_count(Iterator first,std::size_t length,ValueType,value_to_type<access_by_blocks> *)127      inline std::size_t do_count(Iterator first, std::size_t length, ValueType,
128                                  value_to_type<access_by_blocks>*)
129      {
130          std::size_t num = 0;
131          while (length){
132 
133              ValueType value = *first;
134              while (value) {
135                  num += count_table<>::table[value & ((1u<<table_width) - 1)];
136                  value >>= table_width;
137              }
138 
139              ++first;
140              --length;
141          }
142 
143          return num;
144      }
145 
146     // -------------------------------------------------------
147 
148 
149     // Some library implementations simply return a dummy
150     // value such as
151     //
152     //   size_type(-1) / sizeof(T)
153     //
154     // from vector<>::max_size. This tries to get more
155     // meaningful info.
156     //
157     template <typename T>
vector_max_size_workaround(const T & v)158     typename T::size_type vector_max_size_workaround(const T & v) {
159 
160       typedef typename T::allocator_type allocator_type;
161 
162       const typename allocator_type::size_type alloc_max =
163                                                   v.get_allocator().max_size();
164       const typename T::size_type container_max = v.max_size();
165 
166       return alloc_max < container_max?
167                     alloc_max :
168                     container_max;
169     }
170 
171     // for static_asserts
172     template <typename T>
173     struct allowed_block_type {
174         enum { value = T(-1) > 0 }; // ensure T has no sign
175     };
176 
177     template <>
178     struct allowed_block_type<bool> {
179         enum { value = false };
180     };
181 
182 
183     template <typename T>
184     struct is_numeric {
185         enum { value = false };
186     };
187 
188 #   define BOOST_dynamic_bitset_is_numeric(x)       \
189                 template<>                          \
190                 struct is_numeric< x > {            \
191                     enum { value = true };          \
192                 }                                /**/
193 
194     BOOST_dynamic_bitset_is_numeric(bool);
195     BOOST_dynamic_bitset_is_numeric(char);
196 
197 #if !defined(BOOST_NO_INTRINSIC_WCHAR_T)
198     BOOST_dynamic_bitset_is_numeric(wchar_t);
199 #endif
200 
201     BOOST_dynamic_bitset_is_numeric(signed char);
202     BOOST_dynamic_bitset_is_numeric(short int);
203     BOOST_dynamic_bitset_is_numeric(int);
204     BOOST_dynamic_bitset_is_numeric(long int);
205 
206     BOOST_dynamic_bitset_is_numeric(unsigned char);
207     BOOST_dynamic_bitset_is_numeric(unsigned short);
208     BOOST_dynamic_bitset_is_numeric(unsigned int);
209     BOOST_dynamic_bitset_is_numeric(unsigned long);
210 
211 #if defined(BOOST_HAS_LONG_LONG)
212     BOOST_dynamic_bitset_is_numeric(::boost::long_long_type);
213     BOOST_dynamic_bitset_is_numeric(::boost::ulong_long_type);
214 #endif
215 
216     // intentionally omitted
217     //BOOST_dynamic_bitset_is_numeric(float);
218     //BOOST_dynamic_bitset_is_numeric(double);
219     //BOOST_dynamic_bitset_is_numeric(long double);
220 
221 #undef BOOST_dynamic_bitset_is_numeric
222 
223   } // dynamic_bitset_impl
224   } // namespace detail
225 
226 } // namespace boost
227 
228 #endif // include guard
229 
230