25273649944

Committed 03 May 2026 07:55AM UTC coverage: 68.996% (+0.06%) from 68.941%

Build # 25273649944

Build Type

push

github

Committed by

vigna

Commit Message

Per-thread lists for faster local iterations

Coverage Stats

27 of 27 new or added lines in 1 file covered. (100.0%)

6 existing lines in 3 files now uncovered.

7524 of 10905 relevant lines covered (69.0%)

50179874.5 hits per line

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

53.03

/webgraph/src/graphs/bvgraph/codecs/dec_const.rs

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

use std::marker::PhantomData;

use super::super::*;
use anyhow::Result;
use anyhow::bail;
use dsi_bitstream::dispatch::code_consts;
use dsi_bitstream::dispatch::factory::CodesReaderFactoryHelper;
use dsi_bitstream::prelude::*;

use epserde::deser::MemCase;
use epserde::deser::Owned;
use value_traits::slices::SliceByValue;

/// An implementation of [`Decode`] with compile-time defined codes.
#[derive(Debug, Clone)]
#[repr(transparent)]
pub struct ConstCodesDecoder<
    E: Endianness,
    CR: CodesRead<E>,
    const OUTDEGREES: usize = { code_consts::GAMMA },
    const REFERENCES: usize = { code_consts::UNARY },
    const BLOCKS: usize = { code_consts::GAMMA },
    const INTERVALS: usize = { code_consts::GAMMA },
    const RESIDUALS: usize = { code_consts::ZETA3 },
> {
    /// The inner codes reader we will dispatch to
    pub(crate) code_reader: CR,
    /// Makes the compiler happy with the generics we don't use in the struct
    /// (but we need them to be able to use the trait)
    pub(crate) _marker: core::marker::PhantomData<E>,
}

impl<
    E: Endianness,
    CR: CodesRead<E> + BitSeek,
    const OUTDEGREES: usize,
    const REFERENCES: usize,
    const BLOCKS: usize,
    const INTERVALS: usize,
    const RESIDUALS: usize,
> BitSeek for ConstCodesDecoder<E, CR, OUTDEGREES, REFERENCES, BLOCKS, INTERVALS, RESIDUALS>
{
    type Error = <CR as BitSeek>::Error;

    fn set_bit_pos(&mut self, bit_index: u64) -> Result<(), Self::Error> {
        self.code_reader.set_bit_pos(bit_index)
    }

    fn bit_pos(&mut self) -> Result<u64, Self::Error> {
        self.code_reader.bit_pos()
    }
}

impl<
    E: Endianness,
    CR: CodesRead<E>,
    const OUTDEGREES: usize,
    const REFERENCES: usize,
    const BLOCKS: usize,
    const INTERVALS: usize,
    const RESIDUALS: usize,
> ConstCodesDecoder<E, CR, OUTDEGREES, REFERENCES, BLOCKS, INTERVALS, RESIDUALS>
{
    /// Creates a new [`ConstCodesDecoder`] from a [`CodesRead`] implementation
    /// and a [`CompFlags`] struct.
    /// # Errors
    /// If the codes in the [`CompFlags`] do not match the compile-time defined codes
    pub fn new(code_reader: CR, comp_flags: &CompFlags) -> Result<Self> {
        if comp_flags.outdegrees.to_code_const()? != OUTDEGREES {
            bail!("Code for outdegrees does not match");
        }
        if comp_flags.references.to_code_const()? != REFERENCES {
            bail!("Code for references does not match");
        }
        if comp_flags.blocks.to_code_const()? != BLOCKS {
            bail!("Code for blocks does not match");
        }
        if comp_flags.intervals.to_code_const()? != INTERVALS {
            bail!("Code for intervals does not match");
        }
        if comp_flags.residuals.to_code_const()? != RESIDUALS {
            bail!("Code for residuals does not match");
        }
        Ok(Self {
            code_reader,
            _marker: core::marker::PhantomData,
        })
    }
}

