src/libcore/hash/mod.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Generic hashing support.
  12 //!
  13 //! This module provides a generic way to compute the hash of a value. The
  14 //! simplest way to make a type hashable is to use `#[derive(Hash)]`:
  15 //!
  16 //! # Examples
  17 //!
  18 //! ```rust
  19 //! use std::hash::{hash, Hash, SipHasher};
  20 //!
  21 //! #[derive(Hash)]
  22 //! struct Person {
  23 //!     id: uint,
  24 //!     name: String,
  25 //!     phone: u64,
  26 //! }
  27 //!
  28 //! let person1 = Person { id: 5, name: "Janet".to_string(), phone: 555_666_7777 };
  29 //! let person2 = Person { id: 5, name: "Bob".to_string(), phone: 555_666_7777 };
  30 //!
  31 //! assert!(hash::<_, SipHasher>(&person1) != hash::<_, SipHasher>(&person2));
  32 //! ```
  33 //!
  34 //! If you need more control over how a value is hashed, you need to implement
  35 //! the trait `Hash`:
  36 //!
  37 //! ```rust
  38 //! use std::hash::{hash, Hash, Hasher, Writer, SipHasher};
  39 //!
  40 //! struct Person {
  41 //!     id: uint,
  42 //!     name: String,
  43 //!     phone: u64,
  44 //! }
  45 //!
  46 //! impl<H: Hasher + Writer> Hash<H> for Person {
  47 //!     fn hash(&self, state: &mut H) {
  48 //!         self.id.hash(state);
  49 //!         self.phone.hash(state);
  50 //!     }
  51 //! }
  52 //!
  53 //! let person1 = Person { id: 5, name: "Janet".to_string(), phone: 555_666_7777 };
  54 //! let person2 = Person { id: 5, name: "Bob".to_string(), phone: 555_666_7777 };
  55 //!
  56 //! assert_eq!(hash::<_, SipHasher>(&person1), hash::<_, SipHasher>(&person2));
  57 //! ```
  58
  59 #![unstable(feature = "hash",
  60             reason = "module was recently redesigned")]
  61
  62 use prelude::*;
  63
  64 use borrow::{Cow, ToOwned};
  65 use default::Default;
  66 use mem;
  67 use num::Int;
  68
  69 pub use self::sip::SipHasher;
  70
  71 mod sip;
  72
  73 /// A hashable type.
  74 ///
  75 /// The `H` type parameter is an abstract hash state that is used by the `Hash`
  76 /// to compute the hash. Specific implementations of this trait may specialize
  77 /// for particular instances of `H` in order to be able to optimize the hashing
  78 /// behavior.
  79 pub trait Hash<H: Hasher> {
  80     /// Feeds this value into the state given, updating the hasher as necessary.
  81     fn hash(&self, state: &mut H);
  82 }
  83
  84 /// A trait which represents the ability to hash an arbitrary stream of bytes.
  85 pub trait Hasher {
  86     /// Result type of one run of hashing generated by this hasher.
  87     type Output;
  88
  89     /// Resets this hasher back to its initial state (as if it were just
  90     /// created).
  91     fn reset(&mut self);
  92
  93     /// Completes a round of hashing, producing the output hash generated.
  94     fn finish(&self) -> Self::Output;
  95 }
  96
  97 /// A common bound on the `Hasher` parameter to `Hash` implementations in order
  98 /// to generically hash an aggregate.
  99 #[unstable(feature = "hash",
 100            reason = "this trait will likely be replaced by io::Writer")]
 101 #[allow(missing_docs)]
 102 pub trait Writer {
 103     fn write(&mut self, bytes: &[u8]);
 104 }
 105
 106 /// Hash a value with the default SipHasher algorithm (two initial keys of 0).
 107 ///
 108 /// The specified value will be hashed with this hasher and then the resulting
 109 /// hash will be returned.
 110 pub fn hash<T: Hash<H>, H: Hasher + Default>(value: &T) -> H::Output {
 111     let mut h: H = Default::default();
 112     value.hash(&mut h);
 113     h.finish()
 114 }
 115
 116 //////////////////////////////////////////////////////////////////////////////
 117
 118 macro_rules! impl_hash {
 119     ($ty:ident, $uty:ident) => {
 120         impl<S: Writer + Hasher> Hash<S> for $ty {
 121             #[inline]
 122             fn hash(&self, state: &mut S) {
 123                 let a: [u8; ::$ty::BYTES] = unsafe {
 124                     mem::transmute((*self as $uty).to_le() as $ty)
 125                 };
 126                 state.write(&a)
 127             }
 128         }
 129     }
 130 }
 131
 132 impl_hash! { u8, u8 }
 133 impl_hash! { u16, u16 }
 134 impl_hash! { u32, u32 }
 135 impl_hash! { u64, u64 }
 136 impl_hash! { uint, uint }
 137 impl_hash! { i8, u8 }
 138 impl_hash! { i16, u16 }
 139 impl_hash! { i32, u32 }
 140 impl_hash! { i64, u64 }
 141 impl_hash! { int, uint }
 142
 143 impl<S: Writer + Hasher> Hash<S> for bool {
 144     #[inline]
 145     fn hash(&self, state: &mut S) {
 146         (*self as u8).hash(state);
 147     }
 148 }
 149
 150 impl<S: Writer + Hasher> Hash<S> for char {
 151     #[inline]
 152     fn hash(&self, state: &mut S) {
 153         (*self as u32).hash(state);
 154     }
 155 }
 156
 157 impl<S: Writer + Hasher> Hash<S> for str {
 158     #[inline]
 159     fn hash(&self, state: &mut S) {
 160         state.write(self.as_bytes());
 161         0xffu8.hash(state)
 162     }
 163 }
 164
 165 macro_rules! impl_hash_tuple {
 166     () => (
 167         impl<S: Hasher> Hash<S> for () {
 168             #[inline]
 169             fn hash(&self, _state: &mut S) {}
 170         }
 171     );
 172
 173     ( $($name:ident)+) => (
 174         impl<S: Hasher, $($name: Hash<S>),*> Hash<S> for ($($name,)*) {
 175             #[inline]
 176             #[allow(non_snake_case)]
 177             fn hash(&self, state: &mut S) {
 178                 match *self {
 179                     ($(ref $name,)*) => {
 180                         $(
 181                             $name.hash(state);
 182                         )*
 183                     }
 184                 }
 185             }
 186         }
 187     );
 188 }
 189
 190 impl_hash_tuple! {}
 191 impl_hash_tuple! { A }
 192 impl_hash_tuple! { A B }
 193 impl_hash_tuple! { A B C }
 194 impl_hash_tuple! { A B C D }
 195 impl_hash_tuple! { A B C D E }
 196 impl_hash_tuple! { A B C D E F }
 197 impl_hash_tuple! { A B C D E F G }
 198 impl_hash_tuple! { A B C D E F G H }
 199 impl_hash_tuple! { A B C D E F G H I }
 200 impl_hash_tuple! { A B C D E F G H I J }
 201 impl_hash_tuple! { A B C D E F G H I J K }
 202 impl_hash_tuple! { A B C D E F G H I J K L }
 203
 204 impl<S: Writer + Hasher, T: Hash<S>> Hash<S> for [T] {
 205     #[inline]
 206     fn hash(&self, state: &mut S) {
 207         self.len().hash(state);
 208         for elt in self {
 209             elt.hash(state);
 210         }
 211     }
 212 }
 213
 214
 215 impl<'a, S: Hasher, T: ?Sized + Hash<S>> Hash<S> for &'a T {
 216     #[inline]
 217     fn hash(&self, state: &mut S) {
 218         (**self).hash(state);
 219     }
 220 }
 221
 222 impl<'a, S: Hasher, T: ?Sized + Hash<S>> Hash<S> for &'a mut T {
 223     #[inline]
 224     fn hash(&self, state: &mut S) {
 225         (**self).hash(state);
 226     }
 227 }
 228
 229 impl<S: Writer + Hasher, T> Hash<S> for *const T {
 230     #[inline]
 231     fn hash(&self, state: &mut S) {
 232         // NB: raw-pointer Hash does _not_ dereference
 233         // to the target; it just gives you the pointer-bytes.
 234         (*self as uint).hash(state);
 235     }
 236 }
 237
 238 impl<S: Writer + Hasher, T> Hash<S> for *mut T {
 239     #[inline]
 240     fn hash(&self, state: &mut S) {
 241         // NB: raw-pointer Hash does _not_ dereference
 242         // to the target; it just gives you the pointer-bytes.
 243         (*self as uint).hash(state);
 244     }
 245 }
 246
 247 impl<'a, T, B: ?Sized, S: Hasher> Hash<S> for Cow<'a, T, B>
 248     where B: Hash<S> + ToOwned<T>
 249 {
 250     #[inline]
 251     fn hash(&self, state: &mut S) {
 252         Hash::hash(&**self, state)
 253     }
 254 }