fst 0.4.4

Use finite state transducers to compactly represents sets or maps of many strings (> 1 billion is possible).
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

// This module is a drop-in but inefficient replacement of the LRU registry.
// In particular, this registry will never forget a node. In other words, if
// this registry is used during construction, then you're guaranteed a minimal
// FST.
//
// This is really only meant to be used for debugging and experiments. It is
// a memory/CPU hog.
//
// One "easy" improvement here is to use an FNV hash instead of the super
// expensive SipHasher.

#![allow(dead_code)]

use std::collections::hash_map::{Entry, HashMap};

use crate::raw::build::BuilderNode;
use crate::raw::CompiledAddr;

#[derive(Debug)]
pub struct Registry {
    table: HashMap<BuilderNode, RegistryCell>,
}

#[derive(Debug)]
pub enum RegistryEntry<'a> {
    Found(CompiledAddr),
    NotFound(&'a mut RegistryCell),
    Rejected,
}

#[derive(Clone, Copy, Debug)]
pub struct RegistryCell(CompiledAddr);

impl Registry {
    pub fn new(table_size: usize, _lru_size: usize) -> Registry {
        Registry { table: HashMap::with_capacity(table_size) }
    }

    pub fn entry<'a>(&'a mut self, bnode: &BuilderNode) -> RegistryEntry<'a> {
        match self.table.entry(bnode.clone()) {
            Entry::Occupied(v) => RegistryEntry::Found(v.get().0),
            Entry::Vacant(v) => {
                RegistryEntry::NotFound(v.insert(RegistryCell(0)))
            }
        }
    }
}

impl RegistryCell {
    pub fn insert(&mut self, addr: CompiledAddr) {
        self.0 = addr;
    }
}