Expand the benchmarking and unit test suite for ring_buf.

-Adds unit tests for fn get() and fn get_mut() which are currently untested
-Adds unit tests to verify growth of the ringbuffer when reserve is called.
-Adds unit tests to confirm that dropping of items is correct
Move ringbuf to use a raw buffer instead of Option<T>

1 files changed, 486 insertions, 199 deletions

diff --git a/src/libcollections/ring_buf.rs b/src/libcollections/ring_buf.rs
index 46fd86df987..fcf9e33cc9d 100644
--- a/src/libcollections/ring_buf.rs
+++ b/src/libcollections/ring_buf.rs
@@ -15,14 +15,19 @@
 
 use core::prelude::*;
 
-use core::cmp;
 use core::default::Default;
 use core::fmt;
 use core::iter;
-use core::slice;
+use core::raw::Slice as RawSlice;
+use core::ptr;
+use core::kinds::marker;
+use core::mem;
+use core::num;
+
 use std::hash::{Writer, Hash};
+use std::cmp;
 
-use vec::Vec;
+use alloc::heap;
 
 static INITIAL_CAPACITY: uint = 8u; // 2^3
 static MINIMUM_CAPACITY: uint = 2u;
@@ -33,11 +38,37 @@ static MINIMUM_CAPACITY: uint = 2u;
 
 
 /// `RingBuf` is a circular buffer that implements `Deque`.
