WIP optimize scroll in region

This intends to optimize the case where the top of the scrolling region
is the top of the screen. In theory, scrolling in this case can be
optimized to shifting the start/end of the visible region, and then
rearranging any lines that were not supposed to be scrolled (at the
bottom of the region). However, this didn't produce quite the speedup I
expected.

1 files changed, 129 insertions, 0 deletions

diff --git a/src/grid/storage.rs b/src/grid/storage.rs
new file mode 100644
index 00000000..f5c2d87e
--- /dev/null
+++ b/src/grid/storage.rs
@@ -0,0 +1,129 @@
+/// Wrapper around Vec which supports fast indexing and rotation
+///
+/// The rotation implemented by grid::Storage is a simple integer addition.
+/// Compare with standard library rotation which requires rearranging items in
+/// memory.
+///
+/// As a consequence, the indexing operators need to be reimplemented for this
+/// type to account for the 0th element not always being at the start of the
+/// allocation.
+///
+/// Because certain Vec operations are no longer valid on this type, no Deref
+/// implementation is provided. Anything from Vec that should be exposed must be
+/// done so manually.
+use std::ops::{Index, IndexMut};
+
+#[derive(Clone, Debug, Deserialize, Serialize, Eq, PartialEq)]
+pub struct Storage<T> {
+    inner: Vec<T>,
+    zero: usize,
+}
+
+impl<T> Storage<T> {
+    #[inline]
+    pub fn with_capacity(cap: usize) -> Storage<T> {
+        Storage {
+            inner: Vec::with_capacity(cap),
+            zero: 0
+        }
+    }
+
+    #[inline]
+    pub fn push(&mut self, item: T) {
+        self.inner.push(item)
+    }
+
+    #[inline]
+    pub fn pop(&mut self) -> Option<T> {
+        self.inner.pop()
+    }
+
+    #[inline]
+    pub fn len(&self) -> usize {
+        self.inner.len()
+    }
+
+    /// Compute actual index in underlying storage given the requested index.
+    #[inline]
+    fn compute_index(&self, requested: usize) -> usize {
+        (requested + self.zero) % self.len()
+    }
+
+    pub fn swap(&mut self, a: usize, b: usize) {
+        let a = self.compute_index(a);
+        let b = self.compute_index(b);
+        self.inner.swap(a, b);
+    }
+
+    pub fn iter(&self) -> Iter<T> {
+        Iter { storage: self, index: 0 }
+    }
+
+    pub fn iter_mut(&mut self) -> IterMut<T> {
+        IterMut { storage: self, index: 0 }
+    }
+
+    pub fn rotate(&mut self, count: isize) {
+        let len = self.len();
+        assert!(count.abs() as usize <= len);
+        self.zero += (count + len as isize) as usize % len;
+    }
+}
+
+impl<T> Index<usize> for Storage<T> {
+    type Output = T;
+    #[inline]
+    fn index(&self, index: usize) -> &T {
+        let index = self.compute_index(index); // borrowck
+        &self.inner[index]
+    }
+}
+
+impl<T> IndexMut<usize> for Storage<T> {
+    #[inline]
+    fn index_mut(&mut self, index: usize) -> &mut T {
+        let index = self.compute_index(index); // borrowck
+        &mut self.inner[index]
+    }
+}
+
+pub struct Iter<'a, T: 'a> {
+    storage: &'a Storage<T>,
+    index: usize,
+}
+
+pub struct IterMut<'a, T: 'a> {
+    storage: &'a mut Storage<T>,
+    index: usize,
+}
+
+impl<'a, T: 'a> Iterator for Iter<'a, T> {
+    type Item = &'a T;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        if self.index == self.storage.len() {
+            None
+        } else {
+            let res = Some(&self.storage[self.index]);
+            self.index += 1;
+            res
+        }
+    }
+}
+
+impl<'a, T: 'a> Iterator for IterMut<'a, T> {
+    type Item = &'a mut T;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        if self.index == self.storage.len() {
+            None
+        } else {
+            let index = self.index;
+            self.index += 1;
+
+            unsafe {
+                Some(&mut *(&mut self.storage[index] as *mut _))
+            }
+        }
+    }
+}