17861369619

Committed 19 Sep 2025 02:34PM UTC coverage: 66.129% (+1.4%) from 64.717%

Build # 17861369619

Build Type

push

github

Committed by

vigna

Commit Message

Minor fixes

Run Details

3774 of 5707 relevant lines covered (66.13%)

117089019.02 hits per line

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

38.89

/src/func/vfunc.rs

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

use std::borrow::Borrow;

use super::shard_edge::FuseLge3Shards;
use crate::bits::BitFieldVec;
use crate::func::shard_edge::ShardEdge;
use crate::traits::bit_field_slice::*;
use crate::utils::*;
use mem_dbg::*;

/// Static functions with low space overhead, fast parallel construction, and
/// fast queries.
///
/// *Static functions* map keys to values, but they do not store the keys:
/// querying a static function with a key outside of the original set will lead
/// to an arbitrary result. Another name for static functions *retrieval data
/// structure*. Values are retrieved using the [`get`](VFunc::get) method. On
/// some architectures, and with some constraints,
/// [`get_unaligned`](VFunc::get_unaligned) might be faster.
///
/// In exchange, static functions have a very low space overhead, and make it
/// possible to store the association between keys and values just in the space
/// required by the values (with a small overhead).
///
/// This structure is based on “[ε-Cost Sharding: Scaling Hypergraph-Based
/// Static Functions and Filters to Trillions of
/// Keys](https://arxiv.org/abs/2503.18397)”. Space overhead with respect to the
/// optimum depends on the [`ShardEdge`] type. The default is
/// [`FuseLge3Shards`], which provides 10.5% space overhead for large key sets
/// (above a few million keys), which grow up to 12% going towards smaller key
/// sets. Details on other possible [`ShardEdge`] implementations can be found
/// in the [`shard_edge`](crate::func::shard_edge) module documentation.
///
/// Instances of this structure are immutable; they are built using a
/// [`VBuilder`](crate::func::VBuilder) and can be serialized using
/// [ε-serde](`epserde`). Please see the documentation of
/// [`VBuilder`](crate::func::VBuilder) for examples.
///
/// # Generics
///
/// * `T`: The type of the keys.
/// * `W`: The word used to store the data, which is also the output type. It
///   can be any unsigned type.
/// * `D`: The backend storing the function data. It can be a
///   [`BitFieldVec<W>`](crate::bits::BitFieldVec) or a `Box<[W]>`. In the first
///   case, the data is stored using exactly the number of bits needed, but
///   access is slightly slower, while in the second case the data is stored in
///   a boxed slice of `W`, thus forcing the number of bits to the number of
///   bits of `W`, but access will be faster. Note that for most bit sizes in
///   the first case on some architectures you can use [unaligned
///   reads](VFunc::get_unaligned) to get faster queries.
/// * `S`: The signature type. The default is `[u64; 2]`. You can switch to
///   `[u64; 1]` (and possibly
///   [`FuseLge3NoShards`](crate::func::shard_edge::FuseLge3NoShards)) for
///   slightly faster construction and queries, but the construction will not
///   scale beyond 3.8 billion keys.
/// * `E`: The sharding and edge logic type. The default is [`FuseLge3Shards`].
///   For small sets of keys you might try
///   [`FuseLge3NoShards`](crate::func::shard_edge::FuseLge3NoShards), possibly
///   coupled with `[u64; 1]` signatures. For functions with more than a few
///   dozen billion keys, you might try
///   [`FuseLge3FullSigs`](crate::func::shard_edge::FuseLge3FullSigs).
#[derive(Debug, MemDbg, MemSize)]
#[cfg_attr(feature = "epserde", derive(epserde::Epserde))]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct VFunc<
    T: ?Sized + ToSig<S>,
    W: BinSafe + Word = usize,
    D: BitFieldSlice<W> = Box<[W]>,
    S: Sig = [u64; 2],
    E: ShardEdge<S, 3> = FuseLge3Shards,
> {
    pub(crate) shard_edge: E,
    pub(crate) seed: u64,
    pub(crate) num_keys: usize,
    pub(crate) data: D,
    pub(crate) _marker_t: std::marker::PhantomData<T>,
    pub(crate) _marker_w: std::marker::PhantomData<W>,
    pub(crate) _marker_s: std::marker::PhantomData<S>,
}

