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