1 use core::ops::{BitAnd, BitAndAssign, BitOrAssign, Not};
2 
3 /// A trait that defines generalised operations on a `Bits::Store` type.
4 pub trait BitOps:
5     BitAndAssign + Sized + Copy + PartialEq + Not + BitOrAssign + BitOrAssign + BitAnd
6 {
get(bits: &Self, index: usize) -> bool7     fn get(bits: &Self, index: usize) -> bool;
set(bits: &mut Self, index: usize, value: bool) -> bool8     fn set(bits: &mut Self, index: usize, value: bool) -> bool;
set_value(bits: &mut Self, value: Self)9     fn set_value(bits: &mut Self, value: Self);
len(bits: &Self) -> usize10     fn len(bits: &Self) -> usize;
first_index(bits: &Self) -> Option<usize>11     fn first_index(bits: &Self) -> Option<usize>;
first_false_index(bits: &Self) -> Option<usize>12     fn first_false_index(bits: &Self) -> Option<usize>;
last_index(bits: &Self) -> Option<usize>13     fn last_index(bits: &Self) -> Option<usize>;
last_false_index(bits: &Self) -> Option<usize>14     fn last_false_index(bits: &Self) -> Option<usize>;
next_index(bits: &Self, index: usize) -> Option<usize>15     fn next_index(bits: &Self, index: usize) -> Option<usize>;
next_false_index(bits: &Self, index: usize) -> Option<usize>16     fn next_false_index(bits: &Self, index: usize) -> Option<usize>;
prev_index(bits: &Self, index: usize) -> Option<usize>17     fn prev_index(bits: &Self, index: usize) -> Option<usize>;
prev_false_index(bits: &Self, index: usize) -> Option<usize>18     fn prev_false_index(bits: &Self, index: usize) -> Option<usize>;
bit_and(bits: &mut Self, other_bits: &Self)19     fn bit_and(bits: &mut Self, other_bits: &Self);
bit_or(bits: &mut Self, other_bits: &Self)20     fn bit_or(bits: &mut Self, other_bits: &Self);
bit_xor(bits: &mut Self, other_bits: &Self)21     fn bit_xor(bits: &mut Self, other_bits: &Self);
invert(bits: &mut Self)22     fn invert(bits: &mut Self);
make_mask(shift: usize) -> Self23     fn make_mask(shift: usize) -> Self;
bit_size() -> usize24     fn bit_size() -> usize;
zero() -> Self25     fn zero() -> Self;
max() -> Self26     fn max() -> Self;
27 }
28 
29 macro_rules! bitops_for {
30     ($target:ty) => {
31         impl BitOps for $target {
32             #[inline]
33             fn get(bits: &Self, index: usize) -> bool {
34                 bits & (1 << index) != 0
35             }
36 
37             #[inline]
38             fn set(bits: &mut Self, index: usize, value: bool) -> bool {
39                 let mask = 1 << index;
40                 let prev = *bits & mask;
41                 if value {
42                     *bits |= mask;
43                 } else {
44                     *bits &= !mask;
45                 }
46                 prev != 0
47             }
48 
49             #[inline]
50             fn set_value(bits: &mut Self, value: Self) {
51                 *bits = value;
52             }
53 
54             #[inline]
55             fn len(bits: &Self) -> usize {
56                 bits.count_ones() as usize
57             }
58 
59             #[inline]
60             fn first_index(bits: &Self) -> Option<usize> {
61                 if *bits == 0 {
62                     None
63                 } else {
64                     Some(bits.trailing_zeros() as usize)
65                 }
66             }
67 
68             #[inline]
69             fn first_false_index(bits: &Self) -> Option<usize> {
70                 if *bits == <$target>::MAX {
71                     None
72                 } else {
73                     Some(bits.trailing_ones() as usize)
74                 }
75             }
76 
77             #[inline]
78             fn last_index(bits: &Self) -> Option<usize> {
79                 if *bits == 0 {
80                     None
81                 } else {
82                     Some(<$target>::BITS as usize - 1 - (bits.leading_zeros() as usize))
83                 }
84             }
85 
86             #[inline]
87             fn last_false_index(bits: &Self) -> Option<usize> {
88                 if *bits == <$target>::MAX {
89                     None
90                 } else {
91                     Some(<$target>::BITS as usize - 1 - bits.leading_ones() as usize)
92                 }
93             }
94 
95             #[inline]
96             fn next_index(bits: &Self, index: usize) -> Option<usize> {
97                 if *bits == 0 || index >= <$target>::BITS as usize - 1 {
98                     None
99                 } else {
100                     let intermediate =
101                         (*bits & (<$target>::MAX.overflowing_shl(1 + index as u32).0));
102 
103                     if intermediate == 0 {
104                         None
105                     } else {
106                         Some(intermediate.trailing_zeros() as usize)
107                     }
108                 }
109             }
110 
111             #[inline]
112             fn next_false_index(bits: &Self, index: usize) -> Option<usize> {
113                 if *bits == <$target>::MAX || index >= <$target>::BITS as usize - 1 {
114                     None
115                 } else {
116                     let intermediate = (*bits | ((1 << (index + 1)) - 1));
117 
118                     if intermediate == <$target>::MAX {
119                         None
120                     } else {
121                         Some(intermediate.trailing_ones() as usize)
122                     }
123                 }
124             }
125 
126             #[inline]
127             fn prev_index(bits: &Self, index: usize) -> Option<usize> {
128                 if *bits == 0 || index == 0 {
129                     None
130                 } else {
131                     let intermediate = bits & ((1 << index) - 1);
132 
133                     if intermediate == 0 {
134                         None
135                     } else {
136                         Some(<$target>::BITS as usize - 1 - (intermediate.leading_zeros() as usize))
137                     }
138                 }
139             }
140 
141             #[inline]
142             fn prev_false_index(bits: &Self, index: usize) -> Option<usize> {
143                 if *bits == <$target>::MAX || index == 0 {
144                     None
145                 } else {
146                     let intermediate = bits | (<$target>::MAX.overflowing_shl(index as u32).0);
147 
148                     if intermediate == <$target>::MAX {
149                         None
150                     } else {
151                         Some(<$target>::BITS as usize - 1 - (intermediate.leading_ones() as usize))
152                     }
153                 }
154             }
155 
156             #[inline]
157             fn bit_and(bits: &mut Self, other_bits: &Self) {
158                 *bits &= *other_bits;
159             }
160 
161             #[inline]
162             fn bit_or(bits: &mut Self, other_bits: &Self) {
163                 *bits |= *other_bits;
164             }
165 
166             #[inline]
167             fn bit_xor(bits: &mut Self, other_bits: &Self) {
168                 *bits ^= *other_bits;
169             }
170 
171             #[inline]
172             fn invert(bits: &mut Self) {
173                 *bits = !*bits;
174             }
175 
176             #[inline]
177             fn make_mask(shift: usize) -> Self {
178                 if shift == <$target>::BITS as usize {
179                     <$target>::MAX
180                 } else {
181                     (1 << shift) - 1
182                 }
183             }
184 
185             #[cfg(feature = "std")]
186             fn to_hex(bits: &Self) -> String {
187                 format!("{:x}", bits)
188             }
189 
190             #[inline]
191             fn bit_size() -> usize {
192                 <$target>::BITS as usize
193             }
194 
195             #[inline]
196             fn zero() -> Self {
197                 0
198             }
199 
200             #[inline]
201             fn max() -> Self {
202                 <$target>::MAX
203             }
204         }
205     };
206 }
207 
208 // 为 `u8` 、 `u16` 、 `u32` 和 `u64` 实现 `BitOps` trait
209 bitops_for!(u8);
210 bitops_for!(u16);
211 bitops_for!(u32);
212 bitops_for!(u64);
213 bitops_for!(usize);
214 
215 /// Bitmap应当实现的trait
216 pub trait BitMapOps<T: BitOps> {
217     /// 获取指定index的位
218     ///
219     /// ## 返回
220     ///
221     /// - `Some(true)` - 该位为1
222     /// - `Some(false)` - 该位为0
223     /// - `None` - index超出范围
get(&self, index: usize) -> Option<bool>224     fn get(&self, index: usize) -> Option<bool>;
225 
226     /// 设置指定index的位，并返回该位之前的值
227     ///
228     /// ## 参数
229     ///
230     /// - `index` - 位的index
231     /// - `value` - 位的新值
232     ///
233     /// ## 返回
234     ///
235     /// - `Some(true)` - 该位之前为1
236     /// - `Some(false)` - 该位之前为0
237     /// - `None` - index超出范围
set(&mut self, index: usize, value: bool) -> Option<bool>238     fn set(&mut self, index: usize, value: bool) -> Option<bool>;
239 
240     /// 将所有位设置为指定值
set_all(&mut self, value: bool)241     fn set_all(&mut self, value: bool);
242 
243     /// 获取bitmap的长度（以位为单位）
244     ///
245     /// ## Example
246     ///
247     /// ```
248     /// use bitmap::StaticBitmap;
249     /// use bitmap::traits::BitMapOps;
250     ///
251     /// let mut bitmap = StaticBitmap::<34>::new();
252     /// assert_eq!(bitmap.len(), 34);
253     /// ```
254     ///
len(&self) -> usize255     fn len(&self) -> usize;
256     /// 获取bitmap的大小（以字节为单位）
size(&self) -> usize257     fn size(&self) -> usize;
258 
259     /// 获取第一个为1的位的index
260     ///
261     /// ## 返回
262     ///
263     /// - `Some(index)` - 第一个为1的位的index
264     /// - `None` - 不存在为1的位
first_index(&self) -> Option<usize>265     fn first_index(&self) -> Option<usize>;
266 
267     /// 获取第一个为0的位的index
268     ///
269     /// ## 返回
270     ///
271     /// - `Some(index)` - 第一个为0的位的index
272     /// - `None` - 不存在为0的位
first_false_index(&self) -> Option<usize>273     fn first_false_index(&self) -> Option<usize>;
274 
275     /// 获取最后一个为1的位的index
276     ///
277     /// ## 返回
278     ///
279     /// - `Some(index)` - 最后一个为1的位的index
280     /// - `None` - 不存在为1的位
last_index(&self) -> Option<usize>281     fn last_index(&self) -> Option<usize>;
282 
283     /// 获取最后一个为0的位的index
284     ///
285     /// ## 返回
286     ///
287     /// - `Some(index)` - 最后一个为0的位的index
288     /// - `None` - 不存在为0的位
last_false_index(&self) -> Option<usize>289     fn last_false_index(&self) -> Option<usize>;
290 
291     /// 获取指定index之后第一个为1的位的index
next_index(&self, index: usize) -> Option<usize>292     fn next_index(&self, index: usize) -> Option<usize>;
293 
294     /// 获取指定index之后第一个为0的位的index
next_false_index(&self, index: usize) -> Option<usize>295     fn next_false_index(&self, index: usize) -> Option<usize>;
296 
297     /// 获取指定index之前第一个为1的位的index
prev_index(&self, index: usize) -> Option<usize>298     fn prev_index(&self, index: usize) -> Option<usize>;
299 
300     /// 获取指定index之前第一个为0的位的index
prev_false_index(&self, index: usize) -> Option<usize>301     fn prev_false_index(&self, index: usize) -> Option<usize>;
302 
303     /// 反转bitmap
invert(&mut self)304     fn invert(&mut self);
305 
306     /// 判断bitmap是否满了
is_full(&self) -> bool307     fn is_full(&self) -> bool;
308 
309     /// 判断bitmap是否为空
is_empty(&self) -> bool310     fn is_empty(&self) -> bool;
311 
312     /// 将bitmap转换为字节数组
as_bytes(&self) -> &[u8]313     unsafe fn as_bytes(&self) -> &[u8];
314 }
315