boost/compute/container/dynamic_bitset.hpp
//---------------------------------------------------------------------------// // Copyright (c) 2013-2014 Kyle Lutz <kyle.r.lutz@gmail.com> // // Distributed under the Boost Software License, Version 1.0 // See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt // // See http://boostorg.github.com/compute for more information. //---------------------------------------------------------------------------// #ifndef BOOST_COMPUTE_CONTAINER_DYNAMIC_BITSET_HPP #define BOOST_COMPUTE_CONTAINER_DYNAMIC_BITSET_HPP #include <boost/compute/lambda.hpp> #include <boost/compute/algorithm/any_of.hpp> #include <boost/compute/algorithm/fill.hpp> #include <boost/compute/algorithm/transform_reduce.hpp> #include <boost/compute/container/vector.hpp> #include <boost/compute/functional/integer.hpp> #include <boost/compute/types/fundamental.hpp> namespace boost { namespace compute { /// \class dynamic_bitset /// \brief The dynamic_bitset class contains a resizable bit array. /// /// For example, to create a dynamic-bitset with space for 1000 bits on the /// device: /// \code /// boost::compute::dynamic_bitset<> bits(1000, queue); /// \endcode /// /// The Boost.Compute \c dynamic_bitset class provides a STL-like API and is /// modeled after the \c boost::dynamic_bitset class from Boost. /// /// \see \ref vector "vector<T>" template<class Block = ulong_, class Alloc = buffer_allocator<Block> > class dynamic_bitset { public: typedef Block block_type; typedef Alloc allocator_type; typedef vector<Block, Alloc> container_type; typedef typename container_type::size_type size_type; BOOST_STATIC_CONSTANT(size_type, bits_per_block = sizeof(block_type) * CHAR_BIT); BOOST_STATIC_CONSTANT(size_type, npos = static_cast<size_type>(-1)); /// Creates a new dynamic bitset with storage for \p size bits. Initializes /// all bits to zero. dynamic_bitset(size_type size, command_queue &queue) : m_bits(size / sizeof(block_type), queue.get_context()), m_size(size) { // initialize all bits to zero reset(queue); } /// Creates a new dynamic bitset as a copy of \p other. dynamic_bitset(const dynamic_bitset &other) : m_bits(other.m_bits), m_size(other.m_size) { } /// Copies the data from \p other to \c *this. dynamic_bitset& operator=(const dynamic_bitset &other) { if(this != &other){ m_bits = other.m_bits; m_size = other.m_size; } return *this; } /// Destroys the dynamic bitset. ~dynamic_bitset() { } /// Returns the size of the dynamic bitset. size_type size() const { return m_size; } /// Returns the number of blocks to store the bits in the dynamic bitset. size_type num_blocks() const { return m_bits.size(); } /// Returns the maximum possible size for the dynamic bitset. size_type max_size() const { return m_bits.max_size() * bits_per_block; } /// Returns \c true if the dynamic bitset is empty (i.e. \c size() == \c 0). bool empty() const { return size() == 0; } /// Returns the number of set bits (i.e. '1') in the bitset. size_type count(command_queue &queue) const { ulong_ count = 0; transform_reduce( m_bits.begin(), m_bits.end(), &count, popcount<block_type>(), plus<ulong_>(), queue ); return static_cast<size_type>(count); } /// Resizes the bitset to contain \p num_bits. If the new size is greater /// than the current size the new bits are set to zero. void resize(size_type num_bits, command_queue &queue) { // resize bits const size_type current_block_count = m_bits.size(); m_bits.resize(num_bits * bits_per_block, queue); // fill new block with zeros (if new blocks were added) const size_type new_block_count = m_bits.size(); if(new_block_count > current_block_count){ fill_n( m_bits.begin() + current_block_count, new_block_count - current_block_count, block_type(0), queue ); } // store new size m_size = num_bits; } /// Sets the bit at position \p n to \c true. void set(size_type n, command_queue &queue) { set(n, true, queue); } /// Sets the bit at position \p n to \p value. void set(size_type n, bool value, command_queue &queue) { const size_type bit = n % bits_per_block; const size_type block = n / bits_per_block; // load current block block_type block_value; copy_n(m_bits.begin() + block, 1, &block_value, queue); // update block value if(value){ block_value |= (size_type(1) << bit); } else { block_value &= ~(size_type(1) << bit); } // store new block copy_n(&block_value, 1, m_bits.begin() + block, queue); } /// Returns \c true if the bit at position \p n is set (i.e. '1'). bool test(size_type n, command_queue &queue) { const size_type bit = n % (sizeof(block_type) * CHAR_BIT); const size_type block = n / (sizeof(block_type) * CHAR_BIT); block_type block_value; copy_n(m_bits.begin() + block, 1, &block_value, queue); return block_value & (size_type(1) << bit); } /// Flips the value of the bit at position \p n. void flip(size_type n, command_queue &queue) { set(n, !test(n, queue), queue); } /// Returns \c true if any bit in the bitset is set (i.e. '1'). bool any(command_queue &queue) const { return any_of( m_bits.begin(), m_bits.end(), lambda::_1 != block_type(0), queue ); } /// Returns \c true if all of the bits in the bitset are set to zero. bool none(command_queue &queue) const { return !any(queue); } /// Sets all of the bits in the bitset to zero. void reset(command_queue &queue) { fill(m_bits.begin(), m_bits.end(), block_type(0), queue); } /// Sets the bit at position \p n to zero. void reset(size_type n, command_queue &queue) { set(n, false, queue); } /// Empties the bitset (e.g. \c resize(0)). void clear() { m_bits.clear(); } /// Returns the allocator used to allocate storage for the bitset. allocator_type get_allocator() const { return m_bits.get_allocator(); } private: container_type m_bits; size_type m_size; }; } // end compute namespace } // end boost namespace #endif // BOOST_COMPUTE_CONTAINER_DYNAMIC_BITSET_HPP