-#[deriving(Clone)]
 pub struct RingBuf<T> {
-    nelts: uint,
-    lo: uint,
-    elts: Vec<Option<T>>
+    // tail and head are pointers into the buffer. Tail always points
+    // to the first element that could be read, Head always points
+    // to where data should be written.
+    // If tail == head the buffer is empty. The length of the ringbuf
+    // is defined as the distance between the two.
+
+    tail: uint,
+    head: uint,
+    cap: uint,
+    ptr: *mut T
+}
+
+impl<T: Clone> Clone for RingBuf<T> {
+    fn clone(&self) -> RingBuf<T> {
+        self.iter().map(|t| t.clone()).collect()
+    }
+}
+
+#[unsafe_destructor]
+impl<T> Drop for RingBuf<T> {
+    fn drop(&mut self) {
+        self.clear();
+        unsafe {
+            if mem::size_of::<T>() != 0 {
+                heap::deallocate(self.ptr as *mut u8,
+                                 self.cap * mem::size_of::<T>(),
+                                 mem::min_align_of::<T>())
+            }
+        }
+    }
 }
 
 impl<T> Default for RingBuf<T> {
@@ -46,6 +77,30 @@ impl<T> Default for RingBuf<T> {
 }
 
 impl<T> RingBuf<T> {
+    /// Turn ptr into a slice
+    #[inline]
+    unsafe fn buffer_as_slice(&self) -> &[T] {
+        mem::transmute(RawSlice { data: self.ptr as *const T, len: self.cap })
+    }
+
+    /// Moves an element out of the buffer
+    #[inline]
+    unsafe fn buffer_read(&mut self, off: uint) -> T {
+        ptr::read(self.ptr.offset(off as int) as *const T)
+    }
+
+    /// Writes an element into the buffer, moving it.
+    #[inline]
+    unsafe fn buffer_write(&mut self, off: uint, t: T) {
+        ptr::write(self.ptr.offset(off as int), t);
+    }
+
+    /// Returns true iff the buffer is at capacity
+    #[inline]
+    fn is_full(&self) -> bool { self.cap - self.len() == 1 }
+}
+
+impl<T> RingBuf<T> {
     /// Creates an empty `RingBuf`.
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn new() -> RingBuf<T> {
@@ -55,8 +110,21 @@ impl<T> RingBuf<T> {
     /// Creates an empty `RingBuf` with space for at least `n` elements.
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn with_capacity(n: uint) -> RingBuf<T> {
-        RingBuf{nelts: 0, lo: 0,
-              elts: Vec::from_fn(cmp::max(MINIMUM_CAPACITY, n), |_| None)}
+        // +1 since the ringbuffer always leaves one space empty
+        let cap = num::next_power_of_two(cmp::max(n + 1, MINIMUM_CAPACITY));
+        let size = cap.checked_mul(&mem::size_of::<T>())
+                      .expect("capacity overflow");
+
+        RingBuf {
+            tail: 0,
+            head: 0,
+            cap: cap,
+            ptr: if mem::size_of::<T>() != 0 {
+                unsafe { heap::allocate(size, mem::min_align_of::<T>()) as *mut T }
+            } else {
+                heap::EMPTY as *mut T
+            }
+        }
     }
 
     /// Retrieves an element in the `RingBuf` by index.
@@ -74,9 +142,11 @@ impl<T> RingBuf<T> {
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn get(&self, i: uint) -> Option<&T> {
-        match self.elts.get(i) {
-            None => None,
-            Some(opt) => opt.as_ref(),
+        if i < self.len() {
+            let idx = wrap_index(self.tail + i, self.cap);
+            unsafe { Some(&*self.ptr.offset(idx as int)) }
+        } else {
+            None
         }
     }
 
@@ -102,9 +172,11 @@ impl<T> RingBuf<T> {
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn get_mut(&mut self, i: uint) -> Option<&mut T> {
-        match self.elts.get_mut(i) {
-            None => None,
-            Some(opt) => opt.as_mut(),
+        if i < self.len() {
+            let idx = wrap_index(self.tail + i, self.cap);
+            unsafe { Some(&mut *self.ptr.offset(idx as int)) }
+        } else {
+            None
         }
     }
 
@@ -130,15 +202,11 @@ impl<T> RingBuf<T> {
     pub fn swap(&mut self, i: uint, j: uint) {
         assert!(i < self.len());
         assert!(j < self.len());
-        let ri = self.raw_index(i);
-        let rj = self.raw_index(j);
-        self.elts.as_mut_slice().swap(ri, rj);
-    }
-
-    /// Returns the index in the underlying `Vec` for a given logical element
-    /// index.
-    fn raw_index(&self, idx: uint) -> uint {
-        raw_index(self.lo, self.elts.len(), idx)
+        let ri = wrap_index(self.tail + i, self.cap);
+        let rj = wrap_index(self.tail + j, self.cap);
+        unsafe {
+            ptr::swap(self.ptr.offset(ri as int), self.ptr.offset(rj as int))
+        }
     }
 
     /// Returns the number of elements the `RingBuf` can hold without
@@ -150,14 +218,11 @@ impl<T> RingBuf<T> {
     /// use std::collections::RingBuf;
     ///
     /// let buf: RingBuf<int> = RingBuf::with_capacity(10);
-    /// assert_eq!(buf.capacity(), 10);
+    /// assert!(buf.capacity() >= 10);
     /// ```
     #[inline]
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
-    pub fn capacity(&self) -> uint {
-        // FXIME(Gankro): not the actual usable capacity if you use reserve/reserve_exact
-        self.elts.capacity()
-    }
+    pub fn capacity(&self) -> uint { self.cap - 1 }
 
     /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the
     /// given `RingBuf`. Does nothing if the capacity is already sufficient.
@@ -181,8 +246,7 @@ impl<T> RingBuf<T> {
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn reserve_exact(&mut self, additional: uint) {
-        // FIXME(Gankro): this is just wrong. The ringbuf won't actually use this space
-        self.elts.reserve_exact(additional);
+        self.reserve(additional);
     }
 
     /// Reserves capacity for at least `additional` more elements to be inserted in the given
@@ -203,8 +267,63 @@ impl<T> RingBuf<T> {
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn reserve(&mut self, additional: uint) {
-        // FIXME(Gankro): this is just wrong. The ringbuf won't actually use this space
-        self.elts.reserve(additional);
+        let new_len = self.len() + additional;
+        assert!(new_len + 1 > self.len(), "capacity overflow");
+        if new_len > self.capacity() {
+            let count = num::next_power_of_two(new_len + 1);
+            assert!(count >= new_len + 1);
+
+            if mem::size_of::<T>() != 0 {
+                let old = self.cap * mem::size_of::<T>();
+                let new = count.checked_mul(&mem::size_of::<T>())
+                               .expect("capacity overflow");
+                unsafe {
+                    self.ptr = heap::reallocate(self.ptr as *mut u8,
+                                                old,
+                                                new,
+                                                mem::min_align_of::<T>()) as *mut T;
+                }
+            }
+
+            // Move the shortest contiguous section of the ring buffer
+            //    T             H
+            //   [o o o o o o o . ]
+            //    T             H
+            // A [o o o o o o o . . . . . . . . . ]
+            //        H T
+            //   [o o . o o o o o ]
+            //          T             H
+            // B [. . . o o o o o o o . . . . . . ]
+            //              H T
+            //   [o o o o o . o o ]
+            //              H                 T
+            // C [o o o o o . . . . . . . . . o o ]
+
+            let oldcap = self.cap;
+            self.cap = count;
+
+            if self.tail <= self.head { // A
+                // Nop
+            } else if self.head < oldcap - self.tail { // B
+                unsafe {
+                    ptr::copy_nonoverlapping_memory(
+                        self.ptr.offset(oldcap as int),
+                        self.ptr as *const T,
+                        self.head
+                    );
+                }
+                self.head += oldcap;
+            } else { // C
+                unsafe {
+                    ptr::copy_nonoverlapping_memory(
+                        self.ptr.offset((count - (oldcap - self.tail)) as int),
+                        self.ptr.offset(self.tail as int) as *const T,
+                        oldcap - self.tail
+                    );
+                }
+                self.tail = count - (oldcap - self.tail);
+            }
+        }
     }
 
     /// Returns a front-to-back iterator.
@@ -223,7 +342,11 @@ impl<T> RingBuf<T> {
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter(&self) -> Items<T> {
-        Items{index: 0, rindex: self.nelts, lo: self.lo, elts: self.elts.as_slice()}
+        Items {
+            tail: self.tail,
+            head: self.head,
+            ring: unsafe { self.buffer_as_slice() }
+        }
     }
 
     /// Returns a front-to-back iterator which returns mutable references.
@@ -244,32 +367,14 @@ impl<T> RingBuf<T> {
     /// assert_eq!(buf.iter_mut().collect::<Vec<&mut int>>()[], b);
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
-    pub fn iter_mut(&mut self) -> MutItems<T> {
-        let start_index = raw_index(self.lo, self.elts.len(), 0);
-        let end_index = raw_index(self.lo, self.elts.len(), self.nelts);
-
-        // Divide up the array
-        if end_index <= start_index {
-            // Items to iterate goes from:
-            //    start_index to self.elts.len()
-            // and then
-            //    0 to end_index
-            let (temp, remaining1) = self.elts.split_at_mut(start_index);
-            let (remaining2, _) = temp.split_at_mut(end_index);
-            MutItems {
-                remaining1: remaining1.iter_mut(),
-                remaining2: remaining2.iter_mut(),
-                nelts: self.nelts,
-            }
-        } else {
-            // Items to iterate goes from start_index to end_index:
-            let (empty, elts) = self.elts.split_at_mut(0);
-            let remaining1 = elts[mut start_index..end_index];
-            MutItems {
-                remaining1: remaining1.iter_mut(),
-                remaining2: empty.iter_mut(),
-                nelts: self.nelts,
-            }
+    pub fn iter_mut<'a>(&'a mut self) -> MutItems<'a, T> {
+        MutItems {
+            tail: self.tail,
+            head: self.head,
+            cap: self.cap,
+            ptr: self.ptr,
+            marker: marker::ContravariantLifetime::<'a>,
+            marker2: marker::NoCopy
         }
     }
 
@@ -286,7 +391,7 @@ impl<T> RingBuf<T> {
     /// assert_eq!(v.len(), 1);
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
-    pub fn len(&self) -> uint { self.nelts }
+    pub fn len(&self) -> uint { count(self.tail, self.head, self.cap) }
 
     /// Returns true if the buffer contains no elements
     ///
@@ -317,9 +422,11 @@ impl<T> RingBuf<T> {
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn clear(&mut self) {
-        for x in self.elts.iter_mut() { *x = None }
-        self.nelts = 0;
-        self.lo = 0;
+        while !self.is_empty() {
+            self.pop_front();
+        }
+        self.head = 0;
+        self.tail = 0;
     }
 
     /// Provides a reference to the front element, or `None` if the sequence is
@@ -339,7 +446,7 @@ impl<T> RingBuf<T> {
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn front(&self) -> Option<&T> {
-        if self.nelts > 0 { Some(&self[0]) } else { None }
+        if !self.is_empty() { Some(&self[0]) } else { None }
     }
 
     /// Provides a mutable reference to the front element, or `None` if the
@@ -363,7 +470,7 @@ impl<T> RingBuf<T> {
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn front_mut(&mut self) -> Option<&mut T> {
-        if self.nelts > 0 { Some(&mut self[0]) } else { None }
+        if !self.is_empty() { Some(&mut self[0]) } else { None }
     }
 
     /// Provides a reference to the back element, or `None` if the sequence is
@@ -383,7 +490,7 @@ impl<T> RingBuf<T> {
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn back(&self) -> Option<&T> {
-        if self.nelts > 0 { Some(&self[self.nelts - 1]) } else { None }
+        if !self.is_empty() { Some(&self[self.len() - 1]) } else { None }
     }
 
     /// Provides a mutable reference to the back element, or `None` if the
@@ -407,8 +514,8 @@ impl<T> RingBuf<T> {
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn back_mut(&mut self) -> Option<&mut T> {
-        let nelts = self.nelts;
-        if nelts > 0 { Some(&mut self[nelts - 1]) } else { None }
+        let len = self.len();
+        if !self.is_empty() { Some(&mut self[len - 1]) } else { None }
     }
 
     /// Removes the first element and returns it, or `None` if the sequence is
@@ -429,12 +536,13 @@ impl<T> RingBuf<T> {
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn pop_front(&mut self) -> Option<T> {
-        let result = self.elts[self.lo].take();
-        if result.is_some() {
-            self.lo = (self.lo + 1u) % self.elts.len();
-            self.nelts -= 1u;
+        if self.is_empty() {
+            None
+        } else {
+            let tail = self.tail;
+            self.tail = wrap_index(self.tail + 1, self.cap);
+            unsafe { Some(self.buffer_read(tail)) }
         }
-        result
     }
 
     /// Inserts an element first in the sequence.
@@ -451,14 +559,11 @@ impl<T> RingBuf<T> {
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn push_front(&mut self, t: T) {
-        if self.nelts == self.elts.len() {
-            grow(self.nelts, &mut self.lo, &mut self.elts);
-        }
-        if self.lo == 0u {
-            self.lo = self.elts.len() - 1u;
-        } else { self.lo -= 1u; }
-        self.elts[self.lo] = Some(t);
-        self.nelts += 1u;
+        if self.is_full() { self.reserve(1) }
+
+        self.tail = wrap_index(self.tail - 1, self.cap);
+        let tail = self.tail;
+        unsafe { self.buffer_write(tail, t); }
     }
 
     /// Deprecated: Renamed to `push_back`.
@@ -481,12 +586,11 @@ impl<T> RingBuf<T> {
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn push_back(&mut self, t: T) {
-        if self.nelts == self.elts.len() {
-            grow(self.nelts, &mut self.lo, &mut self.elts);
-        }
-        let hi = self.raw_index(self.nelts);
-        self.elts[hi] = Some(t);
-        self.nelts += 1u;
+        if self.is_full() { self.reserve(1) }
+
+        let head = self.head;
+        self.head = wrap_index(self.head + 1, self.cap);
+        unsafe { self.buffer_write(head, t) }
     }
 
     /// Deprecated: Renamed to `pop_back`.
@@ -511,38 +615,51 @@ impl<T> RingBuf<T> {
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn pop_back(&mut self) -> Option<T> {
-        if self.nelts > 0 {
-            self.nelts -= 1;
-            let hi = self.raw_index(self.nelts);
-            self.elts[hi].take()
-        } else {
+        if self.is_empty() {
             None
+        } else {
+            self.head = wrap_index(self.head - 1, self.cap);
+            let head = self.head;
+            unsafe { Some(self.buffer_read(head)) }
         }
     }
 }
 
+/// Returns the index in the underlying buffer for a given logical element index.
+#[inline]
+fn wrap_index(index: uint, size: uint) -> uint {
+    // size is always a power of 2
+    index & (size - 1)
+}
+
+/// Calculate the number of elements left to be read in the buffer
+#[inline]
+fn count(tail: uint, head: uint, size: uint) -> uint {
+    // size is always a power of 2
+    (head - tail) & (size - 1)
+}
+
 /// `RingBuf` iterator.
 pub struct Items<'a, T:'a> {
-    lo: uint,
-    index: uint,
-    rindex: uint,
-    elts: &'a [Option<T>],
+    ring: &'a [T],
+    tail: uint,
+    head: uint
 }
 
 impl<'a, T> Iterator<&'a T> for Items<'a, T> {
     #[inline]
     fn next(&mut self) -> Option<&'a T> {
-        if self.index == self.rindex {
+        if self.tail == self.head {
             return None;
         }
-        let raw_index = raw_index(self.lo, self.elts.len(), self.index);
-        self.index += 1;
-        Some(self.elts[raw_index].as_ref().unwrap())
+        let tail = self.tail;
+        self.tail = wrap_index(self.tail + 1, self.ring.len());
+        unsafe { Some(self.ring.unsafe_get(tail)) }
     }
 
     #[inline]
     fn size_hint(&self) -> (uint, Option<uint>) {
-        let len = self.rindex - self.index;
+        let len = count(self.tail, self.head, self.ring.len());
         (len, Some(len))
     }
 }
@@ -550,129 +667,87 @@ impl<'a, T> Iterator<&'a T> for Items<'a, T> {
 impl<'a, T> DoubleEndedIterator<&'a T> for Items<'a, T> {
     #[inline]
     fn next_back(&mut self) -> Option<&'a T> {
-        if self.index == self.rindex {
+        if self.tail == self.head {
             return None;
         }
-        self.rindex -= 1;
-        let raw_index = raw_index(self.lo, self.elts.len(), self.rindex);
-        Some(self.elts[raw_index].as_ref().unwrap())
+        self.head = wrap_index(self.head - 1, self.ring.len());
+        unsafe { Some(self.ring.unsafe_get(self.head)) }
     }
 }
 
+
 impl<'a, T> ExactSize<&'a T> for Items<'a, T> {}
 
 impl<'a, T> RandomAccessIterator<&'a T> for Items<'a, T> {
     #[inline]
-    fn indexable(&self) -> uint { self.rindex - self.index }
+    fn indexable(&self) -> uint {
+        let (len, _) = self.size_hint();
+        len
+    }
 
     #[inline]
     fn idx(&mut self, j: uint) -> Option<&'a T> {
         if j >= self.indexable() {
             None
         } else {
-            let raw_index = raw_index(self.lo, self.elts.len(), self.index + j);
-            Some(self.elts[raw_index].as_ref().unwrap())
+            let idx = wrap_index(self.tail + j, self.ring.len());
+            unsafe { Some(self.ring.unsafe_get(idx)) }
         }
     }
 }
 
+// FIXME This was implemented differently from Items because of a problem
+//       with returning the mutable reference. I couldn't find a way to
+//       make the lifetime checker happy so, but there should be a way.
 /// `RingBuf` mutable iterator.
 pub struct MutItems<'a, T:'a> {
-    remaining1: slice::MutItems<'a, Option<T>>,
-    remaining2: slice::MutItems<'a, Option<T>>,
-    nelts: uint,
+    ptr: *mut T,
+    tail: uint,
+    head: uint,
+    cap: uint,
+    marker: marker::ContravariantLifetime<'a>,
+    marker2: marker::NoCopy
 }
 
 impl<'a, T> Iterator<&'a mut T> for MutItems<'a, T> {
     #[inline]
     fn next(&mut self) -> Option<&'a mut T> {
-        if self.nelts == 0 {
+        if self.tail == self.head {
             return None;
         }
-        self.nelts -= 1;
-        match self.remaining1.next() {
-            Some(ptr) => return Some(ptr.as_mut().unwrap()),
-            None => {}
-        }
-        match self.remaining2.next() {
-            Some(ptr) => return Some(ptr.as_mut().unwrap()),
-            None => unreachable!(),
+        let tail = self.tail;
+        self.tail = wrap_index(self.tail + 1, self.cap);
+        if mem::size_of::<T>() != 0 {
+            unsafe { Some(&mut *self.ptr.offset(tail as int)) }
+        } else {
+            // use a none zero pointer
+            Some(unsafe { mem::transmute(1u) })
         }
     }
 
     #[inline]
     fn size_hint(&self) -> (uint, Option<uint>) {
-        (self.nelts, Some(self.nelts))
+        let len = count(self.tail, self.head, self.cap);
+        (len, Some(len))
     }
 }
 
 impl<'a, T> DoubleEndedIterator<&'a mut T> for MutItems<'a, T> {
     #[inline]
     fn next_back(&mut self) -> Option<&'a mut T> {
-        if self.nelts == 0 {
+        if self.tail == self.head {
             return None;
         }
-        self.nelts -= 1;
-        match self.remaining2.next_back() {
-            Some(ptr) => return Some(ptr.as_mut().unwrap()),
-            None => {}
-        }
-        match self.remaining1.next_back() {
-            Some(ptr) => return Some(ptr.as_mut().unwrap()),
-            None => unreachable!(),
-        }
+        self.head = wrap_index(self.head - 1, self.cap);
+        unsafe { Some(&mut *self.ptr.offset(self.head as int)) }
     }
 }
 
 impl<'a, T> ExactSize<&'a mut T> for MutItems<'a, T> {}
 
-/// Grow is only called on full elts, so nelts is also len(elts), unlike
-/// elsewhere.
-fn grow<T>(nelts: uint, loptr: &mut uint, elts: &mut Vec<Option<T>>) {
-    assert_eq!(nelts, elts.len());
-    let lo = *loptr;
-    elts.reserve_exact(nelts);
-    let newlen = elts.capacity();
-
-    /* fill with None */
-    for _ in range(elts.len(), newlen) {
-        elts.push(None);
-    }
-
-    /*
-      Move the shortest half into the newly reserved area.
-      lo ---->|
-      nelts ----------->|
-        [o o o|o o o o o]
-      A [. . .|o o o o o o o o|. . . . .]
-      B [o o o|. . . . . . . .|o o o o o]
-     */
-
-    assert!(newlen - nelts/2 >= nelts);
-    if lo <= (nelts - lo) { // A
-        for i in range(0u, lo) {
-            elts.as_mut_slice().swap(i, nelts + i);
-        }
-    } else {                // B
-        for i in range(lo, nelts) {
-            elts.as_mut_slice().swap(i, newlen - nelts + i);
-        }
-        *loptr += newlen - nelts;
-    }
-}
-
-/// Returns the index in the underlying `Vec` for a given logical element index.
-fn raw_index(lo: uint, len: uint, index: uint) -> uint {
-    if lo >= len - index {
-        lo + index - len
-    } else {
-        lo + index
-    }
-}
-
 impl<A: PartialEq> PartialEq for RingBuf<A> {
     fn eq(&self, other: &RingBuf<A>) -> bool {
-        self.nelts == other.nelts &&
+        self.len() == other.len() &&
             self.iter().zip(other.iter()).all(|(a, b)| a.eq(b))
     }
     fn ne(&self, other: &RingBuf<A>) -> bool {
@@ -707,22 +782,14 @@ impl<S: Writer, A: Hash<S>> Hash<S> for RingBuf<A> {
 impl<A> Index<uint, A> for RingBuf<A> {
     #[inline]
     fn index<'a>(&'a self, i: &uint) -> &'a A {
-        let idx = self.raw_index(*i);
-        match self.elts[idx] {
-            None => panic!(),
-            Some(ref v) => v,
-        }
+        self.get(*i).expect("Out of bounds access")
     }
 }
 
 impl<A> IndexMut<uint, A> for RingBuf<A> {
     #[inline]
     fn index_mut<'a>(&'a mut self, i: &uint) -> &'a mut A {
-        let idx = self.raw_index(*i);
-        match *(&mut self.elts[idx]) {
-            None => panic!(),
-            Some(ref mut v) => v
-        }
+        self.get_mut(*i).expect("Out of bounds access")
     }
 }
 
@@ -893,31 +960,86 @@ mod tests {
     }
 
     #[bench]
-    fn bench_push_back(b: &mut test::Bencher) {
-        let mut deq = RingBuf::new();
+    fn bench_push_back_100(b: &mut test::Bencher) {
+        let mut deq = RingBuf::with_capacity(100);
         b.iter(|| {
-            deq.push_back(0i);
+            for i in range(0i, 100) {
+                deq.push_back(i);
+            }
+            deq.clear();
         })
     }
 
     #[bench]
-    fn bench_push_front(b: &mut test::Bencher) {
-        let mut deq = RingBuf::new();
+    fn bench_push_front_100(b: &mut test::Bencher) {
+        let mut deq = RingBuf::with_capacity(100);
         b.iter(|| {
-            deq.push_front(0i);
+            for i in range(0i, 100) {
+                deq.push_front(i);
+            }
+            deq.clear();
         })
     }
 
     #[bench]
-    fn bench_grow(b: &mut test::Bencher) {
-        let mut deq = RingBuf::new();
+    fn bench_pop_100(b: &mut test::Bencher) {
+        let mut deq = RingBuf::with_capacity(100);
+
+        b.iter(|| {
+            for i in range(0i, 100) {
+                deq.push_back(i);
+            }
+            while None != deq.pop_back() {}
+        })
+    }
+
+    #[bench]
+    fn bench_pop_front_100(b: &mut test::Bencher) {
+        let mut deq = RingBuf::with_capacity(100);
+
+        b.iter(|| {
+            for i in range(0i, 100) {
+                deq.push_back(i);
+            }
+            while None != deq.pop_front() {}
+        })
+    }
+
+    #[bench]
+    fn bench_grow_1025(b: &mut test::Bencher) {
+        b.iter(|| {
+            let mut deq = RingBuf::new();
+            for i in range(0i, 1025) {
+                deq.push_front(i);
+            }
+        })
+    }
+
+    #[bench]
+    fn bench_iter_1000(b: &mut test::Bencher) {
+        let ring: RingBuf<int> = range(0i, 1000).collect();
+
         b.iter(|| {
-            for _ in range(0i, 65) {
-                deq.push_front(1i);
+            let mut sum = 0;
+            for &i in ring.iter() {
+                sum += i;
             }
+            sum
         })
     }
 
+    #[bench]
+    fn bench_mut_iter_1000(b: &mut test::Bencher) {
+        let mut ring: RingBuf<int> = range(0i, 1000).collect();
+
+        b.iter(|| {
+            for i in ring.iter_mut() {
+                *i += 1;
+            }
+        })
+    }
+
+
     #[deriving(Clone, PartialEq, Show)]
     enum Taggy {
         One(int),
@@ -1034,11 +1156,11 @@ mod tests {
         let mut d = RingBuf::new();
         d.push_back(0u64);
         d.reserve(50);
-        assert!(d.capacity() >= 64);
+        assert!(d.capacity() >= 51);
         let mut d = RingBuf::new();
         d.push_back(0u32);
         d.reserve(50);
-        assert!(d.capacity() >= 64);
+        assert!(d.capacity() >= 51);
     }
 
     #[test]
@@ -1257,4 +1379,169 @@ mod tests {
                                                                         .collect();
         assert!(format!("{}", ringbuf).as_slice() == "[just, one, test, more]");
     }
+
+    #[test]
+    fn test_drop() {
+        static mut drops: uint = 0;
+        struct Elem;
+        impl Drop for Elem {
+            fn drop(&mut self) {
+                unsafe { drops += 1; }
+            }
+        }
+
+        let mut ring = RingBuf::new();
+        ring.push_back(Elem);
+        ring.push_front(Elem);
+        ring.push_back(Elem);
+        ring.push_front(Elem);
+        drop(ring);
+
+        assert_eq!(unsafe {drops}, 4);
+    }
+
+    #[test]
+    fn test_drop_with_pop() {
+        static mut drops: uint = 0;
+        struct Elem;
+        impl Drop for Elem {
+            fn drop(&mut self) {
+                unsafe { drops += 1; }
+            }
+        }
+
+        let mut ring = RingBuf::new();
+        ring.push_back(Elem);
+        ring.push_front(Elem);
+        ring.push_back(Elem);
+        ring.push_front(Elem);
+
+        drop(ring.pop_back());
+        drop(ring.pop_front());
+        assert_eq!(unsafe {drops}, 2);
+
+        drop(ring);
+        assert_eq!(unsafe {drops}, 4);
+    }
+
+    #[test]
+    fn test_drop_clear() {
+        static mut drops: uint = 0;
+        struct Elem;
+        impl Drop for Elem {
+            fn drop(&mut self) {
+                unsafe { drops += 1; }
+            }
+        }
+
+        let mut ring = RingBuf::new();
+        ring.push_back(Elem);
+        ring.push_front(Elem);
+        ring.push_back(Elem);
+        ring.push_front(Elem);
+        ring.clear();
+        assert_eq!(unsafe {drops}, 4);
+
+        drop(ring);
+        assert_eq!(unsafe {drops}, 4);
+    }
+
+    #[test]
+    fn test_reserve_grow() {
+        // test growth path A
+        // [T o o H] -> [T o o H . . . . ]
+        let mut ring = RingBuf::with_capacity(4);
+        for i in range(0i, 3) {
+            ring.push_back(i);
+        }
+        ring.reserve(7);
+        for i in range(0i, 3) {
+            assert_eq!(ring.pop_front(), Some(i));
+        }
+
+        // test growth path B
+        // [H T o o] -> [. T o o H . . . ]
+        let mut ring = RingBuf::with_capacity(4);
+        for i in range(0i, 1) {
+            ring.push_back(i);
+            assert_eq!(ring.pop_front(), Some(i));
+        }
+        for i in range(0i, 3) {
+            ring.push_back(i);
+        }
+        ring.reserve(7);
+        for i in range(0i, 3) {
+            assert_eq!(ring.pop_front(), Some(i));
+        }
+
+        // test growth path C
+        // [o o H T] -> [o o H . . . . T ]
+        let mut ring = RingBuf::with_capacity(4);
+        for i in range(0i, 3) {
+            ring.push_back(i);
+            assert_eq!(ring.pop_front(), Some(i));
+        }
+        for i in range(0i, 3) {
+            ring.push_back(i);
+        }
+        ring.reserve(7);
+        for i in range(0i, 3) {
+            assert_eq!(ring.pop_front(), Some(i));
+        }
+    }
+
+    #[test]
+    fn test_get() {
+        let mut ring = RingBuf::new();
+        ring.push_back(0i);
+        assert_eq!(ring.get(0), Some(&0));
+        assert_eq!(ring.get(1), None);
+
+        ring.push_back(1);
+        assert_eq!(ring.get(0), Some(&0));
+        assert_eq!(ring.get(1), Some(&1));
+        assert_eq!(ring.get(2), None);
+
+        ring.push_back(2);
+        assert_eq!(ring.get(0), Some(&0));
+        assert_eq!(ring.get(1), Some(&1));
+        assert_eq!(ring.get(2), Some(&2));
+        assert_eq!(ring.get(3), None);
+
+        assert_eq!(ring.pop_front(), Some(0));
+        assert_eq!(ring.get(0), Some(&1));
+        assert_eq!(ring.get(1), Some(&2));
+        assert_eq!(ring.get(2), None);
+
+        assert_eq!(ring.pop_front(), Some(1));
+        assert_eq!(ring.get(0), Some(&2));
+        assert_eq!(ring.get(1), None);
+
+        assert_eq!(ring.pop_front(), Some(2));
+        assert_eq!(ring.get(0), None);
+        assert_eq!(ring.get(1), None);
+    }
+
+    #[test]
+    fn test_get_mut() {
+        let mut ring = RingBuf::new();
+        for i in range(0i, 3) {
+            ring.push_back(i);
+        }
+
+        match ring.get_mut(1) {
+            Some(x) => *x = -1,
+            None => ()
+        };
+
+        assert_eq!(ring.get_mut(0), Some(&mut 0));
+        assert_eq!(ring.get_mut(1), Some(&mut -1));
+        assert_eq!(ring.get_mut(2), Some(&mut 2));
+        assert_eq!(ring.get_mut(3), None);
+
+        assert_eq!(ring.pop_front(), Some(0));
+        assert_eq!(ring.get_mut(0), Some(&mut -1));
+        assert_eq!(ring.get_mut(1), Some(&mut 2));
+        assert_eq!(ring.get_mut(2), None);
+    }
 }