]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
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 | |
c1a9b12d SL |
19 | //! #![feature(hash_default)] |
20 | //! | |
1a4d82fc JJ |
21 | //! use std::hash::{hash, Hash, SipHasher}; |
22 | //! | |
23 | //! #[derive(Hash)] | |
24 | //! struct Person { | |
c34b1796 | 25 | //! id: u32, |
1a4d82fc JJ |
26 | //! name: String, |
27 | //! phone: u64, | |
28 | //! } | |
29 | //! | |
30 | //! let person1 = Person { id: 5, name: "Janet".to_string(), phone: 555_666_7777 }; | |
31 | //! let person2 = Person { id: 5, name: "Bob".to_string(), phone: 555_666_7777 }; | |
32 | //! | |
33 | //! assert!(hash::<_, SipHasher>(&person1) != hash::<_, SipHasher>(&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 | |
c1a9b12d SL |
40 | //! #![feature(hash_default)] |
41 | //! | |
85aaf69f | 42 | //! use std::hash::{hash, Hash, Hasher, SipHasher}; |
1a4d82fc JJ |
43 | //! |
44 | //! struct Person { | |
c34b1796 | 45 | //! id: u32, |
1a4d82fc JJ |
46 | //! name: String, |
47 | //! phone: u64, | |
48 | //! } | |
49 | //! | |
85aaf69f SL |
50 | //! impl Hash for Person { |
51 | //! fn hash<H: Hasher>(&self, state: &mut H) { | |
1a4d82fc JJ |
52 | //! self.id.hash(state); |
53 | //! self.phone.hash(state); | |
54 | //! } | |
55 | //! } | |
56 | //! | |
57 | //! let person1 = Person { id: 5, name: "Janet".to_string(), phone: 555_666_7777 }; | |
58 | //! let person2 = Person { id: 5, name: "Bob".to_string(), phone: 555_666_7777 }; | |
59 | //! | |
60 | //! assert_eq!(hash::<_, SipHasher>(&person1), hash::<_, SipHasher>(&person2)); | |
61 | //! ``` | |
62 | ||
85aaf69f SL |
63 | #![stable(feature = "rust1", since = "1.0.0")] |
64 | ||
65 | use prelude::*; | |
1a4d82fc | 66 | |
85aaf69f | 67 | use mem; |
1a4d82fc JJ |
68 | |
69 | pub use self::sip::SipHasher; | |
70 | ||
71 | mod sip; | |
72 | ||
73 | /// A hashable type. | |
74 | /// | |
75 | /// The `H` type parameter is an abstract hash state that is used by the `Hash` | |
c34b1796 AL |
76 | /// to compute the hash. |
77 | /// | |
78 | /// If you are also implementing `Eq`, there is an additional property that | |
79 | /// is important: | |
80 | /// | |
81 | /// ```text | |
82 | /// k1 == k2 -> hash(k1) == hash(k2) | |
83 | /// ``` | |
84 | /// | |
85 | /// In other words, if two keys are equal, their hashes should also be equal. | |
86 | /// `HashMap` and `HashSet` both rely on this behavior. | |
85aaf69f SL |
87 | #[stable(feature = "rust1", since = "1.0.0")] |
88 | pub trait Hash { | |
1a4d82fc | 89 | /// Feeds this value into the state given, updating the hasher as necessary. |
85aaf69f SL |
90 | #[stable(feature = "rust1", since = "1.0.0")] |
91 | fn hash<H: Hasher>(&self, state: &mut H); | |
92 | ||
93 | /// Feeds a slice of this type into the state provided. | |
c1a9b12d | 94 | #[stable(feature = "hash_slice", since = "1.3.0")] |
85aaf69f SL |
95 | fn hash_slice<H: Hasher>(data: &[Self], state: &mut H) where Self: Sized { |
96 | for piece in data { | |
97 | piece.hash(state); | |
98 | } | |
99 | } | |
1a4d82fc JJ |
100 | } |
101 | ||
1a4d82fc | 102 | /// A trait which represents the ability to hash an arbitrary stream of bytes. |
85aaf69f | 103 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 104 | pub trait Hasher { |
85aaf69f | 105 | /// Completes a round of hashing, producing the output hash generated. |
c34b1796 | 106 | #[stable(feature = "rust1", since = "1.0.0")] |
85aaf69f SL |
107 | fn finish(&self) -> u64; |
108 | ||
109 | /// Writes some data into this `Hasher` | |
85aaf69f SL |
110 | #[stable(feature = "rust1", since = "1.0.0")] |
111 | fn write(&mut self, bytes: &[u8]); | |
112 | ||
113 | /// Write a single `u8` into this hasher | |
85aaf69f | 114 | #[inline] |
c1a9b12d | 115 | #[stable(feature = "hasher_write", since = "1.3.0")] |
85aaf69f SL |
116 | fn write_u8(&mut self, i: u8) { self.write(&[i]) } |
117 | /// Write a single `u16` into this hasher. | |
85aaf69f | 118 | #[inline] |
c1a9b12d | 119 | #[stable(feature = "hasher_write", since = "1.3.0")] |
85aaf69f SL |
120 | fn write_u16(&mut self, i: u16) { |
121 | self.write(&unsafe { mem::transmute::<_, [u8; 2]>(i) }) | |
122 | } | |
123 | /// Write a single `u32` into this hasher. | |
85aaf69f | 124 | #[inline] |
c1a9b12d | 125 | #[stable(feature = "hasher_write", since = "1.3.0")] |
85aaf69f SL |
126 | fn write_u32(&mut self, i: u32) { |
127 | self.write(&unsafe { mem::transmute::<_, [u8; 4]>(i) }) | |
128 | } | |
129 | /// Write a single `u64` into this hasher. | |
85aaf69f | 130 | #[inline] |
c1a9b12d | 131 | #[stable(feature = "hasher_write", since = "1.3.0")] |
85aaf69f SL |
132 | fn write_u64(&mut self, i: u64) { |
133 | self.write(&unsafe { mem::transmute::<_, [u8; 8]>(i) }) | |
134 | } | |
135 | /// Write a single `usize` into this hasher. | |
85aaf69f | 136 | #[inline] |
c1a9b12d | 137 | #[stable(feature = "hasher_write", since = "1.3.0")] |
85aaf69f SL |
138 | fn write_usize(&mut self, i: usize) { |
139 | if cfg!(target_pointer_width = "32") { | |
140 | self.write_u32(i as u32) | |
141 | } else { | |
142 | self.write_u64(i as u64) | |
143 | } | |
144 | } | |
145 | ||
146 | /// Write a single `i8` into this hasher. | |
85aaf69f | 147 | #[inline] |
c1a9b12d | 148 | #[stable(feature = "hasher_write", since = "1.3.0")] |
85aaf69f SL |
149 | fn write_i8(&mut self, i: i8) { self.write_u8(i as u8) } |
150 | /// Write a single `i16` into this hasher. | |
85aaf69f | 151 | #[inline] |
c1a9b12d | 152 | #[stable(feature = "hasher_write", since = "1.3.0")] |
85aaf69f SL |
153 | fn write_i16(&mut self, i: i16) { self.write_u16(i as u16) } |
154 | /// Write a single `i32` into this hasher. | |
85aaf69f | 155 | #[inline] |
c1a9b12d | 156 | #[stable(feature = "hasher_write", since = "1.3.0")] |
85aaf69f SL |
157 | fn write_i32(&mut self, i: i32) { self.write_u32(i as u32) } |
158 | /// Write a single `i64` into this hasher. | |
85aaf69f | 159 | #[inline] |
c1a9b12d | 160 | #[stable(feature = "hasher_write", since = "1.3.0")] |
85aaf69f SL |
161 | fn write_i64(&mut self, i: i64) { self.write_u64(i as u64) } |
162 | /// Write a single `isize` into this hasher. | |
85aaf69f | 163 | #[inline] |
c1a9b12d | 164 | #[stable(feature = "hasher_write", since = "1.3.0")] |
85aaf69f | 165 | fn write_isize(&mut self, i: isize) { self.write_usize(i as usize) } |
1a4d82fc JJ |
166 | } |
167 | ||
1a4d82fc JJ |
168 | /// Hash a value with the default SipHasher algorithm (two initial keys of 0). |
169 | /// | |
170 | /// The specified value will be hashed with this hasher and then the resulting | |
171 | /// hash will be returned. | |
62682a34 SL |
172 | #[unstable(feature = "hash_default", |
173 | reason = "not the most ergonomic interface unless `H` is defaulted \ | |
174 | to SipHasher, but perhaps not ready to commit to that")] | |
c1a9b12d SL |
175 | #[deprecated(since = "1.3.0", |
176 | reason = "has yet to prove itself useful")] | |
85aaf69f SL |
177 | pub fn hash<T: Hash, H: Hasher + Default>(value: &T) -> u64 { |
178 | let mut h: H = Default::default(); | |
179 | value.hash(&mut h); | |
180 | h.finish() | |
181 | } | |
182 | ||
1a4d82fc JJ |
183 | ////////////////////////////////////////////////////////////////////////////// |
184 | ||
1a4d82fc JJ |
185 | mod impls { |
186 | use prelude::*; | |
187 | ||
85aaf69f SL |
188 | use slice; |
189 | use super::*; | |
1a4d82fc | 190 | |
85aaf69f SL |
191 | macro_rules! impl_write { |
192 | ($(($ty:ident, $meth:ident),)*) => {$( | |
193 | #[stable(feature = "rust1", since = "1.0.0")] | |
194 | impl Hash for $ty { | |
195 | fn hash<H: Hasher>(&self, state: &mut H) { | |
196 | state.$meth(*self) | |
197 | } | |
198 | ||
199 | fn hash_slice<H: Hasher>(data: &[$ty], state: &mut H) { | |
c34b1796 AL |
200 | // FIXME(#23542) Replace with type ascription. |
201 | #![allow(trivial_casts)] | |
9346a6ac | 202 | let newlen = data.len() * ::$ty::BYTES; |
85aaf69f SL |
203 | let ptr = data.as_ptr() as *const u8; |
204 | state.write(unsafe { slice::from_raw_parts(ptr, newlen) }) | |
1a4d82fc JJ |
205 | } |
206 | } | |
85aaf69f | 207 | )*} |
1a4d82fc JJ |
208 | } |
209 | ||
85aaf69f SL |
210 | impl_write! { |
211 | (u8, write_u8), | |
212 | (u16, write_u16), | |
213 | (u32, write_u32), | |
214 | (u64, write_u64), | |
215 | (usize, write_usize), | |
216 | (i8, write_i8), | |
217 | (i16, write_i16), | |
218 | (i32, write_i32), | |
219 | (i64, write_i64), | |
220 | (isize, write_isize), | |
221 | } | |
1a4d82fc | 222 | |
85aaf69f SL |
223 | #[stable(feature = "rust1", since = "1.0.0")] |
224 | impl Hash for bool { | |
225 | fn hash<H: Hasher>(&self, state: &mut H) { | |
226 | state.write_u8(*self as u8) | |
1a4d82fc JJ |
227 | } |
228 | } | |
229 | ||
85aaf69f SL |
230 | #[stable(feature = "rust1", since = "1.0.0")] |
231 | impl Hash for char { | |
232 | fn hash<H: Hasher>(&self, state: &mut H) { | |
233 | state.write_u32(*self as u32) | |
1a4d82fc JJ |
234 | } |
235 | } | |
236 | ||
85aaf69f SL |
237 | #[stable(feature = "rust1", since = "1.0.0")] |
238 | impl Hash for str { | |
239 | fn hash<H: Hasher>(&self, state: &mut H) { | |
1a4d82fc | 240 | state.write(self.as_bytes()); |
85aaf69f | 241 | state.write_u8(0xff) |
1a4d82fc JJ |
242 | } |
243 | } | |
244 | ||
245 | macro_rules! impl_hash_tuple { | |
246 | () => ( | |
85aaf69f SL |
247 | #[stable(feature = "rust1", since = "1.0.0")] |
248 | impl Hash for () { | |
249 | fn hash<H: Hasher>(&self, _state: &mut H) {} | |
1a4d82fc JJ |
250 | } |
251 | ); | |
252 | ||
253 | ( $($name:ident)+) => ( | |
85aaf69f SL |
254 | #[stable(feature = "rust1", since = "1.0.0")] |
255 | impl<$($name: Hash),*> Hash for ($($name,)*) { | |
1a4d82fc | 256 | #[allow(non_snake_case)] |
85aaf69f SL |
257 | fn hash<S: Hasher>(&self, state: &mut S) { |
258 | let ($(ref $name,)*) = *self; | |
259 | $($name.hash(state);)* | |
1a4d82fc JJ |
260 | } |
261 | } | |
262 | ); | |
263 | } | |
264 | ||
265 | impl_hash_tuple! {} | |
266 | impl_hash_tuple! { A } | |
267 | impl_hash_tuple! { A B } | |
268 | impl_hash_tuple! { A B C } | |
269 | impl_hash_tuple! { A B C D } | |
270 | impl_hash_tuple! { A B C D E } | |
271 | impl_hash_tuple! { A B C D E F } | |
272 | impl_hash_tuple! { A B C D E F G } | |
273 | impl_hash_tuple! { A B C D E F G H } | |
274 | impl_hash_tuple! { A B C D E F G H I } | |
275 | impl_hash_tuple! { A B C D E F G H I J } | |
276 | impl_hash_tuple! { A B C D E F G H I J K } | |
277 | impl_hash_tuple! { A B C D E F G H I J K L } | |
278 | ||
85aaf69f SL |
279 | #[stable(feature = "rust1", since = "1.0.0")] |
280 | impl<T: Hash> Hash for [T] { | |
281 | fn hash<H: Hasher>(&self, state: &mut H) { | |
1a4d82fc | 282 | self.len().hash(state); |
85aaf69f | 283 | Hash::hash_slice(self, state) |
1a4d82fc JJ |
284 | } |
285 | } | |
286 | ||
287 | ||
85aaf69f SL |
288 | #[stable(feature = "rust1", since = "1.0.0")] |
289 | impl<'a, T: ?Sized + Hash> Hash for &'a T { | |
290 | fn hash<H: Hasher>(&self, state: &mut H) { | |
1a4d82fc JJ |
291 | (**self).hash(state); |
292 | } | |
293 | } | |
294 | ||
85aaf69f SL |
295 | #[stable(feature = "rust1", since = "1.0.0")] |
296 | impl<'a, T: ?Sized + Hash> Hash for &'a mut T { | |
297 | fn hash<H: Hasher>(&self, state: &mut H) { | |
1a4d82fc JJ |
298 | (**self).hash(state); |
299 | } | |
300 | } | |
301 | ||
85aaf69f SL |
302 | #[stable(feature = "rust1", since = "1.0.0")] |
303 | impl<T> Hash for *const T { | |
304 | fn hash<H: Hasher>(&self, state: &mut H) { | |
305 | state.write_usize(*self as usize) | |
1a4d82fc JJ |
306 | } |
307 | } | |
308 | ||
85aaf69f SL |
309 | #[stable(feature = "rust1", since = "1.0.0")] |
310 | impl<T> Hash for *mut T { | |
311 | fn hash<H: Hasher>(&self, state: &mut H) { | |
312 | state.write_usize(*self as usize) | |
1a4d82fc JJ |
313 | } |
314 | } | |
315 | } |