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. 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 Christian R. Trott (crtrott@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 
110  KOKKOS_INLINE_FUNCTION
111  Bitset (const Bitset<Device>&) = default;
112 
113  KOKKOS_INLINE_FUNCTION
114  Bitset& operator= (const Bitset<Device>&) = default;
115 
116  KOKKOS_INLINE_FUNCTION
117  Bitset (Bitset<Device>&&) = default;
118 
119  KOKKOS_INLINE_FUNCTION
120  Bitset& operator= (Bitset<Device>&&) = default;
121 
122  KOKKOS_INLINE_FUNCTION
123  ~Bitset () = default;
124 
127  KOKKOS_FORCEINLINE_FUNCTION
128  unsigned size() const
129  { return m_size; }
130 
133  unsigned count() const
134  {
135  Impl::BitsetCount< Bitset<Device> > f(*this);
136  return f.apply();
137  }
138 
141  void set()
142  {
143  Kokkos::deep_copy(m_blocks, ~0u );
144 
145  if (m_last_block_mask) {
146  //clear the unused bits in the last block
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));
149  }
150  }
151 
154  void reset()
155  {
156  Kokkos::deep_copy(m_blocks, 0u );
157  }
158 
161  void clear()
162  {
163  Kokkos::deep_copy(m_blocks, 0u );
164  }
165 
168  KOKKOS_FORCEINLINE_FUNCTION
169  bool set( unsigned i ) const
170  {
171  if ( i < m_size ) {
172  unsigned * block_ptr = &m_blocks[ i >> block_shift ];
173  const unsigned mask = 1u << static_cast<int>( i & block_mask );
174 
175  return !( atomic_fetch_or( block_ptr, mask ) & mask );
176  }
177  return false;
178  }
179 
182  KOKKOS_FORCEINLINE_FUNCTION
183  bool reset( unsigned i ) const
184  {
185  if ( i < m_size ) {
186  unsigned * block_ptr = &m_blocks[ i >> block_shift ];
187  const unsigned mask = 1u << static_cast<int>( i & block_mask );
188 
189  return atomic_fetch_and( block_ptr, ~mask ) & mask;
190  }
191  return false;
192  }
193 
196  KOKKOS_FORCEINLINE_FUNCTION
197  bool test( unsigned i ) const
198  {
199  if ( i < m_size ) {
200  const unsigned block = volatile_load(&m_blocks[ i >> block_shift ]);
201  const unsigned mask = 1u << static_cast<int>( i & block_mask );
202  return block & mask;
203  }
204  return false;
205  }
206 
210  KOKKOS_FORCEINLINE_FUNCTION
211  unsigned max_hint() const
212  {
213  return m_blocks.extent(0);
214  }
215 
219  KOKKOS_INLINE_FUNCTION
220  Kokkos::pair<bool, unsigned> find_any_set_near( unsigned hint , unsigned scan_direction = BIT_SCAN_FORWARD_MOVE_HINT_FORWARD ) const
221  {
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 ;
226 
227  return find_any_helper(block_idx, offset, block, scan_direction);
228  }
229 
233  KOKKOS_INLINE_FUNCTION
234  Kokkos::pair<bool, unsigned> find_any_unset_near( unsigned hint , unsigned scan_direction = BIT_SCAN_FORWARD_MOVE_HINT_FORWARD ) const
235  {
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 ;
240 
241  return find_any_helper(block_idx, offset, block, scan_direction);
242  }
243 
244 private:
245 
246  KOKKOS_FORCEINLINE_FUNCTION
247  Kokkos::pair<bool, unsigned> find_any_helper(unsigned block_idx, unsigned offset, unsigned block, unsigned scan_direction) const
248  {
249  Kokkos::pair<bool, unsigned> result( block > 0u, 0);
250 
251  if (!result.first) {
252  result.second = update_hint( block_idx, offset, scan_direction );
253  }
254  else {
255  result.second = scan_block( (block_idx << block_shift)
256  , offset
257  , block
258  , scan_direction
259  );
260  }
261  return result;
262  }
263 
264 
265  KOKKOS_FORCEINLINE_FUNCTION
266  unsigned scan_block(unsigned block_start, int offset, unsigned block, unsigned scan_direction ) const
267  {
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)
273  ) + offset
274  ) & block_mask
275  ) + block_start;
276  }
277 
278  KOKKOS_FORCEINLINE_FUNCTION
279  unsigned update_hint( long long block_idx, unsigned offset, unsigned scan_direction ) const
280  {
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;
284 
285  return static_cast<unsigned>(block_idx)*block_size + offset;
286  }
287 
288 private:
289 
290  unsigned m_size;
291  unsigned m_last_block_mask;
292  View< unsigned *, execution_space, MemoryTraits<RandomAccess> > m_blocks;
293 
294 private:
295  template <typename DDevice>
296  friend class Bitset;
297 
298  template <typename DDevice>
299  friend class ConstBitset;
300 
301  template <typename Bitset>
302  friend struct Impl::BitsetCount;
303 
304  template <typename DstDevice, typename SrcDevice>
305  friend void deep_copy( Bitset<DstDevice> & dst, Bitset<SrcDevice> const& src);
306 
307  template <typename DstDevice, typename SrcDevice>
308  friend void deep_copy( Bitset<DstDevice> & dst, ConstBitset<SrcDevice> const& src);
309 };
310 
313 template <typename Device>
314 class ConstBitset
315 {
316 public:
317  typedef Device execution_space;
318  typedef unsigned size_type;
319 
320 private:
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) };
324 
325 public:
326  ConstBitset()
327  : m_size (0)
328  {}
329 
330  ConstBitset(Bitset<Device> const& rhs)
331  : m_size(rhs.m_size)
332  , m_blocks(rhs.m_blocks)
333  {}
334 
335  ConstBitset(ConstBitset<Device> const& rhs)
336  : m_size( rhs.m_size )
337  , m_blocks( rhs.m_blocks )
338  {}
339 
340  ConstBitset<Device> & operator = (Bitset<Device> const & rhs)
341  {
342  this->m_size = rhs.m_size;
343  this->m_blocks = rhs.m_blocks;
344 
345  return *this;
346  }
347 
348  ConstBitset<Device> & operator = (ConstBitset<Device> const & rhs)
349  {
350  this->m_size = rhs.m_size;
351  this->m_blocks = rhs.m_blocks;
352 
353  return *this;
354  }
355 
356 
357  KOKKOS_FORCEINLINE_FUNCTION
358  unsigned size() const
359  {
360  return m_size;
361  }
362 
363  unsigned count() const
364  {
365  Impl::BitsetCount< ConstBitset<Device> > f(*this);
366  return f.apply();
367  }
368 
369  KOKKOS_FORCEINLINE_FUNCTION
370  bool test( unsigned i ) const
371  {
372  if ( i < m_size ) {
373  const unsigned block = m_blocks[ i >> block_shift ];
374  const unsigned mask = 1u << static_cast<int>( i & block_mask );
375  return block & mask;
376  }
377  return false;
378  }
379 
380 private:
381 
382  unsigned m_size;
383  View< const unsigned *, execution_space, MemoryTraits<RandomAccess> > m_blocks;
384 
385 private:
386  template <typename DDevice>
387  friend class ConstBitset;
388 
389  template <typename Bitset>
390  friend struct Impl::BitsetCount;
391 
392  template <typename DstDevice, typename SrcDevice>
393  friend void deep_copy( Bitset<DstDevice> & dst, ConstBitset<SrcDevice> const& src);
394 
395  template <typename DstDevice, typename SrcDevice>
396  friend void deep_copy( ConstBitset<DstDevice> & dst, ConstBitset<SrcDevice> const& src);
397 };
398 
399 
400 template <typename DstDevice, typename SrcDevice>
401 void deep_copy( Bitset<DstDevice> & dst, Bitset<SrcDevice> const& src)
402 {
403  if (dst.size() != src.size()) {
404  throw std::runtime_error("Error: Cannot deep_copy bitsets of different sizes!");
405  }
406 
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));
409 }
410 
411 template <typename DstDevice, typename SrcDevice>
412 void deep_copy( Bitset<DstDevice> & dst, ConstBitset<SrcDevice> const& src)
413 {
414  if (dst.size() != src.size()) {
415  throw std::runtime_error("Error: Cannot deep_copy bitsets of different sizes!");
416  }
417 
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));
420 }
421 
422 template <typename DstDevice, typename SrcDevice>
423 void deep_copy( ConstBitset<DstDevice> & dst, ConstBitset<SrcDevice> const& src)
424 {
425  if (dst.size() != src.size()) {
426  throw std::runtime_error("Error: Cannot deep_copy bitsets of different sizes!");
427  }
428 
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));
431 }
432 
433 } // namespace Kokkos
434 
435 #endif //KOKKOS_BITSET_HPP
436 
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.
Definition: Kokkos_Pair.hpp:64
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
unsigned count() 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