1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! This crate implements a double-ended queue with `O(1)` amortized inserts and removals from both
12 //! ends of the container. It also has `O(1)` indexing like a vector. The contained elements are
13 //! not required to be copyable, and the queue will be sendable if the contained type is sendable.
17 use core::cmp::Ordering;
18 use core::default::Default;
20 use core::iter::{self, FromIterator, RandomAccessIterator};
21 use core::kinds::marker;
23 use core::num::{Int, UnsignedInt};
24 use core::ops::{Index, IndexMut};
26 use core::raw::Slice as RawSlice;
28 use std::hash::{Writer, Hash};
33 static INITIAL_CAPACITY: uint = 8u; // 2^3
34 static MINIMUM_CAPACITY: uint = 2u;
36 // FIXME(conventions): implement shrink_to_fit. Awkward with the current design, but it should
37 // be scrapped anyway. Defer to rewrite?
39 /// `RingBuf` is a circular buffer, which can be used as a double-ended queue efficiently.
41 pub struct RingBuf<T> {
42 // tail and head are pointers into the buffer. Tail always points
43 // to the first element that could be read, Head always points
44 // to where data should be written.
45 // If tail == head the buffer is empty. The length of the ringbuf
46 // is defined as the distance between the two.
55 unsafe impl<T: Send> Send for RingBuf<T> {}
58 unsafe impl<T: Sync> Sync for RingBuf<T> {}
61 impl<T: Clone> Clone for RingBuf<T> {
62 fn clone(&self) -> RingBuf<T> {
63 self.iter().map(|t| t.clone()).collect()
69 impl<T> Drop for RingBuf<T> {
73 if mem::size_of::<T>() != 0 {
74 heap::deallocate(self.ptr as *mut u8,
75 self.cap * mem::size_of::<T>(),
76 mem::min_align_of::<T>())
83 impl<T> Default for RingBuf<T> {
85 fn default() -> RingBuf<T> { RingBuf::new() }
89 /// Turn ptr into a slice
91 unsafe fn buffer_as_slice(&self) -> &[T] {
92 mem::transmute(RawSlice { data: self.ptr as *const T, len: self.cap })
95 /// Turn ptr into a mut slice
97 unsafe fn buffer_as_mut_slice(&mut self) -> &mut [T] {
98 mem::transmute(RawSlice { data: self.ptr as *const T, len: self.cap })
101 /// Moves an element out of the buffer
103 unsafe fn buffer_read(&mut self, off: uint) -> T {
104 ptr::read(self.ptr.offset(off as int) as *const T)
107 /// Writes an element into the buffer, moving it.
109 unsafe fn buffer_write(&mut self, off: uint, t: T) {
110 ptr::write(self.ptr.offset(off as int), t);
113 /// Returns true iff the buffer is at capacity
115 fn is_full(&self) -> bool { self.cap - self.len() == 1 }
117 /// Returns the index in the underlying buffer for a given logical element index.
119 fn wrap_index(&self, idx: uint) -> uint { wrap_index(idx, self.cap) }
121 /// Copies a contiguous block of memory len long from src to dst
123 unsafe fn copy(&self, dst: uint, src: uint, len: uint) {
124 debug_assert!(dst + len <= self.cap, "dst={} src={} len={} cap={}", dst, src, len,
126 debug_assert!(src + len <= self.cap, "dst={} src={} len={} cap={}", dst, src, len,
129 self.ptr.offset(dst as int),
130 self.ptr.offset(src as int) as *const T,
136 /// Creates an empty `RingBuf`.
138 pub fn new() -> RingBuf<T> {
139 RingBuf::with_capacity(INITIAL_CAPACITY)
142 /// Creates an empty `RingBuf` with space for at least `n` elements.
144 pub fn with_capacity(n: uint) -> RingBuf<T> {
145 // +1 since the ringbuffer always leaves one space empty
146 let cap = cmp::max(n + 1, MINIMUM_CAPACITY).next_power_of_two();
147 let size = cap.checked_mul(mem::size_of::<T>())
148 .expect("capacity overflow");
150 let ptr = if mem::size_of::<T>() != 0 {
152 let ptr = heap::allocate(size, mem::min_align_of::<T>()) as *mut T;;
153 if ptr.is_null() { ::alloc::oom() }
157 heap::EMPTY as *mut T
168 /// Retrieves an element in the `RingBuf` by index.
173 /// use std::collections::RingBuf;
175 /// let mut buf = RingBuf::new();
176 /// buf.push_back(3i);
177 /// buf.push_back(4);
178 /// buf.push_back(5);
179 /// assert_eq!(buf.get(1).unwrap(), &4);
182 pub fn get(&self, i: uint) -> Option<&T> {
184 let idx = self.wrap_index(self.tail + i);
185 unsafe { Some(&*self.ptr.offset(idx as int)) }
191 /// Retrieves an element in the `RingBuf` mutably by index.
196 /// use std::collections::RingBuf;
198 /// let mut buf = RingBuf::new();
199 /// buf.push_back(3i);
200 /// buf.push_back(4);
201 /// buf.push_back(5);
202 /// match buf.get_mut(1) {
209 /// assert_eq!(buf[1], 7);
212 pub fn get_mut(&mut self, i: uint) -> Option<&mut T> {
214 let idx = self.wrap_index(self.tail + i);
215 unsafe { Some(&mut *self.ptr.offset(idx as int)) }
221 /// Swaps elements at indices `i` and `j`.
223 /// `i` and `j` may be equal.
225 /// Fails if there is no element with either index.
230 /// use std::collections::RingBuf;
232 /// let mut buf = RingBuf::new();
233 /// buf.push_back(3i);
234 /// buf.push_back(4);
235 /// buf.push_back(5);
237 /// assert_eq!(buf[0], 5);
238 /// assert_eq!(buf[2], 3);
241 pub fn swap(&mut self, i: uint, j: uint) {
242 assert!(i < self.len());
243 assert!(j < self.len());
244 let ri = self.wrap_index(self.tail + i);
245 let rj = self.wrap_index(self.tail + j);
247 ptr::swap(self.ptr.offset(ri as int), self.ptr.offset(rj as int))
251 /// Returns the number of elements the `RingBuf` can hold without
257 /// use std::collections::RingBuf;
259 /// let buf: RingBuf<int> = RingBuf::with_capacity(10);
260 /// assert!(buf.capacity() >= 10);
264 pub fn capacity(&self) -> uint { self.cap - 1 }
266 /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the
267 /// given `RingBuf`. Does nothing if the capacity is already sufficient.
269 /// Note that the allocator may give the collection more space than it requests. Therefore
270 /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future
271 /// insertions are expected.
275 /// Panics if the new capacity overflows `uint`.
280 /// use std::collections::RingBuf;
282 /// let mut buf: RingBuf<int> = vec![1].into_iter().collect();
283 /// buf.reserve_exact(10);
284 /// assert!(buf.capacity() >= 11);
287 pub fn reserve_exact(&mut self, additional: uint) {
288 self.reserve(additional);
291 /// Reserves capacity for at least `additional` more elements to be inserted in the given
292 /// `Ringbuf`. The collection may reserve more space to avoid frequent reallocations.
296 /// Panics if the new capacity overflows `uint`.
301 /// use std::collections::RingBuf;
303 /// let mut buf: RingBuf<int> = vec![1].into_iter().collect();
305 /// assert!(buf.capacity() >= 11);
308 pub fn reserve(&mut self, additional: uint) {
309 let new_len = self.len() + additional;
310 assert!(new_len + 1 > self.len(), "capacity overflow");
311 if new_len > self.capacity() {
312 let count = (new_len + 1).next_power_of_two();
313 assert!(count >= new_len + 1);
315 if mem::size_of::<T>() != 0 {
316 let old = self.cap * mem::size_of::<T>();
317 let new = count.checked_mul(mem::size_of::<T>())
318 .expect("capacity overflow");
320 self.ptr = heap::reallocate(self.ptr as *mut u8,
323 mem::min_align_of::<T>()) as *mut T;
324 if self.ptr.is_null() { ::alloc::oom() }
328 // Move the shortest contiguous section of the ring buffer
330 // [o o o o o o o . ]
332 // A [o o o o o o o . . . . . . . . . ]
334 // [o o . o o o o o ]
336 // B [. . . o o o o o o o . . . . . . ]
338 // [o o o o o . o o ]
340 // C [o o o o o . . . . . . . . . o o ]
342 let oldcap = self.cap;
345 if self.tail <= self.head { // A
347 } else if self.head < oldcap - self.tail { // B
349 ptr::copy_nonoverlapping_memory(
350 self.ptr.offset(oldcap as int),
351 self.ptr as *const T,
356 debug_assert!(self.head > self.tail);
359 ptr::copy_nonoverlapping_memory(
360 self.ptr.offset((count - (oldcap - self.tail)) as int),
361 self.ptr.offset(self.tail as int) as *const T,
365 self.tail = count - (oldcap - self.tail);
366 debug_assert!(self.head < self.tail);
368 debug_assert!(self.head < self.cap);
369 debug_assert!(self.tail < self.cap);
370 debug_assert!(self.cap.count_ones() == 1);
374 /// Returns a front-to-back iterator.
379 /// use std::collections::RingBuf;
381 /// let mut buf = RingBuf::new();
382 /// buf.push_back(5i);
383 /// buf.push_back(3);
384 /// buf.push_back(4);
385 /// let b: &[_] = &[&5, &3, &4];
386 /// assert_eq!(buf.iter().collect::<Vec<&int>>().as_slice(), b);
389 pub fn iter(&self) -> Iter<T> {
393 ring: unsafe { self.buffer_as_slice() }
397 /// Returns a front-to-back iterator that returns mutable references.
402 /// use std::collections::RingBuf;
404 /// let mut buf = RingBuf::new();
405 /// buf.push_back(5i);
406 /// buf.push_back(3);
407 /// buf.push_back(4);
408 /// for num in buf.iter_mut() {
411 /// let b: &[_] = &[&mut 3, &mut 1, &mut 2];
412 /// assert_eq!(buf.iter_mut().collect::<Vec<&mut int>>()[], b);
415 pub fn iter_mut<'a>(&'a mut self) -> IterMut<'a, T> {
421 marker: marker::ContravariantLifetime::<'a>,
425 /// Consumes the list into an iterator yielding elements by value.
427 pub fn into_iter(self) -> IntoIter<T> {
433 /// Returns a pair of slices which contain, in order, the contents of the
436 #[unstable = "matches collection reform specification, waiting for dust to settle"]
437 pub fn as_slices<'a>(&'a self) -> (&'a [T], &'a [T]) {
439 let contiguous = self.is_contiguous();
440 let buf = self.buffer_as_slice();
442 let (empty, buf) = buf.split_at(0);
443 (buf[self.tail..self.head], empty)
445 let (mid, right) = buf.split_at(self.tail);
446 let (left, _) = mid.split_at(self.head);
452 /// Returns a pair of slices which contain, in order, the contents of the
455 #[unstable = "matches collection reform specification, waiting for dust to settle"]
456 pub fn as_mut_slices<'a>(&'a mut self) -> (&'a mut [T], &'a mut [T]) {
458 let contiguous = self.is_contiguous();
459 let head = self.head;
460 let tail = self.tail;
461 let buf = self.buffer_as_mut_slice();
464 let (empty, buf) = buf.split_at_mut(0);
465 (buf.slice_mut(tail, head), empty)
467 let (mid, right) = buf.split_at_mut(tail);
468 let (left, _) = mid.split_at_mut(head);
475 /// Returns the number of elements in the `RingBuf`.
480 /// use std::collections::RingBuf;
482 /// let mut v = RingBuf::new();
483 /// assert_eq!(v.len(), 0);
485 /// assert_eq!(v.len(), 1);
488 pub fn len(&self) -> uint { count(self.tail, self.head, self.cap) }
490 /// Returns true if the buffer contains no elements
495 /// use std::collections::RingBuf;
497 /// let mut v = RingBuf::new();
498 /// assert!(v.is_empty());
499 /// v.push_front(1i);
500 /// assert!(!v.is_empty());
503 pub fn is_empty(&self) -> bool { self.len() == 0 }
505 /// Creates a draining iterator that clears the `RingBuf` and iterates over
506 /// the removed items from start to end.
511 /// use std::collections::RingBuf;
513 /// let mut v = RingBuf::new();
515 /// assert_eq!(v.drain().next(), Some(1));
516 /// assert!(v.is_empty());
519 #[unstable = "matches collection reform specification, waiting for dust to settle"]
520 pub fn drain(&mut self) -> Drain<T> {
526 /// Clears the buffer, removing all values.
531 /// use std::collections::RingBuf;
533 /// let mut v = RingBuf::new();
536 /// assert!(v.is_empty());
540 pub fn clear(&mut self) {
544 /// Provides a reference to the front element, or `None` if the sequence is
550 /// use std::collections::RingBuf;
552 /// let mut d = RingBuf::new();
553 /// assert_eq!(d.front(), None);
557 /// assert_eq!(d.front(), Some(&1i));
560 pub fn front(&self) -> Option<&T> {
561 if !self.is_empty() { Some(&self[0]) } else { None }
564 /// Provides a mutable reference to the front element, or `None` if the
565 /// sequence is empty.
570 /// use std::collections::RingBuf;
572 /// let mut d = RingBuf::new();
573 /// assert_eq!(d.front_mut(), None);
577 /// match d.front_mut() {
578 /// Some(x) => *x = 9i,
581 /// assert_eq!(d.front(), Some(&9i));
584 pub fn front_mut(&mut self) -> Option<&mut T> {
585 if !self.is_empty() { Some(&mut self[0]) } else { None }
588 /// Provides a reference to the back element, or `None` if the sequence is
594 /// use std::collections::RingBuf;
596 /// let mut d = RingBuf::new();
597 /// assert_eq!(d.back(), None);
601 /// assert_eq!(d.back(), Some(&2i));
604 pub fn back(&self) -> Option<&T> {
605 if !self.is_empty() { Some(&self[self.len() - 1]) } else { None }
608 /// Provides a mutable reference to the back element, or `None` if the
609 /// sequence is empty.
614 /// use std::collections::RingBuf;
616 /// let mut d = RingBuf::new();
617 /// assert_eq!(d.back(), None);
621 /// match d.back_mut() {
622 /// Some(x) => *x = 9i,
625 /// assert_eq!(d.back(), Some(&9i));
628 pub fn back_mut(&mut self) -> Option<&mut T> {
629 let len = self.len();
630 if !self.is_empty() { Some(&mut self[len - 1]) } else { None }
633 /// Removes the first element and returns it, or `None` if the sequence is
639 /// use std::collections::RingBuf;
641 /// let mut d = RingBuf::new();
645 /// assert_eq!(d.pop_front(), Some(1i));
646 /// assert_eq!(d.pop_front(), Some(2i));
647 /// assert_eq!(d.pop_front(), None);
650 pub fn pop_front(&mut self) -> Option<T> {
654 let tail = self.tail;
655 self.tail = self.wrap_index(self.tail + 1);
656 unsafe { Some(self.buffer_read(tail)) }
660 /// Inserts an element first in the sequence.
665 /// use std::collections::RingBuf;
667 /// let mut d = RingBuf::new();
668 /// d.push_front(1i);
669 /// d.push_front(2i);
670 /// assert_eq!(d.front(), Some(&2i));
673 pub fn push_front(&mut self, t: T) {
676 debug_assert!(!self.is_full());
679 self.tail = self.wrap_index(self.tail - 1);
680 let tail = self.tail;
681 unsafe { self.buffer_write(tail, t); }
684 /// Appends an element to the back of a buffer
689 /// use std::collections::RingBuf;
691 /// let mut buf = RingBuf::new();
692 /// buf.push_back(1i);
693 /// buf.push_back(3);
694 /// assert_eq!(3, *buf.back().unwrap());
697 pub fn push_back(&mut self, t: T) {
700 debug_assert!(!self.is_full());
703 let head = self.head;
704 self.head = self.wrap_index(self.head + 1);
705 unsafe { self.buffer_write(head, t) }
708 /// Removes the last element from a buffer and returns it, or `None` if
714 /// use std::collections::RingBuf;
716 /// let mut buf = RingBuf::new();
717 /// assert_eq!(buf.pop_back(), None);
718 /// buf.push_back(1i);
719 /// buf.push_back(3);
720 /// assert_eq!(buf.pop_back(), Some(3));
723 pub fn pop_back(&mut self) -> Option<T> {
727 self.head = self.wrap_index(self.head - 1);
728 let head = self.head;
729 unsafe { Some(self.buffer_read(head)) }
734 fn is_contiguous(&self) -> bool {
735 self.tail <= self.head
738 /// Inserts an element at position `i` within the ringbuf. Whichever
739 /// end is closer to the insertion point will be moved to make room,
740 /// and all the affected elements will be moved to new positions.
744 /// Panics if `i` is greater than ringbuf's length
748 /// use std::collections::RingBuf;
750 /// let mut buf = RingBuf::new();
751 /// buf.push_back(10i);
752 /// buf.push_back(12);
753 /// buf.insert(1,11);
754 /// assert_eq!(Some(&11), buf.get(1));
756 pub fn insert(&mut self, i: uint, t: T) {
757 assert!(i <= self.len(), "index out of bounds");
760 debug_assert!(!self.is_full());
763 // Move the least number of elements in the ring buffer and insert
766 // At most len/2 - 1 elements will be moved. O(min(n, n-i))
768 // There are three main cases:
769 // Elements are contiguous
770 // - special case when tail is 0
771 // Elements are discontiguous and the insert is in the tail section
772 // Elements are discontiguous and the insert is in the head section
774 // For each of those there are two more cases:
775 // Insert is closer to tail
776 // Insert is closer to head
778 // Key: H - self.head
781 // I - Insertion element
782 // A - The element that should be after the insertion point
783 // M - Indicates element was moved
785 let idx = self.wrap_index(self.tail + i);
787 let distance_to_tail = i;
788 let distance_to_head = self.len() - i;
790 let contiguous = self.is_contiguous();
792 match (contiguous, distance_to_tail <= distance_to_head, idx >= self.tail) {
793 (true, true, _) if i == 0 => {
798 // [A o o o o o o . . . . . . . . .]
801 // [A o o o o o o o . . . . . I]
804 self.tail = self.wrap_index(self.tail - 1);
806 (true, true, _) => unsafe {
807 // contiguous, insert closer to tail:
810 // [. . . o o A o o o o . . . . . .]
813 // [. . o o I A o o o o . . . . . .]
816 // contiguous, insert closer to tail and tail is 0:
820 // [o o A o o o o . . . . . . . . .]
823 // [o I A o o o o o . . . . . . . o]
826 let new_tail = self.wrap_index(self.tail - 1);
828 self.copy(new_tail, self.tail, 1);
829 // Already moved the tail, so we only copy `i - 1` elements.
830 self.copy(self.tail, self.tail + 1, i - 1);
832 self.tail = new_tail;
834 (true, false, _) => unsafe {
835 // contiguous, insert closer to head:
838 // [. . . o o o o A o o . . . . . .]
841 // [. . . o o o o I A o o . . . . .]
844 self.copy(idx + 1, idx, self.head - idx);
845 self.head = self.wrap_index(self.head + 1);
847 (false, true, true) => unsafe {
848 // discontiguous, insert closer to tail, tail section:
851 // [o o o o o o . . . . . o o A o o]
854 // [o o o o o o . . . . o o I A o o]
857 self.copy(self.tail - 1, self.tail, i);
860 (false, false, true) => unsafe {
861 // discontiguous, insert closer to head, tail section:
864 // [o o . . . . . . . o o o o o A o]
867 // [o o o . . . . . . o o o o o I A]
870 // copy elements up to new head
871 self.copy(1, 0, self.head);
873 // copy last element into empty spot at bottom of buffer
874 self.copy(0, self.cap - 1, 1);
876 // move elements from idx to end forward not including ^ element
877 self.copy(idx + 1, idx, self.cap - 1 - idx);
881 (false, true, false) if idx == 0 => unsafe {
882 // discontiguous, insert is closer to tail, head section,
883 // and is at index zero in the internal buffer:
886 // [A o o o o o o o o o . . . o o o]
889 // [A o o o o o o o o o . . o o o I]
892 // copy elements up to new tail
893 self.copy(self.tail - 1, self.tail, self.cap - self.tail);
895 // copy last element into empty spot at bottom of buffer
896 self.copy(self.cap - 1, 0, 1);
900 (false, true, false) => unsafe {
901 // discontiguous, insert closer to tail, head section:
904 // [o o o A o o o o o o . . . o o o]
907 // [o o I A o o o o o o . . o o o o]
910 // copy elements up to new tail
911 self.copy(self.tail - 1, self.tail, self.cap - self.tail);
913 // copy last element into empty spot at bottom of buffer
914 self.copy(self.cap - 1, 0, 1);
916 // move elements from idx-1 to end forward not including ^ element
917 self.copy(0, 1, idx - 1);
921 (false, false, false) => unsafe {
922 // discontiguous, insert closer to head, head section:
925 // [o o o o A o o . . . . . . o o o]
928 // [o o o o I A o o . . . . . o o o]
931 self.copy(idx + 1, idx, self.head - idx);
936 // tail might've been changed so we need to recalculate
937 let new_idx = self.wrap_index(self.tail + i);
939 self.buffer_write(new_idx, t);
943 /// Removes and returns the element at position `i` from the ringbuf.
944 /// Whichever end is closer to the removal point will be moved to make
945 /// room, and all the affected elements will be moved to new positions.
946 /// Returns `None` if `i` is out of bounds.
950 /// use std::collections::RingBuf;
952 /// let mut buf = RingBuf::new();
953 /// buf.push_back(5i);
954 /// buf.push_back(10i);
955 /// buf.push_back(12i);
956 /// buf.push_back(15);
958 /// assert_eq!(Some(&15), buf.get(2));
961 pub fn remove(&mut self, i: uint) -> Option<T> {
962 if self.is_empty() || self.len() <= i {
966 // There are three main cases:
967 // Elements are contiguous
968 // Elements are discontiguous and the removal is in the tail section
969 // Elements are discontiguous and the removal is in the head section
970 // - special case when elements are technically contiguous,
973 // For each of those there are two more cases:
974 // Insert is closer to tail
975 // Insert is closer to head
977 // Key: H - self.head
980 // x - Element marked for removal
981 // R - Indicates element that is being removed
982 // M - Indicates element was moved
984 let idx = self.wrap_index(self.tail + i);
987 Some(self.buffer_read(idx))
990 let distance_to_tail = i;
991 let distance_to_head = self.len() - i;
993 let contiguous = self.tail <= self.head;
995 match (contiguous, distance_to_tail <= distance_to_head, idx >= self.tail) {
996 (true, true, _) => unsafe {
997 // contiguous, remove closer to tail:
1000 // [. . . o o x o o o o . . . . . .]
1003 // [. . . . o o o o o o . . . . . .]
1006 self.copy(self.tail + 1, self.tail, i);
1009 (true, false, _) => unsafe {
1010 // contiguous, remove closer to head:
1013 // [. . . o o o o x o o . . . . . .]
1016 // [. . . o o o o o o . . . . . . .]
1019 self.copy(idx, idx + 1, self.head - idx - 1);
1022 (false, true, true) => unsafe {
1023 // discontiguous, remove closer to tail, tail section:
1026 // [o o o o o o . . . . . o o x o o]
1029 // [o o o o o o . . . . . . o o o o]
1032 self.copy(self.tail + 1, self.tail, i);
1033 self.tail = self.wrap_index(self.tail + 1);
1035 (false, false, false) => unsafe {
1036 // discontiguous, remove closer to head, head section:
1039 // [o o o o x o o . . . . . . o o o]
1042 // [o o o o o o . . . . . . . o o o]
1045 self.copy(idx, idx + 1, self.head - idx - 1);
1048 (false, false, true) => unsafe {
1049 // discontiguous, remove closer to head, tail section:
1052 // [o o o . . . . . . o o o o o x o]
1055 // [o o . . . . . . . o o o o o o o]
1058 // or quasi-discontiguous, remove next to head, tail section:
1061 // [. . . . . . . . . o o o o o x o]
1064 // [. . . . . . . . . o o o o o o .]
1067 // draw in elements in the tail section
1068 self.copy(idx, idx + 1, self.cap - idx - 1);
1070 // Prevents underflow.
1072 // copy first element into empty spot
1073 self.copy(self.cap - 1, 0, 1);
1075 // move elements in the head section backwards
1076 self.copy(0, 1, self.head - 1);
1079 self.head = self.wrap_index(self.head - 1);
1081 (false, true, false) => unsafe {
1082 // discontiguous, remove closer to tail, head section:
1085 // [o o x o o o o o o o . . . o o o]
1088 // [o o o o o o o o o o . . . . o o]
1091 // draw in elements up to idx
1092 self.copy(1, 0, idx);
1094 // copy last element into empty spot
1095 self.copy(0, self.cap - 1, 1);
1097 // move elements from tail to end forward, excluding the last one
1098 self.copy(self.tail + 1, self.tail, self.cap - self.tail - 1);
1100 self.tail = self.wrap_index(self.tail + 1);
1108 /// Returns the index in the underlying buffer for a given logical element index.
1110 fn wrap_index(index: uint, size: uint) -> uint {
1111 // size is always a power of 2
1115 /// Calculate the number of elements left to be read in the buffer
1117 fn count(tail: uint, head: uint, size: uint) -> uint {
1118 // size is always a power of 2
1119 (head - tail) & (size - 1)
1122 /// `RingBuf` iterator.
1124 pub struct Iter<'a, T:'a> {
1130 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1131 impl<'a, T> Clone for Iter<'a, T> {
1132 fn clone(&self) -> Iter<'a, T> {
1142 impl<'a, T> Iterator for Iter<'a, T> {
1146 fn next(&mut self) -> Option<&'a T> {
1147 if self.tail == self.head {
1150 let tail = self.tail;
1151 self.tail = wrap_index(self.tail + 1, self.ring.len());
1152 unsafe { Some(self.ring.get_unchecked(tail)) }
1156 fn size_hint(&self) -> (uint, Option<uint>) {
1157 let len = count(self.tail, self.head, self.ring.len());
1163 impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
1165 fn next_back(&mut self) -> Option<&'a T> {
1166 if self.tail == self.head {
1169 self.head = wrap_index(self.head - 1, self.ring.len());
1170 unsafe { Some(self.ring.get_unchecked(self.head)) }
1175 impl<'a, T> ExactSizeIterator for Iter<'a, T> {}
1178 impl<'a, T> RandomAccessIterator for Iter<'a, T> {
1180 fn indexable(&self) -> uint {
1181 let (len, _) = self.size_hint();
1186 fn idx(&mut self, j: uint) -> Option<&'a T> {
1187 if j >= self.indexable() {
1190 let idx = wrap_index(self.tail + j, self.ring.len());
1191 unsafe { Some(self.ring.get_unchecked(idx)) }
1196 // FIXME This was implemented differently from Iter because of a problem
1197 // with returning the mutable reference. I couldn't find a way to
1198 // make the lifetime checker happy so, but there should be a way.
1199 /// `RingBuf` mutable iterator.
1201 pub struct IterMut<'a, T:'a> {
1206 marker: marker::ContravariantLifetime<'a>,
1210 impl<'a, T> Iterator for IterMut<'a, T> {
1211 type Item = &'a mut T;
1214 fn next(&mut self) -> Option<&'a mut T> {
1215 if self.tail == self.head {
1218 let tail = self.tail;
1219 self.tail = wrap_index(self.tail + 1, self.cap);
1222 Some(&mut *self.ptr.offset(tail as int))
1227 fn size_hint(&self) -> (uint, Option<uint>) {
1228 let len = count(self.tail, self.head, self.cap);
1234 impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
1236 fn next_back(&mut self) -> Option<&'a mut T> {
1237 if self.tail == self.head {
1240 self.head = wrap_index(self.head - 1, self.cap);
1243 Some(&mut *self.ptr.offset(self.head as int))
1249 impl<'a, T> ExactSizeIterator for IterMut<'a, T> {}
1251 /// A by-value RingBuf iterator
1253 pub struct IntoIter<T> {
1258 impl<T> Iterator for IntoIter<T> {
1262 fn next(&mut self) -> Option<T> {
1263 self.inner.pop_front()
1267 fn size_hint(&self) -> (uint, Option<uint>) {
1268 let len = self.inner.len();
1274 impl<T> DoubleEndedIterator for IntoIter<T> {
1276 fn next_back(&mut self) -> Option<T> {
1277 self.inner.pop_back()
1282 impl<T> ExactSizeIterator for IntoIter<T> {}
1284 /// A draining RingBuf iterator
1285 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1286 pub struct Drain<'a, T: 'a> {
1287 inner: &'a mut RingBuf<T>,
1290 #[unsafe_destructor]
1292 impl<'a, T: 'a> Drop for Drain<'a, T> {
1293 fn drop(&mut self) {
1295 self.inner.head = 0;
1296 self.inner.tail = 0;
1301 impl<'a, T: 'a> Iterator for Drain<'a, T> {
1305 fn next(&mut self) -> Option<T> {
1306 self.inner.pop_front()
1310 fn size_hint(&self) -> (uint, Option<uint>) {
1311 let len = self.inner.len();
1317 impl<'a, T: 'a> DoubleEndedIterator for Drain<'a, T> {
1319 fn next_back(&mut self) -> Option<T> {
1320 self.inner.pop_back()
1325 impl<'a, T: 'a> ExactSizeIterator for Drain<'a, T> {}
1328 impl<A: PartialEq> PartialEq for RingBuf<A> {
1329 fn eq(&self, other: &RingBuf<A>) -> bool {
1330 self.len() == other.len() &&
1331 self.iter().zip(other.iter()).all(|(a, b)| a.eq(b))
1336 impl<A: Eq> Eq for RingBuf<A> {}
1339 impl<A: PartialOrd> PartialOrd for RingBuf<A> {
1340 fn partial_cmp(&self, other: &RingBuf<A>) -> Option<Ordering> {
1341 iter::order::partial_cmp(self.iter(), other.iter())
1346 impl<A: Ord> Ord for RingBuf<A> {
1348 fn cmp(&self, other: &RingBuf<A>) -> Ordering {
1349 iter::order::cmp(self.iter(), other.iter())
1354 impl<S: Writer, A: Hash<S>> Hash<S> for RingBuf<A> {
1355 fn hash(&self, state: &mut S) {
1356 self.len().hash(state);
1357 for elt in self.iter() {
1363 // NOTE(stage0): remove impl after a snapshot
1366 impl<A> Index<uint, A> for RingBuf<A> {
1368 fn index<'a>(&'a self, i: &uint) -> &'a A {
1369 self.get(*i).expect("Out of bounds access")
1373 #[cfg(not(stage0))] // NOTE(stage0): remove cfg after a snapshot
1375 impl<A> Index<uint> for RingBuf<A> {
1379 fn index<'a>(&'a self, i: &uint) -> &'a A {
1380 self.get(*i).expect("Out of bounds access")
1384 // NOTE(stage0): remove impl after a snapshot
1387 impl<A> IndexMut<uint, A> for RingBuf<A> {
1389 fn index_mut<'a>(&'a mut self, i: &uint) -> &'a mut A {
1390 self.get_mut(*i).expect("Out of bounds access")
1394 #[cfg(not(stage0))] // NOTE(stage0): remove cfg after a snapshot
1396 impl<A> IndexMut<uint> for RingBuf<A> {
1400 fn index_mut<'a>(&'a mut self, i: &uint) -> &'a mut A {
1401 self.get_mut(*i).expect("Out of bounds access")
1406 impl<A> FromIterator<A> for RingBuf<A> {
1407 fn from_iter<T: Iterator<Item=A>>(iterator: T) -> RingBuf<A> {
1408 let (lower, _) = iterator.size_hint();
1409 let mut deq = RingBuf::with_capacity(lower);
1410 deq.extend(iterator);
1416 impl<A> Extend<A> for RingBuf<A> {
1417 fn extend<T: Iterator<Item=A>>(&mut self, mut iterator: T) {
1418 for elt in iterator {
1419 self.push_back(elt);
1425 impl<T: fmt::Show> fmt::Show for RingBuf<T> {
1426 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1427 try!(write!(f, "["));
1429 for (i, e) in self.iter().enumerate() {
1430 if i != 0 { try!(write!(f, ", ")); }
1431 try!(write!(f, "{}", *e));
1441 use self::Taggypar::*;
1452 #[allow(deprecated)]
1454 let mut d = RingBuf::new();
1455 assert_eq!(d.len(), 0u);
1459 assert_eq!(d.len(), 3u);
1461 assert_eq!(d.len(), 4u);
1462 debug!("{}", d.front());
1463 assert_eq!(*d.front().unwrap(), 42);
1464 debug!("{}", d.back());
1465 assert_eq!(*d.back().unwrap(), 137);
1466 let mut i = d.pop_front();
1468 assert_eq!(i, Some(42));
1471 assert_eq!(i, Some(137));
1474 assert_eq!(i, Some(137));
1477 assert_eq!(i, Some(17));
1478 assert_eq!(d.len(), 0u);
1480 assert_eq!(d.len(), 1u);
1482 assert_eq!(d.len(), 2u);
1484 assert_eq!(d.len(), 3u);
1486 assert_eq!(d.len(), 4u);
1491 assert_eq!(d[0], 1);
1492 assert_eq!(d[1], 2);
1493 assert_eq!(d[2], 3);
1494 assert_eq!(d[3], 4);
1498 fn test_parameterized<T:Clone + PartialEq + Show>(a: T, b: T, c: T, d: T) {
1499 let mut deq = RingBuf::new();
1500 assert_eq!(deq.len(), 0);
1501 deq.push_front(a.clone());
1502 deq.push_front(b.clone());
1503 deq.push_back(c.clone());
1504 assert_eq!(deq.len(), 3);
1505 deq.push_back(d.clone());
1506 assert_eq!(deq.len(), 4);
1507 assert_eq!((*deq.front().unwrap()).clone(), b.clone());
1508 assert_eq!((*deq.back().unwrap()).clone(), d.clone());
1509 assert_eq!(deq.pop_front().unwrap(), b.clone());
1510 assert_eq!(deq.pop_back().unwrap(), d.clone());
1511 assert_eq!(deq.pop_back().unwrap(), c.clone());
1512 assert_eq!(deq.pop_back().unwrap(), a.clone());
1513 assert_eq!(deq.len(), 0);
1514 deq.push_back(c.clone());
1515 assert_eq!(deq.len(), 1);
1516 deq.push_front(b.clone());
1517 assert_eq!(deq.len(), 2);
1518 deq.push_back(d.clone());
1519 assert_eq!(deq.len(), 3);
1520 deq.push_front(a.clone());
1521 assert_eq!(deq.len(), 4);
1522 assert_eq!(deq[0].clone(), a.clone());
1523 assert_eq!(deq[1].clone(), b.clone());
1524 assert_eq!(deq[2].clone(), c.clone());
1525 assert_eq!(deq[3].clone(), d.clone());
1529 fn test_push_front_grow() {
1530 let mut deq = RingBuf::new();
1531 for i in range(0u, 66) {
1534 assert_eq!(deq.len(), 66);
1536 for i in range(0u, 66) {
1537 assert_eq!(deq[i], 65 - i);
1540 let mut deq = RingBuf::new();
1541 for i in range(0u, 66) {
1545 for i in range(0u, 66) {
1546 assert_eq!(deq[i], i);
1552 let mut deq = RingBuf::new();
1553 for i in range(1u, 4) {
1556 assert_eq!(deq[1], 2);
1561 fn test_index_out_of_bounds() {
1562 let mut deq = RingBuf::new();
1563 for i in range(1u, 4) {
1570 fn bench_new(b: &mut test::Bencher) {
1572 let ring: RingBuf<u64> = RingBuf::new();
1573 test::black_box(ring);
1578 fn bench_push_back_100(b: &mut test::Bencher) {
1579 let mut deq = RingBuf::with_capacity(101);
1581 for i in range(0i, 100) {
1590 fn bench_push_front_100(b: &mut test::Bencher) {
1591 let mut deq = RingBuf::with_capacity(101);
1593 for i in range(0i, 100) {
1602 fn bench_pop_back_100(b: &mut test::Bencher) {
1603 let mut deq: RingBuf<int> = RingBuf::with_capacity(101);
1608 while !deq.is_empty() {
1609 test::black_box(deq.pop_back());
1615 fn bench_pop_front_100(b: &mut test::Bencher) {
1616 let mut deq: RingBuf<int> = RingBuf::with_capacity(101);
1621 while !deq.is_empty() {
1622 test::black_box(deq.pop_front());
1628 fn bench_grow_1025(b: &mut test::Bencher) {
1630 let mut deq = RingBuf::new();
1631 for i in range(0i, 1025) {
1634 test::black_box(deq);
1639 fn bench_iter_1000(b: &mut test::Bencher) {
1640 let ring: RingBuf<int> = range(0i, 1000).collect();
1644 for &i in ring.iter() {
1647 test::black_box(sum);
1652 fn bench_mut_iter_1000(b: &mut test::Bencher) {
1653 let mut ring: RingBuf<int> = range(0i, 1000).collect();
1657 for i in ring.iter_mut() {
1660 test::black_box(sum);
1664 #[derive(Clone, PartialEq, Show)]
1668 Three(int, int, int),
1671 #[derive(Clone, PartialEq, Show)]
1675 Threepar(int, int, int),
1678 #[derive(Clone, PartialEq, Show)]
1686 fn test_param_int() {
1687 test_parameterized::<int>(5, 72, 64, 175);
1691 fn test_param_taggy() {
1692 test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
1696 fn test_param_taggypar() {
1697 test_parameterized::<Taggypar<int>>(Onepar::<int>(1),
1698 Twopar::<int>(1, 2),
1699 Threepar::<int>(1, 2, 3),
1700 Twopar::<int>(17, 42));
1704 fn test_param_reccy() {
1705 let reccy1 = RecCy { x: 1, y: 2, t: One(1) };
1706 let reccy2 = RecCy { x: 345, y: 2, t: Two(1, 2) };
1707 let reccy3 = RecCy { x: 1, y: 777, t: Three(1, 2, 3) };
1708 let reccy4 = RecCy { x: 19, y: 252, t: Two(17, 42) };
1709 test_parameterized::<RecCy>(reccy1, reccy2, reccy3, reccy4);
1713 fn test_with_capacity() {
1714 let mut d = RingBuf::with_capacity(0);
1716 assert_eq!(d.len(), 1);
1717 let mut d = RingBuf::with_capacity(50);
1719 assert_eq!(d.len(), 1);
1723 fn test_with_capacity_non_power_two() {
1724 let mut d3 = RingBuf::with_capacity(3);
1729 assert_eq!(d3.pop_front(), Some(1));
1731 assert_eq!(d3.front(), None);
1738 assert_eq!(d3.pop_front(), Some(3));
1740 // Pushing the lo past half way point to trigger
1741 // the 'B' scenario for growth
1748 // There used to be a bug here about how the
1749 // RingBuf made growth assumptions about the
1750 // underlying Vec which didn't hold and lead
1752 // (Vec grows to next power of two)
1753 //good- [9, 12, 15, X, X, X, X, |6]
1754 //bug- [15, 12, X, X, X, |6, X, X]
1755 assert_eq!(d3.pop_front(), Some(6));
1757 // Which leads us to the following state which
1758 // would be a failure case.
1759 //bug- [15, 12, X, X, X, X, |X, X]
1760 assert_eq!(d3.front(), Some(&9));
1764 fn test_reserve_exact() {
1765 let mut d = RingBuf::new();
1767 d.reserve_exact(50);
1768 assert!(d.capacity() >= 51);
1769 let mut d = RingBuf::new();
1771 d.reserve_exact(50);
1772 assert!(d.capacity() >= 51);
1777 let mut d = RingBuf::new();
1780 assert!(d.capacity() >= 51);
1781 let mut d = RingBuf::new();
1784 assert!(d.capacity() >= 51);
1789 let mut d: RingBuf<int> = range(0i, 5).collect();
1792 assert_eq!(d.iter().map(|&x|x).collect::<Vec<int>>(), vec!(4, 2, 3, 1));
1797 let mut d = RingBuf::new();
1798 assert_eq!(d.iter().next(), None);
1799 assert_eq!(d.iter().size_hint(), (0, Some(0)));
1801 for i in range(0i, 5) {
1805 let b: &[_] = &[&0,&1,&2,&3,&4];
1806 assert_eq!(d.iter().collect::<Vec<&int>>(), b);
1809 for i in range(6i, 9) {
1813 let b: &[_] = &[&8,&7,&6,&0,&1,&2,&3,&4];
1814 assert_eq!(d.iter().collect::<Vec<&int>>(), b);
1817 let mut it = d.iter();
1818 let mut len = d.len();
1822 _ => { len -= 1; assert_eq!(it.size_hint(), (len, Some(len))) }
1828 fn test_rev_iter() {
1829 let mut d = RingBuf::new();
1830 assert_eq!(d.iter().rev().next(), None);
1832 for i in range(0i, 5) {
1836 let b: &[_] = &[&4,&3,&2,&1,&0];
1837 assert_eq!(d.iter().rev().collect::<Vec<&int>>(), b);
1840 for i in range(6i, 9) {
1843 let b: &[_] = &[&4,&3,&2,&1,&0,&6,&7,&8];
1844 assert_eq!(d.iter().rev().collect::<Vec<&int>>(), b);
1848 fn test_mut_rev_iter_wrap() {
1849 let mut d = RingBuf::with_capacity(3);
1850 assert!(d.iter_mut().rev().next().is_none());
1855 assert_eq!(d.pop_front(), Some(1));
1858 assert_eq!(d.iter_mut().rev().map(|x| *x).collect::<Vec<int>>(),
1863 fn test_mut_iter() {
1864 let mut d = RingBuf::new();
1865 assert!(d.iter_mut().next().is_none());
1867 for i in range(0u, 3) {
1871 for (i, elt) in d.iter_mut().enumerate() {
1872 assert_eq!(*elt, 2 - i);
1877 let mut it = d.iter_mut();
1878 assert_eq!(*it.next().unwrap(), 0);
1879 assert_eq!(*it.next().unwrap(), 1);
1880 assert_eq!(*it.next().unwrap(), 2);
1881 assert!(it.next().is_none());
1886 fn test_mut_rev_iter() {
1887 let mut d = RingBuf::new();
1888 assert!(d.iter_mut().rev().next().is_none());
1890 for i in range(0u, 3) {
1894 for (i, elt) in d.iter_mut().rev().enumerate() {
1895 assert_eq!(*elt, i);
1900 let mut it = d.iter_mut().rev();
1901 assert_eq!(*it.next().unwrap(), 0);
1902 assert_eq!(*it.next().unwrap(), 1);
1903 assert_eq!(*it.next().unwrap(), 2);
1904 assert!(it.next().is_none());
1909 fn test_into_iter() {
1913 let d: RingBuf<int> = RingBuf::new();
1914 let mut iter = d.into_iter();
1916 assert_eq!(iter.size_hint(), (0, Some(0)));
1917 assert_eq!(iter.next(), None);
1918 assert_eq!(iter.size_hint(), (0, Some(0)));
1923 let mut d = RingBuf::new();
1924 for i in range(0i, 5) {
1928 let b = vec![0,1,2,3,4];
1929 assert_eq!(d.into_iter().collect::<Vec<int>>(), b);
1934 let mut d = RingBuf::new();
1935 for i in range(0i, 5) {
1938 for i in range(6, 9) {
1942 let b = vec![8,7,6,0,1,2,3,4];
1943 assert_eq!(d.into_iter().collect::<Vec<int>>(), b);
1948 let mut d = RingBuf::new();
1949 for i in range(0i, 5) {
1952 for i in range(6, 9) {
1956 let mut it = d.into_iter();
1957 assert_eq!(it.size_hint(), (8, Some(8)));
1958 assert_eq!(it.next(), Some(8));
1959 assert_eq!(it.size_hint(), (7, Some(7)));
1960 assert_eq!(it.next_back(), Some(4));
1961 assert_eq!(it.size_hint(), (6, Some(6)));
1962 assert_eq!(it.next(), Some(7));
1963 assert_eq!(it.size_hint(), (5, Some(5)));
1972 let mut d: RingBuf<int> = RingBuf::new();
1975 let mut iter = d.drain();
1977 assert_eq!(iter.size_hint(), (0, Some(0)));
1978 assert_eq!(iter.next(), None);
1979 assert_eq!(iter.size_hint(), (0, Some(0)));
1982 assert!(d.is_empty());
1987 let mut d = RingBuf::new();
1988 for i in range(0i, 5) {
1992 assert_eq!(d.drain().collect::<Vec<int>>(), [0, 1, 2, 3, 4]);
1993 assert!(d.is_empty());
1998 let mut d = RingBuf::new();
1999 for i in range(0i, 5) {
2002 for i in range(6, 9) {
2006 assert_eq!(d.drain().collect::<Vec<int>>(), [8,7,6,0,1,2,3,4]);
2007 assert!(d.is_empty());
2012 let mut d = RingBuf::new();
2013 for i in range(0i, 5) {
2016 for i in range(6, 9) {
2021 let mut it = d.drain();
2022 assert_eq!(it.size_hint(), (8, Some(8)));
2023 assert_eq!(it.next(), Some(8));
2024 assert_eq!(it.size_hint(), (7, Some(7)));
2025 assert_eq!(it.next_back(), Some(4));
2026 assert_eq!(it.size_hint(), (6, Some(6)));
2027 assert_eq!(it.next(), Some(7));
2028 assert_eq!(it.size_hint(), (5, Some(5)));
2030 assert!(d.is_empty());
2035 fn test_from_iter() {
2037 let v = vec!(1i,2,3,4,5,6,7);
2038 let deq: RingBuf<int> = v.iter().map(|&x| x).collect();
2039 let u: Vec<int> = deq.iter().map(|&x| x).collect();
2042 let seq = iter::count(0u, 2).take(256);
2043 let deq: RingBuf<uint> = seq.collect();
2044 for (i, &x) in deq.iter().enumerate() {
2047 assert_eq!(deq.len(), 256);
2052 let mut d = RingBuf::new();
2057 assert_eq!(d.len(), 4u);
2058 let mut e = d.clone();
2059 assert_eq!(e.len(), 4u);
2060 while !d.is_empty() {
2061 assert_eq!(d.pop_back(), e.pop_back());
2063 assert_eq!(d.len(), 0u);
2064 assert_eq!(e.len(), 0u);
2069 let mut d = RingBuf::new();
2070 assert!(d == RingBuf::with_capacity(0));
2075 let mut e = RingBuf::with_capacity(0);
2085 assert!(e == RingBuf::new());
2090 let mut x = RingBuf::new();
2091 let mut y = RingBuf::new();
2103 assert!(hash::hash(&x) == hash::hash(&y));
2108 let x = RingBuf::new();
2109 let mut y = RingBuf::new();
2121 let ringbuf: RingBuf<int> = range(0i, 10).collect();
2122 assert!(format!("{}", ringbuf) == "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
2124 let ringbuf: RingBuf<&str> = vec!["just", "one", "test", "more"].iter()
2127 assert!(format!("{}", ringbuf) == "[just, one, test, more]");
2132 static mut drops: uint = 0;
2134 impl Drop for Elem {
2135 fn drop(&mut self) {
2136 unsafe { drops += 1; }
2140 let mut ring = RingBuf::new();
2141 ring.push_back(Elem);
2142 ring.push_front(Elem);
2143 ring.push_back(Elem);
2144 ring.push_front(Elem);
2147 assert_eq!(unsafe {drops}, 4);
2151 fn test_drop_with_pop() {
2152 static mut drops: uint = 0;
2154 impl Drop for Elem {
2155 fn drop(&mut self) {
2156 unsafe { drops += 1; }
2160 let mut ring = RingBuf::new();
2161 ring.push_back(Elem);
2162 ring.push_front(Elem);
2163 ring.push_back(Elem);
2164 ring.push_front(Elem);
2166 drop(ring.pop_back());
2167 drop(ring.pop_front());
2168 assert_eq!(unsafe {drops}, 2);
2171 assert_eq!(unsafe {drops}, 4);
2175 fn test_drop_clear() {
2176 static mut drops: uint = 0;
2178 impl Drop for Elem {
2179 fn drop(&mut self) {
2180 unsafe { drops += 1; }
2184 let mut ring = RingBuf::new();
2185 ring.push_back(Elem);
2186 ring.push_front(Elem);
2187 ring.push_back(Elem);
2188 ring.push_front(Elem);
2190 assert_eq!(unsafe {drops}, 4);
2193 assert_eq!(unsafe {drops}, 4);
2197 fn test_reserve_grow() {
2198 // test growth path A
2199 // [T o o H] -> [T o o H . . . . ]
2200 let mut ring = RingBuf::with_capacity(4);
2201 for i in range(0i, 3) {
2205 for i in range(0i, 3) {
2206 assert_eq!(ring.pop_front(), Some(i));
2209 // test growth path B
2210 // [H T o o] -> [. T o o H . . . ]
2211 let mut ring = RingBuf::with_capacity(4);
2212 for i in range(0i, 1) {
2214 assert_eq!(ring.pop_front(), Some(i));
2216 for i in range(0i, 3) {
2220 for i in range(0i, 3) {
2221 assert_eq!(ring.pop_front(), Some(i));
2224 // test growth path C
2225 // [o o H T] -> [o o H . . . . T ]
2226 let mut ring = RingBuf::with_capacity(4);
2227 for i in range(0i, 3) {
2229 assert_eq!(ring.pop_front(), Some(i));
2231 for i in range(0i, 3) {
2235 for i in range(0i, 3) {
2236 assert_eq!(ring.pop_front(), Some(i));
2242 let mut ring = RingBuf::new();
2244 assert_eq!(ring.get(0), Some(&0));
2245 assert_eq!(ring.get(1), None);
2248 assert_eq!(ring.get(0), Some(&0));
2249 assert_eq!(ring.get(1), Some(&1));
2250 assert_eq!(ring.get(2), None);
2253 assert_eq!(ring.get(0), Some(&0));
2254 assert_eq!(ring.get(1), Some(&1));
2255 assert_eq!(ring.get(2), Some(&2));
2256 assert_eq!(ring.get(3), None);
2258 assert_eq!(ring.pop_front(), Some(0));
2259 assert_eq!(ring.get(0), Some(&1));
2260 assert_eq!(ring.get(1), Some(&2));
2261 assert_eq!(ring.get(2), None);
2263 assert_eq!(ring.pop_front(), Some(1));
2264 assert_eq!(ring.get(0), Some(&2));
2265 assert_eq!(ring.get(1), None);
2267 assert_eq!(ring.pop_front(), Some(2));
2268 assert_eq!(ring.get(0), None);
2269 assert_eq!(ring.get(1), None);
2274 let mut ring = RingBuf::new();
2275 for i in range(0i, 3) {
2279 match ring.get_mut(1) {
2284 assert_eq!(ring.get_mut(0), Some(&mut 0));
2285 assert_eq!(ring.get_mut(1), Some(&mut -1));
2286 assert_eq!(ring.get_mut(2), Some(&mut 2));
2287 assert_eq!(ring.get_mut(3), None);
2289 assert_eq!(ring.pop_front(), Some(0));
2290 assert_eq!(ring.get_mut(0), Some(&mut -1));
2291 assert_eq!(ring.get_mut(1), Some(&mut 2));
2292 assert_eq!(ring.get_mut(2), None);
2297 // This test checks that every single combination of tail position, length, and
2298 // insertion position is tested. Capacity 15 should be large enough to cover every case.
2300 let mut tester = RingBuf::with_capacity(15);
2301 // can't guarantee we got 15, so have to get what we got.
2302 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
2303 // this test isn't covering what it wants to
2304 let cap = tester.capacity();
2307 // len is the length *after* insertion
2308 for len in range(1, cap) {
2309 // 0, 1, 2, .., len - 1
2310 let expected = iter::count(0, 1).take(len).collect();
2311 for tail_pos in range(0, cap) {
2312 for to_insert in range(0, len) {
2313 tester.tail = tail_pos;
2314 tester.head = tail_pos;
2315 for i in range(0, len) {
2317 tester.push_back(i);
2320 tester.insert(to_insert, to_insert);
2321 assert!(tester.tail < tester.cap);
2322 assert!(tester.head < tester.cap);
2323 assert_eq!(tester, expected);
2331 // This test checks that every single combination of tail position, length, and
2332 // removal position is tested. Capacity 15 should be large enough to cover every case.
2334 let mut tester = RingBuf::with_capacity(15);
2335 // can't guarantee we got 15, so have to get what we got.
2336 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
2337 // this test isn't covering what it wants to
2338 let cap = tester.capacity();
2340 // len is the length *after* removal
2341 for len in range(0, cap - 1) {
2342 // 0, 1, 2, .., len - 1
2343 let expected = iter::count(0, 1).take(len).collect();
2344 for tail_pos in range(0, cap) {
2345 for to_remove in range(0, len + 1) {
2346 tester.tail = tail_pos;
2347 tester.head = tail_pos;
2348 for i in range(0, len) {
2350 tester.push_back(1234);
2352 tester.push_back(i);
2354 if to_remove == len {
2355 tester.push_back(1234);
2357 tester.remove(to_remove);
2358 assert!(tester.tail < tester.cap);
2359 assert!(tester.head < tester.cap);
2360 assert_eq!(tester, expected);
2368 let mut ring = RingBuf::new();
2369 ring.push_back(10i);
2370 ring.push_back(20i);
2371 assert_eq!(ring.front(), Some(&10));
2373 assert_eq!(ring.front(), Some(&20));
2375 assert_eq!(ring.front(), None);
2379 fn test_as_slices() {
2380 let mut ring: RingBuf<int> = RingBuf::with_capacity(127);
2381 let cap = ring.capacity() as int;
2383 let last = cap - first;
2384 for i in range(0, first) {
2387 let (left, right) = ring.as_slices();
2388 let expected: Vec<_> = range(0, i+1).collect();
2389 assert_eq!(left, expected);
2390 assert_eq!(right, []);
2393 for j in range(-last, 0) {
2395 let (left, right) = ring.as_slices();
2396 let expected_left: Vec<_> = range(-last, j+1).rev().collect();
2397 let expected_right: Vec<_> = range(0, first).collect();
2398 assert_eq!(left, expected_left);
2399 assert_eq!(right, expected_right);
2402 assert_eq!(ring.len() as int, cap);
2403 assert_eq!(ring.capacity() as int, cap);
2407 fn test_as_mut_slices() {
2408 let mut ring: RingBuf<int> = RingBuf::with_capacity(127);
2409 let cap = ring.capacity() as int;
2411 let last = cap - first;
2412 for i in range(0, first) {
2415 let (left, right) = ring.as_mut_slices();
2416 let expected: Vec<_> = range(0, i+1).collect();
2417 assert_eq!(left, expected);
2418 assert_eq!(right, []);
2421 for j in range(-last, 0) {
2423 let (left, right) = ring.as_mut_slices();
2424 let expected_left: Vec<_> = range(-last, j+1).rev().collect();
2425 let expected_right: Vec<_> = range(0, first).collect();
2426 assert_eq!(left, expected_left);
2427 assert_eq!(right, expected_right);
2430 assert_eq!(ring.len() as int, cap);
2431 assert_eq!(ring.capacity() as int, cap);