6 #include <boost/multiprecision/integer.hpp> 14 : _size(asize), numWords(0), bits(NULL)
73 Q_ASSERT(offset>=0 && offset <
_size);
74 return bits[offset>>6] & ((uint64_t)1 << offset);
79 Q_ASSERT(offset>=0 && offset <
_size);
80 bits[offset>>6] |= ((uint64_t)1 << offset);
85 Q_ASSERT(offset>=0 && offset <
_size);
86 bits[offset>>6] &= ~((uint64_t)1 << offset);
91 Q_ASSERT(offset>=0 && offset <
_size);
93 uint64_t mask = ((uint64_t)1 << offset);
95 uint64_t old_value =
bits[i];
98 (
volatile int64_t*)&
bits[i],
100 (int64_t)(old_value|mask));
101 if (prev_value==old_value)
104 old_value=prev_value;
110 Q_ASSERT(offset>=0 && offset <
_size);
112 uint64_t mask = ~((uint64_t)1 << offset);
114 uint64_t old_value =
bits[i];
117 (
volatile int64_t*)&
bits[i],
119 (int64_t)(old_value&mask));
120 if (prev_value==old_value)
123 old_value=prev_value;
158 Q_ASSERT(index >= 0 && index <
_size);
160 uint64_t word =
bits[i] >> index;
176 Q_ASSERT(index >= 0 && index <
_size);
178 int subIndex = index & 0x3f;
179 uint64_t word =
bits[i];
180 word <<= (63-subIndex);
207 return (parent==that.
parent) &&
208 ((!valid() && !that.
valid()) || (_offset==that.
_offset));
213 return (_offset>=0) && (_offset < parent->_size);
222 _offset = parent->next(_offset+1);
228 _offset = parent->next(_offset+1);
233 _offset = parent->prev(_offset-1);
239 _offset = parent->prev(_offset-1);
244 while((_offset < parent->
_size) && (n-- > 0))
245 _offset = parent->next(_offset+1);
256 while((_offset >= 0) && (n-- > 0))
257 _offset = parent->prev(_offset-1);
269 Q_ASSERT(valid() && that.
valid());
270 Q_ASSERT(parent == that.
parent);
287 #pragma intrinsic(_BitScanForward64) 288 #pragma intrinsic(_BitScanReverse64) 289 #pragma intrinsic(__popcnt64) 290 #pragma intrinsic(_InterlockedCompareExchange64) 301 return __sync_val_compare_and_swap (value, old_value, update_value);
302 #elif defined _MSC_VER 307 return _InterlockedCompareExchange64(value,update_value,old_value);
318 return boost::multiprecision::lsb(word);
326 return 63 - boost::multiprecision::msb(word);
332 return __builtin_popcountll (word);
333 #elif defined _MSC_VER 334 return __popcnt64(word);
void swap(gpuword **A, gpuword **B)
~BitSet()
destructor, releases all data
an iterator over a BitSet
iterator & operator-=(int n)
skip operator
static int numberOfTrailingZeros(uint64_t word)
compute number of trailing zeros in a 64 bit word
static int64_t compare_and_swap(volatile int64_t *value, int64_t old_value, int64_t update_value)
atomic compare-and-swap
global definitions for all algorithms.
iterator operator-(int n)
skip operator
int next(int index) const
find next index with a set (true) bit
void remove(int offset)
assign false
iterator & operator+=(int n)
skip operator
iterator operator+(int n) const
skip operator
void stealBits(BitSet &&that)
steal data
int numWords
number of allocated words (1 word = 64 bits)
void clear()
assign false to all bits
void remove_lf(int offset)
lock-free add operator; not used and not tested!
int prev(int off) const
find previos index with a set (true) bit
bool contains(int offset) const
static int numberOfLeadingZeros(uint64_t word)
compute number of leading zeros in a 64 bit word
void add(int offset)
assign true
iterator & operator--()
pre-decrement; move to the previous set (true) bit
int _offset
current offset
BitSet & operator=(const BitSet &that)
assigment operator
static int bitCount(uint64_t word)
compute number of set bits in a 64 bit word
void copyBits(const BitSet &that)
copy data
iterator()
empty constructor; creates an invalid iterator
A simple bit vector of fixed size.
BitSet()
default constructor; creates an empty set
iterator & operator=(const iterator &that)
assignment operator
BitSet & swap(BitSet &that)
swap contents with other object
int _size
number of valid bits
bool operator==(const iterator &that) const
equality comparator
int count() const
This methods is expensive, as it scans the whole array.
void add_lf(int offset)
lock-free add operator; not used and not tested!
const BitSet * parent
parent BitSet
iterator & operator++()
pre-increment; move to the next set (true) bit