• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

vigna / webgraph-rs / 14999125721

13 May 2025 02:22PM UTC coverage: 49.654% (-5.7%) from 55.382%
14999125721

push

github

zommiommy
wip hyperball cli

4 of 147 new or added lines in 4 files covered. (2.72%)

477 existing lines in 46 files now uncovered.

3663 of 7377 relevant lines covered (49.65%)

25650535.86 hits per line

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

93.52
/webgraph/src/graphs/bvgraph/codecs/dec_dyn.rs
1
/*
2
 * SPDX-FileCopyrightText: 2023 Inria
3
 * SPDX-FileCopyrightText: 2023 Sebastiano Vigna
4
 * SPDX-FileCopyrightText: 2023 Tommaso Fontana
5
 *
6
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
7
 */
8

9
use std::marker::PhantomData;
10

11
use super::super::*;
12
use dsi_bitstream::dispatch::factory::CodesReaderFactoryHelper;
13
use dsi_bitstream::dispatch::CodesReaderFactory;
14
use dsi_bitstream::prelude::*;
15
use epserde::deser::MemCase;
16
use sux::traits::IndexedSeq;
17

18
#[derive(Debug)]
19
pub struct DynCodesDecoder<E: Endianness, CR: CodesRead<E>> {
20
    pub(crate) code_reader: CR,
21
    pub(crate) read_outdegree: FuncCodeReader<E, CR>,
22
    pub(crate) read_reference_offset: FuncCodeReader<E, CR>,
23
    pub(crate) read_block_count: FuncCodeReader<E, CR>,
24
    pub(crate) read_block: FuncCodeReader<E, CR>,
25
    pub(crate) read_interval_count: FuncCodeReader<E, CR>,
26
    pub(crate) read_interval_start: FuncCodeReader<E, CR>,
27
    pub(crate) read_interval_len: FuncCodeReader<E, CR>,
28
    pub(crate) read_first_residual: FuncCodeReader<E, CR>,
29
    pub(crate) read_residual: FuncCodeReader<E, CR>,
30
    pub(crate) _marker: core::marker::PhantomData<E>,
31
}
32

33
/// manual implementation to avoid the `E: Clone` bound
34
impl<E: Endianness, CR: CodesRead<E> + Clone> Clone for DynCodesDecoder<E, CR> {
35
    fn clone(&self) -> Self {
109✔
36
        Self {
37
            code_reader: self.code_reader.clone(),
327✔
38
            read_outdegree: self.read_outdegree.clone(),
327✔
39
            read_reference_offset: self.read_reference_offset.clone(),
327✔
40
            read_block_count: self.read_block_count.clone(),
327✔
41
            read_block: self.read_block.clone(),
327✔
42
            read_interval_count: self.read_interval_count.clone(),
327✔
43
            read_interval_start: self.read_interval_start.clone(),
327✔
44
            read_interval_len: self.read_interval_len.clone(),
327✔
45
            read_first_residual: self.read_first_residual.clone(),
327✔
46
            read_residual: self.read_residual.clone(),
218✔
47
            _marker: PhantomData,
48
        }
49
    }
50
}
51

52
impl<E: Endianness, CR: CodesRead<E>> DynCodesDecoder<E, CR> {
53
    pub fn new(code_reader: CR, cf: &CompFlags) -> anyhow::Result<Self> {
31,104✔
UNCOV
54
        Ok(Self {
×
55
            code_reader,
31,104✔
56
            read_outdegree: FuncCodeReader::new(cf.outdegrees)?,
62,208✔
57
            read_reference_offset: FuncCodeReader::new(cf.references)?,
31,104✔
58
            read_block_count: FuncCodeReader::new(cf.blocks)?,
31,104✔
59
            read_block: FuncCodeReader::new(cf.blocks)?,
31,104✔
60
            read_interval_count: FuncCodeReader::new(cf.intervals)?,
31,104✔
61
            read_interval_start: FuncCodeReader::new(cf.intervals)?,
31,104✔
62
            read_interval_len: FuncCodeReader::new(cf.intervals)?,
31,104✔
63
            read_first_residual: FuncCodeReader::new(cf.residuals)?,
31,104✔
64
            read_residual: FuncCodeReader::new(cf.residuals)?,
31,104✔
65
            _marker: core::marker::PhantomData,
31,104✔
66
        })
67
    }
68
}
69

