]>
Commit | Line | Data |
---|---|---|
85aaf69f | 1 | // Copyright 2014-2015 The Rust Project Developers. See the COPYRIGHT |
1a4d82fc JJ |
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. | |
1a4d82fc JJ |
10 | |
11 | use self::Entry::*; | |
12 | use self::SearchResult::*; | |
13 | use self::VacantEntryState::*; | |
14 | ||
85aaf69f | 15 | use borrow::Borrow; |
1a4d82fc JJ |
16 | use clone::Clone; |
17 | use cmp::{max, Eq, PartialEq}; | |
18 | use default::Default; | |
85aaf69f SL |
19 | use fmt::{self, Debug}; |
20 | use hash::{Hash, SipHasher}; | |
c34b1796 | 21 | use iter::{self, Iterator, ExactSizeIterator, IntoIterator, FromIterator, Extend, Map}; |
1a4d82fc JJ |
22 | use marker::Sized; |
23 | use mem::{self, replace}; | |
c34b1796 | 24 | use ops::{Deref, FnMut, FnOnce, Index}; |
1a4d82fc JJ |
25 | use option::Option::{self, Some, None}; |
26 | use rand::{self, Rng}; | |
27 | use result::Result::{self, Ok, Err}; | |
28 | ||
29 | use super::table::{ | |
30 | self, | |
31 | Bucket, | |
32 | EmptyBucket, | |
33 | FullBucket, | |
34 | FullBucketImm, | |
35 | FullBucketMut, | |
36 | RawTable, | |
37 | SafeHash | |
38 | }; | |
39 | use super::table::BucketState::{ | |
40 | Empty, | |
41 | Full, | |
42 | }; | |
43 | use super::state::HashState; | |
44 | ||
85aaf69f SL |
45 | const INITIAL_LOG2_CAP: usize = 5; |
46 | #[unstable(feature = "std_misc")] | |
47 | pub const INITIAL_CAPACITY: usize = 1 << INITIAL_LOG2_CAP; // 2^5 | |
1a4d82fc JJ |
48 | |
49 | /// The default behavior of HashMap implements a load factor of 90.9%. | |
50 | /// This behavior is characterized by the following condition: | |
51 | /// | |
52 | /// - if size > 0.909 * capacity: grow the map | |
53 | #[derive(Clone)] | |
54 | struct DefaultResizePolicy; | |
55 | ||
56 | impl DefaultResizePolicy { | |
57 | fn new() -> DefaultResizePolicy { | |
58 | DefaultResizePolicy | |
59 | } | |
60 | ||
61 | #[inline] | |
85aaf69f | 62 | fn min_capacity(&self, usable_size: usize) -> usize { |
1a4d82fc JJ |
63 | // Here, we are rephrasing the logic by specifying the lower limit |
64 | // on capacity: | |
65 | // | |
66 | // - if `cap < size * 1.1`: grow the map | |
67 | usable_size * 11 / 10 | |
68 | } | |
69 | ||
70 | /// An inverse of `min_capacity`, approximately. | |
71 | #[inline] | |
85aaf69f | 72 | fn usable_capacity(&self, cap: usize) -> usize { |
1a4d82fc JJ |
73 | // As the number of entries approaches usable capacity, |
74 | // min_capacity(size) must be smaller than the internal capacity, | |
75 | // so that the map is not resized: | |
76 | // `min_capacity(usable_capacity(x)) <= x`. | |
85aaf69f | 77 | // The left-hand side can only be smaller due to flooring by integer |
1a4d82fc JJ |
78 | // division. |
79 | // | |
80 | // This doesn't have to be checked for overflow since allocation size | |
81 | // in bytes will overflow earlier than multiplication by 10. | |
82 | cap * 10 / 11 | |
83 | } | |
84 | } | |
85 | ||
86 | #[test] | |
87 | fn test_resize_policy() { | |
1a4d82fc | 88 | let rp = DefaultResizePolicy; |
85aaf69f | 89 | for n in 0..1000 { |
1a4d82fc JJ |
90 | assert!(rp.min_capacity(rp.usable_capacity(n)) <= n); |
91 | assert!(rp.usable_capacity(rp.min_capacity(n)) <= n); | |
92 | } | |
93 | } | |
94 | ||
95 | // The main performance trick in this hashmap is called Robin Hood Hashing. | |
96 | // It gains its excellent performance from one essential operation: | |
97 | // | |
98 | // If an insertion collides with an existing element, and that element's | |
99 | // "probe distance" (how far away the element is from its ideal location) | |
100 | // is higher than how far we've already probed, swap the elements. | |
101 | // | |
102 | // This massively lowers variance in probe distance, and allows us to get very | |
103 | // high load factors with good performance. The 90% load factor I use is rather | |
104 | // conservative. | |
105 | // | |
106 | // > Why a load factor of approximately 90%? | |
107 | // | |
108 | // In general, all the distances to initial buckets will converge on the mean. | |
109 | // At a load factor of α, the odds of finding the target bucket after k | |
110 | // probes is approximately 1-α^k. If we set this equal to 50% (since we converge | |
111 | // on the mean) and set k=8 (64-byte cache line / 8-byte hash), α=0.92. I round | |
112 | // this down to make the math easier on the CPU and avoid its FPU. | |
113 | // Since on average we start the probing in the middle of a cache line, this | |
114 | // strategy pulls in two cache lines of hashes on every lookup. I think that's | |
115 | // pretty good, but if you want to trade off some space, it could go down to one | |
116 | // cache line on average with an α of 0.84. | |
117 | // | |
118 | // > Wait, what? Where did you get 1-α^k from? | |
119 | // | |
120 | // On the first probe, your odds of a collision with an existing element is α. | |
121 | // The odds of doing this twice in a row is approximately α^2. For three times, | |
122 | // α^3, etc. Therefore, the odds of colliding k times is α^k. The odds of NOT | |
123 | // colliding after k tries is 1-α^k. | |
124 | // | |
125 | // The paper from 1986 cited below mentions an implementation which keeps track | |
126 | // of the distance-to-initial-bucket histogram. This approach is not suitable | |
127 | // for modern architectures because it requires maintaining an internal data | |
128 | // structure. This allows very good first guesses, but we are most concerned | |
129 | // with guessing entire cache lines, not individual indexes. Furthermore, array | |
130 | // accesses are no longer linear and in one direction, as we have now. There | |
131 | // is also memory and cache pressure that this would entail that would be very | |
132 | // difficult to properly see in a microbenchmark. | |
133 | // | |
134 | // ## Future Improvements (FIXME!) | |
135 | // | |
136 | // Allow the load factor to be changed dynamically and/or at initialization. | |
137 | // | |
138 | // Also, would it be possible for us to reuse storage when growing the | |
139 | // underlying table? This is exactly the use case for 'realloc', and may | |
140 | // be worth exploring. | |
141 | // | |
142 | // ## Future Optimizations (FIXME!) | |
143 | // | |
144 | // Another possible design choice that I made without any real reason is | |
145 | // parameterizing the raw table over keys and values. Technically, all we need | |
146 | // is the size and alignment of keys and values, and the code should be just as | |
147 | // efficient (well, we might need one for power-of-two size and one for not...). | |
148 | // This has the potential to reduce code bloat in rust executables, without | |
149 | // really losing anything except 4 words (key size, key alignment, val size, | |
150 | // val alignment) which can be passed in to every call of a `RawTable` function. | |
151 | // This would definitely be an avenue worth exploring if people start complaining | |
152 | // about the size of rust executables. | |
153 | // | |
154 | // Annotate exceedingly likely branches in `table::make_hash` | |
155 | // and `search_hashed` to reduce instruction cache pressure | |
156 | // and mispredictions once it becomes possible (blocked on issue #11092). | |
157 | // | |
158 | // Shrinking the table could simply reallocate in place after moving buckets | |
159 | // to the first half. | |
160 | // | |
161 | // The growth algorithm (fragment of the Proof of Correctness) | |
162 | // -------------------- | |
163 | // | |
164 | // The growth algorithm is basically a fast path of the naive reinsertion- | |
165 | // during-resize algorithm. Other paths should never be taken. | |
166 | // | |
167 | // Consider growing a robin hood hashtable of capacity n. Normally, we do this | |
168 | // by allocating a new table of capacity `2n`, and then individually reinsert | |
169 | // each element in the old table into the new one. This guarantees that the | |
170 | // new table is a valid robin hood hashtable with all the desired statistical | |
171 | // properties. Remark that the order we reinsert the elements in should not | |
172 | // matter. For simplicity and efficiency, we will consider only linear | |
173 | // reinsertions, which consist of reinserting all elements in the old table | |
174 | // into the new one by increasing order of index. However we will not be | |
175 | // starting our reinsertions from index 0 in general. If we start from index | |
176 | // i, for the purpose of reinsertion we will consider all elements with real | |
177 | // index j < i to have virtual index n + j. | |
178 | // | |
179 | // Our hash generation scheme consists of generating a 64-bit hash and | |
180 | // truncating the most significant bits. When moving to the new table, we | |
181 | // simply introduce a new bit to the front of the hash. Therefore, if an | |
182 | // elements has ideal index i in the old table, it can have one of two ideal | |
183 | // locations in the new table. If the new bit is 0, then the new ideal index | |
184 | // is i. If the new bit is 1, then the new ideal index is n + i. Intuitively, | |
185 | // we are producing two independent tables of size n, and for each element we | |
186 | // independently choose which table to insert it into with equal probability. | |
187 | // However the rather than wrapping around themselves on overflowing their | |
188 | // indexes, the first table overflows into the first, and the first into the | |
189 | // second. Visually, our new table will look something like: | |
190 | // | |
191 | // [yy_xxx_xxxx_xxx|xx_yyy_yyyy_yyy] | |
192 | // | |
193 | // Where x's are elements inserted into the first table, y's are elements | |
194 | // inserted into the second, and _'s are empty sections. We now define a few | |
195 | // key concepts that we will use later. Note that this is a very abstract | |
196 | // perspective of the table. A real resized table would be at least half | |
197 | // empty. | |
198 | // | |
199 | // Theorem: A linear robin hood reinsertion from the first ideal element | |
200 | // produces identical results to a linear naive reinsertion from the same | |
201 | // element. | |
202 | // | |
c34b1796 | 203 | // FIXME(Gankro, pczarn): review the proof and put it all in a separate README.md |
1a4d82fc JJ |
204 | |
205 | /// A hash map implementation which uses linear probing with Robin | |
206 | /// Hood bucket stealing. | |
207 | /// | |
bd371182 | 208 | /// The hashes are all keyed by the thread-local random number generator |
1a4d82fc JJ |
209 | /// on creation by default. This means that the ordering of the keys is |
210 | /// randomized, but makes the tables more resistant to | |
211 | /// denial-of-service attacks (Hash DoS). This behaviour can be | |
212 | /// overridden with one of the constructors. | |
213 | /// | |
214 | /// It is required that the keys implement the `Eq` and `Hash` traits, although | |
d9579d0f AL |
215 | /// this can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`. |
216 | /// If you implement these yourself, it is important that the following | |
217 | /// property holds: | |
c34b1796 AL |
218 | /// |
219 | /// ```text | |
220 | /// k1 == k2 -> hash(k1) == hash(k2) | |
221 | /// ``` | |
222 | /// | |
223 | /// In other words, if two keys are equal, their hashes must be equal. | |
224 | /// | |
225 | /// It is a logic error for a key to be modified in such a way that the key's | |
226 | /// hash, as determined by the `Hash` trait, or its equality, as determined by | |
227 | /// the `Eq` trait, changes while it is in the map. This is normally only | |
228 | /// possible through `Cell`, `RefCell`, global state, I/O, or unsafe code. | |
1a4d82fc JJ |
229 | /// |
230 | /// Relevant papers/articles: | |
231 | /// | |
232 | /// 1. Pedro Celis. ["Robin Hood Hashing"](https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf) | |
233 | /// 2. Emmanuel Goossaert. ["Robin Hood | |
234 | /// hashing"](http://codecapsule.com/2013/11/11/robin-hood-hashing/) | |
235 | /// 3. Emmanuel Goossaert. ["Robin Hood hashing: backward shift | |
236 | /// deletion"](http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/) | |
237 | /// | |
c34b1796 | 238 | /// # Examples |
1a4d82fc JJ |
239 | /// |
240 | /// ``` | |
241 | /// use std::collections::HashMap; | |
242 | /// | |
243 | /// // type inference lets us omit an explicit type signature (which | |
244 | /// // would be `HashMap<&str, &str>` in this example). | |
245 | /// let mut book_reviews = HashMap::new(); | |
246 | /// | |
247 | /// // review some books. | |
248 | /// book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book."); | |
249 | /// book_reviews.insert("Grimms' Fairy Tales", "Masterpiece."); | |
250 | /// book_reviews.insert("Pride and Prejudice", "Very enjoyable."); | |
251 | /// book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot."); | |
252 | /// | |
253 | /// // check for a specific one. | |
d9579d0f | 254 | /// if !book_reviews.contains_key("Les Misérables") { |
1a4d82fc JJ |
255 | /// println!("We've got {} reviews, but Les Misérables ain't one.", |
256 | /// book_reviews.len()); | |
257 | /// } | |
258 | /// | |
259 | /// // oops, this review has a lot of spelling mistakes, let's delete it. | |
d9579d0f | 260 | /// book_reviews.remove("The Adventures of Sherlock Holmes"); |
1a4d82fc JJ |
261 | /// |
262 | /// // look up the values associated with some keys. | |
263 | /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"]; | |
d9579d0f | 264 | /// for book in &to_find { |
1a4d82fc | 265 | /// match book_reviews.get(book) { |
d9579d0f AL |
266 | /// Some(review) => println!("{}: {}", book, review), |
267 | /// None => println!("{} is unreviewed.", book) | |
1a4d82fc JJ |
268 | /// } |
269 | /// } | |
270 | /// | |
271 | /// // iterate over everything. | |
d9579d0f AL |
272 | /// for (book, review) in &book_reviews { |
273 | /// println!("{}: \"{}\"", book, review); | |
1a4d82fc JJ |
274 | /// } |
275 | /// ``` | |
276 | /// | |
277 | /// The easiest way to use `HashMap` with a custom type as key is to derive `Eq` and `Hash`. | |
278 | /// We must also derive `PartialEq`. | |
279 | /// | |
280 | /// ``` | |
281 | /// use std::collections::HashMap; | |
282 | /// | |
85aaf69f | 283 | /// #[derive(Hash, Eq, PartialEq, Debug)] |
1a4d82fc JJ |
284 | /// struct Viking { |
285 | /// name: String, | |
286 | /// country: String, | |
287 | /// } | |
288 | /// | |
289 | /// impl Viking { | |
290 | /// /// Create a new Viking. | |
291 | /// fn new(name: &str, country: &str) -> Viking { | |
292 | /// Viking { name: name.to_string(), country: country.to_string() } | |
293 | /// } | |
294 | /// } | |
295 | /// | |
296 | /// // Use a HashMap to store the vikings' health points. | |
297 | /// let mut vikings = HashMap::new(); | |
298 | /// | |
85aaf69f SL |
299 | /// vikings.insert(Viking::new("Einar", "Norway"), 25); |
300 | /// vikings.insert(Viking::new("Olaf", "Denmark"), 24); | |
301 | /// vikings.insert(Viking::new("Harald", "Iceland"), 12); | |
1a4d82fc JJ |
302 | /// |
303 | /// // Use derived implementation to print the status of the vikings. | |
d9579d0f | 304 | /// for (viking, health) in &vikings { |
1a4d82fc JJ |
305 | /// println!("{:?} has {} hp", viking, health); |
306 | /// } | |
307 | /// ``` | |
308 | #[derive(Clone)] | |
85aaf69f | 309 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
310 | pub struct HashMap<K, V, S = RandomState> { |
311 | // All hashes are keyed on these values, to prevent hash collision attacks. | |
312 | hash_state: S, | |
313 | ||
314 | table: RawTable<K, V>, | |
315 | ||
316 | resize_policy: DefaultResizePolicy, | |
317 | } | |
318 | ||
319 | /// Search for a pre-hashed key. | |
320 | fn search_hashed<K, V, M, F>(table: M, | |
321 | hash: SafeHash, | |
322 | mut is_match: F) | |
323 | -> SearchResult<K, V, M> where | |
324 | M: Deref<Target=RawTable<K, V>>, | |
325 | F: FnMut(&K) -> bool, | |
326 | { | |
c34b1796 AL |
327 | // This is the only function where capacity can be zero. To avoid |
328 | // undefined behaviour when Bucket::new gets the raw bucket in this | |
329 | // case, immediately return the appropriate search result. | |
330 | if table.capacity() == 0 { | |
331 | return TableRef(table); | |
332 | } | |
333 | ||
1a4d82fc JJ |
334 | let size = table.size(); |
335 | let mut probe = Bucket::new(table, hash); | |
336 | let ib = probe.index(); | |
337 | ||
338 | while probe.index() != ib + size { | |
339 | let full = match probe.peek() { | |
340 | Empty(b) => return TableRef(b.into_table()), // hit an empty bucket | |
341 | Full(b) => b | |
342 | }; | |
343 | ||
344 | if full.distance() + ib < full.index() { | |
345 | // We can finish the search early if we hit any bucket | |
346 | // with a lower distance to initial bucket than we've probed. | |
347 | return TableRef(full.into_table()); | |
348 | } | |
349 | ||
350 | // If the hash doesn't match, it can't be this one.. | |
351 | if hash == full.hash() { | |
352 | // If the key doesn't match, it can't be this one.. | |
353 | if is_match(full.read().0) { | |
354 | return FoundExisting(full); | |
355 | } | |
356 | } | |
357 | ||
358 | probe = full.next(); | |
359 | } | |
360 | ||
361 | TableRef(probe.into_table()) | |
362 | } | |
363 | ||
364 | fn pop_internal<K, V>(starting_bucket: FullBucketMut<K, V>) -> (K, V) { | |
365 | let (empty, retkey, retval) = starting_bucket.take(); | |
366 | let mut gap = match empty.gap_peek() { | |
367 | Some(b) => b, | |
368 | None => return (retkey, retval) | |
369 | }; | |
370 | ||
371 | while gap.full().distance() != 0 { | |
372 | gap = match gap.shift() { | |
373 | Some(b) => b, | |
374 | None => break | |
375 | }; | |
376 | } | |
377 | ||
378 | // Now we've done all our shifting. Return the value we grabbed earlier. | |
379 | (retkey, retval) | |
380 | } | |
381 | ||
382 | /// Perform robin hood bucket stealing at the given `bucket`. You must | |
383 | /// also pass the position of that bucket's initial bucket so we don't have | |
384 | /// to recalculate it. | |
385 | /// | |
386 | /// `hash`, `k`, and `v` are the elements to "robin hood" into the hashtable. | |
387 | fn robin_hood<'a, K: 'a, V: 'a>(mut bucket: FullBucketMut<'a, K, V>, | |
85aaf69f | 388 | mut ib: usize, |
1a4d82fc JJ |
389 | mut hash: SafeHash, |
390 | mut k: K, | |
391 | mut v: V) | |
392 | -> &'a mut V { | |
393 | let starting_index = bucket.index(); | |
394 | let size = { | |
395 | let table = bucket.table(); // FIXME "lifetime too short". | |
396 | table.size() | |
397 | }; | |
398 | // There can be at most `size - dib` buckets to displace, because | |
399 | // in the worst case, there are `size` elements and we already are | |
400 | // `distance` buckets away from the initial one. | |
401 | let idx_end = starting_index + size - bucket.distance(); | |
402 | ||
403 | loop { | |
404 | let (old_hash, old_key, old_val) = bucket.replace(hash, k, v); | |
405 | loop { | |
406 | let probe = bucket.next(); | |
407 | assert!(probe.index() != idx_end); | |
408 | ||
409 | let full_bucket = match probe.peek() { | |
410 | Empty(bucket) => { | |
411 | // Found a hole! | |
412 | let b = bucket.put(old_hash, old_key, old_val); | |
413 | // Now that it's stolen, just read the value's pointer | |
414 | // right out of the table! | |
415 | return Bucket::at_index(b.into_table(), starting_index) | |
416 | .peek() | |
417 | .expect_full() | |
418 | .into_mut_refs() | |
419 | .1; | |
420 | }, | |
421 | Full(bucket) => bucket | |
422 | }; | |
423 | ||
424 | let probe_ib = full_bucket.index() - full_bucket.distance(); | |
425 | ||
426 | bucket = full_bucket; | |
427 | ||
428 | // Robin hood! Steal the spot. | |
429 | if ib < probe_ib { | |
430 | ib = probe_ib; | |
431 | hash = old_hash; | |
432 | k = old_key; | |
433 | v = old_val; | |
434 | break; | |
435 | } | |
436 | } | |
437 | } | |
438 | } | |
439 | ||
440 | /// A result that works like Option<FullBucket<..>> but preserves | |
441 | /// the reference that grants us access to the table in any case. | |
442 | enum SearchResult<K, V, M> { | |
443 | // This is an entry that holds the given key: | |
444 | FoundExisting(FullBucket<K, V, M>), | |
445 | ||
446 | // There was no such entry. The reference is given back: | |
447 | TableRef(M) | |
448 | } | |
449 | ||
450 | impl<K, V, M> SearchResult<K, V, M> { | |
451 | fn into_option(self) -> Option<FullBucket<K, V, M>> { | |
452 | match self { | |
453 | FoundExisting(bucket) => Some(bucket), | |
454 | TableRef(_) => None | |
455 | } | |
456 | } | |
457 | } | |
458 | ||
85aaf69f SL |
459 | impl<K, V, S> HashMap<K, V, S> |
460 | where K: Eq + Hash, S: HashState | |
1a4d82fc | 461 | { |
85aaf69f | 462 | fn make_hash<X: ?Sized>(&self, x: &X) -> SafeHash where X: Hash { |
1a4d82fc JJ |
463 | table::make_hash(&self.hash_state, x) |
464 | } | |
465 | ||
466 | /// Search for a key, yielding the index if it's found in the hashtable. | |
467 | /// If you already have the hash for the key lying around, use | |
468 | /// search_hashed. | |
469 | fn search<'a, Q: ?Sized>(&'a self, q: &Q) -> Option<FullBucketImm<'a, K, V>> | |
85aaf69f | 470 | where K: Borrow<Q>, Q: Eq + Hash |
1a4d82fc JJ |
471 | { |
472 | let hash = self.make_hash(q); | |
85aaf69f | 473 | search_hashed(&self.table, hash, |k| q.eq(k.borrow())) |
1a4d82fc JJ |
474 | .into_option() |
475 | } | |
476 | ||
477 | fn search_mut<'a, Q: ?Sized>(&'a mut self, q: &Q) -> Option<FullBucketMut<'a, K, V>> | |
85aaf69f | 478 | where K: Borrow<Q>, Q: Eq + Hash |
1a4d82fc JJ |
479 | { |
480 | let hash = self.make_hash(q); | |
85aaf69f | 481 | search_hashed(&mut self.table, hash, |k| q.eq(k.borrow())) |
1a4d82fc JJ |
482 | .into_option() |
483 | } | |
484 | ||
485 | // The caller should ensure that invariants by Robin Hood Hashing hold. | |
486 | fn insert_hashed_ordered(&mut self, hash: SafeHash, k: K, v: V) { | |
487 | let cap = self.table.capacity(); | |
488 | let mut buckets = Bucket::new(&mut self.table, hash); | |
489 | let ib = buckets.index(); | |
490 | ||
491 | while buckets.index() != ib + cap { | |
492 | // We don't need to compare hashes for value swap. | |
493 | // Not even DIBs for Robin Hood. | |
494 | buckets = match buckets.peek() { | |
495 | Empty(empty) => { | |
496 | empty.put(hash, k, v); | |
497 | return; | |
498 | } | |
499 | Full(b) => b.into_bucket() | |
500 | }; | |
501 | buckets.next(); | |
502 | } | |
503 | panic!("Internal HashMap error: Out of space."); | |
504 | } | |
505 | } | |
506 | ||
85aaf69f | 507 | impl<K: Hash + Eq, V> HashMap<K, V, RandomState> { |
9346a6ac | 508 | /// Creates an empty HashMap. |
1a4d82fc | 509 | /// |
c34b1796 | 510 | /// # Examples |
1a4d82fc JJ |
511 | /// |
512 | /// ``` | |
513 | /// use std::collections::HashMap; | |
c34b1796 | 514 | /// let mut map: HashMap<&str, isize> = HashMap::new(); |
1a4d82fc JJ |
515 | /// ``` |
516 | #[inline] | |
85aaf69f | 517 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
518 | pub fn new() -> HashMap<K, V, RandomState> { |
519 | Default::default() | |
520 | } | |
521 | ||
522 | /// Creates an empty hash map with the given initial capacity. | |
523 | /// | |
c34b1796 | 524 | /// # Examples |
1a4d82fc JJ |
525 | /// |
526 | /// ``` | |
527 | /// use std::collections::HashMap; | |
c34b1796 | 528 | /// let mut map: HashMap<&str, isize> = HashMap::with_capacity(10); |
1a4d82fc JJ |
529 | /// ``` |
530 | #[inline] | |
85aaf69f SL |
531 | #[stable(feature = "rust1", since = "1.0.0")] |
532 | pub fn with_capacity(capacity: usize) -> HashMap<K, V, RandomState> { | |
1a4d82fc JJ |
533 | HashMap::with_capacity_and_hash_state(capacity, Default::default()) |
534 | } | |
535 | } | |
536 | ||
85aaf69f SL |
537 | impl<K, V, S> HashMap<K, V, S> |
538 | where K: Eq + Hash, S: HashState | |
1a4d82fc JJ |
539 | { |
540 | /// Creates an empty hashmap which will use the given hasher to hash keys. | |
541 | /// | |
542 | /// The creates map has the default initial capacity. | |
543 | /// | |
c34b1796 | 544 | /// # Examples |
1a4d82fc JJ |
545 | /// |
546 | /// ``` | |
c34b1796 | 547 | /// # #![feature(std_misc)] |
1a4d82fc JJ |
548 | /// use std::collections::HashMap; |
549 | /// use std::collections::hash_map::RandomState; | |
550 | /// | |
551 | /// let s = RandomState::new(); | |
552 | /// let mut map = HashMap::with_hash_state(s); | |
85aaf69f | 553 | /// map.insert(1, 2); |
1a4d82fc JJ |
554 | /// ``` |
555 | #[inline] | |
85aaf69f | 556 | #[unstable(feature = "std_misc", reason = "hasher stuff is unclear")] |
1a4d82fc JJ |
557 | pub fn with_hash_state(hash_state: S) -> HashMap<K, V, S> { |
558 | HashMap { | |
559 | hash_state: hash_state, | |
560 | resize_policy: DefaultResizePolicy::new(), | |
561 | table: RawTable::new(0), | |
562 | } | |
563 | } | |
564 | ||
9346a6ac | 565 | /// Creates an empty HashMap with space for at least `capacity` |
1a4d82fc JJ |
566 | /// elements, using `hasher` to hash the keys. |
567 | /// | |
568 | /// Warning: `hasher` is normally randomly generated, and | |
569 | /// is designed to allow HashMaps to be resistant to attacks that | |
570 | /// cause many collisions and very poor performance. Setting it | |
571 | /// manually using this function can expose a DoS attack vector. | |
572 | /// | |
c34b1796 | 573 | /// # Examples |
1a4d82fc JJ |
574 | /// |
575 | /// ``` | |
c34b1796 | 576 | /// # #![feature(std_misc)] |
1a4d82fc JJ |
577 | /// use std::collections::HashMap; |
578 | /// use std::collections::hash_map::RandomState; | |
579 | /// | |
580 | /// let s = RandomState::new(); | |
581 | /// let mut map = HashMap::with_capacity_and_hash_state(10, s); | |
85aaf69f | 582 | /// map.insert(1, 2); |
1a4d82fc JJ |
583 | /// ``` |
584 | #[inline] | |
85aaf69f SL |
585 | #[unstable(feature = "std_misc", reason = "hasher stuff is unclear")] |
586 | pub fn with_capacity_and_hash_state(capacity: usize, hash_state: S) | |
1a4d82fc JJ |
587 | -> HashMap<K, V, S> { |
588 | let resize_policy = DefaultResizePolicy::new(); | |
589 | let min_cap = max(INITIAL_CAPACITY, resize_policy.min_capacity(capacity)); | |
590 | let internal_cap = min_cap.checked_next_power_of_two().expect("capacity overflow"); | |
591 | assert!(internal_cap >= capacity, "capacity overflow"); | |
592 | HashMap { | |
593 | hash_state: hash_state, | |
594 | resize_policy: resize_policy, | |
595 | table: RawTable::new(internal_cap), | |
596 | } | |
597 | } | |
598 | ||
599 | /// Returns the number of elements the map can hold without reallocating. | |
600 | /// | |
c34b1796 | 601 | /// # Examples |
1a4d82fc JJ |
602 | /// |
603 | /// ``` | |
604 | /// use std::collections::HashMap; | |
c34b1796 | 605 | /// let map: HashMap<isize, isize> = HashMap::with_capacity(100); |
1a4d82fc JJ |
606 | /// assert!(map.capacity() >= 100); |
607 | /// ``` | |
608 | #[inline] | |
85aaf69f SL |
609 | #[stable(feature = "rust1", since = "1.0.0")] |
610 | pub fn capacity(&self) -> usize { | |
1a4d82fc JJ |
611 | self.resize_policy.usable_capacity(self.table.capacity()) |
612 | } | |
613 | ||
614 | /// Reserves capacity for at least `additional` more elements to be inserted | |
615 | /// in the `HashMap`. The collection may reserve more space to avoid | |
616 | /// frequent reallocations. | |
617 | /// | |
618 | /// # Panics | |
619 | /// | |
85aaf69f | 620 | /// Panics if the new allocation size overflows `usize`. |
1a4d82fc | 621 | /// |
c34b1796 | 622 | /// # Examples |
1a4d82fc JJ |
623 | /// |
624 | /// ``` | |
625 | /// use std::collections::HashMap; | |
c34b1796 | 626 | /// let mut map: HashMap<&str, isize> = HashMap::new(); |
1a4d82fc JJ |
627 | /// map.reserve(10); |
628 | /// ``` | |
85aaf69f SL |
629 | #[stable(feature = "rust1", since = "1.0.0")] |
630 | pub fn reserve(&mut self, additional: usize) { | |
1a4d82fc JJ |
631 | let new_size = self.len().checked_add(additional).expect("capacity overflow"); |
632 | let min_cap = self.resize_policy.min_capacity(new_size); | |
633 | ||
634 | // An invalid value shouldn't make us run out of space. This includes | |
635 | // an overflow check. | |
636 | assert!(new_size <= min_cap); | |
637 | ||
638 | if self.table.capacity() < min_cap { | |
639 | let new_capacity = max(min_cap.next_power_of_two(), INITIAL_CAPACITY); | |
640 | self.resize(new_capacity); | |
641 | } | |
642 | } | |
643 | ||
644 | /// Resizes the internal vectors to a new capacity. It's your responsibility to: | |
645 | /// 1) Make sure the new capacity is enough for all the elements, accounting | |
646 | /// for the load factor. | |
647 | /// 2) Ensure new_capacity is a power of two or zero. | |
85aaf69f | 648 | fn resize(&mut self, new_capacity: usize) { |
1a4d82fc JJ |
649 | assert!(self.table.size() <= new_capacity); |
650 | assert!(new_capacity.is_power_of_two() || new_capacity == 0); | |
651 | ||
652 | let mut old_table = replace(&mut self.table, RawTable::new(new_capacity)); | |
653 | let old_size = old_table.size(); | |
654 | ||
655 | if old_table.capacity() == 0 || old_table.size() == 0 { | |
656 | return; | |
657 | } | |
658 | ||
659 | // Grow the table. | |
660 | // Specialization of the other branch. | |
661 | let mut bucket = Bucket::first(&mut old_table); | |
662 | ||
663 | // "So a few of the first shall be last: for many be called, | |
664 | // but few chosen." | |
665 | // | |
666 | // We'll most likely encounter a few buckets at the beginning that | |
667 | // have their initial buckets near the end of the table. They were | |
668 | // placed at the beginning as the probe wrapped around the table | |
669 | // during insertion. We must skip forward to a bucket that won't | |
670 | // get reinserted too early and won't unfairly steal others spot. | |
671 | // This eliminates the need for robin hood. | |
672 | loop { | |
673 | bucket = match bucket.peek() { | |
674 | Full(full) => { | |
675 | if full.distance() == 0 { | |
676 | // This bucket occupies its ideal spot. | |
677 | // It indicates the start of another "cluster". | |
678 | bucket = full.into_bucket(); | |
679 | break; | |
680 | } | |
681 | // Leaving this bucket in the last cluster for later. | |
682 | full.into_bucket() | |
683 | } | |
684 | Empty(b) => { | |
685 | // Encountered a hole between clusters. | |
686 | b.into_bucket() | |
687 | } | |
688 | }; | |
689 | bucket.next(); | |
690 | } | |
691 | ||
692 | // This is how the buckets might be laid out in memory: | |
693 | // ($ marks an initialized bucket) | |
694 | // ________________ | |
695 | // |$$$_$$$$$$_$$$$$| | |
696 | // | |
697 | // But we've skipped the entire initial cluster of buckets | |
698 | // and will continue iteration in this order: | |
699 | // ________________ | |
700 | // |$$$$$$_$$$$$ | |
701 | // ^ wrap around once end is reached | |
702 | // ________________ | |
703 | // $$$_____________| | |
704 | // ^ exit once table.size == 0 | |
705 | loop { | |
706 | bucket = match bucket.peek() { | |
707 | Full(bucket) => { | |
708 | let h = bucket.hash(); | |
709 | let (b, k, v) = bucket.take(); | |
710 | self.insert_hashed_ordered(h, k, v); | |
711 | { | |
712 | let t = b.table(); // FIXME "lifetime too short". | |
713 | if t.size() == 0 { break } | |
714 | }; | |
715 | b.into_bucket() | |
716 | } | |
717 | Empty(b) => b.into_bucket() | |
718 | }; | |
719 | bucket.next(); | |
720 | } | |
721 | ||
722 | assert_eq!(self.table.size(), old_size); | |
723 | } | |
724 | ||
725 | /// Shrinks the capacity of the map as much as possible. It will drop | |
726 | /// down as much as possible while maintaining the internal rules | |
727 | /// and possibly leaving some space in accordance with the resize policy. | |
728 | /// | |
c34b1796 | 729 | /// # Examples |
1a4d82fc JJ |
730 | /// |
731 | /// ``` | |
732 | /// use std::collections::HashMap; | |
733 | /// | |
c34b1796 | 734 | /// let mut map: HashMap<isize, isize> = HashMap::with_capacity(100); |
1a4d82fc JJ |
735 | /// map.insert(1, 2); |
736 | /// map.insert(3, 4); | |
737 | /// assert!(map.capacity() >= 100); | |
738 | /// map.shrink_to_fit(); | |
739 | /// assert!(map.capacity() >= 2); | |
740 | /// ``` | |
85aaf69f | 741 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
742 | pub fn shrink_to_fit(&mut self) { |
743 | let min_capacity = self.resize_policy.min_capacity(self.len()); | |
744 | let min_capacity = max(min_capacity.next_power_of_two(), INITIAL_CAPACITY); | |
745 | ||
746 | // An invalid value shouldn't make us run out of space. | |
747 | debug_assert!(self.len() <= min_capacity); | |
748 | ||
749 | if self.table.capacity() != min_capacity { | |
750 | let old_table = replace(&mut self.table, RawTable::new(min_capacity)); | |
751 | let old_size = old_table.size(); | |
752 | ||
753 | // Shrink the table. Naive algorithm for resizing: | |
754 | for (h, k, v) in old_table.into_iter() { | |
755 | self.insert_hashed_nocheck(h, k, v); | |
756 | } | |
757 | ||
758 | debug_assert_eq!(self.table.size(), old_size); | |
759 | } | |
760 | } | |
761 | ||
762 | /// Insert a pre-hashed key-value pair, without first checking | |
763 | /// that there's enough room in the buckets. Returns a reference to the | |
764 | /// newly insert value. | |
765 | /// | |
766 | /// If the key already exists, the hashtable will be returned untouched | |
767 | /// and a reference to the existing element will be returned. | |
768 | fn insert_hashed_nocheck(&mut self, hash: SafeHash, k: K, v: V) -> &mut V { | |
769 | self.insert_or_replace_with(hash, k, v, |_, _, _| ()) | |
770 | } | |
771 | ||
772 | fn insert_or_replace_with<'a, F>(&'a mut self, | |
773 | hash: SafeHash, | |
774 | k: K, | |
775 | v: V, | |
776 | mut found_existing: F) | |
777 | -> &'a mut V where | |
778 | F: FnMut(&mut K, &mut V, V), | |
779 | { | |
780 | // Worst case, we'll find one empty bucket among `size + 1` buckets. | |
781 | let size = self.table.size(); | |
782 | let mut probe = Bucket::new(&mut self.table, hash); | |
783 | let ib = probe.index(); | |
784 | ||
785 | loop { | |
786 | let mut bucket = match probe.peek() { | |
787 | Empty(bucket) => { | |
788 | // Found a hole! | |
789 | return bucket.put(hash, k, v).into_mut_refs().1; | |
790 | } | |
791 | Full(bucket) => bucket | |
792 | }; | |
793 | ||
794 | // hash matches? | |
795 | if bucket.hash() == hash { | |
796 | // key matches? | |
797 | if k == *bucket.read_mut().0 { | |
798 | let (bucket_k, bucket_v) = bucket.into_mut_refs(); | |
799 | debug_assert!(k == *bucket_k); | |
800 | // Key already exists. Get its reference. | |
801 | found_existing(bucket_k, bucket_v, v); | |
802 | return bucket_v; | |
803 | } | |
804 | } | |
805 | ||
c34b1796 | 806 | let robin_ib = bucket.index() as isize - bucket.distance() as isize; |
1a4d82fc | 807 | |
c34b1796 | 808 | if (ib as isize) < robin_ib { |
1a4d82fc | 809 | // Found a luckier bucket than me. Better steal his spot. |
85aaf69f | 810 | return robin_hood(bucket, robin_ib as usize, hash, k, v); |
1a4d82fc JJ |
811 | } |
812 | ||
813 | probe = bucket.next(); | |
814 | assert!(probe.index() != ib + size + 1); | |
815 | } | |
816 | } | |
817 | ||
818 | /// An iterator visiting all keys in arbitrary order. | |
819 | /// Iterator element type is `&'a K`. | |
820 | /// | |
c34b1796 | 821 | /// # Examples |
1a4d82fc JJ |
822 | /// |
823 | /// ``` | |
824 | /// use std::collections::HashMap; | |
825 | /// | |
826 | /// let mut map = HashMap::new(); | |
85aaf69f | 827 | /// map.insert("a", 1); |
1a4d82fc JJ |
828 | /// map.insert("b", 2); |
829 | /// map.insert("c", 3); | |
830 | /// | |
831 | /// for key in map.keys() { | |
832 | /// println!("{}", key); | |
833 | /// } | |
834 | /// ``` | |
85aaf69f | 835 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
836 | pub fn keys<'a>(&'a self) -> Keys<'a, K, V> { |
837 | fn first<A, B>((a, _): (A, B)) -> A { a } | |
838 | let first: fn((&'a K,&'a V)) -> &'a K = first; // coerce to fn ptr | |
839 | ||
840 | Keys { inner: self.iter().map(first) } | |
841 | } | |
842 | ||
843 | /// An iterator visiting all values in arbitrary order. | |
844 | /// Iterator element type is `&'a V`. | |
845 | /// | |
c34b1796 | 846 | /// # Examples |
1a4d82fc JJ |
847 | /// |
848 | /// ``` | |
849 | /// use std::collections::HashMap; | |
850 | /// | |
851 | /// let mut map = HashMap::new(); | |
85aaf69f | 852 | /// map.insert("a", 1); |
1a4d82fc JJ |
853 | /// map.insert("b", 2); |
854 | /// map.insert("c", 3); | |
855 | /// | |
85aaf69f SL |
856 | /// for val in map.values() { |
857 | /// println!("{}", val); | |
1a4d82fc JJ |
858 | /// } |
859 | /// ``` | |
85aaf69f | 860 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
861 | pub fn values<'a>(&'a self) -> Values<'a, K, V> { |
862 | fn second<A, B>((_, b): (A, B)) -> B { b } | |
863 | let second: fn((&'a K,&'a V)) -> &'a V = second; // coerce to fn ptr | |
864 | ||
865 | Values { inner: self.iter().map(second) } | |
866 | } | |
867 | ||
868 | /// An iterator visiting all key-value pairs in arbitrary order. | |
869 | /// Iterator element type is `(&'a K, &'a V)`. | |
870 | /// | |
c34b1796 | 871 | /// # Examples |
1a4d82fc JJ |
872 | /// |
873 | /// ``` | |
874 | /// use std::collections::HashMap; | |
875 | /// | |
876 | /// let mut map = HashMap::new(); | |
85aaf69f | 877 | /// map.insert("a", 1); |
1a4d82fc JJ |
878 | /// map.insert("b", 2); |
879 | /// map.insert("c", 3); | |
880 | /// | |
881 | /// for (key, val) in map.iter() { | |
882 | /// println!("key: {} val: {}", key, val); | |
883 | /// } | |
884 | /// ``` | |
85aaf69f | 885 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
886 | pub fn iter(&self) -> Iter<K, V> { |
887 | Iter { inner: self.table.iter() } | |
888 | } | |
889 | ||
890 | /// An iterator visiting all key-value pairs in arbitrary order, | |
891 | /// with mutable references to the values. | |
892 | /// Iterator element type is `(&'a K, &'a mut V)`. | |
893 | /// | |
c34b1796 | 894 | /// # Examples |
1a4d82fc JJ |
895 | /// |
896 | /// ``` | |
897 | /// use std::collections::HashMap; | |
898 | /// | |
899 | /// let mut map = HashMap::new(); | |
85aaf69f | 900 | /// map.insert("a", 1); |
1a4d82fc JJ |
901 | /// map.insert("b", 2); |
902 | /// map.insert("c", 3); | |
903 | /// | |
904 | /// // Update all values | |
905 | /// for (_, val) in map.iter_mut() { | |
906 | /// *val *= 2; | |
907 | /// } | |
908 | /// | |
909 | /// for (key, val) in map.iter() { | |
910 | /// println!("key: {} val: {}", key, val); | |
911 | /// } | |
912 | /// ``` | |
85aaf69f | 913 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
914 | pub fn iter_mut(&mut self) -> IterMut<K, V> { |
915 | IterMut { inner: self.table.iter_mut() } | |
916 | } | |
917 | ||
1a4d82fc | 918 | /// Gets the given key's corresponding entry in the map for in-place manipulation. |
bd371182 AL |
919 | /// |
920 | /// # Examples | |
921 | /// | |
922 | /// ``` | |
923 | /// use std::collections::HashMap; | |
924 | /// | |
925 | /// let mut letters = HashMap::new(); | |
926 | /// | |
927 | /// for ch in "a short treatise on fungi".chars() { | |
928 | /// let counter = letters.entry(ch).or_insert(0); | |
929 | /// *counter += 1; | |
930 | /// } | |
931 | /// | |
932 | /// assert_eq!(letters[&'s'], 2); | |
933 | /// assert_eq!(letters[&'t'], 3); | |
934 | /// assert_eq!(letters[&'u'], 1); | |
935 | /// assert_eq!(letters.get(&'y'), None); | |
936 | /// ``` | |
85aaf69f SL |
937 | #[stable(feature = "rust1", since = "1.0.0")] |
938 | pub fn entry(&mut self, key: K) -> Entry<K, V> { | |
1a4d82fc JJ |
939 | // Gotta resize now. |
940 | self.reserve(1); | |
941 | ||
942 | let hash = self.make_hash(&key); | |
943 | search_entry_hashed(&mut self.table, hash, key) | |
944 | } | |
945 | ||
85aaf69f | 946 | /// Returns the number of elements in the map. |
1a4d82fc | 947 | /// |
c34b1796 | 948 | /// # Examples |
1a4d82fc JJ |
949 | /// |
950 | /// ``` | |
951 | /// use std::collections::HashMap; | |
952 | /// | |
953 | /// let mut a = HashMap::new(); | |
954 | /// assert_eq!(a.len(), 0); | |
85aaf69f | 955 | /// a.insert(1, "a"); |
1a4d82fc JJ |
956 | /// assert_eq!(a.len(), 1); |
957 | /// ``` | |
85aaf69f SL |
958 | #[stable(feature = "rust1", since = "1.0.0")] |
959 | pub fn len(&self) -> usize { self.table.size() } | |
1a4d82fc | 960 | |
85aaf69f | 961 | /// Returns true if the map contains no elements. |
1a4d82fc | 962 | /// |
c34b1796 | 963 | /// # Examples |
1a4d82fc JJ |
964 | /// |
965 | /// ``` | |
966 | /// use std::collections::HashMap; | |
967 | /// | |
968 | /// let mut a = HashMap::new(); | |
969 | /// assert!(a.is_empty()); | |
85aaf69f | 970 | /// a.insert(1, "a"); |
1a4d82fc JJ |
971 | /// assert!(!a.is_empty()); |
972 | /// ``` | |
973 | #[inline] | |
85aaf69f | 974 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
975 | pub fn is_empty(&self) -> bool { self.len() == 0 } |
976 | ||
977 | /// Clears the map, returning all key-value pairs as an iterator. Keeps the | |
978 | /// allocated memory for reuse. | |
979 | /// | |
c34b1796 | 980 | /// # Examples |
1a4d82fc JJ |
981 | /// |
982 | /// ``` | |
c34b1796 | 983 | /// # #![feature(std_misc)] |
1a4d82fc JJ |
984 | /// use std::collections::HashMap; |
985 | /// | |
986 | /// let mut a = HashMap::new(); | |
85aaf69f SL |
987 | /// a.insert(1, "a"); |
988 | /// a.insert(2, "b"); | |
1a4d82fc JJ |
989 | /// |
990 | /// for (k, v) in a.drain().take(1) { | |
991 | /// assert!(k == 1 || k == 2); | |
992 | /// assert!(v == "a" || v == "b"); | |
993 | /// } | |
994 | /// | |
995 | /// assert!(a.is_empty()); | |
996 | /// ``` | |
997 | #[inline] | |
85aaf69f SL |
998 | #[unstable(feature = "std_misc", |
999 | reason = "matches collection reform specification, waiting for dust to settle")] | |
1a4d82fc JJ |
1000 | pub fn drain(&mut self) -> Drain<K, V> { |
1001 | fn last_two<A, B, C>((_, b, c): (A, B, C)) -> (B, C) { (b, c) } | |
1002 | let last_two: fn((SafeHash, K, V)) -> (K, V) = last_two; // coerce to fn pointer | |
1003 | ||
1004 | Drain { | |
1005 | inner: self.table.drain().map(last_two), | |
1006 | } | |
1007 | } | |
1008 | ||
1009 | /// Clears the map, removing all key-value pairs. Keeps the allocated memory | |
1010 | /// for reuse. | |
1011 | /// | |
c34b1796 | 1012 | /// # Examples |
1a4d82fc JJ |
1013 | /// |
1014 | /// ``` | |
1015 | /// use std::collections::HashMap; | |
1016 | /// | |
1017 | /// let mut a = HashMap::new(); | |
85aaf69f | 1018 | /// a.insert(1, "a"); |
1a4d82fc JJ |
1019 | /// a.clear(); |
1020 | /// assert!(a.is_empty()); | |
1021 | /// ``` | |
85aaf69f | 1022 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1023 | #[inline] |
1024 | pub fn clear(&mut self) { | |
1025 | self.drain(); | |
1026 | } | |
1027 | ||
1028 | /// Returns a reference to the value corresponding to the key. | |
1029 | /// | |
1030 | /// The key may be any borrowed form of the map's key type, but | |
1031 | /// `Hash` and `Eq` on the borrowed form *must* match those for | |
1032 | /// the key type. | |
1033 | /// | |
c34b1796 | 1034 | /// # Examples |
1a4d82fc JJ |
1035 | /// |
1036 | /// ``` | |
1037 | /// use std::collections::HashMap; | |
1038 | /// | |
1039 | /// let mut map = HashMap::new(); | |
85aaf69f | 1040 | /// map.insert(1, "a"); |
1a4d82fc JJ |
1041 | /// assert_eq!(map.get(&1), Some(&"a")); |
1042 | /// assert_eq!(map.get(&2), None); | |
1043 | /// ``` | |
85aaf69f | 1044 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 1045 | pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V> |
85aaf69f | 1046 | where K: Borrow<Q>, Q: Hash + Eq |
1a4d82fc JJ |
1047 | { |
1048 | self.search(k).map(|bucket| bucket.into_refs().1) | |
1049 | } | |
1050 | ||
1051 | /// Returns true if the map contains a value for the specified key. | |
1052 | /// | |
1053 | /// The key may be any borrowed form of the map's key type, but | |
1054 | /// `Hash` and `Eq` on the borrowed form *must* match those for | |
1055 | /// the key type. | |
1056 | /// | |
c34b1796 | 1057 | /// # Examples |
1a4d82fc JJ |
1058 | /// |
1059 | /// ``` | |
1060 | /// use std::collections::HashMap; | |
1061 | /// | |
1062 | /// let mut map = HashMap::new(); | |
85aaf69f | 1063 | /// map.insert(1, "a"); |
1a4d82fc JJ |
1064 | /// assert_eq!(map.contains_key(&1), true); |
1065 | /// assert_eq!(map.contains_key(&2), false); | |
1066 | /// ``` | |
85aaf69f | 1067 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 1068 | pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool |
85aaf69f | 1069 | where K: Borrow<Q>, Q: Hash + Eq |
1a4d82fc JJ |
1070 | { |
1071 | self.search(k).is_some() | |
1072 | } | |
1073 | ||
1074 | /// Returns a mutable reference to the value corresponding to the key. | |
1075 | /// | |
1076 | /// The key may be any borrowed form of the map's key type, but | |
1077 | /// `Hash` and `Eq` on the borrowed form *must* match those for | |
1078 | /// the key type. | |
1079 | /// | |
c34b1796 | 1080 | /// # Examples |
1a4d82fc JJ |
1081 | /// |
1082 | /// ``` | |
1083 | /// use std::collections::HashMap; | |
1084 | /// | |
1085 | /// let mut map = HashMap::new(); | |
85aaf69f | 1086 | /// map.insert(1, "a"); |
9346a6ac AL |
1087 | /// if let Some(x) = map.get_mut(&1) { |
1088 | /// *x = "b"; | |
1a4d82fc | 1089 | /// } |
c34b1796 | 1090 | /// assert_eq!(map[&1], "b"); |
1a4d82fc | 1091 | /// ``` |
85aaf69f | 1092 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 1093 | pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V> |
85aaf69f | 1094 | where K: Borrow<Q>, Q: Hash + Eq |
1a4d82fc JJ |
1095 | { |
1096 | self.search_mut(k).map(|bucket| bucket.into_mut_refs().1) | |
1097 | } | |
1098 | ||
9346a6ac | 1099 | /// Inserts a key-value pair into the map. If the key already had a value |
1a4d82fc JJ |
1100 | /// present in the map, that value is returned. Otherwise, `None` is returned. |
1101 | /// | |
c34b1796 | 1102 | /// # Examples |
1a4d82fc JJ |
1103 | /// |
1104 | /// ``` | |
1105 | /// use std::collections::HashMap; | |
1106 | /// | |
1107 | /// let mut map = HashMap::new(); | |
85aaf69f | 1108 | /// assert_eq!(map.insert(37, "a"), None); |
1a4d82fc JJ |
1109 | /// assert_eq!(map.is_empty(), false); |
1110 | /// | |
1111 | /// map.insert(37, "b"); | |
1112 | /// assert_eq!(map.insert(37, "c"), Some("b")); | |
c34b1796 | 1113 | /// assert_eq!(map[&37], "c"); |
1a4d82fc | 1114 | /// ``` |
85aaf69f | 1115 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1116 | pub fn insert(&mut self, k: K, v: V) -> Option<V> { |
1117 | let hash = self.make_hash(&k); | |
1118 | self.reserve(1); | |
1119 | ||
1120 | let mut retval = None; | |
1121 | self.insert_or_replace_with(hash, k, v, |_, val_ref, val| { | |
1122 | retval = Some(replace(val_ref, val)); | |
1123 | }); | |
1124 | retval | |
1125 | } | |
1126 | ||
1127 | /// Removes a key from the map, returning the value at the key if the key | |
1128 | /// was previously in the map. | |
1129 | /// | |
1130 | /// The key may be any borrowed form of the map's key type, but | |
1131 | /// `Hash` and `Eq` on the borrowed form *must* match those for | |
1132 | /// the key type. | |
1133 | /// | |
c34b1796 | 1134 | /// # Examples |
1a4d82fc JJ |
1135 | /// |
1136 | /// ``` | |
1137 | /// use std::collections::HashMap; | |
1138 | /// | |
1139 | /// let mut map = HashMap::new(); | |
85aaf69f | 1140 | /// map.insert(1, "a"); |
1a4d82fc JJ |
1141 | /// assert_eq!(map.remove(&1), Some("a")); |
1142 | /// assert_eq!(map.remove(&1), None); | |
1143 | /// ``` | |
85aaf69f | 1144 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 1145 | pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V> |
85aaf69f | 1146 | where K: Borrow<Q>, Q: Hash + Eq |
1a4d82fc JJ |
1147 | { |
1148 | if self.table.size() == 0 { | |
1149 | return None | |
1150 | } | |
1151 | ||
1152 | self.search_mut(k).map(|bucket| pop_internal(bucket).1) | |
1153 | } | |
1154 | } | |
1155 | ||
1156 | fn search_entry_hashed<'a, K: Eq, V>(table: &'a mut RawTable<K,V>, hash: SafeHash, k: K) | |
1157 | -> Entry<'a, K, V> | |
1158 | { | |
1159 | // Worst case, we'll find one empty bucket among `size + 1` buckets. | |
1160 | let size = table.size(); | |
1161 | let mut probe = Bucket::new(table, hash); | |
1162 | let ib = probe.index(); | |
1163 | ||
1164 | loop { | |
1165 | let bucket = match probe.peek() { | |
1166 | Empty(bucket) => { | |
1167 | // Found a hole! | |
1168 | return Vacant(VacantEntry { | |
1169 | hash: hash, | |
1170 | key: k, | |
1171 | elem: NoElem(bucket), | |
1172 | }); | |
1173 | }, | |
1174 | Full(bucket) => bucket | |
1175 | }; | |
1176 | ||
1177 | // hash matches? | |
1178 | if bucket.hash() == hash { | |
1179 | // key matches? | |
1180 | if k == *bucket.read().0 { | |
1181 | return Occupied(OccupiedEntry{ | |
1182 | elem: bucket, | |
1183 | }); | |
1184 | } | |
1185 | } | |
1186 | ||
c34b1796 | 1187 | let robin_ib = bucket.index() as isize - bucket.distance() as isize; |
1a4d82fc | 1188 | |
c34b1796 | 1189 | if (ib as isize) < robin_ib { |
1a4d82fc JJ |
1190 | // Found a luckier bucket than me. Better steal his spot. |
1191 | return Vacant(VacantEntry { | |
1192 | hash: hash, | |
1193 | key: k, | |
85aaf69f | 1194 | elem: NeqElem(bucket, robin_ib as usize), |
1a4d82fc JJ |
1195 | }); |
1196 | } | |
1197 | ||
1198 | probe = bucket.next(); | |
1199 | assert!(probe.index() != ib + size + 1); | |
1200 | } | |
1201 | } | |
1202 | ||
85aaf69f SL |
1203 | impl<K, V, S> PartialEq for HashMap<K, V, S> |
1204 | where K: Eq + Hash, V: PartialEq, S: HashState | |
1a4d82fc JJ |
1205 | { |
1206 | fn eq(&self, other: &HashMap<K, V, S>) -> bool { | |
1207 | if self.len() != other.len() { return false; } | |
1208 | ||
1209 | self.iter().all(|(key, value)| | |
1210 | other.get(key).map_or(false, |v| *value == *v) | |
1211 | ) | |
1212 | } | |
1213 | } | |
1214 | ||
85aaf69f SL |
1215 | #[stable(feature = "rust1", since = "1.0.0")] |
1216 | impl<K, V, S> Eq for HashMap<K, V, S> | |
1217 | where K: Eq + Hash, V: Eq, S: HashState | |
1a4d82fc JJ |
1218 | {} |
1219 | ||
85aaf69f SL |
1220 | #[stable(feature = "rust1", since = "1.0.0")] |
1221 | impl<K, V, S> Debug for HashMap<K, V, S> | |
1222 | where K: Eq + Hash + Debug, V: Debug, S: HashState | |
1a4d82fc JJ |
1223 | { |
1224 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
c34b1796 | 1225 | self.iter().fold(f.debug_map(), |b, (k, v)| b.entry(k, v)).finish() |
1a4d82fc JJ |
1226 | } |
1227 | } | |
1228 | ||
85aaf69f SL |
1229 | #[stable(feature = "rust1", since = "1.0.0")] |
1230 | impl<K, V, S> Default for HashMap<K, V, S> | |
1231 | where K: Eq + Hash, | |
1232 | S: HashState + Default, | |
1a4d82fc JJ |
1233 | { |
1234 | fn default() -> HashMap<K, V, S> { | |
1235 | HashMap::with_hash_state(Default::default()) | |
1236 | } | |
1237 | } | |
1238 | ||
85aaf69f | 1239 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 | 1240 | impl<'a, K, Q: ?Sized, V, S> Index<&'a Q> for HashMap<K, V, S> |
85aaf69f SL |
1241 | where K: Eq + Hash + Borrow<Q>, |
1242 | Q: Eq + Hash, | |
1243 | S: HashState, | |
1a4d82fc JJ |
1244 | { |
1245 | type Output = V; | |
1246 | ||
1247 | #[inline] | |
c34b1796 | 1248 | fn index(&self, index: &Q) -> &V { |
1a4d82fc JJ |
1249 | self.get(index).expect("no entry found for key") |
1250 | } | |
1251 | } | |
1252 | ||
85aaf69f SL |
1253 | /// HashMap iterator. |
1254 | #[stable(feature = "rust1", since = "1.0.0")] | |
1a4d82fc JJ |
1255 | pub struct Iter<'a, K: 'a, V: 'a> { |
1256 | inner: table::Iter<'a, K, V> | |
1257 | } | |
1258 | ||
1259 | // FIXME(#19839) Remove in favor of `#[derive(Clone)]` | |
1260 | impl<'a, K, V> Clone for Iter<'a, K, V> { | |
1261 | fn clone(&self) -> Iter<'a, K, V> { | |
1262 | Iter { | |
1263 | inner: self.inner.clone() | |
1264 | } | |
1265 | } | |
1266 | } | |
1267 | ||
85aaf69f SL |
1268 | /// HashMap mutable values iterator. |
1269 | #[stable(feature = "rust1", since = "1.0.0")] | |
1a4d82fc JJ |
1270 | pub struct IterMut<'a, K: 'a, V: 'a> { |
1271 | inner: table::IterMut<'a, K, V> | |
1272 | } | |
1273 | ||
85aaf69f SL |
1274 | /// HashMap move iterator. |
1275 | #[stable(feature = "rust1", since = "1.0.0")] | |
1a4d82fc | 1276 | pub struct IntoIter<K, V> { |
85aaf69f | 1277 | inner: iter::Map<table::IntoIter<K, V>, fn((SafeHash, K, V)) -> (K, V)> |
1a4d82fc JJ |
1278 | } |
1279 | ||
85aaf69f SL |
1280 | /// HashMap keys iterator. |
1281 | #[stable(feature = "rust1", since = "1.0.0")] | |
1a4d82fc | 1282 | pub struct Keys<'a, K: 'a, V: 'a> { |
85aaf69f | 1283 | inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a K> |
1a4d82fc JJ |
1284 | } |
1285 | ||
1286 | // FIXME(#19839) Remove in favor of `#[derive(Clone)]` | |
1287 | impl<'a, K, V> Clone for Keys<'a, K, V> { | |
1288 | fn clone(&self) -> Keys<'a, K, V> { | |
1289 | Keys { | |
1290 | inner: self.inner.clone() | |
1291 | } | |
1292 | } | |
1293 | } | |
1294 | ||
85aaf69f SL |
1295 | /// HashMap values iterator. |
1296 | #[stable(feature = "rust1", since = "1.0.0")] | |
1a4d82fc | 1297 | pub struct Values<'a, K: 'a, V: 'a> { |
85aaf69f | 1298 | inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a V> |
1a4d82fc JJ |
1299 | } |
1300 | ||
1301 | // FIXME(#19839) Remove in favor of `#[derive(Clone)]` | |
1302 | impl<'a, K, V> Clone for Values<'a, K, V> { | |
1303 | fn clone(&self) -> Values<'a, K, V> { | |
1304 | Values { | |
1305 | inner: self.inner.clone() | |
1306 | } | |
1307 | } | |
1308 | } | |
1309 | ||
85aaf69f SL |
1310 | /// HashMap drain iterator. |
1311 | #[unstable(feature = "std_misc", | |
1312 | reason = "matches collection reform specification, waiting for dust to settle")] | |
1a4d82fc | 1313 | pub struct Drain<'a, K: 'a, V: 'a> { |
85aaf69f | 1314 | inner: iter::Map<table::Drain<'a, K, V>, fn((SafeHash, K, V)) -> (K, V)> |
1a4d82fc JJ |
1315 | } |
1316 | ||
85aaf69f | 1317 | /// A view into a single occupied location in a HashMap. |
c34b1796 | 1318 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1319 | pub struct OccupiedEntry<'a, K: 'a, V: 'a> { |
1320 | elem: FullBucket<K, V, &'a mut RawTable<K, V>>, | |
1321 | } | |
1322 | ||
85aaf69f | 1323 | /// A view into a single empty location in a HashMap. |
c34b1796 | 1324 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1325 | pub struct VacantEntry<'a, K: 'a, V: 'a> { |
1326 | hash: SafeHash, | |
1327 | key: K, | |
1328 | elem: VacantEntryState<K, V, &'a mut RawTable<K, V>>, | |
1329 | } | |
1330 | ||
85aaf69f | 1331 | /// A view into a single location in a map, which may be vacant or occupied. |
c34b1796 | 1332 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 1333 | pub enum Entry<'a, K: 'a, V: 'a> { |
85aaf69f | 1334 | /// An occupied Entry. |
c34b1796 | 1335 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 1336 | Occupied(OccupiedEntry<'a, K, V>), |
c34b1796 | 1337 | |
85aaf69f | 1338 | /// A vacant Entry. |
c34b1796 | 1339 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1340 | Vacant(VacantEntry<'a, K, V>), |
1341 | } | |
1342 | ||
85aaf69f | 1343 | /// Possible states of a VacantEntry. |
1a4d82fc JJ |
1344 | enum VacantEntryState<K, V, M> { |
1345 | /// The index is occupied, but the key to insert has precedence, | |
85aaf69f SL |
1346 | /// and will kick the current one out on insertion. |
1347 | NeqElem(FullBucket<K, V, M>, usize), | |
1348 | /// The index is genuinely vacant. | |
1a4d82fc JJ |
1349 | NoElem(EmptyBucket<K, V, M>), |
1350 | } | |
1351 | ||
85aaf69f SL |
1352 | #[stable(feature = "rust1", since = "1.0.0")] |
1353 | impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S> | |
1354 | where K: Eq + Hash, S: HashState | |
1355 | { | |
1356 | type Item = (&'a K, &'a V); | |
1357 | type IntoIter = Iter<'a, K, V>; | |
1358 | ||
1359 | fn into_iter(self) -> Iter<'a, K, V> { | |
1360 | self.iter() | |
1361 | } | |
1362 | } | |
1363 | ||
1364 | #[stable(feature = "rust1", since = "1.0.0")] | |
1365 | impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S> | |
1366 | where K: Eq + Hash, S: HashState | |
1367 | { | |
1368 | type Item = (&'a K, &'a mut V); | |
1369 | type IntoIter = IterMut<'a, K, V>; | |
1370 | ||
1371 | fn into_iter(mut self) -> IterMut<'a, K, V> { | |
1372 | self.iter_mut() | |
1373 | } | |
1374 | } | |
1375 | ||
1376 | #[stable(feature = "rust1", since = "1.0.0")] | |
1377 | impl<K, V, S> IntoIterator for HashMap<K, V, S> | |
1378 | where K: Eq + Hash, S: HashState | |
1379 | { | |
1380 | type Item = (K, V); | |
1381 | type IntoIter = IntoIter<K, V>; | |
1382 | ||
9346a6ac AL |
1383 | /// Creates a consuming iterator, that is, one that moves each key-value |
1384 | /// pair out of the map in arbitrary order. The map cannot be used after | |
1385 | /// calling this. | |
1386 | /// | |
1387 | /// # Examples | |
1388 | /// | |
1389 | /// ``` | |
1390 | /// use std::collections::HashMap; | |
1391 | /// | |
1392 | /// let mut map = HashMap::new(); | |
1393 | /// map.insert("a", 1); | |
1394 | /// map.insert("b", 2); | |
1395 | /// map.insert("c", 3); | |
1396 | /// | |
1397 | /// // Not possible with .iter() | |
1398 | /// let vec: Vec<(&str, isize)> = map.into_iter().collect(); | |
1399 | /// ``` | |
85aaf69f | 1400 | fn into_iter(self) -> IntoIter<K, V> { |
9346a6ac AL |
1401 | fn last_two<A, B, C>((_, b, c): (A, B, C)) -> (B, C) { (b, c) } |
1402 | let last_two: fn((SafeHash, K, V)) -> (K, V) = last_two; | |
1403 | ||
1404 | IntoIter { | |
1405 | inner: self.table.into_iter().map(last_two) | |
1406 | } | |
85aaf69f SL |
1407 | } |
1408 | } | |
1409 | ||
1410 | #[stable(feature = "rust1", since = "1.0.0")] | |
1a4d82fc JJ |
1411 | impl<'a, K, V> Iterator for Iter<'a, K, V> { |
1412 | type Item = (&'a K, &'a V); | |
1413 | ||
1414 | #[inline] fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() } | |
85aaf69f SL |
1415 | #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } |
1416 | } | |
1417 | #[stable(feature = "rust1", since = "1.0.0")] | |
1418 | impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> { | |
1419 | #[inline] fn len(&self) -> usize { self.inner.len() } | |
1a4d82fc JJ |
1420 | } |
1421 | ||
85aaf69f | 1422 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1423 | impl<'a, K, V> Iterator for IterMut<'a, K, V> { |
1424 | type Item = (&'a K, &'a mut V); | |
1425 | ||
1426 | #[inline] fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() } | |
85aaf69f SL |
1427 | #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } |
1428 | } | |
1429 | #[stable(feature = "rust1", since = "1.0.0")] | |
1430 | impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> { | |
1431 | #[inline] fn len(&self) -> usize { self.inner.len() } | |
1a4d82fc JJ |
1432 | } |
1433 | ||
85aaf69f | 1434 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1435 | impl<K, V> Iterator for IntoIter<K, V> { |
1436 | type Item = (K, V); | |
1437 | ||
1438 | #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() } | |
85aaf69f SL |
1439 | #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } |
1440 | } | |
1441 | #[stable(feature = "rust1", since = "1.0.0")] | |
1442 | impl<K, V> ExactSizeIterator for IntoIter<K, V> { | |
1443 | #[inline] fn len(&self) -> usize { self.inner.len() } | |
1a4d82fc JJ |
1444 | } |
1445 | ||
85aaf69f | 1446 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1447 | impl<'a, K, V> Iterator for Keys<'a, K, V> { |
1448 | type Item = &'a K; | |
1449 | ||
1450 | #[inline] fn next(&mut self) -> Option<(&'a K)> { self.inner.next() } | |
85aaf69f SL |
1451 | #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } |
1452 | } | |
1453 | #[stable(feature = "rust1", since = "1.0.0")] | |
1454 | impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> { | |
1455 | #[inline] fn len(&self) -> usize { self.inner.len() } | |
1a4d82fc JJ |
1456 | } |
1457 | ||
85aaf69f | 1458 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1459 | impl<'a, K, V> Iterator for Values<'a, K, V> { |
1460 | type Item = &'a V; | |
1461 | ||
1462 | #[inline] fn next(&mut self) -> Option<(&'a V)> { self.inner.next() } | |
85aaf69f SL |
1463 | #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } |
1464 | } | |
1465 | #[stable(feature = "rust1", since = "1.0.0")] | |
1466 | impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> { | |
1467 | #[inline] fn len(&self) -> usize { self.inner.len() } | |
1a4d82fc JJ |
1468 | } |
1469 | ||
85aaf69f SL |
1470 | #[stable(feature = "rust1", since = "1.0.0")] |
1471 | impl<'a, K, V> Iterator for Drain<'a, K, V> { | |
1a4d82fc JJ |
1472 | type Item = (K, V); |
1473 | ||
85aaf69f SL |
1474 | #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() } |
1475 | #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } | |
1476 | } | |
1477 | #[stable(feature = "rust1", since = "1.0.0")] | |
1478 | impl<'a, K, V> ExactSizeIterator for Drain<'a, K, V> { | |
1479 | #[inline] fn len(&self) -> usize { self.inner.len() } | |
1a4d82fc JJ |
1480 | } |
1481 | ||
1a4d82fc | 1482 | impl<'a, K, V> Entry<'a, K, V> { |
c34b1796 AL |
1483 | #[unstable(feature = "std_misc", |
1484 | reason = "will soon be replaced by or_insert")] | |
1485 | #[deprecated(since = "1.0", | |
1486 | reason = "replaced with more ergonomic `or_insert` and `or_insert_with`")] | |
1487 | /// Returns a mutable reference to the entry if occupied, or the VacantEntry if vacant | |
1a4d82fc JJ |
1488 | pub fn get(self) -> Result<&'a mut V, VacantEntry<'a, K, V>> { |
1489 | match self { | |
1490 | Occupied(entry) => Ok(entry.into_mut()), | |
1491 | Vacant(entry) => Err(entry), | |
1492 | } | |
1493 | } | |
c34b1796 AL |
1494 | |
1495 | #[stable(feature = "rust1", since = "1.0.0")] | |
1496 | /// Ensures a value is in the entry by inserting the default if empty, and returns | |
1497 | /// a mutable reference to the value in the entry. | |
1498 | pub fn or_insert(self, default: V) -> &'a mut V { | |
1499 | match self { | |
1500 | Occupied(entry) => entry.into_mut(), | |
1501 | Vacant(entry) => entry.insert(default), | |
1502 | } | |
1503 | } | |
1504 | ||
1505 | #[stable(feature = "rust1", since = "1.0.0")] | |
1506 | /// Ensures a value is in the entry by inserting the result of the default function if empty, | |
1507 | /// and returns a mutable reference to the value in the entry. | |
1508 | pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V { | |
1509 | match self { | |
1510 | Occupied(entry) => entry.into_mut(), | |
1511 | Vacant(entry) => entry.insert(default()), | |
1512 | } | |
1513 | } | |
1a4d82fc JJ |
1514 | } |
1515 | ||
1a4d82fc | 1516 | impl<'a, K, V> OccupiedEntry<'a, K, V> { |
85aaf69f SL |
1517 | /// Gets a reference to the value in the entry. |
1518 | #[stable(feature = "rust1", since = "1.0.0")] | |
1a4d82fc JJ |
1519 | pub fn get(&self) -> &V { |
1520 | self.elem.read().1 | |
1521 | } | |
1522 | ||
85aaf69f SL |
1523 | /// Gets a mutable reference to the value in the entry. |
1524 | #[stable(feature = "rust1", since = "1.0.0")] | |
1a4d82fc JJ |
1525 | pub fn get_mut(&mut self) -> &mut V { |
1526 | self.elem.read_mut().1 | |
1527 | } | |
1528 | ||
1529 | /// Converts the OccupiedEntry into a mutable reference to the value in the entry | |
1530 | /// with a lifetime bound to the map itself | |
85aaf69f | 1531 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1532 | pub fn into_mut(self) -> &'a mut V { |
1533 | self.elem.into_mut_refs().1 | |
1534 | } | |
1535 | ||
1536 | /// Sets the value of the entry, and returns the entry's old value | |
85aaf69f | 1537 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1538 | pub fn insert(&mut self, mut value: V) -> V { |
1539 | let old_value = self.get_mut(); | |
1540 | mem::swap(&mut value, old_value); | |
1541 | value | |
1542 | } | |
1543 | ||
1544 | /// Takes the value out of the entry, and returns it | |
85aaf69f | 1545 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1546 | pub fn remove(self) -> V { |
1547 | pop_internal(self.elem).1 | |
1548 | } | |
1549 | } | |
1550 | ||
1a4d82fc JJ |
1551 | impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V> { |
1552 | /// Sets the value of the entry with the VacantEntry's key, | |
1553 | /// and returns a mutable reference to it | |
85aaf69f | 1554 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1555 | pub fn insert(self, value: V) -> &'a mut V { |
1556 | match self.elem { | |
1557 | NeqElem(bucket, ib) => { | |
1558 | robin_hood(bucket, ib, self.hash, self.key, value) | |
1559 | } | |
1560 | NoElem(bucket) => { | |
1561 | bucket.put(self.hash, self.key, value).into_mut_refs().1 | |
1562 | } | |
1563 | } | |
1564 | } | |
1565 | } | |
1566 | ||
85aaf69f SL |
1567 | #[stable(feature = "rust1", since = "1.0.0")] |
1568 | impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S> | |
1569 | where K: Eq + Hash, S: HashState + Default | |
1a4d82fc | 1570 | { |
85aaf69f SL |
1571 | fn from_iter<T: IntoIterator<Item=(K, V)>>(iterable: T) -> HashMap<K, V, S> { |
1572 | let iter = iterable.into_iter(); | |
1a4d82fc JJ |
1573 | let lower = iter.size_hint().0; |
1574 | let mut map = HashMap::with_capacity_and_hash_state(lower, | |
1575 | Default::default()); | |
1576 | map.extend(iter); | |
1577 | map | |
1578 | } | |
1579 | } | |
1580 | ||
85aaf69f SL |
1581 | #[stable(feature = "rust1", since = "1.0.0")] |
1582 | impl<K, V, S> Extend<(K, V)> for HashMap<K, V, S> | |
1583 | where K: Eq + Hash, S: HashState | |
1a4d82fc | 1584 | { |
85aaf69f | 1585 | fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) { |
1a4d82fc JJ |
1586 | for (k, v) in iter { |
1587 | self.insert(k, v); | |
1588 | } | |
1589 | } | |
1590 | } | |
1591 | ||
1592 | ||
1593 | /// `RandomState` is the default state for `HashMap` types. | |
1594 | /// | |
1595 | /// A particular instance `RandomState` will create the same instances of | |
1596 | /// `Hasher`, but the hashers created by two different `RandomState` | |
1597 | /// instances are unlikely to produce the same result for the same values. | |
1598 | #[derive(Clone)] | |
85aaf69f SL |
1599 | #[unstable(feature = "std_misc", |
1600 | reason = "hashing an hash maps may be altered")] | |
1a4d82fc JJ |
1601 | pub struct RandomState { |
1602 | k0: u64, | |
1603 | k1: u64, | |
1604 | } | |
1605 | ||
85aaf69f SL |
1606 | #[unstable(feature = "std_misc", |
1607 | reason = "hashing an hash maps may be altered")] | |
1a4d82fc | 1608 | impl RandomState { |
9346a6ac | 1609 | /// Constructs a new `RandomState` that is initialized with random keys. |
1a4d82fc | 1610 | #[inline] |
85aaf69f | 1611 | #[allow(deprecated)] |
1a4d82fc JJ |
1612 | pub fn new() -> RandomState { |
1613 | let mut r = rand::thread_rng(); | |
1614 | RandomState { k0: r.gen(), k1: r.gen() } | |
1615 | } | |
1616 | } | |
1617 | ||
85aaf69f SL |
1618 | #[unstable(feature = "std_misc", |
1619 | reason = "hashing an hash maps may be altered")] | |
1a4d82fc | 1620 | impl HashState for RandomState { |
85aaf69f | 1621 | type Hasher = SipHasher; |
d9579d0f | 1622 | #[inline] |
85aaf69f SL |
1623 | fn hasher(&self) -> SipHasher { |
1624 | SipHasher::new_with_keys(self.k0, self.k1) | |
1a4d82fc JJ |
1625 | } |
1626 | } | |
1627 | ||
bd371182 | 1628 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1629 | impl Default for RandomState { |
1630 | #[inline] | |
1631 | fn default() -> RandomState { | |
1632 | RandomState::new() | |
1633 | } | |
1634 | } | |
1635 | ||
1a4d82fc JJ |
1636 | #[cfg(test)] |
1637 | mod test_map { | |
1638 | use prelude::v1::*; | |
1639 | ||
1640 | use super::HashMap; | |
1641 | use super::Entry::{Occupied, Vacant}; | |
9346a6ac | 1642 | use iter::{range_inclusive, repeat}; |
1a4d82fc | 1643 | use cell::RefCell; |
9346a6ac | 1644 | use rand::{thread_rng, Rng}; |
1a4d82fc JJ |
1645 | |
1646 | #[test] | |
1647 | fn test_create_capacity_zero() { | |
1648 | let mut m = HashMap::with_capacity(0); | |
1649 | ||
85aaf69f | 1650 | assert!(m.insert(1, 1).is_none()); |
1a4d82fc JJ |
1651 | |
1652 | assert!(m.contains_key(&1)); | |
1653 | assert!(!m.contains_key(&0)); | |
1654 | } | |
1655 | ||
1656 | #[test] | |
1657 | fn test_insert() { | |
1658 | let mut m = HashMap::new(); | |
1659 | assert_eq!(m.len(), 0); | |
85aaf69f | 1660 | assert!(m.insert(1, 2).is_none()); |
1a4d82fc | 1661 | assert_eq!(m.len(), 1); |
85aaf69f | 1662 | assert!(m.insert(2, 4).is_none()); |
1a4d82fc JJ |
1663 | assert_eq!(m.len(), 2); |
1664 | assert_eq!(*m.get(&1).unwrap(), 2); | |
1665 | assert_eq!(*m.get(&2).unwrap(), 4); | |
1666 | } | |
1667 | ||
c34b1796 | 1668 | thread_local! { static DROP_VECTOR: RefCell<Vec<isize>> = RefCell::new(Vec::new()) } |
1a4d82fc JJ |
1669 | |
1670 | #[derive(Hash, PartialEq, Eq)] | |
1671 | struct Dropable { | |
85aaf69f | 1672 | k: usize |
1a4d82fc JJ |
1673 | } |
1674 | ||
1675 | impl Dropable { | |
85aaf69f | 1676 | fn new(k: usize) -> Dropable { |
1a4d82fc JJ |
1677 | DROP_VECTOR.with(|slot| { |
1678 | slot.borrow_mut()[k] += 1; | |
1679 | }); | |
1680 | ||
1681 | Dropable { k: k } | |
1682 | } | |
1683 | } | |
1684 | ||
1685 | impl Drop for Dropable { | |
1686 | fn drop(&mut self) { | |
1687 | DROP_VECTOR.with(|slot| { | |
1688 | slot.borrow_mut()[self.k] -= 1; | |
1689 | }); | |
1690 | } | |
1691 | } | |
1692 | ||
1693 | impl Clone for Dropable { | |
1694 | fn clone(&self) -> Dropable { | |
1695 | Dropable::new(self.k) | |
1696 | } | |
1697 | } | |
1698 | ||
1699 | #[test] | |
1700 | fn test_drops() { | |
1701 | DROP_VECTOR.with(|slot| { | |
85aaf69f | 1702 | *slot.borrow_mut() = repeat(0).take(200).collect(); |
1a4d82fc JJ |
1703 | }); |
1704 | ||
1705 | { | |
1706 | let mut m = HashMap::new(); | |
1707 | ||
1708 | DROP_VECTOR.with(|v| { | |
85aaf69f | 1709 | for i in 0..200 { |
1a4d82fc JJ |
1710 | assert_eq!(v.borrow()[i], 0); |
1711 | } | |
1712 | }); | |
1713 | ||
85aaf69f | 1714 | for i in 0..100 { |
1a4d82fc JJ |
1715 | let d1 = Dropable::new(i); |
1716 | let d2 = Dropable::new(i+100); | |
1717 | m.insert(d1, d2); | |
1718 | } | |
1719 | ||
1720 | DROP_VECTOR.with(|v| { | |
85aaf69f | 1721 | for i in 0..200 { |
1a4d82fc JJ |
1722 | assert_eq!(v.borrow()[i], 1); |
1723 | } | |
1724 | }); | |
1725 | ||
85aaf69f | 1726 | for i in 0..50 { |
1a4d82fc JJ |
1727 | let k = Dropable::new(i); |
1728 | let v = m.remove(&k); | |
1729 | ||
1730 | assert!(v.is_some()); | |
1731 | ||
1732 | DROP_VECTOR.with(|v| { | |
1733 | assert_eq!(v.borrow()[i], 1); | |
1734 | assert_eq!(v.borrow()[i+100], 1); | |
1735 | }); | |
1736 | } | |
1737 | ||
1738 | DROP_VECTOR.with(|v| { | |
85aaf69f | 1739 | for i in 0..50 { |
1a4d82fc JJ |
1740 | assert_eq!(v.borrow()[i], 0); |
1741 | assert_eq!(v.borrow()[i+100], 0); | |
1742 | } | |
1743 | ||
85aaf69f | 1744 | for i in 50..100 { |
1a4d82fc JJ |
1745 | assert_eq!(v.borrow()[i], 1); |
1746 | assert_eq!(v.borrow()[i+100], 1); | |
1747 | } | |
1748 | }); | |
1749 | } | |
1750 | ||
1751 | DROP_VECTOR.with(|v| { | |
85aaf69f | 1752 | for i in 0..200 { |
1a4d82fc JJ |
1753 | assert_eq!(v.borrow()[i], 0); |
1754 | } | |
1755 | }); | |
1756 | } | |
1757 | ||
1758 | #[test] | |
1759 | fn test_move_iter_drops() { | |
1760 | DROP_VECTOR.with(|v| { | |
1761 | *v.borrow_mut() = repeat(0).take(200).collect(); | |
1762 | }); | |
1763 | ||
1764 | let hm = { | |
1765 | let mut hm = HashMap::new(); | |
1766 | ||
1767 | DROP_VECTOR.with(|v| { | |
85aaf69f | 1768 | for i in 0..200 { |
1a4d82fc JJ |
1769 | assert_eq!(v.borrow()[i], 0); |
1770 | } | |
1771 | }); | |
1772 | ||
85aaf69f | 1773 | for i in 0..100 { |
1a4d82fc JJ |
1774 | let d1 = Dropable::new(i); |
1775 | let d2 = Dropable::new(i+100); | |
1776 | hm.insert(d1, d2); | |
1777 | } | |
1778 | ||
1779 | DROP_VECTOR.with(|v| { | |
85aaf69f | 1780 | for i in 0..200 { |
1a4d82fc JJ |
1781 | assert_eq!(v.borrow()[i], 1); |
1782 | } | |
1783 | }); | |
1784 | ||
1785 | hm | |
1786 | }; | |
1787 | ||
1788 | // By the way, ensure that cloning doesn't screw up the dropping. | |
1789 | drop(hm.clone()); | |
1790 | ||
1791 | { | |
1792 | let mut half = hm.into_iter().take(50); | |
1793 | ||
1794 | DROP_VECTOR.with(|v| { | |
85aaf69f | 1795 | for i in 0..200 { |
1a4d82fc JJ |
1796 | assert_eq!(v.borrow()[i], 1); |
1797 | } | |
1798 | }); | |
1799 | ||
85aaf69f | 1800 | for _ in half.by_ref() {} |
1a4d82fc JJ |
1801 | |
1802 | DROP_VECTOR.with(|v| { | |
85aaf69f | 1803 | let nk = (0..100).filter(|&i| { |
1a4d82fc JJ |
1804 | v.borrow()[i] == 1 |
1805 | }).count(); | |
1806 | ||
85aaf69f | 1807 | let nv = (0..100).filter(|&i| { |
1a4d82fc JJ |
1808 | v.borrow()[i+100] == 1 |
1809 | }).count(); | |
1810 | ||
1811 | assert_eq!(nk, 50); | |
1812 | assert_eq!(nv, 50); | |
1813 | }); | |
1814 | }; | |
1815 | ||
1816 | DROP_VECTOR.with(|v| { | |
85aaf69f | 1817 | for i in 0..200 { |
1a4d82fc JJ |
1818 | assert_eq!(v.borrow()[i], 0); |
1819 | } | |
1820 | }); | |
1821 | } | |
1822 | ||
1823 | #[test] | |
1824 | fn test_empty_pop() { | |
c34b1796 | 1825 | let mut m: HashMap<isize, bool> = HashMap::new(); |
1a4d82fc JJ |
1826 | assert_eq!(m.remove(&0), None); |
1827 | } | |
1828 | ||
1829 | #[test] | |
1830 | fn test_lots_of_insertions() { | |
1831 | let mut m = HashMap::new(); | |
1832 | ||
1833 | // Try this a few times to make sure we never screw up the hashmap's | |
1834 | // internal state. | |
85aaf69f | 1835 | for _ in 0..10 { |
1a4d82fc JJ |
1836 | assert!(m.is_empty()); |
1837 | ||
85aaf69f | 1838 | for i in range_inclusive(1, 1000) { |
1a4d82fc JJ |
1839 | assert!(m.insert(i, i).is_none()); |
1840 | ||
1841 | for j in range_inclusive(1, i) { | |
1842 | let r = m.get(&j); | |
1843 | assert_eq!(r, Some(&j)); | |
1844 | } | |
1845 | ||
1846 | for j in range_inclusive(i+1, 1000) { | |
1847 | let r = m.get(&j); | |
1848 | assert_eq!(r, None); | |
1849 | } | |
1850 | } | |
1851 | ||
85aaf69f | 1852 | for i in range_inclusive(1001, 2000) { |
1a4d82fc JJ |
1853 | assert!(!m.contains_key(&i)); |
1854 | } | |
1855 | ||
1856 | // remove forwards | |
85aaf69f | 1857 | for i in range_inclusive(1, 1000) { |
1a4d82fc JJ |
1858 | assert!(m.remove(&i).is_some()); |
1859 | ||
1860 | for j in range_inclusive(1, i) { | |
1861 | assert!(!m.contains_key(&j)); | |
1862 | } | |
1863 | ||
1864 | for j in range_inclusive(i+1, 1000) { | |
1865 | assert!(m.contains_key(&j)); | |
1866 | } | |
1867 | } | |
1868 | ||
85aaf69f | 1869 | for i in range_inclusive(1, 1000) { |
1a4d82fc JJ |
1870 | assert!(!m.contains_key(&i)); |
1871 | } | |
1872 | ||
85aaf69f | 1873 | for i in range_inclusive(1, 1000) { |
1a4d82fc JJ |
1874 | assert!(m.insert(i, i).is_none()); |
1875 | } | |
1876 | ||
1877 | // remove backwards | |
9346a6ac | 1878 | for i in (1..1001).rev() { |
1a4d82fc JJ |
1879 | assert!(m.remove(&i).is_some()); |
1880 | ||
1881 | for j in range_inclusive(i, 1000) { | |
1882 | assert!(!m.contains_key(&j)); | |
1883 | } | |
1884 | ||
1885 | for j in range_inclusive(1, i-1) { | |
1886 | assert!(m.contains_key(&j)); | |
1887 | } | |
1888 | } | |
1889 | } | |
1890 | } | |
1891 | ||
1892 | #[test] | |
1893 | fn test_find_mut() { | |
1894 | let mut m = HashMap::new(); | |
85aaf69f SL |
1895 | assert!(m.insert(1, 12).is_none()); |
1896 | assert!(m.insert(2, 8).is_none()); | |
1897 | assert!(m.insert(5, 14).is_none()); | |
1a4d82fc JJ |
1898 | let new = 100; |
1899 | match m.get_mut(&5) { | |
1900 | None => panic!(), Some(x) => *x = new | |
1901 | } | |
1902 | assert_eq!(m.get(&5), Some(&new)); | |
1903 | } | |
1904 | ||
1905 | #[test] | |
1906 | fn test_insert_overwrite() { | |
1907 | let mut m = HashMap::new(); | |
85aaf69f | 1908 | assert!(m.insert(1, 2).is_none()); |
1a4d82fc | 1909 | assert_eq!(*m.get(&1).unwrap(), 2); |
85aaf69f | 1910 | assert!(!m.insert(1, 3).is_none()); |
1a4d82fc JJ |
1911 | assert_eq!(*m.get(&1).unwrap(), 3); |
1912 | } | |
1913 | ||
1914 | #[test] | |
1915 | fn test_insert_conflicts() { | |
1916 | let mut m = HashMap::with_capacity(4); | |
85aaf69f SL |
1917 | assert!(m.insert(1, 2).is_none()); |
1918 | assert!(m.insert(5, 3).is_none()); | |
1919 | assert!(m.insert(9, 4).is_none()); | |
1a4d82fc JJ |
1920 | assert_eq!(*m.get(&9).unwrap(), 4); |
1921 | assert_eq!(*m.get(&5).unwrap(), 3); | |
1922 | assert_eq!(*m.get(&1).unwrap(), 2); | |
1923 | } | |
1924 | ||
1925 | #[test] | |
1926 | fn test_conflict_remove() { | |
1927 | let mut m = HashMap::with_capacity(4); | |
85aaf69f | 1928 | assert!(m.insert(1, 2).is_none()); |
1a4d82fc JJ |
1929 | assert_eq!(*m.get(&1).unwrap(), 2); |
1930 | assert!(m.insert(5, 3).is_none()); | |
1931 | assert_eq!(*m.get(&1).unwrap(), 2); | |
1932 | assert_eq!(*m.get(&5).unwrap(), 3); | |
1933 | assert!(m.insert(9, 4).is_none()); | |
1934 | assert_eq!(*m.get(&1).unwrap(), 2); | |
1935 | assert_eq!(*m.get(&5).unwrap(), 3); | |
1936 | assert_eq!(*m.get(&9).unwrap(), 4); | |
1937 | assert!(m.remove(&1).is_some()); | |
1938 | assert_eq!(*m.get(&9).unwrap(), 4); | |
1939 | assert_eq!(*m.get(&5).unwrap(), 3); | |
1940 | } | |
1941 | ||
1942 | #[test] | |
1943 | fn test_is_empty() { | |
1944 | let mut m = HashMap::with_capacity(4); | |
85aaf69f | 1945 | assert!(m.insert(1, 2).is_none()); |
1a4d82fc JJ |
1946 | assert!(!m.is_empty()); |
1947 | assert!(m.remove(&1).is_some()); | |
1948 | assert!(m.is_empty()); | |
1949 | } | |
1950 | ||
1951 | #[test] | |
1952 | fn test_pop() { | |
1953 | let mut m = HashMap::new(); | |
85aaf69f | 1954 | m.insert(1, 2); |
1a4d82fc JJ |
1955 | assert_eq!(m.remove(&1), Some(2)); |
1956 | assert_eq!(m.remove(&1), None); | |
1957 | } | |
1958 | ||
1959 | #[test] | |
1960 | fn test_iterate() { | |
1961 | let mut m = HashMap::with_capacity(4); | |
85aaf69f | 1962 | for i in 0..32 { |
1a4d82fc JJ |
1963 | assert!(m.insert(i, i*2).is_none()); |
1964 | } | |
1965 | assert_eq!(m.len(), 32); | |
1966 | ||
1967 | let mut observed: u32 = 0; | |
1968 | ||
85aaf69f | 1969 | for (k, v) in &m { |
1a4d82fc JJ |
1970 | assert_eq!(*v, *k * 2); |
1971 | observed |= 1 << *k; | |
1972 | } | |
1973 | assert_eq!(observed, 0xFFFF_FFFF); | |
1974 | } | |
1975 | ||
1976 | #[test] | |
1977 | fn test_keys() { | |
85aaf69f SL |
1978 | let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; |
1979 | let map: HashMap<_, _> = vec.into_iter().collect(); | |
1980 | let keys: Vec<_> = map.keys().cloned().collect(); | |
1a4d82fc JJ |
1981 | assert_eq!(keys.len(), 3); |
1982 | assert!(keys.contains(&1)); | |
1983 | assert!(keys.contains(&2)); | |
1984 | assert!(keys.contains(&3)); | |
1985 | } | |
1986 | ||
1987 | #[test] | |
1988 | fn test_values() { | |
85aaf69f SL |
1989 | let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; |
1990 | let map: HashMap<_, _> = vec.into_iter().collect(); | |
1991 | let values: Vec<_> = map.values().cloned().collect(); | |
1a4d82fc JJ |
1992 | assert_eq!(values.len(), 3); |
1993 | assert!(values.contains(&'a')); | |
1994 | assert!(values.contains(&'b')); | |
1995 | assert!(values.contains(&'c')); | |
1996 | } | |
1997 | ||
1998 | #[test] | |
1999 | fn test_find() { | |
2000 | let mut m = HashMap::new(); | |
85aaf69f SL |
2001 | assert!(m.get(&1).is_none()); |
2002 | m.insert(1, 2); | |
1a4d82fc JJ |
2003 | match m.get(&1) { |
2004 | None => panic!(), | |
2005 | Some(v) => assert_eq!(*v, 2) | |
2006 | } | |
2007 | } | |
2008 | ||
2009 | #[test] | |
2010 | fn test_eq() { | |
2011 | let mut m1 = HashMap::new(); | |
85aaf69f SL |
2012 | m1.insert(1, 2); |
2013 | m1.insert(2, 3); | |
2014 | m1.insert(3, 4); | |
1a4d82fc JJ |
2015 | |
2016 | let mut m2 = HashMap::new(); | |
85aaf69f SL |
2017 | m2.insert(1, 2); |
2018 | m2.insert(2, 3); | |
1a4d82fc JJ |
2019 | |
2020 | assert!(m1 != m2); | |
2021 | ||
85aaf69f | 2022 | m2.insert(3, 4); |
1a4d82fc JJ |
2023 | |
2024 | assert_eq!(m1, m2); | |
2025 | } | |
2026 | ||
2027 | #[test] | |
2028 | fn test_show() { | |
85aaf69f SL |
2029 | let mut map = HashMap::new(); |
2030 | let empty: HashMap<i32, i32> = HashMap::new(); | |
1a4d82fc | 2031 | |
85aaf69f SL |
2032 | map.insert(1, 2); |
2033 | map.insert(3, 4); | |
1a4d82fc JJ |
2034 | |
2035 | let map_str = format!("{:?}", map); | |
2036 | ||
c34b1796 AL |
2037 | assert!(map_str == "{1: 2, 3: 4}" || |
2038 | map_str == "{3: 4, 1: 2}"); | |
2039 | assert_eq!(format!("{:?}", empty), "{}"); | |
1a4d82fc JJ |
2040 | } |
2041 | ||
2042 | #[test] | |
2043 | fn test_expand() { | |
2044 | let mut m = HashMap::new(); | |
2045 | ||
2046 | assert_eq!(m.len(), 0); | |
2047 | assert!(m.is_empty()); | |
2048 | ||
85aaf69f | 2049 | let mut i = 0; |
1a4d82fc JJ |
2050 | let old_cap = m.table.capacity(); |
2051 | while old_cap == m.table.capacity() { | |
2052 | m.insert(i, i); | |
2053 | i += 1; | |
2054 | } | |
2055 | ||
2056 | assert_eq!(m.len(), i); | |
2057 | assert!(!m.is_empty()); | |
2058 | } | |
2059 | ||
2060 | #[test] | |
2061 | fn test_behavior_resize_policy() { | |
2062 | let mut m = HashMap::new(); | |
2063 | ||
2064 | assert_eq!(m.len(), 0); | |
2065 | assert_eq!(m.table.capacity(), 0); | |
2066 | assert!(m.is_empty()); | |
2067 | ||
2068 | m.insert(0, 0); | |
2069 | m.remove(&0); | |
2070 | assert!(m.is_empty()); | |
2071 | let initial_cap = m.table.capacity(); | |
2072 | m.reserve(initial_cap); | |
2073 | let cap = m.table.capacity(); | |
2074 | ||
2075 | assert_eq!(cap, initial_cap * 2); | |
2076 | ||
85aaf69f SL |
2077 | let mut i = 0; |
2078 | for _ in 0..cap * 3 / 4 { | |
1a4d82fc JJ |
2079 | m.insert(i, i); |
2080 | i += 1; | |
2081 | } | |
2082 | // three quarters full | |
2083 | ||
2084 | assert_eq!(m.len(), i); | |
2085 | assert_eq!(m.table.capacity(), cap); | |
2086 | ||
85aaf69f | 2087 | for _ in 0..cap / 4 { |
1a4d82fc JJ |
2088 | m.insert(i, i); |
2089 | i += 1; | |
2090 | } | |
2091 | // half full | |
2092 | ||
2093 | let new_cap = m.table.capacity(); | |
2094 | assert_eq!(new_cap, cap * 2); | |
2095 | ||
85aaf69f | 2096 | for _ in 0..cap / 2 - 1 { |
1a4d82fc JJ |
2097 | i -= 1; |
2098 | m.remove(&i); | |
2099 | assert_eq!(m.table.capacity(), new_cap); | |
2100 | } | |
2101 | // A little more than one quarter full. | |
2102 | m.shrink_to_fit(); | |
2103 | assert_eq!(m.table.capacity(), cap); | |
2104 | // again, a little more than half full | |
85aaf69f | 2105 | for _ in 0..cap / 2 - 1 { |
1a4d82fc JJ |
2106 | i -= 1; |
2107 | m.remove(&i); | |
2108 | } | |
2109 | m.shrink_to_fit(); | |
2110 | ||
2111 | assert_eq!(m.len(), i); | |
2112 | assert!(!m.is_empty()); | |
2113 | assert_eq!(m.table.capacity(), initial_cap); | |
2114 | } | |
2115 | ||
2116 | #[test] | |
2117 | fn test_reserve_shrink_to_fit() { | |
2118 | let mut m = HashMap::new(); | |
85aaf69f | 2119 | m.insert(0, 0); |
1a4d82fc JJ |
2120 | m.remove(&0); |
2121 | assert!(m.capacity() >= m.len()); | |
85aaf69f | 2122 | for i in 0..128 { |
1a4d82fc JJ |
2123 | m.insert(i, i); |
2124 | } | |
2125 | m.reserve(256); | |
2126 | ||
2127 | let usable_cap = m.capacity(); | |
85aaf69f | 2128 | for i in 128..(128 + 256) { |
1a4d82fc JJ |
2129 | m.insert(i, i); |
2130 | assert_eq!(m.capacity(), usable_cap); | |
2131 | } | |
2132 | ||
85aaf69f | 2133 | for i in 100..(128 + 256) { |
1a4d82fc JJ |
2134 | assert_eq!(m.remove(&i), Some(i)); |
2135 | } | |
2136 | m.shrink_to_fit(); | |
2137 | ||
2138 | assert_eq!(m.len(), 100); | |
2139 | assert!(!m.is_empty()); | |
2140 | assert!(m.capacity() >= m.len()); | |
2141 | ||
85aaf69f | 2142 | for i in 0..100 { |
1a4d82fc JJ |
2143 | assert_eq!(m.remove(&i), Some(i)); |
2144 | } | |
2145 | m.shrink_to_fit(); | |
2146 | m.insert(0, 0); | |
2147 | ||
2148 | assert_eq!(m.len(), 1); | |
2149 | assert!(m.capacity() >= m.len()); | |
2150 | assert_eq!(m.remove(&0), Some(0)); | |
2151 | } | |
2152 | ||
1a4d82fc JJ |
2153 | #[test] |
2154 | fn test_from_iter() { | |
85aaf69f | 2155 | let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; |
1a4d82fc | 2156 | |
85aaf69f | 2157 | let map: HashMap<_, _> = xs.iter().cloned().collect(); |
1a4d82fc | 2158 | |
85aaf69f | 2159 | for &(k, v) in &xs { |
1a4d82fc JJ |
2160 | assert_eq!(map.get(&k), Some(&v)); |
2161 | } | |
2162 | } | |
2163 | ||
2164 | #[test] | |
2165 | fn test_size_hint() { | |
85aaf69f | 2166 | let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; |
1a4d82fc | 2167 | |
85aaf69f | 2168 | let map: HashMap<_, _> = xs.iter().cloned().collect(); |
1a4d82fc JJ |
2169 | |
2170 | let mut iter = map.iter(); | |
2171 | ||
2172 | for _ in iter.by_ref().take(3) {} | |
2173 | ||
2174 | assert_eq!(iter.size_hint(), (3, Some(3))); | |
2175 | } | |
2176 | ||
85aaf69f SL |
2177 | #[test] |
2178 | fn test_iter_len() { | |
2179 | let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; | |
2180 | ||
2181 | let map: HashMap<_, _> = xs.iter().cloned().collect(); | |
2182 | ||
2183 | let mut iter = map.iter(); | |
2184 | ||
2185 | for _ in iter.by_ref().take(3) {} | |
2186 | ||
2187 | assert_eq!(iter.len(), 3); | |
2188 | } | |
2189 | ||
1a4d82fc JJ |
2190 | #[test] |
2191 | fn test_mut_size_hint() { | |
85aaf69f | 2192 | let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; |
1a4d82fc | 2193 | |
85aaf69f | 2194 | let mut map: HashMap<_, _> = xs.iter().cloned().collect(); |
1a4d82fc JJ |
2195 | |
2196 | let mut iter = map.iter_mut(); | |
2197 | ||
2198 | for _ in iter.by_ref().take(3) {} | |
2199 | ||
2200 | assert_eq!(iter.size_hint(), (3, Some(3))); | |
2201 | } | |
2202 | ||
85aaf69f SL |
2203 | #[test] |
2204 | fn test_iter_mut_len() { | |
2205 | let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; | |
2206 | ||
2207 | let mut map: HashMap<_, _> = xs.iter().cloned().collect(); | |
2208 | ||
2209 | let mut iter = map.iter_mut(); | |
2210 | ||
2211 | for _ in iter.by_ref().take(3) {} | |
2212 | ||
2213 | assert_eq!(iter.len(), 3); | |
2214 | } | |
2215 | ||
1a4d82fc JJ |
2216 | #[test] |
2217 | fn test_index() { | |
85aaf69f | 2218 | let mut map = HashMap::new(); |
1a4d82fc JJ |
2219 | |
2220 | map.insert(1, 2); | |
2221 | map.insert(2, 1); | |
2222 | map.insert(3, 4); | |
2223 | ||
c34b1796 | 2224 | assert_eq!(map[&2], 1); |
1a4d82fc JJ |
2225 | } |
2226 | ||
2227 | #[test] | |
c34b1796 | 2228 | #[should_panic] |
1a4d82fc | 2229 | fn test_index_nonexistent() { |
85aaf69f | 2230 | let mut map = HashMap::new(); |
1a4d82fc JJ |
2231 | |
2232 | map.insert(1, 2); | |
2233 | map.insert(2, 1); | |
2234 | map.insert(3, 4); | |
2235 | ||
c34b1796 | 2236 | map[&4]; |
1a4d82fc JJ |
2237 | } |
2238 | ||
2239 | #[test] | |
2240 | fn test_entry(){ | |
85aaf69f | 2241 | let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)]; |
1a4d82fc | 2242 | |
85aaf69f | 2243 | let mut map: HashMap<_, _> = xs.iter().cloned().collect(); |
1a4d82fc JJ |
2244 | |
2245 | // Existing key (insert) | |
2246 | match map.entry(1) { | |
2247 | Vacant(_) => unreachable!(), | |
2248 | Occupied(mut view) => { | |
2249 | assert_eq!(view.get(), &10); | |
2250 | assert_eq!(view.insert(100), 10); | |
2251 | } | |
2252 | } | |
2253 | assert_eq!(map.get(&1).unwrap(), &100); | |
2254 | assert_eq!(map.len(), 6); | |
2255 | ||
2256 | ||
2257 | // Existing key (update) | |
2258 | match map.entry(2) { | |
2259 | Vacant(_) => unreachable!(), | |
2260 | Occupied(mut view) => { | |
2261 | let v = view.get_mut(); | |
2262 | let new_v = (*v) * 10; | |
2263 | *v = new_v; | |
2264 | } | |
2265 | } | |
2266 | assert_eq!(map.get(&2).unwrap(), &200); | |
2267 | assert_eq!(map.len(), 6); | |
2268 | ||
2269 | // Existing key (take) | |
2270 | match map.entry(3) { | |
2271 | Vacant(_) => unreachable!(), | |
2272 | Occupied(view) => { | |
2273 | assert_eq!(view.remove(), 30); | |
2274 | } | |
2275 | } | |
2276 | assert_eq!(map.get(&3), None); | |
2277 | assert_eq!(map.len(), 5); | |
2278 | ||
2279 | ||
2280 | // Inexistent key (insert) | |
2281 | match map.entry(10) { | |
2282 | Occupied(_) => unreachable!(), | |
2283 | Vacant(view) => { | |
2284 | assert_eq!(*view.insert(1000), 1000); | |
2285 | } | |
2286 | } | |
2287 | assert_eq!(map.get(&10).unwrap(), &1000); | |
2288 | assert_eq!(map.len(), 6); | |
2289 | } | |
2290 | ||
2291 | #[test] | |
2292 | fn test_entry_take_doesnt_corrupt() { | |
c34b1796 | 2293 | #![allow(deprecated)] //rand |
1a4d82fc | 2294 | // Test for #19292 |
85aaf69f | 2295 | fn check(m: &HashMap<isize, ()>) { |
1a4d82fc JJ |
2296 | for k in m.keys() { |
2297 | assert!(m.contains_key(k), | |
2298 | "{} is in keys() but not in the map?", k); | |
2299 | } | |
2300 | } | |
2301 | ||
2302 | let mut m = HashMap::new(); | |
9346a6ac | 2303 | let mut rng = thread_rng(); |
1a4d82fc JJ |
2304 | |
2305 | // Populate the map with some items. | |
85aaf69f | 2306 | for _ in 0..50 { |
1a4d82fc JJ |
2307 | let x = rng.gen_range(-10, 10); |
2308 | m.insert(x, ()); | |
2309 | } | |
2310 | ||
85aaf69f | 2311 | for i in 0..1000 { |
1a4d82fc JJ |
2312 | let x = rng.gen_range(-10, 10); |
2313 | match m.entry(x) { | |
2314 | Vacant(_) => {}, | |
2315 | Occupied(e) => { | |
2316 | println!("{}: remove {}", i, x); | |
2317 | e.remove(); | |
2318 | }, | |
2319 | } | |
2320 | ||
2321 | check(&m); | |
2322 | } | |
2323 | } | |
2324 | } |