From e7e665da7f7d6a111446b34a673d443214b1aac1 Mon Sep 17 00:00:00 2001 From: Determinant Date: Wed, 10 Jun 2020 20:16:14 -0400 Subject: ... --- Cargo.lock | 18 +++++- Cargo.toml | 1 + tests/common/mod.rs | 156 ++++++++++++++++++++++++++++++++++++++++++++++++++-- 3 files changed, 168 insertions(+), 7 deletions(-) diff --git a/Cargo.lock b/Cargo.lock index 34e5a1d..0ba1546 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -24,6 +24,12 @@ version = "0.1.7" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "1d49d90015b3c36167a20fe2810c5cd875ad504b39cff3d4eae7977e6b7c1cb2" +[[package]] +name = "autocfg" +version = "1.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f8aac770f1885fd7e387acedd76065302551364496e46b3dd00860b2f8359b9d" + [[package]] name = "bitflags" version = "1.2.1" @@ -94,6 +100,7 @@ version = "0.1.0" dependencies = [ "crc", "hex", + "indexmap", "libc", "lru", "nix", @@ -109,7 +116,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "8e6073d0ca812575946eb5f35ff68dbe519907b25c42530389ff946dc84c6ead" dependencies = [ "ahash", - "autocfg", + "autocfg 0.1.7", ] [[package]] @@ -118,6 +125,15 @@ version = "0.4.2" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "644f9158b2f133fd50f5fb3242878846d9eb792e445c893805ff0e3824006e35" +[[package]] +name = "indexmap" +version = "1.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c398b2b113b55809ceb9ee3e753fcbac793f1956663f3c36549c1346015c2afe" +dependencies = [ + "autocfg 1.0.0", +] + [[package]] name = "lazy_static" version = "1.4.0" diff --git a/Cargo.toml b/Cargo.toml index 1a60577..7eae306 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -17,6 +17,7 @@ hex = "0.4.2" libc = "0.2.44" nix = "0.17.0" rand = "0.7.3" +indexmap = "1.4.0" [lib] name = "growthring" diff --git a/tests/common/mod.rs b/tests/common/mod.rs index 2fd7bbb..209e8af 100644 --- a/tests/common/mod.rs +++ b/tests/common/mod.rs @@ -3,11 +3,14 @@ extern crate growthring; use growthring::wal::{WALFile, WALStore, WALPos, WALBytes}; -use std::collections::{HashMap, hash_map::Entry}; +use indexmap::{IndexMap, map::Entry}; +use rand::Rng; +use std::collections::{HashMap, hash_map}; use std::cell::RefCell; use std::rc::Rc; +use std::convert::TryInto; +use std::collections::VecDeque; -/* thread_local! { //pub static RNG: RefCell = RefCell::new(::from_seed([0; 32])); pub static RNG: RefCell = RefCell::new(rand::thread_rng()); @@ -16,10 +19,9 @@ thread_local! { pub fn gen_rand_letters(i: usize) -> String { //let mut rng = rand::thread_rng(); RNG.with(|rng| { - (0..i).map(|_| (rng.borrow_mut().gen::() % 26 + 'a' as u8) as char).collect() + (0..i).map(|_| (rng.borrow_mut().gen_range(0, 26) + 'a' as u8) as char).collect() }) } -*/ struct FileContentEmul(RefCell>); @@ -103,11 +105,11 @@ impl<'a, G: 'static + FailGen> WALStore for WALStoreEmul<'a, G> { fn open_file(&mut self, filename: &str, touch: bool) -> Result, ()> { if self.fgen.next_fail() { return Err(()) } match self.state.files.entry(filename.to_string()) { - Entry::Occupied(e) => Ok(Box::new(WALFileEmul { + hash_map::Entry::Occupied(e) => Ok(Box::new(WALFileEmul { file: e.get().clone(), fgen: self.fgen.clone() })), - Entry::Vacant(e) => if touch { + hash_map::Entry::Vacant(e) => if touch { Ok(Box::new(WALFileEmul { file: e.insert(Rc::new(FileContentEmul::new())).clone(), fgen: self.fgen.clone() @@ -166,3 +168,145 @@ pub struct ZeroFailGen; impl FailGen for ZeroFailGen { fn next_fail(&self) -> bool { false } } + +/// An ordered list of intervals: `(begin, end, color)*`. +pub struct PaintStrokes(Vec<(u32, u32, u32)>); + +impl PaintStrokes { + pub fn new() -> Self { PaintStrokes(Vec::new()) } + pub fn to_bytes(&self) -> WALBytes { + let mut res: Vec = Vec::new(); + let is = std::mem::size_of::(); + let len = self.0.len() as u32; + res.resize(is * (1 + 3 * self.0.len()), 0); + let mut rs = &mut res[..]; + &mut rs[..is].copy_from_slice(&len.to_le_bytes()); + rs = &mut rs[is..]; + for (s, e, c) in self.0.iter() { + &mut rs[..is].copy_from_slice(&s.to_le_bytes()); + &mut rs[is..is * 2].copy_from_slice(&e.to_le_bytes()); + &mut rs[is * 2..is * 3].copy_from_slice(&c.to_le_bytes()); + rs = &mut rs[is * 3..]; + } + res.into_boxed_slice() + } + + pub fn from_bytes(raw: &[u8]) -> Self { + assert!(raw.len() > 4); + assert!(raw.len() & 3 == 0); + let is = std::mem::size_of::(); + let (len_raw, mut rest) = raw.split_at(is); + let len = u32::from_le_bytes(len_raw.try_into().unwrap()); + let mut res = Vec::new(); + for _ in 0..len { + let (s_raw, rest1) = rest.split_at(is); + let (e_raw, rest2) = rest1.split_at(is); + let (c_raw, rest3) = rest2.split_at(is); + res.push((u32::from_le_bytes(s_raw.try_into().unwrap()), + u32::from_le_bytes(e_raw.try_into().unwrap()), + u32::from_le_bytes(c_raw.try_into().unwrap()))); + rest = rest3 + } + PaintStrokes(res) + } + + pub fn stroke(&mut self, start: u32, end: u32, color: u32) { + self.0.push((start, end, color)) + } + + pub fn into_vec(self) -> Vec<(u32, u32, u32)> { self.0 } +} + +#[test] +fn test_paint_strokes() { + let mut p = PaintStrokes::new(); + for i in 0..3 { + p.stroke(i, i + 3, i + 10) + } + let pr = p.to_bytes(); + for ((s, e, c), i) in PaintStrokes::from_bytes(&pr) + .into_vec().into_iter().zip(0..) { + assert_eq!(s, i); + assert_eq!(e, i + 3); + assert_eq!(c, i + 10); + } +} + +type CanvasTrace = Vec<(u32, u32)>; + +pub struct Canvas { + queue: IndexMap>, + canvas: Box<[u32]> +} + +impl Canvas { + pub fn new(size: usize) -> Self { + let mut canvas = Vec::new(); + // fill the backgroudn color 0 + canvas.resize(size, 0); + let canvas = canvas.into_boxed_slice(); + Canvas { + queue: IndexMap::new(), + canvas + } + } + + fn get_queued(&mut self, pos: u32) -> &mut VecDeque { + match self.queue.entry(pos) { + Entry::Occupied(e) => e.into_mut(), + Entry::Vacant(e) => e.insert(VecDeque::new()) + } + } + + pub fn prepaint(&mut self, strokes: &PaintStrokes) { + for (s, e, c) in strokes.0.iter() { + for i in *s..*e { + self.get_queued(i).push_back(*c) + } + } + } + + // TODO: allow customized scheduler + pub fn rand_paint(&mut self, rng: &mut R) -> u32 { + println!("{}", self.queue.len()); + let idx = rng.gen_range(0, self.queue.len()); + let (pos, _) = self.queue.get_index_mut(idx).unwrap(); + let pos = *pos; + self.paint(pos); + pos + } + + pub fn paint(&mut self, pos: u32) { + let q = self.queue.get_mut(&pos).unwrap(); + self.canvas[pos as usize] = q.pop_front().unwrap(); + if q.is_empty() { self.queue.remove(&pos); } + } + + pub fn is_same(&self, other: &Canvas) -> bool { + self.canvas.cmp(&other.canvas) == std::cmp::Ordering::Equal + } +} + +#[test] +fn test_canvas() { + let mut canvas1 = Canvas::new(10); + let mut canvas2 = Canvas::new(10); + let canvas3 = Canvas::new(11); + let mut s1 = PaintStrokes::new(); + s1.stroke(0, 1, 1); + let mut s2 = PaintStrokes::new(); + s2.stroke(1, 2, 2); + assert!(canvas1.is_same(&canvas2)); + assert!(!canvas2.is_same(&canvas3)); + canvas1.prepaint(&s1); + canvas1.prepaint(&s2); + canvas2.prepaint(&s1); + canvas2.prepaint(&s2); + assert!(canvas1.is_same(&canvas2)); + RNG.with(|rng| canvas1.rand_paint(&mut *rng.borrow_mut())); + assert!(!canvas1.is_same(&canvas2)); + RNG.with(|rng| canvas1.rand_paint(&mut *rng.borrow_mut())); + RNG.with(|rng| canvas2.rand_paint(&mut *rng.borrow_mut())); + RNG.with(|rng| canvas2.rand_paint(&mut *rng.borrow_mut())); + assert!(canvas1.is_same(&canvas2)); +} -- cgit v1.2.3-70-g09d2