70
impl<E: Endianness, CR: CodesRead<E> + BitSeek> BitSeek for DynCodesDecoder<E, CR> {
71
    type Error = <CR as BitSeek>::Error;
72

73
    #[inline(always)]
74
    fn set_bit_pos(&mut self, bit_index: u64) -> Result<(), Self::Error> {
×
75
        self.code_reader.set_bit_pos(bit_index)
×
76
    }
77

78
    #[inline(always)]
79
    fn bit_pos(&mut self) -> Result<u64, Self::Error> {
584,464✔
80
        self.code_reader.bit_pos()
1,168,928✔
81
    }
82
}
83

84
impl<E: Endianness, CR: CodesRead<E>> Decode for DynCodesDecoder<E, CR> {
85
    #[inline(always)]
86
    fn read_outdegree(&mut self) -> u64 {
77,946,313✔
87
        self.read_outdegree.read(&mut self.code_reader).unwrap()
311,785,252✔
88
    }
89

90
    #[inline(always)]
91
    fn read_reference_offset(&mut self) -> u64 {
68,081,185✔
92
        self.read_reference_offset
68,081,185✔
93
            .read(&mut self.code_reader)
136,162,370✔
94
            .unwrap()
95
    }
96

97
    #[inline(always)]
98
    fn read_block_count(&mut self) -> u64 {
42,176,707✔
99
        self.read_block_count.read(&mut self.code_reader).unwrap()
168,706,828✔
100
    }
101
    #[inline(always)]
102
    fn read_block(&mut self) -> u64 {
70,865,668✔
103
        self.read_block.read(&mut self.code_reader).unwrap()
283,462,672✔
104
    }
105

106
    #[inline(always)]
107
    fn read_interval_count(&mut self) -> u64 {
53,611,215✔
108
        self.read_interval_count
53,611,215✔
109
            .read(&mut self.code_reader)
107,222,430✔
110
            .unwrap()
111
    }
112
    #[inline(always)]
113
    fn read_interval_start(&mut self) -> u64 {
18,946,880✔
114
        self.read_interval_start
18,946,880✔
115
            .read(&mut self.code_reader)
37,893,760✔
116
            .unwrap()
117
    }
118
    #[inline(always)]
119
    fn read_interval_len(&mut self) -> u64 {
18,946,880✔
120
        self.read_interval_len.read(&mut self.code_reader).unwrap()
75,787,520✔
121
    }
122

123
    #[inline(always)]
124
    fn read_first_residual(&mut self) -> u64 {
53,416,545✔
125
        self.read_first_residual
53,416,545✔
126
            .read(&mut self.code_reader)
106,833,090✔
127
            .unwrap()
128
    }
129
    #[inline(always)]
130
    fn read_residual(&mut self) -> u64 {
453,834,752✔
131
        self.read_residual.read(&mut self.code_reader).unwrap()
1,815,339,008✔
132
    }
133
}
134

135
#[derive(Debug)]
136
pub struct DynCodesDecoderFactory<
137
    E: Endianness,
138
    F: CodesReaderFactoryHelper<E>,
139
    OFF: IndexedSeq<Input = usize, Output = usize>,
