44 #ifndef KOKKOS_BITSET_HPP 45 #define KOKKOS_BITSET_HPP 47 #include <Kokkos_Core.hpp> 48 #include <Kokkos_Functional.hpp> 50 #include <impl/Kokkos_Bitset_impl.hpp> 56 template <
typename Device = Kokkos::DefaultExecutionSpace >
59 template <
typename Device = Kokkos::DefaultExecutionSpace >
62 template <
typename DstDevice,
typename SrcDevice>
65 template <
typename DstDevice,
typename SrcDevice>
68 template <
typename DstDevice,
typename SrcDevice>
73 template <
typename Device>
77 typedef Device execution_space;
78 typedef unsigned size_type;
80 enum { BIT_SCAN_REVERSE = 1u };
81 enum { MOVE_HINT_BACKWARD = 2u };
84 BIT_SCAN_FORWARD_MOVE_HINT_FORWARD = 0u
85 , BIT_SCAN_REVERSE_MOVE_HINT_FORWARD = BIT_SCAN_REVERSE
86 , BIT_SCAN_FORWARD_MOVE_HINT_BACKWARD = MOVE_HINT_BACKWARD
87 , BIT_SCAN_REVERSE_MOVE_HINT_BACKWARD = BIT_SCAN_REVERSE | MOVE_HINT_BACKWARD
91 enum { block_size =
static_cast<unsigned>(
sizeof(unsigned)*CHAR_BIT) };
92 enum { block_mask = block_size-1u };
93 enum { block_shift = Kokkos::Impl::integral_power_of_two(block_size) };
102 , m_last_block_mask(0u)
103 , m_blocks(
"Bitset", ((m_size + block_mask) >> block_shift) )
105 for (
int i=0, end = static_cast<int>(m_size & block_mask); i < end; ++i) {
106 m_last_block_mask |= 1u << i;
113 this->m_size = rhs.m_size;
114 this->m_last_block_mask = rhs.m_last_block_mask;
115 this->m_blocks = rhs.m_blocks;
122 : m_size( rhs.m_size )
123 , m_last_block_mask( rhs.m_last_block_mask )
124 , m_blocks( rhs.m_blocks )
129 KOKKOS_FORCEINLINE_FUNCTION
137 Impl::BitsetCount< Bitset<Device> > f(*
this);
147 if (m_last_block_mask) {
149 typedef Kokkos::Impl::DeepCopy< typename execution_space::memory_space, Kokkos::HostSpace > raw_deep_copy;
150 raw_deep_copy( m_blocks.data() + (m_blocks.
extent(0) -1u), &m_last_block_mask,
sizeof(
unsigned));
170 KOKKOS_FORCEINLINE_FUNCTION
171 bool set(
unsigned i )
const 174 unsigned * block_ptr = &m_blocks[ i >> block_shift ];
175 const unsigned mask = 1u << static_cast<int>( i & block_mask );
177 return !( atomic_fetch_or( block_ptr, mask ) & mask );
184 KOKKOS_FORCEINLINE_FUNCTION
188 unsigned * block_ptr = &m_blocks[ i >> block_shift ];
189 const unsigned mask = 1u << static_cast<int>( i & block_mask );
191 return atomic_fetch_and( block_ptr, ~mask ) & mask;
198 KOKKOS_FORCEINLINE_FUNCTION
202 const unsigned block = volatile_load(&m_blocks[ i >> block_shift ]);
203 const unsigned mask = 1u << static_cast<int>( i & block_mask );
212 KOKKOS_FORCEINLINE_FUNCTION
215 return m_blocks.
extent(0);
221 KOKKOS_INLINE_FUNCTION
224 const unsigned block_idx = (hint >> block_shift) < m_blocks.
extent(0) ? (hint >> block_shift) : 0;
225 const unsigned offset = hint & block_mask;
226 unsigned block = volatile_load(&m_blocks[ block_idx ]);
227 block = !m_last_block_mask || (block_idx < (m_blocks.
extent(0)-1)) ? block : block & m_last_block_mask ;
229 return find_any_helper(block_idx, offset, block, scan_direction);
235 KOKKOS_INLINE_FUNCTION
238 const unsigned block_idx = hint >> block_shift;
239 const unsigned offset = hint & block_mask;
240 unsigned block = volatile_load(&m_blocks[ block_idx ]);
241 block = !m_last_block_mask || (block_idx < (m_blocks.
extent(0)-1) ) ? ~block : ~block & m_last_block_mask ;
243 return find_any_helper(block_idx, offset, block, scan_direction);
248 KOKKOS_FORCEINLINE_FUNCTION
254 result.second = update_hint( block_idx, offset, scan_direction );
257 result.second = scan_block( (block_idx << block_shift)
267 KOKKOS_FORCEINLINE_FUNCTION
268 unsigned scan_block(
unsigned block_start,
int offset,
unsigned block,
unsigned scan_direction )
const 270 offset = !(scan_direction & BIT_SCAN_REVERSE) ? offset : (offset + block_mask) & block_mask;
271 block = Impl::rotate_right(block, offset);
272 return ((( !(scan_direction & BIT_SCAN_REVERSE) ?
273 Impl::bit_scan_forward(block) :
274 ::Kokkos::log2(block)
280 KOKKOS_FORCEINLINE_FUNCTION
281 unsigned update_hint(
long long block_idx,
unsigned offset,
unsigned scan_direction )
const 283 block_idx += scan_direction & MOVE_HINT_BACKWARD ? -1 : 1;
284 block_idx = block_idx >= 0 ? block_idx : m_blocks.
extent(0) - 1;
285 block_idx = block_idx < static_cast<long long>(m_blocks.
extent(0)) ? block_idx : 0;
287 return static_cast<unsigned>(block_idx)*block_size + offset;
293 unsigned m_last_block_mask;
294 View< unsigned *, execution_space, MemoryTraits<RandomAccess> > m_blocks;
297 template <
typename DDevice>
300 template <
typename DDevice>
301 friend class ConstBitset;
303 template <
typename Bitset>
304 friend struct Impl::BitsetCount;
306 template <
typename DstDevice,
typename SrcDevice>
307 friend void deep_copy( Bitset<DstDevice> & dst, Bitset<SrcDevice>
const& src);
309 template <
typename DstDevice,
typename SrcDevice>
310 friend void deep_copy( Bitset<DstDevice> & dst, ConstBitset<SrcDevice>
const& src);
315 template <
typename Device>
319 typedef Device execution_space;
320 typedef unsigned size_type;
323 enum { block_size =
static_cast<unsigned>(
sizeof(unsigned)*CHAR_BIT) };
324 enum { block_mask = block_size -1u };
325 enum { block_shift = Kokkos::Impl::integral_power_of_two(block_size) };
332 ConstBitset(Bitset<Device>
const& rhs)
334 , m_blocks(rhs.m_blocks)
337 ConstBitset(ConstBitset<Device>
const& rhs)
338 : m_size( rhs.m_size )
339 , m_blocks( rhs.m_blocks )
342 ConstBitset<Device> & operator = (Bitset<Device>
const & rhs)
344 this->m_size = rhs.m_size;
345 this->m_blocks = rhs.m_blocks;
350 ConstBitset<Device> & operator = (ConstBitset<Device>
const & rhs)
352 this->m_size = rhs.m_size;
353 this->m_blocks = rhs.m_blocks;
359 KOKKOS_FORCEINLINE_FUNCTION
360 unsigned size()
const 365 unsigned count()
const 367 Impl::BitsetCount< ConstBitset<Device> > f(*
this);
371 KOKKOS_FORCEINLINE_FUNCTION
372 bool test(
unsigned i )
const 375 const unsigned block = m_blocks[ i >> block_shift ];
376 const unsigned mask = 1u << static_cast<int>( i & block_mask );
385 View< const unsigned *, execution_space, MemoryTraits<RandomAccess> > m_blocks;
388 template <
typename DDevice>
389 friend class ConstBitset;
391 template <
typename Bitset>
392 friend struct Impl::BitsetCount;
394 template <
typename DstDevice,
typename SrcDevice>
395 friend void deep_copy( Bitset<DstDevice> & dst, ConstBitset<SrcDevice>
const& src);
397 template <
typename DstDevice,
typename SrcDevice>
398 friend void deep_copy( ConstBitset<DstDevice> & dst, ConstBitset<SrcDevice>
const& src);
402 template <
typename DstDevice,
typename SrcDevice>
403 void deep_copy( Bitset<DstDevice> & dst, Bitset<SrcDevice>
const& src)
405 if (dst.size() != src.size()) {
406 throw std::runtime_error(
"Error: Cannot deep_copy bitsets of different sizes!");
409 typedef Kokkos::Impl::DeepCopy< typename DstDevice::memory_space, typename SrcDevice::memory_space > raw_deep_copy;
410 raw_deep_copy(dst.m_blocks.data(), src.m_blocks.data(),
sizeof(unsigned)*src.m_blocks.extent(0));
413 template <
typename DstDevice,
typename SrcDevice>
414 void deep_copy( Bitset<DstDevice> & dst, ConstBitset<SrcDevice>
const& src)
416 if (dst.size() != src.size()) {
417 throw std::runtime_error(
"Error: Cannot deep_copy bitsets of different sizes!");
420 typedef Kokkos::Impl::DeepCopy< typename DstDevice::memory_space, typename SrcDevice::memory_space > raw_deep_copy;
421 raw_deep_copy(dst.m_blocks.data(), src.m_blocks.data(),
sizeof(unsigned)*src.m_blocks.extent(0));
424 template <
typename DstDevice,
typename SrcDevice>
425 void deep_copy( ConstBitset<DstDevice> & dst, ConstBitset<SrcDevice>
const& src)
427 if (dst.size() != src.size()) {
428 throw std::runtime_error(
"Error: Cannot deep_copy bitsets of different sizes!");
431 typedef Kokkos::Impl::DeepCopy< typename DstDevice::memory_space, typename SrcDevice::memory_space > raw_deep_copy;
432 raw_deep_copy(dst.m_blocks.data(), src.m_blocks.data(),
sizeof(unsigned)*src.m_blocks.extent(0));
437 #endif //KOKKOS_BITSET_HPP A thread safe view to a bitset.
KOKKOS_FORCEINLINE_FUNCTION unsigned max_hint() const
Bitset(unsigned arg_size=0u)
Bitset(Bitset< Device > const &rhs)
copy constructor
Replacement for std::pair that works on CUDA devices.
KOKKOS_FORCEINLINE_FUNCTION bool test(unsigned i) const
KOKKOS_FORCEINLINE_FUNCTION unsigned size() const
KOKKOS_INLINE_FUNCTION Kokkos::pair< bool, unsigned > find_any_unset_near(unsigned hint, unsigned scan_direction=BIT_SCAN_FORWARD_MOVE_HINT_FORWARD) const
KOKKOS_INLINE_FUNCTION Kokkos::pair< bool, unsigned > find_any_set_near(unsigned hint, unsigned scan_direction=BIT_SCAN_FORWARD_MOVE_HINT_FORWARD) const
void deep_copy(const View< DT, DP... > &dst, typename ViewTraits< DT, DP... >::const_value_type &value, typename std::enable_if< std::is_same< typename ViewTraits< DT, DP... >::specialize, void >::value >::type *=0)
Deep copy a value from Host memory into a view.
Bitset< Device > & operator=(Bitset< Device > const &rhs)
assignment
KOKKOS_FORCEINLINE_FUNCTION bool reset(unsigned i) const
KOKKOS_INLINE_FUNCTION constexpr std::enable_if< std::is_integral< iType >::value, size_t >::type extent(const iType &r) const
rank() to be implemented