src/libcollections/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 `#[deriving(Hash)]`:
  15 //!
  16 //! # Example
  17 //!
  18 //! ```rust
  19 //! use std::hash;
  20 //! use std::hash::Hash;
  21 //!
  22 //! #[deriving(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 core::prelude::*;
  65
  66 use alloc::boxed::Box;
  67 use alloc::rc::Rc;
  68 use core::borrow::{Cow, ToOwned};
  69 use core::intrinsics::TypeId;
  70 use core::mem;
  71 use core::num::Int;
  72
  73 use vec::Vec;
  74
  75 /// Reexport the `sip::hash` function as our default hasher.
  76 pub use self::sip::hash as hash;
  77
  78 pub mod sip;
  79
  80 /// A hashable type. The `S` type parameter is an abstract hash state that is
  81 /// used by the `Hash` to compute the hash. It defaults to
  82 /// `std::hash::sip::SipState`.
  83 pub trait Hash<S = sip::SipState> for Sized? {
  84     /// Computes the hash of a value.
  85     fn hash(&self, state: &mut S);
  86 }
  87
  88 /// A trait that computes a hash for a value. The main users of this trait are
  89 /// containers like `HashMap`, which need a generic way hash multiple types.
  90 pub trait Hasher<S> {
  91     /// Compute the hash of a value.
  92     fn hash<Sized? T: Hash<S>>(&self, value: &T) -> u64;
  93 }
  94
  95 pub trait Writer {
  96     fn write(&mut self, bytes: &[u8]);
  97 }
  98
  99 //////////////////////////////////////////////////////////////////////////////
 100
 101 macro_rules! impl_hash {
 102     ($ty:ident, $uty:ident) => {
 103         impl<S: Writer> Hash<S> for $ty {
 104             #[inline]
 105             fn hash(&self, state: &mut S) {
 106                 let a: [u8, ..::core::$ty::BYTES] = unsafe {
 107                     mem::transmute((*self as $uty).to_le() as $ty)
 108                 };
 109                 state.write(a.as_slice())
 110             }
 111         }
 112     }
 113 }
 114
 115 impl_hash!(u8, u8)
 116 impl_hash!(u16, u16)
 117 impl_hash!(u32, u32)
 118 impl_hash!(u64, u64)
 119 impl_hash!(uint, uint)
 120 impl_hash!(i8, u8)
 121 impl_hash!(i16, u16)
 122 impl_hash!(i32, u32)
 123 impl_hash!(i64, u64)
 124 impl_hash!(int, uint)
 125
 126 impl<S: Writer> Hash<S> for bool {
 127     #[inline]
 128     fn hash(&self, state: &mut S) {
 129         (*self as u8).hash(state);
 130     }
 131 }
 132
 133 impl<S: Writer> Hash<S> for char {
 134     #[inline]
 135     fn hash(&self, state: &mut S) {
 136         (*self as u32).hash(state);
 137     }
 138 }
 139
 140 impl<S: Writer> Hash<S> for str {
 141     #[inline]
 142     fn hash(&self, state: &mut S) {
 143         state.write(self.as_bytes());
 144         0xffu8.hash(state)
 145     }
 146 }
 147
 148 macro_rules! impl_hash_tuple(
 149     () => (
 150         impl<S: Writer> Hash<S> for () {
 151             #[inline]
 152             fn hash(&self, state: &mut S) {
 153                 state.write(&[]);
 154             }
 155         }
 156     );
 157
 158     ( $($name:ident)+) => (
 159         impl<S: Writer, $($name: Hash<S>),*> Hash<S> for ($($name,)*) {
 160             #[inline]
 161             #[allow(non_snake_case)]
 162             fn hash(&self, state: &mut S) {
 163                 match *self {
 164                     ($(ref $name,)*) => {
 165                         $(
 166                             $name.hash(state);
 167                         )*
 168                     }
 169                 }
 170             }
 171         }
 172     );
 173 )
 174
 175 impl_hash_tuple!()
 176 impl_hash_tuple!(A)
 177 impl_hash_tuple!(A B)
 178 impl_hash_tuple!(A B C)
 179 impl_hash_tuple!(A B C D)
 180 impl_hash_tuple!(A B C D E)
 181 impl_hash_tuple!(A B C D E F)
 182 impl_hash_tuple!(A B C D E F G)
 183 impl_hash_tuple!(A B C D E F G H)
 184 impl_hash_tuple!(A B C D E F G H I)
 185 impl_hash_tuple!(A B C D E F G H I J)
 186 impl_hash_tuple!(A B C D E F G H I J K)
 187 impl_hash_tuple!(A B C D E F G H I J K L)
 188
 189 impl<S: Writer, T: Hash<S>> Hash<S> for [T] {
 190     #[inline]
 191     fn hash(&self, state: &mut S) {
 192         self.len().hash(state);
 193         for elt in self.iter() {
 194             elt.hash(state);
 195         }
 196     }
 197 }
 198
 199
 200 impl<S: Writer, T: Hash<S>> Hash<S> for Vec<T> {
 201     #[inline]
 202     fn hash(&self, state: &mut S) {
 203         self.as_slice().hash(state);
 204     }
 205 }
 206
 207 impl<'a, S: Writer, Sized? T: Hash<S>> Hash<S> for &'a T {
 208     #[inline]
 209     fn hash(&self, state: &mut S) {
 210         (**self).hash(state);
 211     }
 212 }
 213
 214 impl<'a, S: Writer, Sized? T: Hash<S>> Hash<S> for &'a mut T {
 215     #[inline]
 216     fn hash(&self, state: &mut S) {
 217         (**self).hash(state);
 218     }
 219 }
 220
 221 impl<S: Writer, Sized? T: Hash<S>> Hash<S> for Box<T> {
 222     #[inline]
 223     fn hash(&self, state: &mut S) {
 224         (**self).hash(state);
 225     }
 226 }
 227
 228 // FIXME (#18248) Make `T` `Sized?`
 229 impl<S: Writer, T: Hash<S>> Hash<S> for Rc<T> {
 230     #[inline]
 231     fn hash(&self, state: &mut S) {
 232         (**self).hash(state);
 233     }
 234 }
 235
 236 impl<S: Writer, T: Hash<S>> Hash<S> for Option<T> {
 237     #[inline]
 238     fn hash(&self, state: &mut S) {
 239         match *self {
 240             Some(ref x) => {
 241                 0u8.hash(state);
 242                 x.hash(state);
 243             }
 244             None => {
 245                 1u8.hash(state);
 246             }
 247         }
 248     }
 249 }
 250
 251 impl<S: Writer, T> Hash<S> for *const T {
 252     #[inline]
 253     fn hash(&self, state: &mut S) {
 254         // NB: raw-pointer Hash does _not_ dereference
 255         // to the target; it just gives you the pointer-bytes.
 256         (*self as uint).hash(state);
 257     }
 258 }
 259
 260 impl<S: Writer, T> Hash<S> for *mut T {
 261     #[inline]
 262     fn hash(&self, state: &mut S) {
 263         // NB: raw-pointer Hash does _not_ dereference
 264         // to the target; it just gives you the pointer-bytes.
 265         (*self as uint).hash(state);
 266     }
 267 }
 268
 269 impl<S: Writer> Hash<S> for TypeId {
 270     #[inline]
 271     fn hash(&self, state: &mut S) {
 272         self.hash().hash(state)
 273     }
 274 }
 275
 276 impl<S: Writer, T: Hash<S>, U: Hash<S>> Hash<S> for Result<T, U> {
 277     #[inline]
 278     fn hash(&self, state: &mut S) {
 279         match *self {
 280             Ok(ref t) => { 1u.hash(state); t.hash(state); }
 281             Err(ref t) => { 2u.hash(state); t.hash(state); }
 282         }
 283     }
 284 }
 285
 286 impl<'a, T, Sized? B, S> Hash<S> for Cow<'a, T, B> where B: Hash<S> + ToOwned<T> {
 287     #[inline]
 288     fn hash(&self, state: &mut S) {
 289         Hash::hash(&**self, state)
 290     }
 291 }
 292
 293 //////////////////////////////////////////////////////////////////////////////
 294
 295 #[cfg(test)]
 296 mod tests {
 297     use core::kinds::Sized;
 298     use std::mem;
 299
 300     use slice::SlicePrelude;
 301     use super::{Hash, Hasher, Writer};
 302
 303     struct MyWriterHasher;
 304
 305     impl Hasher<MyWriter> for MyWriterHasher {
 306         fn hash<Sized? T: Hash<MyWriter>>(&self, value: &T) -> u64 {
 307             let mut state = MyWriter { hash: 0 };
 308             value.hash(&mut state);
 309             state.hash
 310         }
 311     }
 312
 313     struct MyWriter {
 314         hash: u64,
 315     }
 316
 317     impl Writer for MyWriter {
 318         // Most things we'll just add up the bytes.
 319         fn write(&mut self, buf: &[u8]) {
 320             for byte in buf.iter() {
 321                 self.hash += *byte as u64;
 322             }
 323         }
 324     }
 325
 326     #[test]
 327     fn test_writer_hasher() {
 328         use alloc::boxed::Box;
 329
 330         let hasher = MyWriterHasher;
 331
 332         assert_eq!(hasher.hash(&()), 0);
 333
 334         assert_eq!(hasher.hash(&5u8), 5);
 335         assert_eq!(hasher.hash(&5u16), 5);
 336         assert_eq!(hasher.hash(&5u32), 5);
 337         assert_eq!(hasher.hash(&5u64), 5);
 338         assert_eq!(hasher.hash(&5u), 5);
 339
 340         assert_eq!(hasher.hash(&5i8), 5);
 341         assert_eq!(hasher.hash(&5i16), 5);
 342         assert_eq!(hasher.hash(&5i32), 5);
 343         assert_eq!(hasher.hash(&5i64), 5);
 344         assert_eq!(hasher.hash(&5i), 5);
 345
 346         assert_eq!(hasher.hash(&false), 0);
 347         assert_eq!(hasher.hash(&true), 1);
 348
 349         assert_eq!(hasher.hash(&'a'), 97);
 350
 351         let s: &str = "a";
 352         assert_eq!(hasher.hash(& s), 97 + 0xFF);
 353         // FIXME (#18283) Enable test
 354         //let s: Box<str> = box "a";
 355         //assert_eq!(hasher.hash(& s), 97 + 0xFF);
 356         let cs: &[u8] = &[1u8, 2u8, 3u8];
 357         assert_eq!(hasher.hash(& cs), 9);
 358         let cs: Box<[u8]> = box [1u8, 2u8, 3u8];
 359         assert_eq!(hasher.hash(& cs), 9);
 360
 361         // FIXME (#18248) Add tests for hashing Rc<str> and Rc<[T]>
 362
 363         unsafe {
 364             let ptr: *const int = mem::transmute(5i);
 365             assert_eq!(hasher.hash(&ptr), 5);
 366         }
 367
 368         unsafe {
 369             let ptr: *mut int = mem::transmute(5i);
 370             assert_eq!(hasher.hash(&ptr), 5);
 371         }
 372     }
 373
 374     struct Custom {
 375         hash: u64
 376     }
 377
 378     impl Hash<u64> for Custom {
 379         fn hash(&self, state: &mut u64) {
 380             *state = self.hash;
 381         }
 382     }
 383
 384     #[test]
 385     fn test_custom_state() {
 386         let custom = Custom { hash: 5 };
 387         let mut state = 0;
 388         custom.hash(&mut state);
 389         assert_eq!(state, 5);
 390     }
 391 }