#ifndef __BITARRAY__ //数组不支持多线程同时访问，没有对引用计数以及分配的资源做任何锁处理
#define __BITARRAY__ 1 //越界访问修改为抛出异常 #ifdef __BIT_DEBUG__ //__BIT_DEBUG__是调试用的宏定义
#include <cstdio>
#endif #ifdef __cplusplus > 201103L
#include <cstdint>
#else
#include <stdint.h>
#define nullptr NULL
#define noexcept throw()
#endif #define __BIT_ERRMSG_LEN__ 512 #include <cstring>
#include <stdexcept> class BitArray
{
private:
enum __e_bit_size {bit = }; class __Ref_Array //引用计数类
{
public:
__Ref_Array(int64_t __size)
:m_ref_count(), m_size(__size)
{
#ifdef __BIT_DEBUG__
fprintf(stderr, "__Ref_Array ctor @addr： %p with size:%ld\n", this, __size);
#endif
init();
} ~__Ref_Array()
{
#ifdef __BIT_DEBUG__
fprintf(stderr, "__Ref_Array dtor @addr： %p with size:%ld\n", this, __size);
#endif
delete[] m_array;
} __Ref_Array(const __Ref_Array& o)
:m_ref_count(),
m_size(o.m_size),
m_array_size(o.m_array_size),
m_used(o.m_used)
{
#ifdef __BIT_DEBUG__
fprintf(stderr, "__Ref_Array copytor @addr： %p with @addr: %p && size:%ld\n", this, &o, __size);
#endif
m_array = new int8_t[m_array_size];
memcpy(m_array, o.m_array, m_array_size);
} inline bool
get(int64_t __pos) const
{return *(m_array + slot_bit(__pos)) & mask(__pos);} inline void
set(int64_t __pos)
{
*(m_array + slot_bit(__pos)) |= mask(__pos);
m_used ++;
} inline void
clear(int64_t __pos)
{
*(m_array + slot_bit(__pos)) &= ~mask(__pos);
m_used --;
} inline void
reset()
{
std::memset(m_array, , m_array_size);
m_used = ;
} inline int64_t
length() const
{return m_size;} inline int64_t
size() const
{return m_size;} inline int64_t
used() const
{return m_used;} inline int64_t
refCount() const
{return m_ref_count;} inline bool
sizeRange(int64_t __pos) const
{return __pos >= && __pos < m_size;} inline int64_t
sharedPlus()
{return ++ m_ref_count;} inline int64_t
sharedSub()
{return -- m_ref_count;} inline bool
isShared() const
{return m_ref_count > ;} private:
inline void
init()
{
m_array_size = nslot(m_size);
m_array = new int8_t[m_array_size];
reset();
} inline int64_t
slot_bit(int64_t __n) const
{return __n / bit;} inline int64_t
nslot(int64_t __size) const
{return slot_bit(__size + bit - );} inline int8_t
mask(int64_t __pos) const
{return int8_t() << (__pos % bit);} private:
int8_t m_array; //位数组存储
int64_t m_ref_count; //引用计数
int64_t m_size; //引用计数大小
int64_t m_array_size; //分配的int8_t数组大小
int64_t m_used; //已经使用的bit位数
}; private:
class BitProxy //代理类 为了区分 x = ba[?]; 和 ba[?];
{
BitProxy(BitArray& ba, int64_t pos)
:m_array(ba), m_pos(pos)
{} BitProxy& operator = (const BitProxy& rh)
{
if(rh)
m_array.set(m_pos);
else{
m_array.clear(m_pos);
} return *this;
} BitProxy& operator = (bool status)
{
if(status)
m_array.set(m_pos);
else{
m_array.clear(m_pos);
} return *this;
} operator bool() const
{
return m_array.get(m_pos);
} private:
BitArray& m_array;
int64_t m_pos;
}; public: BitArray() noexcept //无参数构造函数
:m_ref(nullptr)
{
#ifdef __BIT_DEBUG__
fprintf(stderr, "BitArray ctor @addr： %p with nullptr ...\n", this);
#endif
} BitArray(int64_t size) noexcept //构造函数
:m_ref(size > new __Ref_Array(size) : nullptr)
{
#ifdef __BIT_DEBUG__
fprintf(stderr, "BitArray ctor @addr： %p with size: %d ...\n", this, size);
#endif
} ~BitArray() //析构函数
{release()} BitArray(const BitArray& o) noexcept //copy构造函数
m_ref(o.m_ref)
{
#ifdef __BIT_DEBUG__
fprintf(stderr, "BitArray copy tor @addr： %p with other BitArray @addr: %p ...\n", this, &o);
#endif
} #ifdef __cplusplus >= 201103L
BitArray(BitArray&& o) noexcept //move构造函数
m_ref(o.m_ref)
{
#ifdef __BIT_DEBUG__
fprintf(stderr, "BitArray move tor @addr： %p <--- other BitArray @addr: %p ...\n", this, &o);
#endif
o.m_ref = nullptr;
}
#endif BitArray& operator=(const BitArray& o) //赋值运算符
{
if(m_ref != o.m_ref)
{
release();
m_ref = o.m_ref;
#ifdef __BIT_DEBUG__
fprintf(stderr, "BitArray assign @addr： %p with other BitArray @addr: %p ...\n", this, &o);
#endif
if(m_ref)
m_ref->sharedPlus();
}
} const BitProxy
operator[] (int64_t pos) const //下标运算符
{return BitProxy(const_cast<BitArray&>(*this), pos);} BitProxy
operator[] (int64_t pos) //下标运算符
{return BitProxy(*this, pos);} public:
inline bool
get(int64_t pos) const throw(std::out_of_range)
{
if(!m_ref || !m_ref->sizeRange(pos))
{
char errmsg[__BIT_ERRMSG_LEN__] = {}; snprintf(errmsg, sizeof(errmsg), "out of range in get -> pos : %d | size : %d\n", pos, size()); throw std::out_of_range(errmsg);
}
else
return m_ref->get(pos);
} inline bool
set(int64_t pos) const throw(std::out_of_range)
{
if(!m_ref || !m_ref->sizeRange(pos))
{
char errmsg[__BIT_ERRMSG_LEN__] = {}; snprintf(errmsg, sizeof(errmsg), "out of range in set -> pos : %d | size : %d\n", pos, size()); throw std::out_of_range(errmsg);
}
else if(m_ref->get(pos))
{
return true;
}
else
{
if(m_ref->isShared())
{
__Ref_Array* last_ref = m_ref; m_ref = new __Ref_Array(*last_ref); last_ref->sharedSub();
} return m_ref->get(pos);
}
} inline bool
clear(int64_t pos) const throw(std::out_of_range)
{
if(!m_ref || !m_ref->sizeRange(pos))
{
char errmsg[__BIT_ERRMSG_LEN__] = {}; snprintf(errmsg, sizeof(errmsg), "out of range in clear -> pos : %d | size : %d\n", pos, size()); throw std::out_of_range(errmsg);
}
else if(!m_ref->get(pos))
{
return true;
}
else
{
if(m_ref->isShared())
{
__Ref_Array* last_ref = m_ref; m_ref = new __Ref_Array(*last_ref); last_ref->sharedSub();
} return m_ref->clear(pos);
}
} inline void
reset()
{if(m_ref) m_ref->reset();} inline int64_t
size()
{return m_ref ? m_ref->size() : ;} inline int64_t
length()
{return m_ref ? m_ref->length() : ;} inline int64_t
count()
{return m_ref ? m_ref->count() : ;}
private:
inline void
release() //引用计数释放
{
#ifdef __BIT_DEBUG__
fprintf(stderr, "BitArray released @addr： %p current reference : %d ...\n", this, m_ref->refCount());
#endif
if(m_ref && (m_ref->sharedSub() == ))
{
delete m_ref;
m_ref = null;
}
} __Ref_Array* m_ref;
}; #endif