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