From 24bc854b8c95ccf8e229d3982466b71ae778d04e Mon Sep 17 00:00:00 2001 From: Pazzaz Date: Thu, 19 Jul 2018 19:58:06 +0200 Subject: Non-naive implementation for `VecDeque.append` --- src/liballoc/collections/vec_deque.rs | 140 +++++++++++++++++++++++++++++++++- 1 file changed, 138 insertions(+), 2 deletions(-) (limited to 'src/liballoc/collections/vec_deque.rs') diff --git a/src/liballoc/collections/vec_deque.rs b/src/liballoc/collections/vec_deque.rs index ba92b886138..d0b70b5db2d 100644 --- a/src/liballoc/collections/vec_deque.rs +++ b/src/liballoc/collections/vec_deque.rs @@ -1834,8 +1834,144 @@ impl VecDeque { #[inline] #[stable(feature = "append", since = "1.4.0")] pub fn append(&mut self, other: &mut Self) { - // naive impl - self.extend(other.drain(..)); + // Copy from src[i1..i1 + len] to dst[i2..i2 + len]. + // Does not check if the ranges are valid. + unsafe fn copy_part(i1: usize, i2: usize, len: usize, src: &[T], dst: &mut [T]) { + debug_assert!(src.get(i1..i1 + len).is_some() && dst.get(i2..i2 + len).is_some()); + ptr::copy_nonoverlapping(src.as_ptr().add(i1), dst.as_mut_ptr().add(i2), len); + } + + let src_total = other.len(); + + // Guarantees there is space in `self` for `other`. + self.reserve(src_total); + + self.head = { + let dst_start_1 = self.head; + let src_start_1 = other.tail; + let dst_wrap_point = self.cap(); + let src_wrap_point = other.cap(); + + let dst = unsafe { self.buffer_as_mut_slice() }; + let src = unsafe { other.buffer_as_slice() }; + + let src_wraps = other.tail > other.head; + let dst_wraps = dst_start_1 + src_total > dst_wrap_point; + + // When minimizing the amount of calls to `copy_part`, there are + // 6 different cases to handle. Whether src and/or dst wrap are 4 + // combinations and there are 3 distinct cases when they both wrap. + // 6 = 3 + 1 + 1 + 1 + match (src_wraps, dst_wraps) { + (true, true) => { + let dst_before_wrap = dst_wrap_point - dst_start_1; + let src_before_wrap = src_wrap_point - src_start_1; + + if src_before_wrap < dst_before_wrap { + // src + // [o o o . . . . . . o o o] + // 2 3 3 1 1 1 + // + // dst + // [. . . . . . o o . . . .] + // 3 3 H 1 1 1 2 + let src_2 = dst_before_wrap - src_before_wrap; + let dst_start_2 = dst_start_1 + src_before_wrap; + let src_3 = src_total - dst_before_wrap; + + unsafe { + copy_part(src_start_1, dst_start_1, src_before_wrap, src, dst); + copy_part(0, dst_start_2, src_2, src, dst); + copy_part(src_2, 0, src_3, src, dst); + } + src_3 + } else if src_before_wrap > dst_before_wrap { + // src + // [o o o . . . . . o o o o] + // 3 3 3 1 1 2 2 + // + // dst + // [. . . . . . o o o o . .] + // 2 2 3 3 3 H 1 1 + let src_2 = src_before_wrap - dst_before_wrap; + let src_start_2 = src_start_1 + dst_before_wrap; + let src_3 = src_total - src_before_wrap; + + unsafe { + copy_part(src_start_1, dst_start_1, dst_before_wrap, src, dst); + copy_part(src_start_2, 0, src_2, src, dst); + copy_part(0, src_2, src_3, src, dst); + } + src_2 + src_3 + } else { + // src + // [o o . . . . . . . o o o] + // 2 2 1 1 1 + // + // dst + // [. . . . . . . o o . . .] + // 2 2 H 1 1 1 + let src_2 = src_total - src_before_wrap; + + unsafe { + copy_part(src_start_1, dst_start_1, src_before_wrap, src, dst); + copy_part(0, 0, src_2, src, dst); + } + src_2 + } + } + (false, true) => { + // src + // [. . . o o o o o . . . .] + // 1 1 2 2 2 + // + // dst + // [. . . . . . . o o o . .] + // 2 2 2 H 1 1 + let dst_1 = dst_wrap_point - dst_start_1; + let src_start_2 = src_start_1 + dst_1; + let dst_2 = src_total - dst_1; + + unsafe { + copy_part(src_start_1, dst_start_1, dst_1, src, dst); + copy_part(src_start_2, 0, dst_2, src, dst); + } + dst_2 + } + (true, false) => { + // src + // [o o . . . . . . . o o o] + // 2 2 1 1 1 + // + // dst + // [. o o . . . . . . . . .] + // 1 1 1 2 2 H + let src_1 = src_wrap_point - src_start_1; + let dst_start_2 = dst_start_1 + src_1; + let src_2 = src_total - src_1; + + unsafe { + copy_part(src_start_1, dst_start_1, src_1, src, dst); + copy_part(0, dst_start_2, src_2, src, dst); + } + dst_start_1 + src_1 + src_2 + } + (false, false) => { + // src + // [. . . o o o . . . . . .] + // 1 1 1 + // + // dst + // [. o o o o o . . . . . .] + // 1 1 1 H + unsafe { + copy_part(src_start_1, dst_start_1, src_total, src, dst); + } + dst_start_1 + src_total + } + } + }; + other.clear(); } /// Retains only the elements specified by the predicate. -- cgit 1.4.1-3-g733a5 From 6ebd62b8ff86a3ce004894b7fa6d1351f65a5167 Mon Sep 17 00:00:00 2001 From: Pazzaz Date: Sun, 22 Jul 2018 22:18:05 +0200 Subject: Make VecDeque append safer and easier to understand --- src/liballoc/collections/vec_deque.rs | 240 +++++++++++++++++++--------------- 1 file changed, 131 insertions(+), 109 deletions(-) (limited to 'src/liballoc/collections/vec_deque.rs') diff --git a/src/liballoc/collections/vec_deque.rs b/src/liballoc/collections/vec_deque.rs index d0b70b5db2d..7f4fbb99c22 100644 --- a/src/liballoc/collections/vec_deque.rs +++ b/src/liballoc/collections/vec_deque.rs @@ -202,6 +202,20 @@ impl VecDeque { len); } + /// Returns a pair of slices which contain the contents of the buffer not used by the VecDeque. + #[inline] + unsafe fn unused_as_mut_slices<'a>(&'a mut self) -> (&'a mut [T], &'a mut [T]) { + let head = self.head; + let tail = self.tail; + let buf = self.buffer_as_mut_slice(); + if head == tail { + let (before, after) = buf.split_at_mut(head); + (after, before) + } else { + RingSlices::ring_slices(buf, tail, head) + } + } + /// Copies a potentially wrapping block of memory len long from src to dest. /// (abs(dst - src) + len) must be no larger than cap() (There must be at /// most one continuous overlapping region between src and dest). @@ -1834,11 +1848,10 @@ impl VecDeque { #[inline] #[stable(feature = "append", since = "1.4.0")] pub fn append(&mut self, other: &mut Self) { - // Copy from src[i1..i1 + len] to dst[i2..i2 + len]. - // Does not check if the ranges are valid. - unsafe fn copy_part(i1: usize, i2: usize, len: usize, src: &[T], dst: &mut [T]) { - debug_assert!(src.get(i1..i1 + len).is_some() && dst.get(i2..i2 + len).is_some()); - ptr::copy_nonoverlapping(src.as_ptr().add(i1), dst.as_mut_ptr().add(i2), len); + // Copies all values from `src_slice` to the start of `dst_slice`. + unsafe fn copy_whole_slice(src_slice: &[T], dst_slice: &mut [T]) { + let len = src_slice.len(); + ptr::copy_nonoverlapping(src_slice.as_ptr(), dst_slice[..len].as_mut_ptr(), len); } let src_total = other.len(); @@ -1846,132 +1859,141 @@ impl VecDeque { // Guarantees there is space in `self` for `other`. self.reserve(src_total); - self.head = { - let dst_start_1 = self.head; - let src_start_1 = other.tail; - let dst_wrap_point = self.cap(); - let src_wrap_point = other.cap(); - - let dst = unsafe { self.buffer_as_mut_slice() }; - let src = unsafe { other.buffer_as_slice() }; + let new_head = { + let original_head = self.head; - let src_wraps = other.tail > other.head; - let dst_wraps = dst_start_1 + src_total > dst_wrap_point; + // The goal is to copy all values from `other` into `self`. To avoid any + // mismatch, all valid values in `other` are retrieved... + let (src_high, src_low) = other.as_slices(); + // and unoccupied parts of self are retrieved. + let (dst_high, dst_low) = unsafe { self.unused_as_mut_slices() }; - // When minimizing the amount of calls to `copy_part`, there are - // 6 different cases to handle. Whether src and/or dst wrap are 4 - // combinations and there are 3 distinct cases when they both wrap. - // 6 = 3 + 1 + 1 + 1 - match (src_wraps, dst_wraps) { + // Then all that is needed is to copy all values from + // src (src_high and src_low) to dst (dst_high and dst_low). + // + // other [o o o . . . . . o o o o] + // [5 6 7] [1 2 3 4] + // src_low src_high + // + // self [. . . . . . o o o o . .] + // [3 4 5 6 7 .] [1 2] + // dst_low dst_high + // + // Values are not copied one by one but as slices in `copy_whole_slice`. + // What slices are used depends on various properties of src and dst. + // There are 6 cases in total: + // 1. `src` and `dst` are contiguous + // 2. `src` is contiguous and `dst` is discontiguous + // 3. `src` is discontiguous and `dst` is contiguous + // 4. `src` and `dst` are discontiguous + // + src_high is smaller than dst_high + // 5. `src` and `dst` are discontiguous + // + dst_high is smaller than src_high + // 6. `src` and `dst` are discontiguous + // + dst_high is the same size as src_high + let src_contiguous = src_low.is_empty(); + let dst_contiguous = dst_high.len() >= src_total; + match (src_contiguous, dst_contiguous) { (true, true) => { - let dst_before_wrap = dst_wrap_point - dst_start_1; - let src_before_wrap = src_wrap_point - src_start_1; - - if src_before_wrap < dst_before_wrap { - // src - // [o o o . . . . . . o o o] - // 2 3 3 1 1 1 - // - // dst - // [. . . . . . o o . . . .] - // 3 3 H 1 1 1 2 - let src_2 = dst_before_wrap - src_before_wrap; - let dst_start_2 = dst_start_1 + src_before_wrap; - let src_3 = src_total - dst_before_wrap; - - unsafe { - copy_part(src_start_1, dst_start_1, src_before_wrap, src, dst); - copy_part(0, dst_start_2, src_2, src, dst); - copy_part(src_2, 0, src_3, src, dst); - } - src_3 - } else if src_before_wrap > dst_before_wrap { - // src - // [o o o . . . . . o o o o] - // 3 3 3 1 1 2 2 - // - // dst - // [. . . . . . o o o o . .] - // 2 2 3 3 3 H 1 1 - let src_2 = src_before_wrap - dst_before_wrap; - let src_start_2 = src_start_1 + dst_before_wrap; - let src_3 = src_total - src_before_wrap; - - unsafe { - copy_part(src_start_1, dst_start_1, dst_before_wrap, src, dst); - copy_part(src_start_2, 0, src_2, src, dst); - copy_part(0, src_2, src_3, src, dst); - } - src_2 + src_3 - } else { - // src - // [o o . . . . . . . o o o] - // 2 2 1 1 1 - // - // dst - // [. . . . . . . o o . . .] - // 2 2 H 1 1 1 - let src_2 = src_total - src_before_wrap; + // 1. + // other [. . . o o o . . . . . .] + // [] [1 1 1] + // + // self [. o o o o o . . . . . .] + // [.] [1 1 1 . . .] - unsafe { - copy_part(src_start_1, dst_start_1, src_before_wrap, src, dst); - copy_part(0, 0, src_2, src, dst); - } - src_2 + unsafe { + copy_whole_slice(src_high, dst_high); } + original_head + src_total } - (false, true) => { - // src - // [. . . o o o o o . . . .] - // 1 1 2 2 2 + (true, false) => { + // 2. + // other [. . . o o o o o . . . .] + // [] [1 1 2 2 2] // - // dst - // [. . . . . . . o o o . .] - // 2 2 2 H 1 1 - let dst_1 = dst_wrap_point - dst_start_1; - let src_start_2 = src_start_1 + dst_1; - let dst_2 = src_total - dst_1; + // self [. . . . . . . o o o . .] + // [2 2 2 . . . .] [1 1] + let (src_1, src_2) = src_high.split_at(dst_high.len()); unsafe { - copy_part(src_start_1, dst_start_1, dst_1, src, dst); - copy_part(src_start_2, 0, dst_2, src, dst); + copy_whole_slice(src_1, dst_high); + copy_whole_slice(src_2, dst_low); } - dst_2 + src_total - dst_high.len() } - (true, false) => { - // src - // [o o . . . . . . . o o o] - // 2 2 1 1 1 + (false, true) => { + // 3. + // other [o o . . . . . . . o o o] + // [2 2] [1 1 1] // - // dst - // [. o o . . . . . . . . .] - // 1 1 1 2 2 H - let src_1 = src_wrap_point - src_start_1; - let dst_start_2 = dst_start_1 + src_1; - let src_2 = src_total - src_1; + // self [. o o . . . . . . . . .] + // [.] [1 1 1 2 2 . . . .] + let (dst_1, dst_2) = dst_high.split_at_mut(src_high.len()); unsafe { - copy_part(src_start_1, dst_start_1, src_1, src, dst); - copy_part(0, dst_start_2, src_2, src, dst); + copy_whole_slice(src_high, dst_1); + copy_whole_slice(src_low, dst_2); } - dst_start_1 + src_1 + src_2 + original_head + src_total } (false, false) => { - // src - // [. . . o o o . . . . . .] - // 1 1 1 - // - // dst - // [. o o o o o . . . . . .] - // 1 1 1 H - unsafe { - copy_part(src_start_1, dst_start_1, src_total, src, dst); + if src_high.len() < dst_high.len() { + // 4. + // other [o o o . . . . . . o o o] + // [2 3 3] [1 1 1] + // + // self [. . . . . . o o . . . .] + // [3 3 . . . .] [1 1 1 2] + + let (dst_1, dst_2) = dst_high.split_at_mut(src_high.len()); + let (src_2, src_3) = src_low.split_at(dst_2.len()); + unsafe { + copy_whole_slice(src_high, dst_1); + copy_whole_slice(src_2, dst_2); + copy_whole_slice(src_3, dst_low); + } + src_3.len() + } else if src_high.len() > dst_high.len() { + // 5. + // other [o o o . . . . . o o o o] + // [3 3 3] [1 1 2 2] + // + // self [. . . . . . o o o o . .] + // [2 2 3 3 3 .] [1 1] + + let (src_1, src_2) = src_high.split_at(dst_high.len()); + let (dst_2, dst_3) = dst_low.split_at_mut(src_2.len()); + unsafe { + copy_whole_slice(src_1, dst_high); + copy_whole_slice(src_2, dst_2); + copy_whole_slice(src_low, dst_3); + } + dst_2.len() + src_low.len() + } else { + // 6. + // other [o o . . . . . . . o o o] + // [2 2] [1 1 1] + // + // self [. . . . . . . o o . . .] + // [2 2 . . . . .] [1 1 1] + + unsafe { + copy_whole_slice(src_high, dst_high); + copy_whole_slice(src_low, dst_low); + } + src_low.len() } - dst_start_1 + src_total } } }; + + // Up until this point we are in a bad state as some values + // exist in both `self` and `other`. To preserve panic safety + // it is important we clear the old values from `other`... other.clear(); + // and that we update `head` as the last step, making the values accessible in `self`. + self.head = new_head; } /// Retains only the elements specified by the predicate. -- cgit 1.4.1-3-g733a5 From 8d3554c48d4f055654807f617609151cfcc7a81d Mon Sep 17 00:00:00 2001 From: Pazzaz Date: Tue, 14 Aug 2018 20:54:25 +0200 Subject: Don't drop values in other, just move the tail --- src/liballoc/collections/vec_deque.rs | 10 +++------- 1 file changed, 3 insertions(+), 7 deletions(-) (limited to 'src/liballoc/collections/vec_deque.rs') diff --git a/src/liballoc/collections/vec_deque.rs b/src/liballoc/collections/vec_deque.rs index 7f4fbb99c22..b66bb82bc37 100644 --- a/src/liballoc/collections/vec_deque.rs +++ b/src/liballoc/collections/vec_deque.rs @@ -1859,7 +1859,7 @@ impl VecDeque { // Guarantees there is space in `self` for `other`. self.reserve(src_total); - let new_head = { + self.head = { let original_head = self.head; // The goal is to copy all values from `other` into `self`. To avoid any @@ -1988,12 +1988,8 @@ impl VecDeque { } }; - // Up until this point we are in a bad state as some values - // exist in both `self` and `other`. To preserve panic safety - // it is important we clear the old values from `other`... - other.clear(); - // and that we update `head` as the last step, making the values accessible in `self`. - self.head = new_head; + // Some values now exist in both `other` and `self` but are made inaccessible in `other`. + other.tail = other.head; } /// Retains only the elements specified by the predicate. -- cgit 1.4.1-3-g733a5 From ae0f25431129f87c271e13c87ecba629529f8723 Mon Sep 17 00:00:00 2001 From: Pazzaz Date: Tue, 14 Aug 2018 20:56:22 +0200 Subject: Clarify dst condition --- src/liballoc/collections/vec_deque.rs | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) (limited to 'src/liballoc/collections/vec_deque.rs') diff --git a/src/liballoc/collections/vec_deque.rs b/src/liballoc/collections/vec_deque.rs index b66bb82bc37..95d4b918df3 100644 --- a/src/liballoc/collections/vec_deque.rs +++ b/src/liballoc/collections/vec_deque.rs @@ -1882,18 +1882,18 @@ impl VecDeque { // Values are not copied one by one but as slices in `copy_whole_slice`. // What slices are used depends on various properties of src and dst. // There are 6 cases in total: - // 1. `src` and `dst` are contiguous - // 2. `src` is contiguous and `dst` is discontiguous - // 3. `src` is discontiguous and `dst` is contiguous - // 4. `src` and `dst` are discontiguous + // 1. `src` is contiguous and fits in dst_high + // 2. `src` is contiguous and does not fit in dst_high + // 3. `src` is discontiguous and fits in dst_high + // 4. `src` is discontiguous and does not fit in dst_high // + src_high is smaller than dst_high - // 5. `src` and `dst` are discontiguous + // 5. `src` is discontiguous and does not fit in dst_high // + dst_high is smaller than src_high - // 6. `src` and `dst` are discontiguous + // 6. `src` is discontiguous and does not fit in dst_high // + dst_high is the same size as src_high let src_contiguous = src_low.is_empty(); - let dst_contiguous = dst_high.len() >= src_total; - match (src_contiguous, dst_contiguous) { + let dst_high_fits_src = dst_high.len() >= src_total; + match (src_contiguous, dst_high_fits_src) { (true, true) => { // 1. // other [. . . o o o . . . . . .] -- cgit 1.4.1-3-g733a5 From 76625280b25bfe66d3a6e2c7e4c04726886fa7e1 Mon Sep 17 00:00:00 2001 From: Pazzaz Date: Wed, 15 Aug 2018 18:01:42 +0200 Subject: Clarify unused_as_mut_slices --- src/liballoc/collections/vec_deque.rs | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-) (limited to 'src/liballoc/collections/vec_deque.rs') diff --git a/src/liballoc/collections/vec_deque.rs b/src/liballoc/collections/vec_deque.rs index 95d4b918df3..297991b3976 100644 --- a/src/liballoc/collections/vec_deque.rs +++ b/src/liballoc/collections/vec_deque.rs @@ -208,11 +208,14 @@ impl VecDeque { let head = self.head; let tail = self.tail; let buf = self.buffer_as_mut_slice(); - if head == tail { + if head != tail { + // In buf, head..tail contains the VecDeque and tail..head is unused. + // So calling `ring_slices` with tail and head swapped returns unused slices. + RingSlices::ring_slices(buf, tail, head) + } else { + // Swapping doesn't help when head == tail. let (before, after) = buf.split_at_mut(head); (after, before) - } else { - RingSlices::ring_slices(buf, tail, head) } } -- cgit 1.4.1-3-g733a5