1 #ifndef libjmmcg_core_bitfield_map_hpp
2 #define libjmmcg_core_bitfield_map_hpp
3 /******************************************************************************
4 ** $Header: svn+ssh://jmmcg@svn.code.sf.net/p/libjmmcg/code/trunk/libjmmcg/core/bitfield_map.hpp 2150 2017-09-16 16:35:01Z jmmcg $
5 **
6 ** Copyright (c) 2014 by J.M.McGuiness, coder@hussar.me.uk
7 **
8 ** This library is free software; you can redistribute it and/or
9 ** modify it under the terms of the GNU Lesser General Public
10 ** License as published by the Free Software Foundation; either
11 ** version 2.1 of the License, or (at your option) any later version.
12 **
13 ** This library is distributed in the hope that it will be useful,
14 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
15 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 ** Lesser General Public License for more details.
17 **
18 ** You should have received a copy of the GNU Lesser General Public
19 ** License along with this library; if not, write to the Free Software
20 ** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
21 */
22
23 #include "bit_fiddling.hpp"
24 #include "count_setbits.hpp"
25 #include "memops.hpp"
26 #include "non_copyable.hpp"
27
28 #include <boost/mpl/accumulate.hpp>
29 #include <boost/mpl/assert.hpp>
30 #include <boost/mpl/at.hpp>
31 #include <boost/mpl/begin.hpp>
32 #include <boost/mpl/deref.hpp>
33 #include <boost/mpl/empty.hpp>
34 #include <boost/mpl/find_if.hpp>
35 #include <boost/mpl/int.hpp>
36 #include <boost/mpl/next.hpp>
37 #include <boost/mpl/not.hpp>
38 #include <boost/mpl/placeholders.hpp>
39 #include <boost/mpl/plus.hpp>
40 #include <boost/mpl/size.hpp>
41 #include <boost/mpl/sizeof.hpp>
42 #include <boost/mpl/transform_view.hpp>
43
44 #include <cassert>
45 #include <limits>
46 #include <cstdint>
47 #include <sstream>
48 #include <stdexcept>
49 #include <type_traits>
50
51 namespace jmmcg {
52
53 struct a_zero_sized_class {};
54
55 namespace private_ {
56
57 /**
58 Avoid sizeof(void) warnings, give it a size of zero.
59 */
60 template<class T>
61 struct give_void_a_size_of {
62 enum : std::size_t {
63 value=sizeof(T)
64 };
65 };
66 template<>
67 struct give_void_a_size_of<void> {
68 enum : std::size_t {
69 value=std::size_t()
70 };
71 };
72 template<>
73 struct give_void_a_size_of<a_zero_sized_class> {
74 enum : std::size_t {
75 value=std::size_t()
76 };
77 };
78
79 }
80
81 /// This container is an associative collection of types. The domain is a bit-map of the mapped_types that are selected in the range.
82 /**
83 This container packs a selection of objects of the types that are given in mapped_types into an internal buffer of contiguous memory. If few types are selected, then the size() returns much less than the size of the object (which must be large enough to holds all of the mapped_types). It could be useful for passing assorted large mapped_types along a slow network link, when, usually, not all are needed.
84 Note that the types placed in mapped_types must be able to support arbitrary alignment - no guarantee of correct alignment is made by this class. These types are packed into the internal buffer such that there is no padding used, hence no guarantee of correct alignment. This restriction implies that only PODs are likely to be supported, in general.
85 */
86 template<
87 class BFSM,
88 std::size_t BFSz=sizeof(typename std::underlying_type<typename boost::mpl::deref<typename boost::mpl::begin<BFSM>::type>::type::first::value_type>::type)
89 >
90 class bitfield_map {
91 public:
92 using key_type=uint64_t;
93 using size_type=std::size_t;
94 using mapped_types=BFSM; ///< The range of mapped-types that may be selected by the domain. This range is a collection that is indexed by the unique enum-tag of the range.
95 using bitfields_tags_type=typename boost::mpl::deref<typename boost::mpl::begin<mapped_types>::type>::type::first::value_type; ///< The range of enum-tags used to indicate the requested element in the mapped_types range.
96 using underlying_key_type=typename std::underlying_type<bitfields_tags_type>::type; ///< The underlying type of the domain enum.
97
98 /**
99 Make sure the funky mpl actually finds something that is POD-like so could be an enumeration...
100 */
101 BOOST_MPL_ASSERT((std::is_pod<bitfields_tags_type>));
102 /**
103 Make sure the funky mpl actually finds something that is integral so could be an enumeration...
104 */
105 BOOST_MPL_ASSERT((std::is_integral<typename std::underlying_type<bitfields_tags_type>::type>));
106
107 enum : std::size_t {
108 range_mapped_types_size=boost::mpl::accumulate<
109 boost::mpl::transform_view<mapped_types, boost::mpl::sizeof_<boost::mpl::second<boost::mpl::_1>>>,
110 boost::mpl::int_<0u>::type,
111 boost::mpl::plus<boost::mpl::_1, boost::mpl::_2>
112 >::type::value, ///< The sum of the sizes of the types in mapped_types.
113 bitfields_size=BFSz, ///< The number of 8-bit bytes that the range of enum-tags should occupy. By default this is the sizeof(underlying_key_type). Note that enums require the underlying type to be an integral type, so this option allows for non-integral "underlying types". Also note that if this option is used it is the responsibility of the user to ensure that the number of bits in the underlying type can accommodate the number of enum-tags in the range.
114 mapped_types_size=boost::mpl::size<mapped_types>::value
115 };
116
117 using raw_mapped_data_t=std::array<uint8_t, range_mapped_types_size>;
118
119 private:
120 using raw_key_type_t=std::array<uint8_t, bitfields_size>;
121
122 public:
123 enum : bool {
124 all_pod=std::is_same<
125 typename boost::mpl::find_if<
126 mapped_types,
127 boost::mpl::not_<std::is_pod<boost::mpl::second<boost::mpl::_1>>>
128 >::type,
129 typename boost::mpl::end<mapped_types>::type
130 >::type::value ///< True if all of the range mapped_types in the container are PODs otherwise false.
131 };
132
133 BOOST_MPL_ASSERT_RELATION(sizeof(bitfields_tags_type), <=, sizeof(key_type));
134 BOOST_MPL_ASSERT_RELATION(sizeof(underlying_key_type), ==, sizeof(bitfields_tags_type));
135 BOOST_MPL_ASSERT_RELATION(range_mapped_types_size, >, 0);
136 BOOST_MPL_ASSERT_RELATION(boost::mpl::empty<mapped_types>::value, !=, true);
137
138 /// Default-construct an empty container.
139 /**
140 Algorithmic complexity: O(1)
141 Post-condition: empty()==true.
142 */
143 constexpr bitfield_map() noexcept(true) FORCE_INLINE;
144 /// Bit-wise copy the contents of the argument into the constructed container, out of the argument.
145 /**
146 Algorithmic complexity: O(sizeof(range of mapped_types))
147 Post-condition: bm.empty()==true.
148 */
149 constexpr bitfield_map(bitfield_map const &) noexcept(true) FORCE_INLINE;
150 /**
151 Algorithmic complexity: O(sizeof(range of mapped_types))
152 Post-condition: bm.empty()==true.
153 */
154 constexpr bitfield_map(bitfield_map &&) noexcept(true) FORCE_INLINE;
155 /**
156 Algorithmic complexity: POD: O(1) otherwise O(sizeof(key_type)^2)
157
158 \see clear()
159 */
160 ~bitfield_map() noexcept(true) FORCE_INLINE;
161
162 /// Bit-wise swap the contents of the container with that of the argument.
163 /**
164 Algorithmic complexity: O(sizeof(range of mapped_types))
165
166 \see swap()
167 */
168 constexpr bitfield_map &operator=(bitfield_map &&) noexcept(true) FORCE_INLINE;
169
170 /// Indicate if there are any elements selected in the mapped_types.
171 /**
172 Algorithmic complexity: O(1)
173 Invariant: emply() iff size()==0
174
175 \return true if no types have been selected in the mapped_types, otherwise false.
176 */
177 constexpr bool empty() const noexcept(true) FORCE_INLINE;
178
179 /// Indicate the total size of any elements selected in the mapped_types, including the size of the domain bitfield.
180 /**
181 Algorithmic complexity: O(sizeof(key_type))
182 Invariant: size()<=max_size()
183
184 \return The size, in bytes, of the types have been selected in the mapped_types, otherwise 0, always less than or equal to the sum of the sizes of the types in mapped_types, range_mapped_types_size.
185
186 \see max_size()
187 */
188 constexpr size_type size() const noexcept(true) FORCE_INLINE;
189
190 /// Indicate the maximum size of all elements that can be selected in the mapped_types, including the size of the domain bitfield.
191 /**
192 Algorithmic complexity: O(1)
193 Invariant: size()<=max_size()
194
195 \return At least the size, in bytes, of all of the types have can be selected in the mapped_types.
196
197 \see size()
198 */
199 static constexpr size_type max_size() noexcept(true) FORCE_INLINE;
200
201 /// Erase each enabled mapped_types selected in the key_type.
202 /**
203 Algorithmic complexity: POD: O(1) otherwise O(sizeof(key_type)^2)
204 Post-condition: empty()==true.
205 */
206 void constexpr clear() noexcept(true) FORCE_INLINE;
207
208 /// Perform a range-checked selection of the requested element.
209 /**
210 Algorithmic complexity: O(sizeof(key_type))
211 Pre-condition: empty()==false.
212
213 \return Return a reference to the enabled SelectedField in the mapped_types, otherwise throw a std::range_error exception..
214 */
215 template<
216 bitfields_tags_type SelectedField,
217 class AsType=typename std::integral_constant<bitfields_tags_type, SelectedField>::type,
218 class Ret=typename boost::mpl::at<mapped_types, AsType>::type
219 >
220 constexpr const Ret &at() const noexcept(false) FORCE_INLINE;
221 /// Perform a range-checked selection of the requested element.
222 /**
223 Algorithmic complexity: O(sizeof(key_type))
224 Pre-condition: empty()==false.
225
226 \return Return a reference to the enabled SelectedField in the mapped_types, otherwise throw a std::range_error exception..
227 */
228 template<
229 bitfields_tags_type SelectedField,
230 class AsType=typename std::integral_constant<bitfields_tags_type, SelectedField>::type,
231 class Ret=typename boost::mpl::at<mapped_types, AsType>::type
232 >
233 constexpr Ret &at() noexcept(false) FORCE_INLINE;
234
235 /// Remove and delete the SelectedField element, if enabled, from the mapped_types range.
236 /**
237 Note: this is not a generic erase, items should only be erased from the end of the collection, otherwise undefined behaviour will result. This should really be considered a pop_back() operation, where the end iterator is manually specified. Not ideal. No compaction of the mapped_types is performed after an erase, so if holes were left, this would cause the at() operations to behave incorrectly.
238 Algorithmic complexity: POD: O(1) otherwise O(sizeof(key_type))
239 Pre-condition: SelectedField is the last enabled bit in the key_type.
240
241 \see push_back()
242 */
243 template<
244 bitfields_tags_type SelectedField,
245 class AsType=typename std::integral_constant<bitfields_tags_type, SelectedField>::type,
246 class Ret=typename boost::mpl::at<mapped_types, AsType>::type
247 >
248 void erase() noexcept(true) FORCE_INLINE;
249
250 /// Find if the SelectedField is enabled in the key_type,
251 /**
252 Algorithmic complexity: O(1)
253
254 \return True if the SelectedField is enabled in the key_type, otherwise false.
255 */
256 template<bitfields_tags_type SelectedField>
257 bool find() const noexcept(true) FORCE_INLINE;
258
259 /// Enable the SelectedField in the key_type, and initialise the appropriate element in the mapped_types, if necessary,
260 /**
261 Note: This only works going from smaller to larger tags in the key_type, one must not insert in the middle, otherwise this may result in undefined behaviour. This is because of the internally-computed offsets into the range of mapped_types. Hence one must not insert randomly: it is likely that existing contents will be incorrectly overwritten, also leading to undefined behaviour.
262 Algorithmic complexity: O(sizeof(key_type))
263 Post-condition: empty()==false.
264
265 \return A reference to the initialised element in the mapped_types.
266 */
267 template<
268 bitfields_tags_type SelectedField,
269 class AsType=typename std::integral_constant<bitfields_tags_type, SelectedField>::type,
270 class Arg=typename boost::mpl::at<mapped_types, AsType>::type
271 >
272 void push_back(Arg const &) noexcept(false) FORCE_INLINE;
273
274 /// Bit-wise swap the contents of the container with that of the argument.
275 /**
276 Algorithmic complexity: O(sizeof(range of mapped_types))
277 */
278 void constexpr swap(bitfield_map &) noexcept(true) FORCE_INLINE;
279
280 private:
281 /**
282 A hack to convert non-integral underlying types to integral types to allow the bit-wise operators to work.
283 */
284 union converter {
285 key_type conv_bfs;
286 raw_key_type_t bfs; ///< Here's hoping this is LSB-justified in the word, otherwise we are b'gg'r'd...
287 };
288 key_type constexpr convert_to_biggest_integral_type() const noexcept(true);
289
290 raw_key_type_t bfs;
291 raw_mapped_data_t raw_mapped_data;
292 }__attribute__((packed));
293
294 }
295
296 #include "bitfield_map_impl.hpp"
297
298 #endif