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: ~str,
  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: ~str,
  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 io::Writer;
  68 use iter::Iterator;
  69 use option::{Option, Some, None};
  70 use rc::Rc;
  71 use str::{Str, StrSlice};
  72 use slice::{Vector, ImmutableVector};
  73 use vec::Vec;
  74
  75 /// Reexport the `sip::hash` function as our default hasher.
  76 pub use hash = self::sip::hash;
  77
  78 pub mod sip;
  79
  80 /// A trait that represents a hashable type. The `S` type parameter is an
  81 /// abstract hash state that is used by the `Hash` to compute the hash.
  82 /// It defaults to `std::hash::sip::SipState`.
  83 pub trait Hash<S = sip::SipState> {
  84     /// Compute a hash of the 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 a hash of the value.
  92     fn hash<T: Hash<S>>(&self, value: &T) -> u64;
  93 }
  94
  95 //////////////////////////////////////////////////////////////////////////////
  96
  97 macro_rules! impl_hash(
  98     ( $( $ty:ty => $method:ident;)* ) => (
  99         $(
 100             impl<S: Writer> Hash<S> for $ty {
 101                 #[inline]
 102                 fn hash(&self, state: &mut S) {
 103                     state.$method(*self);
 104                 }
 105             }
 106         )*
 107     )
 108 )
 109
 110 impl_hash!(
 111     u8 => write_u8;
 112     u16 => write_le_u16;
 113     u32 => write_le_u32;
 114     u64 => write_le_u64;
 115     uint => write_le_uint;
 116     i8 => write_i8;
 117     i16 => write_le_i16;
 118     i32 => write_le_i32;
 119     i64 => write_le_i64;
 120     int => write_le_int;
 121 )
 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<'a, S: Writer> Hash<S> for &'a str {
 138     #[inline]
 139     fn hash(&self, state: &mut S) {
 140         state.write(self.as_bytes());
 141         state.write_u8(0xFF);
 142     }
 143 }
 144
 145 impl<S: Writer> Hash<S> for ~str {
 146     #[inline]
 147     fn hash(&self, state: &mut S) {
 148         self.as_slice().hash(state);
 149     }
 150 }
 151
 152 macro_rules! impl_hash_tuple(
 153     () => (
 154         impl<S: Writer> Hash<S> for () {
 155             #[inline]
 156             fn hash(&self, state: &mut S) {
 157                 state.write([]);
 158             }
 159         }
 160     );
 161
 162     ($A:ident $($B:ident)*) => (
 163         impl<
 164             S: Writer,
 165             $A: Hash<S> $(, $B: Hash<S>)*
 166         > Hash<S> for ($A, $($B),*) {
 167             #[inline]
 168             fn hash(&self, state: &mut S) {
 169                 match *self {
 170                     (ref $A, $(ref $B),*) => {
 171                         $A.hash(state);
 172                         $(
 173                             $B.hash(state);
 174                         )*
 175                     }
 176                 }
 177             }
 178         }
 179
 180         impl_hash_tuple!($($B)*)
 181     );
 182 )
 183
 184 impl_hash_tuple!(a0 a1 a2 a3 a4 a5 a6 a7)
 185
 186 impl<'a, S: Writer, T: Hash<S>> Hash<S> for &'a [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, T: Hash<S>> Hash<S> for &'a mut [T] {
 198     #[inline]
 199     fn hash(&self, state: &mut S) {
 200         self.as_slice().hash(state);
 201     }
 202 }
 203
 204 impl<S: Writer, T: Hash<S>> Hash<S> for ~[T] {
 205     #[inline]
 206     fn hash(&self, state: &mut S) {
 207         self.as_slice().hash(state);
 208     }
 209 }
 210
 211 impl<S: Writer, T: Hash<S>> Hash<S> for Vec<T> {
 212     #[inline]
 213     fn hash(&self, state: &mut S) {
 214         self.as_slice().hash(state);
 215     }
 216 }
 217
 218 impl<'a, S: Writer, T: Hash<S>> Hash<S> for &'a T {
 219     #[inline]
 220     fn hash(&self, state: &mut S) {
 221         (**self).hash(state);
 222     }
 223 }
 224
 225 impl<'a, S: Writer, T: Hash<S>> Hash<S> for &'a mut T {
 226     #[inline]
 227     fn hash(&self, state: &mut S) {
 228         (**self).hash(state);
 229     }
 230 }
 231
 232 impl<S: Writer, T: Hash<S>> Hash<S> for ~T {
 233     #[inline]
 234     fn hash(&self, state: &mut S) {
 235         (**self).hash(state);
 236     }
 237 }
 238
 239 impl<S: Writer, T: Hash<S>> Hash<S> for @T {
 240     #[inline]
 241     fn hash(&self, state: &mut S) {
 242         (**self).hash(state);
 243     }
 244 }
 245
 246 impl<S: Writer, T: Hash<S>> Hash<S> for Rc<T> {
 247     #[inline]
 248     fn hash(&self, state: &mut S) {
 249         (**self).hash(state);
 250     }
 251 }
 252
 253 impl<S: Writer, T: Hash<S>> Hash<S> for Option<T> {
 254     #[inline]
 255     fn hash(&self, state: &mut S) {
 256         match *self {
 257             Some(ref x) => {
 258                 0u8.hash(state);
 259                 x.hash(state);
 260             }
 261             None => {
 262                 1u8.hash(state);
 263             }
 264         }
 265     }
 266 }
 267
 268 impl<S: Writer, T> Hash<S> for *T {
 269     #[inline]
 270     fn hash(&self, state: &mut S) {
 271         // NB: raw-pointer Hash does _not_ dereference
 272         // to the target; it just gives you the pointer-bytes.
 273         (*self as uint).hash(state);
 274     }
 275 }
 276
 277 impl<S: Writer, T> Hash<S> for *mut T {
 278     #[inline]
 279     fn hash(&self, state: &mut S) {
 280         // NB: raw-pointer Hash does _not_ dereference
 281         // to the target; it just gives you the pointer-bytes.
 282         (*self as uint).hash(state);
 283     }
 284 }
 285
 286 //////////////////////////////////////////////////////////////////////////////
 287
 288 #[cfg(test)]
 289 mod tests {
 290     use cast;
 291     use io::{IoResult, Writer};
 292     use iter::{Iterator};
 293     use option::{Some, None};
 294     use result::Ok;
 295     use slice::ImmutableVector;
 296
 297     use super::{Hash, Hasher};
 298
 299     struct MyWriterHasher;
 300
 301     impl Hasher<MyWriter> for MyWriterHasher {
 302         fn hash<T: Hash<MyWriter>>(&self, value: &T) -> u64 {
 303             let mut state = MyWriter { hash: 0 };
 304             value.hash(&mut state);
 305             state.hash
 306         }
 307     }
 308
 309     struct MyWriter {
 310         hash: u64,
 311     }
 312
 313     impl Writer for MyWriter {
 314         // Most things we'll just add up the bytes.
 315         fn write(&mut self, buf: &[u8]) -> IoResult<()> {
 316             for byte in buf.iter() {
 317                 self.hash += *byte as u64;
 318             }
 319             Ok(())
 320         }
 321     }
 322
 323     #[test]
 324     fn test_writer_hasher() {
 325         let hasher = MyWriterHasher;
 326
 327         assert_eq!(hasher.hash(&()), 0);
 328
 329         assert_eq!(hasher.hash(&5u8), 5);
 330         assert_eq!(hasher.hash(&5u16), 5);
 331         assert_eq!(hasher.hash(&5u32), 5);
 332         assert_eq!(hasher.hash(&5u64), 5);
 333         assert_eq!(hasher.hash(&5u), 5);
 334
 335         assert_eq!(hasher.hash(&5i8), 5);
 336         assert_eq!(hasher.hash(&5i16), 5);
 337         assert_eq!(hasher.hash(&5i32), 5);
 338         assert_eq!(hasher.hash(&5i64), 5);
 339         assert_eq!(hasher.hash(&5i), 5);
 340
 341         assert_eq!(hasher.hash(&false), 0);
 342         assert_eq!(hasher.hash(&true), 1);
 343
 344         assert_eq!(hasher.hash(&'a'), 97);
 345
 346         assert_eq!(hasher.hash(& &"a"), 97 + 0xFF);
 347         assert_eq!(hasher.hash(& &[1u8, 2u8, 3u8]), 9);
 348
 349         unsafe {
 350             let ptr: *int = cast::transmute(5);
 351             assert_eq!(hasher.hash(&ptr), 5);
 352         }
 353
 354         unsafe {
 355             let ptr: *mut int = cast::transmute(5);
 356             assert_eq!(hasher.hash(&ptr), 5);
 357         }
 358     }
 359
 360     struct Custom {
 361         hash: u64
 362     }
 363
 364     impl Hash<u64> for Custom {
 365         fn hash(&self, state: &mut u64) {
 366             *state = self.hash;
 367         }
 368     }
 369
 370     #[test]
 371     fn test_custom_state() {
 372         let custom = Custom { hash: 5 };
 373         let mut state = 0;
 374         custom.hash(&mut state);
 375         assert_eq!(state, 5);
 376     }
 377 }