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