1 #ifndef BMVMIN__H__INCLUDED__ 2 #define BMVMIN__H__INCLUDED__ 27 #pragma warning( push ) 28 #pragma warning( disable : 4100) 35 #define BM_MINISET_GAPLEN (bm::gap_len_table<true>::_len[0]) 36 #define BM_MINISET_ARRSIZE(x) ((x / 32) + ( (x % 32) && 1 )) 49 ::memset(dest, 0, dest_len *
sizeof(
unsigned));
67 template <
class A,
size_t N>
class miniset 81 init_gapbuf(mset.m_buf);
83 init_bitbuf(mset.m_buf);
96 A::deallocate(m_buf, m_type ?
128 val ? (m_buf[nword] |= mask) : (m_buf[nword] &= ~mask);
139 unsigned new_block_len =
151 return sizeof(*this) +
163 unsigned typetmp = m_type;
164 m_type = mset.m_type;
165 mset.m_type = typetmp;
174 m_buf = A::allocate(arr_size, 0);
177 ::memcpy(m_buf, buf, arr_size *
sizeof(
bm::word_t));
181 ::memset(m_buf, 0, arr_size *
sizeof(
bm::word_t));
190 m_buf = A::allocate(arr_size, 0);
193 ::memcpy(m_buf, buf, arr_size *
sizeof(
bm::word_t));
211 A::deallocate(m_buf, arr_size);
234 ::memset(m_buf, 0,
sizeof(m_buf));
239 ::memcpy(m_buf, mset.m_buf,
sizeof(m_buf));
254 val ? (m_buf[nword] |= mask) : (m_buf[nword] &= ~mask);
259 return sizeof(*this);
267 m_buf[i] = mset.m_buf[i];
300 size_type arr_size = (size / 32) + 1;
301 m_buf = A::allocate(arr_size, 0);
302 ::memset(m_buf, 0, arr_size *
sizeof(
unsigned));
305 : m_size(bvect.m_size)
307 size_type arr_size = (m_size / 32) + 1;
308 m_buf = A::allocate(arr_size, 0);
309 ::memcpy(m_buf, bvect.m_buf, arr_size *
sizeof(
unsigned));
314 A::deallocate(m_buf, (m_size / 32) + 1);
320 unsigned char mask = (
unsigned char)((
char)0x1 << (pos & 7));
321 unsigned char* offs = (
unsigned char*)m_buf + (pos >> 3);
322 return (*offs) & mask;
328 unsigned char mask = (
unsigned char)(0x1 << (pos & 7));
329 unsigned char* offs = (
unsigned char*)m_buf + (pos >> 3);
336 unsigned char mask = (
unsigned char)(0x1 << (pos & 7));
337 unsigned char* offs = (
unsigned char*)m_buf + (pos >> 3);
338 *offs &= (
unsigned char)~mask;
345 const unsigned* end = m_buf + (m_size / 32)+1;
346 for (
unsigned* start = m_buf; start < end; ++start)
348 unsigned value = *start;
349 for (count += (value!=0); value &= value - 1; ++count);
357 size_type cnt1 = bit_count();
359 if (!cnt1 && !cnt2)
return 0;
360 size_type cnt_min = cnt1 < cnt2 ? cnt1 : cnt2;
361 if (!cnt_min)
return cnt1 ? 1 : -1;
363 size_type idx1 = get_first();
366 for (size_type i = 0; i < cnt_min; ++i)
370 return idx1 < idx2 ? 1 : -1;
372 idx1 = get_next(idx1);
377 if (!idx1)
return -1;
379 return idx1 < idx2 ? 1 : -1;
389 const unsigned char* ptr = (
unsigned char*) m_buf;
390 for (
unsigned i = 0; i < ((m_size/8)+1); ++i)
392 unsigned char w = ptr[i];
395 while ((w & 1u) == 0)
397 w = (
unsigned char)(w >> 1u);
402 pos = size_type(pos +
sizeof(
unsigned char) * 8u);
412 for (i = idx+1; i < m_size; ++i)
414 unsigned char* offs = (
unsigned char*)m_buf + (i >> 3);
417 unsigned char mask = (
unsigned char)((
char)0x1 << (i & 7));
433 const unsigned* end = m_buf + (m_size / 32)+1;
434 const unsigned* src = bvect.
get_buf();
435 for (
unsigned* start = m_buf; start < end; ++start)
443 const unsigned* end = m_buf + (m_size / 32)+1;
444 const unsigned* src = bvect.
get_buf();
445 for (
unsigned* start = m_buf; start < end; ++start)
453 const unsigned* end = m_buf + (m_size / 32)+1;
454 const unsigned* src = bvect.
get_buf();
455 for (
unsigned* start = m_buf; start < end; ++start)
463 const unsigned* end = m_buf + (m_size / 32)+1;
464 const unsigned* src = bvect.
get_buf();
465 for (
unsigned* start = m_buf; start < end; ++start)
471 const unsigned*
get_buf()
const {
return m_buf; }
474 return unsigned(
sizeof(
bvector_mini) + (m_size / 32) + 1);
494 #pragma warning( pop ) Bitvector Bit-vector container with runtime compression of bits.
bvector_mini(const bvector_mini &bvect)
void clear_bit(size_type pos)
Sets bit number pos to 0.
void gap_add_to_bitset(unsigned *dest, const T *pcurr, unsigned len)
Adds(OR) GAP block to bitblock.
const unsigned set_word_shift
const unsigned * get_buf() const
void combine_sub(const bvector_mini &bvect)
unsigned gap_set_value(unsigned val, T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set)
Sets or clears bit in the GAP buffer.
void gap_set_all(T *buf, unsigned set_max, unsigned value)
Sets all bits to 0 or 1 (GAP)
unsigned long long int id64_t
unsigned mem_used() const
void gap_convert_to_bitset(unsigned *dest, const T *buf)
GAP block to bitblock conversion.
size_type get_first() const
Returns index of the first ON bit.
void combine_or(const bvector_mini &bvect)
int compare(const bvector_mini &bvect)
Comparison.
unsigned gap_test(const T *buf, unsigned pos)
Tests if bit = pos is true.
int is_bit_true(size_type pos) const
Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
void set_bit(size_type pos)
Sets bit number pos to 1.
void combine_and(const bvector_mini &bvect)
size_type bit_count() const
Counts number of bits ON.
miniset(const miniset &mset)
unsigned short gap_word_t
bvmini(const bvmini &mset)
Template class implements memory saving set functionality.
unsigned mem_used() const
const unsigned gap_max_bits
unsigned test(bm::id_t n) const
Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
#define BM_MINISET_GAPLEN
void combine_xor(const bvector_mini &bvect)
size_type get_next(size_type idx) const
Returns index of next bit, which is ON.
const unsigned set_word_mask
unsigned mem_used() const
unsigned test(bm::id_t n) const
Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
#define BM_MINISET_ARRSIZE(x)
bvector_mini(size_type size)
Mini bit-vector for auxiliary purposes.
void swap(bvector_mini &bvm)
Bitvector class with very limited functionality.