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;
  20 //! use std::hash::Hash;
  21 //!
  22 //! #[derive(Hash)]
  23 //! struct Person {
  24 //!     id: uint,
  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::hash(&person1) != hash::hash(&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 //! use std::hash;
  40 //! use std::hash::Hash;
  41 //! use std::hash::sip::SipState;
  42 //!
  43 //! struct Person {
  44 //!     id: uint,
  45 //!     name: String,
  46 //!     phone: u64,
  47 //! }
  48 //!
  49 //! impl Hash for Person {
  50 //!     fn hash(&self, state: &mut SipState) {
  51 //!         self.id.hash(state);
  52 //!         self.phone.hash(state);
  53 //!     }
  54 //! }
  55 //!
  56 //! let person1 = Person { id: 5, name: "Janet".to_string(), phone: 555_666_7777 };
  57 //! let person2 = Person { id: 5, name: "Bob".to_string(), phone: 555_666_7777 };
  58 //!
  59 //! assert!(hash::hash(&person1) == hash::hash(&person2));
  60 //! ```
  61
  62 #![allow(unused_must_use)]
  63
  64 use prelude::*;
  65
  66 use borrow::{Cow, ToOwned};
  67 use intrinsics::TypeId;
  68 use mem;
  69 use num::Int;
  70
  71 /// Reexport the `sip::hash` function as our default hasher.
  72 pub use self::sip::hash as hash;
  73
  74 pub mod sip;
  75
  76 /// A hashable type. The `S` type parameter is an abstract hash state that is
  77 /// used by the `Hash` to compute the hash. It defaults to
  78 /// `std::hash::sip::SipState`.
  79 pub trait Hash<S = sip::SipState> for Sized? {
  80     /// Computes the hash of a value.
  81     fn hash(&self, state: &mut S);
  82 }
  83
  84 /// A trait that computes a hash for a value. The main users of this trait are
  85 /// containers like `HashMap`, which need a generic way hash multiple types.
  86 pub trait Hasher<S> {
  87     /// Compute the hash of a value.
  88     fn hash<Sized? T: Hash<S>>(&self, value: &T) -> u64;
  89 }
  90
  91 #[allow(missing_docs)]
  92 pub trait Writer {
  93     fn write(&mut self, bytes: &[u8]);
  94 }
  95
  96 //////////////////////////////////////////////////////////////////////////////
  97
  98 macro_rules! impl_hash {
  99     ($ty:ident, $uty:ident) => {
 100         impl<S: Writer> Hash<S> for $ty {
 101             #[inline]
 102             fn hash(&self, state: &mut S) {
 103                 let a: [u8; ::$ty::BYTES] = unsafe {
 104                     mem::transmute((*self as $uty).to_le() as $ty)
 105                 };
 106                 state.write(a.as_slice())
 107             }
 108         }
 109     }
 110 }
 111
 112 impl_hash! { u8, u8 }
 113 impl_hash! { u16, u16 }
 114 impl_hash! { u32, u32 }
 115 impl_hash! { u64, u64 }
 116 impl_hash! { uint, uint }
 117 impl_hash! { i8, u8 }
 118 impl_hash! { i16, u16 }
 119 impl_hash! { i32, u32 }
 120 impl_hash! { i64, u64 }
 121 impl_hash! { int, uint }
 122
 123 impl<S: Writer> Hash<S> for bool {
 124     #[inline]
 125     fn hash(&self, state: &mut S) {
 126         (*self as u8).hash(state);
 127     }
 128 }
 129
 130 impl<S: Writer> Hash<S> for char {
 131     #[inline]
 132     fn hash(&self, state: &mut S) {
 133         (*self as u32).hash(state);
 134     }
 135 }
 136
 137 impl<S: Writer> Hash<S> for str {
 138     #[inline]
 139     fn hash(&self, state: &mut S) {
 140         state.write(self.as_bytes());
 141         0xffu8.hash(state)
 142     }
 143 }
 144
 145 macro_rules! impl_hash_tuple {
 146     () => (
 147         impl<S: Writer> Hash<S> for () {
 148             #[inline]
 149             fn hash(&self, state: &mut S) {
 150                 state.write(&[]);
 151             }
 152         }
 153     );
 154
 155     ( $($name:ident)+) => (
 156         impl<S: Writer, $($name: Hash<S>),*> Hash<S> for ($($name,)*) {
 157             #[inline]
 158             #[allow(non_snake_case)]
 159             fn hash(&self, state: &mut S) {
 160                 match *self {
 161                     ($(ref $name,)*) => {
 162                         $(
 163                             $name.hash(state);
 164                         )*
 165                     }
 166                 }
 167             }
 168         }
 169     );
 170 }
 171
 172 impl_hash_tuple! {}
 173 impl_hash_tuple! { A }
 174 impl_hash_tuple! { A B }
 175 impl_hash_tuple! { A B C }
 176 impl_hash_tuple! { A B C D }
 177 impl_hash_tuple! { A B C D E }
 178 impl_hash_tuple! { A B C D E F }
 179 impl_hash_tuple! { A B C D E F G }
 180 impl_hash_tuple! { A B C D E F G H }
 181 impl_hash_tuple! { A B C D E F G H I }
 182 impl_hash_tuple! { A B C D E F G H I J }
 183 impl_hash_tuple! { A B C D E F G H I J K }
 184 impl_hash_tuple! { A B C D E F G H I J K L }
 185
 186 impl<S: Writer, T: Hash<S>> Hash<S> for [T] {
 187     #[inline]
 188     fn hash(&self, state: &mut S) {
 189         self.len().hash(state);
 190         for elt in self.iter() {
 191             elt.hash(state);
 192         }
 193     }
 194 }
 195
 196
 197 impl<'a, S: Writer, Sized? T: Hash<S>> Hash<S> for &'a T {
 198     #[inline]
 199     fn hash(&self, state: &mut S) {
 200         (**self).hash(state);
 201     }
 202 }
 203
 204 impl<'a, S: Writer, Sized? T: Hash<S>> Hash<S> for &'a mut T {
 205     #[inline]
 206     fn hash(&self, state: &mut S) {
 207         (**self).hash(state);
 208     }
 209 }
 210
 211 impl<S: Writer, T> Hash<S> for *const T {
 212     #[inline]
 213     fn hash(&self, state: &mut S) {
 214         // NB: raw-pointer Hash does _not_ dereference
 215         // to the target; it just gives you the pointer-bytes.
 216         (*self as uint).hash(state);
 217     }
 218 }
 219
 220 impl<S: Writer, T> Hash<S> for *mut T {
 221     #[inline]
 222     fn hash(&self, state: &mut S) {
 223         // NB: raw-pointer Hash does _not_ dereference
 224         // to the target; it just gives you the pointer-bytes.
 225         (*self as uint).hash(state);
 226     }
 227 }
 228
 229 impl<S: Writer> Hash<S> for TypeId {
 230     #[inline]
 231     fn hash(&self, state: &mut S) {
 232         self.hash().hash(state)
 233     }
 234 }
 235
 236 impl<'a, T, Sized? B, S> Hash<S> for Cow<'a, T, B> where B: Hash<S> + ToOwned<T> {
 237     #[inline]
 238     fn hash(&self, state: &mut S) {
 239         Hash::hash(&**self, state)
 240     }
 241 }