fst_incremental 1.0.2

A thread-safe, updatable finite state set: dynamic insertions, deletions and queries over an immutable fst::Set fronted by a compact mutation buffer with amortized rebuilds.
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

#![allow(dead_code)]

use fst_incremental::{FstConfigOptions, IncrementalFstSet};
use rand::distr::Alphanumeric;
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};

pub const KEY_LENGTH: usize = 16;
pub const BATCH: usize = 1_000;

/// Thresholds no measured operation can reach, so a rebuild never lands inside a timed section.
pub fn no_rebuild() -> FstConfigOptions {
  FstConfigOptions::new()
    .with_rebuild_adds_count(usize::MAX)
    .with_rebuild_dels_ratio(f32::MAX)
}

pub fn rng(seed: u8) -> StdRng {
  StdRng::from_seed([seed; 32])
}

pub fn keys(rng: &mut StdRng, count: usize, key_length: usize) -> Vec<Vec<u8>> {
  (0..count)
    .map(|_| rng.sample_iter(&Alphanumeric).take(key_length).collect())
    .collect()
}

/// FST bytes holding `k`, so a set at this size can be rebuilt cheaply in untimed setup.
pub fn persisted_bytes(k: &[Vec<u8>]) -> Vec<u8> {
  let set = IncrementalFstSet::new(Some(no_rebuild())).unwrap();
  set.bulk_insert(k.to_vec()).unwrap();
  set.force_rebuild().unwrap();
  set.persisted_fst_as_bytes()
}

/// A set with `bytes` persisted and an empty mutation buffer.
pub fn from_bytes(bytes: &[u8]) -> IncrementalFstSet {
  IncrementalFstSet::from_data(Some(bytes.to_vec()), Some(no_rebuild())).unwrap()
}

/// Largest power of two that indexes `len`, as a mask.
///
/// The rotation inside a timed loop must be a mask rather than a division, which means
/// the usable pool is a power of two even when the key set is not.
pub fn pool_mask(len: usize) -> usize {
  assert!(len > 0);
  if len.is_power_of_two() { len - 1 } else { (len.next_power_of_two() >> 1) - 1 }
}