crdt_richtext/
small_set.rs

1use fxhash::FxHashSet;
2const STACK_LEN: usize = 4;
3
4/// When the set is small it only live in the stack memory.
5///
6/// It's used to store the difference of the annotation, which is
7/// usually small or empty. It uses positive(or negative) values to represent new
8/// insertions(or deletion). 0 is illegal value.
9///
10/// A absolute value can only exist once in the set.
11/// i.e. if 3 is in the set, -3 must not be in the set.
12///
13/// If 3 is in the set and user insert -3, the insertion will not happen,
14/// instead the 3 will be removed from the set.
15#[derive(Debug, Clone)]
16pub enum SmallSetI32 {
17    Stack(([i32; STACK_LEN], u8)),
18    Heap(FxHashSet<i32>),
19}
20
21impl Default for SmallSetI32 {
22    fn default() -> Self {
23        Self::new()
24    }
25}
26
27impl SmallSetI32 {
28    const EMPTY_VALUE: i32 = 0;
29    pub(crate) fn new() -> Self {
30        SmallSetI32::Stack(([Self::EMPTY_VALUE; STACK_LEN], 0))
31    }
32
33    pub(crate) fn insert(&mut self, value: i32) {
34        assert!(value != 0);
35        if self.contains(-value) {
36            self.remove(-value);
37            return;
38        }
39
40        match self {
41            SmallSetI32::Stack((stack, size)) => {
42                for entry in stack.iter() {
43                    if *entry == value {
44                        // already exists
45                        return;
46                    }
47                }
48
49                for entry in stack.iter_mut() {
50                    if *entry == Self::EMPTY_VALUE {
51                        *entry = value;
52                        *size += 1;
53                        return;
54                    }
55                }
56
57                let mut set =
58                    FxHashSet::with_capacity_and_hasher(STACK_LEN * 2, Default::default());
59
60                for &v in stack.iter() {
61                    // we already know it's non empty
62                    set.insert(v);
63                }
64                set.insert(value);
65                *self = SmallSetI32::Heap(set);
66            }
67            SmallSetI32::Heap(set) => {
68                set.insert(value);
69            }
70        }
71    }
72
73    pub(crate) fn contains(&self, value: i32) -> bool {
74        if value == 0 {
75            return false;
76        }
77
78        match self {
79            SmallSetI32::Stack((stack, size)) => {
80                if *size == 0 {
81                    return false;
82                }
83
84                for entry in stack.iter() {
85                    if *entry == value {
86                        return true;
87                    }
88                }
89
90                false
91            }
92            SmallSetI32::Heap(set) => set.contains(&value),
93        }
94    }
95
96    pub(crate) fn remove(&mut self, value: i32) {
97        match self {
98            SmallSetI32::Stack((stack, size)) => {
99                if *size == 0 {
100                    return;
101                }
102
103                for entry in stack.iter_mut() {
104                    if *entry == value {
105                        *entry = Self::EMPTY_VALUE;
106                        *size -= 1;
107                    }
108                }
109            }
110            SmallSetI32::Heap(set) => {
111                set.remove(&value);
112            }
113        }
114    }
115
116    pub(crate) fn iter(&self) -> SmallSetIter {
117        match self {
118            SmallSetI32::Stack((stack, _)) => SmallSetIter::Stack(stack.iter()),
119            SmallSetI32::Heap(set) => SmallSetIter::Heap(set.iter()),
120        }
121    }
122
123    pub(crate) fn len(&self) -> usize {
124        match self {
125            SmallSetI32::Stack((_, size)) => *size as usize,
126            SmallSetI32::Heap(set) => set.len(),
127        }
128    }
129
130    pub(crate) fn is_empty(&self) -> bool {
131        self.len() == 0
132    }
133}
134
135pub(crate) enum SmallSetIter<'a> {
136    Stack(std::slice::Iter<'a, i32>),
137    Heap(std::collections::hash_set::Iter<'a, i32>),
138}
139
140impl<'a> Iterator for SmallSetIter<'a> {
141    type Item = i32;
142
143    fn next(&mut self) -> Option<Self::Item> {
144        match self {
145            SmallSetIter::Stack(iter) => {
146                let mut ans = iter.next();
147                while ans == Some(&SmallSetI32::EMPTY_VALUE) {
148                    ans = iter.next();
149                }
150                ans.copied()
151            }
152            SmallSetIter::Heap(iter) => iter.next().copied(),
153        }
154    }
155}
156
157#[cfg(test)]
158mod test {
159    use super::SmallSetI32;
160
161    #[test]
162    fn test() {
163        let mut set = SmallSetI32::new();
164        set.insert(1);
165        set.insert(2);
166        set.insert(2);
167        set.insert(2);
168        set.insert(1);
169        assert_eq!(set.len(), 2);
170        assert!(set.contains(2));
171        assert!(set.contains(1));
172        assert!(!set.contains(0));
173        assert!(!set.contains(-2));
174        set.remove(2);
175        assert!(!set.contains(2));
176        assert!(set.len() == 1);
177    }
178
179    #[test]
180    fn smallset_size() {
181        assert_eq!(32, std::mem::size_of::<SmallSetI32>());
182    }
183}
crdt_richtext/small_set.rs

crdt_richtext/
small_set.rs
