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>
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.ptr_on_device() + (m_blocks.dimension_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.dimension_0();
221 KOKKOS_INLINE_FUNCTION
224 const unsigned block_idx = (hint >> block_shift) < m_blocks.dimension_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.dimension_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.dimension_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 Impl::bit_scan_reverse(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.dimension_0() - 1;
285 block_idx = block_idx < static_cast<long long>(m_blocks.dimension_0()) ? block_idx : 0;
287 return static_cast<unsigned>(block_idx)*block_size + offset;
293 unsigned m_last_block_mask;
297 template <
typename DDevice>
300 template <
typename DDevice>
303 template <
typename Bitset>
304 friend struct Impl::BitsetCount;
306 template <
typename DstDevice,
typename SrcDevice>
309 template <
typename DstDevice,
typename SrcDevice>
315 template <
typename Device>
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) };
334 , m_blocks(rhs.m_blocks)
338 : m_size( rhs.m_size )
339 , m_blocks( rhs.m_blocks )
344 this->m_size = rhs.m_size;
345 this->m_blocks = rhs.m_blocks;
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 );
388 template <
typename DDevice>
391 template <
typename Bitset>
392 friend struct Impl::BitsetCount;
394 template <
typename DstDevice,
typename SrcDevice>
397 template <
typename DstDevice,
typename SrcDevice>
402 template <
typename DstDevice,
typename SrcDevice>
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.ptr_on_device(), src.m_blocks.ptr_on_device(),
sizeof(unsigned)*src.m_blocks.dimension_0());
413 template <
typename DstDevice,
typename SrcDevice>
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.ptr_on_device(), src.m_blocks.ptr_on_device(),
sizeof(unsigned)*src.m_blocks.dimension_0());
424 template <
typename DstDevice,
typename SrcDevice>
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.ptr_on_device(), src.m_blocks.ptr_on_device(),
sizeof(unsigned)*src.m_blocks.dimension_0());
437 #endif //KOKKOS_BITSET_HPP A thread safe view to a bitset.
void deep_copy(const View< DT, DL, DD, DM, DS > &dst, typename Impl::enable_if<(Impl::is_same< typename ViewTraits< DT, DL, DD, DM >::non_const_value_type, typename ViewTraits< DT, DL, DD, DM >::value_type >::value), typename ViewTraits< DT, DL, DD, DM >::const_value_type >::type &value)
Deep copy a value into a view.
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.
View to an array of data.
KOKKOS_FORCEINLINE_FUNCTION bool reset(unsigned i) const
first_type first
The first element of the pair.
Memory space for main process and CPU execution spaces.
KOKKOS_FORCEINLINE_FUNCTION bool test(unsigned i) const
KOKKOS_FORCEINLINE_FUNCTION unsigned size() const
KOKKOS_INLINE_FUNCTION Kokkos::pair< bool, unsigned > find_any_set_near(unsigned hint, unsigned scan_direction=BIT_SCAN_FORWARD_MOVE_HINT_FORWARD) const
Bitset< Device > & operator=(Bitset< Device > const &rhs)
assignment
second_type second
The second element of the pair.
KOKKOS_INLINE_FUNCTION Kokkos::pair< bool, unsigned > find_any_unset_near(unsigned hint, unsigned scan_direction=BIT_SCAN_FORWARD_MOVE_HINT_FORWARD) const