sux 0.14.0

A pure Rust implementation of succinct and compressed data structures
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

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

//! Static functions.
//!
//! 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.
//!
//! In exchange, static functions make it possible to store the association
//! between keys and values just in the space required by the values, plus
//! a small overhead.
//!
//! - [`VFunc`] is a generic static function.
//!
//! - [`VFunc2`] is a two-step static function that has better space usage
//!   in case the distribution of the output values is skewed.
//!
//! - [`LcpMmphfInt`]/[`LcpMmphf`] are *monotone minimal perfect hash
//!   functions*—specialized static functions mapping keys in lexicographical
//!   order to their lexicographical rank. See [`LcpMmphfStr`] and
//!   [`LcpMmphfSliceU8`] for common instantiations.
//!
//! - [`Lcp2MmphfInt`]/[`Lcp2Mmphf`] are versions of
//!   [`LcpMmphfInt`]/[`LcpMmphf`] that use a [`VFunc2`]-like technique to reduce
//!   space usage, at the cost of slightly slower queries.
//!
//! - [`SignedFunc`] wraps any of the above with per-key verification hashes,
//!   returning `None` for keys outside the original set. Use `Box<[W]>` for
//!   full-width hashes or [`BitFieldVec`] for sub-word-width hashes. Use
//!   concrete types like `SignedFunc<LcpMmphfStr, Box<[u64]>>`.
//!
//! Most structures implement the [`TryIntoUnaligned`] trait, allowing them
//! to be converted into (usually faster) structures using unaligned access.
//!
//! [`BitFieldVec`]: crate::bits::BitFieldVec
//! [`TryIntoUnaligned`]: crate::traits::TryIntoUnaligned
//!
//! All constructors follow the pattern `try_new(keys, …, pl)` for default
//! settings, and `try_new_with_builder(keys, …, builder, pl)` to configure
//! the [`VBuilder`] (offline mode, thread count, sharding overhead, seed).

mod vfunc;
pub use vfunc::*;

pub mod vfunc2;
pub use vfunc2::*;

#[cfg(feature = "rayon")]
mod vbuilder;
#[cfg(feature = "rayon")]
pub use vbuilder::*;

pub mod lcp_mmphf;
pub use lcp_mmphf::*;

pub mod lcp2_mmphf;
pub use lcp2_mmphf::*;

pub mod signed;
pub use signed::*;

pub mod shard_edge;

/// Avalanches bits using the finalization step of Austin Appleby's
/// [MurmurHash3].
///
/// [MurmurHash3]: http://code.google.com/p/smhasher/
pub(crate) const fn mix64(mut k: u64) -> u64 {
    k ^= k >> 33;
    k = k.overflowing_mul(0xff51_afd7_ed55_8ccd).0;
    k ^= k >> 33;
    k = k.overflowing_mul(0xc4ce_b9fe_1a85_ec53).0;
    k ^= k >> 33;
    k
}