17735521500

Committed 15 Sep 2025 01:54PM UTC coverage: 49.961% (-0.03%) from 49.987%

Build # 17735521500

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #137 from progval/fix-compil

bench_unit_transpose: Fix compilation

Run Details

3888 of 7782 relevant lines covered (49.96%)

23960578.28 hits per line

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

80.38

/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 lender::IntoLender;
use std::path::PathBuf;
use sux::traits::IndexedSeq;

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

vigna / webgraph-rs / 17735521500

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