19278972970

Committed 11 Nov 2025 09:25PM UTC coverage: 62.316% (+14.3%) from 48.052%

Build # 19278972970

Build Type

push

github

Committed by

zommiommy

Commit Message

BatchCodec print stats and encoding time

Run Details

40 of 53 new or added lines in 4 files covered. (75.47%)

814 existing lines in 46 files now uncovered.

5252 of 8428 relevant lines covered (62.32%)

29580067.92 hits per line

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

84.62

/webgraph/src/traits/split.rs

/*
 * SPDX-FileCopyrightText: 2023 Tommaso Fontana
 * SPDX-FileCopyrightText: 2023 Sebastiano Vigna
 *
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
 */

//! Traits and basic implementations to support parallel completion by splitting
//! the [iterator](SequentialLabeling::Lender) of a labeling into multiple
//! iterators.

use std::rc::Rc;

use impl_tools::autoimpl;

use super::{labels::SequentialLabeling, lenders::NodeLabelsLender};

/// A trait with a single method that splits a labeling into `n` parts which are
/// thread safe.
///
/// Labeling implementing this trait can be analyzed in parallel by calling
/// [`split_iter`](SplitLabeling::split_iter) to split the labeling
/// [iterator](SequentialLabeling::Lender) into `n` parts.
///
/// Each part is returned as a tuple `(usize, SplitLender)` where the first
/// element indicates the first node ID covered by that lender.
///
/// Note that the parts are required to be [`Send`] and [`Sync`], so that they
/// can be safely shared among threads.
///
/// Due to some limitations of the current Rust type system, we cannot provide
/// blanket implementations for this trait. However, we provide ready-made
/// implementations for the [sequential](seq) and [random-access](ra) cases. To
/// use them, you must implement the trait by specifying the associated types
/// `Lender` and `IntoIterator`, and then just return a [`seq::Iter`] or
/// [`ra::Iter`] structure.
#[autoimpl(for<S: trait + ?Sized> &S, &mut S, Rc<S>)]
pub trait SplitLabeling: SequentialLabeling {
    type SplitLender<'a>: for<'next> NodeLabelsLender<'next, Label = <Self as SequentialLabeling>::Label>
        + Send
        + Sync
    where
        Self: 'a;

    type IntoIterator<'a>: IntoIterator<Item = Self::SplitLender<'a>, IntoIter: ExactSizeIterator>
    where
        Self: 'a;

    fn split_iter(&self, n: usize) -> Self::IntoIterator<'_>;
}

/// Ready-made implementation for the sequential case.
///
/// This implementation walks through the iterator of a labeling and
/// clones it at regular intervals. To use it, you have to implement the
/// trait by specifying the associated types `Lender` and `IntoIterator`
/// using the [`seq::Lender`] and [`seq::IntoIterator`] types aliases,
/// and then return a [`seq::Iter`] structure.
///
/// # Examples
///
/// The code for [`BvGraphSeq`](crate::graphs::bvgraph::sequential::BvGraphSeq) is:
/// ```ignore
/// impl<F: SequentialDecoderFactory> SplitLabeling for BvGraphSeq<F>
/// where
///     for<'a> <F as SequentialDecoderFactory>::Decoder<'a>: Clone + Send + Sync,
/// {
///     type SplitLender<'a> = split::seq::Lender<'a, BvGraphSeq<F>> where Self: 'a;
///     type IntoIterator<'a> = split::seq::IntoIterator<'a, BvGraphSeq<F>> where Self: 'a;
///
///     fn split_iter(&self, how_many: usize) -> Self::IntoIterator<'_> {
///         split::seq::Iter::new(self.iter(), self.num_nodes(), how_many)
///     }
/// }
/// ```
pub mod seq {
    use crate::prelude::SequentialLabeling;

    pub struct Iter<L> {
        lender: L,
        nodes_per_iter: usize,
        how_many: usize,
        remaining: usize,
        current_node: usize,
    }

