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/libcoretest/hash/mod.rs | 103 ++++++++++++++++++++++++++------------------ 1 file changed, 60 insertions(+), 43 deletions(-) (limited to 'src/libcoretest') diff --git a/src/libcoretest/hash/mod.rs b/src/libcoretest/hash/mod.rs index 63bf9ec3314..63935894bf5 100644 --- a/src/libcoretest/hash/mod.rs +++ b/src/libcoretest/hash/mod.rs @@ -7,27 +7,22 @@ // , at your // option. This file may not be copied, modified, or distributed // except according to those terms. -use core::marker::Sized; -use std::mem; - -use core::slice::SliceExt; -use core::hash::{Hash, Hasher, Writer}; -struct MyWriterHasher; +use std::mem; +use std::hash::{Hash, Hasher, Writer}; +use std::default::Default; -impl Hasher for MyWriterHasher { - fn hash>(&self, value: &T) -> u64 { - let mut state = MyWriter { hash: 0 }; - value.hash(&mut state); - state.hash - } +struct MyHasher { + hash: u64, } -struct MyWriter { - hash: u64, +impl Default for MyHasher { + fn default() -> MyHasher { + MyHasher { hash: 0 } + } } -impl Writer for MyWriter { +impl Writer for MyHasher { // Most things we'll just add up the bytes. fn write(&mut self, buf: &[u8]) { for byte in buf.iter() { @@ -36,66 +31,88 @@ impl Writer for MyWriter { } } +impl Hasher for MyHasher { + type Output = u64; + fn reset(&mut self) { self.hash = 0; } + fn finish(&self) -> u64 { self.hash } +} + + #[test] fn test_writer_hasher() { - let hasher = MyWriterHasher; + fn hash>(t: &T) -> u64 { + ::std::hash::hash::<_, MyHasher>(t) + } - assert_eq!(hasher.hash(&()), 0); + assert_eq!(hash(&()), 0); - assert_eq!(hasher.hash(&5u8), 5); - assert_eq!(hasher.hash(&5u16), 5); - assert_eq!(hasher.hash(&5u32), 5); - assert_eq!(hasher.hash(&5u64), 5); - assert_eq!(hasher.hash(&5u), 5); + assert_eq!(hash(&5u8), 5); + assert_eq!(hash(&5u16), 5); + assert_eq!(hash(&5u32), 5); + assert_eq!(hash(&5u64), 5); + assert_eq!(hash(&5u), 5); - assert_eq!(hasher.hash(&5i8), 5); - assert_eq!(hasher.hash(&5i16), 5); - assert_eq!(hasher.hash(&5i32), 5); - assert_eq!(hasher.hash(&5i64), 5); - assert_eq!(hasher.hash(&5i), 5); + assert_eq!(hash(&5i8), 5); + assert_eq!(hash(&5i16), 5); + assert_eq!(hash(&5i32), 5); + assert_eq!(hash(&5i64), 5); + assert_eq!(hash(&5i), 5); - assert_eq!(hasher.hash(&false), 0); - assert_eq!(hasher.hash(&true), 1); + assert_eq!(hash(&false), 0); + assert_eq!(hash(&true), 1); - assert_eq!(hasher.hash(&'a'), 97); + assert_eq!(hash(&'a'), 97); let s: &str = "a"; - assert_eq!(hasher.hash(& s), 97 + 0xFF); + assert_eq!(hash(& s), 97 + 0xFF); // FIXME (#18283) Enable test //let s: Box = box "a"; //assert_eq!(hasher.hash(& s), 97 + 0xFF); let cs: &[u8] = &[1u8, 2u8, 3u8]; - assert_eq!(hasher.hash(& cs), 9); + assert_eq!(hash(& cs), 9); let cs: Box<[u8]> = box [1u8, 2u8, 3u8]; - assert_eq!(hasher.hash(& cs), 9); + assert_eq!(hash(& cs), 9); // FIXME (#18248) Add tests for hashing Rc and Rc<[T]> unsafe { let ptr: *const int = mem::transmute(5i); - assert_eq!(hasher.hash(&ptr), 5); + assert_eq!(hash(&ptr), 5); } unsafe { let ptr: *mut int = mem::transmute(5i); - assert_eq!(hasher.hash(&ptr), 5); + assert_eq!(hash(&ptr), 5); } } -struct Custom { - hash: u64 +struct Custom { hash: u64 } +struct CustomHasher { output: u64 } + +impl Hasher for CustomHasher { + type Output = u64; + fn reset(&mut self) { self.output = 0; } + fn finish(&self) -> u64 { self.output } +} + +impl Default for CustomHasher { + fn default() -> CustomHasher { + CustomHasher { output: 0 } + } } -impl Hash for Custom { - fn hash(&self, state: &mut u64) { - *state = self.hash; +impl Hash for Custom { + fn hash(&self, state: &mut CustomHasher) { + state.output = self.hash; } } #[test] fn test_custom_state() { + fn hash>(t: &T) -> u64 { + ::std::hash::hash::<_, CustomHasher>(t) + } + let custom = Custom { hash: 5 }; - let mut state = 0; - custom.hash(&mut state); - assert_eq!(state, 5); + assert_eq!(hash(&Custom { hash: 5 }), 5); } -- cgit 1.4.1-3-g733a5