mvcc_cell 0.1.2

Software-transactional memory for Rust
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

use std::collections::{BTreeMap,BTreeSet};
use std::fmt::Debug;
use parking_lot::Mutex;

#[derive(Debug)]
pub struct Histogram<K>(BTreeMap<K,usize>);

impl<K> Default for Histogram<K> {
    fn default()->Self { Histogram(BTreeMap::new()) }
}

#[allow(dead_code)]
impl<K:Ord + Debug + Copy> Histogram<K> {
    pub fn new()->Self { Self::default() }

    pub fn inc(&mut self, k:K) {
        *self.0.entry(k).or_default() += 1;
    }

    pub fn dec(&mut self, k:K) {
        use std::collections::btree_map::Entry::*;
        let Occupied(mut slot) = self.0.entry(k) else { panic!("Underflow, k={k:?}") };
        *slot.get_mut() -= 1;
        if *slot.get() == 0 { slot.remove(); }
    }

    pub fn iter(&self)->impl '_ + Iterator<Item=(K,usize)> {
        self.0.iter().map(|(&k,&v)| (k,v))
    }

    pub fn keys(&self)->impl '_ + Iterator<Item=K> {
        self.0.keys().copied()
    }
}

#[derive(Debug)]
pub struct TokenHist<K>(Mutex<Histogram<K>>);

impl<K> Default for TokenHist<K> {
    fn default()->Self { TokenHist(Mutex::default()) }
}

impl<K: Ord+Debug+Copy> TokenHist<K> {
    #[allow(dead_code)]
    pub fn new()->Self { Self::default() }

    pub fn make_token(&self, k:K)->Token<'_,K> {
        self.0.lock().inc(k);
        Token { k, hist: self }
    }

    #[allow(dead_code)]
    pub fn counts(&self)->BTreeMap<K,usize> {
        self.0.lock().0.clone()
    }

    pub fn keys(&self)->BTreeSet<K> {
        self.0.lock().keys().collect()
    }
}

pub struct Token<'hist, K:Ord+Debug+Copy> {
    hist: &'hist TokenHist<K>,
    k: K
}

impl<K: Ord+Debug+Copy> std::ops::Deref for Token<'_,K> {
    type Target=K;
    fn deref(&self)->&K { &self.k }
}

impl<K: Ord+Debug+Copy> Drop for Token<'_,K> {
    fn drop(&mut self) {
        self.hist.0.lock().dec(self.k);
    }
}

#[cfg(test)]
mod tests {
    use proptest::prelude::*;
    use super::*;

    proptest! {
        #[test] fn test_histogram(items in prop::collection::vec(0_usize..=0xF, 0..=0xFFF)) {
            let mut h: Histogram<usize> = Histogram::new();

            for &it in items.iter() { h.inc(it); }

            assert_eq!(h.iter().map(|(_,v)| v).sum::<usize>(), items.len());
            for (k,v) in h.iter() {
                assert_eq!(v, items.iter().filter(|&&it| it == k).count());
            }

            for &it in items.iter() { h.dec(it); }

            assert!(h.keys().next().is_none());
        }

        #[test] fn test_token_hist(items in prop::collection::vec(0_usize..=0xF, 0..=0xFFF)) {
            let h: TokenHist<usize> = TokenHist::new();
            let mut tokens: Vec<Token<'_, usize>> = vec![];

            for &it in items.iter() { tokens.push(h.make_token(it)); }

            assert_eq!(h.counts().into_iter().map(|(_,v)| v).sum::<usize>(), items.len());
            for (k,v) in h.counts() {
                assert_eq!(v, items.iter().filter(|&&it| it == k).count());
            }

            tokens.truncate(0);

            assert_eq!(h.keys().len(), 0);
        }
    }
}