    impl<L: lender::Lender> Iter<L> {
        pub fn new(lender: L, number_of_nodes: usize, how_many: usize) -> Self {
            let nodes_per_iter = number_of_nodes.div_ceil(how_many);
            Self {
                lender,
                nodes_per_iter,
                how_many,
                remaining: how_many,
                current_node: 0,
            }
        }
    }

    impl<L: lender::Lender + Clone> Iterator for Iter<L> {
        type Item = lender::Take<L>;

        fn next(&mut self) -> Option<Self::Item> {
            if self.remaining == 0 {
                return None;
            }
            if self.remaining != self.how_many {
                self.lender.advance_by(self.nodes_per_iter).ok()?;
            }
            self.current_node += self.nodes_per_iter;
            self.remaining -= 1;
            Some(self.lender.clone().take(self.nodes_per_iter))
        }

        fn size_hint(&self) -> (usize, Option<usize>) {
            (self.remaining, Some(self.remaining))
        }
    }

    impl<L: lender::Lender + Clone> ExactSizeIterator for Iter<L> {
        fn len(&self) -> usize {
            self.remaining
        }
    }

    pub type Lender<'a, S> = lender::Take<<S as SequentialLabeling>::Lender<'a>>;
    pub type IntoIterator<'a, S> = Iter<<S as SequentialLabeling>::Lender<'a>>;
}

/// Ready-made implementation for the random-access case.
///
/// This implementation uses the [`iter_from`](SequentialLabeling::iter_from) at
/// regular intervals. To use it, you have to implement the trait by specifying
/// the associated types `Lender` and `IntoIterator` using the [`ra::Lender`]
/// and [`ra::IntoIterator`] types aliases, and then return a [`ra::Iter`]
/// structure.
///
/// # Examples
///
/// The code for [`BvGraph`](crate::graphs::bvgraph::random_access::BvGraph) is
/// ```ignore
/// impl<F: RandomAccessDecoderFactory> SplitLabeling for BvGraph<F>
/// where
///     for<'a> <F as RandomAccessDecoderFactory>::Decoder<'a>: Send + Sync,
/// {
///     type SplitLender<'a> = split::ra::Lender<'a, BvGraph<F>> where Self: 'a;
///     type IntoIterator<'a> = split::ra::IntoIterator<'a, BvGraph<F>> where Self: 'a;
///
///     fn split_iter(&self, how_many: usize) -> Self::IntoIterator<'_> {
///         split::ra::Iter::new(self, how_many)
///     }
/// }
/// ```
pub mod ra {
    use crate::prelude::{RandomAccessLabeling, SequentialLabeling};

    pub struct Iter<'a, R: RandomAccessLabeling> {
        labeling: &'a R,
        nodes_per_iter: usize,
        how_many: usize,
        i: usize,
    }

    impl<'a, R: RandomAccessLabeling> Iter<'a, R> {
        pub fn new(labeling: &'a R, how_many: usize) -> Self {
            let nodes_per_iter = labeling.num_nodes().div_ceil(how_many);
            Self {
                labeling,
                nodes_per_iter,
                how_many,
                i: 0,
            }
        }
    }

    impl<'a, R: RandomAccessLabeling> Iterator for Iter<'a, R> {
        type Item = Lender<'a, R>;

        fn next(&mut self) -> Option<Self::Item> {
            use lender::Lender;

            if self.i == self.how_many {
                return None;
            }
            let start_node = self.i * self.nodes_per_iter;
            self.i += 1;
            Some(
                self.labeling
                    .iter_from(start_node)
                    .take(self.nodes_per_iter),
            )
        }
    }

    impl<R: RandomAccessLabeling> ExactSizeIterator for Iter<'_, R> {
        fn len(&self) -> usize {
            self.how_many - self.i
        }
    }

    pub type Lender<'a, R> = lender::Take<<R as SequentialLabeling>::Lender<'a>>;
    pub type IntoIterator<'a, R> = Iter<'a, R>;
}

