4354627675

Build Type

push

github

Committed by GitHub

Commit Message

chore: Use `LmdbMap` and `LmdbMultimap` instead of raw database in cache (#1156)

Run Details

754 of 754 new or added lines in 15 files covered. (100.0%)

29895 of 39630 relevant lines covered (75.44%)

38604.24 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

82.05

/dozer-cache/src/cache/lmdb/cache/query/intersection.rs

use roaring::{MultiOps, RoaringTreemap};

pub fn intersection<E, I: Iterator<Item = Result<u64, E>>>(
    iterators: Vec<I>,
    chunk_size: usize,
) -> Intersection<E, I> {
    let all_iterated_ids = vec![RoaringTreemap::new(); iterators.len()];
    Intersection {
        intersection: None,
        iterators,
        all_iterated_ids,
        chunk_size,
    }
}

pub struct Intersection<E, I: Iterator<Item = Result<u64, E>>> {
    intersection: Option<roaring::treemap::IntoIter>,
    iterators: Vec<I>,
    all_iterated_ids: Vec<RoaringTreemap>,
    chunk_size: usize,
}

impl<E, I: Iterator<Item = Result<u64, E>>> Iterator for Intersection<E, I> {
    type Item = Result<u64, E>;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            if let Some(intersection) = &mut self.intersection {
                if let Some(id) = intersection.next() {
                    return Some(Ok(id));
                } else {
                    self.intersection = None;
                }
            }

            let mut exhaused = true;

            // Get the next chunk of each iterator.
            for (iterated_ids, iterator) in self
                .all_iterated_ids
                .iter_mut()
                .zip(self.iterators.iter_mut())
            {
                for _ in 0..self.chunk_size {
                    if let Some(id) = iterator.next() {
                        exhaused = false;
                        match id {
                            Ok(id) => {
                                iterated_ids.insert(id);
                            }
                            Err(e) => {
                                return Some(Err(e));
                            }
                        }
                    } else {
                        break;
                    }
                }
            }

            if exhaused {
                return None;
            }

            // Emit the intersection of all ids.
            let intersection = self.all_iterated_ids.iter().intersection();
            for iterated_ids in self.all_iterated_ids.iter_mut() {
                *iterated_ids -= &intersection;
            }
            self.intersection = Some(intersection.into_iter());
        }
    }
}

#[cfg(test)]
mod tests {
    use std::convert::Infallible;

    use super::*;

    #[test]
    fn test_intersection() {
        let a = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
        let b = vec![1, 3, 5, 7, 9];
        let c = vec![1, 2, 3, 5, 8];
        let intersection = intersection(
            vec![
                a.into_iter().map(Ok),
                b.into_iter().map(Ok),
                c.into_iter().map(Ok),
            ],
            2,
        );
        assert_eq!(
            intersection
                .collect::<Result<Vec<_>, Infallible>>()
                .unwrap(),
            vec![1, 3, 5]
        );
    }
}

1	use roaring::{MultiOps, RoaringTreemap};
2
3	pub fn intersection<E, I: Iterator<Item = Result<u64, E>>>(	3✔
4	iterators: Vec<I>,	3✔
5	chunk_size: usize,	3✔
6	) -> Intersection<E, I> {	3✔
7	let all_iterated_ids = vec![RoaringTreemap::new(); iterators.len()];	3✔
8	Intersection {	3✔
9	intersection: None,	3✔
10	iterators,	3✔
11	all_iterated_ids,	3✔
12	chunk_size,	3✔
13	}	3✔
14	}	3✔
15
16	pub struct Intersection<E, I: Iterator<Item = Result<u64, E>>> {
17	intersection: Option<roaring::treemap::IntoIter>,
18	iterators: Vec<I>,
19	all_iterated_ids: Vec<RoaringTreemap>,
20	chunk_size: usize,
21	}
22
23	impl<E, I: Iterator<Item = Result<u64, E>>> Iterator for Intersection<E, I> {
24	type Item = Result<u64, E>;
25
26	fn next(&mut self) -> Option<Self::Item> {	10✔
27	loop {
28	if let Some(intersection) = &mut self.intersection {	17✔
29	if let Some(id) = intersection.next() {	14✔
30	return Some(Ok(id));	7✔
31	} else {	7✔
32	self.intersection = None;	7✔
33	}	7✔
34	}	3✔
35
36	let mut exhaused = true;	10✔
37		×
38	// Get the next chunk of each iterator.	×
39	for (iterated_ids, iterator) in self	26✔
40	.all_iterated_ids	10✔
41	.iter_mut()	10✔
42	.zip(self.iterators.iter_mut())	10✔
43	{	×
44	for _ in 0..self.chunk_size {	26✔
45	if let Some(id) = iterator.next() {	55✔
46	exhaused = false;	38✔
47	match id {	38✔
48	Ok(id) => {	38✔
49	iterated_ids.insert(id);	38✔
50	}	38✔
51	Err(e) => {	×
52	return Some(Err(e));	×
53	}	×
54	}	×
55	} else {	×
56	break;	17✔
57	}	×
58	}	×
59	}	×
60		×
61	if exhaused {	10✔
62	return None;	3✔
63	}	7✔
64		7✔
65	// Emit the intersection of all ids.	7✔
66	let intersection = self.all_iterated_ids.iter().intersection();	7✔
67	for iterated_ids in self.all_iterated_ids.iter_mut() {	19✔
68	*iterated_ids -= &intersection;	19✔
69	}	19✔
70	self.intersection = Some(intersection.into_iter());	7✔
71	}	×
72	}	10✔
73	}	×
74
75	#[cfg(test)]
76	mod tests {
77	use std::convert::Infallible;
78
79	use super::*;
80
81	#[test]	1✔
82	fn test_intersection() {	1✔
83	let a = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];	1✔
84	let b = vec![1, 3, 5, 7, 9];	1✔
85	let c = vec![1, 2, 3, 5, 8];	1✔
86	let intersection = intersection(	1✔
87	vec![	1✔
88	a.into_iter().map(Ok),	1✔
89	b.into_iter().map(Ok),	1✔
90	c.into_iter().map(Ok),	1✔
91	],	1✔
92	2,	1✔
93	);	1✔
94	assert_eq!(	1✔
95	intersection	1✔
96	.collect::<Result<Vec<_>, Infallible>>()	1✔
97	.unwrap(),	1✔
98	vec![1, 3, 5]	1✔
99	);	1✔
100	}	1✔
101	}

getdozer / dozer / 4354627675

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous