diff options
Diffstat (limited to 'src/libstd')
| -rw-r--r-- | src/libstd/ptr.rs | 50 | ||||
| -rw-r--r-- | src/libstd/vec.rs | 134 |
2 files changed, 144 insertions, 40 deletions
diff --git a/src/libstd/ptr.rs b/src/libstd/ptr.rs index aee6f1bd204..add2bbd7d44 100644 --- a/src/libstd/ptr.rs +++ b/src/libstd/ptr.rs @@ -143,6 +143,30 @@ pub unsafe fn set_memory<T>(dst: *mut T, c: u8, count: uint) { } /** + * Zeroes out `count` bytes of memory at `dst` + */ +#[inline] +#[cfg(not(stage0))] +pub unsafe fn zero_memory<T>(dst: *mut T, count: uint) { + set_memory(dst, 0, count); +} + +/** + * Zeroes out `count * size_of::<T>` bytes of memory at `dst` + */ +#[inline] +#[cfg(stage0)] +pub unsafe fn zero_memory<T>(dst: *mut T, count: uint) { + let mut count = count * sys::size_of::<T>(); + let mut dst = dst as *mut u8; + while count > 0 { + *dst = 0; + dst = mut_offset(dst, 1); + count -= 1; + } +} + +/** * Swap the values at two mutable locations of the same type, without * deinitialising or copying either one. */ @@ -172,6 +196,32 @@ pub unsafe fn replace_ptr<T>(dest: *mut T, mut src: T) -> T { src } +/** + * Reads the value from `*src` and returns it. Does not copy `*src`. + */ +#[inline(always)] +pub unsafe fn read_ptr<T>(src: *mut T) -> T { + let mut tmp: T = intrinsics::uninit(); + let t: *mut T = &mut tmp; + copy_memory(t, src, 1); + tmp +} + +/** + * Reads the value from `*src` and nulls it out. + * This currently prevents destructors from executing. + */ +#[inline(always)] +pub unsafe fn read_and_zero_ptr<T>(dest: *mut T) -> T { + // Copy the data out from `dest`: + let tmp = read_ptr(dest); + + // Now zero out `dest`: + zero_memory(dest, 1); + + tmp +} + /// Transform a region pointer - &T - to an unsafe pointer - *T. #[inline] pub fn to_unsafe_ptr<T>(thing: &T) -> *T { diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs index 33857556548..cacb3156b75 100644 --- a/src/libstd/vec.rs +++ b/src/libstd/vec.rs @@ -1256,16 +1256,15 @@ impl<T> OwnedVector<T> for ~[T] { /// ~~~ #[inline] fn push_all_move(&mut self, mut rhs: ~[T]) { - let new_len = self.len() + rhs.len(); + let self_len = self.len(); + let rhs_len = rhs.len(); + let new_len = self_len + rhs_len; self.reserve(new_len); - unsafe { - do rhs.as_mut_buf |p, len| { - for uint::range(0, len) |i| { - let x = ptr::replace_ptr(ptr::mut_offset(p, i), - intrinsics::uninit()); - self.push(x); - } - } + unsafe { // Note: infallible. + let self_p = vec::raw::to_mut_ptr(*self); + let rhs_p = vec::raw::to_ptr(rhs); + ptr::copy_memory(ptr::mut_offset(self_p, self_len), rhs_p, rhs_len); + raw::set_len(self, new_len); raw::set_len(&mut rhs, 0); } } @@ -1277,9 +1276,8 @@ impl<T> OwnedVector<T> for ~[T] { ln => { let valptr = ptr::to_mut_unsafe_ptr(&mut self[ln - 1u]); unsafe { - let val = ptr::replace_ptr(valptr, intrinsics::init()); - raw::set_len(self, ln - 1u); - Some(val) + raw::set_len(v, ln - 1u); + ptr::read_ptr(valptr) } } } @@ -1410,7 +1408,7 @@ impl<T> OwnedVector<T> for ~[T] { unsafe { // This loop is optimized out for non-drop types. for uint::range(newlen, oldlen) |i| { - ptr::replace_ptr(ptr::mut_offset(p, i), intrinsics::uninit()); + ptr::read_and_zero_ptr(ptr::mut_offset(p, i)) } } } @@ -1555,37 +1553,93 @@ pub trait OwnedEqVector<T:Eq> { impl<T:Eq> OwnedEqVector<T> for ~[T] { /** - * Remove consecutive repeated elements from a vector; if the vector is - * sorted, this removes all duplicates. - */ - pub fn dedup(&mut self) { + * Remove consecutive repeated elements from a vector; if the vector is + * sorted, this removes all duplicates. + */ + pub fn dedup<T:Eq>(&mut self) { unsafe { - if self.len() == 0 { return; } - let mut last_written = 0; - let mut next_to_read = 1; - do self.as_mut_buf |p, ln| { - // last_written < next_to_read <= ln - while next_to_read < ln { - // last_written < next_to_read < ln - if *ptr::mut_offset(p, next_to_read) == - *ptr::mut_offset(p, last_written) { - ptr::replace_ptr(ptr::mut_offset(p, next_to_read), - intrinsics::uninit()); - } else { - last_written += 1; - // last_written <= next_to_read < ln - if next_to_read != last_written { - ptr::swap_ptr(ptr::mut_offset(p, last_written), - ptr::mut_offset(p, next_to_read)); - } + // Although we have a mutable reference to `self`, we cannot make + // *arbitrary* changes. There exists the possibility that this + // vector is contained with an `@mut` box and hence is still + // readable by the outside world during the `Eq` comparisons. + // Moreover, those comparisons could fail, so we must ensure + // that the vector is in a valid state at all time. + // + // The way that we handle this is by using swaps; we iterate + // over all the elements, swapping as we go so that at the end + // the elements we wish to keep are in the front, and those we + // wish to reject are at the back. We can then truncate the + // vector. This operation is still O(n). + // + // Example: We start in this state, where `r` represents "next + // read" and `w` represents "next_write`. + // + // r + // +---+---+---+---+---+---+ + // | 0 | 1 | 1 | 2 | 3 | 3 | + // +---+---+---+---+---+---+ + // w + // + // Comparing self[r] against self[w-1], tis is not a duplicate, so + // we swap self[r] and self[w] (no effect as r==w) and then increment both + // r and w, leaving us with: + // + // r + // +---+---+---+---+---+---+ + // | 0 | 1 | 1 | 2 | 3 | 3 | + // +---+---+---+---+---+---+ + // w + // + // Comparing self[r] against self[w-1], this value is a duplicate, + // so we increment `r` but leave everything else unchanged: + // + // r + // +---+---+---+---+---+---+ + // | 0 | 1 | 1 | 2 | 3 | 3 | + // +---+---+---+---+---+---+ + // w + // + // Comparing self[r] against self[w-1], this is not a duplicate, + // so swap self[r] and self[w] and advance r and w: + // + // r + // +---+---+---+---+---+---+ + // | 0 | 1 | 2 | 1 | 3 | 3 | + // +---+---+---+---+---+---+ + // w + // + // Not a duplicate, repeat: + // + // r + // +---+---+---+---+---+---+ + // | 0 | 1 | 2 | 3 | 1 | 3 | + // +---+---+---+---+---+---+ + // w + // + // Duplicate, advance r. End of vec. Truncate to w. + + let ln = self.len(); + if ln < 1 { return; } + + // Avoid bounds checks by using unsafe pointers. + let p = vec::raw::to_mut_ptr(*self); + let mut r = 1; + let mut w = 1; + + while r < ln { + let p_r = ptr::mut_offset(p, r); + let p_wm1 = ptr::mut_offset(p, w - 1); + if *p_r != *p_wm1 { + if r != w { + let p_w = ptr::mut_offset(p_wm1, 1); + util::swap(&mut *p_r, &mut *p_w); } - // last_written <= next_to_read < ln - next_to_read += 1; - // last_written < next_to_read <= ln + w += 1; } + r += 1; } - // last_written < next_to_read == ln - raw::set_len(self, last_written + 1); + + self.truncate(w); } } } |