24296210049

Committed 12 Apr 2026 01:49AM UTC coverage: 66.827% (-0.05%) from 66.877%

Build # 24296210049

Build Type

push

github

Committed by

vigna

Commit Message

Clippy hapy

Coverage Stats

6674 of 9987 relevant lines covered (66.83%)

47792805.58 hits per line

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

87.14

/webgraph/src/graphs/bvgraph/sequential.rs

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

use std::path::PathBuf;

use super::*;
use crate::utils::CircularBuffer;
use anyhow::Result;
use bitflags::Flags;
use dsi_bitstream::codes::ToInt;
use dsi_bitstream::traits::BE;
use dsi_bitstream::traits::BitSeek;
use lender::*;
use sux::traits::TryIntoUnaligned;

/// A sequential graph in the BV format.
///
/// The graph depends on a [`SequentialDecoderFactory`] that can be used to
/// create decoders for the graph. This makes it possible to decouple the graph from the
/// underlying storage format, and to use different storage formats for the same
/// graph. For example, one can use a memory-mapped file for the graph, or load
/// it in memory, or even generate it on the fly.
///
/// Note that the knowledge of the codes used by the graph is in the factory,
/// which provides methods to read each component of the BV format (outdegree,
/// reference offset, block count, etc.), whereas the knowledge of the
/// compression parameters (compression window and minimum interval length) is
/// in this structure.
#[derive(Debug, Clone)]
pub struct BvGraphSeq<F> {
    factory: F,
    number_of_nodes: usize,
    number_of_arcs: Option<u64>,
    compression_window: usize,
    min_interval_length: usize,
}

impl BvGraphSeq<()> {
    /// Returns a load configuration that can be customized.
    pub fn with_basename(
        basename: impl AsRef<std::path::Path>,
    ) -> LoadConfig<BE, Sequential, Dynamic, Mmap, Mmap> {
        LoadConfig {
            basename: PathBuf::from(basename.as_ref()),
            graph_load_flags: Flags::empty(),
            offsets_load_flags: Flags::empty(),
            _marker: std::marker::PhantomData,
        }
    }
}

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_at(&self, cutpoints: impl IntoIterator<Item = usize>) -> Self::IntoIterator<'_> {
        split::seq::Iter::new(self.iter(), cutpoints)
    }
}

impl<F: SequentialDecoderFactory> SequentialLabeling for BvGraphSeq<F> {
    type Label = usize;
    type Lender<'a>
        = NodeLabels<F::Decoder<'a>>
    where
        Self: 'a;

    /// Returns the number of nodes in the graph.
    #[inline(always)]
    fn num_nodes(&self) -> usize {
        self.number_of_nodes
    }

    #[inline(always)]
    fn num_arcs_hint(&self) -> Option<u64> {
        self.number_of_arcs
    }

    #[inline(always)]
    fn iter_from(&self, from: usize) -> Self::Lender<'_> {
        let mut iter = NodeLabels::new(
            self.factory.new_decoder().unwrap(),
            self.number_of_nodes,
            self.compression_window,
            self.min_interval_length,
        );

        debug_assert!(
            from <= self.number_of_nodes,
            "from ({from}) is greater than the number of nodes ({})",
            self.number_of_nodes
        );
        // advance_by returns Err only if the lender is exhausted before
        // reaching `from`, which is expected when `from == num_nodes`.
        let _ = iter.advance_by(from);

        iter
    }

    fn build_dcf(&self) -> DCF {
        let n = self.num_nodes();
        let num_arcs = self
            .num_arcs_hint()
            .expect("build_dcf requires num_arcs_hint()");
        let mut efb = sux::dict::EliasFanoBuilder::new(n + 1, num_arcs);
        efb.push(0);
        let mut cumul_deg = 0u64;
        let mut iter = OffsetDegIter::new(
            self.factory.new_decoder().unwrap(),
            n,
            self.compression_window,
            self.min_interval_length,
        );
        for _ in 0..n {
            cumul_deg += iter.next_degree().unwrap() as u64;
            efb.push(cumul_deg);
        }
        // SAFETY: the cumulative degrees are pushed in non-decreasing order.
        unsafe {
            efb.build()
                .map_high_bits(|high_bits| {
                    sux::rank_sel::SelectZeroAdaptConst::<
                        _,
                        _,
                        LOG2_ONES_PER_INVENTORY,
                        LOG2_WORDS_PER_SUBINVENTORY,
                    >::new(sux::rank_sel::SelectAdaptConst::<
                        _,
                        _,
                        LOG2_ONES_PER_INVENTORY,
                        LOG2_WORDS_PER_SUBINVENTORY,
                    >::new(high_bits))
                })
                .try_into_unaligned()
                .unwrap()
        }
    }
}

