1 #ifndef __BITARRAY__  2 #define __BITARRAY__ 1  3   4 #include <cstdio>  5 #include <cstring>  6   7 #if __cplusplus >= 201103L  8 #include <cstdint>  9 #else 10 #include <stdint.h> 11 #endif 12  13 #if __cplusplus < 201103L 14 #define __nullptr NULL 15 #else 16 #define __nullptr nullptr 17 #endif 18  19 class BitArray 20 { 21     private: 22         /*引用计数*/ 23         class __Ref_Array 24         {   25         private: 26             typedef int8_t  __bit_type; 27             typedef int32_t __size_type; 28             typedef int32_t __length_type; 29  30             enum __enum_bit 31             { 32                 __ref_byte = 8, 33             }; 34  35         public: 36             /* 37              * 构造函数 38              * 构造空的位数组 39             */ 40             __Ref_Array(__size_type __size) noexcept 41                 :__M_size(__size), __M_refcount(1) 42             {init_array();} 43  44             /* 45              * 拷贝构造函数 46              * 直接拷贝所有内容，引用计数置1 47             */ 48             __Ref_Array(const __Ref_Array& other) noexcept 49                 :__M_used(other.__M_used), __M_size(other.__M_size), 50                   __M_length(other.__M_length), __M_refcount(1) 51             { 52                 alloc(); 53                 memcpy(__M_array, other.__M_array, __M_length); 54             } 55  56             /* 57              * 析构函数 58              * 析构资源 59             */ 60             ~__Ref_Array() 61             {if(__M_refcount == 0 && !__M_array) delete[] __M_array;} 62  63         public: 64  65             /* 66              * 测试一位的状态 67             */ 68             inline bool 69             test(__size_type __pos) const 70             {return *(__M_array + slot(__pos)) & mask(__pos);} 71  72             /* 73              * 设置一位的状态 74             */ 75             inline bool 76             set(__size_type __pos) 77             { 78                 (*(__M_array + slot(__pos)) |= mask(__pos)); 79  80                 __M_used ++; 81  82                 return true; 83             } 84  85             /* 86              * 清除一位的状态 87             */ 88             inline bool 89             clear(__size_type __pos) 90             { 91                 (*(__M_array + slot(__pos)) &= ~mask(__pos)); 92  93                 __M_used --; 94  95                 return true; 96             } 97  98             /* 99              * 清除所有的状态设置100             */101             inline void102             reset()103             {104                 memset(__M_array, 0, __M_length);105                 __M_used = 0;106             }107 108             /*109              * 测试给定的pos是否合法110             */111             inline bool112             range(__size_type __pos) const113             {return __pos >= 0 && __pos < __M_size;}114 115             /*116              * 获取数组的位个数117             */118             inline __size_type119             size() const120             {return __M_size;}121 122             /*123              * 获取数组的字节长度124             */125             inline __size_type126             length() const127             {return __M_length;}128 129             /*130              * 获取已使用的位个数131             */132             inline __size_type133             used()  const134             {return __M_used;}135 136             /*137              * 获取对象的引用计数138             */139             inline __size_type140             refcount() const141             {return __M_refcount;}142 143         public:144             __size_type145             operator ++()146             {return ++__M_refcount;}147 148             __size_type149             operator --()150             {return --__M_refcount;}151 152             __size_type153             operator ++(int)154             {return __M_refcount ++;}155 156             __size_type157             operator --(int)158             {return __M_refcount --;}159         private:160 161             /*162              * 分配内存163             */164             inline void165             alloc()166             {__M_array = new __bit_type[__M_length];}167 168 169             /*170              * 初始化数组171              * 分配内存，清空数据172             */173             inline void174             init_array()175             {176                 __M_length = nslots(__M_size);177                 alloc();178                 reset();179             }180 181             /*182              * 获取一位的掩码183             */184             inline __bit_type185             mask(__size_type __pos) const186             {return __bit_type(1) << (__pos % __ref_byte);}187 188 189             /*190              * 计算数组的长度191             */192             inline __size_type193             nslots(__size_type __size) const194             {return (__size + __ref_byte - 1) / __ref_byte;}195 196             /*197              * 计算pos所在的位置198             */199             inline __size_type200             slot(__size_type __pos) const201             {return __pos / __ref_byte;}202 203         private:204 205             __bit_type*     __M_array;      //数组空间206             __size_type        __M_used;       //已用计数207             __size_type        __M_size;       //位个数208             __length_type    __M_length;     //数组的字节大小209             __size_type     __M_refcount;   //引用计数210         };211 212 public:213     BitArray(int32_t size) noexcept214         :__M_ref((size == 0) ? __nullptr : new __Ref_Array(size))215     {}216 217     BitArray() noexcept218         :__M_ref(__nullptr)219     {}220 221     BitArray(const BitArray& other) noexcept222         :__M_ref(other.__M_ref)223     {(*__M_ref) ++;}224 225 #if __cplusplus >= 201103L226     BitArray(BitArray&& other) noexcept227         :__M_ref(other.__M_ref)228     {other.__M_ref = __nullptr;}229 #endif230 231     BitArray&232     operator = (const BitArray& other)233     {234         if(__M_ref != other.__M_ref)235         {236             release();237             __M_ref = other.__M_ref;238             (*__M_ref) ++;239         }240 241         return *this;242     }243 public:244     inline int32_t245     size() const246     {return __M_ref ? __M_ref->size() : 0;}247 248     inline int32_t249     length() const250     {return __M_ref ? __M_ref->length() : 0;}251 252     inline int32_t253     used() const254     {return __M_ref ? __M_ref->used() : 0;}255 256 public:257     inline bool258     test(int32_t pos) const259     {return __M_ref && __M_ref->range(pos) ? __M_ref->test(pos) : false;}260 261     inline bool262     set(int32_t pos)263     {264         if(!__M_ref || !__M_ref->range(pos))265         {266             return false;267         }268         else if(__M_ref->test(pos))269         {270             return true;271         }272         else273         {274             if(__M_ref->refcount() > 1)275             {276                 //当数组的引用计数大于1 要复制然后设置277                 __Ref_Array* __last_ref = __M_ref;278 279                 __M_ref = new __Ref_Array(*__last_ref);280 281                 (*__last_ref) --;282             }283 284             return __M_ref->set(pos);285         }286     }287 288     inline bool289     clear(int32_t pos)290     {291         if(!__M_ref || !__M_ref->range(pos))292         {293             return false;294         }295         else if(!__M_ref->test(pos))296         {297             return true;298         }299         else300         {301             if(__M_ref->refcount() > 1)302             {303                 __Ref_Array* __last_ref = __M_ref;304 305                 __M_ref = new __Ref_Array(*__last_ref);306 307                 (*__last_ref) --;308             }309 310             return __M_ref->clear(pos);311         }312     }313 314     inline void315     reset()316     {if(__M_ref) __M_ref->reset();}317 318 private:319 320     inline void321     release()322     {if( -- (*__M_ref) == 0) delete __M_ref;}323 324     __Ref_Array* __M_ref;325 };326 327 328 #endif