18008720487

Committed 25 Sep 2025 01:16PM UTC coverage: 49.589% (-0.4%) from 49.949%

Build # 18008720487

Build Type

push

github

Committed by

vigna

Commit Message

Fixed fuzzing code for new epserde

Run Details

0 of 2 new or added lines in 1 file covered. (0.0%)

650 existing lines in 25 files now uncovered.

3862 of 7788 relevant lines covered (49.59%)

25127316.85 hits per line

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

76.58

/webgraph/src/graphs/bvgraph/random_access.rs

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

#![allow(clippy::type_complexity)]

use crate::prelude::*;
use bitflags::Flags;
use dsi_bitstream::codes::ToInt;
use dsi_bitstream::dispatch::factory::CodesReaderFactoryHelper;
use dsi_bitstream::traits::{Endianness, BE};
use epserde::deser::Owned;
use lender::IntoLender;
use std::path::PathBuf;

use self::sequential::Iter;

#[derive(Debug, Clone)]
pub struct BvGraph<F> {
    factory: F,
    number_of_nodes: usize,
    number_of_arcs: u64,
    compression_window: usize,
    min_interval_length: usize,
}

impl BvGraph<()> {
    /// Returns a load configuration that can be customized.
    pub fn with_basename(
        basename: impl AsRef<std::path::Path>,
    ) -> LoadConfig<BE, Random, 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<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets>
    BvGraph<DynCodesDecoderFactory<E, F, OFF>>
where
    for<'a> &'a OFF::DeserType<'a>: IntoIterator<Item = usize>,
{
    /// Remaps the offsets in a slice of `usize`.
    ///
    /// This method is mainly useful for benchmarking and testing purposes, as
    /// representing the offsets as a slice increasing significantly the
    /// memory footprint. It just replaces current decoder factory with
    /// the result of [`DynCodesDecoderFactory::offsets_to_slice`].
    pub fn offsets_to_slice(self) -> BvGraph<DynCodesDecoderFactory<E, F, Owned<Box<[usize]>>>> {
        BvGraph {
            factory: self.factory.offsets_to_slice(),
            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,
        }
    }
}

impl<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets>
    BvGraph<ConstCodesDecoderFactory<E, F, OFF>>
{
    /// Remaps the offsets in a slice of `usize`.
    ///
    /// This method is mainly useful for benchmarking and testing purposes, as
    /// representing the offsets as a slice increasing significantly the
    /// memory footprint. It just replaces current decoder factory with
    /// the result of [`ConstCodesDecoderFactory::offsets_to_slice`].
    pub fn offsets_to_slice(self) -> BvGraph<ConstCodesDecoderFactory<E, F, Owned<Box<[usize]>>>> {
        BvGraph {
            factory: self.factory.offsets_to_slice(),
            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,
        }
    }
}

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)
    }
}

impl<F> BvGraph<F>
where
    F: RandomAccessDecoderFactory,
{
    /// Creates a new BvGraph from the given parameters.
    ///
    /// # Arguments
    /// - `reader_factory`: backend that can create objects that allows
    ///   us to read the bitstream of the graph to decode the edges.
    /// - `offsets`: the bit offset at which we will have to start for decoding
    ///   the edges of each node. (This is needed for the random accesses,
    ///   [`BvGraphSeq`] does not need them)
    /// - `min_interval_length`: the minimum size of the intervals we are going
    ///   to decode.
    /// - `compression_window`: the maximum distance between two nodes that
    ///   reference each other.
    /// - `number_of_nodes`: the number of nodes in the graph.
    /// - `number_of_arcs`: the number of arcs in the graph.
    ///
    pub fn new(
        factory: F,
        number_of_nodes: usize,
        number_of_arcs: u64,
        compression_window: usize,
        min_interval_length: usize,
    ) -> Self {
        Self {
            factory,
            number_of_nodes,
            number_of_arcs,
            compression_window,
            min_interval_length,
        }
    }

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

impl<F> SequentialLabeling for BvGraph<F>
where
    F: RandomAccessDecoderFactory,
{
    type Label = usize;
    type Lender<'b>
        = Iter<F::Decoder<'b>>
    where
        Self: 'b,
        F: 'b;

    #[inline(always)]
    fn num_nodes(&self) -> usize {
        self.number_of_nodes
    }

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

    /// Returns a fast sequential iterator over the nodes of the graph and their successors.
    fn iter_from(&self, start_node: usize) -> Self::Lender<'_> {
        let codes_reader = self.factory.new_decoder(start_node).unwrap();
        // we have to pre-fill the buffer
        let mut backrefs = CircularBuffer::new(self.compression_window + 1);

        for node_id in start_node.saturating_sub(self.compression_window)..start_node {
            backrefs.replace(node_id, self.successors(node_id).collect());
        }

        Iter {
            decoder: codes_reader,
            backrefs,
            compression_window: self.compression_window,
            min_interval_length: self.min_interval_length,
            number_of_nodes: self.number_of_nodes,
            current_node: start_node,
        }
    }
}

