6 #ifndef TURI_DENSE_BITSET_HPP 7 #define TURI_DENSE_BITSET_HPP 14 #include <core/storage/serialization/serialization_includes.hpp> 15 #include <core/parallel/atomic_ops.hpp> 16 #include <core/util/bitops.hpp> 51 memcpy(array, db.array,
sizeof(
size_t) * arrlen);
65 size_t prev_arrlen = arrlen;
66 arrlen = (n / (
sizeof(size_t) * 8)) + (n % (
sizeof(
size_t) * 8) > 0);
67 array = (
size_t*)realloc(array,
sizeof(
size_t) * arrlen);
71 if (arrlen > prev_arrlen) {
74 std::fill(&array[prev_arrlen], &array[arrlen], 0);
80 std::fill(&array[0], &array[arrlen], 0);
83 inline bool empty()
const {
84 for (
size_t i = 0; i < arrlen; ++i)
if (array[i])
return false;
90 for (
size_t i = 0;i < arrlen; ++i) array[i] = (
size_t) - 1;
96 __builtin_prefetch(&(array[b / (8 *
sizeof(
size_t))]));
100 inline bool get(
size_t b)
const{
101 size_t arrpos, bitpos;
102 bit_to_pos(b, arrpos, bitpos);
103 return array[arrpos] & (size_t(1) << size_t(bitpos));
109 size_t arrpos, bitpos;
110 bit_to_pos(b, arrpos, bitpos);
111 const size_t mask(
size_t(1) <<
size_t(bitpos));
112 return __sync_fetch_and_or(array + arrpos, mask) & mask;
118 size_t arrpos, bitpos;
119 bit_to_pos(b, arrpos, bitpos);
120 const size_t mask(
size_t(1) <<
size_t(bitpos));
121 return __sync_fetch_and_xor(array + arrpos, mask) & mask;
126 size_t arrpos, bitpos;
127 bit_to_pos(b, arrpos, bitpos);
128 return array[arrpos];
133 size_t arrpos, bitpos;
134 bit_to_pos(b, arrpos, bitpos);
167 ASSERT_EQ(other.len, len);
168 ASSERT_EQ(other.arrlen, arrlen);
169 size_t arrpos, bitpos;
170 bit_to_pos(start, arrpos, bitpos);
171 size_t initial_arrpos = arrpos;
172 if (arrpos >= arrlen) arrpos = 0;
174 size_t transferred = 0;
175 while(transferred < b) {
176 if (other.array[arrpos] > 0) {
178 array[arrpos] |= other.array[arrpos];
179 other.array[arrpos] = 0;
182 if (arrpos >= other.arrlen) arrpos = 0;
183 else if (arrpos == initial_arrpos)
break;
185 start = 8 *
sizeof(size_t) * arrpos;
196 size_t arrpos, bitpos;
197 bit_to_pos(b, arrpos, bitpos);
198 const size_t mask(
size_t(1) <<
size_t(bitpos));
199 bool ret = array[arrpos] & mask;
200 array[arrpos] |= mask;
205 inline bool set(
size_t b,
bool value) {
223 size_t arrpos, bitpos;
224 bit_to_pos(b, arrpos, bitpos);
225 const size_t test_mask(
size_t(1) <<
size_t(bitpos));
226 const size_t clear_mask(~test_mask);
227 return __sync_fetch_and_and(array + arrpos, clear_mask) & test_mask;
236 size_t arrpos, bitpos;
237 bit_to_pos(b, arrpos, bitpos);
238 const size_t test_mask(
size_t(1) <<
size_t(bitpos));
239 const size_t clear_mask(~test_mask);
240 bool ret = array[arrpos] & test_mask;
241 array[arrpos] &= clear_mask;
254 size_t arrpos, bitpos;
255 bit_to_pos(b, arrpos, bitpos);
259 struct bit_pos_iterator {
260 typedef std::input_iterator_tag iterator_category;
261 typedef size_t value_type;
262 typedef size_t difference_type;
263 typedef const size_t reference;
264 typedef const size_t* pointer;
267 bit_pos_iterator():pos(-1),db(NULL) {}
268 bit_pos_iterator(
const dense_bitset*
const db,
size_t pos):pos(pos),db(db) {}
270 size_t operator*()
const {
274 if (db->
next_bit(pos) ==
false) pos = (
size_t)(-1);
277 size_t operator++(
int){
278 size_t prevpos = pos;
279 if (db->
next_bit(pos) ==
false) pos = (
size_t)(-1);
282 bool operator==(
const bit_pos_iterator& other)
const {
284 return other.pos == pos;
286 bool operator!=(
const bit_pos_iterator& other)
const {
288 return other.pos != pos;
292 typedef bit_pos_iterator iterator;
293 typedef bit_pos_iterator const_iterator;
296 bit_pos_iterator begin()
const {
298 if (
first_bit(pos) ==
false) pos = size_t(-1);
299 return bit_pos_iterator(
this, pos);
302 bit_pos_iterator end()
const {
303 return bit_pos_iterator(
this, (
size_t)(-1));
311 for (
size_t i = 0; i < arrlen; ++i) {
313 b = (size_t)(i * (
sizeof(
size_t) * 8)) + first_bit_in_block(array[i]);
326 for (
size_t i = 0; i < arrlen; ++i) {
328 b = (size_t)(i * (
sizeof(
size_t) * 8)) + first_bit_in_block(~array[i]);
340 size_t arrpos, bitpos;
341 bit_to_pos(b, arrpos, bitpos);
343 bitpos = next_bit_in_block(bitpos, array[arrpos]);
345 b = (size_t)(arrpos * (
sizeof(
size_t) * 8)) + bitpos;
350 for (
size_t i = arrpos + 1; i < arrlen; ++i) {
352 b = (size_t)(i * (
sizeof(
size_t) * 8)) + first_bit_in_block(array[i]);
365 size_t arrpos, bitpos;
366 bit_to_pos(b, arrpos, bitpos);
368 bitpos = next_bit_in_block(bitpos, ~(array[arrpos]));
371 _b = (size_t)(arrpos * (
sizeof(
size_t) * 8)) + bitpos;
374 for (
size_t i = arrpos + 1; i < arrlen; ++i) {
376 _b = (size_t)(i * (
sizeof(
size_t) * 8)) + first_bit_in_block(~(array[i]));
397 oarc <<len << arrlen;
398 if (arrlen > 0) serialize(oarc, array, arrlen*
sizeof(
size_t));
403 if (array != NULL) free(array);
405 iarc >> len >> arrlen;
407 array = (
size_t*)malloc(arrlen*
sizeof(
size_t));
408 deserialize(iarc, array, arrlen*
sizeof(
size_t));
413 size_t popcount()
const {
415 for (
size_t i = 0;i < arrlen; ++i) {
424 for (
size_t i = 0; i < arrlen; ++i) {
425 ret.array[i] = array[i] & other.array[i];
434 for (
size_t i = 0; i < arrlen; ++i) {
435 ret.array[i] = array[i] | other.array[i];
443 for (
size_t i = 0; i < arrlen; ++i) {
444 ret.array[i] = array[i] - (array[i] & other.array[i]);
452 for (
size_t i = 0; i < arrlen; ++i) {
453 array[i] &= other.array[i];
461 for (
size_t i = 0; i < arrlen; ++i) {
462 array[i] |= other.array[i];
469 for (
size_t i = 0; i < arrlen; ++i) {
470 array[i] = array[i] - (array[i] & other.array[i]);
476 for (
size_t i = 0; i < arrlen; ++i) {
477 array[i] = ~array[i];
482 inline static void bit_to_pos(
size_t b,
size_t& arrpos,
size_t& bitpos) {
484 arrpos = b / (8 *
sizeof(size_t));
485 bitpos = b & (8 *
sizeof(size_t) - 1);
489 inline size_t next_bit_in_block(
const size_t& b,
const size_t& block)
const {
490 size_t belowselectedbit = size_t(-1) - (((size_t(1) << b) - 1)|(size_t(1)<<b));
491 size_t x = block & belowselectedbit ;
492 if (x == 0)
return 0;
497 inline size_t first_bit_in_block(
const size_t& block)
const{
498 if (block == 0)
return 0;
503 void fix_trailing_bits() {
505 size_t lastbits = len % (8 *
sizeof(size_t));
506 if (lastbits == 0)
return;
507 array[arrlen - 1] &= ((size_t(1) << lastbits) - 1);
563 memcpy(array, mem, memlen);
571 memcpy(array, db.array,
sizeof(
size_t) * arrlen);
577 memset((
void*)array, 0,
sizeof(
size_t) * arrlen);
582 for (
size_t i = 0;i < arrlen; ++i) array[i] = -1;
586 inline bool empty()
const {
587 for (
size_t i = 0; i < arrlen; ++i)
if (array[i])
return false;
593 __builtin_prefetch(&(array[b / (8 *
sizeof(
size_t))]));
597 inline bool get(
size_t b)
const{
598 size_t arrpos, bitpos;
599 bit_to_pos(b, arrpos, bitpos);
600 return array[arrpos] & (size_t(1) << size_t(bitpos));
606 size_t arrpos, bitpos;
607 bit_to_pos(b, arrpos, bitpos);
608 const size_t mask(
size_t(1) <<
size_t(bitpos));
609 return __sync_fetch_and_or(array + arrpos, mask) & mask;
615 size_t arrpos, bitpos;
616 bit_to_pos(b, arrpos, bitpos);
617 return array[arrpos];
627 size_t arrpos, bitpos;
628 bit_to_pos(b, arrpos, bitpos);
629 const size_t mask(
size_t(1) <<
size_t(bitpos));
630 bool ret = array[arrpos] & mask;
631 array[arrpos] |= mask;
639 inline bool set(
size_t b,
bool value) {
649 size_t arrpos, bitpos;
650 bit_to_pos(b, arrpos, bitpos);
652 const size_t mask(
size_t(1) <<
size_t(bitpos));
653 bool ret = array[arrpos] & mask;
654 array[arrpos]^= (-((size_t)value) ^ array[arrpos]) & mask;
662 size_t arrpos, bitpos;
663 bit_to_pos(b, arrpos, bitpos);
664 const size_t test_mask(
size_t(1) <<
size_t(bitpos));
665 const size_t clear_mask(~test_mask);
666 return __sync_fetch_and_and(array + arrpos, clear_mask) & test_mask;
675 size_t arrpos, bitpos;
676 bit_to_pos(b, arrpos, bitpos);
677 const size_t test_mask(
size_t(1) <<
size_t(bitpos));
678 const size_t clear_mask(~test_mask);
679 bool ret = array[arrpos] & test_mask;
680 array[arrpos] &= clear_mask;
685 struct bit_pos_iterator {
686 typedef std::input_iterator_tag iterator_category;
687 typedef size_t value_type;
688 typedef size_t difference_type;
689 typedef const size_t reference;
690 typedef const size_t* pointer;
693 bit_pos_iterator():pos(-1),db(NULL) {}
696 size_t operator*()
const {
700 if (db->
next_bit(pos) ==
false) pos = (
size_t)(-1);
703 size_t operator++(
int){
704 size_t prevpos = pos;
705 if (db->
next_bit(pos) ==
false) pos = (
size_t)(-1);
708 bool operator==(
const bit_pos_iterator& other)
const {
710 return other.pos == pos;
712 bool operator!=(
const bit_pos_iterator& other)
const {
714 return other.pos != pos;
718 typedef bit_pos_iterator iterator;
719 typedef bit_pos_iterator const_iterator;
722 bit_pos_iterator begin()
const {
724 if (
first_bit(pos) ==
false) pos = size_t(-1);
725 return bit_pos_iterator(
this, pos);
728 bit_pos_iterator end()
const {
729 return bit_pos_iterator(
this, (
size_t)(-1));
737 for (
size_t i = 0; i < arrlen; ++i) {
739 b = (size_t)(i * (
sizeof(
size_t) * 8)) + first_bit_in_block(array[i]);
751 for (
size_t i = 0; i < arrlen; ++i) {
753 b = (size_t)(i * (
sizeof(
size_t) * 8)) + first_bit_in_block(~array[i]);
767 size_t arrpos, bitpos;
768 bit_to_pos(b, arrpos, bitpos);
770 bitpos = next_bit_in_block(bitpos, array[arrpos]);
772 b = (size_t)(arrpos * (
sizeof(
size_t) * 8)) + bitpos;
777 for (
size_t i = arrpos + 1; i < arrlen; ++i) {
779 b = (size_t)(i * (
sizeof(
size_t) * 8)) + first_bit_in_block(array[i]);
796 serialize(oarc, array, arrlen*
sizeof(
size_t));
807 deserialize(iarc, array, arrlen*
sizeof(
size_t));
811 size_t popcount()
const {
813 for (
size_t i = 0;i < arrlen; ++i) {
814 ret += __builtin_popcountll(array[i]);
822 for (
size_t i = 0; i < arrlen; ++i) {
823 ret.array[i] = array[i] & other.array[i];
832 for (
size_t i = 0; i < arrlen; ++i) {
833 ret.array[i] = array[i] | other.array[i];
841 for (
size_t i = 0; i < arrlen; ++i) {
842 ret.array[i] = array[i] - (array[i] & other.array[i]);
850 for (
size_t i = 0; i < arrlen; ++i) {
851 array[i] &= other.array[i];
859 for (
size_t i = 0; i < arrlen; ++i) {
860 array[i] |= other.array[i];
867 for (
size_t i = 0; i < arrlen; ++i) {
868 array[i] = array[i] - (array[i] & other.array[i]);
875 ASSERT_EQ(arrlen, other.arrlen);
877 for (
size_t i = 0; i < arrlen; ++i) {
878 ret &= (array[i] == other.array[i]);
883 inline static void bit_to_pos(
size_t b,
size_t &arrpos,
size_t &bitpos) {
885 arrpos = b / (8 *
sizeof(size_t));
886 bitpos = b & (8 *
sizeof(size_t) - 1);
891 inline size_t next_bit_in_block(
const size_t &b,
const size_t &block)
const {
892 size_t belowselectedbit = size_t(-1) - (((size_t(1) << b) - 1)|(size_t(1)<<b));
893 size_t x = block & belowselectedbit ;
894 if (x == 0)
return 0;
899 inline size_t first_bit_in_block(
const size_t &block)
const {
901 if (block == 0)
return 0;
907 void fix_trailing_bits() {
909 size_t lastbits = len % (8 *
sizeof(size_t));
910 if (lastbits == 0)
return;
911 array[arrlen - 1] &= ((size_t(1) << lastbits) - 1);
915 static const size_t arrlen;
916 size_t array[len / (
sizeof(size_t) * 8) + (len % (
sizeof(size_t) * 8) > 0)];
bool set_bit(size_t b)
Atomically sets the bit at b to true returning the old value.
void save(oarchive &oarc) const
Serializes this bitset to an archive.
static unsigned int n_trailing_zeros(T v, _ENABLE_IF_UINT(T))
size_t size() const
Returns the number of bits in this bitset.
bool next_zero_bit(size_t &b) const
void save(oarchive &oarc) const
Serializes this bitset to an archive.
The serialization input archive object which, provided with a reference to an istream, will read from the istream, providing deserialization capabilities.
bool set_bit_unsync(size_t b)
bool set_unsync(size_t b, bool value)
static unsigned int num_bits_on(T v, _ENABLE_IF_UINT(T))
dense_bitset & operator=(const dense_bitset &db)
Make a copy of the bitset db.
bool set_unsync(size_t b, bool value)
void initialize_from_mem(void *mem, size_t memlen)
void load(iarchive &iarc)
Deserializes this bitset from an archive.
bool clear_bit(size_t b)
Atomically set the bit at b to false returning the old value.
~fixed_dense_bitset()
destructor
void prefetch(size_t b) const
Prefetches the word containing the bit b.
void clear_word_unsync(size_t b)
void load(iarchive &iarc)
Deserializes this bitset from an archive.
size_t get_containing_word_and_zero(size_t b)
Returns the value of the word containing the bit b.
bool first_bit(size_t &b) const
bool set_bit_unsync(size_t b)
dense_bitset()
Constructs a bitset of 0 length.
void fill()
Sets all bits to 1.
bool first_zero_bit(size_t &b) const
dense_bitset(const dense_bitset &db)
Make a copy of the bitset db.
void clear()
Sets all bits to 0.
void fill()
Sets all bits to 1.
bool next_bit(size_t &b) const
size_t containing_word(size_t b)
Returns the value of the word containing the bit b.
#define ASSERT_TRUE(cond)
dense_bitset(size_t size)
Constructs a bitset with 'size' bits. All bits will be cleared.
bool first_bit(size_t &b) const
fixed_dense_bitset(const fixed_dense_bitset< len > &db)
Make a copy of the bitset db.
fixed_dense_bitset< len > & operator=(const fixed_dense_bitset< len > &db)
Make a copy of the bitset db.
T fetch_and_store(T &a, const T &newval)
Atomically sets a to the newval, returning the old value.
size_t size() const
Returns the number of bits in this bitset.
bool first_zero_bit(size_t &b) const
bool clear_bit_unsync(size_t b)
void prefetch(size_t b) const
Prefetches the word containing the bit b.
bool next_bit(size_t &b) const
The serialization output archive object which, provided with a reference to an ostream, will write to the ostream, providing serialization capabilities.
bool set_bit(size_t b)
Atomically sets the bit at position b to true returning the old value.
size_t containing_word(size_t b)
Returns the value of the word containing the bit b.
~dense_bitset()
destructor
bool clear_bit_unsync(size_t b)
bool clear_bit(size_t b)
Atomically set the bit at b to false returning the old value.
fixed_dense_bitset()
Constructs a bitset of 0 length.
bool xor_bit(size_t b)
Atomically xors a bit with 1.
void clear()
Sets all bits to 0.
void transfer_approximate_unsafe(dense_bitset &other, size_t &start, size_t &b)
Transfers approximately b bits from another bitset to this bitset.