diff options
author | Joel Galenson <jgalenson@google.com> | 2020-10-12 16:02:26 -0700 |
---|---|---|
committer | Joel Galenson <jgalenson@google.com> | 2020-10-12 16:02:26 -0700 |
commit | 2370d12326515c0feed0596971e0f2146127574e (patch) | |
tree | 90cfb9e167dedd07055cec8c34b2f3995528c7d1 /tests | |
parent | 3e2f28bf21e1d4d6c2c8e8dfcae2bed801271a47 (diff) | |
download | weak-table-2370d12326515c0feed0596971e0f2146127574e.tar.gz |
Import weak-table-0.3.0
Test: None
Change-Id: Idcf231392e451e1de74377dce6804c91fd8ac868
Diffstat (limited to 'tests')
-rw-r--r-- | tests/symbols.rs | 54 | ||||
-rw-r--r-- | tests/weak_key_hash_map.rs | 163 |
2 files changed, 217 insertions, 0 deletions
diff --git a/tests/symbols.rs b/tests/symbols.rs new file mode 100644 index 0000000..4f01b0d --- /dev/null +++ b/tests/symbols.rs @@ -0,0 +1,54 @@ +extern crate weak_table; + +use weak_table::WeakHashSet; +use std::ops::Deref; +use std::rc::{Rc, Weak}; + +#[derive(Clone, Debug)] +pub struct Symbol(Rc<str>); + +impl PartialEq for Symbol { + fn eq(&self, other: &Symbol) -> bool { + Rc::ptr_eq(&self.0, &other.0) + } +} + +impl Eq for Symbol {} + +impl Deref for Symbol { + type Target = str; + fn deref(&self) -> &str { + &self.0 + } +} + +#[derive(Debug, Default)] +pub struct SymbolTable(WeakHashSet<Weak<str>>); + +impl SymbolTable { + pub fn new() -> Self { + Self::default() + } + + pub fn intern(&mut self, name: &str) -> Symbol { + if let Some(rc) = self.0.get(name) { + Symbol(rc) + } else { + let rc = Rc::<str>::from(name); + self.0.insert(Rc::clone(&rc)); + Symbol(rc) + } + } +} + +#[test] +fn interning() { + let mut tab = SymbolTable::new(); + + let a0 = tab.intern("a"); + let a1 = tab.intern("a"); + let b = tab.intern("b"); + + assert_eq!(a0, a1); + assert_ne!(a0, b); +} diff --git a/tests/weak_key_hash_map.rs b/tests/weak_key_hash_map.rs new file mode 100644 index 0000000..fe18890 --- /dev/null +++ b/tests/weak_key_hash_map.rs @@ -0,0 +1,163 @@ +use std::collections::HashMap; +use std::fmt::Debug; +use std::hash::Hash; +use std::rc::{Rc, Weak}; + +use rand::Rng; +use quickcheck::{Arbitrary, Gen, quickcheck}; + +use weak_table::WeakKeyHashMap; + +use self::Cmd::*; + +fn test_script<K, V>(script: &Script<K, V>) -> bool + where K: Clone + Debug + Eq + Hash, + V: Clone + Debug + Eq +{ + let mut tester = Tester::with_capacity(4); + tester.execute_script(script); + tester.check() +} + +quickcheck! { + fn prop_u8_u8(script: Script<u8, u8>) -> bool { + test_script(&script) + } + + fn prop_string_usize(script: Script<String, usize>) -> bool { + test_script(&script) + } +} + +#[derive(Clone, Debug)] +pub enum Cmd<K, V> +{ + Insert(K, V), + Reinsert(usize, V), + RemoveInserted(usize), + RemoveOther(K), + ForgetInserted(usize), +} + +#[derive(Clone, Debug)] +pub struct Script<K, V>(Vec<Cmd<K, V>>); + +#[derive(Clone, Debug)] +pub struct Tester<K: Hash + Eq, V> { + weak: WeakKeyHashMap<Weak<K>, V>, + strong: HashMap<Rc<K>, V>, + log: Vec<K>, +} + +impl<K, V> Tester<K, V> + where K: Hash + Eq + Clone + Debug, + V: Eq + Clone + Debug +{ + pub fn new() -> Self { + Tester::with_capacity(8) + } + + pub fn with_capacity(capacity: usize) -> Self { + Tester { + weak: WeakKeyHashMap::with_capacity(capacity), + strong: HashMap::new(), + log: Vec::new(), + } + } + + pub fn check(&self) -> bool { + let copy = self.weak.iter().map(|(k, v)| (k, v.clone())).collect(); + if self.strong == copy { +// eprintln!("Tester::check: succeeded: {:?}", self.weak); + true + } else { + eprintln!("Tester::check: failed: {:?} ≠ {:?}", self.strong, copy); + false + } + } + + pub fn execute_script(&mut self, script: &Script<K, V>) { +// eprintln!("\n*** Starting script ***"); + for cmd in &script.0 { + self.execute_command(cmd); + } + } + + pub fn execute_command(&mut self, cmd: &Cmd<K, V>) { +// eprintln!("Executing command: {:?}", cmd); + match *cmd { + Insert(ref k, ref v) => self.insert(k, v, true), + Reinsert(index, ref v) => self.reinsert(index, v), + RemoveInserted(index) => self.remove_inserted(index), + RemoveOther(ref k) => self.remove_other(k), + ForgetInserted(index) => self.forget_inserted(index), + } +// eprintln!("Table state: {:?}", self.weak); + } + + pub fn insert(&mut self, key: &K, value: &V, log: bool) { + let key_ptr = Rc::new(key.clone()); + self.weak.insert(key_ptr.clone(), value.clone()); + self.strong.remove(key); + self.strong.insert(key_ptr, value.clone()); + if log { self.log.push(key.clone()); } + } + + pub fn reinsert(&mut self, index: usize, value: &V) { + if let Some(key) = self.nth_key_mod_len(index) { + self.insert(&key, value, false); + } + } + + pub fn remove_inserted(&mut self, index: usize) { + if let Some(key) = self.nth_key_mod_len(index) { + self.strong.remove(&key); + self.weak.remove(&key); + } + } + + pub fn remove_other(&mut self, key: &K) { + self.strong.remove(key); + self.weak.remove(key); + } + + pub fn forget_inserted(&mut self, index: usize) { + if let Some(key) = self.nth_key_mod_len(index) { + self.strong.remove(&key); + } + } + + fn nth_key_mod_len(&self, n: usize) -> Option<K> + { + if self.log.is_empty() { + None + } else { + Some(self.log[n % self.log.len()].clone()) + } + } +} + +impl<K: Arbitrary, V: Arbitrary> Arbitrary for Cmd<K, V> { + fn arbitrary<G: Gen>(g: &mut G) -> Self { + let choice = g.gen_range(0, 100); + + match choice { + 00..=39 => Insert(K::arbitrary(g), V::arbitrary(g)), + 40..=49 => Reinsert(usize::arbitrary(g), V::arbitrary(g)), + 50..=69 => RemoveInserted(usize::arbitrary(g)), + 70..=79 => RemoveOther(K::arbitrary(g)), + 80..=99 => ForgetInserted(usize::arbitrary(g)), + _ => unreachable!(), + } + } +} + +impl<K: Arbitrary, V: Arbitrary> Arbitrary for Script<K, V> { + fn arbitrary<G: Gen>(g: &mut G) -> Self { + Script(Vec::<Cmd<K, V>>::arbitrary(g)) + } + + fn shrink(&self) -> Box<dyn Iterator<Item=Self>> { + Box::new(self.0.shrink().map(|v| Script(v))) + } +} |