impl<F> SequentialGraph for BvGraph<F> where F: RandomAccessDecoderFactory {}

impl<F> RandomAccessLabeling for BvGraph<F>
where
    F: RandomAccessDecoderFactory,
{
    type Labels<'a>
        = Succ<F::Decoder<'a>>
    where
        Self: 'a,
        F: 'a;

    fn num_arcs(&self) -> u64 {
        self.number_of_arcs
    }

    /// Returns the outdegree of a node.
    fn outdegree(&self, node_id: usize) -> usize {
        let mut codes_reader = self
            .factory
            .new_decoder(node_id)
            .expect("Cannot create reader");
        codes_reader.read_outdegree() as usize
    }

    #[inline(always)]
    /// Returns a random access iterator over the successors of a node.
    fn labels(&self, node_id: usize) -> Succ<F::Decoder<'_>> {
        let codes_reader = self
            .factory
            .new_decoder(node_id)
            .expect("Cannot create reader");

        let mut result = Succ::new(codes_reader);
        let degree = result.reader.read_outdegree() as usize;
        // no edges, we are done!
        if degree == 0 {
            return result;
        }
        result.size = degree;
        let mut nodes_left_to_decode = degree;
        // read the reference offset
        let ref_delta = if self.compression_window != 0 {
            result.reader.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 neighbors = self.successors(reference_node_id);
            debug_assert!(neighbors.len() != 0);
            // get the info on which destinations to copy
            let number_of_blocks = result.reader.read_block_count() as usize;
            // add +1 if the number of blocks is even, so we have capacity for
            // the block that will be added in the masked iterator
            let alloc_len = 1 + number_of_blocks - (number_of_blocks & 1);
            let mut blocks = Vec::with_capacity(alloc_len);
            if number_of_blocks != 0 {
                // the first block could be zero
                blocks.push(result.reader.read_block() as usize);
                // while the other can't
                for _ in 1..number_of_blocks {
                    blocks.push(result.reader.read_block() as usize + 1);
                }
            }
            // create the masked iterator
            let res = MaskedIterator::new(neighbors, blocks);
            nodes_left_to_decode -= res.len();

            result.copied_nodes_iter = Some(res);
        };

        // if we still have to read nodes
        if nodes_left_to_decode != 0 && self.min_interval_length != 0 {
            // read the number of intervals
            let number_of_intervals = result.reader.read_interval_count() as usize;
            if number_of_intervals != 0 {
                // pre-allocate with capacity for efficiency
                result.intervals = Vec::with_capacity(number_of_intervals + 1);
                let node_id_offset = (result.reader.read_interval_start()).to_int();

                debug_assert!((node_id as i64 + node_id_offset) >= 0);
                let mut start = (node_id as i64 + node_id_offset) as usize;
                let mut delta = result.reader.read_interval_len() as usize;
                delta += self.min_interval_length;
                // save the first interval
                result.intervals.push((start, delta));
                start += delta;
                nodes_left_to_decode -= delta;
                // decode the intervals
                for _ in 1..number_of_intervals {
                    start += 1 + result.reader.read_interval_start() as usize;
                    delta = result.reader.read_interval_len() as usize;
                    delta += self.min_interval_length;

                    result.intervals.push((start, delta));
                    start += delta;
                    nodes_left_to_decode -= delta;
                }
                // fake final interval to avoid checks in the implementation of
                // `next`
                result.intervals.push((usize::MAX - 1, 1));
            }
        }

        // decode just the first extra, if present (the others will be decoded on demand)
        if nodes_left_to_decode != 0 {
            let node_id_offset = result.reader.read_first_residual().to_int();
            result.next_residual_node = (node_id as i64 + node_id_offset) as usize;
            result.residuals_to_go = nodes_left_to_decode - 1;
        }

        // setup the first interval node so we can decode without branches
        if !result.intervals.is_empty() {
            let (start, len) = &mut result.intervals[0];
            *len -= 1;
            result.next_interval_node = *start;
            *start += 1;
            result.intervals_idx += (*len == 0) as usize;
        };

        // cache the first copied node so we don't have to check if the iter
        // ended at every call of `next`
        result.next_copied_node = result
            .copied_nodes_iter
            .as_mut()
            .and_then(|iter| iter.next())
            .unwrap_or(usize::MAX);

        result
    }
}

