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;
110 KOKKOS_INLINE_FUNCTION
113 KOKKOS_INLINE_FUNCTION
116 KOKKOS_INLINE_FUNCTION
119 KOKKOS_INLINE_FUNCTION
122 KOKKOS_INLINE_FUNCTION
127 KOKKOS_FORCEINLINE_FUNCTION
135 Impl::BitsetCount< Bitset<Device> > f(*
this);
145 if (m_last_block_mask) {
147 typedef Kokkos::Impl::DeepCopy< typename execution_space::memory_space, Kokkos::HostSpace > raw_deep_copy;
148 raw_deep_copy( m_blocks.data() + (m_blocks.
extent(0) -1u), &m_last_block_mask,
sizeof(
unsigned));
168 KOKKOS_FORCEINLINE_FUNCTION
169 bool set(
unsigned i )
const
172 unsigned * block_ptr = &m_blocks[ i >> block_shift ];
173 const unsigned mask = 1u << static_cast<int>( i & block_mask );
175 return !( atomic_fetch_or( block_ptr, mask ) & mask );
182 KOKKOS_FORCEINLINE_FUNCTION
186 unsigned * block_ptr = &m_blocks[ i >> block_shift ];
187 const unsigned mask = 1u << static_cast<int>( i & block_mask );
189 return atomic_fetch_and( block_ptr, ~mask ) & mask;
196 KOKKOS_FORCEINLINE_FUNCTION
200 const unsigned block = volatile_load(&m_blocks[ i >> block_shift ]);
201 const unsigned mask = 1u << static_cast<int>( i & block_mask );
210 KOKKOS_FORCEINLINE_FUNCTION
213 return m_blocks.
extent(0);
219 KOKKOS_INLINE_FUNCTION
222 const unsigned block_idx = (hint >> block_shift) < m_blocks.
extent(0) ? (hint >> block_shift) : 0;
223 const unsigned offset = hint & block_mask;
224 unsigned block = volatile_load(&m_blocks[ block_idx ]);
225 block = !m_last_block_mask || (block_idx < (m_blocks.
extent(0)-1)) ? block : block & m_last_block_mask ;
227 return find_any_helper(block_idx, offset, block, scan_direction);
233 KOKKOS_INLINE_FUNCTION
236 const unsigned block_idx = hint >> block_shift;
237 const unsigned offset = hint & block_mask;
238 unsigned block = volatile_load(&m_blocks[ block_idx ]);
239 block = !m_last_block_mask || (block_idx < (m_blocks.
extent(0)-1) ) ? ~block : ~block & m_last_block_mask ;
241 return find_any_helper(block_idx, offset, block, scan_direction);
246 KOKKOS_FORCEINLINE_FUNCTION
252 result.second = update_hint( block_idx, offset, scan_direction );
255 result.second = scan_block( (block_idx << block_shift)
265 KOKKOS_FORCEINLINE_FUNCTION
266 unsigned scan_block(
unsigned block_start,
int offset,
unsigned block,
unsigned scan_direction )
const
268 offset = !(scan_direction & BIT_SCAN_REVERSE) ? offset : (offset + block_mask) & block_mask;
269 block = Impl::rotate_right(block, offset);
270 return ((( !(scan_direction & BIT_SCAN_REVERSE) ?
271 Impl::bit_scan_forward(block) :
272 ::Kokkos::log2(block)
278 KOKKOS_FORCEINLINE_FUNCTION
279 unsigned update_hint(
long long block_idx,
unsigned offset,
unsigned scan_direction )
const
281 block_idx += scan_direction & MOVE_HINT_BACKWARD ? -1 : 1;
282 block_idx = block_idx >= 0 ? block_idx : m_blocks.
extent(0) - 1;
283 block_idx = block_idx < static_cast<long long>(m_blocks.
extent(0)) ? block_idx : 0;
285 return static_cast<unsigned>(block_idx)*block_size + offset;
291 unsigned m_last_block_mask;
292 View< unsigned *, execution_space, MemoryTraits<RandomAccess> > m_blocks;
295 template <
typename DDevice>
298 template <
typename DDevice>
299 friend class ConstBitset;
301 template <
typename Bitset>
302 friend struct Impl::BitsetCount;
304 template <
typename DstDevice,
typename SrcDevice>
305 friend void deep_copy( Bitset<DstDevice> & dst, Bitset<SrcDevice>
const& src);
307 template <
typename DstDevice,
typename SrcDevice>
308 friend void deep_copy( Bitset<DstDevice> & dst, ConstBitset<SrcDevice>
const& src);
313 template <
typename Device>
317 typedef Device execution_space;
318 typedef unsigned size_type;
321 enum { block_size =
static_cast<unsigned>(
sizeof(unsigned)*CHAR_BIT) };
322 enum { block_mask = block_size -1u };
323 enum { block_shift = Kokkos::Impl::integral_power_of_two(block_size) };
330 ConstBitset(Bitset<Device>
const& rhs)
332 , m_blocks(rhs.m_blocks)
335 ConstBitset(ConstBitset<Device>
const& rhs)
336 : m_size( rhs.m_size )
337 , m_blocks( rhs.m_blocks )
340 ConstBitset<Device> & operator = (Bitset<Device>
const & rhs)
342 this->m_size = rhs.m_size;
343 this->m_blocks = rhs.m_blocks;
348 ConstBitset<Device> & operator = (ConstBitset<Device>
const & rhs)
350 this->m_size = rhs.m_size;
351 this->m_blocks = rhs.m_blocks;
357 KOKKOS_FORCEINLINE_FUNCTION
358 unsigned size()
const
363 unsigned count()
const
365 Impl::BitsetCount< ConstBitset<Device> > f(*
this);
369 KOKKOS_FORCEINLINE_FUNCTION
370 bool test(
unsigned i )
const
373 const unsigned block = m_blocks[ i >> block_shift ];
374 const unsigned mask = 1u << static_cast<int>( i & block_mask );
383 View< const unsigned *, execution_space, MemoryTraits<RandomAccess> > m_blocks;
386 template <
typename DDevice>
387 friend class ConstBitset;
389 template <
typename Bitset>
390 friend struct Impl::BitsetCount;
392 template <
typename DstDevice,
typename SrcDevice>
393 friend void deep_copy( Bitset<DstDevice> & dst, ConstBitset<SrcDevice>
const& src);
395 template <
typename DstDevice,
typename SrcDevice>
396 friend void deep_copy( ConstBitset<DstDevice> & dst, ConstBitset<SrcDevice>
const& src);
400 template <
typename DstDevice,
typename SrcDevice>
401 void deep_copy( Bitset<DstDevice> & dst, Bitset<SrcDevice>
const& src)
403 if (dst.size() != src.size()) {
404 throw std::runtime_error(
"Error: Cannot deep_copy bitsets of different sizes!");
407 typedef Kokkos::Impl::DeepCopy< typename DstDevice::memory_space, typename SrcDevice::memory_space > raw_deep_copy;
408 raw_deep_copy(dst.m_blocks.data(), src.m_blocks.data(),
sizeof(unsigned)*src.m_blocks.extent(0));
411 template <
typename DstDevice,
typename SrcDevice>
412 void deep_copy( Bitset<DstDevice> & dst, ConstBitset<SrcDevice>
const& src)
414 if (dst.size() != src.size()) {
415 throw std::runtime_error(
"Error: Cannot deep_copy bitsets of different sizes!");
418 typedef Kokkos::Impl::DeepCopy< typename DstDevice::memory_space, typename SrcDevice::memory_space > raw_deep_copy;
419 raw_deep_copy(dst.m_blocks.data(), src.m_blocks.data(),
sizeof(unsigned)*src.m_blocks.extent(0));
422 template <
typename DstDevice,
typename SrcDevice>
423 void deep_copy( ConstBitset<DstDevice> & dst, ConstBitset<SrcDevice>
const& src)
425 if (dst.size() != src.size()) {
426 throw std::runtime_error(
"Error: Cannot deep_copy bitsets of different sizes!");
429 typedef Kokkos::Impl::DeepCopy< typename DstDevice::memory_space, typename SrcDevice::memory_space > raw_deep_copy;
430 raw_deep_copy(dst.m_blocks.data(), src.m_blocks.data(),
sizeof(unsigned)*src.m_blocks.extent(0));
435 #endif //KOKKOS_BITSET_HPP
A thread safe view to a bitset.
KOKKOS_FORCEINLINE_FUNCTION unsigned max_hint() const
Bitset(unsigned arg_size=0u)
Replacement for std::pair that works on CUDA devices.
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.
KOKKOS_FORCEINLINE_FUNCTION bool reset(unsigned i) const
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
KOKKOS_FORCEINLINE_FUNCTION bool set(unsigned i) 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 constexpr std::enable_if< std::is_integral< iType >::value, size_t >::type extent(const iType &r) const noexcept
rank() to be implemented