]>
Commit | Line | Data |
---|---|---|
1 | //---------------------------------------------------------------------------// | |
2 | // Copyright (c) 2013-2014 Kyle Lutz <kyle.r.lutz@gmail.com> | |
3 | // | |
4 | // Distributed under the Boost Software License, Version 1.0 | |
5 | // See accompanying file LICENSE_1_0.txt or copy at | |
6 | // http://www.boost.org/LICENSE_1_0.txt | |
7 | // | |
8 | // See http://boostorg.github.com/compute for more information. | |
9 | //---------------------------------------------------------------------------// | |
10 | ||
11 | #ifndef BOOST_COMPUTE_CONTAINER_DYNAMIC_BITSET_HPP | |
12 | #define BOOST_COMPUTE_CONTAINER_DYNAMIC_BITSET_HPP | |
13 | ||
14 | #include <boost/compute/lambda.hpp> | |
15 | #include <boost/compute/algorithm/any_of.hpp> | |
16 | #include <boost/compute/algorithm/fill.hpp> | |
17 | #include <boost/compute/algorithm/transform_reduce.hpp> | |
18 | #include <boost/compute/container/vector.hpp> | |
19 | #include <boost/compute/functional/integer.hpp> | |
20 | #include <boost/compute/types/fundamental.hpp> | |
21 | ||
22 | namespace boost { | |
23 | namespace compute { | |
24 | ||
25 | /// \class dynamic_bitset | |
26 | /// \brief The dynamic_bitset class contains a resizable bit array. | |
27 | /// | |
28 | /// For example, to create a dynamic-bitset with space for 1000 bits on the | |
29 | /// device: | |
30 | /// \code | |
31 | /// boost::compute::dynamic_bitset<> bits(1000, queue); | |
32 | /// \endcode | |
33 | /// | |
34 | /// The Boost.Compute \c dynamic_bitset class provides a STL-like API and is | |
35 | /// modeled after the \c boost::dynamic_bitset class from Boost. | |
36 | /// | |
37 | /// \see \ref vector "vector<T>" | |
38 | template<class Block = ulong_, class Alloc = buffer_allocator<Block> > | |
39 | class dynamic_bitset | |
40 | { | |
41 | public: | |
42 | typedef Block block_type; | |
43 | typedef Alloc allocator_type; | |
44 | typedef vector<Block, Alloc> container_type; | |
45 | typedef typename container_type::size_type size_type; | |
46 | ||
47 | BOOST_STATIC_CONSTANT(size_type, bits_per_block = sizeof(block_type) * CHAR_BIT); | |
48 | BOOST_STATIC_CONSTANT(size_type, npos = static_cast<size_type>(-1)); | |
49 | ||
50 | /// Creates a new dynamic bitset with storage for \p size bits. Initializes | |
51 | /// all bits to zero. | |
52 | dynamic_bitset(size_type size, command_queue &queue) | |
53 | : m_bits(size / sizeof(block_type), queue.get_context()), | |
54 | m_size(size) | |
55 | { | |
56 | // initialize all bits to zero | |
57 | reset(queue); | |
58 | } | |
59 | ||
60 | /// Creates a new dynamic bitset as a copy of \p other. | |
61 | dynamic_bitset(const dynamic_bitset &other) | |
62 | : m_bits(other.m_bits), | |
63 | m_size(other.m_size) | |
64 | { | |
65 | } | |
66 | ||
67 | /// Copies the data from \p other to \c *this. | |
68 | dynamic_bitset& operator=(const dynamic_bitset &other) | |
69 | { | |
70 | if(this != &other){ | |
71 | m_bits = other.m_bits; | |
72 | m_size = other.m_size; | |
73 | } | |
74 | ||
75 | return *this; | |
76 | } | |
77 | ||
78 | /// Destroys the dynamic bitset. | |
79 | ~dynamic_bitset() | |
80 | { | |
81 | } | |
82 | ||
83 | /// Returns the size of the dynamic bitset. | |
84 | size_type size() const | |
85 | { | |
86 | return m_size; | |
87 | } | |
88 | ||
89 | /// Returns the number of blocks to store the bits in the dynamic bitset. | |
90 | size_type num_blocks() const | |
91 | { | |
92 | return m_bits.size(); | |
93 | } | |
94 | ||
95 | /// Returns the maximum possible size for the dynamic bitset. | |
96 | size_type max_size() const | |
97 | { | |
98 | return m_bits.max_size() * bits_per_block; | |
99 | } | |
100 | ||
101 | /// Returns \c true if the dynamic bitset is empty (i.e. \c size() == \c 0). | |
102 | bool empty() const | |
103 | { | |
104 | return size() == 0; | |
105 | } | |
106 | ||
107 | /// Returns the number of set bits (i.e. '1') in the bitset. | |
108 | size_type count(command_queue &queue) const | |
109 | { | |
110 | ulong_ count = 0; | |
111 | transform_reduce( | |
112 | m_bits.begin(), | |
113 | m_bits.end(), | |
114 | &count, | |
115 | popcount<block_type>(), | |
116 | plus<ulong_>(), | |
117 | queue | |
118 | ); | |
119 | return static_cast<size_type>(count); | |
120 | } | |
121 | ||
122 | /// Resizes the bitset to contain \p num_bits. If the new size is greater | |
123 | /// than the current size the new bits are set to zero. | |
124 | void resize(size_type num_bits, command_queue &queue) | |
125 | { | |
126 | // resize bits | |
127 | const size_type current_block_count = m_bits.size(); | |
128 | m_bits.resize(num_bits * bits_per_block, queue); | |
129 | ||
130 | // fill new block with zeros (if new blocks were added) | |
131 | const size_type new_block_count = m_bits.size(); | |
132 | if(new_block_count > current_block_count){ | |
133 | fill_n( | |
134 | m_bits.begin() + current_block_count, | |
135 | new_block_count - current_block_count, | |
136 | block_type(0), | |
137 | queue | |
138 | ); | |
139 | } | |
140 | ||
141 | // store new size | |
142 | m_size = num_bits; | |
143 | } | |
144 | ||
145 | /// Sets the bit at position \p n to \c true. | |
146 | void set(size_type n, command_queue &queue) | |
147 | { | |
148 | set(n, true, queue); | |
149 | } | |
150 | ||
151 | /// Sets the bit at position \p n to \p value. | |
152 | void set(size_type n, bool value, command_queue &queue) | |
153 | { | |
154 | const size_type bit = n % bits_per_block; | |
155 | const size_type block = n / bits_per_block; | |
156 | ||
157 | // load current block | |
158 | block_type block_value; | |
159 | copy_n(m_bits.begin() + block, 1, &block_value, queue); | |
160 | ||
161 | // update block value | |
162 | if(value){ | |
163 | block_value |= (size_type(1) << bit); | |
164 | } | |
165 | else { | |
166 | block_value &= ~(size_type(1) << bit); | |
167 | } | |
168 | ||
169 | // store new block | |
170 | copy_n(&block_value, 1, m_bits.begin() + block, queue); | |
171 | } | |
172 | ||
173 | /// Returns \c true if the bit at position \p n is set (i.e. '1'). | |
174 | bool test(size_type n, command_queue &queue) | |
175 | { | |
176 | const size_type bit = n % (sizeof(block_type) * CHAR_BIT); | |
177 | const size_type block = n / (sizeof(block_type) * CHAR_BIT); | |
178 | ||
179 | block_type block_value; | |
180 | copy_n(m_bits.begin() + block, 1, &block_value, queue); | |
181 | ||
182 | return block_value & (size_type(1) << bit); | |
183 | } | |
184 | ||
185 | /// Flips the value of the bit at position \p n. | |
186 | void flip(size_type n, command_queue &queue) | |
187 | { | |
188 | set(n, !test(n, queue), queue); | |
189 | } | |
190 | ||
191 | /// Returns \c true if any bit in the bitset is set (i.e. '1'). | |
192 | bool any(command_queue &queue) const | |
193 | { | |
194 | return any_of( | |
195 | m_bits.begin(), m_bits.end(), lambda::_1 != block_type(0), queue | |
196 | ); | |
197 | } | |
198 | ||
199 | /// Returns \c true if all of the bits in the bitset are set to zero. | |
200 | bool none(command_queue &queue) const | |
201 | { | |
202 | return !any(queue); | |
203 | } | |
204 | ||
205 | /// Sets all of the bits in the bitset to zero. | |
206 | void reset(command_queue &queue) | |
207 | { | |
208 | fill(m_bits.begin(), m_bits.end(), block_type(0), queue); | |
209 | } | |
210 | ||
211 | /// Sets the bit at position \p n to zero. | |
212 | void reset(size_type n, command_queue &queue) | |
213 | { | |
214 | set(n, false, queue); | |
215 | } | |
216 | ||
217 | /// Empties the bitset (e.g. \c resize(0)). | |
218 | void clear() | |
219 | { | |
220 | m_bits.clear(); | |
221 | } | |
222 | ||
223 | /// Returns the allocator used to allocate storage for the bitset. | |
224 | allocator_type get_allocator() const | |
225 | { | |
226 | return m_bits.get_allocator(); | |
227 | } | |
228 | ||
229 | private: | |
230 | container_type m_bits; | |
231 | size_type m_size; | |
232 | }; | |
233 | ||
234 | } // end compute namespace | |
235 | } // end boost namespace | |
236 | ||
237 | #endif // BOOST_COMPUTE_CONTAINER_DYNAMIC_BITSET_HPP |