Kokkos Core Kernels Package  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
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>
68 
69 template <typename DstDevice, typename SrcDevice>
71 
73 template <typename Device>
74 class Bitset {
75  public:
76  typedef Device execution_space;
77  typedef unsigned size_type;
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  typedef Kokkos::Impl::DeepCopy<typename execution_space::memory_space,
142  raw_deep_copy;
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  private:
238  KOKKOS_FORCEINLINE_FUNCTION
239  Kokkos::pair<bool, unsigned> find_any_helper(unsigned block_idx,
240  unsigned offset, unsigned block,
241  unsigned scan_direction) const {
242  Kokkos::pair<bool, unsigned> result(block > 0u, 0);
243 
244  if (!result.first) {
245  result.second = update_hint(block_idx, offset, scan_direction);
246  } else {
247  result.second =
248  scan_block((block_idx << block_shift), offset, block, scan_direction);
249  }
250  return result;
251  }
252 
253  KOKKOS_FORCEINLINE_FUNCTION
254  unsigned scan_block(unsigned block_start, int offset, unsigned block,
255  unsigned scan_direction) const {
256  offset = !(scan_direction & BIT_SCAN_REVERSE)
257  ? offset
258  : (offset + block_mask) & block_mask;
259  block = Impl::rotate_right(block, offset);
260  return (((!(scan_direction & BIT_SCAN_REVERSE)
261  ? Impl::bit_scan_forward(block)
262  : ::Kokkos::log2(block)) +
263  offset) &
264  block_mask) +
265  block_start;
266  }
267 
268  KOKKOS_FORCEINLINE_FUNCTION
269  unsigned update_hint(long long block_idx, unsigned offset,
270  unsigned scan_direction) const {
271  block_idx += scan_direction & MOVE_HINT_BACKWARD ? -1 : 1;
272  block_idx = block_idx >= 0 ? block_idx : m_blocks.extent(0) - 1;
273  block_idx =
274  block_idx < static_cast<long long>(m_blocks.extent(0)) ? block_idx : 0;
275 
276  return static_cast<unsigned>(block_idx) * block_size + offset;
277  }
278 
279  private:
280  unsigned m_size;
281  unsigned m_last_block_mask;
282  View<unsigned*, execution_space, MemoryTraits<RandomAccess> > m_blocks;
283 
284  private:
285  template <typename DDevice>
286  friend class Bitset;
287 
288  template <typename DDevice>
289  friend class ConstBitset;
290 
291  template <typename Bitset>
292  friend struct Impl::BitsetCount;
293 
294  template <typename DstDevice, typename SrcDevice>
295  friend void deep_copy(Bitset<DstDevice>& dst, Bitset<SrcDevice> const& src);
296 
297  template <typename DstDevice, typename SrcDevice>
298  friend void deep_copy(Bitset<DstDevice>& dst,
299  ConstBitset<SrcDevice> const& src);
300 };
301 
304 template <typename Device>
305 class ConstBitset {
306  public:
307  typedef Device execution_space;
308  typedef unsigned size_type;
309 
310  private:
311  enum { block_size = static_cast<unsigned>(sizeof(unsigned) * CHAR_BIT) };
312  enum { block_mask = block_size - 1u };
313  enum { block_shift = Kokkos::Impl::integral_power_of_two(block_size) };
314 
315  public:
316  ConstBitset() : m_size(0) {}
317 
318  ConstBitset(Bitset<Device> const& rhs)
319  : m_size(rhs.m_size), m_blocks(rhs.m_blocks) {}
320 
321  ConstBitset(ConstBitset<Device> const& rhs)
322  : m_size(rhs.m_size), m_blocks(rhs.m_blocks) {}
323 
324  ConstBitset<Device>& operator=(Bitset<Device> const& rhs) {
325  this->m_size = rhs.m_size;
326  this->m_blocks = rhs.m_blocks;
327 
328  return *this;
329  }
330 
331  ConstBitset<Device>& operator=(ConstBitset<Device> const& rhs) {
332  this->m_size = rhs.m_size;
333  this->m_blocks = rhs.m_blocks;
334 
335  return *this;
336  }
337 
338  KOKKOS_FORCEINLINE_FUNCTION
339  unsigned size() const { return m_size; }
340 
341  unsigned count() const {
342  Impl::BitsetCount<ConstBitset<Device> > f(*this);
343  return f.apply();
344  }
345 
346  KOKKOS_FORCEINLINE_FUNCTION
347  bool test(unsigned i) const {
348  if (i < m_size) {
349  const unsigned block = m_blocks[i >> block_shift];
350  const unsigned mask = 1u << static_cast<int>(i & block_mask);
351  return block & mask;
352  }
353  return false;
354  }
355 
356  private:
357  unsigned m_size;
358  View<const unsigned*, execution_space, MemoryTraits<RandomAccess> > m_blocks;
359 
360  private:
361  template <typename DDevice>
362  friend class ConstBitset;
363 
364  template <typename Bitset>
365  friend struct Impl::BitsetCount;
366 
367  template <typename DstDevice, typename SrcDevice>
368  friend void deep_copy(Bitset<DstDevice>& dst,
369  ConstBitset<SrcDevice> const& src);
370 
371  template <typename DstDevice, typename SrcDevice>
372  friend void deep_copy(ConstBitset<DstDevice>& dst,
373  ConstBitset<SrcDevice> const& src);
374 };
375 
376 template <typename DstDevice, typename SrcDevice>
377 void deep_copy(Bitset<DstDevice>& dst, Bitset<SrcDevice> const& src) {
378  if (dst.size() != src.size()) {
379  throw std::runtime_error(
380  "Error: Cannot deep_copy bitsets of different sizes!");
381  }
382 
383  typedef Kokkos::Impl::DeepCopy<typename DstDevice::memory_space,
384  typename SrcDevice::memory_space>
385  raw_deep_copy;
386  raw_deep_copy(dst.m_blocks.data(), src.m_blocks.data(),
387  sizeof(unsigned) * src.m_blocks.extent(0));
388 }
389 
390 template <typename DstDevice, typename SrcDevice>
391 void deep_copy(Bitset<DstDevice>& dst, ConstBitset<SrcDevice> const& src) {
392  if (dst.size() != src.size()) {
393  throw std::runtime_error(
394  "Error: Cannot deep_copy bitsets of different sizes!");
395  }
396 
397  typedef Kokkos::Impl::DeepCopy<typename DstDevice::memory_space,
398  typename SrcDevice::memory_space>
399  raw_deep_copy;
400  raw_deep_copy(dst.m_blocks.data(), src.m_blocks.data(),
401  sizeof(unsigned) * src.m_blocks.extent(0));
402 }
403 
404 template <typename DstDevice, typename SrcDevice>
405 void deep_copy(ConstBitset<DstDevice>& dst, ConstBitset<SrcDevice> const& src) {
406  if (dst.size() != src.size()) {
407  throw std::runtime_error(
408  "Error: Cannot deep_copy bitsets of different sizes!");
409  }
410 
411  typedef Kokkos::Impl::DeepCopy<typename DstDevice::memory_space,
412  typename SrcDevice::memory_space>
413  raw_deep_copy;
414  raw_deep_copy(dst.m_blocks.data(), src.m_blocks.data(),
415  sizeof(unsigned) * src.m_blocks.extent(0));
416 }
417 
418 } // namespace Kokkos
419 
420 #endif // KOKKOS_BITSET_HPP
A thread safe view to a bitset.
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 *=nullptr)
Deep copy a value from Host memory into a view.
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.
Definition: Kokkos_Pair.hpp:65
KOKKOS_FORCEINLINE_FUNCTION bool reset(unsigned i) const
unsigned count() const
KOKKOS_FORCEINLINE_FUNCTION bool test(unsigned i) const
Memory management for host memory.
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