xref: /DragonOS/kernel/crates/bitmap/src/bitmap_core.rs (revision d2b28acb4d1f160779b25d76afca49ed60ad5d48) 
1 use core::{intrinsics::unlikely, marker::PhantomData};
2 
3 use crate::traits::BitOps;
4 
5 pub(crate) struct BitMapCore<T: BitOps> {
6     phantom: PhantomData<T>,
7 }
8 
9 impl<T: BitOps> BitMapCore<T> {
10     pub const fn new() -> Self {
11         Self {
12             phantom: PhantomData,
13         }
14     }
15 
16     /// 获取位图中的某一位
17     pub(crate) fn get(&self, n: usize, data: &[T], index: usize) -> Option<bool> {
18         if unlikely(index >= n) {
19             return None;
20         }
21 
22         let element_index = index / T::bit_size();
23         let bit_index = index % T::bit_size();
24 
25         let element = data.get(element_index)?;
26         let bit = <T as BitOps>::get(element, bit_index);
27 
28         Some(bit)
29     }
30 
31     /// 设置位图中的某一位
32     pub(crate) fn set(&self, n: usize, data: &mut [T], index: usize, value: bool) -> Option<bool> {
33         if unlikely(index >= n) {
34             return None;
35         }
36         let element_index = index / T::bit_size();
37         let bit_index = index % T::bit_size();
38 
39         let element = data.get_mut(element_index)?;
40         let bit = <T as BitOps>::set(element, bit_index, value);
41 
42         Some(bit)
43     }
44 
45     pub(crate) fn set_all(&self, n: usize, data: &mut [T], value: bool) {
46         let val = if value { T::max() } else { T::zero() };
47         for element in data.iter_mut() {
48             *element = val;
49         }
50 
51         // 特殊处理最后一个元素
52         let last_element = data.last_mut().unwrap();
53         let mask = T::make_mask(n % T::bit_size());
54         if mask != T::zero() {
55             *last_element &= mask;
56         }
57     }
58 
59     /// 获取位图中第一个为1的位
60     pub(crate) fn first_index(&self, data: &[T]) -> Option<usize> {
61         for (i, element) in data.iter().enumerate() {
62             let bit = <T as BitOps>::first_index(element);
63             if bit.is_some() {
64                 return Some(i * T::bit_size() + bit.unwrap());
65             }
66         }
67 
68         None
69     }
70 
71     /// 获取位图中第一个为0的位
72     pub(crate) fn first_false_index(&self, n: usize, data: &[T]) -> Option<usize> {
73         for (i, element) in data.iter().enumerate() {
74             if let Some(bit) = <T as BitOps>::first_false_index(element) {
75                 return self.make_index(n, i * T::bit_size() + bit);
76             }
77         }
78 
79         None
80     }
81 
82     /// 获取位图中最后一个为1的位
83     pub(crate) fn last_index(&self, n: usize, data: &[T]) -> Option<usize> {
84         for (i, element) in data.iter().enumerate().rev() {
85             if let Some(bit) = <T as BitOps>::last_index(element) {
86                 return self.make_index(n, i * T::bit_size() + bit);
87             }
88         }
89 
90         None
91     }
92 
93     /// 获取位图中最后一个为0的位
94     ///
95     /// ## 参数
96     ///
97     /// - `data`：位图数据
98     /// - `n`：位图有效位数
99     pub(crate) fn last_false_index(&self, n: usize, data: &[T]) -> Option<usize> {
100         let mut iter = data.iter().rev();
101         let mut last_element = *iter.next()?;
102 
103         // 对最后一个元素进行特殊处理，因为最后一个元素可能不是满的
104         let mut mask = T::make_mask(n % T::bit_size());
105         if mask != T::zero() {
106             <T as BitOps>::invert(&mut mask);
107 
108             last_element |= mask;
109         }
110 
111         if let Some(bit) = <T as BitOps>::last_false_index(&last_element) {
112             return self.make_index(n, (data.len() - 1) * T::bit_size() + bit);
113         }
114 
115         for element in iter {
116             if let Some(bit) = <T as BitOps>::last_false_index(element) {
117                 return self.make_index(n, (data.len() - 1) * T::bit_size() + bit);
118             }
119         }
120 
121         None
122     }
123 
124     /// 获取位图中下一个为1的位
125     pub(crate) fn next_index(&self, n: usize, data: &[T], index: usize) -> Option<usize> {
126         if unlikely(index >= n) {
127             return None;
128         }
129 
130         let element_index = index / T::bit_size();
131         let bit_index = index % T::bit_size();
132 
133         let element = data.get(element_index)?;
134         if let Some(bit) = <T as BitOps>::next_index(element, bit_index) {
135             return self.make_index(n, element_index * T::bit_size() + bit);
136         }
137 
138         for (i, element) in data.iter().enumerate().skip(element_index + 1) {
139             if let Some(bit) = <T as BitOps>::first_index(element) {
140                 return self.make_index(n, i * T::bit_size() + bit);
141             }
142         }
143 
144         None
145     }
146 
147     /// 获取位图中下一个为0的位
148     pub(crate) fn next_false_index(&self, n: usize, data: &[T], index: usize) -> Option<usize> {
149         if unlikely(index >= n) {
150             return None;
151         }
152 
153         let element_index = index / T::bit_size();
154         let bit_index = index % T::bit_size();
155 
156         let element = data.get(element_index)?;
157         if let Some(bit) = <T as BitOps>::next_false_index(element, bit_index) {
158             return self.make_index(n, element_index * T::bit_size() + bit);
159         }
160 
161         for (i, element) in data.iter().enumerate().skip(element_index + 1) {
162             if let Some(bit) = <T as BitOps>::first_false_index(element) {
163                 return self.make_index(n, i * T::bit_size() + bit);
164             }
165         }
166 
167         None
168     }
169 
170     /// 获取位图中上一个为1的位
171     pub(crate) fn prev_index(&self, n: usize, data: &[T], index: usize) -> Option<usize> {
172         if unlikely(index >= n) {
173             return None;
174         }
175         let element_index = index / T::bit_size();
176         let bit_index = index % T::bit_size();
177 
178         let element = data.get(element_index)?;
179         if let Some(bit) = <T as BitOps>::prev_index(element, bit_index) {
180             return self.make_index(n, element_index * T::bit_size() + bit);
181         }
182 
183         for (i, element) in data.iter().enumerate().take(element_index).rev() {
184             if let Some(bit) = <T as BitOps>::last_index(element) {
185                 return self.make_index(n, i * T::bit_size() + bit);
186             }
187         }
188 
189         None
190     }
191 
192     pub(crate) fn prev_false_index(&self, n: usize, data: &[T], index: usize) -> Option<usize> {
193         let element_index = index / T::bit_size();
194         let bit_index = index % T::bit_size();
195 
196         let element = data.get(element_index)?;
197         if let Some(bit) = <T as BitOps>::prev_false_index(element, bit_index) {
198             return self.make_index(n, element_index * T::bit_size() + bit);
199         }
200 
201         for (i, element) in data.iter().enumerate().take(element_index).rev() {
202             if let Some(bit) = <T as BitOps>::last_false_index(element) {
203                 return self.make_index(n, i * T::bit_size() + bit);
204             }
205         }
206 
207         None
208     }
209 
210     pub(crate) fn invert(&self, n: usize, data: &mut [T]) {
211         for element in data.iter_mut() {
212             <T as BitOps>::invert(element);
213         }
214 
215         // 特殊处理最后一个元素
216 
217         let last_element = data.last_mut().unwrap();
218         let mask = T::make_mask(n % T::bit_size());
219         if mask != T::zero() {
220             *last_element &= mask;
221         }
222     }
223 
224     pub(crate) fn is_full(&self, n: usize, data: &[T]) -> bool {
225         let mut iter = data.iter().peekable();
226         while let Some(element) = iter.next() {
227             if iter.peek().is_none() {
228                 // 这是最后一个元素，进行特殊处理
229                 let mut element = *element;
230                 let mut mask = T::make_mask(n % T::bit_size());
231                 if mask == T::zero() {
232                     mask = T::max();
233                 }
234 
235                 T::bit_and(&mut element, &mask);
236                 if element == mask {
237                     return true;
238                 }
239             } else {
240                 if element != &T::make_mask(T::bit_size()) {
241                     return false;
242                 }
243             }
244         }
245 
246         return false;
247     }
248 
249     pub(crate) fn is_empty(&self, data: &[T]) -> bool {
250         for element in data.iter() {
251             if element != &T::zero() {
252                 return false;
253             }
254         }
255 
256         return true;
257     }
258 
259     fn make_index(&self, n: usize, index: usize) -> Option<usize> {
260         if unlikely(index >= n) {
261             return None;
262         }
263 
264         Some(index)
265     }
266 }
267