1	/*
2	* SPDX-FileCopyrightText: 2023 Tommaso Fontana
3	* SPDX-FileCopyrightText: 2023 Sebastiano Vigna
4	*
5	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
6	*/
7
8	//! Traits and basic implementations to support parallel completion by splitting
9	//! the [iterator](SequentialLabeling::Lender) of a labeling into multiple
10	//! iterators.
11
12	use std::rc::Rc;
13
14	use impl_tools::autoimpl;
15
16	use super::{labels::SequentialLabeling, lenders::NodeLabelsLender};
17
18	/// A trait with a single method that splits a labeling into `n` parts which are
19	/// thread safe.
20	///
21	/// Labeling implementing this trait can be analyzed in parallel by calling
22	/// [`split_iter`](SplitLabeling::split_iter) to split the labeling
23	/// [iterator](SequentialLabeling::Lender) into `n` parts.
24	///
25	/// Each part is returned as a tuple `(usize, SplitLender)` where the first
26	/// element indicates the first node ID covered by that lender.
27	///
28	/// Note that the parts are required to be [`Send`] and [`Sync`], so that they
29	/// can be safely shared among threads.
30	///
31	/// Due to some limitations of the current Rust type system, we cannot provide
32	/// blanket implementations for this trait. However, we provide ready-made
33	/// implementations for the [sequential](seq) and [random-access](ra) cases. To
34	/// use them, you must implement the trait by specifying the associated types
35	/// `Lender` and `IntoIterator`, and then just return a [`seq::Iter`] or
36	/// [`ra::Iter`] structure.
37	#[autoimpl(for<S: trait + ?Sized> &S, &mut S, Rc<S>)]
38	pub trait SplitLabeling: SequentialLabeling {
39	type SplitLender<'a>: for<'next> NodeLabelsLender<'next, Label = <Self as SequentialLabeling>::Label>
40	+ Send
41	+ Sync
42	where
43	Self: 'a;
44
45	type IntoIterator<'a>: IntoIterator<Item = Self::SplitLender<'a>, IntoIter: ExactSizeIterator>
46	where
47	Self: 'a;
48
49	fn split_iter(&self, n: usize) -> Self::IntoIterator<'_>;
50	}
51
52	/// Ready-made implementation for the sequential case.
53	///
54	/// This implementation walks through the iterator of a labeling and
55	/// clones it at regular intervals. To use it, you have to implement the
56	/// trait by specifying the associated types `Lender` and `IntoIterator`
57	/// using the [`seq::Lender`] and [`seq::IntoIterator`] types aliases,
58	/// and then return a [`seq::Iter`] structure.
59	///
60	/// # Examples
61	///
62	/// The code for [`BvGraphSeq`](crate::graphs::bvgraph::sequential::BvGraphSeq) is:
63	/// ```ignore
64	/// impl<F: SequentialDecoderFactory> SplitLabeling for BvGraphSeq<F>
65	/// where
66	/// for<'a> <F as SequentialDecoderFactory>::Decoder<'a>: Clone + Send + Sync,
67	/// {
68	/// type SplitLender<'a> = split::seq::Lender<'a, BvGraphSeq<F>> where Self: 'a;
69	/// type IntoIterator<'a> = split::seq::IntoIterator<'a, BvGraphSeq<F>> where Self: 'a;
70	///
71	/// fn split_iter(&self, how_many: usize) -> Self::IntoIterator<'_> {
72	/// split::seq::Iter::new(self.iter(), self.num_nodes(), how_many)
73	/// }
74	/// }
75	/// ```
76	pub mod seq {
77	use crate::prelude::SequentialLabeling;
78
79	pub struct Iter<L> {
80	lender: L,
81	nodes_per_iter: usize,
82	how_many: usize,
83	remaining: usize,
84	current_node: usize,
85	}
86
87	impl<L: lender::Lender> Iter<L> {
88	pub fn new(lender: L, number_of_nodes: usize, how_many: usize) -> Self {	39✔
89	let nodes_per_iter = number_of_nodes.div_ceil(how_many);	156✔
90	Self {
91	lender,
92	nodes_per_iter,
93	how_many,
94	remaining: how_many,
95	current_node: 0,
96	}
97	}
98	}
99
100	impl<L: lender::Lender + Clone> Iterator for Iter<L> {
101	type Item = lender::Take<L>;
102
103	fn next(&mut self) -> Option<Self::Item> {	244✔
104	if self.remaining == 0 {	244✔
105	return None;	39✔
106	}
107	if self.remaining != self.how_many {	205✔
108	self.lender.advance_by(self.nodes_per_iter).ok()?;	664✔
109	}
110	self.current_node += self.nodes_per_iter;	205✔
111	self.remaining -= 1;	205✔
112	Some(self.lender.clone().take(self.nodes_per_iter))	615✔
113	}
114
115	fn size_hint(&self) -> (usize, Option<usize>) {	11✔
116	(self.remaining, Some(self.remaining))	11✔
117	}
118	}
119
120	impl<L: lender::Lender + Clone> ExactSizeIterator for Iter<L> {
UNCOV 121	fn len(&self) -> usize {	×
UNCOV 122	self.remaining	×
123	}
124	}
125
126	pub type Lender<'a, S> = lender::Take<<S as SequentialLabeling>::Lender<'a>>;
127	pub type IntoIterator<'a, S> = Iter<<S as SequentialLabeling>::Lender<'a>>;
128	}
129
130	/// Ready-made implementation for the random-access case.
131	///
132	/// This implementation uses the [`iter_from`](SequentialLabeling::iter_from) at
133	/// regular intervals. To use it, you have to implement the trait by specifying
134	/// the associated types `Lender` and `IntoIterator` using the [`ra::Lender`]
135	/// and [`ra::IntoIterator`] types aliases, and then return a [`ra::Iter`]
136	/// structure.
137	///
138	/// # Examples
139	///
140	/// The code for [`BvGraph`](crate::graphs::bvgraph::random_access::BvGraph) is
141	/// ```ignore
142	/// impl<F: RandomAccessDecoderFactory> SplitLabeling for BvGraph<F>
143	/// where
144	/// for<'a> <F as RandomAccessDecoderFactory>::Decoder<'a>: Send + Sync,
145	/// {
146	/// type SplitLender<'a> = split::ra::Lender<'a, BvGraph<F>> where Self: 'a;
147	/// type IntoIterator<'a> = split::ra::IntoIterator<'a, BvGraph<F>> where Self: 'a;
148	///
149	/// fn split_iter(&self, how_many: usize) -> Self::IntoIterator<'_> {
150	/// split::ra::Iter::new(self, how_many)
151	/// }
152	/// }
153	/// ```
154	pub mod ra {
155	use crate::prelude::{RandomAccessLabeling, SequentialLabeling};
156
157	pub struct Iter<'a, R: RandomAccessLabeling> {
158	labeling: &'a R,
159	nodes_per_iter: usize,
160	how_many: usize,
161	i: usize,
162	}
163
164	impl<'a, R: RandomAccessLabeling> Iter<'a, R> {
165	pub fn new(labeling: &'a R, how_many: usize) -> Self {	16✔
166	let nodes_per_iter = labeling.num_nodes().div_ceil(how_many);	80✔
167	Self {
168	labeling,
169	nodes_per_iter,
170	how_many,
171	i: 0,
172	}
173	}
174	}
175
176	impl<'a, R: RandomAccessLabeling> Iterator for Iter<'a, R> {
177	type Item = Lender<'a, R>;
178
179	fn next(&mut self) -> Option<Self::Item> {	93✔
180	use lender::Lender;
181
182	if self.i == self.how_many {	93✔
183	return None;	13✔
184	}
185	let start_node = self.i * self.nodes_per_iter;	160✔
186	self.i += 1;	80✔
187	Some(
188	self.labeling	160✔
189	.iter_from(start_node)	240✔
190	.take(self.nodes_per_iter),	80✔
191	)
192	}
193	}
194
195	impl<R: RandomAccessLabeling> ExactSizeIterator for Iter<'_, R> {
UNCOV 196	fn len(&self) -> usize {	×
UNCOV 197	self.how_many - self.i	×
198	}
199	}
200
201	pub type Lender<'a, R> = lender::Take<<R as SequentialLabeling>::Lender<'a>>;
202	pub type IntoIterator<'a, R> = Iter<'a, R>;
203	}

vigna / webgraph-rs / 19278972970

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