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 //! # #![feature(hash)]
  20 //! use std::hash::{hash, Hash, SipHasher};
  21 //!
  22 //! #[derive(Hash)]
  23 //! struct Person {
  24 //!     id: u32,
  25 //!     name: String,
  26 //!     phone: u64,
  27 //! }
  28 //!
  29 //! let person1 = Person { id: 5, name: "Janet".to_string(), phone: 555_666_7777 };
  30 //! let person2 = Person { id: 5, name: "Bob".to_string(), phone: 555_666_7777 };
  31 //!
  32 //! assert!(hash::<_, SipHasher>(&person1) != hash::<_, SipHasher>(&person2));
  33 //! ```
  34 //!
  35 //! If you need more control over how a value is hashed, you need to implement
  36 //! the trait `Hash`:
  37 //!
  38 //! ```rust
  39 //! # #![feature(hash)]
  40 //! use std::hash::{hash, Hash, Hasher, SipHasher};
  41 //!
  42 //! struct Person {
  43 //!     id: u32,
  44 //!     name: String,
  45 //!     phone: u64,
  46 //! }
  47 //!
  48 //! impl Hash for Person {
  49 //!     fn hash<H: Hasher>(&self, state: &mut H) {
  50 //!         self.id.hash(state);
  51 //!         self.phone.hash(state);
  52 //!     }
  53 //! }
  54 //!
  55 //! let person1 = Person { id: 5, name: "Janet".to_string(), phone: 555_666_7777 };
  56 //! let person2 = Person { id: 5, name: "Bob".to_string(), phone: 555_666_7777 };
  57 //!
  58 //! assert_eq!(hash::<_, SipHasher>(&person1), hash::<_, SipHasher>(&person2));
  59 //! ```
  60
  61 #![stable(feature = "rust1", since = "1.0.0")]
  62
  63 use prelude::*;
  64
  65 use default::Default;
  66 use mem;
  67
  68 pub use self::sip::SipHasher;
  69
  70 mod sip;
  71
  72 /// A hashable type.
  73 ///
  74 /// The `H` type parameter is an abstract hash state that is used by the `Hash`
  75 /// to compute the hash.
  76 #[stable(feature = "rust1", since = "1.0.0")]
  77 pub trait Hash {
  78     /// Feeds this value into the state given, updating the hasher as necessary.
  79     #[stable(feature = "rust1", since = "1.0.0")]
  80     fn hash<H: Hasher>(&self, state: &mut H);
  81
  82     /// Feeds a slice of this type into the state provided.
  83     #[unstable(feature = "hash", reason = "module was recently redesigned")]
  84     fn hash_slice<H: Hasher>(data: &[Self], state: &mut H) where Self: Sized {
  85         for piece in data {
  86             piece.hash(state);
  87         }
  88     }
  89 }
  90
  91 /// A trait which represents the ability to hash an arbitrary stream of bytes.
  92 #[stable(feature = "rust1", since = "1.0.0")]
  93 pub trait Hasher {
  94     /// Completes a round of hashing, producing the output hash generated.
  95     #[stable(feature = "rust1", since = "1.0.0")]
  96     fn finish(&self) -> u64;
  97
  98     /// Writes some data into this `Hasher`
  99     #[stable(feature = "rust1", since = "1.0.0")]
 100     fn write(&mut self, bytes: &[u8]);
 101
 102     /// Write a single `u8` into this hasher
 103     #[inline]
 104     #[unstable(feature = "hash", reason = "module was recently redesigned")]
 105     fn write_u8(&mut self, i: u8) { self.write(&[i]) }
 106     /// Write a single `u16` into this hasher.
 107     #[inline]
 108     #[unstable(feature = "hash", reason = "module was recently redesigned")]
 109     fn write_u16(&mut self, i: u16) {
 110         self.write(&unsafe { mem::transmute::<_, [u8; 2]>(i) })
 111     }
 112     /// Write a single `u32` into this hasher.
 113     #[inline]
 114     #[unstable(feature = "hash", reason = "module was recently redesigned")]
 115     fn write_u32(&mut self, i: u32) {
 116         self.write(&unsafe { mem::transmute::<_, [u8; 4]>(i) })
 117     }
 118     /// Write a single `u64` into this hasher.
 119     #[inline]
 120     #[unstable(feature = "hash", reason = "module was recently redesigned")]
 121     fn write_u64(&mut self, i: u64) {
 122         self.write(&unsafe { mem::transmute::<_, [u8; 8]>(i) })
 123     }
 124     /// Write a single `usize` into this hasher.
 125     #[inline]
 126     #[unstable(feature = "hash", reason = "module was recently redesigned")]
 127     fn write_usize(&mut self, i: usize) {
 128         if cfg!(target_pointer_width = "32") {
 129             self.write_u32(i as u32)
 130         } else {
 131             self.write_u64(i as u64)
 132         }
 133     }
 134
 135     /// Write a single `i8` into this hasher.
 136     #[inline]
 137     #[unstable(feature = "hash", reason = "module was recently redesigned")]
 138     fn write_i8(&mut self, i: i8) { self.write_u8(i as u8) }
 139     /// Write a single `i16` into this hasher.
 140     #[inline]
 141     #[unstable(feature = "hash", reason = "module was recently redesigned")]
 142     fn write_i16(&mut self, i: i16) { self.write_u16(i as u16) }
 143     /// Write a single `i32` into this hasher.
 144     #[inline]
 145     #[unstable(feature = "hash", reason = "module was recently redesigned")]
 146     fn write_i32(&mut self, i: i32) { self.write_u32(i as u32) }
 147     /// Write a single `i64` into this hasher.
 148     #[inline]
 149     #[unstable(feature = "hash", reason = "module was recently redesigned")]
 150     fn write_i64(&mut self, i: i64) { self.write_u64(i as u64) }
 151     /// Write a single `isize` into this hasher.
 152     #[inline]
 153     #[unstable(feature = "hash", reason = "module was recently redesigned")]
 154     fn write_isize(&mut self, i: isize) { self.write_usize(i as usize) }
 155 }
 156
 157 /// Hash a value with the default SipHasher algorithm (two initial keys of 0).
 158 ///
 159 /// The specified value will be hashed with this hasher and then the resulting
 160 /// hash will be returned.
 161 #[unstable(feature = "hash", reason = "module was recently redesigned")]
 162 pub fn hash<T: Hash, H: Hasher + Default>(value: &T) -> u64 {
 163     let mut h: H = Default::default();
 164     value.hash(&mut h);
 165     h.finish()
 166 }
 167
 168 //////////////////////////////////////////////////////////////////////////////
 169
 170 mod impls {
 171     use prelude::*;
 172
 173     use slice;
 174     use super::*;
 175
 176     macro_rules! impl_write {
 177         ($(($ty:ident, $meth:ident),)*) => {$(
 178             #[stable(feature = "rust1", since = "1.0.0")]
 179             impl Hash for $ty {
 180                 fn hash<H: Hasher>(&self, state: &mut H) {
 181                     state.$meth(*self)
 182                 }
 183
 184                 fn hash_slice<H: Hasher>(data: &[$ty], state: &mut H) {
 185                     // FIXME(#23542) Replace with type ascription.
 186                     #![allow(trivial_casts)]
 187                     let newlen = data.len() * ::$ty::BYTES as usize;
 188                     let ptr = data.as_ptr() as *const u8;
 189                     state.write(unsafe { slice::from_raw_parts(ptr, newlen) })
 190                 }
 191             }
 192         )*}
 193     }
 194
 195     impl_write! {
 196         (u8, write_u8),
 197         (u16, write_u16),
 198         (u32, write_u32),
 199         (u64, write_u64),
 200         (usize, write_usize),
 201         (i8, write_i8),
 202         (i16, write_i16),
 203         (i32, write_i32),
 204         (i64, write_i64),
 205         (isize, write_isize),
 206     }
 207
 208     #[stable(feature = "rust1", since = "1.0.0")]
 209     impl Hash for bool {
 210         fn hash<H: Hasher>(&self, state: &mut H) {
 211             state.write_u8(*self as u8)
 212         }
 213     }
 214
 215     #[stable(feature = "rust1", since = "1.0.0")]
 216     impl Hash for char {
 217         fn hash<H: Hasher>(&self, state: &mut H) {
 218             state.write_u32(*self as u32)
 219         }
 220     }
 221
 222     #[stable(feature = "rust1", since = "1.0.0")]
 223     impl Hash for str {
 224         fn hash<H: Hasher>(&self, state: &mut H) {
 225             state.write(self.as_bytes());
 226             state.write_u8(0xff)
 227         }
 228     }
 229
 230     macro_rules! impl_hash_tuple {
 231         () => (
 232             #[stable(feature = "rust1", since = "1.0.0")]
 233             impl Hash for () {
 234                 fn hash<H: Hasher>(&self, _state: &mut H) {}
 235             }
 236         );
 237
 238         ( $($name:ident)+) => (
 239             #[stable(feature = "rust1", since = "1.0.0")]
 240             impl<$($name: Hash),*> Hash for ($($name,)*) {
 241                 #[allow(non_snake_case)]
 242                 fn hash<S: Hasher>(&self, state: &mut S) {
 243                     let ($(ref $name,)*) = *self;
 244                     $($name.hash(state);)*
 245                 }
 246             }
 247         );
 248     }
 249
 250     impl_hash_tuple! {}
 251     impl_hash_tuple! { A }
 252     impl_hash_tuple! { A B }
 253     impl_hash_tuple! { A B C }
 254     impl_hash_tuple! { A B C D }
 255     impl_hash_tuple! { A B C D E }
 256     impl_hash_tuple! { A B C D E F }
 257     impl_hash_tuple! { A B C D E F G }
 258     impl_hash_tuple! { A B C D E F G H }
 259     impl_hash_tuple! { A B C D E F G H I }
 260     impl_hash_tuple! { A B C D E F G H I J }
 261     impl_hash_tuple! { A B C D E F G H I J K }
 262     impl_hash_tuple! { A B C D E F G H I J K L }
 263
 264     #[stable(feature = "rust1", since = "1.0.0")]
 265     impl<T: Hash> Hash for [T] {
 266         fn hash<H: Hasher>(&self, state: &mut H) {
 267             self.len().hash(state);
 268             Hash::hash_slice(self, state)
 269         }
 270     }
 271
 272
 273     #[stable(feature = "rust1", since = "1.0.0")]
 274     impl<'a, T: ?Sized + Hash> Hash for &'a T {
 275         fn hash<H: Hasher>(&self, state: &mut H) {
 276             (**self).hash(state);
 277         }
 278     }
 279
 280     #[stable(feature = "rust1", since = "1.0.0")]
 281     impl<'a, T: ?Sized + Hash> Hash for &'a mut T {
 282         fn hash<H: Hasher>(&self, state: &mut H) {
 283             (**self).hash(state);
 284         }
 285     }
 286
 287     #[stable(feature = "rust1", since = "1.0.0")]
 288     impl<T> Hash for *const T {
 289         fn hash<H: Hasher>(&self, state: &mut H) {
 290             state.write_usize(*self as usize)
 291         }
 292     }
 293
 294     #[stable(feature = "rust1", since = "1.0.0")]
 295     impl<T> Hash for *mut T {
 296         fn hash<H: Hasher>(&self, state: &mut H) {
 297             state.write_usize(*self as usize)
 298         }
 299     }
 300 }