impl<F: SequentialDecoderFactory> SequentialGraph for BvGraphSeq<F> {}

/// Convenience implementation that makes it possible to iterate
/// over the graph using the [`for_`] macro
/// (see the [crate documentation]).
///
/// [`for_`]: lender::for_
/// [crate documentation]: crate
impl<'a, F: SequentialDecoderFactory> IntoLender for &'a BvGraphSeq<F> {
    type Lender = <BvGraphSeq<F> as SequentialLabeling>::Lender<'a>;

    #[inline(always)]
    fn into_lender(self) -> Self::Lender {
        self.iter()
    }
}

impl<F: SequentialDecoderFactory> BvGraphSeq<F> {
    /// Creates a new sequential graph from a codes reader builder
    /// and the number of nodes.
    pub const fn new(
        codes_reader_builder: F,
        number_of_nodes: usize,
        number_of_arcs: Option<u64>,
        compression_window: usize,
        min_interval_length: usize,
    ) -> Self {
        Self {
            factory: codes_reader_builder,
            number_of_nodes,
            number_of_arcs,
            compression_window,
            min_interval_length,
        }
    }

    #[inline(always)]
    pub fn map_factory<F1, F0>(self, map_func: F0) -> BvGraphSeq<F1>
    where
        F0: FnOnce(F) -> F1,
        F1: SequentialDecoderFactory,
    {
        BvGraphSeq {
            factory: map_func(self.factory),
            number_of_nodes: self.number_of_nodes,
            number_of_arcs: self.number_of_arcs,
            compression_window: self.compression_window,
            min_interval_length: self.min_interval_length,
        }
    }

    /// Consumes self and returns the factory.
    #[inline(always)]
    pub fn into_inner(self) -> F {
        self.factory
    }
}

impl<F: SequentialDecoderFactory> BvGraphSeq<F> {
    /// Returns a specialized iterator that iterates over the offsets and
    /// degrees of the nodes.
    ///
    /// This iterator is slightly faster than the lender returned by
    /// [`iter`] because it does not require to rebuild the successors of each
    /// node.
    ///
    /// [`iter`]: Self::iter
    #[inline(always)]
    pub fn offset_deg_iter(&self) -> OffsetDegIter<F::Decoder<'_>> {
        OffsetDegIter::new(
            self.factory.new_decoder().unwrap(),
            self.number_of_nodes,
            self.compression_window,
            self.min_interval_length,
        )
    }
}

/// A fast sequential iterator over the nodes of the graph and their successors.
/// This iterator does not require to know the offsets of each node in the graph.
#[derive(Debug, Clone)]
pub struct NodeLabels<D: Decode> {
    pub(crate) number_of_nodes: usize,
    pub(crate) compression_window: usize,
    pub(crate) min_interval_length: usize,
    pub(crate) decoder: D,
    pub(crate) backrefs: CircularBuffer<Vec<usize>>,
    pub(crate) current_node: usize,
}

impl<D: Decode + BitSeek> NodeLabels<D> {
    /// Forwards the call of `get_pos` to the inner `codes_reader`.
    /// This returns the current bits offset in the bitstream.
    #[inline(always)]
    pub fn bit_pos(&mut self) -> Result<u64, <D as BitSeek>::Error> {
        self.decoder.bit_pos()
    }
}

impl<D: Decode> NodeLabels<D> {
    /// Creates a new iterator from a codes reader
    pub fn new(
        decoder: D,
        number_of_nodes: usize,
        compression_window: usize,
        min_interval_length: usize,
    ) -> Self {
        Self {
            number_of_nodes,
            compression_window,
            min_interval_length,
            decoder,
            backrefs: CircularBuffer::new(compression_window + 1),
            current_node: 0,
        }
    }

    /// Gets the successors of the next node in the stream.
    pub fn next_successors(&mut self) -> Result<&[usize]> {
        let mut res = self.backrefs.take(self.current_node);
        self.get_successors_iter_priv(self.current_node, &mut res)?;
        let res = self.backrefs.replace(self.current_node, res);
        self.current_node += 1;
        Ok(res)
    }

