Kokkos Core Kernels Package  Version of the Day
Kokkos_Bitset.hpp
1 /*
2 //@HEADER
3 // ************************************************************************
4 //
5 // Kokkos v. 3.0
6 // Copyright (2020) National Technology & Engineering
7 // Solutions of Sandia, LLC (NTESS).
8 //
9 // Under the terms of Contract DE-NA0003525 with NTESS,
10 // the U.S. Government retains certain rights in this software.
11 //
12 // Redistribution and use in source and binary forms, with or without
13 // modification, are permitted provided that the following conditions are
14 // met:
15 //
16 // 1. Redistributions of source code must retain the above copyright
17 // notice, this list of conditions and the following disclaimer.
18 //
19 // 2. Redistributions in binary form must reproduce the above copyright
20 // notice, this list of conditions and the following disclaimer in the
21 // documentation and/or other materials provided with the distribution.
22 //
23 // 3. Neither the name of the Corporation nor the names of the
24 // contributors may be used to endorse or promote products derived from
25 // this software without specific prior written permission.
26 //
27 // THIS SOFTWARE IS PROVIDED BY NTESS "AS IS" AND ANY
28 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
29 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
30 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL NTESS OR THE
31 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
32 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
33 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
34 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
35 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
36 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
37 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38 //
39 // Questions? Contact Christian R. Trott (crtrott@sandia.gov)
40 //
41 // ************************************************************************
42 //@HEADER
43 */
44 
45 #ifndef KOKKOS_BITSET_HPP
46 #define KOKKOS_BITSET_HPP
47 
48 #include <Kokkos_Core.hpp>
49 #include <Kokkos_Functional.hpp>
50 
51 #include <impl/Kokkos_Bitset_impl.hpp>
52 
53 #include <stdexcept>
54 
55 namespace Kokkos {
56 
57 template <typename Device = Kokkos::DefaultExecutionSpace>
58 class Bitset;
59 
60 template <typename Device = Kokkos::DefaultExecutionSpace>
62 
63 template <typename DstDevice, typename SrcDevice>
64 void deep_copy(Bitset<DstDevice>& dst, Bitset<SrcDevice> const& src);
65 
66 template <typename DstDevice, typename SrcDevice>
67 void deep_copy(Bitset<DstDevice>& dst, ConstBitset<SrcDevice> const& src);
68 
69 template <typename DstDevice, typename SrcDevice>
70 void deep_copy(ConstBitset<DstDevice>& dst, ConstBitset<SrcDevice> const& src);
71 
73 template <typename Device>
74 class Bitset {
75  public:
76  using execution_space = Device;
77  using size_type = unsigned int;
78 
79  enum { BIT_SCAN_REVERSE = 1u };
80  enum { MOVE_HINT_BACKWARD = 2u };
81 
82  enum {
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
87  };
88 
89  private:
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) };
93 
94  public:
97  Bitset(unsigned arg_size = 0u)
98  : m_size(arg_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;
103  }
104  }
105 
106  KOKKOS_DEFAULTED_FUNCTION
107  Bitset(const Bitset<Device>&) = default;
108 
109  KOKKOS_DEFAULTED_FUNCTION
110  Bitset& operator=(const Bitset<Device>&) = default;
111 
112  KOKKOS_DEFAULTED_FUNCTION
113  Bitset(Bitset<Device>&&) = default;
114 
115  KOKKOS_DEFAULTED_FUNCTION
116  Bitset& operator=(Bitset<Device>&&) = default;
117 
118  KOKKOS_DEFAULTED_FUNCTION
119  ~Bitset() = default;
120 
123  KOKKOS_FORCEINLINE_FUNCTION
124  unsigned size() const { return m_size; }
125 
128  unsigned count() const {
129  Impl::BitsetCount<Bitset<Device> > f(*this);
130  return f.apply();
131  }
132 
135  void set() {
136  Kokkos::deep_copy(m_blocks, ~0u);
137 
138  if (m_last_block_mask) {
139  // clear the unused bits in the last block
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));
145  }
146  }
147 
150  void reset() { Kokkos::deep_copy(m_blocks, 0u); }
151 
154  void clear() { Kokkos::deep_copy(m_blocks, 0u); }
155 
158  KOKKOS_FORCEINLINE_FUNCTION
159  bool set(unsigned i) const {
160  if (i < m_size) {
161  unsigned* block_ptr = &m_blocks[i >> block_shift];
162  const unsigned mask = 1u << static_cast<int>(i & block_mask);
163 
164  return !(atomic_fetch_or(block_ptr, mask) & mask);
165  }
166  return false;
167  }
168 
171  KOKKOS_FORCEINLINE_FUNCTION
172  bool reset(unsigned i) const {
173  if (i < m_size) {
174  unsigned* block_ptr = &m_blocks[i >> block_shift];
175  const unsigned mask = 1u << static_cast<int>(i & block_mask);
176 
177  return atomic_fetch_and(block_ptr, ~mask) & mask;
178  }
179  return false;
180  }
181 
184  KOKKOS_FORCEINLINE_FUNCTION
185  bool test(unsigned i) const {
186  if (i < m_size) {
187  const unsigned block = volatile_load(&m_blocks[i >> block_shift]);
188  const unsigned mask = 1u << static_cast<int>(i & block_mask);
189  return block & mask;
190  }
191  return false;
192  }
193 
197  KOKKOS_FORCEINLINE_FUNCTION
198  unsigned max_hint() const { return m_blocks.extent(0); }
199 
204  KOKKOS_INLINE_FUNCTION
206  unsigned hint,
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))
213  ? block
214  : block & m_last_block_mask;
215 
216  return find_any_helper(block_idx, offset, block, scan_direction);
217  }
218 
223  KOKKOS_INLINE_FUNCTION
225  unsigned hint,
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))
231  ? ~block
232  : ~block & m_last_block_mask;
233 
234  return find_any_helper(block_idx, offset, block, scan_direction);
235  }
236 
237  KOKKOS_INLINE_FUNCTION constexpr bool is_allocated() const {
238  return m_blocks.is_allocated();
239  }
240 
241  private:
242  KOKKOS_FORCEINLINE_FUNCTION
243  Kokkos::pair<bool, unsigned> find_any_helper(unsigned block_idx,
244  unsigned offset, unsigned block,
245  unsigned scan_direction) const {
246  Kokkos::pair<bool, unsigned> result(block > 0u, 0);
247 
248  if (!result.first) {
249  result.second = update_hint(block_idx, offset, scan_direction);
250  } else {
251  result.second =
252  scan_block((block_idx << block_shift), offset, block, scan_direction);
253  }
254  return result;
255  }
256 
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)
261  ? offset
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)) +
267  offset) &
268  block_mask) +
269  block_start;
270  }
271 
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;
277  block_idx =
278  block_idx < static_cast<long long>(m_blocks.extent(0)) ? block_idx : 0;
279 
280  return static_cast<unsigned>(block_idx) * block_size + offset;
281  }
282 
283  private:
284  unsigned m_size;
285  unsigned m_last_block_mask;
286  View<unsigned*, execution_space, MemoryTraits<RandomAccess> > m_blocks;
287 
288  private:
289  template <typename DDevice>
290  friend class Bitset;
291 
292  template <typename DDevice>
293  friend class ConstBitset;
294 
295  template <typename Bitset>
296  friend struct Impl::BitsetCount;
297 
298  template <typename DstDevice, typename SrcDevice>
299  friend void deep_copy(Bitset<DstDevice>& dst, Bitset<SrcDevice> const& src);
300 
301  template <typename DstDevice, typename SrcDevice>
302  friend void deep_copy(Bitset<DstDevice>& dst,
303  ConstBitset<SrcDevice> const& src);
304 };
305 
308 template <typename Device>
309 class ConstBitset {
310  public:
311  using execution_space = Device;
312  using size_type = unsigned int;
313 
314  private:
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) };
318 
319  public:
320  ConstBitset() : m_size(0) {}
321 
322  ConstBitset(Bitset<Device> const& rhs)
323  : m_size(rhs.m_size), m_blocks(rhs.m_blocks) {}
324 
325  ConstBitset(ConstBitset<Device> const& rhs)
326  : m_size(rhs.m_size), m_blocks(rhs.m_blocks) {}
327 
328  ConstBitset<Device>& operator=(Bitset<Device> const& rhs) {
329  this->m_size = rhs.m_size;
330  this->m_blocks = rhs.m_blocks;
331 
332  return *this;
333  }
334 
335  ConstBitset<Device>& operator=(ConstBitset<Device> const& rhs) {
336  this->m_size = rhs.m_size;
337  this->m_blocks = rhs.m_blocks;
338 
339  return *this;
340  }
341 
342  KOKKOS_FORCEINLINE_FUNCTION
343  unsigned size() const { return m_size; }
344 
345  unsigned count() const {
346  Impl::BitsetCount<ConstBitset<Device> > f(*this);
347  return f.apply();
348  }
349 
350  KOKKOS_FORCEINLINE_FUNCTION
351  bool test(unsigned i) const {
352  if (i < m_size) {
353  const unsigned block = m_blocks[i >> block_shift];
354  const unsigned mask = 1u << static_cast<int>(i & block_mask);
355  return block & mask;
356  }
357  return false;
358  }
359 
360  private:
361  unsigned m_size;
362  View<const unsigned*, execution_space, MemoryTraits<RandomAccess> > m_blocks;
363 
364  private:
365  template <typename DDevice>
366  friend class ConstBitset;
367 
368  template <typename Bitset>
369  friend struct Impl::BitsetCount;
370 
371  template <typename DstDevice, typename SrcDevice>
372  friend void deep_copy(Bitset<DstDevice>& dst,
373  ConstBitset<SrcDevice> const& src);
374 
375  template <typename DstDevice, typename SrcDevice>
376  friend void deep_copy(ConstBitset<DstDevice>& dst,
377  ConstBitset<SrcDevice> const& src);
378 };
379 
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!");
385  }
386 
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));
392 }
393 
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!");
399  }
400 
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));
406 }
407 
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!");
413  }
414 
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));
420 }
421 
422 } // namespace Kokkos
423 
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)
unsigned count() const
Replacement for std::pair that works on CUDA devices.
Definition: Kokkos_Pair.hpp:65
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
Definition: dummy.cpp:3