bmvmin.h
Go to the documentation of this file.
#ifndef BMVMIN__H__INCLUDED__
#define BMVMIN__H__INCLUDED__
/*
Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
For more information please visit: http://bitmagic.io
*/
/*! \file bmvmin.h
\brief Mini bitset for testing and utility purposes (internal)
*/
#ifdef _MSC_VER
#pragma warning( push )
#pragma warning( disable : 4100)
#endif
namespace bm
{
#define BM_MINISET_GAPLEN (bm::gap_len_table<true>::_len[0])
#define BM_MINISET_ARRSIZE(x) ((x / 32) + ( (x % 32) && 1 ))
/*! @defgroup mset Small sets functionality (intrenal)
* @internal
* @ingroup bmagic
*
*/
/*!@{ */
/*!
@brief Template class implements memory saving set functionality
@ingroup mset
@sa bvmini
@internal
*/
template <class A, size_t N> class miniset
{
public:
miniset()
: m_buf(0),
m_type(1)
{}
miniset(const miniset& mset)
{
if (mset.m_buf)
{
if (mset.m_type)
init_gapbuf(mset.m_buf);
else
init_bitbuf(mset.m_buf);
}
else
{
m_type = mset.m_type;
m_buf = 0;
}
}
~miniset()
{
if (m_buf)
{
A::deallocate(m_buf, m_type ?
(BM_MINISET_GAPLEN / (sizeof(bm::word_t) / sizeof(bm::gap_word_t)))
:
(BM_MINISET_ARRSIZE(N)));
}
}
/// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
unsigned test(bm::id_t n) const
{
return
!m_buf ? 0
:
m_type ?
gap_test((gap_word_t*)m_buf, n)
:
m_buf[n>>bm::set_word_shift] & (1<<(n & bm::set_word_mask));
}
void set(bm::id_t n, bool val=true)
{
if (m_type == 0)
{
if (!m_buf)
{
if (!val) return;
init_bitbuf(0);
}
unsigned nword = n >> bm::set_word_shift;
unsigned mask = unsigned(1) << (n & bm::set_word_mask);
val ? (m_buf[nword] |= mask) : (m_buf[nword] &= ~mask);
}
else
{
if (!m_buf)
{
if (!val) return;
init_gapbuf(0);
}
unsigned is_set;
unsigned new_block_len =
gap_set_value(val, (gap_word_t*)m_buf, n, &is_set);
if (new_block_len > unsigned(BM_MINISET_GAPLEN-4))
{
convert_buf();
}
}
}
unsigned mem_used() const
{
return sizeof(*this) +
(m_buf ?
(m_type ? (BM_MINISET_GAPLEN * sizeof(gap_word_t))
: (BM_MINISET_ARRSIZE(N) * sizeof(bm::word_t)))
: 0);
}
void swap(miniset& mset)
{
bm::word_t* buftmp = m_buf;
m_buf = mset.m_buf;
mset.m_buf = buftmp;
unsigned typetmp = m_type;
m_type = mset.m_type;
mset.m_type = typetmp;
}
private:
void init_bitbuf(bm::word_t* buf)
{
unsigned arr_size = BM_MINISET_ARRSIZE(N);
m_buf = A::allocate(arr_size, 0);
if (buf)
{
::memcpy(m_buf, buf, arr_size * sizeof(bm::word_t));
}
else
{
::memset(m_buf, 0, arr_size * sizeof(bm::word_t));
}
m_type = 0;
}
void init_gapbuf(bm::word_t* buf)
{
unsigned arr_size =
unsigned(BM_MINISET_GAPLEN / (sizeof(bm::word_t) / sizeof(bm::gap_word_t)));
m_buf = A::allocate(arr_size, 0);
if (buf)
{
::memcpy(m_buf, buf, arr_size * sizeof(bm::word_t));
}
else
{
*m_buf = 0;
gap_set_all((gap_word_t*)m_buf, bm::gap_max_bits, 0);
}
m_type = 1;
}
void convert_buf()
{
unsigned arr_size = BM_MINISET_ARRSIZE(N);
bm::word_t* buf = A::allocate(arr_size, 0);
gap_convert_to_bitset(buf, (gap_word_t*) m_buf/*, arr_size*/);
arr_size =
unsigned(BM_MINISET_GAPLEN / (sizeof(bm::word_t) / sizeof(bm::gap_word_t)));
A::deallocate(m_buf, arr_size);
m_buf = buf;
m_type = 0;
}
private:
bm::word_t* m_buf; //!< Buffer pointer
unsigned m_type; //!< buffer type (0-bit, 1-gap)
};
/*!
@brief Mini bit-vector for auxiliary purposes
@ingroup mset
@sa miniset
@internal
*/
template<size_t N> class bvmini
{
public:
bvmini(int = 0)
{
::memset(m_buf, 0, sizeof(m_buf));
}
bvmini(const bvmini& mset)
{
::memcpy(m_buf, mset.m_buf, sizeof(m_buf));
}
/// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
unsigned test(bm::id_t n) const
{
return m_buf[n>>bm::set_word_shift] & (1<<(n & bm::set_word_mask));
}
void set(bm::id_t n, bool val=true)
{
unsigned nword = n >> bm::set_word_shift;
unsigned mask = unsigned(1) << (n & bm::set_word_mask);
val ? (m_buf[nword] |= mask) : (m_buf[nword] &= ~mask);
}
unsigned mem_used() const
{
return sizeof(*this);
}
void swap(bvmini& mset)
{
for (unsigned i = 0; i < BM_MINISET_ARRSIZE(N); ++i)
{
bm::word_t tmp = m_buf[i];
m_buf[i] = mset.m_buf[i];
mset.m_buf[i] = tmp;
}
}
private:
bm::word_t m_buf[BM_MINISET_ARRSIZE(N)];
};
/**@} */
/*!
@brief Bitvector class with very limited functionality.
Class implements simple bitset and used for internal
and testing purposes.
@internal
*/
template<class A> class bvector_mini
{
public:
#ifdef BM64ADDR
typedef bm::id64_t size_type;
#else
typedef bm::id_t size_type;
#endif
public:
bvector_mini(size_type size)
: m_buf(0),
m_size(size)
{
size_type arr_size = (size / 32) + 1;
m_buf = A::allocate(arr_size, 0);
::memset(m_buf, 0, arr_size * sizeof(unsigned));
}
bvector_mini(const bvector_mini& bvect)
: m_size(bvect.m_size)
{
size_type arr_size = (m_size / 32) + 1;
m_buf = A::allocate(arr_size, 0);
::memcpy(m_buf, bvect.m_buf, arr_size * sizeof(unsigned));
}
~bvector_mini()
{
A::deallocate(m_buf, (m_size / 32) + 1);
}
/// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
int is_bit_true(size_type pos) const
{
unsigned char mask = (unsigned char)((char)0x1 << (pos & 7));
unsigned char* offs = (unsigned char*)m_buf + (pos >> 3);
return (*offs) & mask;
}
/// Sets bit number pos to 1
void set_bit(size_type pos)
{
unsigned char mask = (unsigned char)(0x1 << (pos & 7));
unsigned char* offs = (unsigned char*)m_buf + (pos >> 3);
*offs |= mask;
}
/// Sets bit number pos to 0
void clear_bit(size_type pos)
{
unsigned char mask = (unsigned char)(0x1 << (pos & 7));
unsigned char* offs = (unsigned char*)m_buf + (pos >> 3);
*offs &= (unsigned char)~mask;
}
/// Counts number of bits ON
size_type bit_count() const
{
size_type count = 0;
const unsigned* end = m_buf + (m_size / 32)+1;
for (unsigned* start = m_buf; start < end; ++start)
{
unsigned value = *start;
for (count += (value!=0); value &= value - 1; ++count);
}
return count;
}
/// Comparison.
int compare(const bvector_mini& bvect)
{
size_type cnt1 = bit_count();
size_type cnt2 = bvect.bit_count();
if (!cnt1 && !cnt2) return 0;
size_type cnt_min = cnt1 < cnt2 ? cnt1 : cnt2;
if (!cnt_min) return cnt1 ? 1 : -1;
size_type idx1 = get_first();
size_type idx2 = bvect.get_first();
for (size_type i = 0; i < cnt_min; ++i)
{
if (idx1 != idx2)
{
return idx1 < idx2 ? 1 : -1;
}
idx1 = get_next(idx1);
idx2 = bvect.get_next(idx2);
}
if (idx1 != idx2)
{
if (!idx1) return -1;
if (!idx2) return 1;
return idx1 < idx2 ? 1 : -1;
}
return 0;
}
/// Returns index of the first ON bit
size_type get_first() const
{
size_type pos = 0;
const unsigned char* ptr = (unsigned char*) m_buf;
for (unsigned i = 0; i < ((m_size/8)+1); ++i)
{
unsigned char w = ptr[i];
if (w != 0)
{
while ((w & 1u) == 0)
{
w = (unsigned char)(w >> 1u);
++pos;
}
return pos;
}
pos = size_type(pos + sizeof(unsigned char) * 8u);
}
return 0;
}
/// Returns index of next bit, which is ON
size_type get_next(size_type idx) const
{
size_type i;
for (i = idx+1; i < m_size; ++i)
{
unsigned char* offs = (unsigned char*)m_buf + (i >> 3);
if (*offs)
{
unsigned char mask = (unsigned char)((char)0x1 << (i & 7));
if (*offs & mask)
{
return i;
}
}
else
{
i += 7;
}
}
return 0;
}
void combine_and(const bvector_mini& bvect)
{
const unsigned* end = m_buf + (m_size / 32)+1;
const unsigned* src = bvect.get_buf();
for (unsigned* start = m_buf; start < end; ++start)
{
*start &= *src++;
}
}
void combine_xor(const bvector_mini& bvect)
{
const unsigned* end = m_buf + (m_size / 32)+1;
const unsigned* src = bvect.get_buf();
for (unsigned* start = m_buf; start < end; ++start)
{
*start ^= *src++;
}
}
void combine_or(const bvector_mini& bvect)
{
const unsigned* end = m_buf + (m_size / 32)+1;
const unsigned* src = bvect.get_buf();
for (unsigned* start = m_buf; start < end; ++start)
{
*start |= *src++;
}
}
void combine_sub(const bvector_mini& bvect)
{
const unsigned* end = m_buf + (m_size / 32)+1;
const unsigned* src = bvect.get_buf();
for (unsigned* start = m_buf; start < end; ++start)
{
*start &= ~(*src++);
}
}
const unsigned* get_buf() const { return m_buf; }
unsigned mem_used() const
{
return unsigned(sizeof(bvector_mini) + (m_size / 32) + 1);
}
void swap(bvector_mini& bvm)
{
bm::word_t* buftmp = m_buf;
m_buf = bvm.m_buf;
bvm.m_buf = buftmp;
}
private:
bm::word_t* m_buf;
size_type m_size;
};
} // namespace bm
#ifdef _MSC_VER
#pragma warning( pop )
#endif
#endif
BM_MINISET_ARRSIZE
#define BM_MINISET_ARRSIZE(x)
Definition bmvmin.h:36
BM_MINISET_GAPLEN
#define BM_MINISET_GAPLEN
Definition bmvmin.h:35
bm::bvector_mini::is_bit_true
int is_bit_true(size_type pos) const
Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
Definition bmvmin.h:303
bm::bvector_mini::mem_used
unsigned mem_used() const
Definition bmvmin.h:457
bm::bvector_mini::get_first
size_type get_first() const
Returns index of the first ON bit.
Definition bmvmin.h:371
bm::bvector_mini::get_next
size_type get_next(size_type idx) const
Returns index of next bit, which is ON.
Definition bmvmin.h:394
bm::bvector_mini::combine_sub
void combine_sub(const bvector_mini &bvect)
Definition bmvmin.h:446
bm::bvector_mini::swap
void swap(bvector_mini &bvm)
Definition bmvmin.h:462
bm::bvector_mini::get_buf
const unsigned * get_buf() const
Definition bmvmin.h:456
bm::bvector_mini::bit_count
size_type bit_count() const
Counts number of bits ON.
Definition bmvmin.h:327
bm::bvector_mini::bvector_mini
bvector_mini(size_type size)
Definition bmvmin.h:281
bm::bvector_mini::combine_and
void combine_and(const bvector_mini &bvect)
Definition bmvmin.h:416
bm::bvector_mini::size_type
bm::id_t size_type
Definition bmvmin.h:277
bm::bvector_mini::combine_or
void combine_or(const bvector_mini &bvect)
Definition bmvmin.h:436
bm::bvector_mini::combine_xor
void combine_xor(const bvector_mini &bvect)
Definition bmvmin.h:426
bm::bvector_mini::compare
int compare(const bvector_mini &bvect)
Comparison.
Definition bmvmin.h:340
bm::bvector_mini::~bvector_mini
~bvector_mini()
Definition bmvmin.h:297
bm::bvector_mini::bvector_mini
bvector_mini(const bvector_mini &bvect)
Definition bmvmin.h:289
bm::bvector_mini::clear_bit
void clear_bit(size_type pos)
Sets bit number pos to 0.
Definition bmvmin.h:319
bm::bvector_mini::set_bit
void set_bit(size_type pos)
Sets bit number pos to 1.
Definition bmvmin.h:311
bm::size_type
bm::bvmini::mem_used
unsigned mem_used() const
Definition bmvmin.h:242
bm::bvmini::set
void set(bm::id_t n, bool val=true)
Definition bmvmin.h:234
bm::bvmini::bvmini
bvmini(int=0)
Definition bmvmin.h:217
bm::bvmini::test
unsigned test(bm::id_t n) const
Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
Definition bmvmin.h:229
bm::bvmini::bvmini
bvmini(const bvmini &mset)
Definition bmvmin.h:222
bm::bvmini::swap
void swap(bvmini &mset)
Definition bmvmin.h:247
bm::miniset::miniset
miniset()
Definition bmvmin.h:56
bm::miniset::set
void set(bm::id_t n, bool val=true)
Definition bmvmin.h:100
bm::miniset::mem_used
unsigned mem_used() const
Definition bmvmin.h:134
bm::miniset::miniset
miniset(const miniset &mset)
Definition bmvmin.h:61
bm::miniset::~miniset
~miniset()
Definition bmvmin.h:77
bm::miniset::test
unsigned test(bm::id_t n) const
Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
Definition bmvmin.h:89
bm::miniset::swap
void swap(miniset &mset)
Definition bmvmin.h:143
bm::gap_set_value
unsigned gap_set_value(unsigned val, T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set) BMNOEXCEPT
Sets or clears bit in the GAP buffer.
Definition bmfunc.h:3254
bm::gap_convert_to_bitset
void gap_convert_to_bitset(unsigned *BMRESTRICT dest, const T *BMRESTRICT buf, unsigned len=0) BMNOEXCEPT
GAP block to bitblock conversion.
Definition bmfunc.h:4475
bm::gap_test
unsigned gap_test(const T *BMRESTRICT buf, unsigned pos) BMNOEXCEPT
Tests if bit = pos is true.
Definition bmfunc.h:1790
bm::gap_set_all
void gap_set_all(T *buf, unsigned set_max, unsigned value) BMNOEXCEPT
Sets all bits to 0 or 1 (GAP).
Definition bmfunc.h:4552
bm
Definition bm.h:78
bm::word_t
unsigned int word_t
Definition bmconst.h:39
bm::set_word_shift
const unsigned set_word_shift
Definition bmconst.h:72
bm::id64_t
unsigned long long int id64_t
Definition bmconst.h:35
bm::id_t
unsigned int id_t
Definition bmconst.h:38
bm::gap_word_t
unsigned short gap_word_t
Definition bmconst.h:78
bm::gap_max_bits
const unsigned gap_max_bits
Definition bmconst.h:81
bm::set_word_mask
const unsigned set_word_mask
Definition bmconst.h:73
bvect
bm::bvector< dbg_alloc > bvect
Definition sample6.cpp:116