    /// Inner method called by `next_successors` and the iterator `next` method
    fn get_successors_iter_priv(&mut self, node_id: usize, results: &mut Vec<usize>) -> Result<()> {
        let degree = self.decoder.read_outdegree() as usize;
        // no edges, we are done!
        if degree == 0 {
            return Ok(());
        }

        results.clear();
        // ensure that we have enough capacity in the vector for not reallocating
        results.reserve(degree);
        // read the reference offset
        let ref_delta = if self.compression_window != 0 {
            self.decoder.read_reference_offset() as usize
        } else {
            0
        };
        // if we copy nodes from a previous one
        if ref_delta != 0 {
            // compute the node id of the reference
            let reference_node_id = node_id - ref_delta;
            // retrieve the data
            let successors = &self.backrefs[reference_node_id];
            // get the info on which destinations to copy
            let number_of_blocks = self.decoder.read_block_count() as usize;
            // no blocks, we copy everything
            if number_of_blocks == 0 {
                results.extend_from_slice(successors);
            } else {
                // otherwise we copy only the blocks of even index
                // the first block could be zero
                let mut idx = self.decoder.read_block() as usize;
                results.extend_from_slice(&successors[..idx]);

                // while the other can't
                for block_id in 1..number_of_blocks {
                    let block = self.decoder.read_block() as usize;
                    let end = idx + block + 1;
                    if block_id % 2 == 0 {
                        results.extend_from_slice(&successors[idx..end]);
                    }
                    idx = end;
                }
                if number_of_blocks & 1 == 0 {
                    results.extend_from_slice(&successors[idx..]);
                }
            }
        };

        // if we still have to read nodes
        let nodes_left_to_decode = degree - results.len();
        if nodes_left_to_decode != 0 && self.min_interval_length != 0 {
            // read the number of intervals
            let number_of_intervals = self.decoder.read_interval_count() as usize;
            if number_of_intervals != 0 {
                // pre-allocate with capacity for efficiency
                let node_id_offset = self.decoder.read_interval_start().to_int();
                let mut start = (node_id as i64 + node_id_offset) as usize;
                let mut delta = self.decoder.read_interval_len() as usize;
                delta += self.min_interval_length;
                // save the first interval
                results.extend(start..(start + delta));
                start += delta;
                // decode the intervals
                for _ in 1..number_of_intervals {
                    start += 1 + self.decoder.read_interval_start() as usize;
                    delta = self.decoder.read_interval_len() as usize;
                    delta += self.min_interval_length;

                    results.extend(start..(start + delta));

                    start += delta;
                }
            }
        }

        // decode the extra nodes if needed
        let nodes_left_to_decode = degree - results.len();
        if nodes_left_to_decode != 0 {
            // pre-allocate with capacity for efficiency
            let node_id_offset = self.decoder.read_first_residual().to_int();
            let mut extra = (node_id as i64 + node_id_offset) as usize;
            results.push(extra);
            // decode the successive extra nodes
            for _ in 1..nodes_left_to_decode {
                extra += 1 + self.decoder.read_residual() as usize;
                results.push(extra);
            }
        }

        results.sort();
        Ok(())
    }
}

impl<'succ, D: Decode> NodeLabelsLender<'succ> for NodeLabels<D> {
    type Label = usize;
    type IntoIterator = crate::traits::labels::AssumeSortedIterator<
        std::iter::Copied<std::slice::Iter<'succ, Self::Label>>,
    >;
}

impl<'succ, D: Decode> Lending<'succ> for NodeLabels<D> {
    type Lend = (usize, <Self as NodeLabelsLender<'succ>>::IntoIterator);
}

impl<D: Decode> Lender for NodeLabels<D> {
    check_covariance!();

    fn next(&mut self) -> Option<Lend<'_, Self>> {
        if self.current_node >= self.number_of_nodes {
            return None;
        }
        let mut res = self.backrefs.take(self.current_node);
        res.clear();
        self.get_successors_iter_priv(self.current_node, &mut res)
            .unwrap();

        let res = self.backrefs.replace(self.current_node, res);
        let node_id = self.current_node;
        self.current_node += 1;
        Some((node_id, unsafe {
            crate::traits::labels::AssumeSortedIterator::new(res.iter().copied())
        }))
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let len = self.len();
        (len, Some(len))
    }
}

