From 511f0b8a3de5a166fc96aba5170782c9abf92101 Mon Sep 17 00:00:00 2001 From: Alex Crichton Date: Tue, 9 Dec 2014 12:37:23 -0800 Subject: std: Stabilize the std::hash module This commit aims to prepare the `std::hash` module for alpha by formalizing its current interface whileholding off on adding `#[stable]` to the new APIs. The current usage with the `HashMap` and `HashSet` types is also reconciled by separating out composable parts of the design. The primary goal of this slight redesign is to separate the concepts of a hasher's state from a hashing algorithm itself. The primary change of this commit is to separate the `Hasher` trait into a `Hasher` and a `HashState` trait. Conceptually the old `Hasher` trait was actually just a factory for various states, but hashing had very little control over how these states were used. Additionally the old `Hasher` trait was actually fairly unrelated to hashing. This commit redesigns the existing `Hasher` trait to match what the notion of a `Hasher` normally implies with the following definition: trait Hasher { type Output; fn reset(&mut self); fn finish(&self) -> Output; } This `Hasher` trait emphasizes that hashing algorithms may produce outputs other than a `u64`, so the output type is made generic. Other than that, however, very little is assumed about a particular hasher. It is left up to implementors to provide specific methods or trait implementations to feed data into a hasher. The corresponding `Hash` trait becomes: trait Hash { fn hash(&self, &mut H); } The old default of `SipState` was removed from this trait as it's not something that we're willing to stabilize until the end of time, but the type parameter is always required to implement `Hasher`. Note that the type parameter `H` remains on the trait to enable multidispatch for specialization of hashing for particular hashers. Note that `Writer` is not mentioned in either of `Hash` or `Hasher`, it is simply used as part `derive` and the implementations for all primitive types. With these definitions, the old `Hasher` trait is realized as a new `HashState` trait in the `collections::hash_state` module as an unstable addition for now. The current definition looks like: trait HashState { type Hasher: Hasher; fn hasher(&self) -> Hasher; } The purpose of this trait is to emphasize that the one piece of functionality for implementors is that new instances of `Hasher` can be created. This conceptually represents the two keys from which more instances of a `SipHasher` can be created, and a `HashState` is what's stored in a `HashMap`, not a `Hasher`. Implementors of custom hash algorithms should implement the `Hasher` trait, and only hash algorithms intended for use in hash maps need to implement or worry about the `HashState` trait. The entire module and `HashState` infrastructure remains `#[unstable]` due to it being recently redesigned, but some other stability decision made for the `std::hash` module are: * The `Writer` trait remains `#[experimental]` as it's intended to be replaced with an `io::Writer` (more details soon). * The top-level `hash` function is `#[unstable]` as it is intended to be generic over the hashing algorithm instead of hardwired to `SipHasher` * The inner `sip` module is now private as its one export, `SipHasher` is reexported in the `hash` module. And finally, a few changes were made to the default parameters on `HashMap`. * The `RandomSipHasher` default type parameter was renamed to `RandomState`. This renaming emphasizes that it is not a hasher, but rather just state to generate hashers. It also moves away from the name "sip" as it may not always be implemented as `SipHasher`. This type lives in the `std::collections::hash_map` module as `#[unstable]` * The associated `Hasher` type of `RandomState` is creatively called... `Hasher`! This concrete structure lives next to `RandomState` as an implemenation of the "default hashing algorithm" used for a `HashMap`. Under the hood this is currently implemented as `SipHasher`, but it draws an explicit interface for now and allows us to modify the implementation over time if necessary. There are many breaking changes outlined above, and as a result this commit is a: [breaking-change] --- src/liballoc/arc.rs | 21 +++++++++++++-------- src/liballoc/boxed.rs | 8 ++++++++ src/liballoc/rc.rs | 35 +++++++++++++++++++++++------------ 3 files changed, 44 insertions(+), 20 deletions(-) (limited to 'src/liballoc') diff --git a/src/liballoc/arc.rs b/src/liballoc/arc.rs index 8def8ad7215..38d6f4dad6e 100644 --- a/src/liballoc/arc.rs +++ b/src/liballoc/arc.rs @@ -67,21 +67,20 @@ //! } //! ``` +use core::prelude::*; + use core::atomic; use core::atomic::Ordering::{Relaxed, Release, Acquire, SeqCst}; use core::borrow::BorrowFrom; -use core::clone::Clone; use core::fmt::{self, Show}; -use core::cmp::{Eq, Ord, PartialEq, PartialOrd, Ordering}; +use core::cmp::{Ordering}; use core::default::Default; -use core::marker::{Sync, Send}; -use core::mem::{min_align_of, size_of, drop}; +use core::mem::{min_align_of, size_of}; use core::mem; use core::nonzero::NonZero; -use core::ops::{Drop, Deref}; -use core::option::Option; -use core::option::Option::{Some, None}; -use core::ptr::{self, PtrExt}; +use core::ops::Deref; +use core::ptr; +use core::hash::{Hash, Hasher}; use heap::deallocate; /// An atomically reference counted wrapper for shared state. @@ -591,6 +590,12 @@ impl Default for Arc { fn default() -> Arc { Arc::new(Default::default()) } } +impl> Hash for Arc { + fn hash(&self, state: &mut H) { + (**self).hash(state) + } +} + #[cfg(test)] #[allow(experimental)] mod tests { diff --git a/src/liballoc/boxed.rs b/src/liballoc/boxed.rs index d46f18abf97..adca8b9cc4c 100644 --- a/src/liballoc/boxed.rs +++ b/src/liballoc/boxed.rs @@ -106,12 +106,20 @@ impl Ord for Box { #[stable]} impl Eq for Box {} +#[cfg(stage0)] impl> Hash for Box { #[inline] fn hash(&self, state: &mut S) { (**self).hash(state); } } +#[cfg(not(stage0))] +impl> Hash for Box { + #[inline] + fn hash(&self, state: &mut S) { + (**self).hash(state); + } +} /// Extension methods for an owning `Any` trait object. #[unstable = "post-DST and coherence changes, this will not be a trait but \ diff --git a/src/liballoc/rc.rs b/src/liballoc/rc.rs index 67b25427710..83eff71e2b8 100644 --- a/src/liballoc/rc.rs +++ b/src/liballoc/rc.rs @@ -10,23 +10,26 @@ //! Thread-local reference-counted boxes (the `Rc` type). //! -//! The `Rc` type provides shared ownership of an immutable value. Destruction is deterministic, -//! and will occur as soon as the last owner is gone. It is marked as non-sendable because it -//! avoids the overhead of atomic reference counting. +//! The `Rc` type provides shared ownership of an immutable value. +//! Destruction is deterministic, and will occur as soon as the last owner is +//! gone. It is marked as non-sendable because it avoids the overhead of atomic +//! reference counting. //! -//! The `downgrade` method can be used to create a non-owning `Weak` pointer to the box. A -//! `Weak` pointer can be upgraded to an `Rc` pointer, but will return `None` if the value -//! has already been dropped. +//! The `downgrade` method can be used to create a non-owning `Weak` pointer +//! to the box. A `Weak` pointer can be upgraded to an `Rc` pointer, but +//! will return `None` if the value has already been dropped. //! -//! For example, a tree with parent pointers can be represented by putting the nodes behind strong -//! `Rc` pointers, and then storing the parent pointers as `Weak` pointers. +//! For example, a tree with parent pointers can be represented by putting the +//! nodes behind strong `Rc` pointers, and then storing the parent pointers +//! as `Weak` pointers. //! //! # Examples //! -//! Consider a scenario where a set of `Gadget`s are owned by a given `Owner`. We want to have our -//! `Gadget`s point to their `Owner`. We can't do this with unique ownership, because more than one -//! gadget may belong to the same `Owner`. `Rc` allows us to share an `Owner` between multiple -//! `Gadget`s, and have the `Owner` remain allocated as long as any `Gadget` points at it. +//! Consider a scenario where a set of `Gadget`s are owned by a given `Owner`. +//! We want to have our `Gadget`s point to their `Owner`. We can't do this with +//! unique ownership, because more than one gadget may belong to the same +//! `Owner`. `Rc` allows us to share an `Owner` between multiple `Gadget`s, +//! and have the `Owner` remain allocated as long as any `Gadget` points at it. //! //! ```rust //! use std::rc::Rc; @@ -597,12 +600,20 @@ impl Ord for Rc { } // FIXME (#18248) Make `T` `Sized?` +#[cfg(stage0)] impl> Hash for Rc { #[inline] fn hash(&self, state: &mut S) { (**self).hash(state); } } +#[cfg(not(stage0))] +impl> Hash for Rc { + #[inline] + fn hash(&self, state: &mut S) { + (**self).hash(state); + } +} #[experimental = "Show is experimental."] impl fmt::Show for Rc { -- cgit 1.4.1-3-g733a5