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