xref: /DragonOS/kernel/crates/bitmap/src/traits.rs (revision bd70d2d1f490aabd570a5301b858bd5eb04149fa) 
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             #[inline]
186             fn bit_size() -> usize {
187                 <$target>::BITS as usize
188             }
189 
190             #[inline]
191             fn zero() -> Self {
192                 0
193             }
194 
195             #[inline]
196             fn max() -> Self {
197                 <$target>::MAX
198             }
199         }
200     };
201 }
202 
203 // 为 `u8` 、 `u16` 、 `u32` 和 `u64` 实现 `BitOps` trait
204 bitops_for!(u8);
205 bitops_for!(u16);
206 bitops_for!(u32);
207 bitops_for!(u64);
208 bitops_for!(usize);
209 
210 /// Bitmap应当实现的trait
211 pub trait BitMapOps<T: BitOps> {
212     /// 获取指定index的位
213     ///
214     /// ## 返回
215     ///
216     /// - `Some(true)` - 该位为1
217     /// - `Some(false)` - 该位为0
218     /// - `None` - index超出范围
get(&self, index: usize) -> Option<bool>219     fn get(&self, index: usize) -> Option<bool>;
220 
221     /// 设置指定index的位，并返回该位之前的值
222     ///
223     /// ## 参数
224     ///
225     /// - `index` - 位的index
226     /// - `value` - 位的新值
227     ///
228     /// ## 返回
229     ///
230     /// - `Some(true)` - 该位之前为1
231     /// - `Some(false)` - 该位之前为0
232     /// - `None` - index超出范围
set(&mut self, index: usize, value: bool) -> Option<bool>233     fn set(&mut self, index: usize, value: bool) -> Option<bool>;
234 
235     /// 将所有位设置为指定值
set_all(&mut self, value: bool)236     fn set_all(&mut self, value: bool);
237 
238     /// 获取bitmap的长度（以位为单位）
239     ///
240     /// ## Example
241     ///
242     /// ```
243     /// use bitmap::StaticBitmap;
244     /// use bitmap::traits::BitMapOps;
245     ///
246     /// let mut bitmap = StaticBitmap::<34>::new();
247     /// assert_eq!(bitmap.len(), 34);
248     /// ```
249     ///
len(&self) -> usize250     fn len(&self) -> usize;
251     /// 获取bitmap的大小（以字节为单位）
size(&self) -> usize252     fn size(&self) -> usize;
253 
254     /// 获取第一个为1的位的index
255     ///
256     /// ## 返回
257     ///
258     /// - `Some(index)` - 第一个为1的位的index
259     /// - `None` - 不存在为1的位
first_index(&self) -> Option<usize>260     fn first_index(&self) -> Option<usize>;
261 
262     /// 获取第一个为0的位的index
263     ///
264     /// ## 返回
265     ///
266     /// - `Some(index)` - 第一个为0的位的index
267     /// - `None` - 不存在为0的位
first_false_index(&self) -> Option<usize>268     fn first_false_index(&self) -> Option<usize>;
269 
270     /// 获取最后一个为1的位的index
271     ///
272     /// ## 返回
273     ///
274     /// - `Some(index)` - 最后一个为1的位的index
275     /// - `None` - 不存在为1的位
last_index(&self) -> Option<usize>276     fn last_index(&self) -> Option<usize>;
277 
278     /// 获取最后一个为0的位的index
279     ///
280     /// ## 返回
281     ///
282     /// - `Some(index)` - 最后一个为0的位的index
283     /// - `None` - 不存在为0的位
last_false_index(&self) -> Option<usize>284     fn last_false_index(&self) -> Option<usize>;
285 
286     /// 获取指定index之后第一个为1的位的index
next_index(&self, index: usize) -> Option<usize>287     fn next_index(&self, index: usize) -> Option<usize>;
288 
289     /// 获取指定index之后第一个为0的位的index
next_false_index(&self, index: usize) -> Option<usize>290     fn next_false_index(&self, index: usize) -> Option<usize>;
291 
292     /// 获取指定index之前第一个为1的位的index
prev_index(&self, index: usize) -> Option<usize>293     fn prev_index(&self, index: usize) -> Option<usize>;
294 
295     /// 获取指定index之前第一个为0的位的index
prev_false_index(&self, index: usize) -> Option<usize>296     fn prev_false_index(&self, index: usize) -> Option<usize>;
297 
298     /// 反转bitmap
invert(&mut self)299     fn invert(&mut self);
300 
301     /// 判断bitmap是否满了
is_full(&self) -> bool302     fn is_full(&self) -> bool;
303 
304     /// 判断bitmap是否为空
is_empty(&self) -> bool305     fn is_empty(&self) -> bool;
306 
307     /// # Safety
308     /// *不应直接修改字节数组*
309     ///
310     /// 将bitmap转换为字节数组
as_bytes(&self) -> &[u8]311     unsafe fn as_bytes(&self) -> &[u8];
312 }
313