impl<
    E: Endianness,
    CR: CodesRead<E>,
    const OUTDEGREES: usize,
    const REFERENCES: usize,
    const BLOCKS: usize,
    const INTERVALS: usize,
    const RESIDUALS: usize,
> Decode for ConstCodesDecoder<E, CR, OUTDEGREES, REFERENCES, BLOCKS, INTERVALS, RESIDUALS>
{
    #[inline(always)]
    fn read_outdegree(&mut self) -> u64 {
        ConstCode::<OUTDEGREES>.read(&mut self.code_reader).unwrap()
    }

    #[inline(always)]
    fn read_reference_offset(&mut self) -> u64 {
        ConstCode::<REFERENCES>.read(&mut self.code_reader).unwrap()
    }

    #[inline(always)]
    fn read_block_count(&mut self) -> u64 {
        ConstCode::<BLOCKS>.read(&mut self.code_reader).unwrap()
    }
    #[inline(always)]
    fn read_block(&mut self) -> u64 {
        ConstCode::<BLOCKS>.read(&mut self.code_reader).unwrap()
    }

    #[inline(always)]
    fn read_interval_count(&mut self) -> u64 {
        ConstCode::<INTERVALS>.read(&mut self.code_reader).unwrap()
    }
    #[inline(always)]
    fn read_interval_start(&mut self) -> u64 {
        ConstCode::<INTERVALS>.read(&mut self.code_reader).unwrap()
    }
    #[inline(always)]
    fn read_interval_len(&mut self) -> u64 {
        ConstCode::<INTERVALS>.read(&mut self.code_reader).unwrap()
    }

    #[inline(always)]
    fn read_first_residual(&mut self) -> u64 {
        ConstCode::<RESIDUALS>.read(&mut self.code_reader).unwrap()
    }
    #[inline(always)]
    fn read_residual(&mut self) -> u64 {
        ConstCode::<RESIDUALS>.read(&mut self.code_reader).unwrap()
    }
}

/// A factory of [`ConstCodesDecoder`]s.
pub struct ConstCodesDecoderFactory<
    E: Endianness,
    F: CodesReaderFactoryHelper<E>,
    OFF: Offsets,
    const OUTDEGREES: usize = { code_consts::GAMMA },
    const REFERENCES: usize = { code_consts::UNARY },
    const BLOCKS: usize = { code_consts::GAMMA },
    const INTERVALS: usize = { code_consts::GAMMA },
    const RESIDUALS: usize = { code_consts::ZETA3 },
> {
    /// The owned data
    factory: F,
    /// The offsets into the data.
    offsets: MemCase<OFF>,
    /// Tell the compiler that's Ok that we don't store `E` but we need it
    /// for typing.
    _marker: core::marker::PhantomData<E>,
}

impl<
    E: Endianness,
    F: CodesReaderFactoryHelper<E>,
    OFF: Offsets,
    const OUTDEGREES: usize,
    const REFERENCES: usize,
    const BLOCKS: usize,
    const INTERVALS: usize,
    const RESIDUALS: usize,
> ConstCodesDecoderFactory<E, F, OFF, OUTDEGREES, REFERENCES, BLOCKS, INTERVALS, RESIDUALS>
{
    /// Remaps the offsets in a slice of `u64`.
    ///
    /// This method is mainly useful for benchmarking and testing purposes, as
    /// representing the offsets as a slice increases significantly the
    /// memory footprint.
    ///
    /// This method is used by [`BvGraph::offsets_to_slice`].
    pub fn offsets_to_slice(
        self,
    ) -> ConstCodesDecoderFactory<
        E,
        F,
        Owned<Box<[u64]>>,
        OUTDEGREES,
        REFERENCES,
        BLOCKS,
        INTERVALS,
        RESIDUALS,
    > {
        let offsets = self.offsets.uncase();
        ConstCodesDecoderFactory {
            factory: self.factory,
            offsets: (0..offsets.len())
                .map(|i| unsafe { offsets.get_value_unchecked(i) })
                .collect::<Vec<_>>()
                .into_boxed_slice()
                .into(),
            _marker: PhantomData,
        }
    }
}

