4 #ifndef DENSE_BITSET_HPP
5 #define DENSE_BITSET_HPP
26 void resize(
size_t n) {
29 arrlen = n / (8*
sizeof(size_t)) + 1;
30 array = (
size_t*)realloc(array,
sizeof(
size_t) * arrlen);
34 for (
size_t i = 0;i < arrlen; ++i) array[i] = 0;
38 memset(array, 0xff, arrlen *
sizeof(
size_t));
41 inline bool get(uint32_t b)
const{
42 uint32_t arrpos, bitpos;
43 bit_to_pos(b, arrpos, bitpos);
44 return array[arrpos] & (size_t(1) << size_t(bitpos));
50 uint32_t arrpos, bitpos;
51 bit_to_pos(b, arrpos, bitpos);
52 const size_t mask(
size_t(1) <<
size_t(bitpos));
53 return __sync_fetch_and_or(array + arrpos, mask) & mask;
57 inline bool set(uint32_t b,
bool value) {
65 uint32_t arrpos, bitpos;
66 bit_to_pos(b, arrpos, bitpos);
67 const size_t test_mask(
size_t(1) <<
size_t(bitpos));
68 const size_t clear_mask(~test_mask);
69 return __sync_fetch_and_and(array + arrpos, clear_mask) & test_mask;
72 inline void clear_bits(uint32_t fromb, uint32_t tob) {
74 const size_t bitsperword =
sizeof(size_t)*8;
75 while((fromb%bitsperword != 0)) {
77 if (fromb>=tob)
return;
81 while((tob%bitsperword != 0)) {
83 if(tob<=fromb)
return;
88 uint32_t from_arrpos = fromb / (8 * (int)
sizeof(
size_t));
89 uint32_t to_arrpos = tob / (8 * (int)
sizeof(
size_t));
90 memset(&array[from_arrpos], 0, (to_arrpos-from_arrpos) * (
int)
sizeof(
size_t));
94 inline size_t size()
const {
101 inline static void bit_to_pos(uint32_t b, uint32_t &arrpos, uint32_t &bitpos) {
103 arrpos = b / (8 * (int)
sizeof(
size_t));
104 bitpos = b & (8 * (int)
sizeof(
size_t) - 1);
107 void generate_bit_masks() {
108 below_selectedbit[0] = size_t(-2);
109 for (
size_t i = 0;i < 8 *
sizeof(size_t) ; ++i) {
110 selectbit[i] = size_t(1) << i;
111 notselectbit[i] = ~selectbit[i];
112 if (i > 0) below_selectedbit[i] = below_selectedbit[i-1] - selectbit[i];
117 inline size_t next_bit_in_block(
const uint32_t &b,
const size_t &block) {
119 size_t x = block & below_selectedbit[b] ;
120 if (x == 0)
return 0;
121 else return __builtin_ctzl(x);
125 inline size_t first_bit_in_block(
const size_t &block) {
127 if (block == 0)
return 0;
128 else return __builtin_ctzl(block);
135 size_t selectbit[8 *
sizeof(size_t)];
136 size_t notselectbit[8 *
sizeof(size_t)];
137 size_t below_selectedbit[8 *
sizeof(size_t)];