diff options
Diffstat (limited to 'src/libcore')
| -rw-r--r-- | src/libcore/ops.rs | 44 | ||||
| -rw-r--r-- | src/libcore/slice/sort.rs | 56 | ||||
| -rw-r--r-- | src/libcore/str/mod.rs | 37 |
3 files changed, 90 insertions, 47 deletions
diff --git a/src/libcore/ops.rs b/src/libcore/ops.rs index 686cc21eba1..d203b68c0df 100644 --- a/src/libcore/ops.rs +++ b/src/libcore/ops.rs @@ -196,7 +196,7 @@ pub trait Drop { fn drop(&mut self); } -/// The `Add` trait is used to specify the functionality of `+`. +/// The addition operator `+`. /// /// # Examples /// @@ -269,7 +269,7 @@ macro_rules! add_impl { add_impl! { usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 f32 f64 } -/// The `Sub` trait is used to specify the functionality of `-`. +/// The subtraction operator `-`. /// /// # Examples /// @@ -342,7 +342,7 @@ macro_rules! sub_impl { sub_impl! { usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 f32 f64 } -/// The `Mul` trait is used to specify the functionality of `*`. +/// The multiplication operator `*`. /// /// # Examples /// @@ -464,7 +464,7 @@ macro_rules! mul_impl { mul_impl! { usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 f32 f64 } -/// The `Div` trait is used to specify the functionality of `/`. +/// The division operator `/`. /// /// # Examples /// @@ -609,7 +609,7 @@ macro_rules! div_impl_float { div_impl_float! { f32 f64 } -/// The `Rem` trait is used to specify the functionality of `%`. +/// The remainder operator `%`. /// /// # Examples /// @@ -689,7 +689,7 @@ macro_rules! rem_impl_float { rem_impl_float! { f32 f64 } -/// The `Neg` trait is used to specify the functionality of unary `-`. +/// The unary negation operator `-`. /// /// # Examples /// @@ -768,7 +768,7 @@ macro_rules! neg_impl_unsigned { // neg_impl_unsigned! { usize u8 u16 u32 u64 } neg_impl_numeric! { isize i8 i16 i32 i64 i128 f32 f64 } -/// The `Not` trait is used to specify the functionality of unary `!`. +/// The unary logical negation operator `!`. /// /// # Examples /// @@ -826,7 +826,7 @@ macro_rules! not_impl { not_impl! { bool usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 } -/// The `BitAnd` trait is used to specify the functionality of `&`. +/// The bitwise AND operator `&`. /// /// # Examples /// @@ -909,7 +909,7 @@ macro_rules! bitand_impl { bitand_impl! { bool usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 } -/// The `BitOr` trait is used to specify the functionality of `|`. +/// The bitwise OR operator `|`. /// /// # Examples /// @@ -992,7 +992,7 @@ macro_rules! bitor_impl { bitor_impl! { bool usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 } -/// The `BitXor` trait is used to specify the functionality of `^`. +/// The bitwise XOR operator `^`. /// /// # Examples /// @@ -1078,7 +1078,7 @@ macro_rules! bitxor_impl { bitxor_impl! { bool usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 } -/// The `Shl` trait is used to specify the functionality of `<<`. +/// The left shift operator `<<`. /// /// # Examples /// @@ -1181,7 +1181,7 @@ macro_rules! shl_impl_all { shl_impl_all! { u8 u16 u32 u64 u128 usize i8 i16 i32 i64 isize i128 } -/// The `Shr` trait is used to specify the functionality of `>>`. +/// The right shift operator `>>`. /// /// # Examples /// @@ -1284,7 +1284,7 @@ macro_rules! shr_impl_all { shr_impl_all! { u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize } -/// The `AddAssign` trait is used to specify the functionality of `+=`. +/// The addition assignment operator `+=`. /// /// # Examples /// @@ -1340,7 +1340,7 @@ macro_rules! add_assign_impl { add_assign_impl! { usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 f32 f64 } -/// The `SubAssign` trait is used to specify the functionality of `-=`. +/// The subtraction assignment operator `-=`. /// /// # Examples /// @@ -1396,7 +1396,7 @@ macro_rules! sub_assign_impl { sub_assign_impl! { usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 f32 f64 } -/// The `MulAssign` trait is used to specify the functionality of `*=`. +/// The multiplication assignment operator `*=`. /// /// # Examples /// @@ -1441,7 +1441,7 @@ macro_rules! mul_assign_impl { mul_assign_impl! { usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 f32 f64 } -/// The `DivAssign` trait is used to specify the functionality of `/=`. +/// The division assignment operator `/=`. /// /// # Examples /// @@ -1485,7 +1485,7 @@ macro_rules! div_assign_impl { div_assign_impl! { usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 f32 f64 } -/// The `RemAssign` trait is used to specify the functionality of `%=`. +/// The remainder assignment operator `%=`. /// /// # Examples /// @@ -1529,7 +1529,7 @@ macro_rules! rem_assign_impl { rem_assign_impl! { usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 f32 f64 } -/// The `BitAndAssign` trait is used to specify the functionality of `&=`. +/// The bitwise AND assignment operator `&=`. /// /// # Examples /// @@ -1615,7 +1615,7 @@ macro_rules! bitand_assign_impl { bitand_assign_impl! { bool usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 } -/// The `BitOrAssign` trait is used to specify the functionality of `|=`. +/// The bitwise OR assignment operator `|=`. /// /// # Examples /// @@ -1659,7 +1659,7 @@ macro_rules! bitor_assign_impl { bitor_assign_impl! { bool usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 } -/// The `BitXorAssign` trait is used to specify the functionality of `^=`. +/// The bitwise XOR assignment operator `^=`. /// /// # Examples /// @@ -1703,7 +1703,7 @@ macro_rules! bitxor_assign_impl { bitxor_assign_impl! { bool usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 } -/// The `ShlAssign` trait is used to specify the functionality of `<<=`. +/// The left shift assignment operator `<<=`. /// /// # Examples /// @@ -1768,7 +1768,7 @@ macro_rules! shl_assign_impl_all { shl_assign_impl_all! { u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize } -/// The `ShrAssign` trait is used to specify the functionality of `>>=`. +/// The right shift assignment operator `>>=`. /// /// # Examples /// diff --git a/src/libcore/slice/sort.rs b/src/libcore/slice/sort.rs index 307e4974d97..3612ee65bca 100644 --- a/src/libcore/slice/sort.rs +++ b/src/libcore/slice/sort.rs @@ -498,32 +498,40 @@ fn partition_equal<T, F>(v: &mut [T], pivot: usize, is_less: &mut F) -> usize #[cold] fn break_patterns<T>(v: &mut [T]) { let len = v.len(); - if len >= 8 { - // A random number will be taken modulo this one. The modulus is a power of two so that we - // can simply take bitwise "and", thus avoiding costly CPU operations. - let modulus = (len / 4).next_power_of_two(); - debug_assert!(modulus >= 1 && modulus <= len / 2); - - // Pseudorandom number generation from the "Xorshift RNGs" paper by George Marsaglia. - let mut random = len; - random ^= random << 13; - random ^= random >> 17; - random ^= random << 5; - random &= modulus - 1; - debug_assert!(random < len / 2); - - // The first index. - let a = len / 4 * 2; - debug_assert!(a >= 1 && a < len - 2); - - // The second index. - let b = len / 4 + random; - debug_assert!(b >= 1 && b < len - 2); - - // Swap neighbourhoods of `a` and `b`. + // Pseudorandom number generator from the "Xorshift RNGs" paper by George Marsaglia. + let mut random = len as u32; + let mut gen_u32 = || { + random ^= random << 13; + random ^= random >> 17; + random ^= random << 5; + random + }; + let mut gen_usize = || { + if mem::size_of::<usize>() <= 4 { + gen_u32() as usize + } else { + (((gen_u32() as u64) << 32) | (gen_u32() as u64)) as usize + } + }; + + // Take random numbers modulo this number. + // The number fits into `usize` because `len` is not greater than `isize::MAX`. + let modulus = len.next_power_of_two(); + + // Some pivot candidates will be in the nearby of this index. Let's randomize them. + let pos = len / 4 * 2; + for i in 0..3 { - v.swap(a - 1 + i, b - 1 + i); + // Generate a random number modulo `len`. However, in order to avoid costly operations + // we first take it modulo a power of two, and then decrease by `len` until it fits + // into the range `[0, len - 1]`. + let mut other = gen_usize() & (modulus - 1); + while other >= len { + other -= len; + } + + v.swap(pos - 1 + i, other); } } } diff --git a/src/libcore/str/mod.rs b/src/libcore/str/mod.rs index dfb6936da6b..0d66d0e93aa 100644 --- a/src/libcore/str/mod.rs +++ b/src/libcore/str/mod.rs @@ -35,6 +35,39 @@ pub mod pattern; /// [`from_str`]: #tymethod.from_str /// [`str`]: ../../std/primitive.str.html /// [`parse`]: ../../std/primitive.str.html#method.parse +/// +/// # Examples +/// +/// Basic implementation of `FromStr` on an example `Point` type: +/// +/// ``` +/// use std::str::FromStr; +/// use std::num::ParseIntError; +/// +/// #[derive(Debug, PartialEq)] +/// struct Point { +/// x: i32, +/// y: i32 +/// } +/// +/// impl FromStr for Point { +/// type Err = ParseIntError; +/// +/// fn from_str(s: &str) -> Result<Self, Self::Err> { +/// let coords: Vec<&str> = s.trim_matches(|p| p == '(' || p == ')' ) +/// .split(",") +/// .collect(); +/// +/// let x_fromstr = coords[0].parse::<i32>()?; +/// let y_fromstr = coords[1].parse::<i32>()?; +/// +/// Ok(Point { x: x_fromstr, y: y_fromstr }) +/// } +/// } +/// +/// let p = Point::from_str("(1,2)"); +/// assert_eq!(p.unwrap(), Point{ x: 1, y: 2} ) +/// ``` #[stable(feature = "rust1", since = "1.0.0")] pub trait FromStr: Sized { /// The associated error which can be returned from parsing. @@ -101,7 +134,9 @@ impl FromStr for bool { } } -/// An error returned when parsing a `bool` from a string fails. +/// An error returned when parsing a `bool` using [`from_str`] fails +/// +/// [`from_str`]: ../../std/primitive.bool.html#method.from_str #[derive(Debug, Clone, PartialEq, Eq)] #[stable(feature = "rust1", since = "1.0.0")] pub struct ParseBoolError { _priv: () } |