impl<
    E: Endianness,
    F: CodesReaderFactoryHelper<E>,
    OFF: Offsets,
    const OUTDEGREES: usize,
    const REFERENCES: usize,
    const BLOCKS: usize,
    const INTERVALS: usize,
    const RESIDUALS: usize,
> ConstCodesDecoderFactory<E, F, OFF, OUTDEGREES, REFERENCES, BLOCKS, INTERVALS, RESIDUALS>
{
    /// Creates a new builder from the given data and compression flags.
    pub fn new(factory: F, offsets: MemCase<OFF>, comp_flags: CompFlags) -> anyhow::Result<Self> {
        if comp_flags.outdegrees.to_code_const()? != OUTDEGREES {
            bail!("Code for outdegrees does not match");
        }
        if comp_flags.references.to_code_const()? != REFERENCES {
            bail!("Code for references does not match");
        }
        if comp_flags.blocks.to_code_const()? != BLOCKS {
            bail!("Code for blocks does not match");
        }
        if comp_flags.intervals.to_code_const()? != INTERVALS {
            bail!("Code for intervals does not match");
        }
        if comp_flags.residuals.to_code_const()? != RESIDUALS {
            bail!("Code for residuals does not match");
        }
        Ok(Self {
            factory,
            offsets,
            _marker: core::marker::PhantomData,
        })
    }
}

impl<
    E: Endianness,
    F: CodesReaderFactoryHelper<E>,
    OFF: Offsets,
    const OUTDEGREES: usize,
    const REFERENCES: usize,
    const BLOCKS: usize,
    const INTERVALS: usize,
    const RESIDUALS: usize,
> RandomAccessDecoderFactory
    for ConstCodesDecoderFactory<E, F, OFF, OUTDEGREES, REFERENCES, BLOCKS, INTERVALS, RESIDUALS>
where
    for<'a> <F as CodesReaderFactory<E>>::CodesReader<'a>: BitSeek,
{
    type Decoder<'a>
        = ConstCodesDecoder<E, <F as CodesReaderFactory<E>>::CodesReader<'a>>
    where
        Self: 'a;

    fn new_decoder(&self, offset: usize) -> anyhow::Result<Self::Decoder<'_>> {
        let mut code_reader = self.factory.new_reader();
        code_reader.set_bit_pos(unsafe { self.offsets.uncase().get_value_unchecked(offset) })?;

        Ok(ConstCodesDecoder {
            code_reader,
            _marker: PhantomData,
        })
    }
}

impl<
    E: Endianness,
    F: CodesReaderFactoryHelper<E>,
    OFF: Offsets,
    const OUTDEGREES: usize,
    const REFERENCES: usize,
    const BLOCKS: usize,
    const INTERVALS: usize,
    const RESIDUALS: usize,
