alice.pds.demo.boltless.dev
This repository has no description
did:plc:3fwecdnvtcscjnrx2p4n7a…
1use super::BitPosition;
2use crate::error::GitError;
3
4#[derive(Clone)]
5pub(crate) struct Bitset {
6 words: Vec<u64>,
7}
8
9impl Bitset {
10 pub(crate) fn zeros(num_bits: usize) -> Self {
11 Self {
12 words: vec![0u64; num_bits.div_ceil(64)],
13 }
14 }
15
16 pub(crate) fn from_ewah(
17 vector: &gix_bitmap::ewah::Vec,
18 num_bits: usize,
19 ) -> Result<Self, GitError> {
20 if vector.num_bits() > num_bits {
21 return Err(GitError::Backend(
22 "bitmap entry is wider than the object count".to_string(),
23 ));
24 }
25 let mut bits = Self::zeros(num_bits);
26 let complete = vector.for_each_set_bit(|index| {
27 (index < num_bits).then(|| bits.set(BitPosition::new(index as u32)))
28 });
29 match complete {
30 Some(()) => Ok(bits),
31 None => Err(GitError::Backend("malformed ewah bitmap".to_string())),
32 }
33 }
34
35 pub(crate) fn set(&mut self, index: BitPosition) {
36 let index = index.get() as usize;
37 self.words[index / 64] |= 1u64 << (index % 64);
38 }
39
40 pub(crate) fn union_with(&mut self, other: &Bitset) {
41 self.words
42 .iter_mut()
43 .zip(&other.words)
44 .for_each(|(slot, bits)| *slot |= *bits);
45 }
46
47 pub(crate) fn difference_indices<'a>(
48 &'a self,
49 other: &'a Bitset,
50 ) -> impl Iterator<Item = BitPosition> + 'a {
51 self.words
52 .iter()
53 .zip(&other.words)
54 .enumerate()
55 .flat_map(|(word, (present, absent))| WordBits {
56 remaining: present & !absent,
57 base: (word as u32) * 64,
58 })
59 }
60}
61
62struct WordBits {
63 remaining: u64,
64 base: u32,
65}
66
67impl Iterator for WordBits {
68 type Item = BitPosition;
69
70 fn next(&mut self) -> Option<BitPosition> {
71 (self.remaining != 0).then(|| {
72 let offset = self.remaining.trailing_zeros();
73 self.remaining &= self.remaining - 1;
74 BitPosition::new(self.base + offset)
75 })
76 }
77}
78
79#[cfg(test)]
80mod tests {
81 use super::*;
82
83 fn set_bits(bits: &Bitset, other: &Bitset) -> Vec<u32> {
84 bits.difference_indices(other)
85 .map(BitPosition::get)
86 .collect()
87 }
88
89 #[test]
90 fn difference_yields_ascending_set_minus_set() {
91 let mut want = Bitset::zeros(130);
92 [1u32, 64, 65, 129]
93 .into_iter()
94 .for_each(|bit| want.set(BitPosition::new(bit)));
95 let mut have = Bitset::zeros(130);
96 [64u32, 129]
97 .into_iter()
98 .for_each(|bit| have.set(BitPosition::new(bit)));
99 assert_eq!(set_bits(&want, &have), vec![1, 65]);
100 }
101
102 #[test]
103 fn union_accumulates_both_operands() {
104 let mut acc = Bitset::zeros(70);
105 let mut other = Bitset::zeros(70);
106 acc.set(BitPosition::new(3));
107 other.set(BitPosition::new(3));
108 other.set(BitPosition::new(69));
109 acc.union_with(&other);
110 let empty = Bitset::zeros(70);
111 assert_eq!(set_bits(&acc, &empty), vec![3, 69]);
112 }
113}