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.
15 #![stable(feature = "rust1", since = "1.0.0")]
19 use core::cmp::Ordering;
20 use core::default::Default;
22 use core::iter::{self, repeat, FromIterator, IntoIterator, RandomAccessIterator};
25 use core::num::{Int, UnsignedInt};
26 use core::ops::{Index, IndexMut};
28 use core::raw::Slice as RawSlice;
30 use std::hash::{Writer, Hash, Hasher};
35 static INITIAL_CAPACITY: uint = 7u; // 2^3 - 1
36 static MINIMUM_CAPACITY: uint = 1u; // 2 - 1
38 /// `RingBuf` is a circular buffer, which can be used as a double-ended queue efficiently.
39 #[stable(feature = "rust1", since = "1.0.0")]
40 pub struct RingBuf<T> {
41 // tail and head are pointers into the buffer. Tail always points
42 // to the first element that could be read, Head always points
43 // to where data should be written.
44 // If tail == head the buffer is empty. The length of the ringbuf
45 // is defined as the distance between the two.
53 #[stable(feature = "rust1", since = "1.0.0")]
54 unsafe impl<T: Send> Send for RingBuf<T> {}
56 #[stable(feature = "rust1", since = "1.0.0")]
57 unsafe impl<T: Sync> Sync for RingBuf<T> {}
59 #[stable(feature = "rust1", since = "1.0.0")]
60 impl<T: Clone> Clone for RingBuf<T> {
61 fn clone(&self) -> RingBuf<T> {
62 self.iter().map(|t| t.clone()).collect()
67 #[stable(feature = "rust1", since = "1.0.0")]
68 impl<T> Drop for RingBuf<T> {
72 if mem::size_of::<T>() != 0 {
73 heap::deallocate(self.ptr as *mut u8,
74 self.cap * mem::size_of::<T>(),
75 mem::min_align_of::<T>())
81 #[stable(feature = "rust1", since = "1.0.0")]
82 impl<T> Default for RingBuf<T> {
84 fn default() -> RingBuf<T> { RingBuf::new() }
88 /// Turn ptr into a slice
90 unsafe fn buffer_as_slice(&self) -> &[T] {
91 mem::transmute(RawSlice { data: self.ptr, len: self.cap })
94 /// Turn ptr into a mut slice
96 unsafe fn buffer_as_mut_slice(&mut self) -> &mut [T] {
97 mem::transmute(RawSlice { data: self.ptr, len: self.cap })
100 /// Moves an element out of the buffer
102 unsafe fn buffer_read(&mut self, off: uint) -> T {
103 ptr::read(self.ptr.offset(off as int))
106 /// Writes an element into the buffer, moving it.
108 unsafe fn buffer_write(&mut self, off: uint, t: T) {
109 ptr::write(self.ptr.offset(off as int), t);
112 /// Returns true iff the buffer is at capacity
114 fn is_full(&self) -> bool { self.cap - self.len() == 1 }
116 /// Returns the index in the underlying buffer for a given logical element index.
118 fn wrap_index(&self, idx: uint) -> uint { wrap_index(idx, self.cap) }
120 /// Copies a contiguous block of memory len long from src to dst
122 unsafe fn copy(&self, dst: uint, src: uint, len: uint) {
123 debug_assert!(dst + len <= self.cap, "dst={} src={} len={} cap={}", dst, src, len,
125 debug_assert!(src + len <= self.cap, "dst={} src={} len={} cap={}", dst, src, len,
128 self.ptr.offset(dst as int),
129 self.ptr.offset(src as int),
133 /// Copies a contiguous block of memory len long from src to dst
135 unsafe fn copy_nonoverlapping(&self, dst: uint, src: uint, len: uint) {
136 debug_assert!(dst + len <= self.cap, "dst={} src={} len={} cap={}", dst, src, len,
138 debug_assert!(src + len <= self.cap, "dst={} src={} len={} cap={}", dst, src, len,
140 ptr::copy_nonoverlapping_memory(
141 self.ptr.offset(dst as int),
142 self.ptr.offset(src as int),
148 /// Creates an empty `RingBuf`.
149 #[stable(feature = "rust1", since = "1.0.0")]
150 pub fn new() -> RingBuf<T> {
151 RingBuf::with_capacity(INITIAL_CAPACITY)
154 /// Creates an empty `RingBuf` with space for at least `n` elements.
155 #[stable(feature = "rust1", since = "1.0.0")]
156 pub fn with_capacity(n: uint) -> RingBuf<T> {
157 // +1 since the ringbuffer always leaves one space empty
158 let cap = cmp::max(n + 1, MINIMUM_CAPACITY + 1).next_power_of_two();
159 assert!(cap > n, "capacity overflow");
160 let size = cap.checked_mul(mem::size_of::<T>())
161 .expect("capacity overflow");
163 let ptr = if mem::size_of::<T>() != 0 {
165 let ptr = heap::allocate(size, mem::min_align_of::<T>()) as *mut T;;
166 if ptr.is_null() { ::alloc::oom() }
170 heap::EMPTY as *mut T
181 /// Retrieves an element in the `RingBuf` by index.
186 /// use std::collections::RingBuf;
188 /// let mut buf = RingBuf::new();
189 /// buf.push_back(3);
190 /// buf.push_back(4);
191 /// buf.push_back(5);
192 /// assert_eq!(buf.get(1).unwrap(), &4);
194 #[stable(feature = "rust1", since = "1.0.0")]
195 pub fn get(&self, i: uint) -> Option<&T> {
197 let idx = self.wrap_index(self.tail + i);
198 unsafe { Some(&*self.ptr.offset(idx as int)) }
204 /// Retrieves an element in the `RingBuf` mutably by index.
209 /// use std::collections::RingBuf;
211 /// let mut buf = RingBuf::new();
212 /// buf.push_back(3);
213 /// buf.push_back(4);
214 /// buf.push_back(5);
215 /// match buf.get_mut(1) {
222 /// assert_eq!(buf[1], 7);
224 #[stable(feature = "rust1", since = "1.0.0")]
225 pub fn get_mut(&mut self, i: uint) -> Option<&mut T> {
227 let idx = self.wrap_index(self.tail + i);
228 unsafe { Some(&mut *self.ptr.offset(idx as int)) }
234 /// Swaps elements at indices `i` and `j`.
236 /// `i` and `j` may be equal.
238 /// Fails if there is no element with either index.
243 /// use std::collections::RingBuf;
245 /// let mut buf = RingBuf::new();
246 /// buf.push_back(3);
247 /// buf.push_back(4);
248 /// buf.push_back(5);
250 /// assert_eq!(buf[0], 5);
251 /// assert_eq!(buf[2], 3);
253 #[stable(feature = "rust1", since = "1.0.0")]
254 pub fn swap(&mut self, i: uint, j: uint) {
255 assert!(i < self.len());
256 assert!(j < self.len());
257 let ri = self.wrap_index(self.tail + i);
258 let rj = self.wrap_index(self.tail + j);
260 ptr::swap(self.ptr.offset(ri as int), self.ptr.offset(rj as int))
264 /// Returns the number of elements the `RingBuf` can hold without
270 /// use std::collections::RingBuf;
272 /// let buf: RingBuf<i32> = RingBuf::with_capacity(10);
273 /// assert!(buf.capacity() >= 10);
276 #[stable(feature = "rust1", since = "1.0.0")]
277 pub fn capacity(&self) -> uint { self.cap - 1 }
279 /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the
280 /// given `RingBuf`. Does nothing if the capacity is already sufficient.
282 /// Note that the allocator may give the collection more space than it requests. Therefore
283 /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future
284 /// insertions are expected.
288 /// Panics if the new capacity overflows `uint`.
293 /// use std::collections::RingBuf;
295 /// let mut buf: RingBuf<i32> = vec![1].into_iter().collect();
296 /// buf.reserve_exact(10);
297 /// assert!(buf.capacity() >= 11);
299 #[stable(feature = "rust1", since = "1.0.0")]
300 pub fn reserve_exact(&mut self, additional: uint) {
301 self.reserve(additional);
304 /// Reserves capacity for at least `additional` more elements to be inserted in the given
305 /// `Ringbuf`. The collection may reserve more space to avoid frequent reallocations.
309 /// Panics if the new capacity overflows `uint`.
314 /// use std::collections::RingBuf;
316 /// let mut buf: RingBuf<i32> = vec![1].into_iter().collect();
318 /// assert!(buf.capacity() >= 11);
320 #[stable(feature = "rust1", since = "1.0.0")]
321 pub fn reserve(&mut self, additional: uint) {
322 let new_len = self.len() + additional;
323 assert!(new_len + 1 > self.len(), "capacity overflow");
324 if new_len > self.capacity() {
325 let count = (new_len + 1).next_power_of_two();
326 assert!(count >= new_len + 1);
328 if mem::size_of::<T>() != 0 {
329 let old = self.cap * mem::size_of::<T>();
330 let new = count.checked_mul(mem::size_of::<T>())
331 .expect("capacity overflow");
333 self.ptr = heap::reallocate(self.ptr as *mut u8,
336 mem::min_align_of::<T>()) as *mut T;
337 if self.ptr.is_null() { ::alloc::oom() }
341 // Move the shortest contiguous section of the ring buffer
343 // [o o o o o o o . ]
345 // A [o o o o o o o . . . . . . . . . ]
347 // [o o . o o o o o ]
349 // B [. . . o o o o o o o . . . . . . ]
351 // [o o o o o . o o ]
353 // C [o o o o o . . . . . . . . . o o ]
355 let oldcap = self.cap;
358 if self.tail <= self.head { // A
360 } else if self.head < oldcap - self.tail { // B
362 self.copy_nonoverlapping(oldcap, 0, self.head);
365 debug_assert!(self.head > self.tail);
367 let new_tail = count - (oldcap - self.tail);
369 self.copy_nonoverlapping(new_tail, self.tail, oldcap - self.tail);
371 self.tail = new_tail;
372 debug_assert!(self.head < self.tail);
374 debug_assert!(self.head < self.cap);
375 debug_assert!(self.tail < self.cap);
376 debug_assert!(self.cap.count_ones() == 1);
380 /// Shrinks the capacity of the ringbuf as much as possible.
382 /// It will drop down as close as possible to the length but the allocator may still inform the
383 /// ringbuf that there is space for a few more elements.
388 /// use std::collections::RingBuf;
390 /// let mut buf = RingBuf::with_capacity(15);
391 /// buf.extend(0u..4);
392 /// assert_eq!(buf.capacity(), 15);
393 /// buf.shrink_to_fit();
394 /// assert!(buf.capacity() >= 4);
396 pub fn shrink_to_fit(&mut self) {
397 // +1 since the ringbuffer always leaves one space empty
398 // len + 1 can't overflow for an existing, well-formed ringbuf.
399 let target_cap = cmp::max(self.len() + 1, MINIMUM_CAPACITY + 1).next_power_of_two();
400 if target_cap < self.cap {
401 // There are three cases of interest:
402 // All elements are out of desired bounds
403 // Elements are contiguous, and head is out of desired bounds
404 // Elements are discontiguous, and tail is out of desired bounds
406 // At all other times, element positions are unaffected.
408 // Indicates that elements at the head should be moved.
409 let head_outside = self.head == 0 || self.head >= target_cap;
410 // Move elements from out of desired bounds (positions after target_cap)
411 if self.tail >= target_cap && head_outside {
413 // [. . . . . . . . o o o o o o o . ]
415 // [o o o o o o o . ]
417 self.copy_nonoverlapping(0, self.tail, self.len());
419 self.head = self.len();
421 } else if self.tail != 0 && self.tail < target_cap && head_outside {
423 // [. . . o o o o o o o . . . . . . ]
425 // [o o . o o o o o ]
426 let len = self.wrap_index(self.head - target_cap);
428 self.copy_nonoverlapping(0, target_cap, len);
431 debug_assert!(self.head < self.tail);
432 } else if self.tail >= target_cap {
434 // [o o o o o . . . . . . . . . o o ]
436 // [o o o o o . o o ]
437 debug_assert!(self.wrap_index(self.head - 1) < target_cap);
438 let len = self.cap - self.tail;
439 let new_tail = target_cap - len;
441 self.copy_nonoverlapping(new_tail, self.tail, len);
443 self.tail = new_tail;
444 debug_assert!(self.head < self.tail);
447 if mem::size_of::<T>() != 0 {
448 let old = self.cap * mem::size_of::<T>();
449 let new_size = target_cap * mem::size_of::<T>();
451 self.ptr = heap::reallocate(self.ptr as *mut u8,
454 mem::min_align_of::<T>()) as *mut T;
455 if self.ptr.is_null() { ::alloc::oom() }
458 self.cap = target_cap;
459 debug_assert!(self.head < self.cap);
460 debug_assert!(self.tail < self.cap);
461 debug_assert!(self.cap.count_ones() == 1);
465 /// Shorten a ringbuf, dropping excess elements from the back.
467 /// If `len` is greater than the ringbuf's current length, this has no
473 /// use std::collections::RingBuf;
475 /// let mut buf = RingBuf::new();
476 /// buf.push_back(5);
477 /// buf.push_back(10);
478 /// buf.push_back(15);
480 /// assert_eq!(buf.len(), 1);
481 /// assert_eq!(Some(&5), buf.get(0));
483 #[unstable(feature = "collections",
484 reason = "matches collection reform specification; waiting on panic semantics")]
485 pub fn truncate(&mut self, len: uint) {
486 for _ in len..self.len() {
491 /// Returns a front-to-back iterator.
496 /// use std::collections::RingBuf;
498 /// let mut buf = RingBuf::new();
499 /// buf.push_back(5);
500 /// buf.push_back(3);
501 /// buf.push_back(4);
502 /// let b: &[_] = &[&5, &3, &4];
503 /// assert_eq!(buf.iter().collect::<Vec<&i32>>().as_slice(), b);
505 #[stable(feature = "rust1", since = "1.0.0")]
506 pub fn iter(&self) -> Iter<T> {
510 ring: unsafe { self.buffer_as_slice() }
514 /// Returns a front-to-back iterator that returns mutable references.
519 /// use std::collections::RingBuf;
521 /// let mut buf = RingBuf::new();
522 /// buf.push_back(5);
523 /// buf.push_back(3);
524 /// buf.push_back(4);
525 /// for num in buf.iter_mut() {
528 /// let b: &[_] = &[&mut 3, &mut 1, &mut 2];
529 /// assert_eq!(&buf.iter_mut().collect::<Vec<&mut i32>>()[], b);
531 #[stable(feature = "rust1", since = "1.0.0")]
532 pub fn iter_mut<'a>(&'a mut self) -> IterMut<'a, T> {
538 marker: marker::ContravariantLifetime::<'a>,
542 /// Consumes the list into an iterator yielding elements by value.
543 #[stable(feature = "rust1", since = "1.0.0")]
544 pub fn into_iter(self) -> IntoIter<T> {
550 /// Returns a pair of slices which contain, in order, the contents of the
553 #[unstable(feature = "collections",
554 reason = "matches collection reform specification, waiting for dust to settle")]
555 pub fn as_slices<'a>(&'a self) -> (&'a [T], &'a [T]) {
557 let contiguous = self.is_contiguous();
558 let buf = self.buffer_as_slice();
560 let (empty, buf) = buf.split_at(0);
561 (&buf[self.tail..self.head], empty)
563 let (mid, right) = buf.split_at(self.tail);
564 let (left, _) = mid.split_at(self.head);
570 /// Returns a pair of slices which contain, in order, the contents of the
573 #[unstable(feature = "collections",
574 reason = "matches collection reform specification, waiting for dust to settle")]
575 pub fn as_mut_slices<'a>(&'a mut self) -> (&'a mut [T], &'a mut [T]) {
577 let contiguous = self.is_contiguous();
578 let head = self.head;
579 let tail = self.tail;
580 let buf = self.buffer_as_mut_slice();
583 let (empty, buf) = buf.split_at_mut(0);
584 (&mut buf[tail .. head], empty)
586 let (mid, right) = buf.split_at_mut(tail);
587 let (left, _) = mid.split_at_mut(head);
594 /// Returns the number of elements in the `RingBuf`.
599 /// use std::collections::RingBuf;
601 /// let mut v = RingBuf::new();
602 /// assert_eq!(v.len(), 0);
604 /// assert_eq!(v.len(), 1);
606 #[stable(feature = "rust1", since = "1.0.0")]
607 pub fn len(&self) -> uint { count(self.tail, self.head, self.cap) }
609 /// Returns true if the buffer contains no elements
614 /// use std::collections::RingBuf;
616 /// let mut v = RingBuf::new();
617 /// assert!(v.is_empty());
619 /// assert!(!v.is_empty());
621 #[stable(feature = "rust1", since = "1.0.0")]
622 pub fn is_empty(&self) -> bool { self.len() == 0 }
624 /// Creates a draining iterator that clears the `RingBuf` and iterates over
625 /// the removed items from start to end.
630 /// use std::collections::RingBuf;
632 /// let mut v = RingBuf::new();
634 /// assert_eq!(v.drain().next(), Some(1));
635 /// assert!(v.is_empty());
638 #[unstable(feature = "collections",
639 reason = "matches collection reform specification, waiting for dust to settle")]
640 pub fn drain(&mut self) -> Drain<T> {
646 /// Clears the buffer, removing all values.
651 /// use std::collections::RingBuf;
653 /// let mut v = RingBuf::new();
656 /// assert!(v.is_empty());
658 #[stable(feature = "rust1", since = "1.0.0")]
660 pub fn clear(&mut self) {
664 /// Provides a reference to the front element, or `None` if the sequence is
670 /// use std::collections::RingBuf;
672 /// let mut d = RingBuf::new();
673 /// assert_eq!(d.front(), None);
677 /// assert_eq!(d.front(), Some(&1));
679 #[stable(feature = "rust1", since = "1.0.0")]
680 pub fn front(&self) -> Option<&T> {
681 if !self.is_empty() { Some(&self[0]) } else { None }
684 /// Provides a mutable reference to the front element, or `None` if the
685 /// sequence is empty.
690 /// use std::collections::RingBuf;
692 /// let mut d = RingBuf::new();
693 /// assert_eq!(d.front_mut(), None);
697 /// match d.front_mut() {
698 /// Some(x) => *x = 9,
701 /// assert_eq!(d.front(), Some(&9));
703 #[stable(feature = "rust1", since = "1.0.0")]
704 pub fn front_mut(&mut self) -> Option<&mut T> {
705 if !self.is_empty() { Some(&mut self[0]) } else { None }
708 /// Provides a reference to the back element, or `None` if the sequence is
714 /// use std::collections::RingBuf;
716 /// let mut d = RingBuf::new();
717 /// assert_eq!(d.back(), None);
721 /// assert_eq!(d.back(), Some(&2));
723 #[stable(feature = "rust1", since = "1.0.0")]
724 pub fn back(&self) -> Option<&T> {
725 if !self.is_empty() { Some(&self[self.len() - 1]) } else { None }
728 /// Provides a mutable reference to the back element, or `None` if the
729 /// sequence is empty.
734 /// use std::collections::RingBuf;
736 /// let mut d = RingBuf::new();
737 /// assert_eq!(d.back(), None);
741 /// match d.back_mut() {
742 /// Some(x) => *x = 9,
745 /// assert_eq!(d.back(), Some(&9));
747 #[stable(feature = "rust1", since = "1.0.0")]
748 pub fn back_mut(&mut self) -> Option<&mut T> {
749 let len = self.len();
750 if !self.is_empty() { Some(&mut self[len - 1]) } else { None }
753 /// Removes the first element and returns it, or `None` if the sequence is
759 /// use std::collections::RingBuf;
761 /// let mut d = RingBuf::new();
765 /// assert_eq!(d.pop_front(), Some(1));
766 /// assert_eq!(d.pop_front(), Some(2));
767 /// assert_eq!(d.pop_front(), None);
769 #[stable(feature = "rust1", since = "1.0.0")]
770 pub fn pop_front(&mut self) -> Option<T> {
774 let tail = self.tail;
775 self.tail = self.wrap_index(self.tail + 1);
776 unsafe { Some(self.buffer_read(tail)) }
780 /// Inserts an element first in the sequence.
785 /// use std::collections::RingBuf;
787 /// let mut d = RingBuf::new();
790 /// assert_eq!(d.front(), Some(&2));
792 #[stable(feature = "rust1", since = "1.0.0")]
793 pub fn push_front(&mut self, t: T) {
796 debug_assert!(!self.is_full());
799 self.tail = self.wrap_index(self.tail - 1);
800 let tail = self.tail;
801 unsafe { self.buffer_write(tail, t); }
804 /// Appends an element to the back of a buffer
809 /// use std::collections::RingBuf;
811 /// let mut buf = RingBuf::new();
812 /// buf.push_back(1);
813 /// buf.push_back(3);
814 /// assert_eq!(3, *buf.back().unwrap());
816 #[stable(feature = "rust1", since = "1.0.0")]
817 pub fn push_back(&mut self, t: T) {
820 debug_assert!(!self.is_full());
823 let head = self.head;
824 self.head = self.wrap_index(self.head + 1);
825 unsafe { self.buffer_write(head, t) }
828 /// Removes the last element from a buffer and returns it, or `None` if
834 /// use std::collections::RingBuf;
836 /// let mut buf = RingBuf::new();
837 /// assert_eq!(buf.pop_back(), None);
838 /// buf.push_back(1);
839 /// buf.push_back(3);
840 /// assert_eq!(buf.pop_back(), Some(3));
842 #[stable(feature = "rust1", since = "1.0.0")]
843 pub fn pop_back(&mut self) -> Option<T> {
847 self.head = self.wrap_index(self.head - 1);
848 let head = self.head;
849 unsafe { Some(self.buffer_read(head)) }
854 fn is_contiguous(&self) -> bool {
855 self.tail <= self.head
858 /// Removes an element from anywhere in the ringbuf and returns it, replacing it with the last
861 /// This does not preserve ordering, but is O(1).
863 /// Returns `None` if `index` is out of bounds.
868 /// use std::collections::RingBuf;
870 /// let mut buf = RingBuf::new();
871 /// assert_eq!(buf.swap_back_remove(0), None);
872 /// buf.push_back(5);
873 /// buf.push_back(99);
874 /// buf.push_back(15);
875 /// buf.push_back(20);
876 /// buf.push_back(10);
877 /// assert_eq!(buf.swap_back_remove(1), Some(99));
879 #[unstable(feature = "collections",
880 reason = "the naming of this function may be altered")]
881 pub fn swap_back_remove(&mut self, index: uint) -> Option<T> {
882 let length = self.len();
883 if length > 0 && index < length - 1 {
884 self.swap(index, length - 1);
885 } else if index >= length {
891 /// Removes an element from anywhere in the ringbuf and returns it, replacing it with the first
894 /// This does not preserve ordering, but is O(1).
896 /// Returns `None` if `index` is out of bounds.
901 /// use std::collections::RingBuf;
903 /// let mut buf = RingBuf::new();
904 /// assert_eq!(buf.swap_front_remove(0), None);
905 /// buf.push_back(15);
906 /// buf.push_back(5);
907 /// buf.push_back(10);
908 /// buf.push_back(99);
909 /// buf.push_back(20);
910 /// assert_eq!(buf.swap_front_remove(3), Some(99));
912 #[unstable(feature = "collections",
913 reason = "the naming of this function may be altered")]
914 pub fn swap_front_remove(&mut self, index: uint) -> Option<T> {
915 let length = self.len();
916 if length > 0 && index < length && index != 0 {
918 } else if index >= length {
924 /// Inserts an element at position `i` within the ringbuf. Whichever
925 /// end is closer to the insertion point will be moved to make room,
926 /// and all the affected elements will be moved to new positions.
930 /// Panics if `i` is greater than ringbuf's length
934 /// use std::collections::RingBuf;
936 /// let mut buf = RingBuf::new();
937 /// buf.push_back(10);
938 /// buf.push_back(12);
939 /// buf.insert(1,11);
940 /// assert_eq!(Some(&11), buf.get(1));
942 pub fn insert(&mut self, i: uint, t: T) {
943 assert!(i <= self.len(), "index out of bounds");
946 debug_assert!(!self.is_full());
949 // Move the least number of elements in the ring buffer and insert
952 // At most len/2 - 1 elements will be moved. O(min(n, n-i))
954 // There are three main cases:
955 // Elements are contiguous
956 // - special case when tail is 0
957 // Elements are discontiguous and the insert is in the tail section
958 // Elements are discontiguous and the insert is in the head section
960 // For each of those there are two more cases:
961 // Insert is closer to tail
962 // Insert is closer to head
964 // Key: H - self.head
967 // I - Insertion element
968 // A - The element that should be after the insertion point
969 // M - Indicates element was moved
971 let idx = self.wrap_index(self.tail + i);
973 let distance_to_tail = i;
974 let distance_to_head = self.len() - i;
976 let contiguous = self.is_contiguous();
978 match (contiguous, distance_to_tail <= distance_to_head, idx >= self.tail) {
979 (true, true, _) if i == 0 => {
984 // [A o o o o o o . . . . . . . . .]
987 // [A o o o o o o o . . . . . I]
990 self.tail = self.wrap_index(self.tail - 1);
992 (true, true, _) => unsafe {
993 // contiguous, insert closer to tail:
996 // [. . . o o A o o o o . . . . . .]
999 // [. . o o I A o o o o . . . . . .]
1002 // contiguous, insert closer to tail and tail is 0:
1006 // [o o A o o o o . . . . . . . . .]
1009 // [o I A o o o o o . . . . . . . o]
1012 let new_tail = self.wrap_index(self.tail - 1);
1014 self.copy(new_tail, self.tail, 1);
1015 // Already moved the tail, so we only copy `i - 1` elements.
1016 self.copy(self.tail, self.tail + 1, i - 1);
1018 self.tail = new_tail;
1020 (true, false, _) => unsafe {
1021 // contiguous, insert closer to head:
1024 // [. . . o o o o A o o . . . . . .]
1027 // [. . . o o o o I A o o . . . . .]
1030 self.copy(idx + 1, idx, self.head - idx);
1031 self.head = self.wrap_index(self.head + 1);
1033 (false, true, true) => unsafe {
1034 // discontiguous, insert closer to tail, tail section:
1037 // [o o o o o o . . . . . o o A o o]
1040 // [o o o o o o . . . . o o I A o o]
1043 self.copy(self.tail - 1, self.tail, i);
1046 (false, false, true) => unsafe {
1047 // discontiguous, insert closer to head, tail section:
1050 // [o o . . . . . . . o o o o o A o]
1053 // [o o o . . . . . . o o o o o I A]
1056 // copy elements up to new head
1057 self.copy(1, 0, self.head);
1059 // copy last element into empty spot at bottom of buffer
1060 self.copy(0, self.cap - 1, 1);
1062 // move elements from idx to end forward not including ^ element
1063 self.copy(idx + 1, idx, self.cap - 1 - idx);
1067 (false, true, false) if idx == 0 => unsafe {
1068 // discontiguous, insert is closer to tail, head section,
1069 // and is at index zero in the internal buffer:
1072 // [A o o o o o o o o o . . . o o o]
1075 // [A o o o o o o o o o . . o o o I]
1078 // copy elements up to new tail
1079 self.copy(self.tail - 1, self.tail, self.cap - self.tail);
1081 // copy last element into empty spot at bottom of buffer
1082 self.copy(self.cap - 1, 0, 1);
1086 (false, true, false) => unsafe {
1087 // discontiguous, insert closer to tail, head section:
1090 // [o o o A o o o o o o . . . o o o]
1093 // [o o I A o o o o o o . . o o o o]
1096 // copy elements up to new tail
1097 self.copy(self.tail - 1, self.tail, self.cap - self.tail);
1099 // copy last element into empty spot at bottom of buffer
1100 self.copy(self.cap - 1, 0, 1);
1102 // move elements from idx-1 to end forward not including ^ element
1103 self.copy(0, 1, idx - 1);
1107 (false, false, false) => unsafe {
1108 // discontiguous, insert closer to head, head section:
1111 // [o o o o A o o . . . . . . o o o]
1114 // [o o o o I A o o . . . . . o o o]
1117 self.copy(idx + 1, idx, self.head - idx);
1122 // tail might've been changed so we need to recalculate
1123 let new_idx = self.wrap_index(self.tail + i);
1125 self.buffer_write(new_idx, t);
1129 /// Removes and returns the element at position `i` from the ringbuf.
1130 /// Whichever end is closer to the removal point will be moved to make
1131 /// room, and all the affected elements will be moved to new positions.
1132 /// Returns `None` if `i` is out of bounds.
1136 /// use std::collections::RingBuf;
1138 /// let mut buf = RingBuf::new();
1139 /// buf.push_back(5);
1140 /// buf.push_back(10);
1141 /// buf.push_back(12);
1142 /// buf.push_back(15);
1144 /// assert_eq!(Some(&15), buf.get(2));
1146 #[stable(feature = "rust1", since = "1.0.0")]
1147 pub fn remove(&mut self, i: uint) -> Option<T> {
1148 if self.is_empty() || self.len() <= i {
1152 // There are three main cases:
1153 // Elements are contiguous
1154 // Elements are discontiguous and the removal is in the tail section
1155 // Elements are discontiguous and the removal is in the head section
1156 // - special case when elements are technically contiguous,
1157 // but self.head = 0
1159 // For each of those there are two more cases:
1160 // Insert is closer to tail
1161 // Insert is closer to head
1163 // Key: H - self.head
1165 // o - Valid element
1166 // x - Element marked for removal
1167 // R - Indicates element that is being removed
1168 // M - Indicates element was moved
1170 let idx = self.wrap_index(self.tail + i);
1173 Some(self.buffer_read(idx))
1176 let distance_to_tail = i;
1177 let distance_to_head = self.len() - i;
1179 let contiguous = self.is_contiguous();
1181 match (contiguous, distance_to_tail <= distance_to_head, idx >= self.tail) {
1182 (true, true, _) => unsafe {
1183 // contiguous, remove closer to tail:
1186 // [. . . o o x o o o o . . . . . .]
1189 // [. . . . o o o o o o . . . . . .]
1192 self.copy(self.tail + 1, self.tail, i);
1195 (true, false, _) => unsafe {
1196 // contiguous, remove closer to head:
1199 // [. . . o o o o x o o . . . . . .]
1202 // [. . . o o o o o o . . . . . . .]
1205 self.copy(idx, idx + 1, self.head - idx - 1);
1208 (false, true, true) => unsafe {
1209 // discontiguous, remove closer to tail, tail section:
1212 // [o o o o o o . . . . . o o x o o]
1215 // [o o o o o o . . . . . . o o o o]
1218 self.copy(self.tail + 1, self.tail, i);
1219 self.tail = self.wrap_index(self.tail + 1);
1221 (false, false, false) => unsafe {
1222 // discontiguous, remove closer to head, head section:
1225 // [o o o o x o o . . . . . . o o o]
1228 // [o o o o o o . . . . . . . o o o]
1231 self.copy(idx, idx + 1, self.head - idx - 1);
1234 (false, false, true) => unsafe {
1235 // discontiguous, remove closer to head, tail section:
1238 // [o o o . . . . . . o o o o o x o]
1241 // [o o . . . . . . . o o o o o o o]
1244 // or quasi-discontiguous, remove next to head, tail section:
1247 // [. . . . . . . . . o o o o o x o]
1250 // [. . . . . . . . . o o o o o o .]
1253 // draw in elements in the tail section
1254 self.copy(idx, idx + 1, self.cap - idx - 1);
1256 // Prevents underflow.
1258 // copy first element into empty spot
1259 self.copy(self.cap - 1, 0, 1);
1261 // move elements in the head section backwards
1262 self.copy(0, 1, self.head - 1);
1265 self.head = self.wrap_index(self.head - 1);
1267 (false, true, false) => unsafe {
1268 // discontiguous, remove closer to tail, head section:
1271 // [o o x o o o o o o o . . . o o o]
1274 // [o o o o o o o o o o . . . . o o]
1277 // draw in elements up to idx
1278 self.copy(1, 0, idx);
1280 // copy last element into empty spot
1281 self.copy(0, self.cap - 1, 1);
1283 // move elements from tail to end forward, excluding the last one
1284 self.copy(self.tail + 1, self.tail, self.cap - self.tail - 1);
1286 self.tail = self.wrap_index(self.tail + 1);
1294 impl<T: Clone> RingBuf<T> {
1295 /// Modifies the ringbuf in-place so that `len()` is equal to new_len,
1296 /// either by removing excess elements or by appending copies of a value to the back.
1301 /// use std::collections::RingBuf;
1303 /// let mut buf = RingBuf::new();
1304 /// buf.push_back(5);
1305 /// buf.push_back(10);
1306 /// buf.push_back(15);
1307 /// buf.resize(2, 0);
1308 /// buf.resize(6, 20);
1309 /// for (a, b) in [5, 10, 20, 20, 20, 20].iter().zip(buf.iter()) {
1310 /// assert_eq!(a, b);
1313 #[unstable(feature = "collections",
1314 reason = "matches collection reform specification; waiting on panic semantics")]
1315 pub fn resize(&mut self, new_len: uint, value: T) {
1316 let len = self.len();
1319 self.extend(repeat(value).take(new_len - len))
1321 self.truncate(new_len);
1326 /// Returns the index in the underlying buffer for a given logical element index.
1328 fn wrap_index(index: uint, size: uint) -> uint {
1329 // size is always a power of 2
1333 /// Calculate the number of elements left to be read in the buffer
1335 fn count(tail: uint, head: uint, size: uint) -> uint {
1336 // size is always a power of 2
1337 (head - tail) & (size - 1)
1340 /// `RingBuf` iterator.
1341 #[stable(feature = "rust1", since = "1.0.0")]
1342 pub struct Iter<'a, T:'a> {
1348 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1349 impl<'a, T> Clone for Iter<'a, T> {
1350 fn clone(&self) -> Iter<'a, T> {
1359 #[stable(feature = "rust1", since = "1.0.0")]
1360 impl<'a, T> Iterator for Iter<'a, T> {
1364 fn next(&mut self) -> Option<&'a T> {
1365 if self.tail == self.head {
1368 let tail = self.tail;
1369 self.tail = wrap_index(self.tail + 1, self.ring.len());
1370 unsafe { Some(self.ring.get_unchecked(tail)) }
1374 fn size_hint(&self) -> (uint, Option<uint>) {
1375 let len = count(self.tail, self.head, self.ring.len());
1380 #[stable(feature = "rust1", since = "1.0.0")]
1381 impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
1383 fn next_back(&mut self) -> Option<&'a T> {
1384 if self.tail == self.head {
1387 self.head = wrap_index(self.head - 1, self.ring.len());
1388 unsafe { Some(self.ring.get_unchecked(self.head)) }
1392 #[stable(feature = "rust1", since = "1.0.0")]
1393 impl<'a, T> ExactSizeIterator for Iter<'a, T> {}
1395 #[stable(feature = "rust1", since = "1.0.0")]
1396 impl<'a, T> RandomAccessIterator for Iter<'a, T> {
1398 fn indexable(&self) -> uint {
1399 let (len, _) = self.size_hint();
1404 fn idx(&mut self, j: uint) -> Option<&'a T> {
1405 if j >= self.indexable() {
1408 let idx = wrap_index(self.tail + j, self.ring.len());
1409 unsafe { Some(self.ring.get_unchecked(idx)) }
1414 // FIXME This was implemented differently from Iter because of a problem
1415 // with returning the mutable reference. I couldn't find a way to
1416 // make the lifetime checker happy so, but there should be a way.
1417 /// `RingBuf` mutable iterator.
1418 #[stable(feature = "rust1", since = "1.0.0")]
1419 pub struct IterMut<'a, T:'a> {
1424 marker: marker::ContravariantLifetime<'a>,
1427 #[stable(feature = "rust1", since = "1.0.0")]
1428 impl<'a, T> Iterator for IterMut<'a, T> {
1429 type Item = &'a mut T;
1432 fn next(&mut self) -> Option<&'a mut T> {
1433 if self.tail == self.head {
1436 let tail = self.tail;
1437 self.tail = wrap_index(self.tail + 1, self.cap);
1440 Some(&mut *self.ptr.offset(tail as int))
1445 fn size_hint(&self) -> (uint, Option<uint>) {
1446 let len = count(self.tail, self.head, self.cap);
1451 #[stable(feature = "rust1", since = "1.0.0")]
1452 impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
1454 fn next_back(&mut self) -> Option<&'a mut T> {
1455 if self.tail == self.head {
1458 self.head = wrap_index(self.head - 1, self.cap);
1461 Some(&mut *self.ptr.offset(self.head as int))
1466 #[stable(feature = "rust1", since = "1.0.0")]
1467 impl<'a, T> ExactSizeIterator for IterMut<'a, T> {}
1469 /// A by-value RingBuf iterator
1470 #[stable(feature = "rust1", since = "1.0.0")]
1471 pub struct IntoIter<T> {
1475 #[stable(feature = "rust1", since = "1.0.0")]
1476 impl<T> Iterator for IntoIter<T> {
1480 fn next(&mut self) -> Option<T> {
1481 self.inner.pop_front()
1485 fn size_hint(&self) -> (uint, Option<uint>) {
1486 let len = self.inner.len();
1491 #[stable(feature = "rust1", since = "1.0.0")]
1492 impl<T> DoubleEndedIterator for IntoIter<T> {
1494 fn next_back(&mut self) -> Option<T> {
1495 self.inner.pop_back()
1499 #[stable(feature = "rust1", since = "1.0.0")]
1500 impl<T> ExactSizeIterator for IntoIter<T> {}
1502 /// A draining RingBuf iterator
1503 #[unstable(feature = "collections",
1504 reason = "matches collection reform specification, waiting for dust to settle")]
1505 pub struct Drain<'a, T: 'a> {
1506 inner: &'a mut RingBuf<T>,
1509 #[unsafe_destructor]
1510 #[stable(feature = "rust1", since = "1.0.0")]
1511 impl<'a, T: 'a> Drop for Drain<'a, T> {
1512 fn drop(&mut self) {
1513 for _ in self.by_ref() {}
1514 self.inner.head = 0;
1515 self.inner.tail = 0;
1519 #[stable(feature = "rust1", since = "1.0.0")]
1520 impl<'a, T: 'a> Iterator for Drain<'a, T> {
1524 fn next(&mut self) -> Option<T> {
1525 self.inner.pop_front()
1529 fn size_hint(&self) -> (uint, Option<uint>) {
1530 let len = self.inner.len();
1535 #[stable(feature = "rust1", since = "1.0.0")]
1536 impl<'a, T: 'a> DoubleEndedIterator for Drain<'a, T> {
1538 fn next_back(&mut self) -> Option<T> {
1539 self.inner.pop_back()
1543 #[stable(feature = "rust1", since = "1.0.0")]
1544 impl<'a, T: 'a> ExactSizeIterator for Drain<'a, T> {}
1546 #[stable(feature = "rust1", since = "1.0.0")]
1547 impl<A: PartialEq> PartialEq for RingBuf<A> {
1548 fn eq(&self, other: &RingBuf<A>) -> bool {
1549 self.len() == other.len() &&
1550 self.iter().zip(other.iter()).all(|(a, b)| a.eq(b))
1554 #[stable(feature = "rust1", since = "1.0.0")]
1555 impl<A: Eq> Eq for RingBuf<A> {}
1557 #[stable(feature = "rust1", since = "1.0.0")]
1558 impl<A: PartialOrd> PartialOrd for RingBuf<A> {
1559 fn partial_cmp(&self, other: &RingBuf<A>) -> Option<Ordering> {
1560 iter::order::partial_cmp(self.iter(), other.iter())
1564 #[stable(feature = "rust1", since = "1.0.0")]
1565 impl<A: Ord> Ord for RingBuf<A> {
1567 fn cmp(&self, other: &RingBuf<A>) -> Ordering {
1568 iter::order::cmp(self.iter(), other.iter())
1572 #[stable(feature = "rust1", since = "1.0.0")]
1573 impl<S: Writer + Hasher, A: Hash<S>> Hash<S> for RingBuf<A> {
1574 fn hash(&self, state: &mut S) {
1575 self.len().hash(state);
1576 for elt in self.iter() {
1582 #[stable(feature = "rust1", since = "1.0.0")]
1583 impl<A> Index<uint> for RingBuf<A> {
1587 fn index<'a>(&'a self, i: &uint) -> &'a A {
1588 self.get(*i).expect("Out of bounds access")
1592 #[stable(feature = "rust1", since = "1.0.0")]
1593 impl<A> IndexMut<uint> for RingBuf<A> {
1597 fn index_mut<'a>(&'a mut self, i: &uint) -> &'a mut A {
1598 self.get_mut(*i).expect("Out of bounds access")
1602 #[stable(feature = "rust1", since = "1.0.0")]
1603 impl<A> FromIterator<A> for RingBuf<A> {
1604 fn from_iter<T: Iterator<Item=A>>(iterator: T) -> RingBuf<A> {
1605 let (lower, _) = iterator.size_hint();
1606 let mut deq = RingBuf::with_capacity(lower);
1607 deq.extend(iterator);
1612 impl<T> IntoIterator for RingBuf<T> {
1613 type Iter = IntoIter<T>;
1615 fn into_iter(self) -> IntoIter<T> {
1620 impl<'a, T> IntoIterator for &'a RingBuf<T> {
1621 type Iter = Iter<'a, T>;
1623 fn into_iter(self) -> Iter<'a, T> {
1628 impl<'a, T> IntoIterator for &'a mut RingBuf<T> {
1629 type Iter = IterMut<'a, T>;
1631 fn into_iter(mut self) -> IterMut<'a, T> {
1636 #[stable(feature = "rust1", since = "1.0.0")]
1637 impl<A> Extend<A> for RingBuf<A> {
1638 fn extend<T: Iterator<Item=A>>(&mut self, mut iterator: T) {
1639 for elt in iterator {
1640 self.push_back(elt);
1645 #[stable(feature = "rust1", since = "1.0.0")]
1646 impl<T: fmt::Debug> fmt::Debug for RingBuf<T> {
1647 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1648 try!(write!(f, "RingBuf ["));
1650 for (i, e) in self.iter().enumerate() {
1651 if i != 0 { try!(write!(f, ", ")); }
1652 try!(write!(f, "{:?}", *e));
1662 use self::Taggypar::*;
1665 use std::fmt::Debug;
1666 use std::hash::{self, SipHasher};
1673 #[allow(deprecated)]
1675 let mut d = RingBuf::new();
1676 assert_eq!(d.len(), 0u);
1680 assert_eq!(d.len(), 3u);
1682 assert_eq!(d.len(), 4u);
1683 assert_eq!(*d.front().unwrap(), 42);
1684 assert_eq!(*d.back().unwrap(), 137);
1685 let mut i = d.pop_front();
1686 assert_eq!(i, Some(42));
1688 assert_eq!(i, Some(137));
1690 assert_eq!(i, Some(137));
1692 assert_eq!(i, Some(17));
1693 assert_eq!(d.len(), 0u);
1695 assert_eq!(d.len(), 1u);
1697 assert_eq!(d.len(), 2u);
1699 assert_eq!(d.len(), 3u);
1701 assert_eq!(d.len(), 4u);
1706 assert_eq!(d[0], 1);
1707 assert_eq!(d[1], 2);
1708 assert_eq!(d[2], 3);
1709 assert_eq!(d[3], 4);
1713 fn test_parameterized<T:Clone + PartialEq + Debug>(a: T, b: T, c: T, d: T) {
1714 let mut deq = RingBuf::new();
1715 assert_eq!(deq.len(), 0);
1716 deq.push_front(a.clone());
1717 deq.push_front(b.clone());
1718 deq.push_back(c.clone());
1719 assert_eq!(deq.len(), 3);
1720 deq.push_back(d.clone());
1721 assert_eq!(deq.len(), 4);
1722 assert_eq!((*deq.front().unwrap()).clone(), b.clone());
1723 assert_eq!((*deq.back().unwrap()).clone(), d.clone());
1724 assert_eq!(deq.pop_front().unwrap(), b.clone());
1725 assert_eq!(deq.pop_back().unwrap(), d.clone());
1726 assert_eq!(deq.pop_back().unwrap(), c.clone());
1727 assert_eq!(deq.pop_back().unwrap(), a.clone());
1728 assert_eq!(deq.len(), 0);
1729 deq.push_back(c.clone());
1730 assert_eq!(deq.len(), 1);
1731 deq.push_front(b.clone());
1732 assert_eq!(deq.len(), 2);
1733 deq.push_back(d.clone());
1734 assert_eq!(deq.len(), 3);
1735 deq.push_front(a.clone());
1736 assert_eq!(deq.len(), 4);
1737 assert_eq!(deq[0].clone(), a.clone());
1738 assert_eq!(deq[1].clone(), b.clone());
1739 assert_eq!(deq[2].clone(), c.clone());
1740 assert_eq!(deq[3].clone(), d.clone());
1744 fn test_push_front_grow() {
1745 let mut deq = RingBuf::new();
1749 assert_eq!(deq.len(), 66);
1752 assert_eq!(deq[i], 65 - i);
1755 let mut deq = RingBuf::new();
1761 assert_eq!(deq[i], i);
1767 let mut deq = RingBuf::new();
1771 assert_eq!(deq[1], 2);
1776 fn test_index_out_of_bounds() {
1777 let mut deq = RingBuf::new();
1785 fn bench_new(b: &mut test::Bencher) {
1787 let ring: RingBuf<u64> = RingBuf::new();
1788 test::black_box(ring);
1793 fn bench_push_back_100(b: &mut test::Bencher) {
1794 let mut deq = RingBuf::with_capacity(101);
1805 fn bench_push_front_100(b: &mut test::Bencher) {
1806 let mut deq = RingBuf::with_capacity(101);
1817 fn bench_pop_back_100(b: &mut test::Bencher) {
1818 let mut deq: RingBuf<i32> = RingBuf::with_capacity(101);
1823 while !deq.is_empty() {
1824 test::black_box(deq.pop_back());
1830 fn bench_pop_front_100(b: &mut test::Bencher) {
1831 let mut deq: RingBuf<i32> = RingBuf::with_capacity(101);
1836 while !deq.is_empty() {
1837 test::black_box(deq.pop_front());
1843 fn bench_grow_1025(b: &mut test::Bencher) {
1845 let mut deq = RingBuf::new();
1849 test::black_box(deq);
1854 fn bench_iter_1000(b: &mut test::Bencher) {
1855 let ring: RingBuf<i32> = (0..1000).collect();
1859 for &i in ring.iter() {
1862 test::black_box(sum);
1867 fn bench_mut_iter_1000(b: &mut test::Bencher) {
1868 let mut ring: RingBuf<i32> = (0..1000).collect();
1872 for i in ring.iter_mut() {
1875 test::black_box(sum);
1879 #[derive(Clone, PartialEq, Debug)]
1883 Three(i32, i32, i32),
1886 #[derive(Clone, PartialEq, Debug)]
1890 Threepar(i32, i32, i32),
1893 #[derive(Clone, PartialEq, Debug)]
1901 fn test_param_int() {
1902 test_parameterized::<i32>(5, 72, 64, 175);
1906 fn test_param_taggy() {
1907 test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
1911 fn test_param_taggypar() {
1912 test_parameterized::<Taggypar<i32>>(Onepar::<i32>(1),
1913 Twopar::<i32>(1, 2),
1914 Threepar::<i32>(1, 2, 3),
1915 Twopar::<i32>(17, 42));
1919 fn test_param_reccy() {
1920 let reccy1 = RecCy { x: 1, y: 2, t: One(1) };
1921 let reccy2 = RecCy { x: 345, y: 2, t: Two(1, 2) };
1922 let reccy3 = RecCy { x: 1, y: 777, t: Three(1, 2, 3) };
1923 let reccy4 = RecCy { x: 19, y: 252, t: Two(17, 42) };
1924 test_parameterized::<RecCy>(reccy1, reccy2, reccy3, reccy4);
1928 fn test_with_capacity() {
1929 let mut d = RingBuf::with_capacity(0);
1931 assert_eq!(d.len(), 1);
1932 let mut d = RingBuf::with_capacity(50);
1934 assert_eq!(d.len(), 1);
1938 fn test_with_capacity_non_power_two() {
1939 let mut d3 = RingBuf::with_capacity(3);
1944 assert_eq!(d3.pop_front(), Some(1));
1946 assert_eq!(d3.front(), None);
1953 assert_eq!(d3.pop_front(), Some(3));
1955 // Pushing the lo past half way point to trigger
1956 // the 'B' scenario for growth
1963 // There used to be a bug here about how the
1964 // RingBuf made growth assumptions about the
1965 // underlying Vec which didn't hold and lead
1967 // (Vec grows to next power of two)
1968 //good- [9, 12, 15, X, X, X, X, |6]
1969 //bug- [15, 12, X, X, X, |6, X, X]
1970 assert_eq!(d3.pop_front(), Some(6));
1972 // Which leads us to the following state which
1973 // would be a failure case.
1974 //bug- [15, 12, X, X, X, X, |X, X]
1975 assert_eq!(d3.front(), Some(&9));
1979 fn test_reserve_exact() {
1980 let mut d = RingBuf::new();
1982 d.reserve_exact(50);
1983 assert!(d.capacity() >= 51);
1984 let mut d = RingBuf::new();
1986 d.reserve_exact(50);
1987 assert!(d.capacity() >= 51);
1992 let mut d = RingBuf::new();
1995 assert!(d.capacity() >= 51);
1996 let mut d = RingBuf::new();
1999 assert!(d.capacity() >= 51);
2004 let mut d: RingBuf<i32> = (0..5).collect();
2007 assert_eq!(d.iter().map(|&x|x).collect::<Vec<i32>>(), vec!(4, 2, 3, 1));
2012 let mut d = RingBuf::new();
2013 assert_eq!(d.iter().next(), None);
2014 assert_eq!(d.iter().size_hint(), (0, Some(0)));
2020 let b: &[_] = &[&0,&1,&2,&3,&4];
2021 assert_eq!(d.iter().collect::<Vec<&i32>>(), b);
2028 let b: &[_] = &[&8,&7,&6,&0,&1,&2,&3,&4];
2029 assert_eq!(d.iter().collect::<Vec<&i32>>(), b);
2032 let mut it = d.iter();
2033 let mut len = d.len();
2037 _ => { len -= 1; assert_eq!(it.size_hint(), (len, Some(len))) }
2043 fn test_rev_iter() {
2044 let mut d = RingBuf::new();
2045 assert_eq!(d.iter().rev().next(), None);
2051 let b: &[_] = &[&4,&3,&2,&1,&0];
2052 assert_eq!(d.iter().rev().collect::<Vec<&i32>>(), b);
2058 let b: &[_] = &[&4,&3,&2,&1,&0,&6,&7,&8];
2059 assert_eq!(d.iter().rev().collect::<Vec<&i32>>(), b);
2063 fn test_mut_rev_iter_wrap() {
2064 let mut d = RingBuf::with_capacity(3);
2065 assert!(d.iter_mut().rev().next().is_none());
2070 assert_eq!(d.pop_front(), Some(1));
2073 assert_eq!(d.iter_mut().rev().map(|x| *x).collect::<Vec<i32>>(),
2078 fn test_mut_iter() {
2079 let mut d = RingBuf::new();
2080 assert!(d.iter_mut().next().is_none());
2086 for (i, elt) in d.iter_mut().enumerate() {
2087 assert_eq!(*elt, 2 - i);
2092 let mut it = d.iter_mut();
2093 assert_eq!(*it.next().unwrap(), 0);
2094 assert_eq!(*it.next().unwrap(), 1);
2095 assert_eq!(*it.next().unwrap(), 2);
2096 assert!(it.next().is_none());
2101 fn test_mut_rev_iter() {
2102 let mut d = RingBuf::new();
2103 assert!(d.iter_mut().rev().next().is_none());
2109 for (i, elt) in d.iter_mut().rev().enumerate() {
2110 assert_eq!(*elt, i);
2115 let mut it = d.iter_mut().rev();
2116 assert_eq!(*it.next().unwrap(), 0);
2117 assert_eq!(*it.next().unwrap(), 1);
2118 assert_eq!(*it.next().unwrap(), 2);
2119 assert!(it.next().is_none());
2124 fn test_into_iter() {
2128 let d: RingBuf<i32> = RingBuf::new();
2129 let mut iter = d.into_iter();
2131 assert_eq!(iter.size_hint(), (0, Some(0)));
2132 assert_eq!(iter.next(), None);
2133 assert_eq!(iter.size_hint(), (0, Some(0)));
2138 let mut d = RingBuf::new();
2143 let b = vec![0,1,2,3,4];
2144 assert_eq!(d.into_iter().collect::<Vec<i32>>(), b);
2149 let mut d = RingBuf::new();
2157 let b = vec![8,7,6,0,1,2,3,4];
2158 assert_eq!(d.into_iter().collect::<Vec<i32>>(), b);
2163 let mut d = RingBuf::new();
2171 let mut it = d.into_iter();
2172 assert_eq!(it.size_hint(), (8, Some(8)));
2173 assert_eq!(it.next(), Some(8));
2174 assert_eq!(it.size_hint(), (7, Some(7)));
2175 assert_eq!(it.next_back(), Some(4));
2176 assert_eq!(it.size_hint(), (6, Some(6)));
2177 assert_eq!(it.next(), Some(7));
2178 assert_eq!(it.size_hint(), (5, Some(5)));
2187 let mut d: RingBuf<i32> = RingBuf::new();
2190 let mut iter = d.drain();
2192 assert_eq!(iter.size_hint(), (0, Some(0)));
2193 assert_eq!(iter.next(), None);
2194 assert_eq!(iter.size_hint(), (0, Some(0)));
2197 assert!(d.is_empty());
2202 let mut d = RingBuf::new();
2207 assert_eq!(d.drain().collect::<Vec<_>>(), [0, 1, 2, 3, 4]);
2208 assert!(d.is_empty());
2213 let mut d = RingBuf::new();
2221 assert_eq!(d.drain().collect::<Vec<_>>(), [8,7,6,0,1,2,3,4]);
2222 assert!(d.is_empty());
2227 let mut d: RingBuf<i32> = RingBuf::new();
2236 let mut it = d.drain();
2237 assert_eq!(it.size_hint(), (8, Some(8)));
2238 assert_eq!(it.next(), Some(8));
2239 assert_eq!(it.size_hint(), (7, Some(7)));
2240 assert_eq!(it.next_back(), Some(4));
2241 assert_eq!(it.size_hint(), (6, Some(6)));
2242 assert_eq!(it.next(), Some(7));
2243 assert_eq!(it.size_hint(), (5, Some(5)));
2245 assert!(d.is_empty());
2250 fn test_from_iter() {
2252 let v = vec!(1,2,3,4,5,6,7);
2253 let deq: RingBuf<i32> = v.iter().map(|&x| x).collect();
2254 let u: Vec<i32> = deq.iter().map(|&x| x).collect();
2257 let seq = iter::count(0u, 2).take(256);
2258 let deq: RingBuf<uint> = seq.collect();
2259 for (i, &x) in deq.iter().enumerate() {
2262 assert_eq!(deq.len(), 256);
2267 let mut d = RingBuf::new();
2272 assert_eq!(d.len(), 4u);
2273 let mut e = d.clone();
2274 assert_eq!(e.len(), 4u);
2275 while !d.is_empty() {
2276 assert_eq!(d.pop_back(), e.pop_back());
2278 assert_eq!(d.len(), 0u);
2279 assert_eq!(e.len(), 0u);
2284 let mut d = RingBuf::new();
2285 assert!(d == RingBuf::with_capacity(0));
2290 let mut e = RingBuf::with_capacity(0);
2300 assert!(e == RingBuf::new());
2305 let mut x = RingBuf::new();
2306 let mut y = RingBuf::new();
2318 assert!(hash::hash::<_, SipHasher>(&x) == hash::hash::<_, SipHasher>(&y));
2323 let x = RingBuf::new();
2324 let mut y = RingBuf::new();
2336 let ringbuf: RingBuf<i32> = (0..10).collect();
2337 assert_eq!(format!("{:?}", ringbuf), "RingBuf [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
2339 let ringbuf: RingBuf<&str> = vec!["just", "one", "test", "more"].iter()
2342 assert_eq!(format!("{:?}", ringbuf), "RingBuf [\"just\", \"one\", \"test\", \"more\"]");
2347 static mut drops: uint = 0;
2349 impl Drop for Elem {
2350 fn drop(&mut self) {
2351 unsafe { drops += 1; }
2355 let mut ring = RingBuf::new();
2356 ring.push_back(Elem);
2357 ring.push_front(Elem);
2358 ring.push_back(Elem);
2359 ring.push_front(Elem);
2362 assert_eq!(unsafe {drops}, 4);
2366 fn test_drop_with_pop() {
2367 static mut drops: uint = 0;
2369 impl Drop for Elem {
2370 fn drop(&mut self) {
2371 unsafe { drops += 1; }
2375 let mut ring = RingBuf::new();
2376 ring.push_back(Elem);
2377 ring.push_front(Elem);
2378 ring.push_back(Elem);
2379 ring.push_front(Elem);
2381 drop(ring.pop_back());
2382 drop(ring.pop_front());
2383 assert_eq!(unsafe {drops}, 2);
2386 assert_eq!(unsafe {drops}, 4);
2390 fn test_drop_clear() {
2391 static mut drops: uint = 0;
2393 impl Drop for Elem {
2394 fn drop(&mut self) {
2395 unsafe { drops += 1; }
2399 let mut ring = RingBuf::new();
2400 ring.push_back(Elem);
2401 ring.push_front(Elem);
2402 ring.push_back(Elem);
2403 ring.push_front(Elem);
2405 assert_eq!(unsafe {drops}, 4);
2408 assert_eq!(unsafe {drops}, 4);
2412 fn test_reserve_grow() {
2413 // test growth path A
2414 // [T o o H] -> [T o o H . . . . ]
2415 let mut ring = RingBuf::with_capacity(4);
2421 assert_eq!(ring.pop_front(), Some(i));
2424 // test growth path B
2425 // [H T o o] -> [. T o o H . . . ]
2426 let mut ring = RingBuf::with_capacity(4);
2429 assert_eq!(ring.pop_front(), Some(i));
2436 assert_eq!(ring.pop_front(), Some(i));
2439 // test growth path C
2440 // [o o H T] -> [o o H . . . . T ]
2441 let mut ring = RingBuf::with_capacity(4);
2444 assert_eq!(ring.pop_front(), Some(i));
2451 assert_eq!(ring.pop_front(), Some(i));
2457 let mut ring = RingBuf::new();
2459 assert_eq!(ring.get(0), Some(&0));
2460 assert_eq!(ring.get(1), None);
2463 assert_eq!(ring.get(0), Some(&0));
2464 assert_eq!(ring.get(1), Some(&1));
2465 assert_eq!(ring.get(2), None);
2468 assert_eq!(ring.get(0), Some(&0));
2469 assert_eq!(ring.get(1), Some(&1));
2470 assert_eq!(ring.get(2), Some(&2));
2471 assert_eq!(ring.get(3), None);
2473 assert_eq!(ring.pop_front(), Some(0));
2474 assert_eq!(ring.get(0), Some(&1));
2475 assert_eq!(ring.get(1), Some(&2));
2476 assert_eq!(ring.get(2), None);
2478 assert_eq!(ring.pop_front(), Some(1));
2479 assert_eq!(ring.get(0), Some(&2));
2480 assert_eq!(ring.get(1), None);
2482 assert_eq!(ring.pop_front(), Some(2));
2483 assert_eq!(ring.get(0), None);
2484 assert_eq!(ring.get(1), None);
2489 let mut ring = RingBuf::new();
2494 match ring.get_mut(1) {
2499 assert_eq!(ring.get_mut(0), Some(&mut 0));
2500 assert_eq!(ring.get_mut(1), Some(&mut -1));
2501 assert_eq!(ring.get_mut(2), Some(&mut 2));
2502 assert_eq!(ring.get_mut(3), None);
2504 assert_eq!(ring.pop_front(), Some(0));
2505 assert_eq!(ring.get_mut(0), Some(&mut -1));
2506 assert_eq!(ring.get_mut(1), Some(&mut 2));
2507 assert_eq!(ring.get_mut(2), None);
2511 fn test_swap_front_back_remove() {
2512 fn test(back: bool) {
2513 // This test checks that every single combination of tail position and length is tested.
2514 // Capacity 15 should be large enough to cover every case.
2515 let mut tester = RingBuf::with_capacity(15);
2516 let usable_cap = tester.capacity();
2517 let final_len = usable_cap / 2;
2519 for len in 0..final_len {
2520 let expected = if back {
2523 (0..len).rev().collect()
2525 for tail_pos in 0..usable_cap {
2526 tester.tail = tail_pos;
2527 tester.head = tail_pos;
2529 for i in 0..len * 2 {
2530 tester.push_front(i);
2533 assert_eq!(tester.swap_back_remove(i), Some(len * 2 - 1 - i));
2536 for i in 0..len * 2 {
2537 tester.push_back(i);
2540 let idx = tester.len() - 1 - i;
2541 assert_eq!(tester.swap_front_remove(idx), Some(len * 2 - 1 - i));
2544 assert!(tester.tail < tester.cap);
2545 assert!(tester.head < tester.cap);
2546 assert_eq!(tester, expected);
2556 // This test checks that every single combination of tail position, length, and
2557 // insertion position is tested. Capacity 15 should be large enough to cover every case.
2559 let mut tester = RingBuf::with_capacity(15);
2560 // can't guarantee we got 15, so have to get what we got.
2561 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
2562 // this test isn't covering what it wants to
2563 let cap = tester.capacity();
2566 // len is the length *after* insertion
2568 // 0, 1, 2, .., len - 1
2569 let expected = iter::count(0, 1).take(len).collect();
2570 for tail_pos in 0..cap {
2571 for to_insert in 0..len {
2572 tester.tail = tail_pos;
2573 tester.head = tail_pos;
2576 tester.push_back(i);
2579 tester.insert(to_insert, to_insert);
2580 assert!(tester.tail < tester.cap);
2581 assert!(tester.head < tester.cap);
2582 assert_eq!(tester, expected);
2590 // This test checks that every single combination of tail position, length, and
2591 // removal position is tested. Capacity 15 should be large enough to cover every case.
2593 let mut tester = RingBuf::with_capacity(15);
2594 // can't guarantee we got 15, so have to get what we got.
2595 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
2596 // this test isn't covering what it wants to
2597 let cap = tester.capacity();
2599 // len is the length *after* removal
2600 for len in 0..cap - 1 {
2601 // 0, 1, 2, .., len - 1
2602 let expected = iter::count(0, 1).take(len).collect();
2603 for tail_pos in 0..cap {
2604 for to_remove in 0..len + 1 {
2605 tester.tail = tail_pos;
2606 tester.head = tail_pos;
2609 tester.push_back(1234);
2611 tester.push_back(i);
2613 if to_remove == len {
2614 tester.push_back(1234);
2616 tester.remove(to_remove);
2617 assert!(tester.tail < tester.cap);
2618 assert!(tester.head < tester.cap);
2619 assert_eq!(tester, expected);
2626 fn test_shrink_to_fit() {
2627 // This test checks that every single combination of head and tail position,
2628 // is tested. Capacity 15 should be large enough to cover every case.
2630 let mut tester = RingBuf::with_capacity(15);
2631 // can't guarantee we got 15, so have to get what we got.
2632 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
2633 // this test isn't covering what it wants to
2634 let cap = tester.capacity();
2636 let max_cap = tester.capacity();
2638 for len in 0..cap + 1 {
2639 // 0, 1, 2, .., len - 1
2640 let expected = iter::count(0, 1).take(len).collect();
2641 for tail_pos in 0..max_cap + 1 {
2642 tester.tail = tail_pos;
2643 tester.head = tail_pos;
2646 tester.push_back(i);
2648 tester.shrink_to_fit();
2649 assert!(tester.capacity() <= cap);
2650 assert!(tester.tail < tester.cap);
2651 assert!(tester.head < tester.cap);
2652 assert_eq!(tester, expected);
2659 let mut ring = RingBuf::new();
2662 assert_eq!(ring.front(), Some(&10));
2664 assert_eq!(ring.front(), Some(&20));
2666 assert_eq!(ring.front(), None);
2670 fn test_as_slices() {
2671 let mut ring: RingBuf<i32> = RingBuf::with_capacity(127);
2672 let cap = ring.capacity() as i32;
2674 let last = cap - first;
2678 let (left, right) = ring.as_slices();
2679 let expected: Vec<_> = (0..i+1).collect();
2680 assert_eq!(left, expected);
2681 assert_eq!(right, []);
2686 let (left, right) = ring.as_slices();
2687 let expected_left: Vec<_> = (-last..j+1).rev().collect();
2688 let expected_right: Vec<_> = (0..first).collect();
2689 assert_eq!(left, expected_left);
2690 assert_eq!(right, expected_right);
2693 assert_eq!(ring.len() as i32, cap);
2694 assert_eq!(ring.capacity() as i32, cap);
2698 fn test_as_mut_slices() {
2699 let mut ring: RingBuf<i32> = RingBuf::with_capacity(127);
2700 let cap = ring.capacity() as i32;
2702 let last = cap - first;
2706 let (left, right) = ring.as_mut_slices();
2707 let expected: Vec<_> = (0..i+1).collect();
2708 assert_eq!(left, expected);
2709 assert_eq!(right, []);
2714 let (left, right) = ring.as_mut_slices();
2715 let expected_left: Vec<_> = (-last..j+1).rev().collect();
2716 let expected_right: Vec<_> = (0..first).collect();
2717 assert_eq!(left, expected_left);
2718 assert_eq!(right, expected_right);
2721 assert_eq!(ring.len() as i32, cap);
2722 assert_eq!(ring.capacity() as i32, cap);