(index<- ) ./libstd/hashmap.rs
1 // Copyright 2013 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10
11 //! An unordered map and set type implemented as hash tables
12 //!
13 //! The tables use a keyed hash with new random keys generated for each container, so the ordering
14 //! of a set of keys in a hash table is randomized.
15
16 #[mutable_doc];
17
18 use container::{Container, Mutable, Map, MutableMap, Set, MutableSet};
19 use clone::Clone;
20 use cmp::{Eq, Equiv};
21 use default::Default;
22 use hash::Hash;
23 use iter::{Iterator, FromIterator, Extendable};
24 use iter::{FilterMap, Chain, Repeat, Zip};
25 use num;
26 use option::{None, Option, Some};
27 use rand::Rng;
28 use rand;
29 use uint;
30 use util::replace;
31 use vec::{ImmutableVector, MutableVector, OwnedVector};
32 use vec;
33
34 static INITIAL_CAPACITY: uint = 32u; // 2^5
35
36 struct Bucket<K,V> {
37 hash: uint,
38 key: K,
39 value: V,
40 }
41
42 /// A hash map implementation which uses linear probing along with the SipHash
43 /// hash function for internal state. This means that the order of all hash maps
44 /// is randomized by keying each hash map randomly on creation.
45 ///
46 /// It is required that the keys implement the `Eq` and `Hash` traits, although
47 /// this can frequently be achieved by just implementing the `Eq` and
48 /// `IterBytes` traits as `Hash` is automatically implemented for types that
49 /// implement `IterBytes`.
50 pub struct HashMap<K,V> {
51 priv k0: u64,
52 priv k1: u64,
53 priv resize_at: uint,
54 priv size: uint,
55 priv buckets: ~[Option<Bucket<K, V>>],
56 }
57
58 // We could rewrite FoundEntry to have type Option<&Bucket<K, V>>
59 // which would be nifty
60 enum SearchResult {
61 FoundEntry(uint), FoundHole(uint), TableFull
62 }
63
64 #[inline]
65 fn resize_at(capacity: uint) -> uint {
66 (capacity * 3) / 4
67 }
68
69 impl<K:Hash + Eq,V> HashMap<K, V> {
70 #[inline]
71 fn to_bucket(&self, h: uint) -> uint {
72 // A good hash function with entropy spread over all of the
73 // bits is assumed. SipHash is more than good enough.
74 h % self.buckets.len()
75 }
76
77 #[inline]
78 fn next_bucket(&self, idx: uint, len_buckets: uint) -> uint {
79 (idx + 1) % len_buckets
80 }
81
82 #[inline]
83 fn bucket_sequence(&self, hash: uint,
84 op: &fn(uint) -> bool) -> bool {
85 let start_idx = self.to_bucket(hash);
86 let len_buckets = self.buckets.len();
87 let mut idx = start_idx;
88 loop {
89 if !op(idx) { return false; }
90 idx = self.next_bucket(idx, len_buckets);
91 if idx == start_idx {
92 return true;
93 }
94 }
95 }
96
97 #[inline]
98 fn bucket_for_key(&self, k: &K) -> SearchResult {
99 let hash = k.hash_keyed(self.k0, self.k1) as uint;
100 self.bucket_for_key_with_hash(hash, k)
101 }
102
103 #[inline]
104 fn bucket_for_key_equiv<Q:Hash + Equiv<K>>(&self, k: &Q)
105 -> SearchResult {
106 let hash = k.hash_keyed(self.k0, self.k1) as uint;
107 self.bucket_for_key_with_hash_equiv(hash, k)
108 }
109
110 #[inline]
111 fn bucket_for_key_with_hash(&self,
112 hash: uint,
113 k: &K)
114 -> SearchResult {
115 let mut ret = TableFull;
116 do self.bucket_sequence(hash) |i| {
117 match self.buckets[i] {
118 Some(ref bkt) if bkt.hash == hash && *k == bkt.key => {
119 ret = FoundEntry(i); false
120 },
121 None => { ret = FoundHole(i); false }
122 _ => true,
123 }
124 };
125 ret
126 }
127
128 #[inline]
129 fn bucket_for_key_with_hash_equiv<Q:Equiv<K>>(&self,
130 hash: uint,
131 k: &Q)
132 -> SearchResult {
133 let mut ret = TableFull;
134 do self.bucket_sequence(hash) |i| {
135 match self.buckets[i] {
136 Some(ref bkt) if bkt.hash == hash && k.equiv(&bkt.key) => {
137 ret = FoundEntry(i); false
138 },
139 None => { ret = FoundHole(i); false }
140 _ => true,
141 }
142 };
143 ret
144 }
145
146 /// Expand the capacity of the array to the next power of two
147 /// and re-insert each of the existing buckets.
148 #[inline]
149 fn expand(&mut self) {
150 let new_capacity = self.buckets.len() * 2;
151 self.resize(new_capacity);
152 }
153
154 /// Expands the capacity of the array and re-insert each of the
155 /// existing buckets.
156 fn resize(&mut self, new_capacity: uint) {
157 self.resize_at = resize_at(new_capacity);
158
159 let old_buckets = replace(&mut self.buckets,
160 vec::from_fn(new_capacity, |_| None));
161
162 self.size = 0;
163 // move_rev_iter is more efficient
164 for bucket in old_buckets.move_rev_iter() {
165 self.insert_opt_bucket(bucket);
166 }
167 }
168
169 fn insert_opt_bucket(&mut self, bucket: Option<Bucket<K, V>>) {
170 match bucket {
171 Some(Bucket{hash: hash, key: key, value: value}) => {
172 self.insert_internal(hash, key, value);
173 }
174 None => {}
175 }
176 }
177
178 #[inline]
179 fn value_for_bucket<'a>(&'a self, idx: uint) -> &'a V {
180 match self.buckets[idx] {
181 Some(ref bkt) => &bkt.value,
182 None => fail2!("HashMap::find: internal logic error"),
183 }
184 }
185
186 #[inline]
187 fn mut_value_for_bucket<'a>(&'a mut self, idx: uint) -> &'a mut V {
188 match self.buckets[idx] {
189 Some(ref mut bkt) => &mut bkt.value,
190 None => unreachable!()
191 }
192 }
193
194 /// Inserts the key value pair into the buckets.
195 /// Assumes that there will be a bucket.
196 /// True if there was no previous entry with that key
197 fn insert_internal(&mut self, hash: uint, k: K, v: V) -> Option<V> {
198 match self.bucket_for_key_with_hash(hash, &k) {
199 TableFull => { fail2!("Internal logic error"); }
200 FoundHole(idx) => {
201 self.buckets[idx] = Some(Bucket{hash: hash, key: k,
202 value: v});
203 self.size += 1;
204 None
205 }
206 FoundEntry(idx) => {
207 match self.buckets[idx] {
208 None => { fail2!("insert_internal: Internal logic error") }
209 Some(ref mut b) => {
210 b.hash = hash;
211 b.key = k;
212 Some(replace(&mut b.value, v))
213 }
214 }
215 }
216 }
217 }
218
219 fn pop_internal(&mut self, hash: uint, k: &K) -> Option<V> {
220 // Removing from an open-addressed hashtable
221 // is, well, painful. The problem is that
222 // the entry may lie on the probe path for other
223 // entries, so removing it would make you think that
224 // those probe paths are empty.
225 //
226 // To address this we basically have to keep walking,
227 // re-inserting entries we find until we reach an empty
228 // bucket. We know we will eventually reach one because
229 // we insert one ourselves at the beginning (the removed
230 // entry).
231 //
232 // I found this explanation elucidating:
233 // http://www.maths.lse.ac.uk/Courses/MA407/del-hash.pdf
234 let mut idx = match self.bucket_for_key_with_hash(hash, k) {
235 TableFull | FoundHole(_) => return None,
236 FoundEntry(idx) => idx
237 };
238
239 let len_buckets = self.buckets.len();
240 let bucket = self.buckets[idx].take();
241
242 let value = do bucket.map |bucket| {
243 bucket.value
244 };
245
246 /* re-inserting buckets may cause changes in size, so remember
247 what our new size is ahead of time before we start insertions */
248 let size = self.size - 1;
249 idx = self.next_bucket(idx, len_buckets);
250 while self.buckets[idx].is_some() {
251 let bucket = self.buckets[idx].take();
252 self.insert_opt_bucket(bucket);
253 idx = self.next_bucket(idx, len_buckets);
254 }
255 self.size = size;
256
257 value
258 }
259 }
260
261 impl<K:Hash + Eq,V> Container for HashMap<K, V> {
262 /// Return the number of elements in the map
263 fn len(&self) -> uint { self.size }
264 }
265
266 impl<K:Hash + Eq,V> Mutable for HashMap<K, V> {
267 /// Clear the map, removing all key-value pairs.
268 fn clear(&mut self) {
269 for bkt in self.buckets.mut_iter() {
270 *bkt = None;
271 }
272 self.size = 0;
273 }
274 }
275
276 impl<K:Hash + Eq,V> Map<K, V> for HashMap<K, V> {
277 /// Return a reference to the value corresponding to the key
278 fn find<'a>(&'a self, k: &K) -> Option<&'a V> {
279 match self.bucket_for_key(k) {
280 FoundEntry(idx) => Some(self.value_for_bucket(idx)),
281 TableFull | FoundHole(_) => None,
282 }
283 }
284 }
285
286 impl<K:Hash + Eq,V> MutableMap<K, V> for HashMap<K, V> {
287 /// Return a mutable reference to the value corresponding to the key
288 fn find_mut<'a>(&'a mut self, k: &K) -> Option<&'a mut V> {
289 let idx = match self.bucket_for_key(k) {
290 FoundEntry(idx) => idx,
291 TableFull | FoundHole(_) => return None
292 };
293 Some(self.mut_value_for_bucket(idx))
294 }
295
296 /// Insert a key-value pair from the map. If the key already had a value
297 /// present in the map, that value is returned. Otherwise None is returned.
298 fn swap(&mut self, k: K, v: V) -> Option<V> {
299 // this could be faster.
300
301 if self.size >= self.resize_at {
302 // n.b.: We could also do this after searching, so
303 // that we do not resize if this call to insert is
304 // simply going to update a key in place. My sense
305 // though is that it's worse to have to search through
306 // buckets to find the right spot twice than to just
307 // resize in this corner case.
308 self.expand();
309 }
310
311 let hash = k.hash_keyed(self.k0, self.k1) as uint;
312 self.insert_internal(hash, k, v)
313 }
314
315 /// Removes a key from the map, returning the value at the key if the key
316 /// was previously in the map.
317 fn pop(&mut self, k: &K) -> Option<V> {
318 let hash = k.hash_keyed(self.k0, self.k1) as uint;
319 self.pop_internal(hash, k)
320 }
321 }
322
323 impl<K: Hash + Eq, V> HashMap<K, V> {
324 /// Create an empty HashMap
325 pub fn new() -> HashMap<K, V> {
326 HashMap::with_capacity(INITIAL_CAPACITY)
327 }
328
329 /// Create an empty HashMap with space for at least `capacity`
330 /// elements in the hash table.
331 pub fn with_capacity(capacity: uint) -> HashMap<K, V> {
332 let mut r = rand::task_rng();
333 HashMap::with_capacity_and_keys(r.gen(), r.gen(), capacity)
334 }
335
336 /// Create an empty HashMap with space for at least `capacity`
337 /// elements, using `k0` and `k1` as the keys.
338 ///
339 /// Warning: `k0` and `k1` are normally randomly generated, and
340 /// are designed to allow HashMaps to be resistant to attacks that
341 /// cause many collisions and very poor performance. Setting them
342 /// manually using this function can expose a DoS attack vector.
343 pub fn with_capacity_and_keys(k0: u64, k1: u64, capacity: uint) -> HashMap<K, V> {
344 let cap = num::max(INITIAL_CAPACITY, capacity);
345 HashMap {
346 k0: k0, k1: k1,
347 resize_at: resize_at(cap),
348 size: 0,
349 buckets: vec::from_fn(cap, |_| None)
350 }
351 }
352
353 /// Reserve space for at least `n` elements in the hash table.
354 pub fn reserve_at_least(&mut self, n: uint) {
355 if n > self.buckets.len() {
356 let buckets = n * 4 / 3 + 1;
357 self.resize(uint::next_power_of_two(buckets));
358 }
359 }
360
361 /// Modify and return the value corresponding to the key in the map, or
362 /// insert and return a new value if it doesn't exist.
363 pub fn mangle<'a,A>(&'a mut self, k: K, a: A, not_found: &fn(&K, A) -> V,
364 found: &fn(&K, &mut V, A)) -> &'a mut V {
365 if self.size >= self.resize_at {
366 // n.b.: We could also do this after searching, so
367 // that we do not resize if this call to insert is
368 // simply going to update a key in place. My sense
369 // though is that it's worse to have to search through
370 // buckets to find the right spot twice than to just
371 // resize in this corner case.
372 self.expand();
373 }
374
375 let hash = k.hash_keyed(self.k0, self.k1) as uint;
376 let idx = match self.bucket_for_key_with_hash(hash, &k) {
377 TableFull => fail2!("Internal logic error"),
378 FoundEntry(idx) => { found(&k, self.mut_value_for_bucket(idx), a); idx }
379 FoundHole(idx) => {
380 let v = not_found(&k, a);
381 self.buckets[idx] = Some(Bucket{hash: hash, key: k, value: v});
382 self.size += 1;
383 idx
384 }
385 };
386
387 self.mut_value_for_bucket(idx)
388 }
389
390 /// Return the value corresponding to the key in the map, or insert
391 /// and return the value if it doesn't exist.
392 pub fn find_or_insert<'a>(&'a mut self, k: K, v: V) -> &'a mut V {
393 self.mangle(k, v, |_k, a| a, |_k,_v,_a| ())
394 }
395
396 /// Return the value corresponding to the key in the map, or create,
397 /// insert, and return a new value if it doesn't exist.
398 pub fn find_or_insert_with<'a>(&'a mut self, k: K, f: &fn(&K) -> V)
399 -> &'a mut V {
400 self.mangle(k, (), |k,_a| f(k), |_k,_v,_a| ())
401 }
402
403 /// Insert a key-value pair into the map if the key is not already present.
404 /// Otherwise, modify the existing value for the key.
405 /// Returns the new or modified value for the key.
406 pub fn insert_or_update_with<'a>(&'a mut self, k: K, v: V,
407 f: &fn(&K, &mut V)) -> &'a mut V {
408 self.mangle(k, v, |_k,a| a, |k,v,_a| f(k,v))
409 }
410
411 /// Retrieves a value for the given key, failing if the key is not
412 /// present.
413 pub fn get<'a>(&'a self, k: &K) -> &'a V {
414 match self.find(k) {
415 Some(v) => v,
416 None => fail2!("No entry found for key: {:?}", k),
417 }
418 }
419
420 /// Retrieves a (mutable) value for the given key, failing if the key
421 /// is not present.
422 pub fn get_mut<'a>(&'a mut self, k: &K) -> &'a mut V {
423 match self.find_mut(k) {
424 Some(v) => v,
425 None => fail2!("No entry found for key: {:?}", k),
426 }
427 }
428
429 /// Return true if the map contains a value for the specified key,
430 /// using equivalence
431 pub fn contains_key_equiv<Q:Hash + Equiv<K>>(&self, key: &Q) -> bool {
432 match self.bucket_for_key_equiv(key) {
433 FoundEntry(_) => {true}
434 TableFull | FoundHole(_) => {false}
435 }
436 }
437
438 /// Return the value corresponding to the key in the map, using
439 /// equivalence
440 pub fn find_equiv<'a, Q:Hash + Equiv<K>>(&'a self, k: &Q)
441 -> Option<&'a V> {
442 match self.bucket_for_key_equiv(k) {
443 FoundEntry(idx) => Some(self.value_for_bucket(idx)),
444 TableFull | FoundHole(_) => None,
445 }
446 }
447
448 /// Visit all keys
449 pub fn each_key(&self, blk: &fn(k: &K) -> bool) -> bool {
450 self.iter().advance(|(k, _)| blk(k))
451 }
452
453 /// Visit all values
454 pub fn each_value<'a>(&'a self, blk: &fn(v: &'a V) -> bool) -> bool {
455 self.iter().advance(|(_, v)| blk(v))
456 }
457
458 /// An iterator visiting all key-value pairs in arbitrary order.
459 /// Iterator element type is (&'a K, &'a V).
460 pub fn iter<'a>(&'a self) -> HashMapIterator<'a, K, V> {
461 HashMapIterator { iter: self.buckets.iter() }
462 }
463
464 /// An iterator visiting all key-value pairs in arbitrary order,
465 /// with mutable references to the values.
466 /// Iterator element type is (&'a K, &'a mut V).
467 pub fn mut_iter<'a>(&'a mut self) -> HashMapMutIterator<'a, K, V> {
468 HashMapMutIterator { iter: self.buckets.mut_iter() }
469 }
470
471 /// Creates a consuming iterator, that is, one that moves each key-value
472 /// pair out of the map in arbitrary order. The map cannot be used after
473 /// calling this.
474 pub fn move_iter(self) -> HashMapMoveIterator<K, V> {
475 // `move_rev_iter` is more efficient than `move_iter` for vectors
476 HashMapMoveIterator {iter: self.buckets.move_rev_iter()}
477 }
478 }
479
480 impl<K: Hash + Eq, V: Clone> HashMap<K, V> {
481 /// Like `find`, but returns a copy of the value.
482 pub fn find_copy(&self, k: &K) -> Option<V> {
483 self.find(k).map(|v| (*v).clone())
484 }
485
486 /// Like `get`, but returns a copy of the value.
487 pub fn get_copy(&self, k: &K) -> V {
488 (*self.get(k)).clone()
489 }
490 }
491
492 impl<K:Hash + Eq,V:Eq> Eq for HashMap<K, V> {
493 fn eq(&self, other: &HashMap<K, V>) -> bool {
494 if self.len() != other.len() { return false; }
495
496 do self.iter().all |(key, value)| {
497 match other.find(key) {
498 None => false,
499 Some(v) => value == v
500 }
501 }
502 }
503
504 fn ne(&self, other: &HashMap<K, V>) -> bool { !self.eq(other) }
505 }
506
507 impl<K:Hash + Eq + Clone,V:Clone> Clone for HashMap<K,V> {
508 fn clone(&self) -> HashMap<K,V> {
509 let mut new_map = HashMap::with_capacity(self.len());
510 for (key, value) in self.iter() {
511 new_map.insert((*key).clone(), (*value).clone());
512 }
513 new_map
514 }
515 }
516
517 /// HashMap iterator
518 #[deriving(Clone)]
519 pub struct HashMapIterator<'self, K, V> {
520 priv iter: vec::VecIterator<'self, Option<Bucket<K, V>>>,
521 }
522
523 /// HashMap mutable values iterator
524 pub struct HashMapMutIterator<'self, K, V> {
525 priv iter: vec::VecMutIterator<'self, Option<Bucket<K, V>>>,
526 }
527
528 /// HashMap move iterator
529 pub struct HashMapMoveIterator<K, V> {
530 priv iter: vec::MoveRevIterator<Option<Bucket<K, V>>>,
531 }
532
533 /// HashSet iterator
534 #[deriving(Clone)]
535 pub struct HashSetIterator<'self, K> {
536 priv iter: vec::VecIterator<'self, Option<Bucket<K, ()>>>,
537 }
538
539 /// HashSet move iterator
540 pub struct HashSetMoveIterator<K> {
541 priv iter: vec::MoveRevIterator<Option<Bucket<K, ()>>>,
542 }
543
544 impl<'self, K, V> Iterator<(&'self K, &'self V)> for HashMapIterator<'self, K, V> {
545 #[inline]
546 fn next(&mut self) -> Option<(&'self K, &'self V)> {
547 for elt in self.iter {
548 match elt {
549 &Some(ref bucket) => return Some((&bucket.key, &bucket.value)),
550 &None => {},
551 }
552 }
553 None
554 }
555 }
556
557 impl<'self, K, V> Iterator<(&'self K, &'self mut V)> for HashMapMutIterator<'self, K, V> {
558 #[inline]
559 fn next(&mut self) -> Option<(&'self K, &'self mut V)> {
560 for elt in self.iter {
561 match elt {
562 &Some(ref mut bucket) => return Some((&bucket.key, &mut bucket.value)),
563 &None => {},
564 }
565 }
566 None
567 }
568 }
569
570 impl<K, V> Iterator<(K, V)> for HashMapMoveIterator<K, V> {
571 #[inline]
572 fn next(&mut self) -> Option<(K, V)> {
573 for elt in self.iter {
574 match elt {
575 Some(Bucket {key, value, _}) => return Some((key, value)),
576 None => {},
577 }
578 }
579 None
580 }
581 }
582
583 impl<'self, K> Iterator<&'self K> for HashSetIterator<'self, K> {
584 #[inline]
585 fn next(&mut self) -> Option<&'self K> {
586 for elt in self.iter {
587 match elt {
588 &Some(ref bucket) => return Some(&bucket.key),
589 &None => {},
590 }
591 }
592 None
593 }
594 }
595
596 impl<K> Iterator<K> for HashSetMoveIterator<K> {
597 #[inline]
598 fn next(&mut self) -> Option<K> {
599 for elt in self.iter {
600 match elt {
601 Some(bucket) => return Some(bucket.key),
602 None => {},
603 }
604 }
605 None
606 }
607 }
608
609 impl<K: Eq + Hash, V> FromIterator<(K, V)> for HashMap<K, V> {
610 fn from_iterator<T: Iterator<(K, V)>>(iter: &mut T) -> HashMap<K, V> {
611 let (lower, _) = iter.size_hint();
612 let mut map = HashMap::with_capacity(lower);
613 map.extend(iter);
614 map
615 }
616 }
617
618 impl<K: Eq + Hash, V> Extendable<(K, V)> for HashMap<K, V> {
619 fn extend<T: Iterator<(K, V)>>(&mut self, iter: &mut T) {
620 for (k, v) in *iter {
621 self.insert(k, v);
622 }
623 }
624 }
625
626 impl<K: Eq + Hash, V> Default for HashMap<K, V> {
627 fn default() -> HashMap<K, V> { HashMap::new() }
628 }
629
630 /// An implementation of a hash set using the underlying representation of a
631 /// HashMap where the value is (). As with the `HashMap` type, a `HashSet`
632 /// requires that the elements implement the `Eq` and `Hash` traits.
633 pub struct HashSet<T> {
634 priv map: HashMap<T, ()>
635 }
636
637 impl<T:Hash + Eq> Eq for HashSet<T> {
638 fn eq(&self, other: &HashSet<T>) -> bool { self.map == other.map }
639 fn ne(&self, other: &HashSet<T>) -> bool { self.map != other.map }
640 }
641
642 impl<T:Hash + Eq> Container for HashSet<T> {
643 /// Return the number of elements in the set
644 fn len(&self) -> uint { self.map.len() }
645 }
646
647 impl<T:Hash + Eq> Mutable for HashSet<T> {
648 /// Clear the set, removing all values.
649 fn clear(&mut self) { self.map.clear() }
650 }
651
652 impl<T:Hash + Eq> Set<T> for HashSet<T> {
653 /// Return true if the set contains a value
654 fn contains(&self, value: &T) -> bool { self.map.contains_key(value) }
655
656 /// Return true if the set has no elements in common with `other`.
657 /// This is equivalent to checking for an empty intersection.
658 fn is_disjoint(&self, other: &HashSet<T>) -> bool {
659 self.iter().all(|v| !other.contains(v))
660 }
661
662 /// Return true if the set is a subset of another
663 fn is_subset(&self, other: &HashSet<T>) -> bool {
664 self.iter().all(|v| other.contains(v))
665 }
666
667 /// Return true if the set is a superset of another
668 fn is_superset(&self, other: &HashSet<T>) -> bool {
669 other.is_subset(self)
670 }
671 }
672
673 impl<T:Hash + Eq> MutableSet<T> for HashSet<T> {
674 /// Add a value to the set. Return true if the value was not already
675 /// present in the set.
676 fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) }
677
678 /// Remove a value from the set. Return true if the value was
679 /// present in the set.
680 fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
681 }
682
683 impl<T:Hash + Eq> HashSet<T> {
684 /// Create an empty HashSet
685 pub fn new() -> HashSet<T> {
686 HashSet::with_capacity(INITIAL_CAPACITY)
687 }
688
689 /// Create an empty HashSet with space for at least `n` elements in
690 /// the hash table.
691 pub fn with_capacity(capacity: uint) -> HashSet<T> {
692 HashSet { map: HashMap::with_capacity(capacity) }
693 }
694
695 /// Create an empty HashSet with space for at least `capacity`
696 /// elements in the hash table, using `k0` and `k1` as the keys.
697 ///
698 /// Warning: `k0` and `k1` are normally randomly generated, and
699 /// are designed to allow HashSets to be resistant to attacks that
700 /// cause many collisions and very poor performance. Setting them
701 /// manually using this function can expose a DoS attack vector.
702 pub fn with_capacity_and_keys(k0: u64, k1: u64, capacity: uint) -> HashSet<T> {
703 HashSet { map: HashMap::with_capacity_and_keys(k0, k1, capacity) }
704 }
705
706 /// Reserve space for at least `n` elements in the hash table.
707 pub fn reserve_at_least(&mut self, n: uint) {
708 self.map.reserve_at_least(n)
709 }
710
711 /// Returns true if the hash set contains a value equivalent to the
712 /// given query value.
713 pub fn contains_equiv<Q:Hash + Equiv<T>>(&self, value: &Q) -> bool {
714 self.map.contains_key_equiv(value)
715 }
716
717 /// An iterator visiting all elements in arbitrary order.
718 /// Iterator element type is &'a T.
719 pub fn iter<'a>(&'a self) -> HashSetIterator<'a, T> {
720 HashSetIterator { iter: self.map.buckets.iter() }
721 }
722
723 /// Creates a consuming iterator, that is, one that moves each value out
724 /// of the set in arbitrary order. The set cannot be used after calling
725 /// this.
726 pub fn move_iter(self) -> HashSetMoveIterator<T> {
727 // `move_rev_iter` is more efficient than `move_iter` for vectors
728 HashSetMoveIterator {iter: self.map.buckets.move_rev_iter()}
729 }
730
731 /// Visit the values representing the difference
732 pub fn difference_iter<'a>(&'a self, other: &'a HashSet<T>) -> SetAlgebraIter<'a, T> {
733 Repeat::new(other)
734 .zip(self.iter())
735 .filter_map(|(other, elt)| {
736 if !other.contains(elt) { Some(elt) } else { None }
737 })
738 }
739
740 /// Visit the values representing the symmetric difference
741 pub fn symmetric_difference_iter<'a>(&'a self, other: &'a HashSet<T>)
742 -> Chain<SetAlgebraIter<'a, T>, SetAlgebraIter<'a, T>> {
743 self.difference_iter(other).chain(other.difference_iter(self))
744 }
745
746 /// Visit the values representing the intersection
747 pub fn intersection_iter<'a>(&'a self, other: &'a HashSet<T>)
748 -> SetAlgebraIter<'a, T> {
749 Repeat::new(other)
750 .zip(self.iter())
751 .filter_map(|(other, elt)| {
752 if other.contains(elt) { Some(elt) } else { None }
753 })
754 }
755
756 /// Visit the values representing the union
757 pub fn union_iter<'a>(&'a self, other: &'a HashSet<T>)
758 -> Chain<HashSetIterator<'a, T>, SetAlgebraIter<'a, T>> {
759 self.iter().chain(other.difference_iter(self))
760 }
761
762 }
763
764 impl<T:Hash + Eq + Clone> Clone for HashSet<T> {
765 fn clone(&self) -> HashSet<T> {
766 HashSet {
767 map: self.map.clone()
768 }
769 }
770 }
771
772 impl<K: Eq + Hash> FromIterator<K> for HashSet<K> {
773 fn from_iterator<T: Iterator<K>>(iter: &mut T) -> HashSet<K> {
774 let (lower, _) = iter.size_hint();
775 let mut set = HashSet::with_capacity(lower);
776 set.extend(iter);
777 set
778 }
779 }
780
781 impl<K: Eq + Hash> Extendable<K> for HashSet<K> {
782 fn extend<T: Iterator<K>>(&mut self, iter: &mut T) {
783 for k in *iter {
784 self.insert(k);
785 }
786 }
787 }
788
789 impl<K: Eq + Hash> Default for HashSet<K> {
790 fn default() -> HashSet<K> { HashSet::new() }
791 }
792
793 // `Repeat` is used to feed the filter closure an explicit capture
794 // of a reference to the other set
795 /// Set operations iterator
796 pub type SetAlgebraIter<'self, T> =
797 FilterMap<'static,(&'self HashSet<T>, &'self T), &'self T,
798 Zip<Repeat<&'self HashSet<T>>,HashSetIterator<'self,T>>>;
799
800
801 #[cfg(test)]
802 mod test_map {
803 use prelude::*;
804 use super::*;
805
806 #[test]
807 fn test_create_capacity_zero() {
808 let mut m = HashMap::with_capacity(0);
809 assert!(m.insert(1, 1));
810 }
811
812 #[test]
813 fn test_insert() {
814 let mut m = HashMap::new();
815 assert!(m.insert(1, 2));
816 assert!(m.insert(2, 4));
817 assert_eq!(*m.get(&1), 2);
818 assert_eq!(*m.get(&2), 4);
819 }
820
821 #[test]
822 fn test_find_mut() {
823 let mut m = HashMap::new();
824 assert!(m.insert(1, 12));
825 assert!(m.insert(2, 8));
826 assert!(m.insert(5, 14));
827 let new = 100;
828 match m.find_mut(&5) {
829 None => fail2!(), Some(x) => *x = new
830 }
831 assert_eq!(m.find(&5), Some(&new));
832 }
833
834 #[test]
835 fn test_insert_overwrite() {
836 let mut m = HashMap::new();
837 assert!(m.insert(1, 2));
838 assert_eq!(*m.get(&1), 2);
839 assert!(!m.insert(1, 3));
840 assert_eq!(*m.get(&1), 3);
841 }
842
843 #[test]
844 fn test_insert_conflicts() {
845 let mut m = HashMap::with_capacity(4);
846 assert!(m.insert(1, 2));
847 assert!(m.insert(5, 3));
848 assert!(m.insert(9, 4));
849 assert_eq!(*m.get(&9), 4);
850 assert_eq!(*m.get(&5), 3);
851 assert_eq!(*m.get(&1), 2);
852 }
853
854 #[test]
855 fn test_conflict_remove() {
856 let mut m = HashMap::with_capacity(4);
857 assert!(m.insert(1, 2));
858 assert!(m.insert(5, 3));
859 assert!(m.insert(9, 4));
860 assert!(m.remove(&1));
861 assert_eq!(*m.get(&9), 4);
862 assert_eq!(*m.get(&5), 3);
863 }
864
865 #[test]
866 fn test_is_empty() {
867 let mut m = HashMap::with_capacity(4);
868 assert!(m.insert(1, 2));
869 assert!(!m.is_empty());
870 assert!(m.remove(&1));
871 assert!(m.is_empty());
872 }
873
874 #[test]
875 fn test_pop() {
876 let mut m = HashMap::new();
877 m.insert(1, 2);
878 assert_eq!(m.pop(&1), Some(2));
879 assert_eq!(m.pop(&1), None);
880 }
881
882 #[test]
883 fn test_swap() {
884 let mut m = HashMap::new();
885 assert_eq!(m.swap(1, 2), None);
886 assert_eq!(m.swap(1, 3), Some(2));
887 assert_eq!(m.swap(1, 4), Some(3));
888 }
889
890 #[test]
891 fn test_find_or_insert() {
892 let mut m: HashMap<int,int> = HashMap::new();
893 assert_eq!(*m.find_or_insert(1, 2), 2);
894 assert_eq!(*m.find_or_insert(1, 3), 2);
895 }
896
897 #[test]
898 fn test_find_or_insert_with() {
899 let mut m: HashMap<int,int> = HashMap::new();
900 assert_eq!(*m.find_or_insert_with(1, |_| 2), 2);
901 assert_eq!(*m.find_or_insert_with(1, |_| 3), 2);
902 }
903
904 #[test]
905 fn test_insert_or_update_with() {
906 let mut m: HashMap<int,int> = HashMap::new();
907 assert_eq!(*m.insert_or_update_with(1, 2, |_,x| *x+=1), 2);
908 assert_eq!(*m.insert_or_update_with(1, 2, |_,x| *x+=1), 3);
909 }
910
911 #[test]
912 fn test_move_iter() {
913 let hm = {
914 let mut hm = HashMap::new();
915
916 hm.insert('a', 1);
917 hm.insert('b', 2);
918
919 hm
920 };
921
922 let v = hm.move_iter().collect::<~[(char, int)]>();
923 assert!([('a', 1), ('b', 2)] == v || [('b', 2), ('a', 1)] == v);
924 }
925
926 #[test]
927 fn test_iterate() {
928 let mut m = HashMap::with_capacity(4);
929 for i in range(0u, 32) {
930 assert!(m.insert(i, i*2));
931 }
932 let mut observed = 0;
933 for (k, v) in m.iter() {
934 assert_eq!(*v, *k * 2);
935 observed |= (1 << *k);
936 }
937 assert_eq!(observed, 0xFFFF_FFFF);
938 }
939
940 #[test]
941 fn test_find() {
942 let mut m = HashMap::new();
943 assert!(m.find(&1).is_none());
944 m.insert(1, 2);
945 match m.find(&1) {
946 None => fail2!(),
947 Some(v) => assert!(*v == 2)
948 }
949 }
950
951 #[test]
952 fn test_eq() {
953 let mut m1 = HashMap::new();
954 m1.insert(1, 2);
955 m1.insert(2, 3);
956 m1.insert(3, 4);
957
958 let mut m2 = HashMap::new();
959 m2.insert(1, 2);
960 m2.insert(2, 3);
961
962 assert!(m1 != m2);
963
964 m2.insert(3, 4);
965
966 assert_eq!(m1, m2);
967 }
968
969 #[test]
970 fn test_expand() {
971 let mut m = HashMap::new();
972
973 assert_eq!(m.len(), 0);
974 assert!(m.is_empty());
975
976 let mut i = 0u;
977 let old_resize_at = m.resize_at;
978 while old_resize_at == m.resize_at {
979 m.insert(i, i);
980 i += 1;
981 }
982
983 assert_eq!(m.len(), i);
984 assert!(!m.is_empty());
985 }
986
987 #[test]
988 fn test_find_equiv() {
989 let mut m = HashMap::new();
990
991 let (foo, bar, baz) = (1,2,3);
992 m.insert(~"foo", foo);
993 m.insert(~"bar", bar);
994 m.insert(~"baz", baz);
995
996
997 assert_eq!(m.find_equiv(&("foo")), Some(&foo));
998 assert_eq!(m.find_equiv(&("bar")), Some(&bar));
999 assert_eq!(m.find_equiv(&("baz")), Some(&baz));
1000
1001 assert_eq!(m.find_equiv(&("qux")), None);
1002 }
1003
1004 #[test]
1005 fn test_from_iter() {
1006 let xs = ~[(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
1007
1008 let map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
1009
1010 for &(k, v) in xs.iter() {
1011 assert_eq!(map.find(&k), Some(&v));
1012 }
1013 }
1014 }
1015
1016 #[cfg(test)]
1017 mod test_set {
1018 use super::*;
1019 use prelude::*;
1020 use container::Container;
1021 use vec::ImmutableEqVector;
1022
1023 #[test]
1024 fn test_disjoint() {
1025 let mut xs = HashSet::new();
1026 let mut ys = HashSet::new();
1027 assert!(xs.is_disjoint(&ys));
1028 assert!(ys.is_disjoint(&xs));
1029 assert!(xs.insert(5));
1030 assert!(ys.insert(11));
1031 assert!(xs.is_disjoint(&ys));
1032 assert!(ys.is_disjoint(&xs));
1033 assert!(xs.insert(7));
1034 assert!(xs.insert(19));
1035 assert!(xs.insert(4));
1036 assert!(ys.insert(2));
1037 assert!(ys.insert(-11));
1038 assert!(xs.is_disjoint(&ys));
1039 assert!(ys.is_disjoint(&xs));
1040 assert!(ys.insert(7));
1041 assert!(!xs.is_disjoint(&ys));
1042 assert!(!ys.is_disjoint(&xs));
1043 }
1044
1045 #[test]
1046 fn test_subset_and_superset() {
1047 let mut a = HashSet::new();
1048 assert!(a.insert(0));
1049 assert!(a.insert(5));
1050 assert!(a.insert(11));
1051 assert!(a.insert(7));
1052
1053 let mut b = HashSet::new();
1054 assert!(b.insert(0));
1055 assert!(b.insert(7));
1056 assert!(b.insert(19));
1057 assert!(b.insert(250));
1058 assert!(b.insert(11));
1059 assert!(b.insert(200));
1060
1061 assert!(!a.is_subset(&b));
1062 assert!(!a.is_superset(&b));
1063 assert!(!b.is_subset(&a));
1064 assert!(!b.is_superset(&a));
1065
1066 assert!(b.insert(5));
1067
1068 assert!(a.is_subset(&b));
1069 assert!(!a.is_superset(&b));
1070 assert!(!b.is_subset(&a));
1071 assert!(b.is_superset(&a));
1072 }
1073
1074 #[test]
1075 fn test_iterate() {
1076 let mut a = HashSet::new();
1077 for i in range(0u, 32) {
1078 assert!(a.insert(i));
1079 }
1080 let mut observed = 0;
1081 for k in a.iter() {
1082 observed |= (1 << *k);
1083 }
1084 assert_eq!(observed, 0xFFFF_FFFF);
1085 }
1086
1087 #[test]
1088 fn test_intersection() {
1089 let mut a = HashSet::new();
1090 let mut b = HashSet::new();
1091
1092 assert!(a.insert(11));
1093 assert!(a.insert(1));
1094 assert!(a.insert(3));
1095 assert!(a.insert(77));
1096 assert!(a.insert(103));
1097 assert!(a.insert(5));
1098 assert!(a.insert(-5));
1099
1100 assert!(b.insert(2));
1101 assert!(b.insert(11));
1102 assert!(b.insert(77));
1103 assert!(b.insert(-9));
1104 assert!(b.insert(-42));
1105 assert!(b.insert(5));
1106 assert!(b.insert(3));
1107
1108 let mut i = 0;
1109 let expected = [3, 5, 11, 77];
1110 for x in a.intersection_iter(&b) {
1111 assert!(expected.contains(x));
1112 i += 1
1113 }
1114 assert_eq!(i, expected.len());
1115 }
1116
1117 #[test]
1118 fn test_difference() {
1119 let mut a = HashSet::new();
1120 let mut b = HashSet::new();
1121
1122 assert!(a.insert(1));
1123 assert!(a.insert(3));
1124 assert!(a.insert(5));
1125 assert!(a.insert(9));
1126 assert!(a.insert(11));
1127
1128 assert!(b.insert(3));
1129 assert!(b.insert(9));
1130
1131 let mut i = 0;
1132 let expected = [1, 5, 11];
1133 for x in a.difference_iter(&b) {
1134 assert!(expected.contains(x));
1135 i += 1
1136 }
1137 assert_eq!(i, expected.len());
1138 }
1139
1140 #[test]
1141 fn test_symmetric_difference() {
1142 let mut a = HashSet::new();
1143 let mut b = HashSet::new();
1144
1145 assert!(a.insert(1));
1146 assert!(a.insert(3));
1147 assert!(a.insert(5));
1148 assert!(a.insert(9));
1149 assert!(a.insert(11));
1150
1151 assert!(b.insert(-2));
1152 assert!(b.insert(3));
1153 assert!(b.insert(9));
1154 assert!(b.insert(14));
1155 assert!(b.insert(22));
1156
1157 let mut i = 0;
1158 let expected = [-2, 1, 5, 11, 14, 22];
1159 for x in a.symmetric_difference_iter(&b) {
1160 assert!(expected.contains(x));
1161 i += 1
1162 }
1163 assert_eq!(i, expected.len());
1164 }
1165
1166 #[test]
1167 fn test_union() {
1168 let mut a = HashSet::new();
1169 let mut b = HashSet::new();
1170
1171 assert!(a.insert(1));
1172 assert!(a.insert(3));
1173 assert!(a.insert(5));
1174 assert!(a.insert(9));
1175 assert!(a.insert(11));
1176 assert!(a.insert(16));
1177 assert!(a.insert(19));
1178 assert!(a.insert(24));
1179
1180 assert!(b.insert(-2));
1181 assert!(b.insert(1));
1182 assert!(b.insert(5));
1183 assert!(b.insert(9));
1184 assert!(b.insert(13));
1185 assert!(b.insert(19));
1186
1187 let mut i = 0;
1188 let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
1189 for x in a.union_iter(&b) {
1190 assert!(expected.contains(x));
1191 i += 1
1192 }
1193 assert_eq!(i, expected.len());
1194 }
1195
1196 #[test]
1197 fn test_from_iter() {
1198 let xs = ~[1, 2, 3, 4, 5, 6, 7, 8, 9];
1199
1200 let set: HashSet<int> = xs.iter().map(|&x| x).collect();
1201
1202 for x in xs.iter() {
1203 assert!(set.contains(x));
1204 }
1205 }
1206
1207 #[test]
1208 fn test_move_iter() {
1209 let hs = {
1210 let mut hs = HashSet::new();
1211
1212 hs.insert('a');
1213 hs.insert('b');
1214
1215 hs
1216 };
1217
1218 let v = hs.move_iter().collect::<~[char]>();
1219 assert!(['a', 'b'] == v || ['b', 'a'] == v);
1220 }
1221
1222 #[test]
1223 fn test_eq() {
1224 let mut s1 = HashSet::new();
1225 s1.insert(1);
1226 s1.insert(2);
1227 s1.insert(3);
1228
1229 let mut s2 = HashSet::new();
1230 s2.insert(1);
1231 s2.insert(2);
1232
1233 assert!(s1 != s2);
1234
1235 s2.insert(3);
1236
1237 assert_eq!(s1, s2);
1238 }
1239 }
libstd/hashmap.rs:59:24-59:24 -enum- definition:
// which would be nifty
enum SearchResult {
references:-132: -> SearchResult {
114: -> SearchResult {
105: -> SearchResult {
98: fn bucket_for_key(&self, k: &K) -> SearchResult {
libstd/hashmap.rs:528:26-528:26 -struct- definition:
/// HashMap move iterator
pub struct HashMapMoveIterator<K, V> {
references:-476: HashMapMoveIterator {iter: self.buckets.move_rev_iter()}
474: pub fn move_iter(self) -> HashMapMoveIterator<K, V> {
570: impl<K, V> Iterator<(K, V)> for HashMapMoveIterator<K, V> {
libstd/hashmap.rs:518:19-518:19 -struct- definition:
#[deriving(Clone)]
pub struct HashMapIterator<'self, K, V> {
references:-518: #[deriving(Clone)]
460: pub fn iter<'a>(&'a self) -> HashMapIterator<'a, K, V> {
518: #[deriving(Clone)]
544: impl<'self, K, V> Iterator<(&'self K, &'self V)> for HashMapIterator<'self, K, V> {
518: #[deriving(Clone)]
518: #[deriving(Clone)]
461: HashMapIterator { iter: self.buckets.iter() }
libstd/hashmap.rs:64:10-64:10 -fn- definition:
#[inline]
fn resize_at(capacity: uint) -> uint {
references:-347: resize_at: resize_at(cap),
157: self.resize_at = resize_at(new_capacity);
libstd/hashmap.rs:35:1-35:1 -struct- definition:
struct Bucket<K,V> {
references:-169: fn insert_opt_bucket(&mut self, bucket: Option<Bucket<K, V>>) {
575: Some(Bucket {key, value, _}) => return Some((key, value)),
541: priv iter: vec::MoveRevIterator<Option<Bucket<K, ()>>>,
536: priv iter: vec::VecIterator<'self, Option<Bucket<K, ()>>>,
171: Some(Bucket{hash: hash, key: key, value: value}) => {
201: self.buckets[idx] = Some(Bucket{hash: hash, key: k,
525: priv iter: vec::VecMutIterator<'self, Option<Bucket<K, V>>>,
55: priv buckets: ~[Option<Bucket<K, V>>],
381: self.buckets[idx] = Some(Bucket{hash: hash, key: k, value: v});
530: priv iter: vec::MoveRevIterator<Option<Bucket<K, V>>>,
520: priv iter: vec::VecIterator<'self, Option<Bucket<K, V>>>,
libstd/hashmap.rs:49:27-49:27 -struct- definition:
/// implement `IterBytes`.
pub struct HashMap<K,V> {
references:-480: impl<K: Hash + Eq, V: Clone> HashMap<K, V> {
261: impl<K:Hash + Eq,V> Container for HashMap<K, V> {
634: priv map: HashMap<T, ()>
610: fn from_iterator<T: Iterator<(K, V)>>(iter: &mut T) -> HashMap<K, V> {
345: HashMap {
627: fn default() -> HashMap<K, V> { HashMap::new() }
609: impl<K: Eq + Hash, V> FromIterator<(K, V)> for HashMap<K, V> {
492: impl<K:Hash + Eq,V:Eq> Eq for HashMap<K, V> {
276: impl<K:Hash + Eq,V> Map<K, V> for HashMap<K, V> {
69: impl<K:Hash + Eq,V> HashMap<K, V> {
266: impl<K:Hash + Eq,V> Mutable for HashMap<K, V> {
504: fn ne(&self, other: &HashMap<K, V>) -> bool { !self.eq(other) }
286: impl<K:Hash + Eq,V> MutableMap<K, V> for HashMap<K, V> {
323: impl<K: Hash + Eq, V> HashMap<K, V> {
508: fn clone(&self) -> HashMap<K,V> {
626: impl<K: Eq + Hash, V> Default for HashMap<K, V> {
618: impl<K: Eq + Hash, V> Extendable<(K, V)> for HashMap<K, V> {
331: pub fn with_capacity(capacity: uint) -> HashMap<K, V> {
343: pub fn with_capacity_and_keys(k0: u64, k1: u64, capacity: uint) -> HashMap<K, V> {
507: impl<K:Hash + Eq + Clone,V:Clone> Clone for HashMap<K,V> {
325: pub fn new() -> HashMap<K, V> {
493: fn eq(&self, other: &HashMap<K, V>) -> bool {
libstd/to_str.rs:
54: impl<A:ToStr+Hash+Eq, B:ToStr> ToStr for HashMap<A, B> {
libstd/hashmap.rs:534:19-534:19 -struct- definition:
#[deriving(Clone)]
pub struct HashSetIterator<'self, K> {
references:-583: impl<'self, K> Iterator<&'self K> for HashSetIterator<'self, K> {
719: pub fn iter<'a>(&'a self) -> HashSetIterator<'a, T> {
534: #[deriving(Clone)]
758: -> Chain<HashSetIterator<'a, T>, SetAlgebraIter<'a, T>> {
798: Zip<Repeat<&'self HashSet<T>>,HashSetIterator<'self,T>>>;
720: HashSetIterator { iter: self.map.buckets.iter() }
534: #[deriving(Clone)]
534: #[deriving(Clone)]
534: #[deriving(Clone)]
libstd/hashmap.rs:539:26-539:26 -struct- definition:
/// HashSet move iterator
pub struct HashSetMoveIterator<K> {
references:-728: HashSetMoveIterator {iter: self.map.buckets.move_rev_iter()}
596: impl<K> Iterator<K> for HashSetMoveIterator<K> {
726: pub fn move_iter(self) -> HashSetMoveIterator<T> {
libstd/task/spawn.rs:
117: fn move_iter(self) -> HashSetMoveIterator<KillHandle> {
libstd/hashmap.rs:632:69-632:69 -struct- definition:
/// requires that the elements implement the `Eq` and `Hash` traits.
pub struct HashSet<T> {
references:-741: pub fn symmetric_difference_iter<'a>(&'a self, other: &'a HashSet<T>)
798: Zip<Repeat<&'self HashSet<T>>,HashSetIterator<'self,T>>>;
637: impl<T:Hash + Eq> Eq for HashSet<T> {
702: pub fn with_capacity_and_keys(k0: u64, k1: u64, capacity: uint) -> HashSet<T> {
642: impl<T:Hash + Eq> Container for HashSet<T> {
765: fn clone(&self) -> HashSet<T> {
691: pub fn with_capacity(capacity: uint) -> HashSet<T> {
652: impl<T:Hash + Eq> Set<T> for HashSet<T> {
789: impl<K: Eq + Hash> Default for HashSet<K> {
658: fn is_disjoint(&self, other: &HashSet<T>) -> bool {
766: HashSet {
692: HashSet { map: HashMap::with_capacity(capacity) }
647: impl<T:Hash + Eq> Mutable for HashSet<T> {
757: pub fn union_iter<'a>(&'a self, other: &'a HashSet<T>)
663: fn is_subset(&self, other: &HashSet<T>) -> bool {
790: fn default() -> HashSet<K> { HashSet::new() }
772: impl<K: Eq + Hash> FromIterator<K> for HashSet<K> {
773: fn from_iterator<T: Iterator<K>>(iter: &mut T) -> HashSet<K> {
638: fn eq(&self, other: &HashSet<T>) -> bool { self.map == other.map }
639: fn ne(&self, other: &HashSet<T>) -> bool { self.map != other.map }
747: pub fn intersection_iter<'a>(&'a self, other: &'a HashSet<T>)
797: FilterMap<'static,(&'self HashSet<T>, &'self T), &'self T,
683: impl<T:Hash + Eq> HashSet<T> {
685: pub fn new() -> HashSet<T> {
673: impl<T:Hash + Eq> MutableSet<T> for HashSet<T> {
781: impl<K: Eq + Hash> Extendable<K> for HashSet<K> {
764: impl<T:Hash + Eq + Clone> Clone for HashSet<T> {
668: fn is_superset(&self, other: &HashSet<T>) -> bool {
703: HashSet { map: HashMap::with_capacity_and_keys(k0, k1, capacity) }
732: pub fn difference_iter<'a>(&'a self, other: &'a HashSet<T>) -> SetAlgebraIter<'a, T> {
libstd/task/spawn.rs:
(99)libstd/rt/crate_map.rs:
(105)(84)libstd/to_str.rs:
(75)libstd/hashmap.rs:523:36-523:36 -struct- definition:
/// HashMap mutable values iterator
pub struct HashMapMutIterator<'self, K, V> {
references:-468: HashMapMutIterator { iter: self.buckets.mut_iter() }
467: pub fn mut_iter<'a>(&'a mut self) -> HashMapMutIterator<'a, K, V> {
557: impl<'self, K, V> Iterator<(&'self K, &'self mut V)> for HashMapMutIterator<'self, K, V> {
libstd/hashmap.rs:795:28-795:28 -ty- definition:
/// Set operations iterator
pub type SetAlgebraIter<'self, T> =
references:-742: -> Chain<SetAlgebraIter<'a, T>, SetAlgebraIter<'a, T>> {
758: -> Chain<HashSetIterator<'a, T>, SetAlgebraIter<'a, T>> {
732: pub fn difference_iter<'a>(&'a self, other: &'a HashSet<T>) -> SetAlgebraIter<'a, T> {
742: -> Chain<SetAlgebraIter<'a, T>, SetAlgebraIter<'a, T>> {
748: -> SetAlgebraIter<'a, T> {