23492656594

Committed 24 Mar 2026 01:44PM UTC coverage: 76.733% (+0.9%) from 75.877%

Build # 23492656594

Build Type

push

github

Committed by

vigna

Commit Message

fmt

Coverage Stats

5824 of 7590 relevant lines covered (76.73%)

104003994.68 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::Word;
use crate::utils::*;
use mem_dbg::*;
use value_traits::slices::SliceByValue;

/// 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 is *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](https://crates.io/crates/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<Box<[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, W = usize, D = Box<[W]>, S = [u64; 2], E = 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: Word + BinSafe,
    D: SliceByValue<Value = 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);
        // SAFETY: The ShardEdge implementation guarantees that all indices
        // returned by `edge()` are within bounds of `self.data`. This invariant
        // is established during construction by VBuilder, which ensures the
        // data array is sized according to the ShardEdge's `num_vertices()`
        unsafe {
            self.data.get_value_unchecked(edge[0])
                ^ self.data.get_value_unchecked(edge[1])
                ^ self.data.get_value_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 const fn len(&self) -> usize {
        self.num_keys
    }

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

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

vigna / sux-rs / 23492656594

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