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