Created
December 8, 2014 19:28
-
-
Save cgaebel/893fc58472511e79d968 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #[inline] | |
| fn memmove(&self, dst: uint, src: uint, len: uint) { | |
| unsafe { | |
| debug_assert!(dst + len <= self.cap, "dst={} src={} len={} cap={}", dst, src, len, self.cap); | |
| debug_assert!(src + len <= self.cap, "dst={} src={} len={} cap={}", dst, src, len, self.cap); | |
| ptr::copy_memory( | |
| self.ptr.offset(dst as int), | |
| self.ptr.offset(src as int) as *const T, | |
| len); | |
| } | |
| } | |
| #[inline] | |
| fn memcpy(&self, dst: uint, src: uint, len: uint) { | |
| unsafe { | |
| debug_assert!(dst + len <= self.cap, "dst={} src={} len={} cap={}", dst, src, len, self.cap); | |
| debug_assert!(src + len <= self.cap, "dst={} src={} len={} cap={}", dst, src, len, self.cap); | |
| ptr::copy_nonoverlapping_memory( | |
| self.ptr.offset(dst as int), | |
| self.ptr.offset(src as int) as *const T, | |
| len); | |
| } | |
| } | |
| /// Inserts an element at position `i` within the ringbuf, shifting all | |
| /// elements after position `i` one position to the right. | |
| /// | |
| /// # Panics | |
| /// | |
| /// Panics if `i` is not between `0` and the ringbuf's length (both | |
| /// bounds inclusive). | |
| /// | |
| /// # Example | |
| /// ```rust | |
| /// use std::collections::RingBuf; | |
| /// | |
| /// let mut buf = RingBuf::new(); | |
| /// buf.push_back(10i); | |
| /// buf.push_back(12); | |
| /// buf.insert(1,11); | |
| /// assert_eq!(Some(&11), buf.get(1)); | |
| /// ``` | |
| pub fn insert(&mut self, i: uint, t: T) { | |
| assert!(i <= self.len(), "index out of bounds"); | |
| if self.is_full() { | |
| self.reserve(1); | |
| debug_assert!(!self.is_full()); | |
| } | |
| // Move the least number of elements in the ring buffer and insert | |
| // Key: I - Insertion element | |
| // A - The element that should be after the insertion point | |
| // M - Indicates element was moved | |
| // H - self.head | |
| // T - self.tail | |
| // o - valid element | |
| // | |
| // T I H | |
| // [. . . o o o o A o o . . . . ] | |
| // T H | |
| // 1 [. . . o o o o I A o o . . . ] | |
| // M M M | |
| // H T I | |
| // [o o o . . . . . . . o o o o o o o A o o ] | |
| // H T | |
| // 2 [o o o o . . . . . . o o o o o o o I A o ] | |
| // M M M M M M | |
| // H T I | |
| // [. . . . . o o o o o o o A o o o] | |
| // H T | |
| // 3 [o . . . . o o o o o o o I A o o] | |
| // M M M M | |
| let idx = self.wrap_index(self.tail + i); | |
| let wraps_around = self.tail > self.head; | |
| let will_wrap_around = wraps_around || self.head + 1 == self.cap; | |
| let idx_in_right_half = idx > self.head; | |
| if wraps_around && idx_in_right_half { | |
| // shuffle LHS down in a wrapped buffer. | |
| let src = 0; | |
| let dst = 1; | |
| let len = self.head; | |
| self.memmove(dst, src, len); | |
| } | |
| if will_wrap_around && idx_in_right_half { | |
| // copy the last element in the buffer to the front | |
| let dst = 0; | |
| let src = self.cap - 1; | |
| let len = 1; | |
| self.memcpy(dst, src, len); | |
| } | |
| { | |
| // shift things to the right of A down the buffer. | |
| let dst = idx + 1; | |
| let src = idx; | |
| let end = if wraps_around { self.head } else { self.cap }; | |
| let len = end - dst; | |
| self.memmove(dst, src, len); | |
| } | |
| // write the element we need to insert. | |
| unsafe { | |
| self.buffer_write(idx, t); | |
| } | |
| let new_head = self.head + 1; | |
| let new_head = self.wrap_index(new_head); | |
| self.head = new_head; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment