src/libstd/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 /*!
  12  * Generic hashing support.
  13  *
  14  * This module provides a generic way to compute the hash of a value. The
  15  * simplest way to make a type hashable is to use `#[deriving(Hash)]`:
  16  *
  17  * # Example
  18  *
  19  * ```rust
  20  * use std::hash;
  21  * use std::hash::Hash;
  22  *
  23  * #[deriving(Hash)]
  24  * struct Person {
  25  *     id: uint,
  26  *     name: String,
  27  *     phone: u64,
  28  * }
  29  *
  30  * let person1 = Person { id: 5, name: "Janet".to_owned(), phone: 555_666_7777 };
  31  * let person2 = Person { id: 5, name: "Bob".to_owned(), phone: 555_666_7777 };
  32  *
  33  * assert!(hash::hash(&person1) != hash::hash(&person2));
  34  * ```
  35  *
  36  * If you need more control over how a value is hashed, you need to implement
  37  * the trait `Hash`:
  38  *
  39  * ```rust
  40  * use std::hash;
  41  * use std::hash::Hash;
  42  * use std::hash::sip::SipState;
  43  *
  44  * struct Person {
  45  *     id: uint,
  46  *     name: String,
  47  *     phone: u64,
  48  * }
  49  *
  50  * impl Hash for Person {
  51  *     fn hash(&self, state: &mut SipState) {
  52  *         self.id.hash(state);
  53  *         self.phone.hash(state);
  54  *     }
  55  * }
  56  *
  57  * let person1 = Person { id: 5, name: "Janet".to_owned(), phone: 555_666_7777 };
  58  * let person2 = Person { id: 5, name: "Bob".to_owned(), phone: 555_666_7777 };
  59  *
  60  * assert!(hash::hash(&person1) == hash::hash(&person2));
  61  * ```
  62  */
  63
  64 #![allow(unused_must_use)]
  65
  66 use container::Container;
  67 use intrinsics::TypeId;
  68 use iter::Iterator;
  69 use option::{Option, Some, None};
  70 use owned::Box;
  71 use rc::Rc;
  72 use result::{Result, Ok, Err};
  73 use slice::{Vector, ImmutableVector};
  74 use str::{Str, StrSlice};
  75 use vec::Vec;
  76
  77 /// Reexport the `sip::hash` function as our default hasher.
  78 pub use hash = self::sip::hash;
  79
  80 pub use Writer = io::Writer;
  81
  82 pub mod sip;
  83
  84 /// A trait that represents a hashable type. The `S` type parameter is an
  85 /// abstract hash state that is used by the `Hash` to compute the hash.
  86 /// It defaults to `std::hash::sip::SipState`.
  87 pub trait Hash<S = sip::SipState> {
  88     /// Compute a hash of the value.
  89     fn hash(&self, state: &mut S);
  90 }
  91
  92 /// A trait that computes a hash for a value. The main users of this trait are
  93 /// containers like `HashMap`, which need a generic way hash multiple types.
  94 pub trait Hasher<S> {
  95     /// Compute a hash of the value.
  96     fn hash<T: Hash<S>>(&self, value: &T) -> u64;
  97 }
  98
  99 //////////////////////////////////////////////////////////////////////////////
 100
 101 macro_rules! impl_hash(
 102     ( $( $ty:ty => $method:ident;)* ) => (
 103         $(
 104             impl<S: Writer> Hash<S> for $ty {
 105                 #[inline]
 106                 fn hash(&self, state: &mut S) {
 107                     state.$method(*self);
 108                 }
 109             }
 110         )*
 111     )
 112 )
 113
 114 impl_hash!(
 115     u8 => write_u8;
 116     u16 => write_le_u16;
 117     u32 => write_le_u32;
 118     u64 => write_le_u64;
 119     uint => write_le_uint;
 120     i8 => write_i8;
 121     i16 => write_le_i16;
 122     i32 => write_le_i32;
 123     i64 => write_le_i64;
 124     int => write_le_int;
 125 )
 126
 127 impl<S: Writer> Hash<S> for bool {
 128     #[inline]
 129     fn hash(&self, state: &mut S) {
 130         (*self as u8).hash(state);
 131     }
 132 }
 133
 134 impl<S: Writer> Hash<S> for char {
 135     #[inline]
 136     fn hash(&self, state: &mut S) {
 137         (*self as u32).hash(state);
 138     }
 139 }
 140
 141 impl<'a, S: Writer> Hash<S> for &'a str {
 142     #[inline]
 143     fn hash(&self, state: &mut S) {
 144         state.write(self.as_bytes());
 145         state.write_u8(0xFF);
 146     }
 147 }
 148
 149 macro_rules! impl_hash_tuple(
 150     () => (
 151         impl<S: Writer> Hash<S> for () {
 152             #[inline]
 153             fn hash(&self, state: &mut S) {
 154                 state.write([]);
 155             }
 156         }
 157     );
 158
 159     ($A:ident $($B:ident)*) => (
 160         impl<
 161             S: Writer,
 162             $A: Hash<S> $(, $B: Hash<S>)*
 163         > Hash<S> for ($A, $($B),*) {
 164             #[inline]
 165             fn hash(&self, state: &mut S) {
 166                 match *self {
 167                     (ref $A, $(ref $B),*) => {
 168                         $A.hash(state);
 169                         $(
 170                             $B.hash(state);
 171                         )*
 172                     }
 173                 }
 174             }
 175         }
 176
 177         impl_hash_tuple!($($B)*)
 178     );
 179 )
 180
 181 impl_hash_tuple!(a0 a1 a2 a3 a4 a5 a6 a7)
 182
 183 impl<'a, S: Writer, T: Hash<S>> Hash<S> for &'a [T] {
 184     #[inline]
 185     fn hash(&self, state: &mut S) {
 186         self.len().hash(state);
 187         for elt in self.iter() {
 188             elt.hash(state);
 189         }
 190     }
 191 }
 192
 193
 194 impl<'a, S: Writer, T: Hash<S>> Hash<S> for &'a mut [T] {
 195     #[inline]
 196     fn hash(&self, state: &mut S) {
 197         self.as_slice().hash(state);
 198     }
 199 }
 200
 201 impl<S: Writer, T: Hash<S>> Hash<S> for ~[T] {
 202     #[inline]
 203     fn hash(&self, state: &mut S) {
 204         self.as_slice().hash(state);
 205     }
 206 }
 207
 208 impl<S: Writer, T: Hash<S>> Hash<S> for Vec<T> {
 209     #[inline]
 210     fn hash(&self, state: &mut S) {
 211         self.as_slice().hash(state);
 212     }
 213 }
 214
 215 impl<'a, S: Writer, T: 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: Writer, T: 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, T: Hash<S>> Hash<S> for Box<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 @T {
 237     #[inline]
 238     fn hash(&self, state: &mut S) {
 239         (**self).hash(state);
 240     }
 241 }
 242
 243 impl<S: Writer, T: Hash<S>> Hash<S> for Rc<T> {
 244     #[inline]
 245     fn hash(&self, state: &mut S) {
 246         (**self).hash(state);
 247     }
 248 }
 249
 250 impl<S: Writer, T: Hash<S>> Hash<S> for Option<T> {
 251     #[inline]
 252     fn hash(&self, state: &mut S) {
 253         match *self {
 254             Some(ref x) => {
 255                 0u8.hash(state);
 256                 x.hash(state);
 257             }
 258             None => {
 259                 1u8.hash(state);
 260             }
 261         }
 262     }
 263 }
 264
 265 impl<S: Writer, T> Hash<S> for *T {
 266     #[inline]
 267     fn hash(&self, state: &mut S) {
 268         // NB: raw-pointer Hash does _not_ dereference
 269         // to the target; it just gives you the pointer-bytes.
 270         (*self as uint).hash(state);
 271     }
 272 }
 273
 274 impl<S: Writer, T> Hash<S> for *mut T {
 275     #[inline]
 276     fn hash(&self, state: &mut S) {
 277         // NB: raw-pointer Hash does _not_ dereference
 278         // to the target; it just gives you the pointer-bytes.
 279         (*self as uint).hash(state);
 280     }
 281 }
 282
 283 impl<S: Writer> Hash<S> for TypeId {
 284     #[inline]
 285     fn hash(&self, state: &mut S) {
 286         self.hash().hash(state)
 287     }
 288 }
 289
 290 impl<S: Writer, T: Hash<S>, U: Hash<S>> Hash<S> for Result<T, U> {
 291     #[inline]
 292     fn hash(&self, state: &mut S) {
 293         match *self {
 294             Ok(ref t) => { 1u.hash(state); t.hash(state); }
 295             Err(ref t) => { 2u.hash(state); t.hash(state); }
 296         }
 297     }
 298 }
 299
 300 //////////////////////////////////////////////////////////////////////////////
 301
 302 #[cfg(test)]
 303 mod tests {
 304     use mem;
 305     use io::{IoResult, Writer};
 306     use iter::{Iterator};
 307     use option::{Some, None};
 308     use result::Ok;
 309     use slice::ImmutableVector;
 310
 311     use super::{Hash, Hasher};
 312
 313     struct MyWriterHasher;
 314
 315     impl Hasher<MyWriter> for MyWriterHasher {
 316         fn hash<T: Hash<MyWriter>>(&self, value: &T) -> u64 {
 317             let mut state = MyWriter { hash: 0 };
 318             value.hash(&mut state);
 319             state.hash
 320         }
 321     }
 322
 323     struct MyWriter {
 324         hash: u64,
 325     }
 326
 327     impl Writer for MyWriter {
 328         // Most things we'll just add up the bytes.
 329         fn write(&mut self, buf: &[u8]) -> IoResult<()> {
 330             for byte in buf.iter() {
 331                 self.hash += *byte as u64;
 332             }
 333             Ok(())
 334         }
 335     }
 336
 337     #[test]
 338     fn test_writer_hasher() {
 339         let hasher = MyWriterHasher;
 340
 341         assert_eq!(hasher.hash(&()), 0);
 342
 343         assert_eq!(hasher.hash(&5u8), 5);
 344         assert_eq!(hasher.hash(&5u16), 5);
 345         assert_eq!(hasher.hash(&5u32), 5);
 346         assert_eq!(hasher.hash(&5u64), 5);
 347         assert_eq!(hasher.hash(&5u), 5);
 348
 349         assert_eq!(hasher.hash(&5i8), 5);
 350         assert_eq!(hasher.hash(&5i16), 5);
 351         assert_eq!(hasher.hash(&5i32), 5);
 352         assert_eq!(hasher.hash(&5i64), 5);
 353         assert_eq!(hasher.hash(&5i), 5);
 354
 355         assert_eq!(hasher.hash(&false), 0);
 356         assert_eq!(hasher.hash(&true), 1);
 357
 358         assert_eq!(hasher.hash(&'a'), 97);
 359
 360         assert_eq!(hasher.hash(&("a")), 97 + 0xFF);
 361         assert_eq!(hasher.hash(& &[1u8, 2u8, 3u8]), 9);
 362
 363         unsafe {
 364             let ptr: *int = mem::transmute(5);
 365             assert_eq!(hasher.hash(&ptr), 5);
 366         }
 367
 368         unsafe {
 369             let ptr: *mut int = mem::transmute(5);
 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 }