1 use hashlink::{linked_hash_map, LinkedHashMap};
2 
3 #[allow(dead_code)]
assert_covariance()4 fn assert_covariance() {
5     fn set<'new>(v: LinkedHashMap<&'static str, ()>) -> LinkedHashMap<&'new str, ()> {
6         v
7     }
8 
9     fn iter<'a, 'new>(
10         v: linked_hash_map::Iter<'a, &'static str, &'static str>,
11     ) -> linked_hash_map::Iter<'a, &'new str, &'new str> {
12         v
13     }
14 
15     fn iter_mut<'a, 'new>(
16         v: linked_hash_map::Iter<'a, &'static str, ()>,
17     ) -> linked_hash_map::Iter<'a, &'new str, ()> {
18         v
19     }
20 
21     fn into_iter<'new>(
22         v: linked_hash_map::IntoIter<&'static str, &'static str>,
23     ) -> linked_hash_map::IntoIter<&'new str, &'new str> {
24         v
25     }
26 
27     fn drain<'new>(
28         d: linked_hash_map::Drain<'static, &'static str, &'static str>,
29     ) -> linked_hash_map::Drain<'new, &'new str, &'new str> {
30         d
31     }
32 
33     fn raw_entry_builder<'a, 'new>(
34         v: linked_hash_map::RawEntryBuilder<'a, &'static str, &'static str, ()>,
35     ) -> linked_hash_map::RawEntryBuilder<'a, &'new str, &'new str, ()> {
36         v
37     }
38 }
39 
40 #[test]
test_index()41 fn test_index() {
42     let mut map = LinkedHashMap::new();
43     map.insert(1, 10);
44     map.insert(2, 20);
45     assert_eq!(10, map[&1]);
46     map[&2] = 22;
47     assert_eq!(22, map[&2]);
48 }
49 
50 #[test]
test_insert_and_get()51 fn test_insert_and_get() {
52     let mut map = LinkedHashMap::new();
53     map.insert(1, 10);
54     map.insert(2, 20);
55     assert_eq!(map.get(&1), Some(&10));
56     assert_eq!(map.get(&2), Some(&20));
57     assert_eq!(map.len(), 2);
58 }
59 
60 #[test]
test_insert_update()61 fn test_insert_update() {
62     let mut map = LinkedHashMap::new();
63     map.insert("1".to_string(), vec![10, 10]);
64     map.insert("1".to_string(), vec![10, 19]);
65     assert_eq!(map.get(&"1".to_string()), Some(&vec![10, 19]));
66     assert_eq!(map.len(), 1);
67 }
68 
69 #[test]
test_entry_insert_vacant()70 fn test_entry_insert_vacant() {
71     let mut map = LinkedHashMap::new();
72     match map.entry("1".to_string()) {
73         linked_hash_map::Entry::Vacant(e) => {
74             assert_eq!(*e.insert(vec![10, 10]), vec![10, 10]);
75         }
76         _ => panic!("fail"),
77     }
78     assert!(map.contains_key("1"));
79     assert_eq!(map["1"], vec![10, 10]);
80 
81     match map.entry("1".to_string()) {
82         linked_hash_map::Entry::Occupied(mut e) => {
83             assert_eq!(*e.get(), vec![10, 10]);
84             assert_eq!(e.insert(vec![10, 16]), vec![10, 10]);
85         }
86         _ => panic!("fail"),
87     }
88 
89     assert!(map.contains_key("1"));
90     assert_eq!(map["1"], vec![10, 16]);
91 
92     match map.entry("1".to_string()) {
93         linked_hash_map::Entry::Occupied(e) => {
94             assert_eq!(e.remove(), vec![10, 16]);
95         }
96         _ => panic!("fail"),
97     }
98 }
99 
100 #[test]
test_remove()101 fn test_remove() {
102     let mut map = LinkedHashMap::new();
103     map.insert(1, 10);
104     map.insert(2, 20);
105     map.insert(3, 30);
106     map.insert(4, 40);
107     map.insert(5, 50);
108     map.remove(&3);
109     map.remove(&4);
110     assert!(map.get(&3).is_none());
111     assert!(map.get(&4).is_none());
112     map.insert(6, 60);
113     map.insert(7, 70);
114     map.insert(8, 80);
115     assert_eq!(map.get(&6), Some(&60));
116     assert_eq!(map.get(&7), Some(&70));
117     assert_eq!(map.get(&8), Some(&80));
118 }
119 
120 #[test]
test_pop()121 fn test_pop() {
122     let mut map = LinkedHashMap::new();
123     map.insert(1, 10);
124     map.insert(2, 20);
125     map.insert(3, 30);
126     map.insert(4, 40);
127     map.insert(5, 50);
128     assert_eq!(map.pop_front(), Some((1, 10)));
129     assert!(map.get(&1).is_none());
130     assert_eq!(map.pop_back(), Some((5, 50)));
131     assert!(map.get(&5).is_none());
132     map.insert(6, 60);
133     map.insert(7, 70);
134     map.insert(8, 80);
135     assert_eq!(map.pop_front(), Some((2, 20)));
136     assert!(map.get(&2).is_none());
137     assert_eq!(map.pop_back(), Some((8, 80)));
138     assert!(map.get(&8).is_none());
139     map.insert(3, 30);
140     assert_eq!(map.pop_front(), Some((4, 40)));
141     assert!(map.get(&4).is_none());
142     assert_eq!(map.pop_back(), Some((3, 30)));
143     assert!(map.get(&3).is_none());
144 }
145 
146 #[test]
test_move()147 fn test_move() {
148     let to_back = |map: &mut LinkedHashMap<_, _>, key| match map.entry(key) {
149         linked_hash_map::Entry::Occupied(mut occupied) => occupied.to_back(),
150         linked_hash_map::Entry::Vacant(_) => panic!(),
151     };
152 
153     let to_front = |map: &mut LinkedHashMap<_, _>, key| match map.entry(key) {
154         linked_hash_map::Entry::Occupied(mut occupied) => occupied.to_front(),
155         linked_hash_map::Entry::Vacant(_) => panic!(),
156     };
157 
158     let mut map = LinkedHashMap::new();
159     map.insert(1, 10);
160     map.insert(2, 20);
161     map.insert(3, 30);
162     map.insert(4, 40);
163     map.insert(5, 50);
164 
165     to_back(&mut map, 1);
166     assert_eq!(map.keys().copied().collect::<Vec<_>>(), vec![2, 3, 4, 5, 1]);
167 
168     to_front(&mut map, 4);
169     assert_eq!(map.keys().copied().collect::<Vec<_>>(), vec![4, 2, 3, 5, 1]);
170 
171     to_back(&mut map, 3);
172     assert_eq!(map.keys().copied().collect::<Vec<_>>(), vec![4, 2, 5, 1, 3]);
173 
174     to_front(&mut map, 2);
175     assert_eq!(map.keys().copied().collect::<Vec<_>>(), vec![2, 4, 5, 1, 3]);
176 
177     to_back(&mut map, 3);
178     assert_eq!(map.keys().copied().collect::<Vec<_>>(), vec![2, 4, 5, 1, 3]);
179 
180     to_front(&mut map, 2);
181     assert_eq!(map.keys().copied().collect::<Vec<_>>(), vec![2, 4, 5, 1, 3]);
182 }
183 
184 #[test]
test_clear()185 fn test_clear() {
186     let mut map = LinkedHashMap::new();
187     map.insert(1, 10);
188     map.insert(2, 20);
189     map.clear();
190     assert!(map.get(&1).is_none());
191     assert!(map.get(&2).is_none());
192     assert!(map.is_empty());
193 }
194 
195 #[test]
test_iter()196 fn test_iter() {
197     let mut map = LinkedHashMap::new();
198 
199     // empty iter
200     assert_eq!(None, map.iter().next());
201 
202     map.insert("a", 10);
203     map.insert("b", 20);
204     map.insert("c", 30);
205 
206     // regular iter
207     let mut iter = map.iter();
208     assert_eq!((&"a", &10), iter.next().unwrap());
209     assert_eq!((&"b", &20), iter.next().unwrap());
210     assert_eq!((&"c", &30), iter.next().unwrap());
211     assert_eq!(None, iter.next());
212     assert_eq!(None, iter.next());
213 
214     let mut iter = map.iter();
215     assert_eq!((&"a", &10), iter.next().unwrap());
216     let mut iclone = iter.clone();
217     assert_eq!((&"b", &20), iter.next().unwrap());
218     assert_eq!((&"b", &20), iclone.next().unwrap());
219     assert_eq!((&"c", &30), iter.next().unwrap());
220     assert_eq!((&"c", &30), iclone.next().unwrap());
221 
222     // reversed iter
223     let mut rev_iter = map.iter().rev();
224     assert_eq!((&"c", &30), rev_iter.next().unwrap());
225     assert_eq!((&"b", &20), rev_iter.next().unwrap());
226     assert_eq!((&"a", &10), rev_iter.next().unwrap());
227     assert_eq!(None, rev_iter.next());
228     assert_eq!(None, rev_iter.next());
229 
230     // mixed
231     let mut mixed_iter = map.iter();
232     assert_eq!((&"a", &10), mixed_iter.next().unwrap());
233     assert_eq!((&"c", &30), mixed_iter.next_back().unwrap());
234     assert_eq!((&"b", &20), mixed_iter.next().unwrap());
235     assert_eq!(None, mixed_iter.next());
236     assert_eq!(None, mixed_iter.next_back());
237 }
238 
239 #[test]
test_borrow()240 fn test_borrow() {
241     #[derive(PartialEq, Eq, Hash)]
242     struct Foo(Bar);
243     #[derive(PartialEq, Eq, Hash)]
244     struct Bar(i32);
245 
246     impl ::std::borrow::Borrow<Bar> for Foo {
247         fn borrow(&self) -> &Bar {
248             &self.0
249         }
250     }
251 
252     let mut map = LinkedHashMap::new();
253     map.insert(Foo(Bar(1)), "a");
254     map.insert(Foo(Bar(2)), "b");
255 
256     assert!(map.contains_key(&Bar(1)));
257     assert!(map.contains_key(&Bar(2)));
258     assert!(map.contains_key(&Foo(Bar(1))));
259     assert!(map.contains_key(&Foo(Bar(2))));
260 
261     assert_eq!(map.get(&Bar(1)), Some(&"a"));
262     assert_eq!(map.get(&Bar(2)), Some(&"b"));
263     assert_eq!(map.get(&Foo(Bar(1))), Some(&"a"));
264     assert_eq!(map.get(&Foo(Bar(2))), Some(&"b"));
265 
266     assert_eq!(map.get_mut(&Bar(1)), Some(&mut "a"));
267     assert_eq!(map.get_mut(&Bar(2)), Some(&mut "b"));
268     assert_eq!(map.get_mut(&Foo(Bar(1))), Some(&mut "a"));
269     assert_eq!(map.get_mut(&Foo(Bar(2))), Some(&mut "b"));
270 
271     assert_eq!(map[&Bar(1)], "a");
272     assert_eq!(map[&Bar(2)], "b");
273     assert_eq!(map[&Foo(Bar(1))], "a");
274     assert_eq!(map[&Foo(Bar(2))], "b");
275 
276     assert_eq!(map.remove(&Bar(1)), Some("a"));
277     assert_eq!(map.remove(&Bar(2)), Some("b"));
278     assert_eq!(map.remove(&Foo(Bar(1))), None);
279     assert_eq!(map.remove(&Foo(Bar(2))), None);
280 }
281 
282 #[test]
test_iter_mut()283 fn test_iter_mut() {
284     let mut map = LinkedHashMap::new();
285     map.insert("a", 10);
286     map.insert("c", 30);
287     map.insert("b", 20);
288 
289     {
290         let mut iter = map.iter_mut();
291         let entry = iter.next().unwrap();
292         assert_eq!("a", *entry.0);
293         *entry.1 = 17;
294 
295         assert_eq!(format!("{:?}", iter), "[(\"c\", 30), (\"b\", 20)]");
296 
297         // reverse iterator
298         let mut iter = iter.rev();
299         let entry = iter.next().unwrap();
300         assert_eq!("b", *entry.0);
301         *entry.1 = 23;
302 
303         let entry = iter.next().unwrap();
304         assert_eq!("c", *entry.0);
305         assert_eq!(None, iter.next());
306         assert_eq!(None, iter.next());
307     }
308 
309     assert_eq!(17, map[&"a"]);
310     assert_eq!(23, map[&"b"]);
311 }
312 
313 #[test]
test_consuming_iter()314 fn test_consuming_iter() {
315     let map = {
316         let mut map = LinkedHashMap::new();
317         map.insert("a", 10);
318         map.insert("c", 30);
319         map.insert("b", 20);
320         map
321     };
322 
323     let mut iter = map.into_iter();
324     assert_eq!(Some(("a", 10)), iter.next());
325     assert_eq!(Some(("b", 20)), iter.next_back());
326     assert_eq!(iter.len(), 1);
327     assert_eq!(format!("{:?}", iter), "[(\"c\", 30)]");
328     assert_eq!(Some(("c", 30)), iter.next());
329     assert_eq!(None, iter.next());
330 }
331 
332 #[test]
test_consuming_iter_empty()333 fn test_consuming_iter_empty() {
334     let map = LinkedHashMap::<&str, i32>::new();
335     let mut iter = map.into_iter();
336     assert_eq!(None, iter.next());
337 }
338 
339 #[test]
test_consuming_iter_with_free_list()340 fn test_consuming_iter_with_free_list() {
341     let mut map = LinkedHashMap::new();
342     map.insert("a", 10);
343     map.insert("c", 30);
344     map.insert("b", 20);
345     map.remove("a");
346     map.remove("b");
347 
348     let mut iter = map.into_iter();
349     assert_eq!(Some(("c", 30)), iter.next());
350     assert_eq!(None, iter.next());
351 }
352 
353 #[test]
test_into_iter_drop()354 fn test_into_iter_drop() {
355     struct Counter<'a>(&'a mut usize);
356 
357     impl<'a> Drop for Counter<'a> {
358         fn drop(&mut self) {
359             *self.0 += 1;
360         }
361     }
362 
363     let mut a = 0;
364     let mut b = 0;
365     let mut c = 0;
366 
367     {
368         let mut map = LinkedHashMap::new();
369         map.insert("a", Counter(&mut a));
370         map.insert("b", Counter(&mut b));
371         map.insert("c", Counter(&mut c));
372 
373         let mut iter = map.into_iter();
374         assert_eq!(iter.next().map(|p| p.0), Some("a"));
375         assert_eq!(iter.next_back().map(|p| p.0), Some("c"));
376     }
377 
378     assert_eq!(a, 1);
379     assert_eq!(b, 1);
380     assert_eq!(c, 1);
381 }
382 
383 #[test]
test_drain()384 fn test_drain() {
385     use std::{cell::Cell, rc::Rc};
386 
387     struct Counter(Rc<Cell<u32>>);
388 
389     impl<'a> Drop for Counter {
390         fn drop(&mut self) {
391             self.0.set(self.0.get() + 1);
392         }
393     }
394 
395     let mut map = LinkedHashMap::new();
396 
397     let a = Rc::new(Cell::new(0));
398     let b = Rc::new(Cell::new(0));
399     let c = Rc::new(Cell::new(0));
400 
401     map.insert("a", Counter(a.clone()));
402     map.insert("b", Counter(b.clone()));
403     map.insert("c", Counter(c.clone()));
404 
405     let mut iter = map.drain();
406     assert_eq!(iter.next().map(|p| p.0), Some("a"));
407     assert_eq!(iter.next_back().map(|p| p.0), Some("c"));
408     assert_eq!(iter.next_back().map(|p| p.0), Some("b"));
409     assert!(iter.next().is_none());
410     assert!(iter.next_back().is_none());
411 
412     drop(iter);
413     assert_eq!(map.len(), 0);
414 
415     assert_eq!(a.get(), 1);
416     assert_eq!(b.get(), 1);
417     assert_eq!(c.get(), 1);
418 
419     map.insert("a", Counter(a.clone()));
420     map.insert("b", Counter(b.clone()));
421     map.insert("c", Counter(c.clone()));
422 
423     let mut iter = map.drain();
424     assert_eq!(iter.next().map(|p| p.0), Some("a"));
425     assert_eq!(iter.next().map(|p| p.0), Some("b"));
426     assert_eq!(iter.next_back().map(|p| p.0), Some("c"));
427     assert!(iter.next().is_none());
428     assert!(iter.next_back().is_none());
429 
430     drop(iter);
431     assert_eq!(map.len(), 0);
432 
433     assert_eq!(a.get(), 2);
434     assert_eq!(b.get(), 2);
435     assert_eq!(c.get(), 2);
436 
437     map.insert("a", Counter(a.clone()));
438     map.insert("b", Counter(b.clone()));
439     map.insert("c", Counter(c.clone()));
440 
441     map.drain();
442     assert_eq!(map.len(), 0);
443 
444     assert_eq!(a.get(), 3);
445     assert_eq!(b.get(), 3);
446     assert_eq!(c.get(), 3);
447 }
448 
449 #[test]
test_send_sync()450 fn test_send_sync() {
451     fn is_send_sync<T: Send + Sync>() {}
452 
453     is_send_sync::<LinkedHashMap<u32, i32>>();
454     is_send_sync::<linked_hash_map::Entry<u32, i32, ()>>();
455     is_send_sync::<linked_hash_map::RawEntryBuilder<u32, i32, ()>>();
456     is_send_sync::<linked_hash_map::RawEntryBuilderMut<u32, i32, ()>>();
457     is_send_sync::<linked_hash_map::RawEntryMut<u32, i32, ()>>();
458     is_send_sync::<linked_hash_map::Iter<u32, i32>>();
459     is_send_sync::<linked_hash_map::IterMut<u32, i32>>();
460     is_send_sync::<linked_hash_map::Drain<u32, i32>>();
461     is_send_sync::<linked_hash_map::Keys<u32, i32>>();
462     is_send_sync::<linked_hash_map::Values<u32, i32>>();
463 }
464 
465 #[test]
test_retain()466 fn test_retain() {
467     use std::{cell::Cell, rc::Rc};
468 
469     let xs = [1, 2, 3, 4, 5, 6];
470     let mut map: LinkedHashMap<String, i32> = xs.iter().map(|i| (i.to_string(), *i)).collect();
471     map.retain(|_, v| *v % 2 == 0);
472     assert_eq!(map.len(), 3);
473     assert!(map.contains_key("2"));
474     assert!(map.contains_key("4"));
475     assert!(map.contains_key("6"));
476 
477     struct Counter(Rc<Cell<u32>>);
478 
479     impl<'a> Drop for Counter {
480         fn drop(&mut self) {
481             self.0.set(self.0.get() + 1);
482         }
483     }
484 
485     let c = Rc::new(Cell::new(0));
486 
487     let mut map = LinkedHashMap::new();
488     map.insert(1, Counter(Rc::clone(&c)));
489     map.insert(2, Counter(Rc::clone(&c)));
490     map.insert(3, Counter(Rc::clone(&c)));
491     map.insert(4, Counter(Rc::clone(&c)));
492 
493     map.retain(|k, _| *k % 2 == 0);
494 
495     assert!(c.get() == 2);
496     drop(map);
497     assert!(c.get() == 4);
498 }
499