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 { 7 fn get(bits: &Self, index: usize) -> bool; 8 fn set(bits: &mut Self, index: usize, value: bool) -> bool; 9 fn set_value(bits: &mut Self, value: Self); 10 fn len(bits: &Self) -> usize; 11 fn first_index(bits: &Self) -> Option<usize>; 12 fn first_false_index(bits: &Self) -> Option<usize>; 13 fn last_index(bits: &Self) -> Option<usize>; 14 fn last_false_index(bits: &Self) -> Option<usize>; 15 fn next_index(bits: &Self, index: usize) -> Option<usize>; 16 fn next_false_index(bits: &Self, index: usize) -> Option<usize>; 17 fn prev_index(bits: &Self, index: usize) -> Option<usize>; 18 fn prev_false_index(bits: &Self, index: usize) -> Option<usize>; 19 fn bit_and(bits: &mut Self, other_bits: &Self); 20 fn bit_or(bits: &mut Self, other_bits: &Self); 21 fn bit_xor(bits: &mut Self, other_bits: &Self); 22 fn invert(bits: &mut Self); 23 fn make_mask(shift: usize) -> Self; 24 fn bit_size() -> usize; 25 fn zero() -> Self; 26 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超出范围 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超出范围 233 fn set(&mut self, index: usize, value: bool) -> Option<bool>; 234 235 /// 将所有位设置为指定值 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 /// 250 fn len(&self) -> usize; 251 /// 获取bitmap的大小（以字节为单位） 252 fn size(&self) -> usize; 253 254 /// 获取第一个为1的位的index 255 /// 256 /// ## 返回 257 /// 258 /// - `Some(index)` - 第一个为1的位的index 259 /// - `None` - 不存在为1的位 260 fn first_index(&self) -> Option<usize>; 261 262 /// 获取第一个为0的位的index 263 /// 264 /// ## 返回 265 /// 266 /// - `Some(index)` - 第一个为0的位的index 267 /// - `None` - 不存在为0的位 268 fn first_false_index(&self) -> Option<usize>; 269 270 /// 获取最后一个为1的位的index 271 /// 272 /// ## 返回 273 /// 274 /// - `Some(index)` - 最后一个为1的位的index 275 /// - `None` - 不存在为1的位 276 fn last_index(&self) -> Option<usize>; 277 278 /// 获取最后一个为0的位的index 279 /// 280 /// ## 返回 281 /// 282 /// - `Some(index)` - 最后一个为0的位的index 283 /// - `None` - 不存在为0的位 284 fn last_false_index(&self) -> Option<usize>; 285 286 /// 获取指定index之后第一个为1的位的index 287 fn next_index(&self, index: usize) -> Option<usize>; 288 289 /// 获取指定index之后第一个为0的位的index 290 fn next_false_index(&self, index: usize) -> Option<usize>; 291 292 /// 获取指定index之前第一个为1的位的index 293 fn prev_index(&self, index: usize) -> Option<usize>; 294 295 /// 获取指定index之前第一个为0的位的index 296 fn prev_false_index(&self, index: usize) -> Option<usize>; 297 298 /// 反转bitmap 299 fn invert(&mut self); 300 301 /// 判断bitmap是否满了 302 fn is_full(&self) -> bool; 303 304 /// 判断bitmap是否为空 305 fn is_empty(&self) -> bool; 306 307 /// # Safety 308 /// *不应直接修改字节数组* 309 /// 310 /// 将bitmap转换为字节数组 311 unsafe fn as_bytes(&self) -> &[u8]; 312 } 313