140
> {
141
    /// The owned data we will read as a bitstream.
142
    factory: F,
143
    /// The offsets into the data.
144
    offsets: MemCase<OFF>,
145
    /// The compression flags.
146
    compression_flags: CompFlags,
147
    // The cached functions to read the codes.
148
    read_outdegree: FactoryFuncCodeReader<E, F>,
149
    read_reference_offset: FactoryFuncCodeReader<E, F>,
150
    read_block_count: FactoryFuncCodeReader<E, F>,
151
    read_blocks: FactoryFuncCodeReader<E, F>,
152
    read_interval_count: FactoryFuncCodeReader<E, F>,
153
    read_interval_start: FactoryFuncCodeReader<E, F>,
154
    read_interval_len: FactoryFuncCodeReader<E, F>,
155
    read_first_residual: FactoryFuncCodeReader<E, F>,
156
    read_residual: FactoryFuncCodeReader<E, F>,
157
    /// Tell the compiler that's Ok that we don't store `E` but we need it
158
    /// for typing.
159
    _marker: core::marker::PhantomData<E>,
160
}
161

162
impl<
163
        E: Endianness,
164
        F: CodesReaderFactoryHelper<E>,
165
        OFF: IndexedSeq<Input = usize, Output = usize>,
166
    > DynCodesDecoderFactory<E, F, OFF>
167
where
168
    // TODO!: This dependence can soon be removed, as there will be a IndexedSeq::iter method
169
    for<'a> &'a OFF: IntoIterator<Item = usize>,
170
{
171
    /// Remaps the offsets in a slice of `usize`.
172
    ///
173
    /// This method is mainly useful for benchmarking and testing purposes, as
174
    /// representing the offsets as a slice increasing significantly the
175
    /// memory footprint.
176
    ///
177
    /// This method is used by [`BvGraph::offsets_to_slice`].
178
    pub fn offsets_to_slice(self) -> DynCodesDecoderFactory<E, F, SliceSeq<usize, Box<[usize]>>> {
1✔
179
        DynCodesDecoderFactory {
180
            factory: self.factory,
2✔
181
            offsets: <Box<[usize]> as Into<SliceSeq<usize, Box<[usize]>>>>::into(
2✔
182
                self.offsets
183
                    .into_iter()
184
                    .collect::<Vec<_>>()
185
                    .into_boxed_slice(),
186
            )
187
            .into(),
188
            compression_flags: self.compression_flags,
2✔
189
            read_outdegree: self.read_outdegree,
2✔
190
            read_reference_offset: self.read_reference_offset,
2✔
191
            read_block_count: self.read_block_count,
2✔
192
            read_blocks: self.read_blocks,
2✔
193
            read_interval_count: self.read_interval_count,
2✔
194
            read_interval_start: self.read_interval_start,
2✔
195
            read_interval_len: self.read_interval_len,
2✔
196
            read_first_residual: self.read_first_residual,
2✔
197
            read_residual: self.read_residual,
1✔
198
            _marker: PhantomData,
199
        }
200
    }
201
}
202

203
impl<
204
        E: Endianness,
205
        F: CodesReaderFactoryHelper<E>,
206
        OFF: IndexedSeq<Input = usize, Output = usize>,
207
    > DynCodesDecoderFactory<E, F, OFF>
208
{
209
    #[inline(always)]
210
    /// Returns a clone of the compression flags.
211
    pub fn get_compression_flags(&self) -> CompFlags {
×
212
        self.compression_flags
×
213
    }
214

215
    /// Creates a new builder from the data and the compression flags.
216
    pub fn new(factory: F, offsets: MemCase<OFF>, cf: CompFlags) -> anyhow::Result<Self> {
13,969✔
UNCOV
217
        Ok(Self {
×
218
            factory,
13,969✔
219
            offsets,
13,969✔
220
            read_outdegree: FactoryFuncCodeReader::new(cf.outdegrees)?,
27,938✔
221
            read_reference_offset: FactoryFuncCodeReader::new(cf.references)?,
13,969✔
222
            read_block_count: FactoryFuncCodeReader::new(cf.blocks)?,
13,969✔
223
            read_blocks: FactoryFuncCodeReader::new(cf.blocks)?,
13,969✔
224
            read_interval_count: FactoryFuncCodeReader::new(cf.intervals)?,
13,969✔
225
            read_interval_start: FactoryFuncCodeReader::new(cf.intervals)?,
13,969✔
226
            read_interval_len: FactoryFuncCodeReader::new(cf.intervals)?,
13,969✔
227
            read_first_residual: FactoryFuncCodeReader::new(cf.residuals)?,
13,969✔
228
            read_residual: FactoryFuncCodeReader::new(cf.residuals)?,
13,969✔
229
            compression_flags: cf,
13,969✔
UNCOV
230
            _marker: core::marker::PhantomData,
×
231
        })
232
    }
233
}
234

