Kokkos Core Kernels Package  Version of the Day
Kokkos_Bitset.hpp
1 /*
2 //@HEADER
3 // ************************************************************************
4 //
5 // Kokkos v. 2.0
6 // Copyright (2014) Sandia Corporation
7 //
8 // Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
9 // the U.S. Government retains certain rights in this software.
10 //
11 // Redistribution and use in source and binary forms, with or without
12 // modification, are permitted provided that the following conditions are
13 // met:
14 //
15 // 1. Redistributions of source code must retain the above copyright
16 // notice, this list of conditions and the following disclaimer.
17 //
18 // 2. Redistributions in binary form must reproduce the above copyright
19 // notice, this list of conditions and the following disclaimer in the
20 // documentation and/or other materials provided with the distribution.
21 //
22 // 3. Neither the name of the Corporation nor the names of the
23 // contributors may be used to endorse or promote products derived from
24 // this software without specific prior written permission.
25 //
26 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
27 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
30 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
31 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
32 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37 //
38 // Questions? Contact H. Carter Edwards (hcedwar@sandia.gov)
39 //
40 // ************************************************************************
41 //@HEADER
42 */
43 
44 #ifndef KOKKOS_BITSET_HPP
45 #define KOKKOS_BITSET_HPP
46 
47 #include <Kokkos_Core.hpp>
48 #include <Kokkos_Functional.hpp>
49 
50 #include <impl/Kokkos_Bitset_impl.hpp>
51 
52 #include <stdexcept>
53 
54 namespace Kokkos {
55 
56 template <typename Device = Kokkos::DefaultExecutionSpace >
57 class Bitset;
58 
59 template <typename Device = Kokkos::DefaultExecutionSpace >
61 
62 template <typename DstDevice, typename SrcDevice>
63 void deep_copy( Bitset<DstDevice> & dst, Bitset<SrcDevice> const& src);
64 
65 template <typename DstDevice, typename SrcDevice>
66 void deep_copy( Bitset<DstDevice> & dst, ConstBitset<SrcDevice> const& src);
67 
68 template <typename DstDevice, typename SrcDevice>
70 
71 
73 template <typename Device>
74 class Bitset
75 {
76 public:
77  typedef Device execution_space;
78  typedef unsigned size_type;
79 
80  enum { BIT_SCAN_REVERSE = 1u };
81  enum { MOVE_HINT_BACKWARD = 2u };
82 
83  enum {
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
88  };
89 
90 private:
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) };
94 
95 public:
96 
97 
100  Bitset(unsigned arg_size = 0u)
101  : m_size(arg_size)
102  , m_last_block_mask(0u)
103  , m_blocks("Bitset", ((m_size + block_mask) >> block_shift) )
104  {
105  for (int i=0, end = static_cast<int>(m_size & block_mask); i < end; ++i) {
106  m_last_block_mask |= 1u << i;
107  }
108  }
109 
112  {
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;
116 
117  return *this;
118  }
119 
121  Bitset( Bitset<Device> const & rhs)
122  : m_size( rhs.m_size )
123  , m_last_block_mask( rhs.m_last_block_mask )
124  , m_blocks( rhs.m_blocks )
125  {}
126 
129  KOKKOS_FORCEINLINE_FUNCTION
130  unsigned size() const
131  { return m_size; }
132 
135  unsigned count() const
136  {
137  Impl::BitsetCount< Bitset<Device> > f(*this);
138  return f.apply();
139  }
140 
143  void set()
144  {
145  Kokkos::deep_copy(m_blocks, ~0u );
146 
147  if (m_last_block_mask) {
148  //clear the unused bits in the last block
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));
151  }
152  }
153 
156  void reset()
157  {
158  Kokkos::deep_copy(m_blocks, 0u );
159  }
160 
163  void clear()
164  {
165  Kokkos::deep_copy(m_blocks, 0u );
166  }
167 
170  KOKKOS_FORCEINLINE_FUNCTION
171  bool set( unsigned i ) const
172  {
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_or( block_ptr, mask ) & mask );
178  }
179  return false;
180  }
181 
184  KOKKOS_FORCEINLINE_FUNCTION
185  bool reset( unsigned i ) const
186  {
187  if ( i < m_size ) {
188  unsigned * block_ptr = &m_blocks[ i >> block_shift ];
189  const unsigned mask = 1u << static_cast<int>( i & block_mask );
190 
191  return atomic_fetch_and( block_ptr, ~mask ) & mask;
192  }
193  return false;
194  }
195 
198  KOKKOS_FORCEINLINE_FUNCTION
199  bool test( unsigned i ) const
200  {
201  if ( i < m_size ) {
202  const unsigned block = volatile_load(&m_blocks[ i >> block_shift ]);
203  const unsigned mask = 1u << static_cast<int>( i & block_mask );
204  return block & mask;
205  }
206  return false;
207  }
208 
212  KOKKOS_FORCEINLINE_FUNCTION
213  unsigned max_hint() const
214  {
215  return m_blocks.dimension_0();
216  }
217 
221  KOKKOS_INLINE_FUNCTION
222  Kokkos::pair<bool, unsigned> find_any_set_near( unsigned hint , unsigned scan_direction = BIT_SCAN_FORWARD_MOVE_HINT_FORWARD ) const
223  {
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 ;
228 
229  return find_any_helper(block_idx, offset, block, scan_direction);
230  }
231 
235  KOKKOS_INLINE_FUNCTION
236  Kokkos::pair<bool, unsigned> find_any_unset_near( unsigned hint , unsigned scan_direction = BIT_SCAN_FORWARD_MOVE_HINT_FORWARD ) const
237  {
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 ;
242 
243  return find_any_helper(block_idx, offset, block, scan_direction);
244  }
245 
246 private:
247 
248  KOKKOS_FORCEINLINE_FUNCTION
249  Kokkos::pair<bool, unsigned> find_any_helper(unsigned block_idx, unsigned offset, unsigned block, unsigned scan_direction) const
250  {
251  Kokkos::pair<bool, unsigned> result( block > 0u, 0);
252 
253  if (!result.first) {
254  result.second = update_hint( block_idx, offset, scan_direction );
255  }
256  else {
257  result.second = scan_block( (block_idx << block_shift)
258  , offset
259  , block
260  , scan_direction
261  );
262  }
263  return result;
264  }
265 
266 
267  KOKKOS_FORCEINLINE_FUNCTION
268  unsigned scan_block(unsigned block_start, int offset, unsigned block, unsigned scan_direction ) const
269  {
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)
275  ) + offset
276  ) & block_mask
277  ) + block_start;
278  }
279 
280  KOKKOS_FORCEINLINE_FUNCTION
281  unsigned update_hint( long long block_idx, unsigned offset, unsigned scan_direction ) const
282  {
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;
286 
287  return static_cast<unsigned>(block_idx)*block_size + offset;
288  }
289 
290 private:
291 
292  unsigned m_size;
293  unsigned m_last_block_mask;
294  View< unsigned *, execution_space, MemoryTraits<RandomAccess> > m_blocks;
295 
296 private:
297  template <typename DDevice>
298  friend class Bitset;
299 
300  template <typename DDevice>
301  friend class ConstBitset;
302 
303  template <typename Bitset>
304  friend struct Impl::BitsetCount;
305 
306  template <typename DstDevice, typename SrcDevice>
307  friend void deep_copy( Bitset<DstDevice> & dst, Bitset<SrcDevice> const& src);
308 
309  template <typename DstDevice, typename SrcDevice>
310  friend void deep_copy( Bitset<DstDevice> & dst, ConstBitset<SrcDevice> const& src);
311 };
312 
315 template <typename Device>
316 class ConstBitset
317 {
318 public:
319  typedef Device execution_space;
320  typedef unsigned size_type;
321 
322 private:
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) };
326 
327 public:
328  ConstBitset()
329  : m_size (0)
330  {}
331 
332  ConstBitset(Bitset<Device> const& rhs)
333  : m_size(rhs.m_size)
334  , m_blocks(rhs.m_blocks)
335  {}
336 
337  ConstBitset(ConstBitset<Device> const& rhs)
338  : m_size( rhs.m_size )
339  , m_blocks( rhs.m_blocks )
340  {}
341 
342  ConstBitset<Device> & operator = (Bitset<Device> const & rhs)
343  {
344  this->m_size = rhs.m_size;
345  this->m_blocks = rhs.m_blocks;
346 
347  return *this;
348  }
349 
350  ConstBitset<Device> & operator = (ConstBitset<Device> const & rhs)
351  {
352  this->m_size = rhs.m_size;
353  this->m_blocks = rhs.m_blocks;
354 
355  return *this;
356  }
357 
358 
359  KOKKOS_FORCEINLINE_FUNCTION
360  unsigned size() const
361  {
362  return m_size;
363  }
364 
365  unsigned count() const
366  {
367  Impl::BitsetCount< ConstBitset<Device> > f(*this);
368  return f.apply();
369  }
370 
371  KOKKOS_FORCEINLINE_FUNCTION
372  bool test( unsigned i ) const
373  {
374  if ( i < m_size ) {
375  const unsigned block = m_blocks[ i >> block_shift ];
376  const unsigned mask = 1u << static_cast<int>( i & block_mask );
377  return block & mask;
378  }
379  return false;
380  }
381 
382 private:
383 
384  unsigned m_size;
385  View< const unsigned *, execution_space, MemoryTraits<RandomAccess> > m_blocks;
386 
387 private:
388  template <typename DDevice>
389  friend class ConstBitset;
390 
391  template <typename Bitset>
392  friend struct Impl::BitsetCount;
393 
394  template <typename DstDevice, typename SrcDevice>
395  friend void deep_copy( Bitset<DstDevice> & dst, ConstBitset<SrcDevice> const& src);
396 
397  template <typename DstDevice, typename SrcDevice>
398  friend void deep_copy( ConstBitset<DstDevice> & dst, ConstBitset<SrcDevice> const& src);
399 };
400 
401 
402 template <typename DstDevice, typename SrcDevice>
403 void deep_copy( Bitset<DstDevice> & dst, Bitset<SrcDevice> const& src)
404 {
405  if (dst.size() != src.size()) {
406  throw std::runtime_error("Error: Cannot deep_copy bitsets of different sizes!");
407  }
408 
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());
411 }
412 
413 template <typename DstDevice, typename SrcDevice>
414 void deep_copy( Bitset<DstDevice> & dst, ConstBitset<SrcDevice> const& src)
415 {
416  if (dst.size() != src.size()) {
417  throw std::runtime_error("Error: Cannot deep_copy bitsets of different sizes!");
418  }
419 
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());
422 }
423 
424 template <typename DstDevice, typename SrcDevice>
425 void deep_copy( ConstBitset<DstDevice> & dst, ConstBitset<SrcDevice> const& src)
426 {
427  if (dst.size() != src.size()) {
428  throw std::runtime_error("Error: Cannot deep_copy bitsets of different sizes!");
429  }
430 
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());
433 }
434 
435 } // namespace Kokkos
436 
437 #endif //KOKKOS_BITSET_HPP
A thread safe view to a bitset.
KOKKOS_FORCEINLINE_FUNCTION unsigned max_hint() const
Bitset(unsigned arg_size=0u)
Bitset(Bitset< Device > const &rhs)
copy constructor
unsigned count() const
Replacement for std::pair that works on CUDA devices.
Definition: Kokkos_Pair.hpp:64
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_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
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.
Bitset< Device > & operator=(Bitset< Device > const &rhs)
assignment
KOKKOS_FORCEINLINE_FUNCTION bool reset(unsigned i) const