diff options
| author | Alex Crichton <alex@alexcrichton.com> | 2015-02-19 18:35:52 -0800 |
|---|---|---|
| committer | Alex Crichton <alex@alexcrichton.com> | 2015-02-20 22:17:17 -0800 |
| commit | 6686f7aa471f162697d08a78ad4d04d3c0e9612c (patch) | |
| tree | 038bc233524ca60ad55a6303c8601170a8a1039b | |
| parent | 522d09dfecbeca1595f25ac58c6d0178bbd21d7d (diff) | |
| download | rust-6686f7aa471f162697d08a78ad4d04d3c0e9612c.tar.gz rust-6686f7aa471f162697d08a78ad4d04d3c0e9612c.zip | |
Register new snapshots
41 files changed, 20 insertions, 5242 deletions
diff --git a/src/liballoc/arc.rs b/src/liballoc/arc.rs index 934e6ab2159..cc49164ef91 100644 --- a/src/liballoc/arc.rs +++ b/src/liballoc/arc.rs @@ -598,13 +598,6 @@ impl<T: Default + Sync + Send> Default for Arc<T> { fn default() -> Arc<T> { Arc::new(Default::default()) } } -#[cfg(stage0)] -impl<H: Hasher, T: Hash<H>> Hash<H> for Arc<T> { - fn hash(&self, state: &mut H) { - (**self).hash(state) - } -} -#[cfg(not(stage0))] #[stable(feature = "rust1", since = "1.0.0")] impl<T: Hash> Hash for Arc<T> { fn hash<H: Hasher>(&self, state: &mut H) { diff --git a/src/liballoc/boxed.rs b/src/liballoc/boxed.rs index a3516bd667b..ce889c79601 100644 --- a/src/liballoc/boxed.rs +++ b/src/liballoc/boxed.rs @@ -220,14 +220,6 @@ impl<T: ?Sized + Ord> Ord for Box<T> { #[stable(feature = "rust1", since = "1.0.0")] impl<T: ?Sized + Eq> Eq for Box<T> {} -#[cfg(stage0)] -impl<S: hash::Hasher, T: ?Sized + Hash<S>> Hash<S> for Box<T> { - #[inline] - fn hash(&self, state: &mut S) { - (**self).hash(state); - } -} -#[cfg(not(stage0))] #[stable(feature = "rust1", since = "1.0.0")] impl<T: ?Sized + Hash> Hash for Box<T> { fn hash<H: hash::Hasher>(&self, state: &mut H) { diff --git a/src/liballoc/rc.rs b/src/liballoc/rc.rs index 9d395115431..ed7d34de7a6 100644 --- a/src/liballoc/rc.rs +++ b/src/liballoc/rc.rs @@ -592,14 +592,6 @@ impl<T: Ord> Ord for Rc<T> { } // FIXME (#18248) Make `T` `Sized?` -#[cfg(stage0)] -impl<S: Hasher, T: Hash<S>> Hash<S> for Rc<T> { - #[inline] - fn hash(&self, state: &mut S) { - (**self).hash(state); - } -} -#[cfg(not(stage0))] #[stable(feature = "rust1", since = "1.0.0")] impl<T: Hash> Hash for Rc<T> { fn hash<H: Hasher>(&self, state: &mut H) { diff --git a/src/libcollections/bit.rs b/src/libcollections/bit.rs index 11c576eab15..21218201182 100644 --- a/src/libcollections/bit.rs +++ b/src/libcollections/bit.rs @@ -985,17 +985,6 @@ impl fmt::Debug for BitVec { } #[stable(feature = "rust1", since = "1.0.0")] -#[cfg(stage0)] -impl<S: hash::Writer + hash::Hasher> hash::Hash<S> for BitVec { - fn hash(&self, state: &mut S) { - self.nbits.hash(state); - for elem in self.blocks() { - elem.hash(state); - } - } -} -#[stable(feature = "rust1", since = "1.0.0")] -#[cfg(not(stage0))] impl hash::Hash for BitVec { fn hash<H: hash::Hasher>(&self, state: &mut H) { self.nbits.hash(state); @@ -1776,16 +1765,7 @@ impl fmt::Debug for BitSet { } } -#[cfg(stage0)] -impl<S: hash::Writer + hash::Hasher> hash::Hash<S> for BitSet { - fn hash(&self, state: &mut S) { - for pos in self { - pos.hash(state); - } - } -} #[stable(feature = "rust1", since = "1.0.0")] -#[cfg(not(stage0))] impl hash::Hash for BitSet { fn hash<H: hash::Hasher>(&self, state: &mut H) { for pos in self { diff --git a/src/libcollections/borrow.rs b/src/libcollections/borrow.rs index 901d7a73b51..e92f38741c9 100644 --- a/src/libcollections/borrow.rs +++ b/src/libcollections/borrow.rs @@ -282,16 +282,6 @@ impl<'a, B: ?Sized> fmt::Display for Cow<'a, B> where } #[stable(feature = "rust1", since = "1.0.0")] -#[cfg(stage0)] -impl<'a, B: ?Sized, S: Hasher> Hash<S> for Cow<'a, B> where B: Hash<S> + ToOwned -{ - #[inline] - fn hash(&self, state: &mut S) { - Hash::hash(&**self, state) - } -} -#[stable(feature = "rust1", since = "1.0.0")] -#[cfg(not(stage0))] impl<'a, B: ?Sized> Hash for Cow<'a, B> where B: Hash + ToOwned { #[inline] diff --git a/src/libcollections/borrow_stage0.rs b/src/libcollections/borrow_stage0.rs deleted file mode 100644 index c1d74b16ce6..00000000000 --- a/src/libcollections/borrow_stage0.rs +++ /dev/null @@ -1,313 +0,0 @@ -// Copyright 2014 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or -// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license -// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -//! A module for working with borrowed data. - -#![stable(feature = "rust1", since = "1.0.0")] - -use core::clone::Clone; -use core::cmp::{Eq, Ord, Ordering, PartialEq, PartialOrd}; -use core::hash::{Hash, Hasher}; -use core::marker::Sized; -use core::ops::Deref; -use core::option::Option; - -use fmt; -use alloc::{rc, arc}; - -use self::Cow::*; - -/// A trait for borrowing data. -/// -/// In general, there may be several ways to "borrow" a piece of data. The -/// typical ways of borrowing a type `T` are `&T` (a shared borrow) and `&mut T` -/// (a mutable borrow). But types like `Vec<T>` provide additional kinds of -/// borrows: the borrowed slices `&[T]` and `&mut [T]`. -/// -/// When writing generic code, it is often desirable to abstract over all ways -/// of borrowing data from a given type. That is the role of the `Borrow` -/// trait: if `T: Borrow<U>`, then `&U` can be borrowed from `&T`. A given -/// type can be borrowed as multiple different types. In particular, `Vec<T>: -/// Borrow<Vec<T>>` and `Vec<T>: Borrow<[T]>`. -#[stable(feature = "rust1", since = "1.0.0")] -pub trait Borrow<Borrowed: ?Sized> { - /// Immutably borrow from an owned value. - #[stable(feature = "rust1", since = "1.0.0")] - fn borrow(&self) -> &Borrowed; -} - -/// A trait for mutably borrowing data. -/// -/// Similar to `Borrow`, but for mutable borrows. -#[stable(feature = "rust1", since = "1.0.0")] -pub trait BorrowMut<Borrowed: ?Sized> : Borrow<Borrowed> { - /// Mutably borrow from an owned value. - #[stable(feature = "rust1", since = "1.0.0")] - fn borrow_mut(&mut self) -> &mut Borrowed; -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<T: ?Sized> Borrow<T> for T { - fn borrow(&self) -> &T { self } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<T: ?Sized> BorrowMut<T> for T { - fn borrow_mut(&mut self) -> &mut T { self } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, T: ?Sized> Borrow<T> for &'a T { - fn borrow(&self) -> &T { &**self } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, T: ?Sized> Borrow<T> for &'a mut T { - fn borrow(&self) -> &T { &**self } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, T: ?Sized> BorrowMut<T> for &'a mut T { - fn borrow_mut(&mut self) -> &mut T { &mut **self } -} - -impl<T> Borrow<T> for rc::Rc<T> { - fn borrow(&self) -> &T { &**self } -} - -impl<T> Borrow<T> for arc::Arc<T> { - fn borrow(&self) -> &T { &**self } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, B: ?Sized> Borrow<B> for Cow<'a, B> where B: ToOwned, <B as ToOwned>::Owned: 'a { - fn borrow(&self) -> &B { - &**self - } -} - -/// A generalization of Clone to borrowed data. -/// -/// Some types make it possible to go from borrowed to owned, usually by -/// implementing the `Clone` trait. But `Clone` works only for going from `&T` -/// to `T`. The `ToOwned` trait generalizes `Clone` to construct owned data -/// from any borrow of a given type. -#[stable(feature = "rust1", since = "1.0.0")] -pub trait ToOwned { - #[stable(feature = "rust1", since = "1.0.0")] - type Owned: Borrow<Self>; - - /// Create owned data from borrowed data, usually by copying. - #[stable(feature = "rust1", since = "1.0.0")] - fn to_owned(&self) -> Self::Owned; -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<T> ToOwned for T where T: Clone { - type Owned = T; - fn to_owned(&self) -> T { self.clone() } -} - -/// A clone-on-write smart pointer. -/// -/// The type `Cow` is a smart pointer providing clone-on-write functionality: it -/// can enclose and provide immutable access to borrowed data, and clone the -/// data lazily when mutation or ownership is required. The type is designed to -/// work with general borrowed data via the `Borrow` trait. -/// -/// `Cow` implements both `Deref`, which means that you can call -/// non-mutating methods directly on the data it encloses. If mutation -/// is desired, `to_mut` will obtain a mutable references to an owned -/// value, cloning if necessary. -/// -/// # Example -/// -/// ```rust -/// use std::borrow::Cow; -/// -/// fn abs_all(input: &mut Cow<[int]>) { -/// for i in 0..input.len() { -/// let v = input[i]; -/// if v < 0 { -/// // clones into a vector the first time (if not already owned) -/// input.to_mut()[i] = -v; -/// } -/// } -/// } -/// ``` -#[stable(feature = "rust1", since = "1.0.0")] -pub enum Cow<'a, B: ?Sized + 'a> where B: ToOwned { - /// Borrowed data. - #[stable(feature = "rust1", since = "1.0.0")] - Borrowed(&'a B), - - /// Owned data. - #[stable(feature = "rust1", since = "1.0.0")] - Owned(<B as ToOwned>::Owned) -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, B: ?Sized> Clone for Cow<'a, B> where B: ToOwned { - fn clone(&self) -> Cow<'a, B> { - match *self { - Borrowed(b) => Borrowed(b), - Owned(ref o) => { - let b: &B = o.borrow(); - Owned(b.to_owned()) - }, - } - } -} - -impl<'a, B: ?Sized> Cow<'a, B> where B: ToOwned, <B as ToOwned>::Owned: 'a { - /// Acquire a mutable reference to the owned form of the data. - /// - /// Copies the data if it is not already owned. - #[stable(feature = "rust1", since = "1.0.0")] - pub fn to_mut(&mut self) -> &mut <B as ToOwned>::Owned where <B as ToOwned>::Owned: 'a { - match *self { - Borrowed(borrowed) => { - *self = Owned(borrowed.to_owned()); - self.to_mut() - } - Owned(ref mut owned) => owned - } - } - - /// Extract the owned data. - /// - /// Copies the data if it is not already owned. - #[stable(feature = "rust1", since = "1.0.0")] - pub fn into_owned(self) -> <B as ToOwned>::Owned { - match self { - Borrowed(borrowed) => borrowed.to_owned(), - Owned(owned) => owned - } - } - - /// Returns true if this `Cow` wraps a borrowed value - #[deprecated(since = "1.0.0", reason = "match on the enum instead")] - #[unstable(feature = "std_misc")] - pub fn is_borrowed(&self) -> bool { - match *self { - Borrowed(_) => true, - _ => false, - } - } - - /// Returns true if this `Cow` wraps an owned value - #[deprecated(since = "1.0.0", reason = "match on the enum instead")] - #[unstable(feature = "std_misc")] - pub fn is_owned(&self) -> bool { - match *self { - Owned(_) => true, - _ => false, - } - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, B: ?Sized> Deref for Cow<'a, B> where - B: ToOwned, <B as ToOwned>::Owned: 'a -{ - type Target = B; - - fn deref(&self) -> &B { - match *self { - Borrowed(borrowed) => borrowed, - Owned(ref owned) => owned.borrow() - } - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, B: ?Sized> Eq for Cow<'a, B> where B: Eq + ToOwned, <B as ToOwned>::Owned: 'a {} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, B: ?Sized> Ord for Cow<'a, B> where - B: Ord + ToOwned, <B as ToOwned>::Owned: 'a -{ - #[inline] - fn cmp(&self, other: &Cow<'a, B>) -> Ordering { - Ord::cmp(&**self, &**other) - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, 'b, B: ?Sized, C: ?Sized> PartialEq<Cow<'b, C>> for Cow<'a, B> where - B: PartialEq<C> + ToOwned, C: ToOwned, - <B as ToOwned>::Owned: 'a, <C as ToOwned>::Owned: 'b, -{ - #[inline] - fn eq(&self, other: &Cow<'b, C>) -> bool { - PartialEq::eq(&**self, &**other) - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, B: ?Sized> PartialOrd for Cow<'a, B> where - B: PartialOrd + ToOwned, <B as ToOwned>::Owned: 'a -{ - #[inline] - fn partial_cmp(&self, other: &Cow<'a, B>) -> Option<Ordering> { - PartialOrd::partial_cmp(&**self, &**other) - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, B: ?Sized> fmt::Debug for Cow<'a, B> where - B: fmt::Debug + ToOwned, - <B as ToOwned>::Owned: fmt::Debug, -{ - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - match *self { - Borrowed(ref b) => fmt::Debug::fmt(b, f), - Owned(ref o) => fmt::Debug::fmt(o, f), - } - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, B: ?Sized> fmt::Display for Cow<'a, B> where - B: fmt::Display + ToOwned, - <B as ToOwned>::Owned: fmt::Display, -{ - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - match *self { - Borrowed(ref b) => fmt::Display::fmt(b, f), - Owned(ref o) => fmt::Display::fmt(o, f), - } - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, B: ?Sized, S: Hasher> Hash<S> for Cow<'a, B> where - B: Hash<S> + ToOwned, <B as ToOwned>::Owned: 'a -{ - #[inline] - fn hash(&self, state: &mut S) { - Hash::hash(&**self, state) - } -} - -/// Trait for moving into a `Cow` -#[stable(feature = "rust1", since = "1.0.0")] -pub trait IntoCow<'a, B: ?Sized> where B: ToOwned { - /// Moves `self` into `Cow` - #[stable(feature = "rust1", since = "1.0.0")] - fn into_cow(self) -> Cow<'a, B>; -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, B: ?Sized> IntoCow<'a, B> for Cow<'a, B> where B: ToOwned { - fn into_cow(self) -> Cow<'a, B> { - self - } -} diff --git a/src/libcollections/btree/map.rs b/src/libcollections/btree/map.rs index 7823f536c7a..1b456eec830 100644 --- a/src/libcollections/btree/map.rs +++ b/src/libcollections/btree/map.rs @@ -852,16 +852,6 @@ impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> { } } -#[cfg(stage0)] -#[stable(feature = "rust1", since = "1.0.0")] -impl<S: Hasher, K: Hash<S>, V: Hash<S>> Hash<S> for BTreeMap<K, V> { - fn hash(&self, state: &mut S) { - for elt in self { - elt.hash(state); - } - } -} -#[cfg(not(stage0))] #[stable(feature = "rust1", since = "1.0.0")] impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> { fn hash<H: Hasher>(&self, state: &mut H) { diff --git a/src/libcollections/lib.rs b/src/libcollections/lib.rs index 6569ab9c05a..1f3c54a4cb5 100644 --- a/src/libcollections/lib.rs +++ b/src/libcollections/lib.rs @@ -86,23 +86,17 @@ mod macros; pub mod binary_heap; mod bit; mod btree; -pub mod linked_list; +pub mod borrow; pub mod enum_set; pub mod fmt; -pub mod vec_deque; +pub mod linked_list; pub mod slice; pub mod str; pub mod string; pub mod vec; +pub mod vec_deque; pub mod vec_map; -#[cfg(stage0)] -#[path = "borrow_stage0.rs"] -pub mod borrow; - -#[cfg(not(stage0))] -pub mod borrow; - #[unstable(feature = "collections", reason = "RFC 509")] pub mod bit_vec { diff --git a/src/libcollections/linked_list.rs b/src/libcollections/linked_list.rs index c142819a518..3c61fc3da90 100644 --- a/src/libcollections/linked_list.rs +++ b/src/libcollections/linked_list.rs @@ -28,8 +28,6 @@ use core::cmp::Ordering; use core::default::Default; use core::fmt; use core::hash::{Hasher, Hash}; -#[cfg(stage0)] -use core::hash::Writer; use core::iter::{self, FromIterator, IntoIterator}; use core::mem; use core::ptr; @@ -932,17 +930,6 @@ impl<A: fmt::Debug> fmt::Debug for LinkedList<A> { } #[stable(feature = "rust1", since = "1.0.0")] -#[cfg(stage0)] -impl<S: Writer + Hasher, A: Hash<S>> Hash<S> for LinkedList<A> { - fn hash(&self, state: &mut S) { - self.len().hash(state); - for elt in self { - elt.hash(state); - } - } -} -#[stable(feature = "rust1", since = "1.0.0")] -#[cfg(not(stage0))] impl<A: Hash> Hash for LinkedList<A> { fn hash<H: Hasher>(&self, state: &mut H) { self.len().hash(state); diff --git a/src/libcollections/string.rs b/src/libcollections/string.rs index 3b179d0b94c..6c2624cd204 100644 --- a/src/libcollections/string.rs +++ b/src/libcollections/string.rs @@ -834,16 +834,7 @@ impl fmt::Debug for String { } } -#[unstable(feature = "collections", reason = "waiting on Hash stabilization")] -#[cfg(stage0)] -impl<H: hash::Writer + hash::Hasher> hash::Hash<H> for String { - #[inline] - fn hash(&self, hasher: &mut H) { - (**self).hash(hasher) - } -} #[stable(feature = "rust1", since = "1.0.0")] -#[cfg(not(stage0))] impl hash::Hash for String { #[inline] fn hash<H: hash::Hasher>(&self, hasher: &mut H) { diff --git a/src/libcollections/vec.rs b/src/libcollections/vec.rs index 1cc2a5235ab..2f9577c08de 100644 --- a/src/libcollections/vec.rs +++ b/src/libcollections/vec.rs @@ -1303,15 +1303,7 @@ impl<T:Clone> Clone for Vec<T> { } } -#[cfg(stage0)] -impl<S: hash::Writer + hash::Hasher, T: Hash<S>> Hash<S> for Vec<T> { - #[inline] - fn hash(&self, state: &mut S) { - Hash::hash(&**self, state) - } -} #[stable(feature = "rust1", since = "1.0.0")] -#[cfg(not(stage0))] impl<T: Hash> Hash for Vec<T> { #[inline] fn hash<H: hash::Hasher>(&self, state: &mut H) { @@ -1599,9 +1591,7 @@ impl<T> AsSlice<T> for Vec<T> { fn as_slice(&self) -> &[T] { unsafe { let p = *self.ptr; - if cfg!(not(stage0)) { // NOTE remove cfg after next snapshot - assume(p != 0 as *mut T); - } + assume(p != 0 as *mut T); mem::transmute(RawSlice { data: p, len: self.len diff --git a/src/libcollections/vec_deque.rs b/src/libcollections/vec_deque.rs index 3ba22a41ff7..f65e644fa52 100644 --- a/src/libcollections/vec_deque.rs +++ b/src/libcollections/vec_deque.rs @@ -32,7 +32,6 @@ use core::ptr::{self, Unique}; use core::raw::Slice as RawSlice; use core::hash::{Hash, Hasher}; -#[cfg(stage0)] use core::hash::Writer; use core::cmp; use alloc::heap; @@ -1675,17 +1674,6 @@ impl<A: Ord> Ord for VecDeque<A> { } #[stable(feature = "rust1", since = "1.0.0")] -#[cfg(stage0)] -impl<S: Writer + Hasher, A: Hash<S>> Hash<S> for VecDeque<A> { - fn hash(&self, state: &mut S) { - self.len().hash(state); - for elt in self { - elt.hash(state); - } - } -} -#[stable(feature = "rust1", since = "1.0.0")] -#[cfg(not(stage0))] impl<A: Hash> Hash for VecDeque<A> { fn hash<H: Hasher>(&self, state: &mut H) { self.len().hash(state); diff --git a/src/libcollections/vec_map.rs b/src/libcollections/vec_map.rs index 54589a31423..d59e3c70c39 100644 --- a/src/libcollections/vec_map.rs +++ b/src/libcollections/vec_map.rs @@ -21,7 +21,6 @@ use core::cmp::Ordering; use core::default::Default; use core::fmt; use core::hash::{Hash, Hasher}; -#[cfg(stage0)] use core::hash::Writer; use core::iter::{Enumerate, FilterMap, Map, FromIterator, IntoIterator}; use core::iter; use core::mem::replace; @@ -113,21 +112,7 @@ impl<V:Clone> Clone for VecMap<V> { } } -#[cfg(stage0)] -impl<S: Writer + Hasher, V: Hash<S>> Hash<S> for VecMap<V> { - fn hash(&self, state: &mut S) { - // In order to not traverse the `VecMap` twice, count the elements - // during iteration. - let mut count: usize = 0; - for elt in self { - elt.hash(state); - count += 1; - } - count.hash(state); - } -} #[stable(feature = "rust1", since = "1.0.0")] -#[cfg(not(stage0))] impl<V: Hash> Hash for VecMap<V> { fn hash<H: Hasher>(&self, state: &mut H) { // In order to not traverse the `VecMap` twice, count the elements diff --git a/src/libcore/array.rs b/src/libcore/array.rs index afb5d95c9f8..e8f6e31756d 100644 --- a/src/libcore/array.rs +++ b/src/libcore/array.rs @@ -35,13 +35,6 @@ macro_rules! array_impls { } } - #[cfg(stage0)] - impl<S: hash::Writer + hash::Hasher, T: Hash<S>> Hash<S> for [T; $N] { - fn hash(&self, state: &mut S) { - Hash::hash(&self[..], state) - } - } - #[cfg(not(stage0))] #[stable(feature = "rust1", since = "1.0.0")] impl<T: Hash> Hash for [T; $N] { fn hash<H: hash::Hasher>(&self, state: &mut H) { diff --git a/src/libcore/hash/mod.rs b/src/libcore/hash/mod.rs index 2e83334b937..ed48903a7c2 100644 --- a/src/libcore/hash/mod.rs +++ b/src/libcore/hash/mod.rs @@ -73,7 +73,6 @@ mod sip; /// to compute the hash. Specific implementations of this trait may specialize /// for particular instances of `H` in order to be able to optimize the hashing /// behavior. -#[cfg(not(stage0))] #[stable(feature = "rust1", since = "1.0.0")] pub trait Hash { /// Feeds this value into the state given, updating the hasher as necessary. @@ -89,72 +88,40 @@ pub trait Hash { } } -/// A hashable type. -/// -/// The `H` type parameter is an abstract hash state that is used by the `Hash` -/// to compute the hash. Specific implementations of this trait may specialize -/// for particular instances of `H` in order to be able to optimize the hashing -/// behavior. -#[cfg(stage0)] -pub trait Hash<H: Hasher> { - /// Feeds this value into the state given, updating the hasher as necessary. - fn hash(&self, state: &mut H); -} - /// A trait which represents the ability to hash an arbitrary stream of bytes. #[stable(feature = "rust1", since = "1.0.0")] pub trait Hasher { - /// Result type of one run of hashing generated by this hasher. - #[cfg(stage0)] - type Output; - - /// Resets this hasher back to its initial state (as if it were just - /// created). - #[cfg(stage0)] - fn reset(&mut self); - - /// Completes a round of hashing, producing the output hash generated. - #[cfg(stage0)] - fn finish(&self) -> Self::Output; - /// Completes a round of hashing, producing the output hash generated. - #[cfg(not(stage0))] #[unstable(feature = "hash", reason = "module was recently redesigned")] fn finish(&self) -> u64; /// Writes some data into this `Hasher` - #[cfg(not(stage0))] #[stable(feature = "rust1", since = "1.0.0")] fn write(&mut self, bytes: &[u8]); /// Write a single `u8` into this hasher - #[cfg(not(stage0))] #[inline] #[unstable(feature = "hash", reason = "module was recently redesigned")] fn write_u8(&mut self, i: u8) { self.write(&[i]) } /// Write a single `u16` into this hasher. - #[cfg(not(stage0))] #[inline] #[unstable(feature = "hash", reason = "module was recently redesigned")] fn write_u16(&mut self, i: u16) { self.write(&unsafe { mem::transmute::<_, [u8; 2]>(i) }) } /// Write a single `u32` into this hasher. - #[cfg(not(stage0))] #[inline] #[unstable(feature = "hash", reason = "module was recently redesigned")] fn write_u32(&mut self, i: u32) { self.write(&unsafe { mem::transmute::<_, [u8; 4]>(i) }) } /// Write a single `u64` into this hasher. - #[cfg(not(stage0))] #[inline] #[unstable(feature = "hash", reason = "module was recently redesigned")] fn write_u64(&mut self, i: u64) { self.write(&unsafe { mem::transmute::<_, [u8; 8]>(i) }) } /// Write a single `usize` into this hasher. - #[cfg(not(stage0))] #[inline] #[unstable(feature = "hash", reason = "module was recently redesigned")] fn write_usize(&mut self, i: usize) { @@ -166,58 +133,31 @@ pub trait Hasher { } /// Write a single `i8` into this hasher. - #[cfg(not(stage0))] #[inline] #[unstable(feature = "hash", reason = "module was recently redesigned")] fn write_i8(&mut self, i: i8) { self.write_u8(i as u8) } /// Write a single `i16` into this hasher. - #[cfg(not(stage0))] #[inline] #[unstable(feature = "hash", reason = "module was recently redesigned")] fn write_i16(&mut self, i: i16) { self.write_u16(i as u16) } /// Write a single `i32` into this hasher. - #[cfg(not(stage0))] #[inline] #[unstable(feature = "hash", reason = "module was recently redesigned")] fn write_i32(&mut self, i: i32) { self.write_u32(i as u32) } /// Write a single `i64` into this hasher. - #[cfg(not(stage0))] #[inline] #[unstable(feature = "hash", reason = "module was recently redesigned")] fn write_i64(&mut self, i: i64) { self.write_u64(i as u64) } /// Write a single `isize` into this hasher. - #[cfg(not(stage0))] #[inline] #[unstable(feature = "hash", reason = "module was recently redesigned")] fn write_isize(&mut self, i: isize) { self.write_usize(i as usize) } } -/// A common bound on the `Hasher` parameter to `Hash` implementations in order -/// to generically hash an aggregate. -#[unstable(feature = "hash", - reason = "this trait will likely be replaced by io::Writer")] -#[allow(missing_docs)] -#[cfg(stage0)] -pub trait Writer { - fn write(&mut self, bytes: &[u8]); -} - /// Hash a value with the default SipHasher algorithm (two initial keys of 0). /// /// The specified value will be hashed with this hasher and then the resulting /// hash will be returned. -#[cfg(stage0)] -pub fn hash<T: Hash<H>, H: Hasher + Default>(value: &T) -> H::Output { - let mut h: H = Default::default(); - value.hash(&mut h); - h.finish() -} - -/// Hash a value with the default SipHasher algorithm (two initial keys of 0). -/// -/// The specified value will be hashed with this hasher and then the resulting -/// hash will be returned. -#[cfg(not(stage0))] #[unstable(feature = "hash", reason = "module was recently redesigned")] pub fn hash<T: Hash, H: Hasher + Default>(value: &T) -> u64 { let mut h: H = Default::default(); @@ -227,145 +167,6 @@ pub fn hash<T: Hash, H: Hasher + Default>(value: &T) -> u64 { ////////////////////////////////////////////////////////////////////////////// -#[cfg(stage0)] -mod impls { - use prelude::*; - - use mem; - use num::Int; - use super::*; - - macro_rules! impl_hash { - ($ty:ident, $uty:ident) => { - impl<S: Writer + Hasher> Hash<S> for $ty { - #[inline] - fn hash(&self, state: &mut S) { - let a: [u8; ::$ty::BYTES] = unsafe { - mem::transmute(*self) - }; - state.write(&a) - } - } - } - } - - impl_hash! { u8, u8 } - impl_hash! { u16, u16 } - impl_hash! { u32, u32 } - impl_hash! { u64, u64 } - impl_hash! { uint, uint } - impl_hash! { i8, u8 } - impl_hash! { i16, u16 } - impl_hash! { i32, u32 } - impl_hash! { i64, u64 } - impl_hash! { int, uint } - - impl<S: Writer + Hasher> Hash<S> for bool { - #[inline] - fn hash(&self, state: &mut S) { - (*self as u8).hash(state); - } - } - - impl<S: Writer + Hasher> Hash<S> for char { - #[inline] - fn hash(&self, state: &mut S) { - (*self as u32).hash(state); - } - } - - impl<S: Writer + Hasher> Hash<S> for str { - #[inline] - fn hash(&self, state: &mut S) { - state.write(self.as_bytes()); - 0xffu8.hash(state) - } - } - - macro_rules! impl_hash_tuple { - () => ( - impl<S: Hasher> Hash<S> for () { - #[inline] - fn hash(&self, _state: &mut S) {} - } - ); - - ( $($name:ident)+) => ( - impl<S: Hasher, $($name: Hash<S>),*> Hash<S> for ($($name,)*) { - #[inline] - #[allow(non_snake_case)] - fn hash(&self, state: &mut S) { - match *self { - ($(ref $name,)*) => { - $( - $name.hash(state); - )* - } - } - } - } - ); - } - - impl_hash_tuple! {} - impl_hash_tuple! { A } - impl_hash_tuple! { A B } - impl_hash_tuple! { A B C } - impl_hash_tuple! { A B C D } - impl_hash_tuple! { A B C D E } - impl_hash_tuple! { A B C D E F } - impl_hash_tuple! { A B C D E F G } - impl_hash_tuple! { A B C D E F G H } - impl_hash_tuple! { A B C D E F G H I } - impl_hash_tuple! { A B C D E F G H I J } - impl_hash_tuple! { A B C D E F G H I J K } - impl_hash_tuple! { A B C D E F G H I J K L } - - impl<S: Writer + Hasher, T: Hash<S>> Hash<S> for [T] { - #[inline] - fn hash(&self, state: &mut S) { - self.len().hash(state); - for elt in self { - elt.hash(state); - } - } - } - - - impl<'a, S: Hasher, T: ?Sized + Hash<S>> Hash<S> for &'a T { - #[inline] - fn hash(&self, state: &mut S) { - (**self).hash(state); - } - } - - impl<'a, S: Hasher, T: ?Sized + Hash<S>> Hash<S> for &'a mut T { - #[inline] - fn hash(&self, state: &mut S) { - (**self).hash(state); - } - } - - impl<S: Writer + Hasher, T> Hash<S> for *const T { - #[inline] - fn hash(&self, state: &mut S) { - // NB: raw-pointer Hash does _not_ dereference - // to the target; it just gives you the pointer-bytes. - (*self as uint).hash(state); - } - } - - impl<S: Writer + Hasher, T> Hash<S> for *mut T { - #[inline] - fn hash(&self, state: &mut S) { - // NB: raw-pointer Hash does _not_ dereference - // to the target; it just gives you the pointer-bytes. - (*self as uint).hash(state); - } - } -} - -#[cfg(not(stage0))] mod impls { use prelude::*; diff --git a/src/libcore/hash/sip.rs b/src/libcore/hash/sip.rs index ce8917cc205..6f24fc70673 100644 --- a/src/libcore/hash/sip.rs +++ b/src/libcore/hash/sip.rs @@ -16,8 +16,6 @@ use prelude::*; use default::Default; use super::Hasher; -#[cfg(stage0)] -use super::Writer; /// An implementation of SipHash 2-4. /// @@ -175,26 +173,9 @@ impl SipHasher { } } -#[cfg(stage0)] -impl Writer for SipHasher { - #[inline] - fn write(&mut self, msg: &[u8]) { - self.write(msg) - } -} - #[stable(feature = "rust1", since = "1.0.0")] impl Hasher for SipHasher { - #[cfg(stage0)] - type Output = u64; - - #[cfg(stage0)] - fn reset(&mut self) { - self.reset(); - } - #[inline] - #[cfg(not(stage0))] fn write(&mut self, msg: &[u8]) { self.write(msg) } diff --git a/src/libcore/marker.rs b/src/libcore/marker.rs index d284eb34179..99385725a99 100644 --- a/src/libcore/marker.rs +++ b/src/libcore/marker.rs @@ -32,19 +32,9 @@ use hash::Hash; use hash::Hasher; /// Types able to be transferred across thread boundaries. -#[unstable(feature = "core", - reason = "will be overhauled with new lifetime rules; see RFC 458")] -#[lang="send"] -#[rustc_on_unimplemented = "`{Self}` cannot be sent between threads safely"] -#[cfg(stage0)] -pub unsafe trait Send: 'static { - // empty. -} -/// Types able to be transferred across thread boundaries. #[stable(feature = "rust1", since = "1.0.0")] #[lang="send"] #[rustc_on_unimplemented = "`{Self}` cannot be sent between threads safely"] -#[cfg(not(stage0))] pub unsafe trait Send : MarkerTrait { // empty. } @@ -233,13 +223,6 @@ pub struct Managed; macro_rules! impls{ ($t: ident) => ( - #[cfg(stage0)] - impl<T:?Sized, S: Hasher> Hash<S> for $t<T> { - #[inline] - fn hash(&self, _: &mut S) { - } - } - #[cfg(not(stage0))] impl<T:?Sized> Hash for $t<T> { #[inline] fn hash<H: Hasher>(&self, _: &mut H) { @@ -348,14 +331,6 @@ impl<T:?Sized> MarkerTrait for T { } #[stable(feature = "rust1", since = "1.0.0")] pub trait PhantomFn<A:?Sized,R:?Sized=()> { } -#[cfg(stage0)] // built into the trait matching system after stage0 -impl<A:?Sized, R:?Sized, U:?Sized> PhantomFn<A,R> for U { } - -/// Specific to stage0. You should not be seeing these docs! -#[cfg(stage0)] -#[lang="covariant_type"] // only relevant to stage0 -pub struct PhantomData<T:?Sized>; - /// `PhantomData` is a way to tell the compiler about fake fields. /// Phantom data is required whenever type parameters are not used. /// The idea is that if the compiler encounters a `PhantomData<T>` @@ -374,14 +349,12 @@ pub struct PhantomData<T:?Sized>; /// here! For now, please see [RFC 738][738] for more information. /// /// [738]: https://github.com/rust-lang/rfcs/blob/master/text/0738-variance.md -#[cfg(not(stage0))] #[lang="phantom_data"] #[stable(feature = "rust1", since = "1.0.0")] pub struct PhantomData<T:?Sized>; impls! { PhantomData } -#[cfg(not(stage0))] mod impls { use super::{Send, Sync, Sized}; @@ -417,7 +390,6 @@ pub struct ContravariantType<T>; #[unstable(feature = "core", reason = "deprecated")] #[deprecated(since = "1.0.0", reason = "Replace with `PhantomData<T>`")] #[lang="covariant_type"] -#[cfg(not(stage0))] pub struct CovariantType<T>; /// Old-style marker trait. Deprecated. diff --git a/src/librustc/lint/mod.rs b/src/librustc/lint/mod.rs index bdcc10ebcec..021827b0101 100644 --- a/src/librustc/lint/mod.rs +++ b/src/librustc/lint/mod.rs @@ -185,14 +185,6 @@ impl PartialEq for LintId { impl Eq for LintId { } -#[cfg(stage0)] -impl<S: hash::Writer + hash::Hasher> hash::Hash<S> for LintId { - fn hash(&self, state: &mut S) { - let ptr = self.lint as *const Lint; - ptr.hash(state); - } -} -#[cfg(not(stage0))] impl hash::Hash for LintId { fn hash<H: hash::Hasher>(&self, state: &mut H) { let ptr = self.lint as *const Lint; diff --git a/src/librustc/metadata/encoder.rs b/src/librustc/metadata/encoder.rs index 42a70cec5df..b7cdf63dd99 100644 --- a/src/librustc/metadata/encoder.rs +++ b/src/librustc/metadata/encoder.rs @@ -1588,48 +1588,6 @@ fn encode_info_for_items(ecx: &EncodeContext, // Path and definition ID indexing -#[cfg(stage0)] -fn encode_index<T, F>(rbml_w: &mut Encoder, index: Vec<entry<T>>, mut write_fn: F) where - F: FnMut(&mut SeekableMemWriter, &T), - T: Hash<SipHasher>, -{ - let mut buckets: Vec<Vec<entry<T>>> = (0..256u16).map(|_| Vec::new()).collect(); - for elt in index { - let mut s = SipHasher::new(); - elt.val.hash(&mut s); - let h = s.finish() as uint; - (&mut buckets[h % 256]).push(elt); - } - - rbml_w.start_tag(tag_index); - let mut bucket_locs = Vec::new(); - rbml_w.start_tag(tag_index_buckets); - for bucket in &buckets { - bucket_locs.push(rbml_w.writer.tell().unwrap()); - rbml_w.start_tag(tag_index_buckets_bucket); - for elt in bucket { - rbml_w.start_tag(tag_index_buckets_bucket_elt); - assert!(elt.pos < 0xffff_ffff); - { - let wr: &mut SeekableMemWriter = rbml_w.writer; - wr.write_be_u32(elt.pos as u32); - } - write_fn(rbml_w.writer, &elt.val); - rbml_w.end_tag(); - } - rbml_w.end_tag(); - } - rbml_w.end_tag(); - rbml_w.start_tag(tag_index_table); - for pos in &bucket_locs { - assert!(*pos < 0xffff_ffff); - let wr: &mut SeekableMemWriter = rbml_w.writer; - wr.write_be_u32(*pos as u32); - } - rbml_w.end_tag(); - rbml_w.end_tag(); -} -#[cfg(not(stage0))] fn encode_index<T, F>(rbml_w: &mut Encoder, index: Vec<entry<T>>, mut write_fn: F) where F: FnMut(&mut SeekableMemWriter, &T), T: Hash, diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs index e9908397f97..87f0e1ed6c6 100644 --- a/src/librustc/middle/ty.rs +++ b/src/librustc/middle/ty.rs @@ -73,7 +73,6 @@ use std::cell::{Cell, RefCell}; use std::cmp; use std::fmt; use std::hash::{Hash, SipHasher, Hasher}; -#[cfg(stage0)] use std::hash::Writer; use std::mem; use std::ops; use std::rc::Rc; @@ -959,13 +958,6 @@ impl<'tcx> PartialEq for TyS<'tcx> { } impl<'tcx> Eq for TyS<'tcx> {} -#[cfg(stage0)] -impl<'tcx, S: Writer + Hasher> Hash<S> for TyS<'tcx> { - fn hash(&self, s: &mut S) { - (self as *const _).hash(s) - } -} -#[cfg(not(stage0))] impl<'tcx> Hash for TyS<'tcx> { fn hash<H: Hasher>(&self, s: &mut H) { (self as *const _).hash(s) @@ -988,13 +980,6 @@ impl<'tcx> PartialEq for InternedTy<'tcx> { impl<'tcx> Eq for InternedTy<'tcx> {} -#[cfg(stage0)] -impl<'tcx, S: Writer + Hasher> Hash<S> for InternedTy<'tcx> { - fn hash(&self, s: &mut S) { - self.ty.sty.hash(s) - } -} -#[cfg(not(stage0))] impl<'tcx> Hash for InternedTy<'tcx> { fn hash<H: Hasher>(&self, s: &mut H) { self.ty.sty.hash(s) diff --git a/src/librustc/util/common.rs b/src/librustc/util/common.rs index c9d50b9cecf..a3cc23b7bba 100644 --- a/src/librustc/util/common.rs +++ b/src/librustc/util/common.rs @@ -14,7 +14,6 @@ use std::cell::{RefCell, Cell}; use std::collections::HashMap; use std::fmt::Debug; use std::hash::Hash; -#[cfg(stage0)] use std::hash::Hasher; use std::iter::repeat; use std::time::Duration; use std::collections::hash_state::HashState; @@ -139,57 +138,13 @@ pub fn block_query<P>(b: &ast::Block, p: P) -> bool where P: FnMut(&ast::Expr) - /// K: Eq + Hash<S>, V, S, H: Hasher<S> /// -/// Determines whether there exists a path from `source` to `destination`. The graph is defined by -/// the `edges_map`, which maps from a node `S` to a list of its adjacent nodes `T`. +/// Determines whether there exists a path from `source` to `destination`. The +/// graph is defined by the `edges_map`, which maps from a node `S` to a list of +/// its adjacent nodes `T`. /// -/// Efficiency note: This is implemented in an inefficient way because it is typically invoked on -/// very small graphs. If the graphs become larger, a more efficient graph representation and -/// algorithm would probably be advised. -#[cfg(stage0)] -pub fn can_reach<T, S>(edges_map: &HashMap<T, Vec<T>, S>, source: T, - destination: T) -> bool - where S: HashState, - <S as HashState>::Hasher: Hasher<Output=u64>, - T: Hash<<S as HashState>::Hasher> + Eq + Clone, -{ - if source == destination { - return true; - } - - // Do a little breadth-first-search here. The `queue` list - // doubles as a way to detect if we've seen a particular FR - // before. Note that we expect this graph to be an *extremely - // shallow* tree. - let mut queue = vec!(source); - let mut i = 0; - while i < queue.len() { - match edges_map.get(&queue[i]) { - Some(edges) => { - for target in edges { - if *target == destination { - return true; - } - - if !queue.iter().any(|x| x == target) { - queue.push((*target).clone()); - } - } - } - None => {} - } - i += 1; - } - return false; -} -/// K: Eq + Hash<S>, V, S, H: Hasher<S> -/// -/// Determines whether there exists a path from `source` to `destination`. The graph is defined by -/// the `edges_map`, which maps from a node `S` to a list of its adjacent nodes `T`. -/// -/// Efficiency note: This is implemented in an inefficient way because it is typically invoked on -/// very small graphs. If the graphs become larger, a more efficient graph representation and -/// algorithm would probably be advised. -#[cfg(not(stage0))] +/// Efficiency note: This is implemented in an inefficient way because it is +/// typically invoked on very small graphs. If the graphs become larger, a more +/// efficient graph representation and algorithm would probably be advised. pub fn can_reach<T, S>(edges_map: &HashMap<T, Vec<T>, S>, source: T, destination: T) -> bool where S: HashState, T: Hash + Eq + Clone, @@ -250,52 +205,6 @@ pub fn can_reach<T, S>(edges_map: &HashMap<T, Vec<T>, S>, source: T, /// } /// ``` #[inline(always)] -#[cfg(stage0)] -pub fn memoized<T, U, S, F>(cache: &RefCell<HashMap<T, U, S>>, arg: T, f: F) -> U - where T: Clone + Hash<<S as HashState>::Hasher> + Eq, - U: Clone, - S: HashState, - <S as HashState>::Hasher: Hasher<Output=u64>, - F: FnOnce(T) -> U, -{ - let key = arg.clone(); - let result = cache.borrow().get(&key).cloned(); - match result { - Some(result) => result, - None => { - let result = f(arg); - cache.borrow_mut().insert(key, result.clone()); - result - } - } -} -/// Memoizes a one-argument closure using the given RefCell containing -/// a type implementing MutableMap to serve as a cache. -/// -/// In the future the signature of this function is expected to be: -/// ``` -/// pub fn memoized<T: Clone, U: Clone, M: MutableMap<T, U>>( -/// cache: &RefCell<M>, -/// f: &|T| -> U -/// ) -> impl |T| -> U { -/// ``` -/// but currently it is not possible. -/// -/// # Example -/// ``` -/// struct Context { -/// cache: RefCell<HashMap<uint, uint>> -/// } -/// -/// fn factorial(ctxt: &Context, n: uint) -> uint { -/// memoized(&ctxt.cache, n, |n| match n { -/// 0 | 1 => n, -/// _ => factorial(ctxt, n - 2) + factorial(ctxt, n - 1) -/// }) -/// } -/// ``` -#[inline(always)] -#[cfg(not(stage0))] pub fn memoized<T, U, S, F>(cache: &RefCell<HashMap<T, U, S>>, arg: T, f: F) -> U where T: Clone + Hash + Eq, U: Clone, diff --git a/src/librustc/util/nodemap.rs b/src/librustc/util/nodemap.rs index 1b07ce789e7..b15da7dab3e 100644 --- a/src/librustc/util/nodemap.rs +++ b/src/librustc/util/nodemap.rs @@ -16,7 +16,6 @@ use std::collections::hash_state::{DefaultState}; use std::collections::{HashMap, HashSet}; use std::default::Default; use std::hash::{Hasher, Hash}; -#[cfg(stage0)] use std::hash::Writer; use syntax::ast; pub type FnvHashMap<K, V> = HashMap<K, V, DefaultState<FnvHasher>>; @@ -28,19 +27,9 @@ pub type DefIdMap<T> = FnvHashMap<ast::DefId, T>; pub type NodeSet = FnvHashSet<ast::NodeId>; pub type DefIdSet = FnvHashSet<ast::DefId>; -#[cfg(stage0)] -pub fn FnvHashMap<K: Hash<FnvHasher> + Eq, V>() -> FnvHashMap<K, V> { - Default::default() -} -#[cfg(stage0)] -pub fn FnvHashSet<V: Hash<FnvHasher> + Eq>() -> FnvHashSet<V> { - Default::default() -} -#[cfg(not(stage0))] pub fn FnvHashMap<K: Hash + Eq, V>() -> FnvHashMap<K, V> { Default::default() } -#[cfg(not(stage0))] pub fn FnvHashSet<V: Hash + Eq>() -> FnvHashSet<V> { Default::default() } @@ -63,26 +52,6 @@ impl Default for FnvHasher { fn default() -> FnvHasher { FnvHasher(0xcbf29ce484222325) } } -#[cfg(stage0)] -impl Hasher for FnvHasher { - type Output = u64; - fn reset(&mut self) { *self = Default::default(); } - fn finish(&self) -> u64 { self.0 } -} - -#[cfg(stage0)] -impl Writer for FnvHasher { - fn write(&mut self, bytes: &[u8]) { - let FnvHasher(mut hash) = *self; - for byte in bytes { - hash = hash ^ (*byte as u64); - hash = hash * 0x100000001b3; - } - *self = FnvHasher(hash); - } -} - -#[cfg(not(stage0))] impl Hasher for FnvHasher { fn write(&mut self, bytes: &[u8]) { let FnvHasher(mut hash) = *self; diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs index 1d46c011bb3..0454af45b7c 100644 --- a/src/librustc/util/ppaux.rs +++ b/src/librustc/util/ppaux.rs @@ -29,7 +29,6 @@ use middle::ty_fold::TypeFoldable; use std::collections::HashMap; use std::collections::hash_state::HashState; use std::hash::Hash; -#[cfg(stage0)] use std::hash::Hasher; use std::rc::Rc; use syntax::abi; use syntax::ast_map; @@ -1434,23 +1433,6 @@ impl<'tcx, T:Repr<'tcx>> Repr<'tcx> for ty::Binder<T> { } } -#[cfg(stage0)] -impl<'tcx, S, K, V> Repr<'tcx> for HashMap<K, V, S> - where K: Hash<<S as HashState>::Hasher> + Eq + Repr<'tcx>, - V: Repr<'tcx>, - S: HashState, - <S as HashState>::Hasher: Hasher<Output=u64>, -{ - fn repr(&self, tcx: &ctxt<'tcx>) -> String { - format!("HashMap({})", - self.iter() - .map(|(k,v)| format!("{} => {}", k.repr(tcx), v.repr(tcx))) - .collect::<Vec<String>>() - .connect(", ")) - } -} - -#[cfg(not(stage0))] impl<'tcx, S, K, V> Repr<'tcx> for HashMap<K, V, S> where K: Hash + Eq + Repr<'tcx>, V: Repr<'tcx>, diff --git a/src/libserialize/collection_impls.rs b/src/libserialize/collection_impls.rs index 10cf02f85e8..e7430f698e9 100644 --- a/src/libserialize/collection_impls.rs +++ b/src/libserialize/collection_impls.rs @@ -13,7 +13,6 @@ use std::usize; use std::default::Default; use std::hash::Hash; -#[cfg(stage0)] use std::hash::Hasher; use std::collections::hash_state::HashState; use {Decodable, Encodable, Decoder, Encoder}; @@ -158,26 +157,6 @@ impl< } } -#[cfg(stage0)] -impl<K, V, S> Encodable for HashMap<K, V, S> - where K: Encodable + Hash< <S as HashState>::Hasher> + Eq, - V: Encodable, - S: HashState, - <S as HashState>::Hasher: Hasher<Output=u64> -{ - fn encode<E: Encoder>(&self, e: &mut E) -> Result<(), E::Error> { - e.emit_map(self.len(), |e| { - let mut i = 0; - for (key, val) in self { - try!(e.emit_map_elt_key(i, |e| key.encode(e))); - try!(e.emit_map_elt_val(i, |e| val.encode(e))); - i += 1; - } - Ok(()) - }) - } -} -#[cfg(not(stage0))] impl<K, V, S> Encodable for HashMap<K, V, S> where K: Encodable + Hash + Eq, V: Encodable, @@ -196,27 +175,6 @@ impl<K, V, S> Encodable for HashMap<K, V, S> } } -#[cfg(stage0)] -impl<K, V, S> Decodable for HashMap<K, V, S> - where K: Decodable + Hash< <S as HashState>::Hasher> + Eq, - V: Decodable, - S: HashState + Default, - <S as HashState>::Hasher: Hasher<Output=u64> -{ - fn decode<D: Decoder>(d: &mut D) -> Result<HashMap<K, V, S>, D::Error> { - d.read_map(|d, len| { - let state = Default::default(); - let mut map = HashMap::with_capacity_and_hash_state(len, state); - for i in 0..len { - let key = try!(d.read_map_elt_key(i, |d| Decodable::decode(d))); - let val = try!(d.read_map_elt_val(i, |d| Decodable::decode(d))); - map.insert(key, val); - } - Ok(map) - }) - } -} -#[cfg(not(stage0))] impl<K, V, S> Decodable for HashMap<K, V, S> where K: Decodable + Hash + Eq, V: Decodable, @@ -236,24 +194,6 @@ impl<K, V, S> Decodable for HashMap<K, V, S> } } -#[cfg(stage0)] -impl<T, S> Encodable for HashSet<T, S> - where T: Encodable + Hash< <S as HashState>::Hasher> + Eq, - S: HashState, - <S as HashState>::Hasher: Hasher<Output=u64> -{ - fn encode<E: Encoder>(&self, s: &mut E) -> Result<(), E::Error> { - s.emit_seq(self.len(), |s| { - let mut i = 0; - for e in self { - try!(s.emit_seq_elt(i, |s| e.encode(s))); - i += 1; - } - Ok(()) - }) - } -} -#[cfg(not(stage0))] impl<T, S> Encodable for HashSet<T, S> where T: Encodable + Hash + Eq, S: HashState, @@ -270,24 +210,6 @@ impl<T, S> Encodable for HashSet<T, S> } } -#[cfg(stage0)] -impl<T, S> Decodable for HashSet<T, S> - where T: Decodable + Hash< <S as HashState>::Hasher> + Eq, - S: HashState + Default, - <S as HashState>::Hasher: Hasher<Output=u64> -{ - fn decode<D: Decoder>(d: &mut D) -> Result<HashSet<T, S>, D::Error> { - d.read_seq(|d, len| { - let state = Default::default(); - let mut set = HashSet::with_capacity_and_hash_state(len, state); - for i in 0..len { - set.insert(try!(d.read_seq_elt(i, |d| Decodable::decode(d)))); - } - Ok(set) - }) - } -} -#[cfg(not(stage0))] impl<T, S> Decodable for HashSet<T, S> where T: Decodable + Hash + Eq, S: HashState + Default, diff --git a/src/libstd/collections/hash/map_stage0.rs b/src/libstd/collections/hash/map_stage0.rs deleted file mode 100644 index f9e5044c597..00000000000 --- a/src/libstd/collections/hash/map_stage0.rs +++ /dev/null @@ -1,2330 +0,0 @@ -// Copyright 2014-2015 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or -// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license -// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. -// -// ignore-lexer-test FIXME #15883 - -use self::Entry::*; -use self::SearchResult::*; -use self::VacantEntryState::*; - -use borrow::Borrow; -use clone::Clone; -use cmp::{max, Eq, PartialEq}; -use default::Default; -use fmt::{self, Debug}; -use hash::{self, Hash, SipHasher}; -use iter::{self, Iterator, ExactSizeIterator, IntoIterator, IteratorExt, FromIterator, Extend, Map}; -use marker::Sized; -use mem::{self, replace}; -use num::{Int, UnsignedInt}; -use ops::{Deref, FnMut, Index, IndexMut}; -use option::Option::{self, Some, None}; -use rand::{self, Rng}; -use result::Result::{self, Ok, Err}; - -use super::table::{ - self, - Bucket, - EmptyBucket, - FullBucket, - FullBucketImm, - FullBucketMut, - RawTable, - SafeHash -}; -use super::table::BucketState::{ - Empty, - Full, -}; -use super::state::HashState; - -const INITIAL_LOG2_CAP: usize = 5; -#[unstable(feature = "std_misc")] -pub const INITIAL_CAPACITY: usize = 1 << INITIAL_LOG2_CAP; // 2^5 - -/// The default behavior of HashMap implements a load factor of 90.9%. -/// This behavior is characterized by the following condition: -/// -/// - if size > 0.909 * capacity: grow the map -#[derive(Clone)] -struct DefaultResizePolicy; - -impl DefaultResizePolicy { - fn new() -> DefaultResizePolicy { - DefaultResizePolicy - } - - #[inline] - fn min_capacity(&self, usable_size: usize) -> usize { - // Here, we are rephrasing the logic by specifying the lower limit - // on capacity: - // - // - if `cap < size * 1.1`: grow the map - usable_size * 11 / 10 - } - - /// An inverse of `min_capacity`, approximately. - #[inline] - fn usable_capacity(&self, cap: usize) -> usize { - // As the number of entries approaches usable capacity, - // min_capacity(size) must be smaller than the internal capacity, - // so that the map is not resized: - // `min_capacity(usable_capacity(x)) <= x`. - // The left-hand side can only be smaller due to flooring by integer - // division. - // - // This doesn't have to be checked for overflow since allocation size - // in bytes will overflow earlier than multiplication by 10. - cap * 10 / 11 - } -} - -#[test] -fn test_resize_policy() { - use prelude::v1::*; - let rp = DefaultResizePolicy; - for n in 0..1000 { - assert!(rp.min_capacity(rp.usable_capacity(n)) <= n); - assert!(rp.usable_capacity(rp.min_capacity(n)) <= n); - } -} - -// The main performance trick in this hashmap is called Robin Hood Hashing. -// It gains its excellent performance from one essential operation: -// -// If an insertion collides with an existing element, and that element's -// "probe distance" (how far away the element is from its ideal location) -// is higher than how far we've already probed, swap the elements. -// -// This massively lowers variance in probe distance, and allows us to get very -// high load factors with good performance. The 90% load factor I use is rather -// conservative. -// -// > Why a load factor of approximately 90%? -// -// In general, all the distances to initial buckets will converge on the mean. -// At a load factor of α, the odds of finding the target bucket after k -// probes is approximately 1-α^k. If we set this equal to 50% (since we converge -// on the mean) and set k=8 (64-byte cache line / 8-byte hash), α=0.92. I round -// this down to make the math easier on the CPU and avoid its FPU. -// Since on average we start the probing in the middle of a cache line, this -// strategy pulls in two cache lines of hashes on every lookup. I think that's -// pretty good, but if you want to trade off some space, it could go down to one -// cache line on average with an α of 0.84. -// -// > Wait, what? Where did you get 1-α^k from? -// -// On the first probe, your odds of a collision with an existing element is α. -// The odds of doing this twice in a row is approximately α^2. For three times, -// α^3, etc. Therefore, the odds of colliding k times is α^k. The odds of NOT -// colliding after k tries is 1-α^k. -// -// The paper from 1986 cited below mentions an implementation which keeps track -// of the distance-to-initial-bucket histogram. This approach is not suitable -// for modern architectures because it requires maintaining an internal data -// structure. This allows very good first guesses, but we are most concerned -// with guessing entire cache lines, not individual indexes. Furthermore, array -// accesses are no longer linear and in one direction, as we have now. There -// is also memory and cache pressure that this would entail that would be very -// difficult to properly see in a microbenchmark. -// -// ## Future Improvements (FIXME!) -// -// Allow the load factor to be changed dynamically and/or at initialization. -// -// Also, would it be possible for us to reuse storage when growing the -// underlying table? This is exactly the use case for 'realloc', and may -// be worth exploring. -// -// ## Future Optimizations (FIXME!) -// -// Another possible design choice that I made without any real reason is -// parameterizing the raw table over keys and values. Technically, all we need -// is the size and alignment of keys and values, and the code should be just as -// efficient (well, we might need one for power-of-two size and one for not...). -// This has the potential to reduce code bloat in rust executables, without -// really losing anything except 4 words (key size, key alignment, val size, -// val alignment) which can be passed in to every call of a `RawTable` function. -// This would definitely be an avenue worth exploring if people start complaining -// about the size of rust executables. -// -// Annotate exceedingly likely branches in `table::make_hash` -// and `search_hashed` to reduce instruction cache pressure -// and mispredictions once it becomes possible (blocked on issue #11092). -// -// Shrinking the table could simply reallocate in place after moving buckets -// to the first half. -// -// The growth algorithm (fragment of the Proof of Correctness) -// -------------------- -// -// The growth algorithm is basically a fast path of the naive reinsertion- -// during-resize algorithm. Other paths should never be taken. -// -// Consider growing a robin hood hashtable of capacity n. Normally, we do this -// by allocating a new table of capacity `2n`, and then individually reinsert -// each element in the old table into the new one. This guarantees that the -// new table is a valid robin hood hashtable with all the desired statistical -// properties. Remark that the order we reinsert the elements in should not -// matter. For simplicity and efficiency, we will consider only linear -// reinsertions, which consist of reinserting all elements in the old table -// into the new one by increasing order of index. However we will not be -// starting our reinsertions from index 0 in general. If we start from index -// i, for the purpose of reinsertion we will consider all elements with real -// index j < i to have virtual index n + j. -// -// Our hash generation scheme consists of generating a 64-bit hash and -// truncating the most significant bits. When moving to the new table, we -// simply introduce a new bit to the front of the hash. Therefore, if an -// elements has ideal index i in the old table, it can have one of two ideal -// locations in the new table. If the new bit is 0, then the new ideal index -// is i. If the new bit is 1, then the new ideal index is n + i. Intuitively, -// we are producing two independent tables of size n, and for each element we -// independently choose which table to insert it into with equal probability. -// However the rather than wrapping around themselves on overflowing their -// indexes, the first table overflows into the first, and the first into the -// second. Visually, our new table will look something like: -// -// [yy_xxx_xxxx_xxx|xx_yyy_yyyy_yyy] -// -// Where x's are elements inserted into the first table, y's are elements -// inserted into the second, and _'s are empty sections. We now define a few -// key concepts that we will use later. Note that this is a very abstract -// perspective of the table. A real resized table would be at least half -// empty. -// -// Theorem: A linear robin hood reinsertion from the first ideal element -// produces identical results to a linear naive reinsertion from the same -// element. -// -// FIXME(Gankro, pczarn): review the proof and put it all in a separate doc.rs - -/// A hash map implementation which uses linear probing with Robin -/// Hood bucket stealing. -/// -/// The hashes are all keyed by the task-local random number generator -/// on creation by default. This means that the ordering of the keys is -/// randomized, but makes the tables more resistant to -/// denial-of-service attacks (Hash DoS). This behaviour can be -/// overridden with one of the constructors. -/// -/// It is required that the keys implement the `Eq` and `Hash` traits, although -/// this can frequently be achieved by using `#[derive(Eq, Hash)]`. -/// -/// Relevant papers/articles: -/// -/// 1. Pedro Celis. ["Robin Hood Hashing"](https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf) -/// 2. Emmanuel Goossaert. ["Robin Hood -/// hashing"](http://codecapsule.com/2013/11/11/robin-hood-hashing/) -/// 3. Emmanuel Goossaert. ["Robin Hood hashing: backward shift -/// deletion"](http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/) -/// -/// # Example -/// -/// ``` -/// use std::collections::HashMap; -/// -/// // type inference lets us omit an explicit type signature (which -/// // would be `HashMap<&str, &str>` in this example). -/// let mut book_reviews = HashMap::new(); -/// -/// // review some books. -/// book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book."); -/// book_reviews.insert("Grimms' Fairy Tales", "Masterpiece."); -/// book_reviews.insert("Pride and Prejudice", "Very enjoyable."); -/// book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot."); -/// -/// // check for a specific one. -/// if !book_reviews.contains_key(&("Les Misérables")) { -/// println!("We've got {} reviews, but Les Misérables ain't one.", -/// book_reviews.len()); -/// } -/// -/// // oops, this review has a lot of spelling mistakes, let's delete it. -/// book_reviews.remove(&("The Adventures of Sherlock Holmes")); -/// -/// // look up the values associated with some keys. -/// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"]; -/// for book in to_find.iter() { -/// match book_reviews.get(book) { -/// Some(review) => println!("{}: {}", *book, *review), -/// None => println!("{} is unreviewed.", *book) -/// } -/// } -/// -/// // iterate over everything. -/// for (book, review) in book_reviews.iter() { -/// println!("{}: \"{}\"", *book, *review); -/// } -/// ``` -/// -/// The easiest way to use `HashMap` with a custom type as key is to derive `Eq` and `Hash`. -/// We must also derive `PartialEq`. -/// -/// ``` -/// use std::collections::HashMap; -/// -/// #[derive(Hash, Eq, PartialEq, Debug)] -/// struct Viking { -/// name: String, -/// country: String, -/// } -/// -/// impl Viking { -/// /// Create a new Viking. -/// fn new(name: &str, country: &str) -> Viking { -/// Viking { name: name.to_string(), country: country.to_string() } -/// } -/// } -/// -/// // Use a HashMap to store the vikings' health points. -/// let mut vikings = HashMap::new(); -/// -/// vikings.insert(Viking::new("Einar", "Norway"), 25); -/// vikings.insert(Viking::new("Olaf", "Denmark"), 24); -/// vikings.insert(Viking::new("Harald", "Iceland"), 12); -/// -/// // Use derived implementation to print the status of the vikings. -/// for (viking, health) in vikings.iter() { -/// println!("{:?} has {} hp", viking, health); -/// } -/// ``` -#[derive(Clone)] -#[stable(feature = "rust1", since = "1.0.0")] -pub struct HashMap<K, V, S = RandomState> { - // All hashes are keyed on these values, to prevent hash collision attacks. - hash_state: S, - - table: RawTable<K, V>, - - resize_policy: DefaultResizePolicy, -} - -/// Search for a pre-hashed key. -fn search_hashed<K, V, M, F>(table: M, - hash: SafeHash, - mut is_match: F) - -> SearchResult<K, V, M> where - M: Deref<Target=RawTable<K, V>>, - F: FnMut(&K) -> bool, -{ - let size = table.size(); - let mut probe = Bucket::new(table, hash); - let ib = probe.index(); - - while probe.index() != ib + size { - let full = match probe.peek() { - Empty(b) => return TableRef(b.into_table()), // hit an empty bucket - Full(b) => b - }; - - if full.distance() + ib < full.index() { - // We can finish the search early if we hit any bucket - // with a lower distance to initial bucket than we've probed. - return TableRef(full.into_table()); - } - - // If the hash doesn't match, it can't be this one.. - if hash == full.hash() { - // If the key doesn't match, it can't be this one.. - if is_match(full.read().0) { - return FoundExisting(full); - } - } - - probe = full.next(); - } - - TableRef(probe.into_table()) -} - -fn pop_internal<K, V>(starting_bucket: FullBucketMut<K, V>) -> (K, V) { - let (empty, retkey, retval) = starting_bucket.take(); - let mut gap = match empty.gap_peek() { - Some(b) => b, - None => return (retkey, retval) - }; - - while gap.full().distance() != 0 { - gap = match gap.shift() { - Some(b) => b, - None => break - }; - } - - // Now we've done all our shifting. Return the value we grabbed earlier. - (retkey, retval) -} - -/// Perform robin hood bucket stealing at the given `bucket`. You must -/// also pass the position of that bucket's initial bucket so we don't have -/// to recalculate it. -/// -/// `hash`, `k`, and `v` are the elements to "robin hood" into the hashtable. -fn robin_hood<'a, K: 'a, V: 'a>(mut bucket: FullBucketMut<'a, K, V>, - mut ib: usize, - mut hash: SafeHash, - mut k: K, - mut v: V) - -> &'a mut V { - let starting_index = bucket.index(); - let size = { - let table = bucket.table(); // FIXME "lifetime too short". - table.size() - }; - // There can be at most `size - dib` buckets to displace, because - // in the worst case, there are `size` elements and we already are - // `distance` buckets away from the initial one. - let idx_end = starting_index + size - bucket.distance(); - - loop { - let (old_hash, old_key, old_val) = bucket.replace(hash, k, v); - loop { - let probe = bucket.next(); - assert!(probe.index() != idx_end); - - let full_bucket = match probe.peek() { - Empty(bucket) => { - // Found a hole! - let b = bucket.put(old_hash, old_key, old_val); - // Now that it's stolen, just read the value's pointer - // right out of the table! - return Bucket::at_index(b.into_table(), starting_index) - .peek() - .expect_full() - .into_mut_refs() - .1; - }, - Full(bucket) => bucket - }; - - let probe_ib = full_bucket.index() - full_bucket.distance(); - - bucket = full_bucket; - - // Robin hood! Steal the spot. - if ib < probe_ib { - ib = probe_ib; - hash = old_hash; - k = old_key; - v = old_val; - break; - } - } - } -} - -/// A result that works like Option<FullBucket<..>> but preserves -/// the reference that grants us access to the table in any case. -enum SearchResult<K, V, M> { - // This is an entry that holds the given key: - FoundExisting(FullBucket<K, V, M>), - - // There was no such entry. The reference is given back: - TableRef(M) -} - -impl<K, V, M> SearchResult<K, V, M> { - fn into_option(self) -> Option<FullBucket<K, V, M>> { - match self { - FoundExisting(bucket) => Some(bucket), - TableRef(_) => None - } - } -} - -impl<K, V, S, H> HashMap<K, V, S> - where K: Eq + Hash<H>, - S: HashState<Hasher=H>, - H: hash::Hasher<Output=u64> -{ - fn make_hash<X: ?Sized>(&self, x: &X) -> SafeHash where X: Hash<H> { - table::make_hash(&self.hash_state, x) - } - - /// Search for a key, yielding the index if it's found in the hashtable. - /// If you already have the hash for the key lying around, use - /// search_hashed. - fn search<'a, Q: ?Sized>(&'a self, q: &Q) -> Option<FullBucketImm<'a, K, V>> - where K: Borrow<Q>, Q: Eq + Hash<H> - { - let hash = self.make_hash(q); - search_hashed(&self.table, hash, |k| q.eq(k.borrow())) - .into_option() - } - - fn search_mut<'a, Q: ?Sized>(&'a mut self, q: &Q) -> Option<FullBucketMut<'a, K, V>> - where K: Borrow<Q>, Q: Eq + Hash<H> - { - let hash = self.make_hash(q); - search_hashed(&mut self.table, hash, |k| q.eq(k.borrow())) - .into_option() - } - - // The caller should ensure that invariants by Robin Hood Hashing hold. - fn insert_hashed_ordered(&mut self, hash: SafeHash, k: K, v: V) { - let cap = self.table.capacity(); - let mut buckets = Bucket::new(&mut self.table, hash); - let ib = buckets.index(); - - while buckets.index() != ib + cap { - // We don't need to compare hashes for value swap. - // Not even DIBs for Robin Hood. - buckets = match buckets.peek() { - Empty(empty) => { - empty.put(hash, k, v); - return; - } - Full(b) => b.into_bucket() - }; - buckets.next(); - } - panic!("Internal HashMap error: Out of space."); - } -} - -impl<K: Hash<Hasher> + Eq, V> HashMap<K, V, RandomState> { - /// Create an empty HashMap. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// let mut map: HashMap<&str, int> = HashMap::new(); - /// ``` - #[inline] - #[stable(feature = "rust1", since = "1.0.0")] - pub fn new() -> HashMap<K, V, RandomState> { - Default::default() - } - - /// Creates an empty hash map with the given initial capacity. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// let mut map: HashMap<&str, int> = HashMap::with_capacity(10); - /// ``` - #[inline] - #[stable(feature = "rust1", since = "1.0.0")] - pub fn with_capacity(capacity: usize) -> HashMap<K, V, RandomState> { - HashMap::with_capacity_and_hash_state(capacity, Default::default()) - } -} - -impl<K, V, S, H> HashMap<K, V, S> - where K: Eq + Hash<H>, - S: HashState<Hasher=H>, - H: hash::Hasher<Output=u64> -{ - /// Creates an empty hashmap which will use the given hasher to hash keys. - /// - /// The creates map has the default initial capacity. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// use std::collections::hash_map::RandomState; - /// - /// let s = RandomState::new(); - /// let mut map = HashMap::with_hash_state(s); - /// map.insert(1, 2); - /// ``` - #[inline] - #[unstable(feature = "std_misc", reason = "hasher stuff is unclear")] - pub fn with_hash_state(hash_state: S) -> HashMap<K, V, S> { - HashMap { - hash_state: hash_state, - resize_policy: DefaultResizePolicy::new(), - table: RawTable::new(0), - } - } - - /// Create an empty HashMap with space for at least `capacity` - /// elements, using `hasher` to hash the keys. - /// - /// Warning: `hasher` is normally randomly generated, and - /// is designed to allow HashMaps to be resistant to attacks that - /// cause many collisions and very poor performance. Setting it - /// manually using this function can expose a DoS attack vector. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// use std::collections::hash_map::RandomState; - /// - /// let s = RandomState::new(); - /// let mut map = HashMap::with_capacity_and_hash_state(10, s); - /// map.insert(1, 2); - /// ``` - #[inline] - #[unstable(feature = "std_misc", reason = "hasher stuff is unclear")] - pub fn with_capacity_and_hash_state(capacity: usize, hash_state: S) - -> HashMap<K, V, S> { - let resize_policy = DefaultResizePolicy::new(); - let min_cap = max(INITIAL_CAPACITY, resize_policy.min_capacity(capacity)); - let internal_cap = min_cap.checked_next_power_of_two().expect("capacity overflow"); - assert!(internal_cap >= capacity, "capacity overflow"); - HashMap { - hash_state: hash_state, - resize_policy: resize_policy, - table: RawTable::new(internal_cap), - } - } - - /// Returns the number of elements the map can hold without reallocating. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// let map: HashMap<int, int> = HashMap::with_capacity(100); - /// assert!(map.capacity() >= 100); - /// ``` - #[inline] - #[stable(feature = "rust1", since = "1.0.0")] - pub fn capacity(&self) -> usize { - self.resize_policy.usable_capacity(self.table.capacity()) - } - - /// Reserves capacity for at least `additional` more elements to be inserted - /// in the `HashMap`. The collection may reserve more space to avoid - /// frequent reallocations. - /// - /// # Panics - /// - /// Panics if the new allocation size overflows `usize`. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// let mut map: HashMap<&str, int> = HashMap::new(); - /// map.reserve(10); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn reserve(&mut self, additional: usize) { - let new_size = self.len().checked_add(additional).expect("capacity overflow"); - let min_cap = self.resize_policy.min_capacity(new_size); - - // An invalid value shouldn't make us run out of space. This includes - // an overflow check. - assert!(new_size <= min_cap); - - if self.table.capacity() < min_cap { - let new_capacity = max(min_cap.next_power_of_two(), INITIAL_CAPACITY); - self.resize(new_capacity); - } - } - - /// Resizes the internal vectors to a new capacity. It's your responsibility to: - /// 1) Make sure the new capacity is enough for all the elements, accounting - /// for the load factor. - /// 2) Ensure new_capacity is a power of two or zero. - fn resize(&mut self, new_capacity: usize) { - assert!(self.table.size() <= new_capacity); - assert!(new_capacity.is_power_of_two() || new_capacity == 0); - - let mut old_table = replace(&mut self.table, RawTable::new(new_capacity)); - let old_size = old_table.size(); - - if old_table.capacity() == 0 || old_table.size() == 0 { - return; - } - - // Grow the table. - // Specialization of the other branch. - let mut bucket = Bucket::first(&mut old_table); - - // "So a few of the first shall be last: for many be called, - // but few chosen." - // - // We'll most likely encounter a few buckets at the beginning that - // have their initial buckets near the end of the table. They were - // placed at the beginning as the probe wrapped around the table - // during insertion. We must skip forward to a bucket that won't - // get reinserted too early and won't unfairly steal others spot. - // This eliminates the need for robin hood. - loop { - bucket = match bucket.peek() { - Full(full) => { - if full.distance() == 0 { - // This bucket occupies its ideal spot. - // It indicates the start of another "cluster". - bucket = full.into_bucket(); - break; - } - // Leaving this bucket in the last cluster for later. - full.into_bucket() - } - Empty(b) => { - // Encountered a hole between clusters. - b.into_bucket() - } - }; - bucket.next(); - } - - // This is how the buckets might be laid out in memory: - // ($ marks an initialized bucket) - // ________________ - // |$$$_$$$$$$_$$$$$| - // - // But we've skipped the entire initial cluster of buckets - // and will continue iteration in this order: - // ________________ - // |$$$$$$_$$$$$ - // ^ wrap around once end is reached - // ________________ - // $$$_____________| - // ^ exit once table.size == 0 - loop { - bucket = match bucket.peek() { - Full(bucket) => { - let h = bucket.hash(); - let (b, k, v) = bucket.take(); - self.insert_hashed_ordered(h, k, v); - { - let t = b.table(); // FIXME "lifetime too short". - if t.size() == 0 { break } - }; - b.into_bucket() - } - Empty(b) => b.into_bucket() - }; - bucket.next(); - } - - assert_eq!(self.table.size(), old_size); - } - - /// Shrinks the capacity of the map as much as possible. It will drop - /// down as much as possible while maintaining the internal rules - /// and possibly leaving some space in accordance with the resize policy. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map: HashMap<int, int> = HashMap::with_capacity(100); - /// map.insert(1, 2); - /// map.insert(3, 4); - /// assert!(map.capacity() >= 100); - /// map.shrink_to_fit(); - /// assert!(map.capacity() >= 2); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn shrink_to_fit(&mut self) { - let min_capacity = self.resize_policy.min_capacity(self.len()); - let min_capacity = max(min_capacity.next_power_of_two(), INITIAL_CAPACITY); - - // An invalid value shouldn't make us run out of space. - debug_assert!(self.len() <= min_capacity); - - if self.table.capacity() != min_capacity { - let old_table = replace(&mut self.table, RawTable::new(min_capacity)); - let old_size = old_table.size(); - - // Shrink the table. Naive algorithm for resizing: - for (h, k, v) in old_table.into_iter() { - self.insert_hashed_nocheck(h, k, v); - } - - debug_assert_eq!(self.table.size(), old_size); - } - } - - /// Insert a pre-hashed key-value pair, without first checking - /// that there's enough room in the buckets. Returns a reference to the - /// newly insert value. - /// - /// If the key already exists, the hashtable will be returned untouched - /// and a reference to the existing element will be returned. - fn insert_hashed_nocheck(&mut self, hash: SafeHash, k: K, v: V) -> &mut V { - self.insert_or_replace_with(hash, k, v, |_, _, _| ()) - } - - fn insert_or_replace_with<'a, F>(&'a mut self, - hash: SafeHash, - k: K, - v: V, - mut found_existing: F) - -> &'a mut V where - F: FnMut(&mut K, &mut V, V), - { - // Worst case, we'll find one empty bucket among `size + 1` buckets. - let size = self.table.size(); - let mut probe = Bucket::new(&mut self.table, hash); - let ib = probe.index(); - - loop { - let mut bucket = match probe.peek() { - Empty(bucket) => { - // Found a hole! - return bucket.put(hash, k, v).into_mut_refs().1; - } - Full(bucket) => bucket - }; - - // hash matches? - if bucket.hash() == hash { - // key matches? - if k == *bucket.read_mut().0 { - let (bucket_k, bucket_v) = bucket.into_mut_refs(); - debug_assert!(k == *bucket_k); - // Key already exists. Get its reference. - found_existing(bucket_k, bucket_v, v); - return bucket_v; - } - } - - let robin_ib = bucket.index() as int - bucket.distance() as int; - - if (ib as int) < robin_ib { - // Found a luckier bucket than me. Better steal his spot. - return robin_hood(bucket, robin_ib as usize, hash, k, v); - } - - probe = bucket.next(); - assert!(probe.index() != ib + size + 1); - } - } - - /// An iterator visiting all keys in arbitrary order. - /// Iterator element type is `&'a K`. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map = HashMap::new(); - /// map.insert("a", 1); - /// map.insert("b", 2); - /// map.insert("c", 3); - /// - /// for key in map.keys() { - /// println!("{}", key); - /// } - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn keys<'a>(&'a self) -> Keys<'a, K, V> { - fn first<A, B>((a, _): (A, B)) -> A { a } - let first: fn((&'a K,&'a V)) -> &'a K = first; // coerce to fn ptr - - Keys { inner: self.iter().map(first) } - } - - /// An iterator visiting all values in arbitrary order. - /// Iterator element type is `&'a V`. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map = HashMap::new(); - /// map.insert("a", 1); - /// map.insert("b", 2); - /// map.insert("c", 3); - /// - /// for val in map.values() { - /// println!("{}", val); - /// } - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn values<'a>(&'a self) -> Values<'a, K, V> { - fn second<A, B>((_, b): (A, B)) -> B { b } - let second: fn((&'a K,&'a V)) -> &'a V = second; // coerce to fn ptr - - Values { inner: self.iter().map(second) } - } - - /// An iterator visiting all key-value pairs in arbitrary order. - /// Iterator element type is `(&'a K, &'a V)`. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map = HashMap::new(); - /// map.insert("a", 1); - /// map.insert("b", 2); - /// map.insert("c", 3); - /// - /// for (key, val) in map.iter() { - /// println!("key: {} val: {}", key, val); - /// } - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn iter(&self) -> Iter<K, V> { - Iter { inner: self.table.iter() } - } - - /// An iterator visiting all key-value pairs in arbitrary order, - /// with mutable references to the values. - /// Iterator element type is `(&'a K, &'a mut V)`. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map = HashMap::new(); - /// map.insert("a", 1); - /// map.insert("b", 2); - /// map.insert("c", 3); - /// - /// // Update all values - /// for (_, val) in map.iter_mut() { - /// *val *= 2; - /// } - /// - /// for (key, val) in map.iter() { - /// println!("key: {} val: {}", key, val); - /// } - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn iter_mut(&mut self) -> IterMut<K, V> { - IterMut { inner: self.table.iter_mut() } - } - - /// Creates a consuming iterator, that is, one that moves each key-value - /// pair out of the map in arbitrary order. The map cannot be used after - /// calling this. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map = HashMap::new(); - /// map.insert("a", 1); - /// map.insert("b", 2); - /// map.insert("c", 3); - /// - /// // Not possible with .iter() - /// let vec: Vec<(&str, int)> = map.into_iter().collect(); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn into_iter(self) -> IntoIter<K, V> { - fn last_two<A, B, C>((_, b, c): (A, B, C)) -> (B, C) { (b, c) } - let last_two: fn((SafeHash, K, V)) -> (K, V) = last_two; - - IntoIter { - inner: self.table.into_iter().map(last_two) - } - } - - /// Gets the given key's corresponding entry in the map for in-place manipulation. - #[stable(feature = "rust1", since = "1.0.0")] - pub fn entry(&mut self, key: K) -> Entry<K, V> { - // Gotta resize now. - self.reserve(1); - - let hash = self.make_hash(&key); - search_entry_hashed(&mut self.table, hash, key) - } - - /// Returns the number of elements in the map. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut a = HashMap::new(); - /// assert_eq!(a.len(), 0); - /// a.insert(1, "a"); - /// assert_eq!(a.len(), 1); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn len(&self) -> usize { self.table.size() } - - /// Returns true if the map contains no elements. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut a = HashMap::new(); - /// assert!(a.is_empty()); - /// a.insert(1, "a"); - /// assert!(!a.is_empty()); - /// ``` - #[inline] - #[stable(feature = "rust1", since = "1.0.0")] - pub fn is_empty(&self) -> bool { self.len() == 0 } - - /// Clears the map, returning all key-value pairs as an iterator. Keeps the - /// allocated memory for reuse. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut a = HashMap::new(); - /// a.insert(1, "a"); - /// a.insert(2, "b"); - /// - /// for (k, v) in a.drain().take(1) { - /// assert!(k == 1 || k == 2); - /// assert!(v == "a" || v == "b"); - /// } - /// - /// assert!(a.is_empty()); - /// ``` - #[inline] - #[unstable(feature = "std_misc", - reason = "matches collection reform specification, waiting for dust to settle")] - pub fn drain(&mut self) -> Drain<K, V> { - fn last_two<A, B, C>((_, b, c): (A, B, C)) -> (B, C) { (b, c) } - let last_two: fn((SafeHash, K, V)) -> (K, V) = last_two; // coerce to fn pointer - - Drain { - inner: self.table.drain().map(last_two), - } - } - - /// Clears the map, removing all key-value pairs. Keeps the allocated memory - /// for reuse. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut a = HashMap::new(); - /// a.insert(1, "a"); - /// a.clear(); - /// assert!(a.is_empty()); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - #[inline] - pub fn clear(&mut self) { - self.drain(); - } - - /// Returns a reference to the value corresponding to the key. - /// - /// The key may be any borrowed form of the map's key type, but - /// `Hash` and `Eq` on the borrowed form *must* match those for - /// the key type. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map = HashMap::new(); - /// map.insert(1, "a"); - /// assert_eq!(map.get(&1), Some(&"a")); - /// assert_eq!(map.get(&2), None); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V> - where K: Borrow<Q>, Q: Hash<H> + Eq - { - self.search(k).map(|bucket| bucket.into_refs().1) - } - - /// Returns true if the map contains a value for the specified key. - /// - /// The key may be any borrowed form of the map's key type, but - /// `Hash` and `Eq` on the borrowed form *must* match those for - /// the key type. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map = HashMap::new(); - /// map.insert(1, "a"); - /// assert_eq!(map.contains_key(&1), true); - /// assert_eq!(map.contains_key(&2), false); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool - where K: Borrow<Q>, Q: Hash<H> + Eq - { - self.search(k).is_some() - } - - /// Returns a mutable reference to the value corresponding to the key. - /// - /// The key may be any borrowed form of the map's key type, but - /// `Hash` and `Eq` on the borrowed form *must* match those for - /// the key type. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map = HashMap::new(); - /// map.insert(1, "a"); - /// match map.get_mut(&1) { - /// Some(x) => *x = "b", - /// None => (), - /// } - /// assert_eq!(map[1], "b"); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V> - where K: Borrow<Q>, Q: Hash<H> + Eq - { - self.search_mut(k).map(|bucket| bucket.into_mut_refs().1) - } - - /// Inserts a key-value pair from the map. If the key already had a value - /// present in the map, that value is returned. Otherwise, `None` is returned. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map = HashMap::new(); - /// assert_eq!(map.insert(37, "a"), None); - /// assert_eq!(map.is_empty(), false); - /// - /// map.insert(37, "b"); - /// assert_eq!(map.insert(37, "c"), Some("b")); - /// assert_eq!(map[37], "c"); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn insert(&mut self, k: K, v: V) -> Option<V> { - let hash = self.make_hash(&k); - self.reserve(1); - - let mut retval = None; - self.insert_or_replace_with(hash, k, v, |_, val_ref, val| { - retval = Some(replace(val_ref, val)); - }); - retval - } - - /// Removes a key from the map, returning the value at the key if the key - /// was previously in the map. - /// - /// The key may be any borrowed form of the map's key type, but - /// `Hash` and `Eq` on the borrowed form *must* match those for - /// the key type. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map = HashMap::new(); - /// map.insert(1, "a"); - /// assert_eq!(map.remove(&1), Some("a")); - /// assert_eq!(map.remove(&1), None); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V> - where K: Borrow<Q>, Q: Hash<H> + Eq - { - if self.table.size() == 0 { - return None - } - - self.search_mut(k).map(|bucket| pop_internal(bucket).1) - } -} - -fn search_entry_hashed<'a, K: Eq, V>(table: &'a mut RawTable<K,V>, hash: SafeHash, k: K) - -> Entry<'a, K, V> -{ - // Worst case, we'll find one empty bucket among `size + 1` buckets. - let size = table.size(); - let mut probe = Bucket::new(table, hash); - let ib = probe.index(); - - loop { - let bucket = match probe.peek() { - Empty(bucket) => { - // Found a hole! - return Vacant(VacantEntry { - hash: hash, - key: k, - elem: NoElem(bucket), - }); - }, - Full(bucket) => bucket - }; - - // hash matches? - if bucket.hash() == hash { - // key matches? - if k == *bucket.read().0 { - return Occupied(OccupiedEntry{ - elem: bucket, - }); - } - } - - let robin_ib = bucket.index() as int - bucket.distance() as int; - - if (ib as int) < robin_ib { - // Found a luckier bucket than me. Better steal his spot. - return Vacant(VacantEntry { - hash: hash, - key: k, - elem: NeqElem(bucket, robin_ib as usize), - }); - } - - probe = bucket.next(); - assert!(probe.index() != ib + size + 1); - } -} - -impl<K, V, S, H> PartialEq for HashMap<K, V, S> - where K: Eq + Hash<H>, V: PartialEq, - S: HashState<Hasher=H>, - H: hash::Hasher<Output=u64> -{ - fn eq(&self, other: &HashMap<K, V, S>) -> bool { - if self.len() != other.len() { return false; } - - self.iter().all(|(key, value)| - other.get(key).map_or(false, |v| *value == *v) - ) - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<K, V, S, H> Eq for HashMap<K, V, S> - where K: Eq + Hash<H>, V: Eq, - S: HashState<Hasher=H>, - H: hash::Hasher<Output=u64> -{} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<K, V, S, H> Debug for HashMap<K, V, S> - where K: Eq + Hash<H> + Debug, V: Debug, - S: HashState<Hasher=H>, - H: hash::Hasher<Output=u64> -{ - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - try!(write!(f, "HashMap {{")); - - for (i, (k, v)) in self.iter().enumerate() { - if i != 0 { try!(write!(f, ", ")); } - try!(write!(f, "{:?}: {:?}", *k, *v)); - } - - write!(f, "}}") - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<K, V, S, H> Default for HashMap<K, V, S> - where K: Eq + Hash<H>, - S: HashState<Hasher=H> + Default, - H: hash::Hasher<Output=u64> -{ - fn default() -> HashMap<K, V, S> { - HashMap::with_hash_state(Default::default()) - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<K, Q: ?Sized, V, S, H> Index<Q> for HashMap<K, V, S> - where K: Eq + Hash<H> + Borrow<Q>, - Q: Eq + Hash<H>, - S: HashState<Hasher=H>, - H: hash::Hasher<Output=u64> -{ - type Output = V; - - #[inline] - fn index<'a>(&'a self, index: &Q) -> &'a V { - self.get(index).expect("no entry found for key") - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<K, V, S, H, Q: ?Sized> IndexMut<Q> for HashMap<K, V, S> - where K: Eq + Hash<H> + Borrow<Q>, - Q: Eq + Hash<H>, - S: HashState<Hasher=H>, - H: hash::Hasher<Output=u64> -{ - #[inline] - fn index_mut<'a>(&'a mut self, index: &Q) -> &'a mut V { - self.get_mut(index).expect("no entry found for key") - } -} - -/// HashMap iterator. -#[stable(feature = "rust1", since = "1.0.0")] -pub struct Iter<'a, K: 'a, V: 'a> { - inner: table::Iter<'a, K, V> -} - -// FIXME(#19839) Remove in favor of `#[derive(Clone)]` -impl<'a, K, V> Clone for Iter<'a, K, V> { - fn clone(&self) -> Iter<'a, K, V> { - Iter { - inner: self.inner.clone() - } - } -} - -/// HashMap mutable values iterator. -#[stable(feature = "rust1", since = "1.0.0")] -pub struct IterMut<'a, K: 'a, V: 'a> { - inner: table::IterMut<'a, K, V> -} - -/// HashMap move iterator. -#[stable(feature = "rust1", since = "1.0.0")] -pub struct IntoIter<K, V> { - inner: iter::Map<table::IntoIter<K, V>, fn((SafeHash, K, V)) -> (K, V)> -} - -/// HashMap keys iterator. -#[stable(feature = "rust1", since = "1.0.0")] -pub struct Keys<'a, K: 'a, V: 'a> { - inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a K> -} - -// FIXME(#19839) Remove in favor of `#[derive(Clone)]` -impl<'a, K, V> Clone for Keys<'a, K, V> { - fn clone(&self) -> Keys<'a, K, V> { - Keys { - inner: self.inner.clone() - } - } -} - -/// HashMap values iterator. -#[stable(feature = "rust1", since = "1.0.0")] -pub struct Values<'a, K: 'a, V: 'a> { - inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a V> -} - -// FIXME(#19839) Remove in favor of `#[derive(Clone)]` -impl<'a, K, V> Clone for Values<'a, K, V> { - fn clone(&self) -> Values<'a, K, V> { - Values { - inner: self.inner.clone() - } - } -} - -/// HashMap drain iterator. -#[unstable(feature = "std_misc", - reason = "matches collection reform specification, waiting for dust to settle")] -pub struct Drain<'a, K: 'a, V: 'a> { - inner: iter::Map<table::Drain<'a, K, V>, fn((SafeHash, K, V)) -> (K, V)> -} - -/// A view into a single occupied location in a HashMap. -#[unstable(feature = "std_misc", - reason = "precise API still being fleshed out")] -pub struct OccupiedEntry<'a, K: 'a, V: 'a> { - elem: FullBucket<K, V, &'a mut RawTable<K, V>>, -} - -/// A view into a single empty location in a HashMap. -#[unstable(feature = "std_misc", - reason = "precise API still being fleshed out")] -pub struct VacantEntry<'a, K: 'a, V: 'a> { - hash: SafeHash, - key: K, - elem: VacantEntryState<K, V, &'a mut RawTable<K, V>>, -} - -/// A view into a single location in a map, which may be vacant or occupied. -#[unstable(feature = "std_misc", - reason = "precise API still being fleshed out")] -pub enum Entry<'a, K: 'a, V: 'a> { - /// An occupied Entry. - Occupied(OccupiedEntry<'a, K, V>), - /// A vacant Entry. - Vacant(VacantEntry<'a, K, V>), -} - -/// Possible states of a VacantEntry. -enum VacantEntryState<K, V, M> { - /// The index is occupied, but the key to insert has precedence, - /// and will kick the current one out on insertion. - NeqElem(FullBucket<K, V, M>, usize), - /// The index is genuinely vacant. - NoElem(EmptyBucket<K, V, M>), -} - -impl<'a, K, V, S, H> IntoIterator for &'a HashMap<K, V, S> - where K: Eq + Hash<H>, - S: HashState<Hasher=H>, - H: hash::Hasher<Output=u64> -{ - type Item = (&'a K, &'a V); - type IntoIter = Iter<'a, K, V>; - - fn into_iter(self) -> Iter<'a, K, V> { - self.iter() - } -} - -impl<'a, K, V, S, H> IntoIterator for &'a mut HashMap<K, V, S> - where K: Eq + Hash<H>, - S: HashState<Hasher=H>, - H: hash::Hasher<Output=u64> -{ - type Item = (&'a K, &'a mut V); - type IntoIter = IterMut<'a, K, V>; - - fn into_iter(mut self) -> IterMut<'a, K, V> { - self.iter_mut() - } -} - -impl<K, V, S, H> IntoIterator for HashMap<K, V, S> - where K: Eq + Hash<H>, - S: HashState<Hasher=H>, - H: hash::Hasher<Output=u64> -{ - type Item = (K, V); - type IntoIter = IntoIter<K, V>; - - fn into_iter(self) -> IntoIter<K, V> { - self.into_iter() - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> Iterator for Iter<'a, K, V> { - type Item = (&'a K, &'a V); - - #[inline] fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() } - #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } -} -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> { - #[inline] fn len(&self) -> usize { self.inner.len() } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> Iterator for IterMut<'a, K, V> { - type Item = (&'a K, &'a mut V); - - #[inline] fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() } - #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } -} -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> { - #[inline] fn len(&self) -> usize { self.inner.len() } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<K, V> Iterator for IntoIter<K, V> { - type Item = (K, V); - - #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() } - #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } -} -#[stable(feature = "rust1", since = "1.0.0")] -impl<K, V> ExactSizeIterator for IntoIter<K, V> { - #[inline] fn len(&self) -> usize { self.inner.len() } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> Iterator for Keys<'a, K, V> { - type Item = &'a K; - - #[inline] fn next(&mut self) -> Option<(&'a K)> { self.inner.next() } - #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } -} -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> { - #[inline] fn len(&self) -> usize { self.inner.len() } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> Iterator for Values<'a, K, V> { - type Item = &'a V; - - #[inline] fn next(&mut self) -> Option<(&'a V)> { self.inner.next() } - #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } -} -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> { - #[inline] fn len(&self) -> usize { self.inner.len() } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> Iterator for Drain<'a, K, V> { - type Item = (K, V); - - #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() } - #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } -} -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> ExactSizeIterator for Drain<'a, K, V> { - #[inline] fn len(&self) -> usize { self.inner.len() } -} - -#[unstable(feature = "std_misc", - reason = "matches collection reform v2 specification, waiting for dust to settle")] -impl<'a, K, V> Entry<'a, K, V> { - /// Returns a mutable reference to the entry if occupied, or the VacantEntry if vacant. - pub fn get(self) -> Result<&'a mut V, VacantEntry<'a, K, V>> { - match self { - Occupied(entry) => Ok(entry.into_mut()), - Vacant(entry) => Err(entry), - } - } -} - -impl<'a, K, V> OccupiedEntry<'a, K, V> { - /// Gets a reference to the value in the entry. - #[stable(feature = "rust1", since = "1.0.0")] - pub fn get(&self) -> &V { - self.elem.read().1 - } - - /// Gets a mutable reference to the value in the entry. - #[stable(feature = "rust1", since = "1.0.0")] - pub fn get_mut(&mut self) -> &mut V { - self.elem.read_mut().1 - } - - /// Converts the OccupiedEntry into a mutable reference to the value in the entry - /// with a lifetime bound to the map itself - #[stable(feature = "rust1", since = "1.0.0")] - pub fn into_mut(self) -> &'a mut V { - self.elem.into_mut_refs().1 - } - - /// Sets the value of the entry, and returns the entry's old value - #[stable(feature = "rust1", since = "1.0.0")] - pub fn insert(&mut self, mut value: V) -> V { - let old_value = self.get_mut(); - mem::swap(&mut value, old_value); - value - } - - /// Takes the value out of the entry, and returns it - #[stable(feature = "rust1", since = "1.0.0")] - pub fn remove(self) -> V { - pop_internal(self.elem).1 - } -} - -impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V> { - /// Sets the value of the entry with the VacantEntry's key, - /// and returns a mutable reference to it - #[stable(feature = "rust1", since = "1.0.0")] - pub fn insert(self, value: V) -> &'a mut V { - match self.elem { - NeqElem(bucket, ib) => { - robin_hood(bucket, ib, self.hash, self.key, value) - } - NoElem(bucket) => { - bucket.put(self.hash, self.key, value).into_mut_refs().1 - } - } - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<K, V, S, H> FromIterator<(K, V)> for HashMap<K, V, S> - where K: Eq + Hash<H>, - S: HashState<Hasher=H> + Default, - H: hash::Hasher<Output=u64> -{ - fn from_iter<T: IntoIterator<Item=(K, V)>>(iter: T) -> HashMap<K, V, S> { - let iter = iter.into_iter(); - let lower = iter.size_hint().0; - let mut map = HashMap::with_capacity_and_hash_state(lower, - Default::default()); - map.extend(iter); - map - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<K, V, S, H> Extend<(K, V)> for HashMap<K, V, S> - where K: Eq + Hash<H>, - S: HashState<Hasher=H>, - H: hash::Hasher<Output=u64> -{ - fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) { - for (k, v) in iter { - self.insert(k, v); - } - } -} - - -/// `RandomState` is the default state for `HashMap` types. -/// -/// A particular instance `RandomState` will create the same instances of -/// `Hasher`, but the hashers created by two different `RandomState` -/// instances are unlikely to produce the same result for the same values. -#[derive(Clone)] -#[unstable(feature = "std_misc", - reason = "hashing an hash maps may be altered")] -pub struct RandomState { - k0: u64, - k1: u64, -} - -#[unstable(feature = "std_misc", - reason = "hashing an hash maps may be altered")] -impl RandomState { - /// Construct a new `RandomState` that is initialized with random keys. - #[inline] - #[allow(deprecated)] - pub fn new() -> RandomState { - let mut r = rand::thread_rng(); - RandomState { k0: r.gen(), k1: r.gen() } - } -} - -#[unstable(feature = "std_misc", - reason = "hashing an hash maps may be altered")] -impl HashState for RandomState { - type Hasher = Hasher; - fn hasher(&self) -> Hasher { - Hasher { inner: SipHasher::new_with_keys(self.k0, self.k1) } - } -} - -#[unstable(feature = "std_misc", - reason = "hashing an hash maps may be altered")] -impl Default for RandomState { - #[inline] - fn default() -> RandomState { - RandomState::new() - } -} - -/// A hasher implementation which is generated from `RandomState` instances. -/// -/// This is the default hasher used in a `HashMap` to hash keys. Types do not -/// typically declare an ability to explicitly hash into this particular type, -/// but rather in a `H: hash::Writer` type parameter. -#[unstable(feature = "std_misc", - reason = "hashing an hash maps may be altered")] -pub struct Hasher { inner: SipHasher } - -impl hash::Writer for Hasher { - fn write(&mut self, data: &[u8]) { - hash::Writer::write(&mut self.inner, data) - } -} - -impl hash::Hasher for Hasher { - type Output = u64; - fn reset(&mut self) { hash::Hasher::reset(&mut self.inner) } - fn finish(&self) -> u64 { self.inner.finish() } -} - -#[cfg(test)] -mod test_map { - use prelude::v1::*; - - use super::HashMap; - use super::Entry::{Occupied, Vacant}; - use iter::{range_inclusive, range_step_inclusive, repeat}; - use cell::RefCell; - use rand::{weak_rng, Rng}; - - #[test] - fn test_create_capacity_zero() { - let mut m = HashMap::with_capacity(0); - - assert!(m.insert(1, 1).is_none()); - - assert!(m.contains_key(&1)); - assert!(!m.contains_key(&0)); - } - - #[test] - fn test_insert() { - let mut m = HashMap::new(); - assert_eq!(m.len(), 0); - assert!(m.insert(1, 2).is_none()); - assert_eq!(m.len(), 1); - assert!(m.insert(2, 4).is_none()); - assert_eq!(m.len(), 2); - assert_eq!(*m.get(&1).unwrap(), 2); - assert_eq!(*m.get(&2).unwrap(), 4); - } - - thread_local! { static DROP_VECTOR: RefCell<Vec<int>> = RefCell::new(Vec::new()) } - - #[derive(Hash, PartialEq, Eq)] - struct Dropable { - k: usize - } - - impl Dropable { - fn new(k: usize) -> Dropable { - DROP_VECTOR.with(|slot| { - slot.borrow_mut()[k] += 1; - }); - - Dropable { k: k } - } - } - - impl Drop for Dropable { - fn drop(&mut self) { - DROP_VECTOR.with(|slot| { - slot.borrow_mut()[self.k] -= 1; - }); - } - } - - impl Clone for Dropable { - fn clone(&self) -> Dropable { - Dropable::new(self.k) - } - } - - #[test] - fn test_drops() { - DROP_VECTOR.with(|slot| { - *slot.borrow_mut() = repeat(0).take(200).collect(); - }); - - { - let mut m = HashMap::new(); - - DROP_VECTOR.with(|v| { - for i in 0..200 { - assert_eq!(v.borrow()[i], 0); - } - }); - - for i in 0..100 { - let d1 = Dropable::new(i); - let d2 = Dropable::new(i+100); - m.insert(d1, d2); - } - - DROP_VECTOR.with(|v| { - for i in 0..200 { - assert_eq!(v.borrow()[i], 1); - } - }); - - for i in 0..50 { - let k = Dropable::new(i); - let v = m.remove(&k); - - assert!(v.is_some()); - - DROP_VECTOR.with(|v| { - assert_eq!(v.borrow()[i], 1); - assert_eq!(v.borrow()[i+100], 1); - }); - } - - DROP_VECTOR.with(|v| { - for i in 0..50 { - assert_eq!(v.borrow()[i], 0); - assert_eq!(v.borrow()[i+100], 0); - } - - for i in 50..100 { - assert_eq!(v.borrow()[i], 1); - assert_eq!(v.borrow()[i+100], 1); - } - }); - } - - DROP_VECTOR.with(|v| { - for i in 0..200 { - assert_eq!(v.borrow()[i], 0); - } - }); - } - - #[test] - fn test_move_iter_drops() { - DROP_VECTOR.with(|v| { - *v.borrow_mut() = repeat(0).take(200).collect(); - }); - - let hm = { - let mut hm = HashMap::new(); - - DROP_VECTOR.with(|v| { - for i in 0..200 { - assert_eq!(v.borrow()[i], 0); - } - }); - - for i in 0..100 { - let d1 = Dropable::new(i); - let d2 = Dropable::new(i+100); - hm.insert(d1, d2); - } - - DROP_VECTOR.with(|v| { - for i in 0..200 { - assert_eq!(v.borrow()[i], 1); - } - }); - - hm - }; - - // By the way, ensure that cloning doesn't screw up the dropping. - drop(hm.clone()); - - { - let mut half = hm.into_iter().take(50); - - DROP_VECTOR.with(|v| { - for i in 0..200 { - assert_eq!(v.borrow()[i], 1); - } - }); - - for _ in half.by_ref() {} - - DROP_VECTOR.with(|v| { - let nk = (0..100).filter(|&i| { - v.borrow()[i] == 1 - }).count(); - - let nv = (0..100).filter(|&i| { - v.borrow()[i+100] == 1 - }).count(); - - assert_eq!(nk, 50); - assert_eq!(nv, 50); - }); - }; - - DROP_VECTOR.with(|v| { - for i in 0..200 { - assert_eq!(v.borrow()[i], 0); - } - }); - } - - #[test] - fn test_empty_pop() { - let mut m: HashMap<int, bool> = HashMap::new(); - assert_eq!(m.remove(&0), None); - } - - #[test] - fn test_lots_of_insertions() { - let mut m = HashMap::new(); - - // Try this a few times to make sure we never screw up the hashmap's - // internal state. - for _ in 0..10 { - assert!(m.is_empty()); - - for i in range_inclusive(1, 1000) { - assert!(m.insert(i, i).is_none()); - - for j in range_inclusive(1, i) { - let r = m.get(&j); - assert_eq!(r, Some(&j)); - } - - for j in range_inclusive(i+1, 1000) { - let r = m.get(&j); - assert_eq!(r, None); - } - } - - for i in range_inclusive(1001, 2000) { - assert!(!m.contains_key(&i)); - } - - // remove forwards - for i in range_inclusive(1, 1000) { - assert!(m.remove(&i).is_some()); - - for j in range_inclusive(1, i) { - assert!(!m.contains_key(&j)); - } - - for j in range_inclusive(i+1, 1000) { - assert!(m.contains_key(&j)); - } - } - - for i in range_inclusive(1, 1000) { - assert!(!m.contains_key(&i)); - } - - for i in range_inclusive(1, 1000) { - assert!(m.insert(i, i).is_none()); - } - - // remove backwards - for i in range_step_inclusive(1000, 1, -1) { - assert!(m.remove(&i).is_some()); - - for j in range_inclusive(i, 1000) { - assert!(!m.contains_key(&j)); - } - - for j in range_inclusive(1, i-1) { - assert!(m.contains_key(&j)); - } - } - } - } - - #[test] - fn test_find_mut() { - let mut m = HashMap::new(); - assert!(m.insert(1, 12).is_none()); - assert!(m.insert(2, 8).is_none()); - assert!(m.insert(5, 14).is_none()); - let new = 100; - match m.get_mut(&5) { - None => panic!(), Some(x) => *x = new - } - assert_eq!(m.get(&5), Some(&new)); - } - - #[test] - fn test_insert_overwrite() { - let mut m = HashMap::new(); - assert!(m.insert(1, 2).is_none()); - assert_eq!(*m.get(&1).unwrap(), 2); - assert!(!m.insert(1, 3).is_none()); - assert_eq!(*m.get(&1).unwrap(), 3); - } - - #[test] - fn test_insert_conflicts() { - let mut m = HashMap::with_capacity(4); - assert!(m.insert(1, 2).is_none()); - assert!(m.insert(5, 3).is_none()); - assert!(m.insert(9, 4).is_none()); - assert_eq!(*m.get(&9).unwrap(), 4); - assert_eq!(*m.get(&5).unwrap(), 3); - assert_eq!(*m.get(&1).unwrap(), 2); - } - - #[test] - fn test_conflict_remove() { - let mut m = HashMap::with_capacity(4); - assert!(m.insert(1, 2).is_none()); - assert_eq!(*m.get(&1).unwrap(), 2); - assert!(m.insert(5, 3).is_none()); - assert_eq!(*m.get(&1).unwrap(), 2); - assert_eq!(*m.get(&5).unwrap(), 3); - assert!(m.insert(9, 4).is_none()); - assert_eq!(*m.get(&1).unwrap(), 2); - assert_eq!(*m.get(&5).unwrap(), 3); - assert_eq!(*m.get(&9).unwrap(), 4); - assert!(m.remove(&1).is_some()); - assert_eq!(*m.get(&9).unwrap(), 4); - assert_eq!(*m.get(&5).unwrap(), 3); - } - - #[test] - fn test_is_empty() { - let mut m = HashMap::with_capacity(4); - assert!(m.insert(1, 2).is_none()); - assert!(!m.is_empty()); - assert!(m.remove(&1).is_some()); - assert!(m.is_empty()); - } - - #[test] - fn test_pop() { - let mut m = HashMap::new(); - m.insert(1, 2); - assert_eq!(m.remove(&1), Some(2)); - assert_eq!(m.remove(&1), None); - } - - #[test] - fn test_iterate() { - let mut m = HashMap::with_capacity(4); - for i in 0..32 { - assert!(m.insert(i, i*2).is_none()); - } - assert_eq!(m.len(), 32); - - let mut observed: u32 = 0; - - for (k, v) in &m { - assert_eq!(*v, *k * 2); - observed |= 1 << *k; - } - assert_eq!(observed, 0xFFFF_FFFF); - } - - #[test] - fn test_keys() { - let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; - let map: HashMap<_, _> = vec.into_iter().collect(); - let keys: Vec<_> = map.keys().cloned().collect(); - assert_eq!(keys.len(), 3); - assert!(keys.contains(&1)); - assert!(keys.contains(&2)); - assert!(keys.contains(&3)); - } - - #[test] - fn test_values() { - let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; - let map: HashMap<_, _> = vec.into_iter().collect(); - let values: Vec<_> = map.values().cloned().collect(); - assert_eq!(values.len(), 3); - assert!(values.contains(&'a')); - assert!(values.contains(&'b')); - assert!(values.contains(&'c')); - } - - #[test] - fn test_find() { - let mut m = HashMap::new(); - assert!(m.get(&1).is_none()); - m.insert(1, 2); - match m.get(&1) { - None => panic!(), - Some(v) => assert_eq!(*v, 2) - } - } - - #[test] - fn test_eq() { - let mut m1 = HashMap::new(); - m1.insert(1, 2); - m1.insert(2, 3); - m1.insert(3, 4); - - let mut m2 = HashMap::new(); - m2.insert(1, 2); - m2.insert(2, 3); - - assert!(m1 != m2); - - m2.insert(3, 4); - - assert_eq!(m1, m2); - } - - #[test] - fn test_show() { - let mut map = HashMap::new(); - let empty: HashMap<i32, i32> = HashMap::new(); - - map.insert(1, 2); - map.insert(3, 4); - - let map_str = format!("{:?}", map); - - assert!(map_str == "HashMap {1: 2, 3: 4}" || - map_str == "HashMap {3: 4, 1: 2}"); - assert_eq!(format!("{:?}", empty), "HashMap {}"); - } - - #[test] - fn test_expand() { - let mut m = HashMap::new(); - - assert_eq!(m.len(), 0); - assert!(m.is_empty()); - - let mut i = 0; - let old_cap = m.table.capacity(); - while old_cap == m.table.capacity() { - m.insert(i, i); - i += 1; - } - - assert_eq!(m.len(), i); - assert!(!m.is_empty()); - } - - #[test] - fn test_behavior_resize_policy() { - let mut m = HashMap::new(); - - assert_eq!(m.len(), 0); - assert_eq!(m.table.capacity(), 0); - assert!(m.is_empty()); - - m.insert(0, 0); - m.remove(&0); - assert!(m.is_empty()); - let initial_cap = m.table.capacity(); - m.reserve(initial_cap); - let cap = m.table.capacity(); - - assert_eq!(cap, initial_cap * 2); - - let mut i = 0; - for _ in 0..cap * 3 / 4 { - m.insert(i, i); - i += 1; - } - // three quarters full - - assert_eq!(m.len(), i); - assert_eq!(m.table.capacity(), cap); - - for _ in 0..cap / 4 { - m.insert(i, i); - i += 1; - } - // half full - - let new_cap = m.table.capacity(); - assert_eq!(new_cap, cap * 2); - - for _ in 0..cap / 2 - 1 { - i -= 1; - m.remove(&i); - assert_eq!(m.table.capacity(), new_cap); - } - // A little more than one quarter full. - m.shrink_to_fit(); - assert_eq!(m.table.capacity(), cap); - // again, a little more than half full - for _ in 0..cap / 2 - 1 { - i -= 1; - m.remove(&i); - } - m.shrink_to_fit(); - - assert_eq!(m.len(), i); - assert!(!m.is_empty()); - assert_eq!(m.table.capacity(), initial_cap); - } - - #[test] - fn test_reserve_shrink_to_fit() { - let mut m = HashMap::new(); - m.insert(0, 0); - m.remove(&0); - assert!(m.capacity() >= m.len()); - for i in 0..128 { - m.insert(i, i); - } - m.reserve(256); - - let usable_cap = m.capacity(); - for i in 128..(128 + 256) { - m.insert(i, i); - assert_eq!(m.capacity(), usable_cap); - } - - for i in 100..(128 + 256) { - assert_eq!(m.remove(&i), Some(i)); - } - m.shrink_to_fit(); - - assert_eq!(m.len(), 100); - assert!(!m.is_empty()); - assert!(m.capacity() >= m.len()); - - for i in 0..100 { - assert_eq!(m.remove(&i), Some(i)); - } - m.shrink_to_fit(); - m.insert(0, 0); - - assert_eq!(m.len(), 1); - assert!(m.capacity() >= m.len()); - assert_eq!(m.remove(&0), Some(0)); - } - - #[test] - fn test_from_iter() { - let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; - - let map: HashMap<_, _> = xs.iter().cloned().collect(); - - for &(k, v) in &xs { - assert_eq!(map.get(&k), Some(&v)); - } - } - - #[test] - fn test_size_hint() { - let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; - - let map: HashMap<_, _> = xs.iter().cloned().collect(); - - let mut iter = map.iter(); - - for _ in iter.by_ref().take(3) {} - - assert_eq!(iter.size_hint(), (3, Some(3))); - } - - #[test] - fn test_iter_len() { - let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; - - let map: HashMap<_, _> = xs.iter().cloned().collect(); - - let mut iter = map.iter(); - - for _ in iter.by_ref().take(3) {} - - assert_eq!(iter.len(), 3); - } - - #[test] - fn test_mut_size_hint() { - let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; - - let mut map: HashMap<_, _> = xs.iter().cloned().collect(); - - let mut iter = map.iter_mut(); - - for _ in iter.by_ref().take(3) {} - - assert_eq!(iter.size_hint(), (3, Some(3))); - } - - #[test] - fn test_iter_mut_len() { - let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; - - let mut map: HashMap<_, _> = xs.iter().cloned().collect(); - - let mut iter = map.iter_mut(); - - for _ in iter.by_ref().take(3) {} - - assert_eq!(iter.len(), 3); - } - - #[test] - fn test_index() { - let mut map = HashMap::new(); - - map.insert(1, 2); - map.insert(2, 1); - map.insert(3, 4); - - assert_eq!(map[2], 1); - } - - #[test] - #[should_fail] - fn test_index_nonexistent() { - let mut map = HashMap::new(); - - map.insert(1, 2); - map.insert(2, 1); - map.insert(3, 4); - - map[4]; - } - - #[test] - fn test_entry(){ - let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)]; - - let mut map: HashMap<_, _> = xs.iter().cloned().collect(); - - // Existing key (insert) - match map.entry(1) { - Vacant(_) => unreachable!(), - Occupied(mut view) => { - assert_eq!(view.get(), &10); - assert_eq!(view.insert(100), 10); - } - } - assert_eq!(map.get(&1).unwrap(), &100); - assert_eq!(map.len(), 6); - - - // Existing key (update) - match map.entry(2) { - Vacant(_) => unreachable!(), - Occupied(mut view) => { - let v = view.get_mut(); - let new_v = (*v) * 10; - *v = new_v; - } - } - assert_eq!(map.get(&2).unwrap(), &200); - assert_eq!(map.len(), 6); - - // Existing key (take) - match map.entry(3) { - Vacant(_) => unreachable!(), - Occupied(view) => { - assert_eq!(view.remove(), 30); - } - } - assert_eq!(map.get(&3), None); - assert_eq!(map.len(), 5); - - - // Inexistent key (insert) - match map.entry(10) { - Occupied(_) => unreachable!(), - Vacant(view) => { - assert_eq!(*view.insert(1000), 1000); - } - } - assert_eq!(map.get(&10).unwrap(), &1000); - assert_eq!(map.len(), 6); - } - - #[test] - fn test_entry_take_doesnt_corrupt() { - // Test for #19292 - fn check(m: &HashMap<isize, ()>) { - for k in m.keys() { - assert!(m.contains_key(k), - "{} is in keys() but not in the map?", k); - } - } - - let mut m = HashMap::new(); - let mut rng = weak_rng(); - - // Populate the map with some items. - for _ in 0..50 { - let x = rng.gen_range(-10, 10); - m.insert(x, ()); - } - - for i in 0..1000 { - let x = rng.gen_range(-10, 10); - match m.entry(x) { - Vacant(_) => {}, - Occupied(e) => { - println!("{}: remove {}", i, x); - e.remove(); - }, - } - - check(&m); - } - } -} diff --git a/src/libstd/collections/hash/mod.rs b/src/libstd/collections/hash/mod.rs index 39c1458b720..47e300af269 100644 --- a/src/libstd/collections/hash/mod.rs +++ b/src/libstd/collections/hash/mod.rs @@ -12,14 +12,6 @@ mod bench; mod table; -#[cfg(stage0)] -#[path = "map_stage0.rs"] pub mod map; -#[cfg(not(stage0))] -pub mod map; -#[cfg(stage0)] -#[path = "set_stage0.rs"] -pub mod set; -#[cfg(not(stage0))] pub mod set; pub mod state; diff --git a/src/libstd/collections/hash/set_stage0.rs b/src/libstd/collections/hash/set_stage0.rs deleted file mode 100644 index 68c9e02d8ad..00000000000 --- a/src/libstd/collections/hash/set_stage0.rs +++ /dev/null @@ -1,1252 +0,0 @@ -// Copyright 2014 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or -// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license -// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. -// -// ignore-lexer-test FIXME #15883 - -use borrow::Borrow; -use clone::Clone; -use cmp::{Eq, PartialEq}; -use core::marker::Sized; -use default::Default; -use fmt::Debug; -use fmt; -use hash::{self, Hash}; -use iter::{ - Iterator, IntoIterator, ExactSizeIterator, IteratorExt, FromIterator, Map, Chain, Extend, -}; -use ops::{BitOr, BitAnd, BitXor, Sub}; -use option::Option::{Some, None, self}; - -use super::map::{self, HashMap, Keys, INITIAL_CAPACITY, RandomState, Hasher}; -use super::state::HashState; - -// Future Optimization (FIXME!) -// ============================= -// -// Iteration over zero sized values is a noop. There is no need -// for `bucket.val` in the case of HashSet. I suppose we would need HKT -// to get rid of it properly. - -/// An implementation of a hash set using the underlying representation of a -/// HashMap where the value is (). As with the `HashMap` type, a `HashSet` -/// requires that the elements implement the `Eq` and `Hash` traits. -/// -/// # Example -/// -/// ``` -/// use std::collections::HashSet; -/// // Type inference lets us omit an explicit type signature (which -/// // would be `HashSet<&str>` in this example). -/// let mut books = HashSet::new(); -/// -/// // Add some books. -/// books.insert("A Dance With Dragons"); -/// books.insert("To Kill a Mockingbird"); -/// books.insert("The Odyssey"); -/// books.insert("The Great Gatsby"); -/// -/// // Check for a specific one. -/// if !books.contains(&("The Winds of Winter")) { -/// println!("We have {} books, but The Winds of Winter ain't one.", -/// books.len()); -/// } -/// -/// // Remove a book. -/// books.remove(&"The Odyssey"); -/// -/// // Iterate over everything. -/// for book in books.iter() { -/// println!("{}", *book); -/// } -/// ``` -/// -/// The easiest way to use `HashSet` with a custom type is to derive -/// `Eq` and `Hash`. We must also derive `PartialEq`, this will in the -/// future be implied by `Eq`. -/// -/// ``` -/// use std::collections::HashSet; -/// #[derive(Hash, Eq, PartialEq, Debug)] -/// struct Viking<'a> { -/// name: &'a str, -/// power: usize, -/// } -/// -/// let mut vikings = HashSet::new(); -/// -/// vikings.insert(Viking { name: "Einar", power: 9 }); -/// vikings.insert(Viking { name: "Einar", power: 9 }); -/// vikings.insert(Viking { name: "Olaf", power: 4 }); -/// vikings.insert(Viking { name: "Harald", power: 8 }); -/// -/// // Use derived implementation to print the vikings. -/// for x in vikings.iter() { -/// println!("{:?}", x); -/// } -/// ``` -#[derive(Clone)] -#[stable(feature = "rust1", since = "1.0.0")] -pub struct HashSet<T, S = RandomState> { - map: HashMap<T, (), S> -} - -impl<T: Hash<Hasher> + Eq> HashSet<T, RandomState> { - /// Create an empty HashSet. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// let mut set: HashSet<int> = HashSet::new(); - /// ``` - #[inline] - #[stable(feature = "rust1", since = "1.0.0")] - pub fn new() -> HashSet<T, RandomState> { - HashSet::with_capacity(INITIAL_CAPACITY) - } - - /// Create an empty HashSet with space for at least `n` elements in - /// the hash table. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// let mut set: HashSet<int> = HashSet::with_capacity(10); - /// ``` - #[inline] - #[stable(feature = "rust1", since = "1.0.0")] - pub fn with_capacity(capacity: usize) -> HashSet<T, RandomState> { - HashSet { map: HashMap::with_capacity(capacity) } - } -} - -impl<T, S, H> HashSet<T, S> - where T: Eq + Hash<H>, - S: HashState<Hasher=H>, - H: hash::Hasher<Output=u64> -{ - /// Creates a new empty hash set which will use the given hasher to hash - /// keys. - /// - /// The hash set is also created with the default initial capacity. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// use std::collections::hash_map::RandomState; - /// - /// let s = RandomState::new(); - /// let mut set = HashSet::with_hash_state(s); - /// set.insert(2); - /// ``` - #[inline] - #[unstable(feature = "std_misc", reason = "hasher stuff is unclear")] - pub fn with_hash_state(hash_state: S) -> HashSet<T, S> { - HashSet::with_capacity_and_hash_state(INITIAL_CAPACITY, hash_state) - } - - /// Create an empty HashSet with space for at least `capacity` - /// elements in the hash table, using `hasher` to hash the keys. - /// - /// Warning: `hasher` is normally randomly generated, and - /// is designed to allow `HashSet`s to be resistant to attacks that - /// cause many collisions and very poor performance. Setting it - /// manually using this function can expose a DoS attack vector. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// use std::collections::hash_map::RandomState; - /// - /// let s = RandomState::new(); - /// let mut set = HashSet::with_capacity_and_hash_state(10, s); - /// set.insert(1); - /// ``` - #[inline] - #[unstable(feature = "std_misc", reason = "hasher stuff is unclear")] - pub fn with_capacity_and_hash_state(capacity: usize, hash_state: S) - -> HashSet<T, S> { - HashSet { - map: HashMap::with_capacity_and_hash_state(capacity, hash_state), - } - } - - /// Returns the number of elements the set can hold without reallocating. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// let set: HashSet<int> = HashSet::with_capacity(100); - /// assert!(set.capacity() >= 100); - /// ``` - #[inline] - #[stable(feature = "rust1", since = "1.0.0")] - pub fn capacity(&self) -> usize { - self.map.capacity() - } - - /// Reserves capacity for at least `additional` more elements to be inserted - /// in the `HashSet`. The collection may reserve more space to avoid - /// frequent reallocations. - /// - /// # Panics - /// - /// Panics if the new allocation size overflows `usize`. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// let mut set: HashSet<int> = HashSet::new(); - /// set.reserve(10); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn reserve(&mut self, additional: usize) { - self.map.reserve(additional) - } - - /// Shrinks the capacity of the set as much as possible. It will drop - /// down as much as possible while maintaining the internal rules - /// and possibly leaving some space in accordance with the resize policy. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let mut set: HashSet<int> = HashSet::with_capacity(100); - /// set.insert(1); - /// set.insert(2); - /// assert!(set.capacity() >= 100); - /// set.shrink_to_fit(); - /// assert!(set.capacity() >= 2); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn shrink_to_fit(&mut self) { - self.map.shrink_to_fit() - } - - /// An iterator visiting all elements in arbitrary order. - /// Iterator element type is &'a T. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// let mut set = HashSet::new(); - /// set.insert("a"); - /// set.insert("b"); - /// - /// // Will print in an arbitrary order. - /// for x in set.iter() { - /// println!("{}", x); - /// } - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn iter(&self) -> Iter<T> { - Iter { iter: self.map.keys() } - } - - /// Creates a consuming iterator, that is, one that moves each value out - /// of the set in arbitrary order. The set cannot be used after calling - /// this. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// let mut set = HashSet::new(); - /// set.insert("a".to_string()); - /// set.insert("b".to_string()); - /// - /// // Not possible to collect to a Vec<String> with a regular `.iter()`. - /// let v: Vec<String> = set.into_iter().collect(); - /// - /// // Will print in an arbitrary order. - /// for x in v.iter() { - /// println!("{}", x); - /// } - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn into_iter(self) -> IntoIter<T> { - fn first<A, B>((a, _): (A, B)) -> A { a } - let first: fn((T, ())) -> T = first; - - IntoIter { iter: self.map.into_iter().map(first) } - } - - /// Visit the values representing the difference. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// let a: HashSet<int> = [1, 2, 3].iter().map(|&x| x).collect(); - /// let b: HashSet<int> = [4, 2, 3, 4].iter().map(|&x| x).collect(); - /// - /// // Can be seen as `a - b`. - /// for x in a.difference(&b) { - /// println!("{}", x); // Print 1 - /// } - /// - /// let diff: HashSet<int> = a.difference(&b).map(|&x| x).collect(); - /// assert_eq!(diff, [1].iter().map(|&x| x).collect()); - /// - /// // Note that difference is not symmetric, - /// // and `b - a` means something else: - /// let diff: HashSet<int> = b.difference(&a).map(|&x| x).collect(); - /// assert_eq!(diff, [4].iter().map(|&x| x).collect()); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn difference<'a>(&'a self, other: &'a HashSet<T, S>) -> Difference<'a, T, S> { - Difference { - iter: self.iter(), - other: other, - } - } - - /// Visit the values representing the symmetric difference. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// let a: HashSet<int> = [1, 2, 3].iter().map(|&x| x).collect(); - /// let b: HashSet<int> = [4, 2, 3, 4].iter().map(|&x| x).collect(); - /// - /// // Print 1, 4 in arbitrary order. - /// for x in a.symmetric_difference(&b) { - /// println!("{}", x); - /// } - /// - /// let diff1: HashSet<int> = a.symmetric_difference(&b).map(|&x| x).collect(); - /// let diff2: HashSet<int> = b.symmetric_difference(&a).map(|&x| x).collect(); - /// - /// assert_eq!(diff1, diff2); - /// assert_eq!(diff1, [1, 4].iter().map(|&x| x).collect()); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn symmetric_difference<'a>(&'a self, other: &'a HashSet<T, S>) - -> SymmetricDifference<'a, T, S> { - SymmetricDifference { iter: self.difference(other).chain(other.difference(self)) } - } - - /// Visit the values representing the intersection. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// let a: HashSet<int> = [1, 2, 3].iter().map(|&x| x).collect(); - /// let b: HashSet<int> = [4, 2, 3, 4].iter().map(|&x| x).collect(); - /// - /// // Print 2, 3 in arbitrary order. - /// for x in a.intersection(&b) { - /// println!("{}", x); - /// } - /// - /// let diff: HashSet<int> = a.intersection(&b).map(|&x| x).collect(); - /// assert_eq!(diff, [2, 3].iter().map(|&x| x).collect()); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn intersection<'a>(&'a self, other: &'a HashSet<T, S>) -> Intersection<'a, T, S> { - Intersection { - iter: self.iter(), - other: other, - } - } - - /// Visit the values representing the union. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// let a: HashSet<int> = [1, 2, 3].iter().map(|&x| x).collect(); - /// let b: HashSet<int> = [4, 2, 3, 4].iter().map(|&x| x).collect(); - /// - /// // Print 1, 2, 3, 4 in arbitrary order. - /// for x in a.union(&b) { - /// println!("{}", x); - /// } - /// - /// let diff: HashSet<int> = a.union(&b).map(|&x| x).collect(); - /// assert_eq!(diff, [1, 2, 3, 4].iter().map(|&x| x).collect()); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn union<'a>(&'a self, other: &'a HashSet<T, S>) -> Union<'a, T, S> { - Union { iter: self.iter().chain(other.difference(self)) } - } - - /// Return the number of elements in the set - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let mut v = HashSet::new(); - /// assert_eq!(v.len(), 0); - /// v.insert(1); - /// assert_eq!(v.len(), 1); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn len(&self) -> usize { self.map.len() } - - /// Returns true if the set contains no elements - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let mut v = HashSet::new(); - /// assert!(v.is_empty()); - /// v.insert(1); - /// assert!(!v.is_empty()); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn is_empty(&self) -> bool { self.map.len() == 0 } - - /// Clears the set, returning all elements in an iterator. - #[inline] - #[unstable(feature = "std_misc", - reason = "matches collection reform specification, waiting for dust to settle")] - pub fn drain(&mut self) -> Drain<T> { - fn first<A, B>((a, _): (A, B)) -> A { a } - let first: fn((T, ())) -> T = first; // coerce to fn pointer - - Drain { iter: self.map.drain().map(first) } - } - - /// Clears the set, removing all values. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let mut v = HashSet::new(); - /// v.insert(1); - /// v.clear(); - /// assert!(v.is_empty()); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn clear(&mut self) { self.map.clear() } - - /// Returns `true` if the set contains a value. - /// - /// The value may be any borrowed form of the set's value type, but - /// `Hash` and `Eq` on the borrowed form *must* match those for - /// the value type. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let set: HashSet<_> = [1, 2, 3].iter().cloned().collect(); - /// assert_eq!(set.contains(&1), true); - /// assert_eq!(set.contains(&4), false); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool - where T: Borrow<Q>, Q: Hash<H> + Eq - { - self.map.contains_key(value) - } - - /// Returns `true` if the set has no elements in common with `other`. - /// This is equivalent to checking for an empty intersection. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect(); - /// let mut b = HashSet::new(); - /// - /// assert_eq!(a.is_disjoint(&b), true); - /// b.insert(4); - /// assert_eq!(a.is_disjoint(&b), true); - /// b.insert(1); - /// assert_eq!(a.is_disjoint(&b), false); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn is_disjoint(&self, other: &HashSet<T, S>) -> bool { - self.iter().all(|v| !other.contains(v)) - } - - /// Returns `true` if the set is a subset of another. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let sup: HashSet<_> = [1, 2, 3].iter().cloned().collect(); - /// let mut set = HashSet::new(); - /// - /// assert_eq!(set.is_subset(&sup), true); - /// set.insert(2); - /// assert_eq!(set.is_subset(&sup), true); - /// set.insert(4); - /// assert_eq!(set.is_subset(&sup), false); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn is_subset(&self, other: &HashSet<T, S>) -> bool { - self.iter().all(|v| other.contains(v)) - } - - /// Returns `true` if the set is a superset of another. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let sub: HashSet<_> = [1, 2].iter().cloned().collect(); - /// let mut set = HashSet::new(); - /// - /// assert_eq!(set.is_superset(&sub), false); - /// - /// set.insert(0); - /// set.insert(1); - /// assert_eq!(set.is_superset(&sub), false); - /// - /// set.insert(2); - /// assert_eq!(set.is_superset(&sub), true); - /// ``` - #[inline] - #[stable(feature = "rust1", since = "1.0.0")] - pub fn is_superset(&self, other: &HashSet<T, S>) -> bool { - other.is_subset(self) - } - - /// Adds a value to the set. Returns `true` if the value was not already - /// present in the set. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let mut set = HashSet::new(); - /// - /// assert_eq!(set.insert(2), true); - /// assert_eq!(set.insert(2), false); - /// assert_eq!(set.len(), 1); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()).is_none() } - - /// Removes a value from the set. Returns `true` if the value was - /// present in the set. - /// - /// The value may be any borrowed form of the set's value type, but - /// `Hash` and `Eq` on the borrowed form *must* match those for - /// the value type. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let mut set = HashSet::new(); - /// - /// set.insert(2); - /// assert_eq!(set.remove(&2), true); - /// assert_eq!(set.remove(&2), false); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool - where T: Borrow<Q>, Q: Hash<H> + Eq - { - self.map.remove(value).is_some() - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<T, S, H> PartialEq for HashSet<T, S> - where T: Eq + Hash<H>, - S: HashState<Hasher=H>, - H: hash::Hasher<Output=u64> -{ - fn eq(&self, other: &HashSet<T, S>) -> bool { - if self.len() != other.len() { return false; } - - self.iter().all(|key| other.contains(key)) - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<T, S, H> Eq for HashSet<T, S> - where T: Eq + Hash<H>, - S: HashState<Hasher=H>, - H: hash::Hasher<Output=u64> -{} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<T, S, H> fmt::Debug for HashSet<T, S> - where T: Eq + Hash<H> + fmt::Debug, - S: HashState<Hasher=H>, - H: hash::Hasher<Output=u64> -{ - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - try!(write!(f, "HashSet {{")); - - for (i, x) in self.iter().enumerate() { - if i != 0 { try!(write!(f, ", ")); } - try!(write!(f, "{:?}", *x)); - } - - write!(f, "}}") - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<T, S, H> FromIterator<T> for HashSet<T, S> - where T: Eq + Hash<H>, - S: HashState<Hasher=H> + Default, - H: hash::Hasher<Output=u64> -{ - fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> HashSet<T, S> { - let iter = iter.into_iter(); - let lower = iter.size_hint().0; - let mut set = HashSet::with_capacity_and_hash_state(lower, Default::default()); - set.extend(iter); - set - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<T, S, H> Extend<T> for HashSet<T, S> - where T: Eq + Hash<H>, - S: HashState<Hasher=H>, - H: hash::Hasher<Output=u64> -{ - fn extend<I: IntoIterator<Item=T>>(&mut self, iter: I) { - for k in iter { - self.insert(k); - } - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<T, S, H> Default for HashSet<T, S> - where T: Eq + Hash<H>, - S: HashState<Hasher=H> + Default, - H: hash::Hasher<Output=u64> -{ - #[stable(feature = "rust1", since = "1.0.0")] - fn default() -> HashSet<T, S> { - HashSet::with_hash_state(Default::default()) - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, 'b, T, S, H> BitOr<&'b HashSet<T, S>> for &'a HashSet<T, S> - where T: Eq + Hash<H> + Clone, - S: HashState<Hasher=H> + Default, - H: hash::Hasher<Output=u64> -{ - type Output = HashSet<T, S>; - - /// Returns the union of `self` and `rhs` as a new `HashSet<T, S>`. - /// - /// # Examples - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect(); - /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect(); - /// - /// let set = &a | &b; - /// - /// let mut i = 0; - /// let expected = [1, 2, 3, 4, 5]; - /// for x in set.iter() { - /// assert!(expected.contains(x)); - /// i += 1; - /// } - /// assert_eq!(i, expected.len()); - /// ``` - fn bitor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> { - self.union(rhs).cloned().collect() - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, 'b, T, S, H> BitAnd<&'b HashSet<T, S>> for &'a HashSet<T, S> - where T: Eq + Hash<H> + Clone, - S: HashState<Hasher=H> + Default, - H: hash::Hasher<Output=u64> -{ - type Output = HashSet<T, S>; - - /// Returns the intersection of `self` and `rhs` as a new `HashSet<T, S>`. - /// - /// # Examples - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect(); - /// let b: HashSet<_> = vec![2, 3, 4].into_iter().collect(); - /// - /// let set = &a & &b; - /// - /// let mut i = 0; - /// let expected = [2, 3]; - /// for x in set.iter() { - /// assert!(expected.contains(x)); - /// i += 1; - /// } - /// assert_eq!(i, expected.len()); - /// ``` - fn bitand(self, rhs: &HashSet<T, S>) -> HashSet<T, S> { - self.intersection(rhs).cloned().collect() - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, 'b, T, S, H> BitXor<&'b HashSet<T, S>> for &'a HashSet<T, S> - where T: Eq + Hash<H> + Clone, - S: HashState<Hasher=H> + Default, - H: hash::Hasher<Output=u64> -{ - type Output = HashSet<T, S>; - - /// Returns the symmetric difference of `self` and `rhs` as a new `HashSet<T, S>`. - /// - /// # Examples - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect(); - /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect(); - /// - /// let set = &a ^ &b; - /// - /// let mut i = 0; - /// let expected = [1, 2, 4, 5]; - /// for x in set.iter() { - /// assert!(expected.contains(x)); - /// i += 1; - /// } - /// assert_eq!(i, expected.len()); - /// ``` - fn bitxor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> { - self.symmetric_difference(rhs).cloned().collect() - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, 'b, T, S, H> Sub<&'b HashSet<T, S>> for &'a HashSet<T, S> - where T: Eq + Hash<H> + Clone, - S: HashState<Hasher=H> + Default, - H: hash::Hasher<Output=u64> -{ - type Output = HashSet<T, S>; - - /// Returns the difference of `self` and `rhs` as a new `HashSet<T, S>`. - /// - /// # Examples - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect(); - /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect(); - /// - /// let set = &a - &b; - /// - /// let mut i = 0; - /// let expected = [1, 2]; - /// for x in set.iter() { - /// assert!(expected.contains(x)); - /// i += 1; - /// } - /// assert_eq!(i, expected.len()); - /// ``` - fn sub(self, rhs: &HashSet<T, S>) -> HashSet<T, S> { - self.difference(rhs).cloned().collect() - } -} - -/// HashSet iterator -#[stable(feature = "rust1", since = "1.0.0")] -pub struct Iter<'a, K: 'a> { - iter: Keys<'a, K, ()> -} - -/// HashSet move iterator -#[stable(feature = "rust1", since = "1.0.0")] -pub struct IntoIter<K> { - iter: Map<map::IntoIter<K, ()>, fn((K, ())) -> K> -} - -/// HashSet drain iterator -#[stable(feature = "rust1", since = "1.0.0")] -pub struct Drain<'a, K: 'a> { - iter: Map<map::Drain<'a, K, ()>, fn((K, ())) -> K>, -} - -/// Intersection iterator -#[stable(feature = "rust1", since = "1.0.0")] -pub struct Intersection<'a, T: 'a, S: 'a> { - // iterator of the first set - iter: Iter<'a, T>, - // the second set - other: &'a HashSet<T, S>, -} - -/// Difference iterator -#[stable(feature = "rust1", since = "1.0.0")] -pub struct Difference<'a, T: 'a, S: 'a> { - // iterator of the first set - iter: Iter<'a, T>, - // the second set - other: &'a HashSet<T, S>, -} - -/// Symmetric difference iterator. -#[stable(feature = "rust1", since = "1.0.0")] -pub struct SymmetricDifference<'a, T: 'a, S: 'a> { - iter: Chain<Difference<'a, T, S>, Difference<'a, T, S>> -} - -/// Set union iterator. -#[stable(feature = "rust1", since = "1.0.0")] -pub struct Union<'a, T: 'a, S: 'a> { - iter: Chain<Iter<'a, T>, Difference<'a, T, S>> -} - -impl<'a, T, S, H> IntoIterator for &'a HashSet<T, S> - where T: Eq + Hash<H>, - S: HashState<Hasher=H>, - H: hash::Hasher<Output=u64> -{ - type Item = &'a T; - type IntoIter = Iter<'a, T>; - - fn into_iter(self) -> Iter<'a, T> { - self.iter() - } -} - -impl<T, S, H> IntoIterator for HashSet<T, S> - where T: Eq + Hash<H>, - S: HashState<Hasher=H>, - H: hash::Hasher<Output=u64> -{ - type Item = T; - type IntoIter = IntoIter<T>; - - fn into_iter(self) -> IntoIter<T> { - self.into_iter() - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K> Iterator for Iter<'a, K> { - type Item = &'a K; - - fn next(&mut self) -> Option<&'a K> { self.iter.next() } - fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } -} -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K> ExactSizeIterator for Iter<'a, K> { - fn len(&self) -> usize { self.iter.len() } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<K> Iterator for IntoIter<K> { - type Item = K; - - fn next(&mut self) -> Option<K> { self.iter.next() } - fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } -} -#[stable(feature = "rust1", since = "1.0.0")] -impl<K> ExactSizeIterator for IntoIter<K> { - fn len(&self) -> usize { self.iter.len() } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K> Iterator for Drain<'a, K> { - type Item = K; - - fn next(&mut self) -> Option<K> { self.iter.next() } - fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } -} -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K> ExactSizeIterator for Drain<'a, K> { - fn len(&self) -> usize { self.iter.len() } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, T, S, H> Iterator for Intersection<'a, T, S> - where T: Eq + Hash<H>, - S: HashState<Hasher=H>, - H: hash::Hasher<Output=u64> -{ - type Item = &'a T; - - fn next(&mut self) -> Option<&'a T> { - loop { - match self.iter.next() { - None => return None, - Some(elt) => if self.other.contains(elt) { - return Some(elt) - }, - } - } - } - - fn size_hint(&self) -> (usize, Option<usize>) { - let (_, upper) = self.iter.size_hint(); - (0, upper) - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, T, S, H> Iterator for Difference<'a, T, S> - where T: Eq + Hash<H>, - S: HashState<Hasher=H>, - H: hash::Hasher<Output=u64> -{ - type Item = &'a T; - - fn next(&mut self) -> Option<&'a T> { - loop { - match self.iter.next() { - None => return None, - Some(elt) => if !self.other.contains(elt) { - return Some(elt) - }, - } - } - } - - fn size_hint(&self) -> (usize, Option<usize>) { - let (_, upper) = self.iter.size_hint(); - (0, upper) - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, T, S, H> Iterator for SymmetricDifference<'a, T, S> - where T: Eq + Hash<H>, - S: HashState<Hasher=H>, - H: hash::Hasher<Output=u64> -{ - type Item = &'a T; - - fn next(&mut self) -> Option<&'a T> { self.iter.next() } - fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, T, S, H> Iterator for Union<'a, T, S> - where T: Eq + Hash<H>, - S: HashState<Hasher=H>, - H: hash::Hasher<Output=u64> -{ - type Item = &'a T; - - fn next(&mut self) -> Option<&'a T> { self.iter.next() } - fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } -} - -#[cfg(test)] -mod test_set { - use prelude::v1::*; - - use super::HashSet; - - #[test] - fn test_disjoint() { - let mut xs = HashSet::new(); - let mut ys = HashSet::new(); - assert!(xs.is_disjoint(&ys)); - assert!(ys.is_disjoint(&xs)); - assert!(xs.insert(5)); - assert!(ys.insert(11)); - assert!(xs.is_disjoint(&ys)); - assert!(ys.is_disjoint(&xs)); - assert!(xs.insert(7)); - assert!(xs.insert(19)); - assert!(xs.insert(4)); - assert!(ys.insert(2)); - assert!(ys.insert(-11)); - assert!(xs.is_disjoint(&ys)); - assert!(ys.is_disjoint(&xs)); - assert!(ys.insert(7)); - assert!(!xs.is_disjoint(&ys)); - assert!(!ys.is_disjoint(&xs)); - } - - #[test] - fn test_subset_and_superset() { - let mut a = HashSet::new(); - assert!(a.insert(0)); - assert!(a.insert(5)); - assert!(a.insert(11)); - assert!(a.insert(7)); - - let mut b = HashSet::new(); - assert!(b.insert(0)); - assert!(b.insert(7)); - assert!(b.insert(19)); - assert!(b.insert(250)); - assert!(b.insert(11)); - assert!(b.insert(200)); - - assert!(!a.is_subset(&b)); - assert!(!a.is_superset(&b)); - assert!(!b.is_subset(&a)); - assert!(!b.is_superset(&a)); - - assert!(b.insert(5)); - - assert!(a.is_subset(&b)); - assert!(!a.is_superset(&b)); - assert!(!b.is_subset(&a)); - assert!(b.is_superset(&a)); - } - - #[test] - fn test_iterate() { - let mut a = HashSet::new(); - for i in 0..32 { - assert!(a.insert(i)); - } - let mut observed: u32 = 0; - for k in &a { - observed |= 1 << *k; - } - assert_eq!(observed, 0xFFFF_FFFF); - } - - #[test] - fn test_intersection() { - let mut a = HashSet::new(); - let mut b = HashSet::new(); - - assert!(a.insert(11)); - assert!(a.insert(1)); - assert!(a.insert(3)); - assert!(a.insert(77)); - assert!(a.insert(103)); - assert!(a.insert(5)); - assert!(a.insert(-5)); - - assert!(b.insert(2)); - assert!(b.insert(11)); - assert!(b.insert(77)); - assert!(b.insert(-9)); - assert!(b.insert(-42)); - assert!(b.insert(5)); - assert!(b.insert(3)); - - let mut i = 0; - let expected = [3, 5, 11, 77]; - for x in a.intersection(&b) { - assert!(expected.contains(x)); - i += 1 - } - assert_eq!(i, expected.len()); - } - - #[test] - fn test_difference() { - let mut a = HashSet::new(); - let mut b = HashSet::new(); - - assert!(a.insert(1)); - assert!(a.insert(3)); - assert!(a.insert(5)); - assert!(a.insert(9)); - assert!(a.insert(11)); - - assert!(b.insert(3)); - assert!(b.insert(9)); - - let mut i = 0; - let expected = [1, 5, 11]; - for x in a.difference(&b) { - assert!(expected.contains(x)); - i += 1 - } - assert_eq!(i, expected.len()); - } - - #[test] - fn test_symmetric_difference() { - let mut a = HashSet::new(); - let mut b = HashSet::new(); - - assert!(a.insert(1)); - assert!(a.insert(3)); - assert!(a.insert(5)); - assert!(a.insert(9)); - assert!(a.insert(11)); - - assert!(b.insert(-2)); - assert!(b.insert(3)); - assert!(b.insert(9)); - assert!(b.insert(14)); - assert!(b.insert(22)); - - let mut i = 0; - let expected = [-2, 1, 5, 11, 14, 22]; - for x in a.symmetric_difference(&b) { - assert!(expected.contains(x)); - i += 1 - } - assert_eq!(i, expected.len()); - } - - #[test] - fn test_union() { - let mut a = HashSet::new(); - let mut b = HashSet::new(); - - assert!(a.insert(1)); - assert!(a.insert(3)); - assert!(a.insert(5)); - assert!(a.insert(9)); - assert!(a.insert(11)); - assert!(a.insert(16)); - assert!(a.insert(19)); - assert!(a.insert(24)); - - assert!(b.insert(-2)); - assert!(b.insert(1)); - assert!(b.insert(5)); - assert!(b.insert(9)); - assert!(b.insert(13)); - assert!(b.insert(19)); - - let mut i = 0; - let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24]; - for x in a.union(&b) { - assert!(expected.contains(x)); - i += 1 - } - assert_eq!(i, expected.len()); - } - - #[test] - fn test_from_iter() { - let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9]; - - let set: HashSet<_> = xs.iter().cloned().collect(); - - for x in &xs { - assert!(set.contains(x)); - } - } - - #[test] - fn test_move_iter() { - let hs = { - let mut hs = HashSet::new(); - - hs.insert('a'); - hs.insert('b'); - - hs - }; - - let v = hs.into_iter().collect::<Vec<char>>(); - assert!(['a', 'b'] == v || ['b', 'a'] == v); - } - - #[test] - fn test_eq() { - // These constants once happened to expose a bug in insert(). - // I'm keeping them around to prevent a regression. - let mut s1 = HashSet::new(); - - s1.insert(1); - s1.insert(2); - s1.insert(3); - - let mut s2 = HashSet::new(); - - s2.insert(1); - s2.insert(2); - - assert!(s1 != s2); - - s2.insert(3); - - assert_eq!(s1, s2); - } - - #[test] - fn test_show() { - let mut set = HashSet::new(); - let empty = HashSet::<i32>::new(); - - set.insert(1); - set.insert(2); - - let set_str = format!("{:?}", set); - - assert!(set_str == "HashSet {1, 2}" || set_str == "HashSet {2, 1}"); - assert_eq!(format!("{:?}", empty), "HashSet {}"); - } - - #[test] - fn test_trivial_drain() { - let mut s = HashSet::<i32>::new(); - for _ in s.drain() {} - assert!(s.is_empty()); - drop(s); - - let mut s = HashSet::<i32>::new(); - drop(s.drain()); - assert!(s.is_empty()); - } - - #[test] - fn test_drain() { - let mut s: HashSet<_> = (1..100).collect(); - - // try this a bunch of times to make sure we don't screw up internal state. - for _ in 0..20 { - assert_eq!(s.len(), 99); - - { - let mut last_i = 0; - let mut d = s.drain(); - for (i, x) in d.by_ref().take(50).enumerate() { - last_i = i; - assert!(x != 0); - } - assert_eq!(last_i, 49); - } - - for _ in &s { panic!("s should be empty!"); } - - // reset to try again. - s.extend(1..100); - } - } -} diff --git a/src/libstd/collections/hash/table.rs b/src/libstd/collections/hash/table.rs index f301f6db92f..7513cb8a61c 100644 --- a/src/libstd/collections/hash/table.rs +++ b/src/libstd/collections/hash/table.rs @@ -143,25 +143,6 @@ impl SafeHash { /// We need to remove hashes of 0. That's reserved for empty buckets. /// This function wraps up `hash_keyed` to be the only way outside this /// module to generate a SafeHash. -#[cfg(stage0)] -pub fn make_hash<T: ?Sized, S, H>(hash_state: &S, t: &T) -> SafeHash - where T: Hash<H>, - S: HashState<Hasher=H>, - H: Hasher<Output=u64> -{ - let mut state = hash_state.hasher(); - t.hash(&mut state); - // We need to avoid 0u64 in order to prevent collisions with - // EMPTY_HASH. We can maintain our precious uniform distribution - // of initial indexes by unconditionally setting the MSB, - // effectively reducing 64-bits hashes to 63 bits. - SafeHash { hash: 0x8000_0000_0000_0000 | state.finish() } -} - -/// We need to remove hashes of 0. That's reserved for empty buckets. -/// This function wraps up `hash_keyed` to be the only way outside this -/// module to generate a SafeHash. -#[cfg(not(stage0))] pub fn make_hash<T: ?Sized, S>(hash_state: &S, t: &T) -> SafeHash where T: Hash, S: HashState { diff --git a/src/libstd/ffi/os_str.rs b/src/libstd/ffi/os_str.rs index 84149a2eb8e..fe0df1728ef 100644 --- a/src/libstd/ffi/os_str.rs +++ b/src/libstd/ffi/os_str.rs @@ -41,7 +41,6 @@ use string::{String, CowString}; use ops; use cmp; use hash::{Hash, Hasher}; -#[cfg(stage0)] use hash::Writer; use old_path::{Path, GenericPath}; use sys::os_str::{Buf, Slice}; @@ -163,14 +162,6 @@ impl Ord for OsString { } } -#[cfg(stage0)] -impl<'a, S: Hasher + Writer> Hash<S> for OsString { - #[inline] - fn hash(&self, state: &mut S) { - (&**self).hash(state) - } -} -#[cfg(not(stage0))] #[stable(feature = "rust1", since = "1.0.0")] impl Hash for OsString { #[inline] @@ -263,14 +254,6 @@ impl Ord for OsStr { fn cmp(&self, other: &OsStr) -> cmp::Ordering { self.bytes().cmp(other.bytes()) } } -#[cfg(stage0)] -impl<'a, S: Hasher + Writer> Hash<S> for OsStr { - #[inline] - fn hash(&self, state: &mut S) { - self.bytes().hash(state) - } -} -#[cfg(not(stage0))] #[stable(feature = "rust1", since = "1.0.0")] impl Hash for OsStr { #[inline] diff --git a/src/libstd/net/addr.rs b/src/libstd/net/addr.rs index 51944adf3b4..f16f501c46a 100644 --- a/src/libstd/net/addr.rs +++ b/src/libstd/net/addr.rs @@ -147,21 +147,6 @@ impl PartialEq for Repr { } impl Eq for Repr {} -#[cfg(stage0)] -impl<S: hash::Hasher + hash::Writer> hash::Hash<S> for Repr { - fn hash(&self, s: &mut S) { - match *self { - Repr::V4(ref a) => { - (a.sin_family, a.sin_port, a.sin_addr.s_addr).hash(s) - } - Repr::V6(ref a) => { - (a.sin6_family, a.sin6_port, &a.sin6_addr.s6_addr, - a.sin6_flowinfo, a.sin6_scope_id).hash(s) - } - } - } -} -#[cfg(not(stage0))] #[stable(feature = "rust1", since = "1.0.0")] impl hash::Hash for Repr { fn hash<H: hash::Hasher>(&self, s: &mut H) { diff --git a/src/libstd/net/ip.rs b/src/libstd/net/ip.rs index 571a1b03ef0..d699886e577 100644 --- a/src/libstd/net/ip.rs +++ b/src/libstd/net/ip.rs @@ -189,13 +189,6 @@ impl PartialEq for Ipv4Addr { } impl Eq for Ipv4Addr {} -#[cfg(stage0)] -impl<S: hash::Hasher + hash::Writer> hash::Hash<S> for Ipv4Addr { - fn hash(&self, s: &mut S) { - self.inner.s_addr.hash(s) - } -} -#[cfg(not(stage0))] #[stable(feature = "rust1", since = "1.0.0")] impl hash::Hash for Ipv4Addr { fn hash<H: hash::Hasher>(&self, s: &mut H) { @@ -429,13 +422,6 @@ impl PartialEq for Ipv6Addr { } impl Eq for Ipv6Addr {} -#[cfg(stage0)] -impl<S: hash::Hasher + hash::Writer> hash::Hash<S> for Ipv6Addr { - fn hash(&self, s: &mut S) { - self.inner.s6_addr.hash(s) - } -} -#[cfg(not(stage0))] #[stable(feature = "rust1", since = "1.0.0")] impl hash::Hash for Ipv6Addr { fn hash<H: hash::Hasher>(&self, s: &mut H) { diff --git a/src/libstd/old_io/process.rs b/src/libstd/old_io/process.rs index c803cfbcb7d..a13295b1ccb 100644 --- a/src/libstd/old_io/process.rs +++ b/src/libstd/old_io/process.rs @@ -104,19 +104,7 @@ struct EnvKey(CString); #[derive(Eq, Clone, Debug)] struct EnvKey(CString); -#[cfg(all(windows, stage0))] -impl<H: hash::Writer + hash::Hasher> hash::Hash<H> for EnvKey { - fn hash(&self, state: &mut H) { - let &EnvKey(ref x) = self; - match str::from_utf8(x.as_bytes()) { - Ok(s) => for ch in s.chars() { - (ch as u8 as char).to_lowercase().hash(state); - }, - Err(..) => x.hash(state) - } - } -} -#[cfg(all(windows, not(stage0)))] +#[cfg(windows)] impl hash::Hash for EnvKey { fn hash<H: hash::Hasher>(&self, state: &mut H) { let &EnvKey(ref x) = self; diff --git a/src/libstd/old_path/posix.rs b/src/libstd/old_path/posix.rs index 15eee9e4a0c..8d5765e1ffe 100644 --- a/src/libstd/old_path/posix.rs +++ b/src/libstd/old_path/posix.rs @@ -100,14 +100,6 @@ impl FromStr for Path { #[derive(Debug, Clone, PartialEq, Copy)] pub struct ParsePathError; -#[cfg(stage0)] -impl<S: hash::Writer + hash::Hasher> hash::Hash<S> for Path { - #[inline] - fn hash(&self, state: &mut S) { - self.repr.hash(state) - } -} -#[cfg(not(stage0))] #[stable(feature = "rust1", since = "1.0.0")] impl hash::Hash for Path { #[inline] diff --git a/src/libstd/old_path/windows.rs b/src/libstd/old_path/windows.rs index 887dc804c7a..31a2be1daf3 100644 --- a/src/libstd/old_path/windows.rs +++ b/src/libstd/old_path/windows.rs @@ -127,21 +127,6 @@ impl FromStr for Path { #[derive(Debug, Clone, PartialEq, Copy)] pub struct ParsePathError; -#[cfg(stage0)] -impl<S: hash::Writer + hash::Hasher> hash::Hash<S> for Path { - #[cfg(not(test))] - #[inline] - fn hash(&self, state: &mut S) { - self.repr.hash(state) - } - - #[cfg(test)] - #[inline] - fn hash(&self, _: &mut S) { - // No-op because the `hash` implementation will be wrong. - } -} -#[cfg(not(stage0))] #[stable(feature = "rust1", since = "1.0.0")] impl hash::Hash for Path { #[cfg(not(test))] diff --git a/src/libstd/sys/common/wtf8.rs b/src/libstd/sys/common/wtf8.rs index ca3ae1a7a34..9119a3c60d8 100644 --- a/src/libstd/sys/common/wtf8.rs +++ b/src/libstd/sys/common/wtf8.rs @@ -32,7 +32,6 @@ use borrow::Cow; use cmp; use fmt; use hash::{Hash, Hasher}; -#[cfg(stage0)] use hash::Writer; use iter::{FromIterator, IntoIterator}; use mem; use num::Int; @@ -796,14 +795,6 @@ impl<'a> Iterator for EncodeWide<'a> { } } -#[cfg(stage0)] -impl<S: Writer + Hasher> Hash<S> for CodePoint { - #[inline] - fn hash(&self, state: &mut S) { - self.value.hash(state) - } -} -#[cfg(not(stage0))] impl Hash for CodePoint { #[inline] fn hash<H: Hasher>(&self, state: &mut H) { @@ -811,15 +802,6 @@ impl Hash for CodePoint { } } -#[cfg(stage0)] -impl<S: Writer + Hasher> Hash<S> for Wtf8Buf { - #[inline] - fn hash(&self, state: &mut S) { - state.write(&self.bytes); - 0xfeu8.hash(state) - } -} -#[cfg(not(stage0))] impl Hash for Wtf8Buf { #[inline] fn hash<H: Hasher>(&self, state: &mut H) { @@ -828,15 +810,6 @@ impl Hash for Wtf8Buf { } } -#[cfg(stage0)] -impl<'a, S: Writer + Hasher> Hash<S> for Wtf8 { - #[inline] - fn hash(&self, state: &mut S) { - state.write(&self.bytes); - 0xfeu8.hash(state) - } -} -#[cfg(not(stage0))] impl Hash for Wtf8 { #[inline] fn hash<H: Hasher>(&self, state: &mut H) { diff --git a/src/libstd/sys/unix/process.rs b/src/libstd/sys/unix/process.rs index b30ac889120..4f48485bfc4 100644 --- a/src/libstd/sys/unix/process.rs +++ b/src/libstd/sys/unix/process.rs @@ -12,8 +12,6 @@ use prelude::v1::*; use self::Req::*; use collections::HashMap; -#[cfg(stage0)] -use collections::hash_map::Hasher; use ffi::CString; use hash::Hash; use old_io::process::{ProcessExit, ExitStatus, ExitSignal}; @@ -64,223 +62,6 @@ impl Process { mkerr_libc(r) } - #[cfg(stage0)] - pub fn spawn<K, V, C, P>(cfg: &C, in_fd: Option<P>, - out_fd: Option<P>, err_fd: Option<P>) - -> IoResult<Process> - where C: ProcessConfig<K, V>, P: AsInner<FileDesc>, - K: BytesContainer + Eq + Hash<Hasher>, V: BytesContainer - { - use libc::funcs::posix88::unistd::{fork, dup2, close, chdir, execvp}; - - mod rustrt { - extern { - pub fn rust_unset_sigprocmask(); - } - } - - #[cfg(all(target_os = "android", target_arch = "aarch64"))] - unsafe fn getdtablesize() -> c_int { - libc::sysconf(libc::consts::os::sysconf::_SC_OPEN_MAX) as c_int - } - #[cfg(not(all(target_os = "android", target_arch = "aarch64")))] - unsafe fn getdtablesize() -> c_int { - libc::funcs::bsd44::getdtablesize() - } - - unsafe fn set_cloexec(fd: c_int) { - let ret = c::ioctl(fd, c::FIOCLEX); - assert_eq!(ret, 0); - } - - let dirp = cfg.cwd().map(|c| c.as_ptr()).unwrap_or(ptr::null()); - - // temporary until unboxed closures land - let cfg = unsafe { - mem::transmute::<&ProcessConfig<K,V>,&'static ProcessConfig<K,V>>(cfg) - }; - - with_envp(cfg.env(), move|envp: *const c_void| { - with_argv(cfg.program(), cfg.args(), move|argv: *const *const libc::c_char| unsafe { - let (input, mut output) = try!(sys::os::pipe()); - - // We may use this in the child, so perform allocations before the - // fork - let devnull = b"/dev/null\0"; - - set_cloexec(output.fd()); - - let pid = fork(); - if pid < 0 { - return Err(super::last_error()) - } else if pid > 0 { - #[inline] - fn combine(arr: &[u8]) -> i32 { - let a = arr[0] as u32; - let b = arr[1] as u32; - let c = arr[2] as u32; - let d = arr[3] as u32; - - ((a << 24) | (b << 16) | (c << 8) | (d << 0)) as i32 - } - - let p = Process{ pid: pid }; - drop(output); - let mut bytes = [0; 8]; - return match input.read(&mut bytes) { - Ok(8) => { - assert!(combine(CLOEXEC_MSG_FOOTER) == combine(&bytes[4.. 8]), - "Validation on the CLOEXEC pipe failed: {:?}", bytes); - let errno = combine(&bytes[0.. 4]); - assert!(p.wait(0).is_ok(), "wait(0) should either return Ok or panic"); - Err(super::decode_error(errno)) - } - Err(ref e) if e.kind == EndOfFile => Ok(p), - Err(e) => { - assert!(p.wait(0).is_ok(), "wait(0) should either return Ok or panic"); - panic!("the CLOEXEC pipe failed: {:?}", e) - }, - Ok(..) => { // pipe I/O up to PIPE_BUF bytes should be atomic - assert!(p.wait(0).is_ok(), "wait(0) should either return Ok or panic"); - panic!("short read on the CLOEXEC pipe") - } - }; - } - - // And at this point we've reached a special time in the life of the - // child. The child must now be considered hamstrung and unable to - // do anything other than syscalls really. Consider the following - // scenario: - // - // 1. Thread A of process 1 grabs the malloc() mutex - // 2. Thread B of process 1 forks(), creating thread C - // 3. Thread C of process 2 then attempts to malloc() - // 4. The memory of process 2 is the same as the memory of - // process 1, so the mutex is locked. - // - // This situation looks a lot like deadlock, right? It turns out - // that this is what pthread_atfork() takes care of, which is - // presumably implemented across platforms. The first thing that - // threads to *before* forking is to do things like grab the malloc - // mutex, and then after the fork they unlock it. - // - // Despite this information, libnative's spawn has been witnessed to - // deadlock on both OSX and FreeBSD. I'm not entirely sure why, but - // all collected backtraces point at malloc/free traffic in the - // child spawned process. - // - // For this reason, the block of code below should contain 0 - // invocations of either malloc of free (or their related friends). - // - // As an example of not having malloc/free traffic, we don't close - // this file descriptor by dropping the FileDesc (which contains an - // allocation). Instead we just close it manually. This will never - // have the drop glue anyway because this code never returns (the - // child will either exec() or invoke libc::exit) - let _ = libc::close(input.fd()); - - fn fail(output: &mut FileDesc) -> ! { - let errno = sys::os::errno() as u32; - let bytes = [ - (errno >> 24) as u8, - (errno >> 16) as u8, - (errno >> 8) as u8, - (errno >> 0) as u8, - CLOEXEC_MSG_FOOTER[0], CLOEXEC_MSG_FOOTER[1], - CLOEXEC_MSG_FOOTER[2], CLOEXEC_MSG_FOOTER[3] - ]; - // pipe I/O up to PIPE_BUF bytes should be atomic - assert!(output.write(&bytes).is_ok()); - unsafe { libc::_exit(1) } - } - - rustrt::rust_unset_sigprocmask(); - - // If a stdio file descriptor is set to be ignored (via a -1 file - // descriptor), then we don't actually close it, but rather open - // up /dev/null into that file descriptor. Otherwise, the first file - // descriptor opened up in the child would be numbered as one of the - // stdio file descriptors, which is likely to wreak havoc. - let setup = |src: Option<P>, dst: c_int| { - let src = match src { - None => { - let flags = if dst == libc::STDIN_FILENO { - libc::O_RDONLY - } else { - libc::O_RDWR - }; - libc::open(devnull.as_ptr() as *const _, flags, 0) - } - Some(obj) => { - let fd = obj.as_inner().fd(); - // Leak the memory and the file descriptor. We're in the - // child now an all our resources are going to be - // cleaned up very soon - mem::forget(obj); - fd - } - }; - src != -1 && retry(|| dup2(src, dst)) != -1 - }; - - if !setup(in_fd, libc::STDIN_FILENO) { fail(&mut output) } - if !setup(out_fd, libc::STDOUT_FILENO) { fail(&mut output) } - if !setup(err_fd, libc::STDERR_FILENO) { fail(&mut output) } - - // close all other fds - for fd in (3..getdtablesize()).rev() { - if fd != output.fd() { - let _ = close(fd as c_int); - } - } - - match cfg.gid() { - Some(u) => { - if libc::setgid(u as libc::gid_t) != 0 { - fail(&mut output); - } - } - None => {} - } - match cfg.uid() { - Some(u) => { - // When dropping privileges from root, the `setgroups` call - // will remove any extraneous groups. If we don't call this, - // then even though our uid has dropped, we may still have - // groups that enable us to do super-user things. This will - // fail if we aren't root, so don't bother checking the - // return value, this is just done as an optimistic - // privilege dropping function. - extern { - fn setgroups(ngroups: libc::c_int, - ptr: *const libc::c_void) -> libc::c_int; - } - let _ = setgroups(0, ptr::null()); - - if libc::setuid(u as libc::uid_t) != 0 { - fail(&mut output); - } - } - None => {} - } - if cfg.detach() { - // Don't check the error of setsid because it fails if we're the - // process leader already. We just forked so it shouldn't return - // error, but ignore it anyway. - let _ = libc::setsid(); - } - if !dirp.is_null() && chdir(dirp) == -1 { - fail(&mut output); - } - if !envp.is_null() { - *sys::os::environ() = envp as *const _; - } - let _ = execvp(*argv, argv as *mut _); - fail(&mut output); - }) - }) - } - #[cfg(not(stage0))] pub fn spawn<K, V, C, P>(cfg: &C, in_fd: Option<P>, out_fd: Option<P>, err_fd: Option<P>) -> IoResult<Process> @@ -766,45 +547,6 @@ fn with_argv<T,F>(prog: &CString, args: &[CString], cb(ptrs.as_ptr()) } -#[cfg(stage0)] -fn with_envp<K,V,T,F>(env: Option<&HashMap<K, V>>, - cb: F) - -> T - where F : FnOnce(*const c_void) -> T, - K : BytesContainer + Eq + Hash<Hasher>, - V : BytesContainer -{ - // On posixy systems we can pass a char** for envp, which is a - // null-terminated array of "k=v\0" strings. Since we must create - // these strings locally, yet expose a raw pointer to them, we - // create a temporary vector to own the CStrings that outlives the - // call to cb. - match env { - Some(env) => { - let mut tmps = Vec::with_capacity(env.len()); - - for pair in env { - let mut kv = Vec::new(); - kv.push_all(pair.0.container_as_bytes()); - kv.push('=' as u8); - kv.push_all(pair.1.container_as_bytes()); - kv.push(0); // terminating null - tmps.push(kv); - } - - // As with `with_argv`, this is unsafe, since cb could leak the pointers. - let mut ptrs: Vec<*const libc::c_char> = - tmps.iter() - .map(|tmp| tmp.as_ptr() as *const libc::c_char) - .collect(); - ptrs.push(ptr::null()); - - cb(ptrs.as_ptr() as *const c_void) - } - _ => cb(ptr::null()) - } -} -#[cfg(not(stage0))] fn with_envp<K,V,T,F>(env: Option<&HashMap<K, V>>, cb: F) -> T diff --git a/src/libstd/sys/windows/process.rs b/src/libstd/sys/windows/process.rs index 60d24e6174f..334cafd3eb1 100644 --- a/src/libstd/sys/windows/process.rs +++ b/src/libstd/sys/windows/process.rs @@ -10,7 +10,6 @@ use prelude::v1::*; -#[cfg(stage0)] use collections::hash_map::Hasher; use collections; use env; use ffi::CString; @@ -106,170 +105,6 @@ impl Process { } #[allow(deprecated)] - #[cfg(stage0)] - pub fn spawn<K, V, C, P>(cfg: &C, in_fd: Option<P>, - out_fd: Option<P>, err_fd: Option<P>) - -> IoResult<Process> - where C: ProcessConfig<K, V>, P: AsInner<FileDesc>, - K: BytesContainer + Eq + Hash<Hasher>, V: BytesContainer - { - use libc::types::os::arch::extra::{DWORD, HANDLE, STARTUPINFO}; - use libc::consts::os::extra::{ - TRUE, FALSE, - STARTF_USESTDHANDLES, - INVALID_HANDLE_VALUE, - DUPLICATE_SAME_ACCESS - }; - use libc::funcs::extra::kernel32::{ - GetCurrentProcess, - DuplicateHandle, - CloseHandle, - CreateProcessW - }; - use libc::funcs::extra::msvcrt::get_osfhandle; - - use mem; - use iter::IteratorExt; - use str::StrExt; - - if cfg.gid().is_some() || cfg.uid().is_some() { - return Err(IoError { - kind: old_io::IoUnavailable, - desc: "unsupported gid/uid requested on windows", - detail: None, - }) - } - - // To have the spawning semantics of unix/windows stay the same, we need to - // read the *child's* PATH if one is provided. See #15149 for more details. - let program = cfg.env().and_then(|env| { - for (key, v) in env { - if b"PATH" != key.container_as_bytes() { continue } - - // Split the value and test each path to see if the - // program exists. - for path in os::split_paths(v.container_as_bytes()) { - let path = path.join(cfg.program().as_bytes()) - .with_extension(env::consts::EXE_EXTENSION); - if path.exists() { - return Some(CString::from_slice(path.as_vec())) - } - } - break - } - None - }); - - unsafe { - let mut si = zeroed_startupinfo(); - si.cb = mem::size_of::<STARTUPINFO>() as DWORD; - si.dwFlags = STARTF_USESTDHANDLES; - - let cur_proc = GetCurrentProcess(); - - // Similarly to unix, we don't actually leave holes for the stdio file - // descriptors, but rather open up /dev/null equivalents. These - // equivalents are drawn from libuv's windows process spawning. - let set_fd = |fd: &Option<P>, slot: &mut HANDLE, - is_stdin: bool| { - match *fd { - None => { - let access = if is_stdin { - libc::FILE_GENERIC_READ - } else { - libc::FILE_GENERIC_WRITE | libc::FILE_READ_ATTRIBUTES - }; - let size = mem::size_of::<libc::SECURITY_ATTRIBUTES>(); - let mut sa = libc::SECURITY_ATTRIBUTES { - nLength: size as libc::DWORD, - lpSecurityDescriptor: ptr::null_mut(), - bInheritHandle: 1, - }; - let mut filename: Vec<u16> = "NUL".utf16_units().collect(); - filename.push(0); - *slot = libc::CreateFileW(filename.as_ptr(), - access, - libc::FILE_SHARE_READ | - libc::FILE_SHARE_WRITE, - &mut sa, - libc::OPEN_EXISTING, - 0, - ptr::null_mut()); - if *slot == INVALID_HANDLE_VALUE { - return Err(super::last_error()) - } - } - Some(ref fd) => { - let orig = get_osfhandle(fd.as_inner().fd()) as HANDLE; - if orig == INVALID_HANDLE_VALUE { - return Err(super::last_error()) - } - if DuplicateHandle(cur_proc, orig, cur_proc, slot, - 0, TRUE, DUPLICATE_SAME_ACCESS) == FALSE { - return Err(super::last_error()) - } - } - } - Ok(()) - }; - - try!(set_fd(&in_fd, &mut si.hStdInput, true)); - try!(set_fd(&out_fd, &mut si.hStdOutput, false)); - try!(set_fd(&err_fd, &mut si.hStdError, false)); - - let cmd_str = make_command_line(program.as_ref().unwrap_or(cfg.program()), - cfg.args()); - let mut pi = zeroed_process_information(); - let mut create_err = None; - - // stolen from the libuv code. - let mut flags = libc::CREATE_UNICODE_ENVIRONMENT; - if cfg.detach() { - flags |= libc::DETACHED_PROCESS | libc::CREATE_NEW_PROCESS_GROUP; - } - - with_envp(cfg.env(), |envp| { - with_dirp(cfg.cwd(), |dirp| { - let mut cmd_str: Vec<u16> = cmd_str.utf16_units().collect(); - cmd_str.push(0); - let _lock = CREATE_PROCESS_LOCK.lock().unwrap(); - let created = CreateProcessW(ptr::null(), - cmd_str.as_mut_ptr(), - ptr::null_mut(), - ptr::null_mut(), - TRUE, - flags, envp, dirp, - &mut si, &mut pi); - if created == FALSE { - create_err = Some(super::last_error()); - } - }) - }); - - assert!(CloseHandle(si.hStdInput) != 0); - assert!(CloseHandle(si.hStdOutput) != 0); - assert!(CloseHandle(si.hStdError) != 0); - - match create_err { - Some(err) => return Err(err), - None => {} - } - - // We close the thread handle because we don't care about keeping the - // thread id valid, and we aren't keeping the thread handle around to be - // able to close it later. We don't close the process handle however - // because std::we want the process id to stay valid at least until the - // calling code closes the process handle. - assert!(CloseHandle(pi.hThread) != 0); - - Ok(Process { - pid: pi.dwProcessId as pid_t, - handle: pi.hProcess as *mut () - }) - } - } - #[allow(deprecated)] - #[cfg(not(stage0))] pub fn spawn<K, V, C, P>(cfg: &C, in_fd: Option<P>, out_fd: Option<P>, err_fd: Option<P>) -> IoResult<Process> @@ -589,35 +424,6 @@ fn make_command_line(prog: &CString, args: &[CString]) -> String { } } -#[cfg(stage0)] -fn with_envp<K, V, T, F>(env: Option<&collections::HashMap<K, V>>, cb: F) -> T - where K: BytesContainer + Eq + Hash<Hasher>, - V: BytesContainer, - F: FnOnce(*mut c_void) -> T, -{ - // On Windows we pass an "environment block" which is not a char**, but - // rather a concatenation of null-terminated k=v\0 sequences, with a final - // \0 to terminate. - match env { - Some(env) => { - let mut blk = Vec::new(); - - for pair in env { - let kv = format!("{}={}", - pair.0.container_as_str().unwrap(), - pair.1.container_as_str().unwrap()); - blk.extend(kv.utf16_units()); - blk.push(0); - } - - blk.push(0); - - cb(blk.as_mut_ptr() as *mut c_void) - } - _ => cb(ptr::null_mut()) - } -} -#[cfg(not(stage0))] fn with_envp<K, V, T, F>(env: Option<&collections::HashMap<K, V>>, cb: F) -> T where K: BytesContainer + Eq + Hash, V: BytesContainer, diff --git a/src/libstd/thunk.rs b/src/libstd/thunk.rs index fe39954f0d4..5bede984f13 100644 --- a/src/libstd/thunk.rs +++ b/src/libstd/thunk.rs @@ -17,9 +17,6 @@ use core::marker::Send; use core::ops::FnOnce; pub struct Thunk<'a, A=(),R=()> { - #[cfg(stage0)] - invoke: Box<Invoke<A,R>+Send>, - #[cfg(not(stage0))] invoke: Box<Invoke<A,R>+Send + 'a>, } diff --git a/src/libsyntax/ptr.rs b/src/libsyntax/ptr.rs index adb5383a8fd..ca3a1848c3a 100644 --- a/src/libsyntax/ptr.rs +++ b/src/libsyntax/ptr.rs @@ -111,13 +111,6 @@ impl<T: Display> Display for P<T> { } } -#[cfg(stage0)] -impl<S: Hasher, T: Hash<S>> Hash<S> for P<T> { - fn hash(&self, state: &mut S) { - (**self).hash(state); - } -} -#[cfg(not(stage0))] impl<T: Hash> Hash for P<T> { fn hash<H: Hasher>(&self, state: &mut H) { (**self).hash(state); diff --git a/src/libsyntax/util/interner.rs b/src/libsyntax/util/interner.rs index dffeac6f3f7..5be45a2698f 100644 --- a/src/libsyntax/util/interner.rs +++ b/src/libsyntax/util/interner.rs @@ -18,7 +18,6 @@ use std::borrow::Borrow; use std::cell::RefCell; use std::cmp::Ordering; use std::collections::HashMap; -#[cfg(stage0)] use std::collections::hash_map::Hasher; use std::fmt; use std::hash::Hash; use std::ops::Deref; @@ -30,71 +29,6 @@ pub struct Interner<T> { } // when traits can extend traits, we should extend index<Name,T> to get [] -#[cfg(stage0)] -impl<T: Eq + Hash<Hasher> + Clone + 'static> Interner<T> { - pub fn new() -> Interner<T> { - Interner { - map: RefCell::new(HashMap::new()), - vect: RefCell::new(Vec::new()), - } - } - - pub fn prefill(init: &[T]) -> Interner<T> { - let rv = Interner::new(); - for v in init { - rv.intern((*v).clone()); - } - rv - } - - pub fn intern(&self, val: T) -> Name { - let mut map = self.map.borrow_mut(); - match (*map).get(&val) { - Some(&idx) => return idx, - None => (), - } - - let mut vect = self.vect.borrow_mut(); - let new_idx = Name((*vect).len() as u32); - (*map).insert(val.clone(), new_idx); - (*vect).push(val); - new_idx - } - - pub fn gensym(&self, val: T) -> Name { - let mut vect = self.vect.borrow_mut(); - let new_idx = Name((*vect).len() as u32); - // leave out of .map to avoid colliding - (*vect).push(val); - new_idx - } - - pub fn get(&self, idx: Name) -> T { - let vect = self.vect.borrow(); - (*vect)[idx.usize()].clone() - } - - pub fn len(&self) -> usize { - let vect = self.vect.borrow(); - (*vect).len() - } - - pub fn find<Q: ?Sized>(&self, val: &Q) -> Option<Name> - where T: Borrow<Q>, Q: Eq + Hash<Hasher> { - let map = self.map.borrow(); - match (*map).get(val) { - Some(v) => Some(*v), - None => None, - } - } - - pub fn clear(&self) { - *self.map.borrow_mut() = HashMap::new(); - *self.vect.borrow_mut() = Vec::new(); - } -} -// when traits can extend traits, we should extend index<Name,T> to get [] -#[cfg(not(stage0))] impl<T: Eq + Hash + Clone + 'static> Interner<T> { pub fn new() -> Interner<T> { Interner { @@ -275,15 +209,6 @@ impl StrInterner { self.vect.borrow().len() } - #[cfg(stage0)] - pub fn find<Q: ?Sized>(&self, val: &Q) -> Option<Name> - where RcStr: Borrow<Q>, Q: Eq + Hash<Hasher> { - match (*self.map.borrow()).get(val) { - Some(v) => Some(*v), - None => None, - } - } - #[cfg(not(stage0))] pub fn find<Q: ?Sized>(&self, val: &Q) -> Option<Name> where RcStr: Borrow<Q>, Q: Eq + Hash { match (*self.map.borrow()).get(val) { diff --git a/src/snapshots.txt b/src/snapshots.txt index 4759c44259d..46a942b6eeb 100644 --- a/src/snapshots.txt +++ b/src/snapshots.txt @@ -1,3 +1,12 @@ +S 2015-02-19 522d09d + freebsd-x86_64 7ea14ef85a25bca70a310a2cd660b356cf61abc7 + linux-i386 26e3caa1ce1c482b9941a6bdc64b3e65d036c200 + linux-x86_64 44f514aabb4e4049e4db9a4e1fdeb16f6cee60f2 + macos-i386 157910592224083df56f5f31ced3e6f3dc9b1de0 + macos-x86_64 56c28aa0e14ec6991ad6ca213568f1155561105d + winnt-i386 da0f7a3fbc913fbb177917f2850bb41501affb5c + winnt-x86_64 22bd816ccd2690fc9804b27ca525f603be8aeaa5 + S 2015-02-17 f1bb6c2 freebsd-x86_64 59f3a2c6350c170804fb65838e1b504eeab89105 linux-i386 191ed5ec4f17e32d36abeade55a1c6085e51245c |