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