235
impl<
236
        E: Endianness,
237
        F: CodesReaderFactoryHelper<E>,
238
        OFF: IndexedSeq<Input = usize, Output = usize>,
239
    > RandomAccessDecoderFactory for DynCodesDecoderFactory<E, F, OFF>
240
where
241
    for<'a> <F as CodesReaderFactory<E>>::CodesReader<'a>: BitSeek,
242
{
243
    type Decoder<'a>
244
        = DynCodesDecoder<E, <F as CodesReaderFactory<E>>::CodesReader<'a>>
245
    where
246
        Self: 'a;
247

248
    #[inline(always)]
249
    fn new_decoder(&self, node: usize) -> anyhow::Result<Self::Decoder<'_>> {
227,767,094✔
250
        let mut code_reader = self.factory.new_reader();
683,301,282✔
251
        code_reader.set_bit_pos(self.offsets.get(node) as u64)?;
911,068,376✔
252

253
        Ok(DynCodesDecoder {
227,767,094✔
254
            code_reader,
227,767,094✔
255
            read_outdegree: self.read_outdegree.get(),
227,767,094✔
256
            read_reference_offset: self.read_reference_offset.get(),
227,767,094✔
257
            read_block_count: self.read_block_count.get(),
227,767,094✔
258
            read_block: self.read_blocks.get(),
227,767,094✔
259
            read_interval_count: self.read_interval_count.get(),
227,767,094✔
260
            read_interval_start: self.read_interval_start.get(),
227,767,094✔
261
            read_interval_len: self.read_interval_len.get(),
227,767,094✔
262
            read_first_residual: self.read_first_residual.get(),
227,767,094✔
263
            read_residual: self.read_residual.get(),
227,767,094✔
264
            _marker: PhantomData,
227,767,094✔
265
        })
266
    }
267
}
268

269
impl<
270
        E: Endianness,
271
        F: CodesReaderFactoryHelper<E>,
272
        OFF: IndexedSeq<Input = usize, Output = usize>,
273
    > SequentialDecoderFactory for DynCodesDecoderFactory<E, F, OFF>
274
{
275
    type Decoder<'a>
276
        = DynCodesDecoder<E, <F as CodesReaderFactory<E>>::CodesReader<'a>>
277
    where
278
        Self: 'a;
279

280
    #[inline(always)]
281
    fn new_decoder(&self) -> anyhow::Result<Self::Decoder<'_>> {
6,985✔
282
        Ok(DynCodesDecoder {
6,985✔
283
            code_reader: self.factory.new_reader(),
20,955✔
284
            read_outdegree: self.read_outdegree.get(),
20,955✔
285
            read_reference_offset: self.read_reference_offset.get(),
20,955✔
286
            read_block_count: self.read_block_count.get(),
20,955✔
287
            read_block: self.read_blocks.get(),
20,955✔
288
            read_interval_count: self.read_interval_count.get(),
20,955✔
289
            read_interval_start: self.read_interval_start.get(),
20,955✔
290
            read_interval_len: self.read_interval_len.get(),
20,955✔
291
            read_first_residual: self.read_first_residual.get(),
20,955✔
292
            read_residual: self.read_residual.get(),
13,970✔
293
            _marker: PhantomData,
6,985✔
294
        })
295
    }
296
}
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc