cs431_homework/test/adt/
map.rs

1//! Testing utilities for map types.
2
3use core::fmt::Debug;
4use core::hash::Hash;
5use std::collections::HashMap;
6use std::collections::hash_map::Entry;
7use std::thread::scope;
8
9use crossbeam_epoch::pin;
10use rand::prelude::*;
11
12use crate::ConcurrentMap;
13use crate::test::RandGen;
14
15/// Runs many operations in a single thread and tests if it works like a map data structure using
16/// `std::collections::HashMap` as reference.
17pub fn stress_sequential<
18    K: Clone + Debug + Eq + Hash + RandGen,
19    V: Clone + Debug + Eq + RandGen,
20    M: Default + ConcurrentMap<K, V>,
21>(
22    steps: usize,
23) {
24    enum Ops {
25        LookupSome,
26        LookupNone,
27        Insert,
28        DeleteSome,
29        DeleteNone,
30    }
31    const OPS: [Ops; 5] = [
32        Ops::LookupSome,
33        Ops::LookupNone,
34        Ops::Insert,
35        Ops::DeleteSome,
36        Ops::DeleteNone,
37    ];
38
39    let mut rng = rand::rng();
40    let map = M::default();
41    let mut hashmap = HashMap::new();
42
43    for i in 0..steps {
44        let op = OPS.choose(&mut rng).unwrap();
45
46        match op {
47            Ops::LookupSome => {
48                let Some(key) = hashmap.keys().choose(&mut rng) else {
49                    continue;
50                };
51
52                println!("iteration {i}: lookup({key:?}) (existing)");
53
54                assert_eq!(map.lookup(key, &pin()), hashmap.get(key));
55            }
56            Ops::LookupNone => {
57                let key = K::rand_gen(&mut rng);
58                let hmap_res = hashmap.get(&key);
59                let non = if hmap_res.is_some() { "" } else { "non-" };
60
61                println!("iteration {i}: lookup({key:?}) ({non}existing)");
62
63                assert_eq!(map.lookup(&key, &pin()), hmap_res);
64            }
65            Ops::Insert => {
66                let key = K::rand_gen(&mut rng);
67                let value = V::rand_gen(&mut rng);
68
69                println!("iteration {i}: insert({key:?}, {value:?})");
70
71                let map_res = map.insert(key.clone(), value.clone(), &pin());
72                let hmap_res = match hashmap.entry(key) {
73                    Entry::Vacant(e) => {
74                        let _ = e.insert(value);
75                        Ok(())
76                    }
77                    _ => Err(value),
78                };
79                assert_eq!(map_res, hmap_res);
80            }
81            Ops::DeleteSome => {
82                let Some(key) = hashmap.keys().choose(&mut rng).cloned() else {
83                    continue;
84                };
85
86                println!("iteration {i}: delete({key:?}) (existing)");
87
88                assert_eq!(
89                    map.delete(&key, &pin()).cloned(),
90                    hashmap.remove(&key).ok_or(())
91                );
92            }
93            Ops::DeleteNone => {
94                let key = K::rand_gen(&mut rng);
95                let hmap_res = hashmap.remove(&key).ok_or(());
96                let non = if hmap_res.is_ok() { "" } else { "non-" };
97
98                println!("iteration {i}: delete({key:?}) ({non}existing)");
99
100                assert_eq!(map.delete(&key, &pin()).cloned(), hmap_res);
101            }
102        }
103    }
104}
105
106/// Runs random lookup operations concurrently.
107pub fn lookup_concurrent<
108    K: Clone + Debug + Eq + Hash + RandGen + Sync,
109    V: Clone + Debug + Eq + RandGen + Sync,
110    M: Default + Sync + ConcurrentMap<K, V>,
111>(
112    threads: usize,
113    steps: usize,
114) {
115    enum Ops {
116        LookupSome,
117        LookupNone,
118    }
119    const OPS: [Ops; 2] = [Ops::LookupSome, Ops::LookupNone];
120
121    let mut rng = rand::rng();
122    let map = M::default();
123    let mut hashmap = HashMap::new();
124
125    for _ in 0..steps {
126        let key = K::rand_gen(&mut rng);
127        let value = V::rand_gen(&mut rng);
128        let _unused = map.insert(key.clone(), value.clone(), &pin());
129        let _ = hashmap.entry(key).or_insert(value);
130    }
131
132    scope(|s| {
133        let mut handles = Vec::new();
134        for _ in 0..threads {
135            let handle = s.spawn(|| {
136                let mut rng = rand::rng();
137                for _ in 0..steps {
138                    let op = OPS.choose(&mut rng).unwrap();
139
140                    let key = match op {
141                        Ops::LookupSome => hashmap.keys().choose(&mut rng).unwrap().clone(),
142                        Ops::LookupNone => K::rand_gen(&mut rng),
143                    };
144                    assert_eq!(map.lookup(&key, &pin()), hashmap.get(&key));
145                }
146            });
147            handles.push(handle);
148        }
149    });
150}
151
152/// Runs random insert operations concurrently.
153pub fn insert_concurrent<
154    K: Clone + Debug + Eq + Hash + RandGen,
155    V: Clone + Debug + Eq + RandGen,
156    M: Default + Sync + ConcurrentMap<K, V>,
157>(
158    threads: usize,
159    steps: usize,
160) {
161    let map = M::default();
162
163    scope(|s| {
164        let mut handles = Vec::new();
165        for _ in 0..threads {
166            let handle = s.spawn(|| {
167                let mut rng = rand::rng();
168                for _ in 0..steps {
169                    let key = K::rand_gen(&mut rng);
170                    let value = V::rand_gen(&mut rng);
171                    if map.insert(key.clone(), value.clone(), &pin()).is_ok() {
172                        assert_eq!(map.lookup(&key, &pin()).unwrap(), &value);
173                    }
174                }
175            });
176            handles.push(handle);
177        }
178    });
179}
180
181enum Ops {
182    Lookup,
183    Insert,
184    Delete,
185}
186const OPS: [Ops; 3] = [Ops::Lookup, Ops::Insert, Ops::Delete];
187
188#[derive(Clone)]
189/// Successful operations are logged as `Some`. Failed operations are `None`.
190///
191/// We currently only make use of the `Some` variant for `result`.
192enum Log<K, V> {
193    Lookup { key: K, result: Option<V> },
194    Insert { key: K, result: Option<V> },
195    Delete { key: K, result: Option<V> },
196}
197
198impl<K, V> Log<K, V> {
199    fn key(&self) -> &K {
200        match self {
201            Self::Lookup { key, .. } | Self::Insert { key, .. } | Self::Delete { key, .. } => key,
202        }
203    }
204}
205
206/// Randomly runs many operations concurrently.
207pub fn stress_concurrent<
208    K: Debug + Eq + RandGen,
209    V: Debug + Eq + RandGen,
210    M: Default + Sync + ConcurrentMap<K, V>,
211>(
212    threads: usize,
213    steps: usize,
214) {
215    let map = M::default();
216
217    scope(|s| {
218        let mut handles = Vec::new();
219        for _ in 0..threads {
220            let handle = s.spawn(|| {
221                let mut rng = rand::rng();
222                for _ in 0..steps {
223                    let op = OPS.choose(&mut rng).unwrap();
224                    let key = K::rand_gen(&mut rng);
225
226                    match op {
227                        Ops::Lookup => {
228                            let _ = map.lookup(&key, &pin());
229                        }
230                        Ops::Insert => {
231                            let _ = map.insert(key, V::rand_gen(&mut rng), &pin());
232                        }
233                        Ops::Delete => {
234                            let _ = map.delete(&key, &pin());
235                        }
236                    }
237                }
238            });
239            handles.push(handle);
240        }
241    });
242}
243
244fn assert_logs_consistent<K: Debug + Eq + Hash, V: Debug + Eq + Hash>(logs: &[Log<K, V>]) {
245    let mut per_key_logs = HashMap::new();
246    for l in logs {
247        per_key_logs.entry(l.key()).or_insert(vec![]).push(l);
248    }
249
250    for (k, logs) in per_key_logs {
251        let mut inserts = HashMap::new();
252        let mut deletes = HashMap::new();
253
254        for l in logs.iter() {
255            match l {
256                Log::Insert {
257                    result: Some(v), ..
258                } => *inserts.entry(v).or_insert(0) += 1,
259                Log::Delete {
260                    result: Some(v), ..
261                } => *deletes.entry(v).or_insert(0) += 1,
262                _ => (),
263            }
264        }
265
266        for l in logs {
267            if let Log::Lookup {
268                result: Some(v), ..
269            } = l
270            {
271                assert!(
272                    inserts.contains_key(v),
273                    "key: {k:?}, value: {v:?}, lookup success but not inserted."
274                );
275            }
276        }
277
278        for (v, d_count) in deletes {
279            let i_count = inserts.get(v).copied().unwrap_or(0);
280            assert!(
281                i_count >= d_count,
282                "key: {k:?}, value: {v:?}, inserted {i_count} times but deleted {d_count} times."
283            );
284        }
285    }
286}
287
288/// Randomly runs many operations concurrently and logs the operations & results per thread. Then
289/// checks the consistency of the log. For example, if the key `k` was successfully deleted twice,
290/// then `k` must have been inserted at least twice.
291pub fn log_concurrent<
292    K: Clone + Debug + Eq + Hash + RandGen + Send,
293    V: Clone + Debug + Eq + Hash + RandGen + Send,
294    M: Default + Sync + ConcurrentMap<K, V>,
295>(
296    threads: usize,
297    steps: usize,
298) {
299    let map = M::default();
300
301    let logs = scope(|s| {
302        let mut handles = Vec::new();
303
304        for _ in 0..threads {
305            let handle = s.spawn(|| {
306                let mut rng = rand::rng();
307                let mut logs = Vec::new();
308
309                for _ in 0..steps {
310                    let op = OPS.choose(&mut rng).unwrap();
311                    let key = K::rand_gen(&mut rng);
312
313                    match op {
314                        Ops::Lookup => {
315                            let result = map.lookup(&key, &pin()).cloned();
316                            logs.push(Log::Lookup { key, result });
317                        }
318                        Ops::Insert => {
319                            let value = V::rand_gen(&mut rng);
320                            let result = map
321                                .insert(key.clone(), value.clone(), &pin())
322                                .ok()
323                                .map(|_| value);
324                            logs.push(Log::Insert { key, result });
325                        }
326                        Ops::Delete => {
327                            let result = map.delete(&key, &pin()).cloned().ok();
328                            logs.push(Log::Delete { key, result });
329                        }
330                    }
331                }
332                logs
333            });
334            handles.push(handle);
335        }
336        handles
337            .into_iter()
338            .flat_map(|h| h.join().unwrap())
339            .collect::<Box<[_]>>()
340    });
341
342    assert_logs_consistent(&logs);
343}
cs431_homework/test/adt/map.rs

cs431_homework/test/adt/
map.rs