// SAFETY: BvGraph successors are always returned in sorted order.
unsafe impl<D: Decode> SortedLender for NodeLabels<D> {}

impl<D: Decode> ExactSizeLender for NodeLabels<D> {
    #[inline(always)]
    fn len(&self) -> usize {
        self.number_of_nodes - self.current_node
    }
}

1	/*
2	* SPDX-FileCopyrightText: 2023 Inria
3	* SPDX-FileCopyrightText: 2023 Sebastiano Vigna
4	*
5	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
6	*/
7
8	use std::path::PathBuf;
9
10	use super::*;
11	use crate::utils::CircularBuffer;
12	use anyhow::Result;
13	use bitflags::Flags;
14	use dsi_bitstream::codes::ToInt;
15	use dsi_bitstream::traits::BE;
16	use dsi_bitstream::traits::BitSeek;
17	use lender::*;
18	use sux::traits::TryIntoUnaligned;
19
20	/// A sequential graph in the BV format.
21	///
22	/// The graph depends on a [`SequentialDecoderFactory`] that can be used to
23	/// create decoders for the graph. This makes it possible to decouple the graph from the
24	/// underlying storage format, and to use different storage formats for the same
25	/// graph. For example, one can use a memory-mapped file for the graph, or load
26	/// it in memory, or even generate it on the fly.
27	///
28	/// Note that the knowledge of the codes used by the graph is in the factory,
29	/// which provides methods to read each component of the BV format (outdegree,
30	/// reference offset, block count, etc.), whereas the knowledge of the
31	/// compression parameters (compression window and minimum interval length) is
32	/// in this structure.
33	#[derive(Debug, Clone)]
34	pub struct BvGraphSeq<F> {
35	factory: F,
36	number_of_nodes: usize,
37	number_of_arcs: Option<u64>,
38	compression_window: usize,
39	min_interval_length: usize,
40	}
41
42	impl BvGraphSeq<()> {
43	/// Returns a load configuration that can be customized.
44	pub fn with_basename(	249,112✔
45	basename: impl AsRef<std::path::Path>,
46	) -> LoadConfig<BE, Sequential, Dynamic, Mmap, Mmap> {
47	LoadConfig {
48	basename: PathBuf::from(basename.as_ref()),	996,448✔
49	graph_load_flags: Flags::empty(),	498,224✔
50	offsets_load_flags: Flags::empty(),	249,112✔
51	_marker: std::marker::PhantomData,
52	}
53	}
54	}
55
56	impl<F: SequentialDecoderFactory> SplitLabeling for BvGraphSeq<F>
57	where
58	for<'a> <F as SequentialDecoderFactory>::Decoder<'a>: Clone + Send + Sync,
59	{
60	type SplitLender<'a>
61	= split::seq::Lender<'a, BvGraphSeq<F>>
62	where
63	Self: 'a;
64	type IntoIterator<'a>
65	= split::seq::IntoIterator<'a, BvGraphSeq<F>>
66	where
67	Self: 'a;
68
69	fn split_iter_at(&self, cutpoints: impl IntoIterator<Item = usize>) -> Self::IntoIterator<'_> {	25✔
70	split::seq::Iter::new(self.iter(), cutpoints)	100✔
71	}
72	}
73
74	impl<F: SequentialDecoderFactory> SequentialLabeling for BvGraphSeq<F> {
75	type Label = usize;
76	type Lender<'a>
77	= NodeLabels<F::Decoder<'a>>
78	where
79	Self: 'a;
80
81	/// Returns the number of nodes in the graph.
82	#[inline(always)]
83	fn num_nodes(&self) -> usize {	746,563✔
84	self.number_of_nodes	746,563✔
85	}
86
87	#[inline(always)]
88	fn num_arcs_hint(&self) -> Option<u64> {	21✔
89	self.number_of_arcs	21✔
90	}
91
92	#[inline(always)]
93	fn iter_from(&self, from: usize) -> Self::Lender<'_> {	755,654✔
94	let mut iter = NodeLabels::new(
95	self.factory.new_decoder().unwrap(),	2,266,962✔
96	self.number_of_nodes,	755,654✔
97	self.compression_window,	755,654✔
98	self.min_interval_length,	755,654✔
99	);
100
101	debug_assert!(	755,654✔
102	from <= self.number_of_nodes,	755,654✔
103	"from ({from}) is greater than the number of nodes ({})",	×
104	self.number_of_nodes	×
105	);
106	// advance_by returns Err only if the lender is exhausted before
107	// reaching `from`, which is expected when `from == num_nodes`.
108	let _ = iter.advance_by(from);	1,511,308✔
109
110	iter	755,654✔
111	}
112
113	fn build_dcf(&self) -> DCF {	3✔
114	let n = self.num_nodes();	9✔
115	let num_arcs = self	6✔
116	.num_arcs_hint()
117	.expect("build_dcf requires num_arcs_hint()");
118	let mut efb = sux::dict::EliasFanoBuilder::new(n + 1, num_arcs);	12✔
119	efb.push(0);	6✔
120	let mut cumul_deg = 0u64;	6✔
121	let mut iter = OffsetDegIter::new(
122	self.factory.new_decoder().unwrap(),	9✔
123	n,	3✔
124	self.compression_window,	3✔
125	self.min_interval_length,	3✔
126	);
127	for _ in 0..n {	325,576✔
128	cumul_deg += iter.next_degree().unwrap() as u64;	976,719✔
129	efb.push(cumul_deg);	651,146✔
130	}
131	// SAFETY: the cumulative degrees are pushed in non-decreasing order.
132	unsafe {
133	efb.build()	6✔
134	.map_high_bits(\|high_bits\| {	6✔
135	sux::rank_sel::SelectZeroAdaptConst::<	3✔
136	_,	3✔
137	_,	3✔
138	LOG2_ONES_PER_INVENTORY,	3✔
139	LOG2_WORDS_PER_SUBINVENTORY,	3✔
140	>::new(sux::rank_sel::SelectAdaptConst::<	6✔
141	_,	3✔
142	_,	3✔
143	LOG2_ONES_PER_INVENTORY,	3✔
144	LOG2_WORDS_PER_SUBINVENTORY,	3✔
145	>::new(high_bits))	6✔
146	})
147	.try_into_unaligned()
148	.unwrap()
149	}
150	}
151	}
152
153	impl<F: SequentialDecoderFactory> SequentialGraph for BvGraphSeq<F> {}
154
155	/// Convenience implementation that makes it possible to iterate
156	/// over the graph using the [`for_`] macro
157	/// (see the [crate documentation]).
158	///
159	/// [`for_`]: lender::for_
160	/// [crate documentation]: crate
161	impl<'a, F: SequentialDecoderFactory> IntoLender for &'a BvGraphSeq<F> {
162	type Lender = <BvGraphSeq<F> as SequentialLabeling>::Lender<'a>;
163
164	#[inline(always)]
165	fn into_lender(self) -> Self::Lender {	×
166	self.iter()	×
167	}
168	}
169
170	impl<F: SequentialDecoderFactory> BvGraphSeq<F> {
171	/// Creates a new sequential graph from a codes reader builder
172	/// and the number of nodes.
173	pub const fn new(	755,542✔
174	codes_reader_builder: F,
175	number_of_nodes: usize,
176	number_of_arcs: Option<u64>,
177	compression_window: usize,
178	min_interval_length: usize,
179	) -> Self {
180	Self {
181	factory: codes_reader_builder,
182	number_of_nodes,
183	number_of_arcs,
184	compression_window,
185	min_interval_length,
186	}
187	}
188
189	#[inline(always)]
190	pub fn map_factory<F1, F0>(self, map_func: F0) -> BvGraphSeq<F1>	×
191	where
192	F0: FnOnce(F) -> F1,
193	F1: SequentialDecoderFactory,
194	{
195	BvGraphSeq {
196	factory: map_func(self.factory),	×
197	number_of_nodes: self.number_of_nodes,	×
198	number_of_arcs: self.number_of_arcs,	×
199	compression_window: self.compression_window,	×
200	min_interval_length: self.min_interval_length,	×
201	}
202	}
203
204	/// Consumes self and returns the factory.
205	#[inline(always)]
206	pub fn into_inner(self) -> F {	×
207	self.factory	×
208	}
209	}
210
211	impl<F: SequentialDecoderFactory> BvGraphSeq<F> {
212	/// Returns a specialized iterator that iterates over the offsets and
213	/// degrees of the nodes.
214	///
215	/// This iterator is slightly faster than the lender returned by
216	/// [`iter`] because it does not require to rebuild the successors of each
217	/// node.
218	///
219	/// [`iter`]: Self::iter
220	#[inline(always)]
221	pub fn offset_deg_iter(&self) -> OffsetDegIter<F::Decoder<'_>> {	257,536✔
222	OffsetDegIter::new(
223	self.factory.new_decoder().unwrap(),	772,608✔
224	self.number_of_nodes,	257,536✔
225	self.compression_window,	257,536✔
226	self.min_interval_length,	257,536✔
227	)
228	}
229	}
230
231	/// A fast sequential iterator over the nodes of the graph and their successors.
232	/// This iterator does not require to know the offsets of each node in the graph.
233	#[derive(Debug, Clone)]
234	pub struct NodeLabels<D: Decode> {
235	pub(crate) number_of_nodes: usize,
236	pub(crate) compression_window: usize,
237	pub(crate) min_interval_length: usize,
238	pub(crate) decoder: D,
239	pub(crate) backrefs: CircularBuffer<Vec<usize>>,
240	pub(crate) current_node: usize,
241	}
242
243	impl<D: Decode + BitSeek> NodeLabels<D> {
244	/// Forwards the call of `get_pos` to the inner `codes_reader`.
245	/// This returns the current bits offset in the bitstream.
246	#[inline(always)]
247	pub fn bit_pos(&mut self) -> Result<u64, <D as BitSeek>::Error> {	1,469,850✔
248	self.decoder.bit_pos()	2,939,700✔
249	}
250	}
251
252	impl<D: Decode> NodeLabels<D> {
253	/// Creates a new iterator from a codes reader
254	pub fn new(	1,253,388✔
255	decoder: D,
256	number_of_nodes: usize,
257	compression_window: usize,
258	min_interval_length: usize,
259	) -> Self {
260	Self {
261	number_of_nodes,
262	compression_window,
263	min_interval_length,
264	decoder,
265	backrefs: CircularBuffer::new(compression_window + 1),	1,253,388✔
266	current_node: 0,
267	}
268	}
269
270	/// Gets the successors of the next node in the stream.
271	pub fn next_successors(&mut self) -> Result<&[usize]> {	×
272	let mut res = self.backrefs.take(self.current_node);	×
273	self.get_successors_iter_priv(self.current_node, &mut res)?;	×
274	let res = self.backrefs.replace(self.current_node, res);	×
275	self.current_node += 1;	×
276	Ok(res)	×
277	}
278
279	/// Inner method called by `next_successors` and the iterator `next` method
280	fn get_successors_iter_priv(&mut self, node_id: usize, results: &mut Vec<usize>) -> Result<()> {	288,942,433✔
281	let degree = self.decoder.read_outdegree() as usize;	577,884,866✔
282	// no edges, we are done!
283	if degree == 0 {	288,942,433✔
284	return Ok(());	35,757,138✔
285	}
286
287	results.clear();	506,370,590✔
288	// ensure that we have enough capacity in the vector for not reallocating
289	results.reserve(degree);	759,555,885✔
290	// read the reference offset
291	let ref_delta = if self.compression_window != 0 {	506,370,590✔
292	self.decoder.read_reference_offset() as usize	220,595,854✔
293	} else {
294	0	32,589,441✔
295	};
296	// if we copy nodes from a previous one
297	if ref_delta != 0 {	253,185,295✔
298	// compute the node id of the reference
299	let reference_node_id = node_id - ref_delta;	194,870,926✔
300	// retrieve the data
301	let successors = &self.backrefs[reference_node_id];	194,870,926✔
302	// get the info on which destinations to copy
303	let number_of_blocks = self.decoder.read_block_count() as usize;	194,870,926✔
304	// no blocks, we copy everything
305	if number_of_blocks == 0 {	130,801,401✔
306	results.extend_from_slice(successors);	66,731,876✔
307	} else {
308	// otherwise we copy only the blocks of even index
309	// the first block could be zero
310	let mut idx = self.decoder.read_block() as usize;	128,139,050✔
311	results.extend_from_slice(&successors[..idx]);	192,208,575✔
312
313	// while the other can't
314	for block_id in 1..number_of_blocks {	167,439,303✔
315	let block = self.decoder.read_block() as usize;	206,739,556✔
316	let end = idx + block + 1;	206,739,556✔
317	if block_id % 2 == 0 {	136,193,016✔
318	results.extend_from_slice(&successors[idx..end]);	131,292,952✔
319	}
320	idx = end;	103,369,778✔
321	}
322	if number_of_blocks & 1 == 0 {	101,792,827✔
323	results.extend_from_slice(&successors[idx..]);	113,169,906✔
324	}
325	}
326	};
327
328	// if we still have to read nodes
329	let nodes_left_to_decode = degree - results.len();	759,555,885✔
330	if nodes_left_to_decode != 0 && self.min_interval_length != 0 {	475,429,370✔
331	// read the number of intervals
332	let number_of_intervals = self.decoder.read_interval_count() as usize;	358,940,956✔
333	if number_of_intervals != 0 {	179,470,478✔
334	// pre-allocate with capacity for efficiency
335	let node_id_offset = self.decoder.read_interval_start().to_int();	177,185,500✔
336	let mut start = (node_id as i64 + node_id_offset) as usize;	88,592,750✔
337	let mut delta = self.decoder.read_interval_len() as usize;	88,592,750✔
338	delta += self.min_interval_length;	44,296,375✔
339	// save the first interval
340	results.extend(start..(start + delta));	177,185,500✔
341	start += delta;	44,296,375✔
342	// decode the intervals
343	for _ in 1..number_of_intervals {	70,726,457✔
344	start += 1 + self.decoder.read_interval_start() as usize;	52,860,164✔
345	delta = self.decoder.read_interval_len() as usize;	52,860,164✔
346	delta += self.min_interval_length;	52,860,164✔
347
348	results.extend(start..(start + delta));	105,720,328✔
349
350	start += delta;	26,430,082✔
351	}
352	}
353	}
354
355	// decode the extra nodes if needed
356	let nodes_left_to_decode = degree - results.len();	759,555,885✔
357	if nodes_left_to_decode != 0 {	253,185,295✔
358	// pre-allocate with capacity for efficiency
359	let node_id_offset = self.decoder.read_first_residual().to_int();	879,725,300✔
360	let mut extra = (node_id as i64 + node_id_offset) as usize;	439,862,650✔
361	results.push(extra);	659,793,975✔
362	// decode the successive extra nodes
363	for _ in 1..nodes_left_to_decode {	1,456,955,504✔
364	extra += 1 + self.decoder.read_residual() as usize;	2,147,483,647✔
365	results.push(extra);	2,147,483,647✔
366	}
367	}
368
369	results.sort();	253,185,295✔
370	Ok(())	253,185,295✔
371	}
372	}
373
374	impl<'succ, D: Decode> NodeLabelsLender<'succ> for NodeLabels<D> {
375	type Label = usize;
376	type IntoIterator = crate::traits::labels::AssumeSortedIterator<
377	std::iter::Copied<std::slice::Iter<'succ, Self::Label>>,
378	>;
379	}
380
381	impl<'succ, D: Decode> Lending<'succ> for NodeLabels<D> {
382	type Lend = (usize, <Self as NodeLabelsLender<'succ>>::IntoIterator);
383	}
384
385	impl<D: Decode> Lender for NodeLabels<D> {
386	check_covariance!();
387
388	fn next(&mut self) -> Option<Lend<'_, Self>> {	288,942,676✔
389	if self.current_node >= self.number_of_nodes {	288,942,676✔
390	return None;	243✔
391	}
392	let mut res = self.backrefs.take(self.current_node);	1,155,769,732✔
393	res.clear();	577,884,866✔
394	self.get_successors_iter_priv(self.current_node, &mut res)	1,155,769,732✔
395	.unwrap();
396
397	let res = self.backrefs.replace(self.current_node, res);	1,444,712,165✔
398	let node_id = self.current_node;	577,884,866✔
399	self.current_node += 1;	288,942,433✔
400	Some((node_id, unsafe {	577,884,866✔
401	crate::traits::labels::AssumeSortedIterator::new(res.iter().copied())	577,884,866✔
402	}))
403	}
404
405	fn size_hint(&self) -> (usize, Option<usize>) {	3,581,241✔
406	let len = self.len();	10,743,723✔
407	(len, Some(len))	3,581,241✔
408	}
409	}
410
411	// SAFETY: BvGraph successors are always returned in sorted order.
412	unsafe impl<D: Decode> SortedLender for NodeLabels<D> {}
413
414	impl<D: Decode> ExactSizeLender for NodeLabels<D> {
415	#[inline(always)]
416	fn len(&self) -> usize {	325,616✔
417	self.number_of_nodes - self.current_node	325,616✔
418	}
419	}

vigna / webgraph-rs / 24296210049

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