impl<T: ?Sized + ToSig<S>, W: BinSafe + Word, D: BitFieldSlice<W>, S: Sig, E: ShardEdge<S, 3>>
    VFunc<T, W, D, S, E>
{
    /// Returns the value associated with the given signature, or a random value
    /// if the signature is not the signature of a key.
    ///
    /// This method is mainly useful in the construction of compound functions.
    #[inline]
    pub fn get_by_sig(&self, sig: S) -> W {
        let edge = self.shard_edge.edge(sig);
        unsafe {
            self.data.get_unchecked(edge[0])
                ^ self.data.get_unchecked(edge[1])
                ^ self.data.get_unchecked(edge[2])
        }
    }

    /// Returns the value associated with the given key, or a random value if the
    /// key is not present.
    #[inline(always)]
    pub fn get(&self, key: impl Borrow<T>) -> W {
        self.get_by_sig(T::to_sig(key.borrow(), self.seed))
    }

    /// Returns the number of keys in the function.
    pub fn len(&self) -> usize {
        self.num_keys
    }

    /// Returns whether the function has no keys.
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
}

impl<T: ?Sized + ToSig<S>, W: BinSafe + Word, S: Sig, E: ShardEdge<S, 3>>
    VFunc<T, W, BitFieldVec<W>, S, E>
{
    /// Returns the value associated with the given signature, or a random value
    /// if the signature is not the signature of a key, using [unaligned
    /// reads](BitFieldVec::get_unaligned).
    ///
    /// This method uses [`BitFieldVec::get_unaligned`], and has
    /// the same constraints.
    ///
    /// This method is mainly useful in the construction of compound functions.
    #[inline]
    pub fn get_by_sig_unaligned(&self, sig: S) -> W {
        let edge = self.shard_edge.edge(sig);
        unsafe {
            self.data.get_unaligned_unchecked(edge[0])
                ^ self.data.get_unaligned_unchecked(edge[1])
                ^ self.data.get_unaligned_unchecked(edge[2])
        }
    }

    /// Returns the value associated with the given key, or a random value if
    /// the key is not present, using [unaligned
    /// reads](BitFieldVec::get_unaligned).
    ///
    /// This method uses [`BitFieldVec::get_unaligned`], and has
    /// the same constraints.
    #[inline(always)]
    pub fn get_unaligned(&self, key: impl Borrow<T>) -> W {
        self.get_by_sig_unaligned(T::to_sig(key.borrow(), self.seed))
    }
}