impl<F: SequentialDecoderFactory> BvGraph<F>
where
    for<'a> F::Decoder<'a>: Decode,
{
    #[inline(always)]
    /// Creates an iterator specialized in the degrees of the nodes.
    /// This is slightly faster because it can avoid decoding some of the nodes
    /// and completely skip the merging step.
    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,
        )
    }
}

impl<F: RandomAccessDecoderFactory> BvGraph<F>
where
    for<'a> F::Decoder<'a>: Decode,
{
    #[inline(always)]
    /// Creates an iterator specialized in the degrees of the nodes starting
    /// from a given node.
    pub fn offset_deg_iter_from(&self, node: usize) -> OffsetDegIter<F::Decoder<'_>> {
        let mut backrefs = vec![0; self.compression_window];
        for node_id in node.saturating_sub(self.compression_window)..node {
            backrefs[node_id % self.compression_window] = self.outdegree(node_id);
        }
        OffsetDegIter::new_from(
            self.factory.new_decoder(node).unwrap(),
            self.number_of_nodes,
            self.compression_window,
            self.min_interval_length,
            node,
            backrefs,
        )
    }
}
impl<F> RandomAccessGraph for BvGraph<F> where F: RandomAccessDecoderFactory {}

/// The iterator returned from [`BvGraph`] that returns the successors of a
/// node in sorted order.
#[derive(Debug, Clone)]
pub struct Succ<D: Decode> {
    reader: D,
    /// The number of values left
    size: usize,
    /// Iterator over the destinations that we are going to copy
    /// from another node
    copied_nodes_iter: Option<MaskedIterator<Succ<D>>>,

    /// Intervals of extra nodes
    intervals: Vec<(usize, usize)>,
    /// The index of interval to return
    intervals_idx: usize,
    /// Remaining residual nodes
    residuals_to_go: usize,
    /// The next residual node
    next_residual_node: usize,
    /// The next residual node
    next_copied_node: usize,
    /// The next interval node
    next_interval_node: usize,
}

impl<D: Decode> ExactSizeIterator for Succ<D> {
    #[inline(always)]
    fn len(&self) -> usize {
        self.size
    }
}

unsafe impl<D: Decode> SortedIterator for Succ<D> {}

impl<D: Decode> Succ<D> {
    /// Creates an empty iterator
    fn new(reader: D) -> Self {
        Self {
            reader,
            size: 0,
            copied_nodes_iter: None,
            intervals: vec![],
            intervals_idx: 0,
            residuals_to_go: 0,
            next_residual_node: usize::MAX,
            next_copied_node: usize::MAX,
            next_interval_node: usize::MAX,
        }
    }
}

impl<D: Decode> Iterator for Succ<D> {
    type Item = usize;

