45 #ifndef KOKKOS_BITSET_HPP 46 #define KOKKOS_BITSET_HPP 48 #include <Kokkos_Core.hpp> 49 #include <Kokkos_Functional.hpp> 51 #include <impl/Kokkos_Bitset_impl.hpp> 57 template <
typename Device = Kokkos::DefaultExecutionSpace>
60 template <
typename Device = Kokkos::DefaultExecutionSpace>
63 template <
typename DstDevice,
typename SrcDevice>
66 template <
typename DstDevice,
typename SrcDevice>
69 template <
typename DstDevice,
typename SrcDevice>
73 template <
typename Device>
76 using execution_space = Device;
77 using size_type =
unsigned int;
79 enum { BIT_SCAN_REVERSE = 1u };
80 enum { MOVE_HINT_BACKWARD = 2u };
83 BIT_SCAN_FORWARD_MOVE_HINT_FORWARD = 0u,
84 BIT_SCAN_REVERSE_MOVE_HINT_FORWARD = BIT_SCAN_REVERSE,
85 BIT_SCAN_FORWARD_MOVE_HINT_BACKWARD = MOVE_HINT_BACKWARD,
86 BIT_SCAN_REVERSE_MOVE_HINT_BACKWARD = BIT_SCAN_REVERSE | MOVE_HINT_BACKWARD
90 enum { block_size =
static_cast<unsigned>(
sizeof(unsigned) * CHAR_BIT) };
91 enum { block_mask = block_size - 1u };
92 enum { block_shift = Kokkos::Impl::integral_power_of_two(block_size) };
99 m_last_block_mask(0u),
100 m_blocks(
"Bitset", ((m_size + block_mask) >> block_shift)) {
101 for (
int i = 0, end = static_cast<int>(m_size & block_mask); i < end; ++i) {
102 m_last_block_mask |= 1u << i;
106 KOKKOS_DEFAULTED_FUNCTION
109 KOKKOS_DEFAULTED_FUNCTION
112 KOKKOS_DEFAULTED_FUNCTION
115 KOKKOS_DEFAULTED_FUNCTION
118 KOKKOS_DEFAULTED_FUNCTION
123 KOKKOS_FORCEINLINE_FUNCTION
124 unsigned size()
const {
return m_size; }
129 Impl::BitsetCount<Bitset<Device> > f(*
this);
136 Kokkos::deep_copy(m_blocks, ~0u);
138 if (m_last_block_mask) {
140 using raw_deep_copy =
141 Kokkos::Impl::DeepCopy<
typename execution_space::memory_space,
143 raw_deep_copy(m_blocks.data() + (m_blocks.
extent(0) - 1u),
144 &m_last_block_mask,
sizeof(
unsigned));
150 void reset() { Kokkos::deep_copy(m_blocks, 0u); }
154 void clear() { Kokkos::deep_copy(m_blocks, 0u); }
158 KOKKOS_FORCEINLINE_FUNCTION
159 bool set(
unsigned i)
const {
161 unsigned* block_ptr = &m_blocks[i >> block_shift];
162 const unsigned mask = 1u << static_cast<int>(i & block_mask);
164 return !(atomic_fetch_or(block_ptr, mask) & mask);
171 KOKKOS_FORCEINLINE_FUNCTION
174 unsigned* block_ptr = &m_blocks[i >> block_shift];
175 const unsigned mask = 1u << static_cast<int>(i & block_mask);
177 return atomic_fetch_and(block_ptr, ~mask) & mask;
184 KOKKOS_FORCEINLINE_FUNCTION
187 const unsigned block = volatile_load(&m_blocks[i >> block_shift]);
188 const unsigned mask = 1u << static_cast<int>(i & block_mask);
197 KOKKOS_FORCEINLINE_FUNCTION
204 KOKKOS_INLINE_FUNCTION
207 unsigned scan_direction = BIT_SCAN_FORWARD_MOVE_HINT_FORWARD)
const {
208 const unsigned block_idx =
209 (hint >> block_shift) < m_blocks.
extent(0) ? (hint >> block_shift) : 0;
210 const unsigned offset = hint & block_mask;
211 unsigned block = volatile_load(&m_blocks[block_idx]);
212 block = !m_last_block_mask || (block_idx < (m_blocks.
extent(0) - 1))
214 : block & m_last_block_mask;
216 return find_any_helper(block_idx, offset, block, scan_direction);
223 KOKKOS_INLINE_FUNCTION
226 unsigned scan_direction = BIT_SCAN_FORWARD_MOVE_HINT_FORWARD)
const {
227 const unsigned block_idx = hint >> block_shift;
228 const unsigned offset = hint & block_mask;
229 unsigned block = volatile_load(&m_blocks[block_idx]);
230 block = !m_last_block_mask || (block_idx < (m_blocks.
extent(0) - 1))
232 : ~block & m_last_block_mask;
234 return find_any_helper(block_idx, offset, block, scan_direction);
237 KOKKOS_INLINE_FUNCTION constexpr
bool is_allocated()
const {
238 return m_blocks.is_allocated();
242 KOKKOS_FORCEINLINE_FUNCTION
244 unsigned offset,
unsigned block,
245 unsigned scan_direction)
const {
249 result.second = update_hint(block_idx, offset, scan_direction);
252 scan_block((block_idx << block_shift), offset, block, scan_direction);
257 KOKKOS_FORCEINLINE_FUNCTION
258 unsigned scan_block(
unsigned block_start,
int offset,
unsigned block,
259 unsigned scan_direction)
const {
260 offset = !(scan_direction & BIT_SCAN_REVERSE)
262 : (offset + block_mask) & block_mask;
263 block = Impl::rotate_right(block, offset);
264 return (((!(scan_direction & BIT_SCAN_REVERSE)
265 ? Impl::bit_scan_forward(block)
266 : ::Kokkos::log2(block)) +
272 KOKKOS_FORCEINLINE_FUNCTION
273 unsigned update_hint(
long long block_idx,
unsigned offset,
274 unsigned scan_direction)
const {
275 block_idx += scan_direction & MOVE_HINT_BACKWARD ? -1 : 1;
276 block_idx = block_idx >= 0 ? block_idx : m_blocks.
extent(0) - 1;
278 block_idx < static_cast<long long>(m_blocks.
extent(0)) ? block_idx : 0;
280 return static_cast<unsigned>(block_idx) * block_size + offset;
285 unsigned m_last_block_mask;
286 View<unsigned*, execution_space, MemoryTraits<RandomAccess> > m_blocks;
289 template <
typename DDevice>
292 template <
typename DDevice>
293 friend class ConstBitset;
295 template <
typename Bitset>
296 friend struct Impl::BitsetCount;
298 template <
typename DstDevice,
typename SrcDevice>
299 friend void deep_copy(Bitset<DstDevice>& dst, Bitset<SrcDevice>
const& src);
301 template <
typename DstDevice,
typename SrcDevice>
302 friend void deep_copy(Bitset<DstDevice>& dst,
303 ConstBitset<SrcDevice>
const& src);
308 template <
typename Device>
311 using execution_space = Device;
312 using size_type =
unsigned int;
315 enum { block_size =
static_cast<unsigned>(
sizeof(unsigned) * CHAR_BIT) };
316 enum { block_mask = block_size - 1u };
317 enum { block_shift = Kokkos::Impl::integral_power_of_two(block_size) };
320 ConstBitset() : m_size(0) {}
322 ConstBitset(Bitset<Device>
const& rhs)
323 : m_size(rhs.m_size), m_blocks(rhs.m_blocks) {}
325 ConstBitset(ConstBitset<Device>
const& rhs)
326 : m_size(rhs.m_size), m_blocks(rhs.m_blocks) {}
328 ConstBitset<Device>& operator=(Bitset<Device>
const& rhs) {
329 this->m_size = rhs.m_size;
330 this->m_blocks = rhs.m_blocks;
335 ConstBitset<Device>& operator=(ConstBitset<Device>
const& rhs) {
336 this->m_size = rhs.m_size;
337 this->m_blocks = rhs.m_blocks;
342 KOKKOS_FORCEINLINE_FUNCTION
343 unsigned size()
const {
return m_size; }
345 unsigned count()
const {
346 Impl::BitsetCount<ConstBitset<Device> > f(*
this);
350 KOKKOS_FORCEINLINE_FUNCTION
351 bool test(
unsigned i)
const {
353 const unsigned block = m_blocks[i >> block_shift];
354 const unsigned mask = 1u << static_cast<int>(i & block_mask);
362 View<const unsigned*, execution_space, MemoryTraits<RandomAccess> > m_blocks;
365 template <
typename DDevice>
366 friend class ConstBitset;
368 template <
typename Bitset>
369 friend struct Impl::BitsetCount;
371 template <
typename DstDevice,
typename SrcDevice>
372 friend void deep_copy(Bitset<DstDevice>& dst,
373 ConstBitset<SrcDevice>
const& src);
375 template <
typename DstDevice,
typename SrcDevice>
376 friend void deep_copy(ConstBitset<DstDevice>& dst,
377 ConstBitset<SrcDevice>
const& src);
380 template <
typename DstDevice,
typename SrcDevice>
381 void deep_copy(Bitset<DstDevice>& dst, Bitset<SrcDevice>
const& src) {
382 if (dst.size() != src.size()) {
383 throw std::runtime_error(
384 "Error: Cannot deep_copy bitsets of different sizes!");
387 using raw_deep_copy =
388 Kokkos::Impl::DeepCopy<
typename DstDevice::memory_space,
389 typename SrcDevice::memory_space>;
390 raw_deep_copy(dst.m_blocks.data(), src.m_blocks.data(),
391 sizeof(unsigned) * src.m_blocks.extent(0));
394 template <
typename DstDevice,
typename SrcDevice>
395 void deep_copy(Bitset<DstDevice>& dst, ConstBitset<SrcDevice>
const& src) {
396 if (dst.size() != src.size()) {
397 throw std::runtime_error(
398 "Error: Cannot deep_copy bitsets of different sizes!");
401 using raw_deep_copy =
402 Kokkos::Impl::DeepCopy<
typename DstDevice::memory_space,
403 typename SrcDevice::memory_space>;
404 raw_deep_copy(dst.m_blocks.data(), src.m_blocks.data(),
405 sizeof(unsigned) * src.m_blocks.extent(0));
408 template <
typename DstDevice,
typename SrcDevice>
409 void deep_copy(ConstBitset<DstDevice>& dst, ConstBitset<SrcDevice>
const& src) {
410 if (dst.size() != src.size()) {
411 throw std::runtime_error(
412 "Error: Cannot deep_copy bitsets of different sizes!");
415 using raw_deep_copy =
416 Kokkos::Impl::DeepCopy<
typename DstDevice::memory_space,
417 typename SrcDevice::memory_space>;
418 raw_deep_copy(dst.m_blocks.data(), src.m_blocks.data(),
419 sizeof(unsigned) * src.m_blocks.extent(0));
424 #endif // KOKKOS_BITSET_HPP A thread safe view to a bitset.
KOKKOS_FORCEINLINE_FUNCTION unsigned max_hint() 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
Bitset(unsigned arg_size=0u)
Replacement for std::pair that works on CUDA devices.
Memory management for host memory.
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
KOKKOS_FORCEINLINE_FUNCTION bool reset(unsigned i) const