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 #[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超出范围 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超出范围 238 fn set(&mut self, index: usize, value: bool) -> Option<bool>; 239 240 /// 将所有位设置为指定值 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 /// 255 fn len(&self) -> usize; 256 /// 获取bitmap的大小（以字节为单位） 257 fn size(&self) -> usize; 258 259 /// 获取第一个为1的位的index 260 /// 261 /// ## 返回 262 /// 263 /// - `Some(index)` - 第一个为1的位的index 264 /// - `None` - 不存在为1的位 265 fn first_index(&self) -> Option<usize>; 266 267 /// 获取第一个为0的位的index 268 /// 269 /// ## 返回 270 /// 271 /// - `Some(index)` - 第一个为0的位的index 272 /// - `None` - 不存在为0的位 273 fn first_false_index(&self) -> Option<usize>; 274 275 /// 获取最后一个为1的位的index 276 /// 277 /// ## 返回 278 /// 279 /// - `Some(index)` - 最后一个为1的位的index 280 /// - `None` - 不存在为1的位 281 fn last_index(&self) -> Option<usize>; 282 283 /// 获取最后一个为0的位的index 284 /// 285 /// ## 返回 286 /// 287 /// - `Some(index)` - 最后一个为0的位的index 288 /// - `None` - 不存在为0的位 289 fn last_false_index(&self) -> Option<usize>; 290 291 /// 获取指定index之后第一个为1的位的index 292 fn next_index(&self, index: usize) -> Option<usize>; 293 294 /// 获取指定index之后第一个为0的位的index 295 fn next_false_index(&self, index: usize) -> Option<usize>; 296 297 /// 获取指定index之前第一个为1的位的index 298 fn prev_index(&self, index: usize) -> Option<usize>; 299 300 /// 获取指定index之前第一个为0的位的index 301 fn prev_false_index(&self, index: usize) -> Option<usize>; 302 303 /// 反转bitmap 304 fn invert(&mut self); 305 306 /// 判断bitmap是否满了 307 fn is_full(&self) -> bool; 308 309 /// 判断bitmap是否为空 310 fn is_empty(&self) -> bool; 311 312 /// 将bitmap转换为字节数组 313 unsafe fn as_bytes(&self) -> &[u8]; 314 } 315