Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
bitset.cpp
Go to the documentation of this file.
1 
2 #include <data/bitset.h>
3 
4 #include <memory.h>
5 #include <qglobal.h>
6 #include <boost/multiprecision/integer.hpp>
7 
8 using namespace frechet;
9 using namespace data;
10 
12 
13 BitSet::BitSet(int asize)
14  : _size(asize), numWords(0), bits(NULL)
15 {
16  if (_size > 0) {
17  numWords = (_size+63)/64;
18  bits = new uint64_t[numWords];
19  clear();
20  }
21 }
22 
23 //BitSet::BitSet(BitSet&& that)
24 //{
25 // stealBits(that);
26 //}
27 
28 BitSet::BitSet(const BitSet& that) : bits(NULL)
29 {
30  copyBits(that);
31 }
32 
34 {
35  delete bits;
36 }
37 
39 {
40  copyBits(that);
41  return *this;
42 }
43 
45  std::swap(_size,that._size);
47  std::swap(bits,that.bits);
48  return *this;
49 }
50 
51 //BitSet& BitSet::operator=(BitSet&& that) {
52 // stealBits(that);
53 // return *this;
54 //}
55 
56 int BitSet::size() const { return _size; }
57 
58 int BitSet::count() const
59 {
60  int popCount = 0;
61  for (int i = 0; i < numWords; ++i) {
62  popCount += bitCount(bits[i]);
63  }
64  return popCount;
65 }
66 
67 void BitSet::clear() {
68  memset(bits,0,sizeof(uint64_t)*numWords);
69 }
70 
71 bool BitSet::contains(int offset) const
72 {
73  Q_ASSERT(offset>=0 && offset < _size);
74  return bits[offset>>6] & ((uint64_t)1 << offset);
75 }
76 
77 void BitSet::add(int offset)
78 {
79  Q_ASSERT(offset>=0 && offset < _size);
80  bits[offset>>6] |= ((uint64_t)1 << offset);
81 }
82 
83 void BitSet::remove(int offset)
84 {
85  Q_ASSERT(offset>=0 && offset < _size);
86  bits[offset>>6] &= ~((uint64_t)1 << offset);
87 }
88 
89 void BitSet::add_lf(int offset)
90 {
91  Q_ASSERT(offset>=0 && offset < _size);
92  int i = offset>>6;
93  uint64_t mask = ((uint64_t)1 << offset);
94 
95  uint64_t old_value = bits[i]; // when reading this value, do we need a memory barrier?
96  for(;;) {
97  uint64_t prev_value = compare_and_swap(
98  (volatile int64_t*)&bits[i],
99  (int64_t)old_value,
100  (int64_t)(old_value|mask));
101  if (prev_value==old_value)
102  return;
103  else
104  old_value=prev_value;
105  }
106 }
107 
108 void BitSet::remove_lf(int offset)
109 {
110  Q_ASSERT(offset>=0 && offset < _size);
111  int i = offset>>6;
112  uint64_t mask = ~((uint64_t)1 << offset);
113 
114  uint64_t old_value = bits[i]; // volatile, memory barrier?
115  for(;;) {
116  uint64_t prev_value = compare_and_swap(
117  (volatile int64_t*)&bits[i],
118  (int64_t)old_value,
119  (int64_t)(old_value&mask));
120  if (prev_value==old_value)
121  return;
122  else
123  old_value=prev_value;
124  }
125 }
126 
127 
128 BitSet::iterator BitSet::begin() const { return iterator(this,0); }
129 
130 void BitSet::copyBits(const BitSet &that)
131 {
132  delete bits;
133  _size = that._size;
134  numWords = that.numWords;
135  if (numWords > 0) {
136  bits = new uint64_t[numWords];
137  memcpy(bits,that.bits,numWords*sizeof(uint64_t));
138  }
139  else {
140  bits = NULL;
141  }
142 }
143 
144 void BitSet::stealBits(BitSet&& that) {
145  bits = that.bits;
146  _size = that._size;
147  numWords = that.numWords;
148  that.bits = NULL;
149 }
150 
151 int BitSet::next(int index) const
152 {
153  if (index >= _size)
154  return index;
155  if (index < 0)
156  index = 0;
157 
158  Q_ASSERT(index >= 0 && index < _size);
159  int i = index >> 6;
160  uint64_t word = bits[i] >> index; // skip all the bits to the right of index
161 
162  if (word!=0)
163  return index + numberOfTrailingZeros(word);
164 
165  while(++i < numWords) {
166  word = bits[i];
167  if (word != 0)
168  return (i<<6) + numberOfTrailingZeros(word);
169  }
170 
171  return _size;
172 }
173 
174 int BitSet::prev(int index) const
175 {
176  Q_ASSERT(index >= 0 && index < _size);
177  int i = index >> 6;
178  int subIndex = index & 0x3f; // index within the word
179  uint64_t word = bits[i]; // skip all the bits to the left of index
180  word <<= (63-subIndex);
181 
182  if (word != 0) {
183  return (i << 6) + subIndex - numberOfLeadingZeros(word);
184  }
185 
186  while (--i >= 0) {
187  word = bits[i];
188  if (word !=0 ) {
189  return (i << 6) + 63 - numberOfLeadingZeros(word);
190  }
191  }
192  return -1;
193 }
194 
195 
196 BitSet::iterator::iterator() : parent(NULL), _offset(0) { }
197 
198 BitSet::iterator::iterator(const BitSet::iterator &that) : parent(that.parent), _offset(that._offset) { }
199 
201  parent = that.parent;
202  _offset = that._offset;
203  return *this;
204 }
205 
207  return (parent==that.parent) &&
208  ((!valid() && !that.valid()) || (_offset==that._offset));
209 }
210 
212 {
213  return (_offset>=0) && (_offset < parent->_size);
214 }
215 
217 {
218  return _offset;
219 }
220 
222  _offset = parent->next(_offset+1);
223  return *this;
224 }
225 
227  iterator it = *this;
228  _offset = parent->next(_offset+1);
229  return it;
230 }
231 
233  _offset = parent->prev(_offset-1);
234  return *this;
235 }
236 
238  iterator it = *this;
239  _offset = parent->prev(_offset-1);
240  return it;
241 }
242 
244  while((_offset < parent->_size) && (n-- > 0))
245  _offset = parent->next(_offset+1);
246  return *this;
247 }
248 
250  iterator it = *this;
251  it += n;
252  return it;
253 }
254 
256  while((_offset >= 0) && (n-- > 0))
257  _offset = parent->prev(_offset-1);
258  return *this;
259 }
260 
262  iterator it = *this;
263  it -= n;
264  return it;
265 }
266 
268 {
269  Q_ASSERT(valid() && that.valid());
270  Q_ASSERT(parent == that.parent);
271  return _offset - that._offset;
272 }
273 
274 
275 BitSet::iterator::iterator(const BitSet *aparent, int start)
276  : parent(aparent)
277 {
278  if (start >= parent->_size)
279  _offset = parent->_size;
280  else
281  _offset = parent->next(start);
282 }
283 
284 
285 #ifdef _MSC_VER
286 #include <intrin.h>
287 #pragma intrinsic(_BitScanForward64)
288 #pragma intrinsic(_BitScanReverse64)
289 #pragma intrinsic(__popcnt64)
290 #pragma intrinsic(_InterlockedCompareExchange64)
291 #endif
292 
298 int64_t BitSet::compare_and_swap(volatile int64_t* value, int64_t old_value, int64_t update_value)
299 {
300 #if defined __GNUC__
301  return __sync_val_compare_and_swap (value, old_value, update_value);
302 #elif defined _MSC_VER
303  // Destination = value
304  // Comparand = old_value
305  // Exchange = new value
306  // returns actual value of *Destination
307  return _InterlockedCompareExchange64(value,update_value,old_value);
308 #else
309 # error
310 #endif
311 }
312 
314 {
315  if (word == 0)
316  return 64;
317  else
318  return boost::multiprecision::lsb(word);
319 }
320 
322 {
323  if (word == 0)
324  return 64;
325  else
326  return 63 - boost::multiprecision::msb(word);
327 }
328 
329 int BitSet::bitCount(uint64_t word)
330 {
331 #if defined __GNUC__
332  return __builtin_popcountll (word);
333 #elif defined _MSC_VER
334  return __popcnt64(word);
335 #else
336 # error
337 #endif
338 }
void swap(gpuword **A, gpuword **B)
~BitSet()
destructor, releases all data
Definition: bitset.cpp:33
an iterator over a BitSet
Definition: bitset.h:93
iterator & operator-=(int n)
skip operator
Definition: bitset.cpp:255
static int numberOfTrailingZeros(uint64_t word)
compute number of trailing zeros in a 64 bit word
Definition: bitset.cpp:313
iterator begin() const
Definition: bitset.cpp:128
static int64_t compare_and_swap(volatile int64_t *value, int64_t old_value, int64_t update_value)
atomic compare-and-swap
Definition: bitset.cpp:298
global definitions for all algorithms.
iterator operator-(int n)
skip operator
Definition: bitset.cpp:261
int next(int index) const
find next index with a set (true) bit
Definition: bitset.cpp:151
void remove(int offset)
assign false
Definition: bitset.cpp:83
iterator & operator+=(int n)
skip operator
Definition: bitset.cpp:243
iterator operator+(int n) const
skip operator
Definition: bitset.cpp:249
void stealBits(BitSet &&that)
steal data
Definition: bitset.cpp:144
int numWords
number of allocated words (1 word = 64 bits)
Definition: bitset.h:21
void clear()
assign false to all bits
Definition: bitset.cpp:67
uint64_t * bits
bit data
Definition: bitset.h:23
void remove_lf(int offset)
lock-free add operator; not used and not tested!
Definition: bitset.cpp:108
int prev(int off) const
find previos index with a set (true) bit
Definition: bitset.cpp:174
bool contains(int offset) const
Definition: bitset.cpp:71
static int numberOfLeadingZeros(uint64_t word)
compute number of leading zeros in a 64 bit word
Definition: bitset.cpp:321
void add(int offset)
assign true
Definition: bitset.cpp:77
iterator & operator--()
pre-decrement; move to the previous set (true) bit
Definition: bitset.cpp:232
int _offset
current offset
Definition: bitset.h:158
BitSet & operator=(const BitSet &that)
assigment operator
Definition: bitset.cpp:38
static int bitCount(uint64_t word)
compute number of set bits in a 64 bit word
Definition: bitset.cpp:329
void copyBits(const BitSet &that)
copy data
Definition: bitset.cpp:130
iterator()
empty constructor; creates an invalid iterator
Definition: bitset.cpp:196
A simple bit vector of fixed size.
Definition: bitset.h:16
BitSet()
default constructor; creates an empty set
Definition: bitset.cpp:11
iterator & operator=(const iterator &that)
assignment operator
Definition: bitset.cpp:200
BitSet & swap(BitSet &that)
swap contents with other object
Definition: bitset.cpp:44
int _size
number of valid bits
Definition: bitset.h:19
bool operator==(const iterator &that) const
equality comparator
Definition: bitset.cpp:206
int count() const
This methods is expensive, as it scans the whole array.
Definition: bitset.cpp:58
void add_lf(int offset)
lock-free add operator; not used and not tested!
Definition: bitset.cpp:89
int size() const
Definition: bitset.cpp:56
const BitSet * parent
parent BitSet
Definition: bitset.h:156
iterator & operator++()
pre-increment; move to the next set (true) bit
Definition: bitset.cpp:221