    fn next(&mut self) -> Option<Self::Item> {
        // check if we should stop iterating
        if self.size == 0 {
            return None;
        }

        self.size -= 1;
        debug_assert!(
            self.next_copied_node != usize::MAX
                || self.next_residual_node != usize::MAX
                || self.next_interval_node != usize::MAX,
            "At least one of the nodes must present, this should be a problem with the degree.",
        );

        // find the smallest of the values
        let min = self.next_residual_node.min(self.next_interval_node);

        // depending on from where the node was, forward it
        if min >= self.next_copied_node {
            let res = self.next_copied_node;
            self.next_copied_node = self
                .copied_nodes_iter
                .as_mut()
                .and_then(|iter| iter.next())
                .unwrap_or(usize::MAX);
            return Some(res);
        } else if min == self.next_residual_node {
            if self.residuals_to_go == 0 {
                self.next_residual_node = usize::MAX;
            } else {
                self.residuals_to_go -= 1;
                // NOTE: here we cannot propagate the error
                self.next_residual_node += 1 + self.reader.read_residual() as usize;
            }
        } else {
            let (start, len) = &mut self.intervals[self.intervals_idx];
            debug_assert_ne!(
                *len, 0,
                "there should never be an interval with length zero here"
            );
            // if the interval has other values, just reduce the interval
            *len -= 1;
            self.next_interval_node = *start;
            *start += 1;
            self.intervals_idx += (*len == 0) as usize;
        }

        Some(min)
    }

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

impl<'a, F: RandomAccessDecoderFactory> IntoLender for &'a BvGraph<F> {
    type Lender = <BvGraph<F> as SequentialLabeling>::Lender<'a>;

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

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	#![allow(clippy::type_complexity)]
9
10	use crate::prelude::*;
11	use bitflags::Flags;
12	use dsi_bitstream::codes::ToInt;
13	use dsi_bitstream::dispatch::factory::CodesReaderFactoryHelper;
14	use dsi_bitstream::traits::{Endianness, BE};
15	use epserde::deser::Owned;
16	use lender::IntoLender;
17	use std::path::PathBuf;
18
19	use self::sequential::Iter;
20
21	#[derive(Debug, Clone)]
22	pub struct BvGraph<F> {
23	factory: F,
24	number_of_nodes: usize,
25	number_of_arcs: u64,
26	compression_window: usize,
27	min_interval_length: usize,
28	}
29
30	impl BvGraph<()> {
31	/// Returns a load configuration that can be customized.
32	pub fn with_basename(	38✔
33	basename: impl AsRef<std::path::Path>,
34	) -> LoadConfig<BE, Random, Dynamic, Mmap, Mmap> {
35	LoadConfig {
36	basename: PathBuf::from(basename.as_ref()),	152✔
37	graph_load_flags: Flags::empty(),	76✔
38	offsets_load_flags: Flags::empty(),	38✔
39	_marker: std::marker::PhantomData,
40	}
41	}
42	}
43
44	impl<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets>
45	BvGraph<DynCodesDecoderFactory<E, F, OFF>>
46	where
47	for<'a> &'a OFF::DeserType<'a>: IntoIterator<Item = usize>,
48	{
49	/// Remaps the offsets in a slice of `usize`.
50	///
51	/// This method is mainly useful for benchmarking and testing purposes, as
52	/// representing the offsets as a slice increasing significantly the
53	/// memory footprint. It just replaces current decoder factory with
54	/// the result of [`DynCodesDecoderFactory::offsets_to_slice`].
UNCOV 55	pub fn offsets_to_slice(self) -> BvGraph<DynCodesDecoderFactory<E, F, Owned<Box<[usize]>>>> {	×
56	BvGraph {
UNCOV 57	factory: self.factory.offsets_to_slice(),	×
UNCOV 58	number_of_nodes: self.number_of_nodes,	×
UNCOV 59	number_of_arcs: self.number_of_arcs,	×
UNCOV 60	compression_window: self.compression_window,	×
UNCOV 61	min_interval_length: self.min_interval_length,	×
62	}
63	}
64	}
65
66	impl<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets>
67	BvGraph<ConstCodesDecoderFactory<E, F, OFF>>
68	{
69	/// Remaps the offsets in a slice of `usize`.
70	///
71	/// This method is mainly useful for benchmarking and testing purposes, as
72	/// representing the offsets as a slice increasing significantly the
73	/// memory footprint. It just replaces current decoder factory with
74	/// the result of [`ConstCodesDecoderFactory::offsets_to_slice`].
UNCOV 75	pub fn offsets_to_slice(self) -> BvGraph<ConstCodesDecoderFactory<E, F, Owned<Box<[usize]>>>> {	×
76	BvGraph {
UNCOV 77	factory: self.factory.offsets_to_slice(),	×
UNCOV 78	number_of_nodes: self.number_of_nodes,	×
UNCOV 79	number_of_arcs: self.number_of_arcs,	×
UNCOV 80	compression_window: self.compression_window,	×
UNCOV 81	min_interval_length: self.min_interval_length,	×
82	}
83	}
84	}
85
86	impl<F: RandomAccessDecoderFactory> SplitLabeling for BvGraph<F>
87	where
88	for<'a> <F as RandomAccessDecoderFactory>::Decoder<'a>: Send + Sync,
89	{
90	type SplitLender<'a>
91	= split::ra::Lender<'a, BvGraph<F>>
92	where
93	Self: 'a;
94	type IntoIterator<'a>
95	= split::ra::IntoIterator<'a, BvGraph<F>>
96	where
97	Self: 'a;
98
99	fn split_iter(&self, how_many: usize) -> Self::IntoIterator<'_> {	12✔
100	split::ra::Iter::new(self, how_many)	36✔
101	}
102	}
103
104	impl<F> BvGraph<F>
105	where
106	F: RandomAccessDecoderFactory,
107	{
108	/// Creates a new BvGraph from the given parameters.
109	///
110	/// # Arguments
111	/// - `reader_factory`: backend that can create objects that allows
112	/// us to read the bitstream of the graph to decode the edges.
113	/// - `offsets`: the bit offset at which we will have to start for decoding
114	/// the edges of each node. (This is needed for the random accesses,
115	/// [`BvGraphSeq`] does not need them)
116	/// - `min_interval_length`: the minimum size of the intervals we are going
117	/// to decode.
118	/// - `compression_window`: the maximum distance between two nodes that
119	/// reference each other.
120	/// - `number_of_nodes`: the number of nodes in the graph.
121	/// - `number_of_arcs`: the number of arcs in the graph.
122	///
123	pub fn new(	6,996✔
124	factory: F,
125	number_of_nodes: usize,
126	number_of_arcs: u64,
127	compression_window: usize,
128	min_interval_length: usize,
129	) -> Self {
130	Self {
131	factory,
132	number_of_nodes,
133	number_of_arcs,
134	compression_window,
135	min_interval_length,
136	}
137	}
138
139	#[inline(always)]
140	/// Consume self and return the factory
UNCOV 141	pub fn into_inner(self) -> F {	×
UNCOV 142	self.factory	×
143	}
144	}
145
146	impl<F> SequentialLabeling for BvGraph<F>
147	where
148	F: RandomAccessDecoderFactory,
149	{
150	type Label = usize;
151	type Lender<'b>
152	= Iter<F::Decoder<'b>>
153	where
154	Self: 'b,
155	F: 'b;
156
157	#[inline(always)]
158	fn num_nodes(&self) -> usize {	332,953✔
159	self.number_of_nodes	332,953✔
160	}
161
162	#[inline(always)]
UNCOV 163	fn num_arcs_hint(&self) -> Option<u64> {	×
UNCOV 164	Some(self.number_of_arcs)	×
165	}
166
167	/// Returns a fast sequential iterator over the nodes of the graph and their successors.
168	fn iter_from(&self, start_node: usize) -> Self::Lender<'_> {	14,045✔
169	let codes_reader = self.factory.new_decoder(start_node).unwrap();	70,225✔
170	// we have to pre-fill the buffer
171	let mut backrefs = CircularBuffer::new(self.compression_window + 1);	42,135✔
172
173	for node_id in start_node.saturating_sub(self.compression_window)..start_node {	153,978✔
UNCOV 174	backrefs.replace(node_id, self.successors(node_id).collect());	×
175	}
176
177	Iter {
178	decoder: codes_reader,
179	backrefs,
180	compression_window: self.compression_window,	28,090✔
181	min_interval_length: self.min_interval_length,	28,090✔
182	number_of_nodes: self.number_of_nodes,	14,045✔
183	current_node: start_node,
184	}
185	}
186	}
187
188	impl<F> SequentialGraph for BvGraph<F> where F: RandomAccessDecoderFactory {}
189
190	impl<F> RandomAccessLabeling for BvGraph<F>
191	where
192	F: RandomAccessDecoderFactory,
193	{
194	type Labels<'a>
195	= Succ<F::Decoder<'a>>
196	where
197	Self: 'a,
198	F: 'a;
199
200	fn num_arcs(&self) -> u64 {	8,020✔
201	self.number_of_arcs	8,020✔
202	}
203
204	/// Returns the outdegree of a node.
205	fn outdegree(&self, node_id: usize) -> usize {	72,481,483✔
206	let mut codes_reader = self	144,962,966✔
207	.factory	72,481,483✔
208	.new_decoder(node_id)	144,962,966✔
209	.expect("Cannot create reader");
210	codes_reader.read_outdegree() as usize	72,481,483✔
211	}
212
213	#[inline(always)]
214	/// Returns a random access iterator over the successors of a node.
215	fn labels(&self, node_id: usize) -> Succ<F::Decoder<'_>> {	227,050,269✔
216	let codes_reader = self	454,100,538✔
217	.factory	227,050,269✔
218	.new_decoder(node_id)	454,100,538✔
219	.expect("Cannot create reader");
220
221	let mut result = Succ::new(codes_reader);	681,150,807✔
222	let degree = result.reader.read_outdegree() as usize;	454,100,538✔
223	// no edges, we are done!
224	if degree == 0 {	227,050,269✔
225	return result;	7,448,117✔
226	}
UNCOV 227	result.size = degree;	×
UNCOV 228	let mut nodes_left_to_decode = degree;	×
229	// read the reference offset
UNCOV 230	let ref_delta = if self.compression_window != 0 {	×
231	result.reader.read_reference_offset() as usize	219,601,856✔
232	} else {
233	0	296✔
234	};
235	// if we copy nodes from a previous one
UNCOV 236	if ref_delta != 0 {	×
237	// compute the node id of the reference
238	let reference_node_id = node_id - ref_delta;	291,681,752✔
239	// retrieve the data
240	let neighbors = self.successors(reference_node_id);	583,363,504✔
241	debug_assert!(neighbors.len() != 0);	291,681,752✔
242	// get the info on which destinations to copy
243	let number_of_blocks = result.reader.read_block_count() as usize;	291,681,752✔
244	// add +1 if the number of blocks is even, so we have capacity for
245	// the block that will be added in the masked iterator
246	let alloc_len = 1 + number_of_blocks - (number_of_blocks & 1);	291,681,752✔
247	let mut blocks = Vec::with_capacity(alloc_len);	437,522,628✔
248	if number_of_blocks != 0 {	145,840,876✔
249	// the first block could be zero
250	blocks.push(result.reader.read_block() as usize);	291,138,057✔
251	// while the other can't
252	for _ in 1..number_of_blocks {	249,845,207✔
253	blocks.push(result.reader.read_block() as usize + 1);	152,799,188✔
254	}
255	}
256	// create the masked iterator
257	let res = MaskedIterator::new(neighbors, blocks);	583,363,504✔
258	nodes_left_to_decode -= res.len();	145,840,876✔
259
260	result.copied_nodes_iter = Some(res);	291,681,752✔
261	};
262
263	// if we still have to read nodes
264	if nodes_left_to_decode != 0 && self.min_interval_length != 0 {	390,694,391✔
265	// read the number of intervals
266	let number_of_intervals = result.reader.read_interval_count() as usize;	342,183,534✔
267	if number_of_intervals != 0 {	171,091,767✔
268	// pre-allocate with capacity for efficiency
269	result.intervals = Vec::with_capacity(number_of_intervals + 1);	147,378,774✔
270	let node_id_offset = (result.reader.read_interval_start()).to_int();	196,505,032✔
271
272	debug_assert!((node_id as i64 + node_id_offset) >= 0);	98,252,516✔
273	let mut start = (node_id as i64 + node_id_offset) as usize;	98,252,516✔
274	let mut delta = result.reader.read_interval_len() as usize;	98,252,516✔
275	delta += self.min_interval_length;	49,126,258✔
276	// save the first interval
277	result.intervals.push((start, delta));	147,378,774✔
278	start += delta;	49,126,258✔
279	nodes_left_to_decode -= delta;	49,126,258✔
280	// decode the intervals
281	for _ in 1..number_of_intervals {	96,704,889✔
282	start += 1 + result.reader.read_interval_start() as usize;	47,578,631✔
283	delta = result.reader.read_interval_len() as usize;	47,578,631✔
284	delta += self.min_interval_length;	47,578,631✔
285
286	result.intervals.push((start, delta));	47,578,631✔
287	start += delta;	47,578,631✔
288	nodes_left_to_decode -= delta;	47,578,631✔
289	}
290	// fake final interval to avoid checks in the implementation of
291	// `next`
292	result.intervals.push((usize::MAX - 1, 1));	147,378,774✔
293	}
294	}
295
296	// decode just the first extra, if present (the others will be decoded on demand)
297	if nodes_left_to_decode != 0 {	387,393,034✔
298	let node_id_offset = result.reader.read_first_residual().to_int();	838,954,410✔
299	result.next_residual_node = (node_id as i64 + node_id_offset) as usize;	167,790,882✔
300	result.residuals_to_go = nodes_left_to_decode - 1;	167,790,882✔
301	}
302
303	// setup the first interval node so we can decode without branches
304	if !result.intervals.is_empty() {	49,126,258✔
305	let (start, len) = &mut result.intervals[0];	49,126,258✔
306	*len -= 1;	49,126,258✔
307	result.next_interval_node = *start;	49,126,258✔
308	*start += 1;	49,126,258✔
309	result.intervals_idx += (*len == 0) as usize;	49,126,258✔
310	};
311
312	// cache the first copied node so we don't have to check if the iter
313	// ended at every call of `next`
UNCOV 314	result.next_copied_node = result	×
UNCOV 315	.copied_nodes_iter	×
UNCOV 316	.as_mut()	×
317	.and_then(\|iter\| iter.next())	328,657,628✔
UNCOV 318	.unwrap_or(usize::MAX);	×
319
UNCOV 320	result	×
321	}
322	}
323
324	impl<F: SequentialDecoderFactory> BvGraph<F>
325	where
326	for<'a> F::Decoder<'a>: Decode,
327	{
328	#[inline(always)]
329	/// Creates an iterator specialized in the degrees of the nodes.
330	/// This is slightly faster because it can avoid decoding some of the nodes
331	/// and completely skip the merging step.
332	pub fn offset_deg_iter(&self) -> OffsetDegIter<F::Decoder<'_>> {	1✔
333	OffsetDegIter::new(
334	self.factory.new_decoder().unwrap(),	3✔
335	self.number_of_nodes,	1✔
336	self.compression_window,	1✔
337	self.min_interval_length,	1✔
338	)
339	}
340	}
341
342	impl<F: RandomAccessDecoderFactory> BvGraph<F>
343	where
344	for<'a> F::Decoder<'a>: Decode,
345	{
346	#[inline(always)]
347	/// Creates an iterator specialized in the degrees of the nodes starting
348	/// from a given node.
349	pub fn offset_deg_iter_from(&self, node: usize) -> OffsetDegIter<F::Decoder<'_>> {	100✔
350	let mut backrefs = vec![0; self.compression_window];	300✔
351	for node_id in node.saturating_sub(self.compression_window)..node {	1,072✔
UNCOV 352	backrefs[node_id % self.compression_window] = self.outdegree(node_id);	×
353	}
354	OffsetDegIter::new_from(
355	self.factory.new_decoder(node).unwrap(),	400✔
356	self.number_of_nodes,	100✔
357	self.compression_window,	100✔
358	self.min_interval_length,	100✔
359	node,	100✔
360	backrefs,	100✔
361	)
362	}
363	}
364	impl<F> RandomAccessGraph for BvGraph<F> where F: RandomAccessDecoderFactory {}
365
366	/// The iterator returned from [`BvGraph`] that returns the successors of a
367	/// node in sorted order.
368	#[derive(Debug, Clone)]
369	pub struct Succ<D: Decode> {
370	reader: D,
371	/// The number of values left
372	size: usize,
373	/// Iterator over the destinations that we are going to copy
374	/// from another node
375	copied_nodes_iter: Option<MaskedIterator<Succ<D>>>,
376
377	/// Intervals of extra nodes
378	intervals: Vec<(usize, usize)>,
379	/// The index of interval to return
380	intervals_idx: usize,
381	/// Remaining residual nodes
382	residuals_to_go: usize,
383	/// The next residual node
384	next_residual_node: usize,
385	/// The next residual node
386	next_copied_node: usize,
387	/// The next interval node
388	next_interval_node: usize,
389	}
390
391	impl<D: Decode> ExactSizeIterator for Succ<D> {
392	#[inline(always)]
393	fn len(&self) -> usize {	355,823,884✔
394	self.size	355,823,884✔
395	}
396	}
397
398	unsafe impl<D: Decode> SortedIterator for Succ<D> {}
399
400	impl<D: Decode> Succ<D> {
401	/// Creates an empty iterator
402	fn new(reader: D) -> Self {	529,252,068✔
403	Self {
404	reader,
405	size: 0,
406	copied_nodes_iter: None,
407	intervals: vec![],	529,252,068✔
408	intervals_idx: 0,
409	residuals_to_go: 0,
410	next_residual_node: usize::MAX,
411	next_copied_node: usize::MAX,
412	next_interval_node: usize::MAX,
413	}
414	}
415	}
416
417	impl<D: Decode> Iterator for Succ<D> {
418	type Item = usize;
419
420	fn next(&mut self) -> Option<Self::Item> {	2,147,483,647✔
421	// check if we should stop iterating
422	if self.size == 0 {	2,147,483,647✔
423	return None;	211,442,624✔
424	}
425
UNCOV 426	self.size -= 1;	×
UNCOV 427	debug_assert!(	×
UNCOV 428	self.next_copied_node != usize::MAX	×
429	\|\| self.next_residual_node != usize::MAX	2,147,483,647✔
430	\|\| self.next_interval_node != usize::MAX,	1,034,641,412✔
UNCOV 431	"At least one of the nodes must present, this should be a problem with the degree.",	×
432	);
433
434	// find the smallest of the values
435	let min = self.next_residual_node.min(self.next_interval_node);	2,147,483,647✔
436
437	// depending on from where the node was, forward it
438	if min >= self.next_copied_node {	×
439	let res = self.next_copied_node;	2,147,483,647✔
440	self.next_copied_node = self	2,147,483,647✔
441	.copied_nodes_iter	2,147,483,647✔
442	.as_mut()	2,147,483,647✔
443	.and_then(\|iter\| iter.next())	2,147,483,647✔
444	.unwrap_or(usize::MAX);	2,147,483,647✔
445	return Some(res);	2,147,483,647✔
446	} else if min == self.next_residual_node {	2,147,483,647✔
447	if self.residuals_to_go == 0 {	1,536,941,796✔
448	self.next_residual_node = usize::MAX;	289,762,968✔
449	} else {
450	self.residuals_to_go -= 1;	957,415,860✔
451	// NOTE: here we cannot propagate the error
452	self.next_residual_node += 1 + self.reader.read_residual() as usize;	957,415,860✔
453	}
454	} else {
455	let (start, len) = &mut self.intervals[self.intervals_idx];	2,147,483,647✔
UNCOV 456	debug_assert_ne!(	×
UNCOV 457	*len, 0,	×
UNCOV 458	"there should never be an interval with length zero here"	×
459	);
460	// if the interval has other values, just reduce the interval
461	*len -= 1;	2,147,483,647✔
462	self.next_interval_node = *start;	2,147,483,647✔
463	*start += 1;	2,147,483,647✔
464	self.intervals_idx += (*len == 0) as usize;	2,147,483,647✔
465	}
466
467	Some(min)	2,147,483,647✔
468	}
469
470	fn size_hint(&self) -> (usize, Option<usize>) {	4,064,316✔
471	(self.size, Some(self.size))	4,064,316✔
472	}
473	}
474
475	impl<'a, F: RandomAccessDecoderFactory> IntoLender for &'a BvGraph<F> {
476	type Lender = <BvGraph<F> as SequentialLabeling>::Lender<'a>;
477
478	#[inline(always)]
UNCOV 479	fn into_lender(self) -> Self::Lender {	×
UNCOV 480	self.iter()	×
481	}
482	}

vigna / webgraph-rs / 18008720487

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