1	/*
2	* SPDX-FileCopyrightText: 2025 Sebastiano Vigna
3	*
4	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
5	*/
6
7	use std::borrow::Borrow;
8
9	use super::shard_edge::FuseLge3Shards;
10	use crate::bits::BitFieldVec;
11	use crate::func::shard_edge::ShardEdge;
12	use crate::traits::bit_field_slice::*;
13	use crate::utils::*;
14	use mem_dbg::*;
15
16	/// Static functions with low space overhead, fast parallel construction, and
17	/// fast queries.
18	///
19	/// Static functions map keys to values, but they do not store the keys:
20	/// querying a static function with a key outside of the original set will lead
21	/// to an arbitrary result. Another name for static functions *retrieval data
22	/// structure*. Values are retrieved using the [`get`](VFunc::get) method. On
23	/// some architectures, and with some constraints,
24	/// [`get_unaligned`](VFunc::get_unaligned) might be faster.
25	///
26	/// In exchange, static functions have a very low space overhead, and make it
27	/// possible to store the association between keys and values just in the space
28	/// required by the values (with a small overhead).
29	///
30	/// This structure is based on “[ε-Cost Sharding: Scaling Hypergraph-Based
31	/// Static Functions and Filters to Trillions of
32	/// Keys](https://arxiv.org/abs/2503.18397)”. Space overhead with respect to the
33	/// optimum depends on the [`ShardEdge`] type. The default is
34	/// [`FuseLge3Shards`], which provides 10.5% space overhead for large key sets
35	/// (above a few million keys), which grow up to 12% going towards smaller key
36	/// sets. Details on other possible [`ShardEdge`] implementations can be found
37	/// in the [`shard_edge`](crate::func::shard_edge) module documentation.
38	///
39	/// Instances of this structure are immutable; they are built using a
40	/// [`VBuilder`](crate::func::VBuilder) and can be serialized using
41	/// [ε-serde](`epserde`). Please see the documentation of
42	/// [`VBuilder`](crate::func::VBuilder) for examples.
43	///
44	/// # Generics
45	///
46	/// * `T`: The type of the keys.
47	/// * `W`: The word used to store the data, which is also the output type. It
48	/// can be any unsigned type.
49	/// * `D`: The backend storing the function data. It can be a
50	/// [`BitFieldVec<W>`](crate::bits::BitFieldVec) or a `Box<[W]>`. In the first
51	/// case, the data is stored using exactly the number of bits needed, but
52	/// access is slightly slower, while in the second case the data is stored in
53	/// a boxed slice of `W`, thus forcing the number of bits to the number of
54	/// bits of `W`, but access will be faster. Note that for most bit sizes in
55	/// the first case on some architectures you can use [unaligned
56	/// reads](VFunc::get_unaligned) to get faster queries.
57	/// * `S`: The signature type. The default is `[u64; 2]`. You can switch to
58	/// `[u64; 1]` (and possibly
59	/// [`FuseLge3NoShards`](crate::func::shard_edge::FuseLge3NoShards)) for
60	/// slightly faster construction and queries, but the construction will not
61	/// scale beyond 3.8 billion keys.
62	/// * `E`: The sharding and edge logic type. The default is [`FuseLge3Shards`].
63	/// For small sets of keys you might try
64	/// [`FuseLge3NoShards`](crate::func::shard_edge::FuseLge3NoShards), possibly
65	/// coupled with `[u64; 1]` signatures. For functions with more than a few
66	/// dozen billion keys, you might try
67	/// [`FuseLge3FullSigs`](crate::func::shard_edge::FuseLge3FullSigs).
68	#[derive(Debug, MemDbg, MemSize)]
69	#[cfg_attr(feature = "epserde", derive(epserde::Epserde))]
70	#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
71	pub struct VFunc<
72	T: ?Sized + ToSig<S>,
73	W: BinSafe + Word = usize,
74	D: BitFieldSlice<W> = Box<[W]>,
75	S: Sig = [u64; 2],
76	E: ShardEdge<S, 3> = FuseLge3Shards,
77	> {
78	pub(crate) shard_edge: E,
79	pub(crate) seed: u64,
80	pub(crate) num_keys: usize,
81	pub(crate) data: D,
82	pub(crate) _marker_t: std::marker::PhantomData<T>,
83	pub(crate) _marker_w: std::marker::PhantomData<W>,
84	pub(crate) _marker_s: std::marker::PhantomData<S>,
85	}
86
87	impl<T: ?Sized + ToSig<S>, W: BinSafe + Word, D: BitFieldSlice<W>, S: Sig, E: ShardEdge<S, 3>>
88	VFunc<T, W, D, S, E>
89	{
90	/// Returns the value associated with the given signature, or a random value
91	/// if the signature is not the signature of a key.
92	///
93	/// This method is mainly useful in the construction of compound functions.
94	#[inline]
95	pub fn get_by_sig(&self, sig: S) -> W {	23,010,100✔
96	let edge = self.shard_edge.edge(sig);	92,040,400✔
97	unsafe {
98	self.data.get_unchecked(edge[0])	115,050,500✔
99	^ self.data.get_unchecked(edge[1])	69,030,300✔
100	^ self.data.get_unchecked(edge[2])	46,020,200✔
101	}
102	}
103
104	/// Returns the value associated with the given key, or a random value if the
105	/// key is not present.
106	#[inline(always)]
107	pub fn get(&self, key: impl Borrow<T>) -> W {	12,606,060✔
108	self.get_by_sig(T::to_sig(key.borrow(), self.seed))	75,636,360✔
109	}
110
111	/// Returns the number of keys in the function.
112	pub fn len(&self) -> usize {	×
113	self.num_keys	×
114	}
115
116	/// Returns whether the function has no keys.
117	pub fn is_empty(&self) -> bool {	×
118	self.len() == 0	×
119	}
120	}
121
122	impl<T: ?Sized + ToSig<S>, W: BinSafe + Word, S: Sig, E: ShardEdge<S, 3>>
123	VFunc<T, W, BitFieldVec<W>, S, E>
124	{
125	/// Returns the value associated with the given signature, or a random value
126	/// if the signature is not the signature of a key, using [unaligned
127	/// reads](BitFieldVec::get_unaligned).
128	///
129	/// This method uses [`BitFieldVec::get_unaligned`], and has
130	/// the same constraints.
131	///
132	/// This method is mainly useful in the construction of compound functions.
133	#[inline]
134	pub fn get_by_sig_unaligned(&self, sig: S) -> W {	×
135	let edge = self.shard_edge.edge(sig);	×
136	unsafe {
137	self.data.get_unaligned_unchecked(edge[0])	×
138	^ self.data.get_unaligned_unchecked(edge[1])	×
139	^ self.data.get_unaligned_unchecked(edge[2])	×
140	}
141	}
142
143	/// Returns the value associated with the given key, or a random value if
144	/// the key is not present, using [unaligned
145	/// reads](BitFieldVec::get_unaligned).
146	///
147	/// This method uses [`BitFieldVec::get_unaligned`], and has
148	/// the same constraints.
149	#[inline(always)]
150	pub fn get_unaligned(&self, key: impl Borrow<T>) -> W {	×
151	self.get_by_sig_unaligned(T::to_sig(key.borrow(), self.seed))	×
152	}
153	}

vigna / sux-rs / 17861369619

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