C++ BitArray 引用計數實現，bitarray計數
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 void
102 reset()
103 {
104 memset(__M_array, 0, __M_length);
105 __M_used = 0;
106 }
107
108 /*
109 * 測試給定的pos是否合法
110 */
111 inline bool
112 range(__size_type __pos) const
113 {return __pos >= 0 && __pos < __M_size;}
114
115 /*
116 * 獲取數組的位個數
117 */
118 inline __size_type
119 size() const
120 {return __M_size;}
121
122 /*
123 * 獲取數組的字節長度
124 */
125 inline __size_type
126 length() const
127 {return __M_length;}
128
129 /*
130 * 獲取已使用的位個數
131 */
132 inline __size_type
133 used() const
134 {return __M_used;}
135
136 /*
137 * 獲取對象的引用計數
138 */
139 inline __size_type
140 refcount() const
141 {return __M_refcount;}
142
143 public:
144 __size_type
145 operator ++()
146 {return ++__M_refcount;}
147
148 __size_type
149 operator --()
150 {return --__M_refcount;}
151
152 __size_type
153 operator ++(int)
154 {return __M_refcount ++;}
155
156 __size_type
157 operator --(int)
158 {return __M_refcount --;}
159 private:
160
161 /*
162 * 分配內存
163 */
164 inline void
165 alloc()
166 {__M_array = new __bit_type[__M_length];}
167
168
169 /*
170 * 初始化數組
171 * 分配內存，清空數據
172 */
173 inline void
174 init_array()
175 {
176 __M_length = nslots(__M_size);
177 alloc();
178 reset();
179 }
180
181 /*
182 * 獲取一位的掩碼
183 */
184 inline __bit_type
185 mask(__size_type __pos) const
186 {return __bit_type(1) << (__pos % __ref_byte);}
187
188
189 /*
190 * 計算數組的長度
191 */
192 inline __size_type
193 nslots(__size_type __size) const
194 {return (__size + __ref_byte - 1) / __ref_byte;}
195
196 /*
197 * 計算pos所在的位置
198 */
199 inline __size_type
200 slot(__size_type __pos) const
201 {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) noexcept
214 :__M_ref((size == 0) ? __nullptr : new __Ref_Array(size))
215 {}
216
217 BitArray() noexcept
218 :__M_ref(__nullptr)
219 {}
220
221 BitArray(const BitArray& other) noexcept
222 :__M_ref(other.__M_ref)
223 {(*__M_ref) ++;}
224
225 #if __cplusplus >= 201103L
226 BitArray(BitArray&& other) noexcept
227 :__M_ref(other.__M_ref)
228 {other.__M_ref = __nullptr;}
229 #endif
230
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_t
245 size() const
246 {return __M_ref ? __M_ref->size() : 0;}
247
248 inline int32_t
249 length() const
250 {return __M_ref ? __M_ref->length() : 0;}
251
252 inline int32_t
253 used() const
254 {return __M_ref ? __M_ref->used() : 0;}
255
256 public:
257 inline bool
258 test(int32_t pos) const
259 {return __M_ref && __M_ref->range(pos) ? __M_ref->test(pos) : false;}
260
261 inline bool
262 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 else
273 {
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 bool
289 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 else
300 {
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 void
315 reset()
316 {if(__M_ref) __M_ref->reset();}
317
318 private:
319
320 inline void
321 release()
322 {if( -- (*__M_ref) == 0) delete __M_ref;}
323
324 __Ref_Array* __M_ref;
325 };
326
327
328 #endif