> SequentialDecoderFactory
    for ConstCodesDecoderFactory<E, F, OFF, OUTDEGREES, REFERENCES, BLOCKS, INTERVALS, RESIDUALS>
{
    type Decoder<'a>
        = ConstCodesDecoder<E, <F as CodesReaderFactory<E>>::CodesReader<'a>>
    where
        Self: 'a;

    fn new_decoder(&self) -> anyhow::Result<Self::Decoder<'_>> {
        let code_reader = self.factory.new_reader();

        Ok(ConstCodesDecoder {
            code_reader,
            _marker: PhantomData,
        })
    }
}

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::marker::PhantomData;
9
10	use super::super::*;
11	use anyhow::Result;
12	use anyhow::bail;
13	use dsi_bitstream::dispatch::code_consts;
14	use dsi_bitstream::dispatch::factory::CodesReaderFactoryHelper;
15	use dsi_bitstream::prelude::*;
16
17	use epserde::deser::MemCase;
18	use epserde::deser::Owned;
19	use value_traits::slices::SliceByValue;
20
21	/// An implementation of [`Decode`] with compile-time defined codes.
22	#[derive(Debug, Clone)]
23	#[repr(transparent)]
24	pub struct ConstCodesDecoder<
25	E: Endianness,
26	CR: CodesRead<E>,
27	const OUTDEGREES: usize = { code_consts::GAMMA },
28	const REFERENCES: usize = { code_consts::UNARY },
29	const BLOCKS: usize = { code_consts::GAMMA },
30	const INTERVALS: usize = { code_consts::GAMMA },
31	const RESIDUALS: usize = { code_consts::ZETA3 },
32	> {
33	/// The inner codes reader we will dispatch to
34	pub(crate) code_reader: CR,
35	/// Makes the compiler happy with the generics we don't use in the struct
36	/// (but we need them to be able to use the trait)
37	pub(crate) _marker: core::marker::PhantomData<E>,
38	}
39
40	impl<
41	E: Endianness,
42	CR: CodesRead<E> + BitSeek,
43	const OUTDEGREES: usize,
44	const REFERENCES: usize,
45	const BLOCKS: usize,
46	const INTERVALS: usize,
47	const RESIDUALS: usize,
48	> BitSeek for ConstCodesDecoder<E, CR, OUTDEGREES, REFERENCES, BLOCKS, INTERVALS, RESIDUALS>
49	{
50	type Error = <CR as BitSeek>::Error;
51
52	fn set_bit_pos(&mut self, bit_index: u64) -> Result<(), Self::Error> {	×
53	self.code_reader.set_bit_pos(bit_index)	×
54	}
55
56	fn bit_pos(&mut self) -> Result<u64, Self::Error> {	4✔
57	self.code_reader.bit_pos()	8✔
58	}
59	}
60
61	impl<
62	E: Endianness,
63	CR: CodesRead<E>,
64	const OUTDEGREES: usize,
65	const REFERENCES: usize,
66	const BLOCKS: usize,
67	const INTERVALS: usize,
68	const RESIDUALS: usize,
69	> ConstCodesDecoder<E, CR, OUTDEGREES, REFERENCES, BLOCKS, INTERVALS, RESIDUALS>
70	{
71	/// Creates a new [`ConstCodesDecoder`] from a [`CodesRead`] implementation
72	/// and a [`CompFlags`] struct.
73	/// # Errors
74	/// If the codes in the [`CompFlags`] do not match the compile-time defined codes
75	pub fn new(code_reader: CR, comp_flags: &CompFlags) -> Result<Self> {	×
76	if comp_flags.outdegrees.to_code_const()? != OUTDEGREES {	×
77	bail!("Code for outdegrees does not match");	×
78	}
79	if comp_flags.references.to_code_const()? != REFERENCES {	×
80	bail!("Code for references does not match");	×
81	}
82	if comp_flags.blocks.to_code_const()? != BLOCKS {	×
83	bail!("Code for blocks does not match");	×
84	}
85	if comp_flags.intervals.to_code_const()? != INTERVALS {	×
86	bail!("Code for intervals does not match");	×
87	}
88	if comp_flags.residuals.to_code_const()? != RESIDUALS {	×
89	bail!("Code for residuals does not match");	×
90	}
91	Ok(Self {	×
92	code_reader,	×
93	_marker: core::marker::PhantomData,	×
94	})
95	}
96	}
97
98	impl<
99	E: Endianness,
100	CR: CodesRead<E>,
101	const OUTDEGREES: usize,
102	const REFERENCES: usize,
103	const BLOCKS: usize,
104	const INTERVALS: usize,
105	const RESIDUALS: usize,
106	> Decode for ConstCodesDecoder<E, CR, OUTDEGREES, REFERENCES, BLOCKS, INTERVALS, RESIDUALS>
107	{
108	#[inline(always)]
109	fn read_outdegree(&mut self) -> u64 {	108✔
110	ConstCode::<OUTDEGREES>.read(&mut self.code_reader).unwrap()	432✔
111	}
112
113	#[inline(always)]
114	fn read_reference_offset(&mut self) -> u64 {	104✔
115	ConstCode::<REFERENCES>.read(&mut self.code_reader).unwrap()	416✔
116	}
117
118	#[inline(always)]
UNCOV 119	fn read_block_count(&mut self) -> u64 {	×
UNCOV 120	ConstCode::<BLOCKS>.read(&mut self.code_reader).unwrap()	×
121	}
122	#[inline(always)]
123	fn read_block(&mut self) -> u64 {	×
124	ConstCode::<BLOCKS>.read(&mut self.code_reader).unwrap()	×
125	}
126
127	#[inline(always)]
128	fn read_interval_count(&mut self) -> u64 {	104✔
129	ConstCode::<INTERVALS>.read(&mut self.code_reader).unwrap()	416✔
130	}
131	#[inline(always)]
132	fn read_interval_start(&mut self) -> u64 {	1✔
133	ConstCode::<INTERVALS>.read(&mut self.code_reader).unwrap()	4✔
134	}
135	#[inline(always)]
136	fn read_interval_len(&mut self) -> u64 {	1✔
137	ConstCode::<INTERVALS>.read(&mut self.code_reader).unwrap()	4✔
138	}
139
140	#[inline(always)]
141	fn read_first_residual(&mut self) -> u64 {	103✔
142	ConstCode::<RESIDUALS>.read(&mut self.code_reader).unwrap()	412✔
143	}
144	#[inline(always)]
UNCOV 145	fn read_residual(&mut self) -> u64 {	×
UNCOV 146	ConstCode::<RESIDUALS>.read(&mut self.code_reader).unwrap()	×
147	}
148	}
149
150	/// A factory of [`ConstCodesDecoder`]s.
151	pub struct ConstCodesDecoderFactory<
152	E: Endianness,
153	F: CodesReaderFactoryHelper<E>,
154	OFF: Offsets,
155	const OUTDEGREES: usize = { code_consts::GAMMA },
156	const REFERENCES: usize = { code_consts::UNARY },
157	const BLOCKS: usize = { code_consts::GAMMA },
158	const INTERVALS: usize = { code_consts::GAMMA },
159	const RESIDUALS: usize = { code_consts::ZETA3 },
160	> {
161	/// The owned data
162	factory: F,
163	/// The offsets into the data.
164	offsets: MemCase<OFF>,
165	/// Tell the compiler that's Ok that we don't store `E` but we need it
166	/// for typing.
167	_marker: core::marker::PhantomData<E>,
168	}
169
170	impl<
171	E: Endianness,
172	F: CodesReaderFactoryHelper<E>,
173	OFF: Offsets,
174	const OUTDEGREES: usize,
175	const REFERENCES: usize,
176	const BLOCKS: usize,
177	const INTERVALS: usize,
178	const RESIDUALS: usize,
179	> ConstCodesDecoderFactory<E, F, OFF, OUTDEGREES, REFERENCES, BLOCKS, INTERVALS, RESIDUALS>
180	{
181	/// Remaps the offsets in a slice of `u64`.
182	///
183	/// This method is mainly useful for benchmarking and testing purposes, as
184	/// representing the offsets as a slice increases significantly the
185	/// memory footprint.
186	///
187	/// This method is used by [`BvGraph::offsets_to_slice`].
188	pub fn offsets_to_slice(	×
189	self,
190	) -> ConstCodesDecoderFactory<
191	E,
192	F,
193	Owned<Box<[u64]>>,
194	OUTDEGREES,
195	REFERENCES,
196	BLOCKS,
197	INTERVALS,
198	RESIDUALS,
199	> {
200	let offsets = self.offsets.uncase();	×
201	ConstCodesDecoderFactory {
202	factory: self.factory,	×
203	offsets: (0..offsets.len())	×
204	.map(\|i\| unsafe { offsets.get_value_unchecked(i) })
205	.collect::<Vec<_>>()
206	.into_boxed_slice()
207	.into(),
208	_marker: PhantomData,
209	}
210	}
211	}
212
213	impl<
214	E: Endianness,
215	F: CodesReaderFactoryHelper<E>,
216	OFF: Offsets,
217	const OUTDEGREES: usize,
218	const REFERENCES: usize,
219	const BLOCKS: usize,
220	const INTERVALS: usize,
221	const RESIDUALS: usize,
222	> ConstCodesDecoderFactory<E, F, OFF, OUTDEGREES, REFERENCES, BLOCKS, INTERVALS, RESIDUALS>
223	{
224	/// Creates a new builder from the given data and compression flags.
225	pub fn new(factory: F, offsets: MemCase<OFF>, comp_flags: CompFlags) -> anyhow::Result<Self> {	9✔
226	if comp_flags.outdegrees.to_code_const()? != OUTDEGREES {	18✔
227	bail!("Code for outdegrees does not match");	×
228	}
229	if comp_flags.references.to_code_const()? != REFERENCES {	18✔
230	bail!("Code for references does not match");	×
231	}
232	if comp_flags.blocks.to_code_const()? != BLOCKS {	18✔
233	bail!("Code for blocks does not match");	×
234	}
235	if comp_flags.intervals.to_code_const()? != INTERVALS {	18✔
236	bail!("Code for intervals does not match");	×
237	}
238	if comp_flags.residuals.to_code_const()? != RESIDUALS {	18✔
239	bail!("Code for residuals does not match");	×
240	}
241	Ok(Self {	9✔
242	factory,	18✔
243	offsets,	9✔
244	_marker: core::marker::PhantomData,	9✔
245	})
246	}
247	}
248
249	impl<
250	E: Endianness,
251	F: CodesReaderFactoryHelper<E>,
252	OFF: Offsets,
253	const OUTDEGREES: usize,
254	const REFERENCES: usize,
255	const BLOCKS: usize,
256	const INTERVALS: usize,
257	const RESIDUALS: usize,
258	> RandomAccessDecoderFactory
259	for ConstCodesDecoderFactory<E, F, OFF, OUTDEGREES, REFERENCES, BLOCKS, INTERVALS, RESIDUALS>
260	where
261	for<'a> <F as CodesReaderFactory<E>>::CodesReader<'a>: BitSeek,
262	{
263	type Decoder<'a>
264	= ConstCodesDecoder<E, <F as CodesReaderFactory<E>>::CodesReader<'a>>
265	where
266	Self: 'a;
267
268	fn new_decoder(&self, offset: usize) -> anyhow::Result<Self::Decoder<'_>> {	4✔
269	let mut code_reader = self.factory.new_reader();	12✔
270	code_reader.set_bit_pos(unsafe { self.offsets.uncase().get_value_unchecked(offset) })?;	20✔
271
272	Ok(ConstCodesDecoder {	4✔
273	code_reader,	4✔
274	_marker: PhantomData,	4✔
275	})
276	}
277	}
278
279	impl<
280	E: Endianness,
281	F: CodesReaderFactoryHelper<E>,
282	OFF: Offsets,
283	const OUTDEGREES: usize,
284	const REFERENCES: usize,
285	const BLOCKS: usize,
286	const INTERVALS: usize,
287	const RESIDUALS: usize,
288	> SequentialDecoderFactory
289	for ConstCodesDecoderFactory<E, F, OFF, OUTDEGREES, REFERENCES, BLOCKS, INTERVALS, RESIDUALS>
290	{
291	type Decoder<'a>
292	= ConstCodesDecoder<E, <F as CodesReaderFactory<E>>::CodesReader<'a>>
293	where
294	Self: 'a;
295
296	fn new_decoder(&self) -> anyhow::Result<Self::Decoder<'_>> {	8✔
297	let code_reader = self.factory.new_reader();	24✔
298
299	Ok(ConstCodesDecoder {	8✔
300	code_reader,	8✔
301	_marker: PhantomData,	8✔
302	})
303	}
304	}

vigna / webgraph-rs / 25273649944

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