]> git.proxmox.com Git - rustc.git/blame - src/libcollectionstest/btree/map.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / libcollectionstest / btree / map.rs
CommitLineData
c34b1796
AL
1// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
2// file at the top-level directory of this distribution and at
3// http://rust-lang.org/COPYRIGHT.
4//
5// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8// option. This file may not be copied, modified, or distributed
9// except according to those terms.
10
11use std::collections::BTreeMap;
12use std::collections::Bound::{Excluded, Included, Unbounded, self};
13use std::collections::btree_map::Entry::{Occupied, Vacant};
d9579d0f 14use std::rc::Rc;
c34b1796
AL
15
16#[test]
17fn test_basic_large() {
18 let mut map = BTreeMap::new();
19 let size = 10000;
20 assert_eq!(map.len(), 0);
21
22 for i in 0..size {
23 assert_eq!(map.insert(i, 10*i), None);
24 assert_eq!(map.len(), i + 1);
25 }
26
27 for i in 0..size {
28 assert_eq!(map.get(&i).unwrap(), &(i*10));
29 }
30
31 for i in size..size*2 {
32 assert_eq!(map.get(&i), None);
33 }
34
35 for i in 0..size {
36 assert_eq!(map.insert(i, 100*i), Some(10*i));
37 assert_eq!(map.len(), size);
38 }
39
40 for i in 0..size {
41 assert_eq!(map.get(&i).unwrap(), &(i*100));
42 }
43
44 for i in 0..size/2 {
45 assert_eq!(map.remove(&(i*2)), Some(i*200));
46 assert_eq!(map.len(), size - i - 1);
47 }
48
49 for i in 0..size/2 {
50 assert_eq!(map.get(&(2*i)), None);
51 assert_eq!(map.get(&(2*i+1)).unwrap(), &(i*200 + 100));
52 }
53
54 for i in 0..size/2 {
55 assert_eq!(map.remove(&(2*i)), None);
56 assert_eq!(map.remove(&(2*i+1)), Some(i*200 + 100));
57 assert_eq!(map.len(), size/2 - i - 1);
58 }
59}
60
61#[test]
62fn test_basic_small() {
63 let mut map = BTreeMap::new();
64 assert_eq!(map.remove(&1), None);
65 assert_eq!(map.get(&1), None);
66 assert_eq!(map.insert(1, 1), None);
67 assert_eq!(map.get(&1), Some(&1));
68 assert_eq!(map.insert(1, 2), Some(1));
69 assert_eq!(map.get(&1), Some(&2));
70 assert_eq!(map.insert(2, 4), None);
71 assert_eq!(map.get(&2), Some(&4));
72 assert_eq!(map.remove(&1), Some(2));
73 assert_eq!(map.remove(&2), Some(4));
74 assert_eq!(map.remove(&1), None);
75}
76
77#[test]
78fn test_iter() {
79 let size = 10000;
80
81 // Forwards
82 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
83
84 fn test<T>(size: usize, mut iter: T) where T: Iterator<Item=(usize, usize)> {
85 for i in 0..size {
86 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
87 assert_eq!(iter.next().unwrap(), (i, i));
88 }
89 assert_eq!(iter.size_hint(), (0, Some(0)));
90 assert_eq!(iter.next(), None);
91 }
92 test(size, map.iter().map(|(&k, &v)| (k, v)));
93 test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
94 test(size, map.into_iter());
95}
96
97#[test]
98fn test_iter_rev() {
99 let size = 10000;
100
101 // Forwards
102 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
103
104 fn test<T>(size: usize, mut iter: T) where T: Iterator<Item=(usize, usize)> {
105 for i in 0..size {
106 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
107 assert_eq!(iter.next().unwrap(), (size - i - 1, size - i - 1));
108 }
109 assert_eq!(iter.size_hint(), (0, Some(0)));
110 assert_eq!(iter.next(), None);
111 }
112 test(size, map.iter().rev().map(|(&k, &v)| (k, v)));
113 test(size, map.iter_mut().rev().map(|(&k, &mut v)| (k, v)));
114 test(size, map.into_iter().rev());
115}
116
54a0048b
SL
117#[test]
118fn test_values_mut() {
119 let mut a = BTreeMap::new();
120 a.insert(1, String::from("hello"));
121 a.insert(2, String::from("goodbye"));
122
123 for value in a.values_mut() {
124 value.push_str("!");
125 }
126
127 let values: Vec<String> = a.values().cloned().collect();
128 assert_eq!(values, [String::from("hello!"),
129 String::from("goodbye!")]);
130}
131
c34b1796
AL
132#[test]
133fn test_iter_mixed() {
134 let size = 10000;
135
136 // Forwards
137 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
138
139 fn test<T>(size: usize, mut iter: T)
140 where T: Iterator<Item=(usize, usize)> + DoubleEndedIterator {
141 for i in 0..size / 4 {
142 assert_eq!(iter.size_hint(), (size - i * 2, Some(size - i * 2)));
143 assert_eq!(iter.next().unwrap(), (i, i));
144 assert_eq!(iter.next_back().unwrap(), (size - i - 1, size - i - 1));
145 }
146 for i in size / 4..size * 3 / 4 {
147 assert_eq!(iter.size_hint(), (size * 3 / 4 - i, Some(size * 3 / 4 - i)));
148 assert_eq!(iter.next().unwrap(), (i, i));
149 }
150 assert_eq!(iter.size_hint(), (0, Some(0)));
151 assert_eq!(iter.next(), None);
152 }
153 test(size, map.iter().map(|(&k, &v)| (k, v)));
154 test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
155 test(size, map.into_iter());
156}
157
158#[test]
159fn test_range_small() {
160 let size = 5;
161
162 // Forwards
163 let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
164
165 let mut j = 0;
166 for ((&k, &v), i) in map.range(Included(&2), Unbounded).zip(2..size) {
167 assert_eq!(k, i);
168 assert_eq!(v, i);
169 j += 1;
170 }
171 assert_eq!(j, size - 2);
172}
173
174#[test]
175fn test_range_1000() {
176 let size = 1000;
177 let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
178
179 fn test(map: &BTreeMap<u32, u32>, size: u32, min: Bound<&u32>, max: Bound<&u32>) {
180 let mut kvs = map.range(min, max).map(|(&k, &v)| (k, v));
181 let mut pairs = (0..size).map(|i| (i, i));
182
183 for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
184 assert_eq!(kv, pair);
185 }
186 assert_eq!(kvs.next(), None);
187 assert_eq!(pairs.next(), None);
188 }
189 test(&map, size, Included(&0), Excluded(&size));
190 test(&map, size, Unbounded, Excluded(&size));
191 test(&map, size, Included(&0), Included(&(size - 1)));
192 test(&map, size, Unbounded, Included(&(size - 1)));
193 test(&map, size, Included(&0), Unbounded);
194 test(&map, size, Unbounded, Unbounded);
195}
196
197#[test]
198fn test_range() {
199 let size = 200;
200 let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
201
202 for i in 0..size {
203 for j in i..size {
204 let mut kvs = map.range(Included(&i), Included(&j)).map(|(&k, &v)| (k, v));
9cc50fc6 205 let mut pairs = (i..j+1).map(|i| (i, i));
c34b1796
AL
206
207 for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
208 assert_eq!(kv, pair);
209 }
210 assert_eq!(kvs.next(), None);
211 assert_eq!(pairs.next(), None);
212 }
213 }
214}
215
d9579d0f
AL
216#[test]
217fn test_borrow() {
218 // make sure these compile -- using the Borrow trait
219 {
220 let mut map = BTreeMap::new();
221 map.insert("0".to_string(), 1);
222 assert_eq!(map["0"], 1);
223 }
224
225 {
226 let mut map = BTreeMap::new();
227 map.insert(Box::new(0), 1);
228 assert_eq!(map[&0], 1);
229 }
230
231 {
232 let mut map = BTreeMap::new();
233 map.insert(Box::new([0, 1]) as Box<[i32]>, 1);
234 assert_eq!(map[&[0, 1][..]], 1);
235 }
236
237 {
238 let mut map = BTreeMap::new();
239 map.insert(Rc::new(0), 1);
240 assert_eq!(map[&0], 1);
241 }
242}
243
c34b1796
AL
244#[test]
245fn test_entry(){
246 let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
247
248 let mut map: BTreeMap<_, _> = xs.iter().cloned().collect();
249
250 // Existing key (insert)
251 match map.entry(1) {
252 Vacant(_) => unreachable!(),
253 Occupied(mut view) => {
254 assert_eq!(view.get(), &10);
255 assert_eq!(view.insert(100), 10);
256 }
257 }
258 assert_eq!(map.get(&1).unwrap(), &100);
259 assert_eq!(map.len(), 6);
260
261
262 // Existing key (update)
263 match map.entry(2) {
264 Vacant(_) => unreachable!(),
265 Occupied(mut view) => {
266 let v = view.get_mut();
267 *v *= 10;
268 }
269 }
270 assert_eq!(map.get(&2).unwrap(), &200);
271 assert_eq!(map.len(), 6);
272
273 // Existing key (take)
274 match map.entry(3) {
275 Vacant(_) => unreachable!(),
276 Occupied(view) => {
277 assert_eq!(view.remove(), 30);
278 }
279 }
280 assert_eq!(map.get(&3), None);
281 assert_eq!(map.len(), 5);
282
283
284 // Inexistent key (insert)
285 match map.entry(10) {
286 Occupied(_) => unreachable!(),
287 Vacant(view) => {
288 assert_eq!(*view.insert(1000), 1000);
289 }
290 }
291 assert_eq!(map.get(&10).unwrap(), &1000);
292 assert_eq!(map.len(), 6);
293}
294
62682a34
SL
295#[test]
296fn test_extend_ref() {
297 let mut a = BTreeMap::new();
298 a.insert(1, "one");
299 let mut b = BTreeMap::new();
300 b.insert(2, "two");
301 b.insert(3, "three");
302
303 a.extend(&b);
304
305 assert_eq!(a.len(), 3);
306 assert_eq!(a[&1], "one");
307 assert_eq!(a[&2], "two");
308 assert_eq!(a[&3], "three");
309}
310
b039eaaf
SL
311#[test]
312fn test_zst() {
313 let mut m = BTreeMap::new();
314 assert_eq!(m.len(), 0);
315
316 assert_eq!(m.insert((), ()), None);
317 assert_eq!(m.len(), 1);
318
319 assert_eq!(m.insert((), ()), Some(()));
320 assert_eq!(m.len(), 1);
321 assert_eq!(m.iter().count(), 1);
322
323 m.clear();
324 assert_eq!(m.len(), 0);
325
326 for _ in 0..100 {
327 m.insert((), ());
328 }
329
330 assert_eq!(m.len(), 1);
331 assert_eq!(m.iter().count(), 1);
332}
333
334// This test's only purpose is to ensure that zero-sized keys with nonsensical orderings
335// do not cause segfaults when used with zero-sized values. All other map behavior is
336// undefined.
337#[test]
338fn test_bad_zst() {
339 use std::cmp::Ordering;
340
341 struct Bad;
342
343 impl PartialEq for Bad {
344 fn eq(&self, _: &Self) -> bool { false }
345 }
346
347 impl Eq for Bad {}
348
349 impl PartialOrd for Bad {
350 fn partial_cmp(&self, _: &Self) -> Option<Ordering> { Some(Ordering::Less) }
351 }
352
353 impl Ord for Bad {
354 fn cmp(&self, _: &Self) -> Ordering { Ordering::Less }
355 }
356
357 let mut m = BTreeMap::new();
358
359 for _ in 0..100 {
360 m.insert(Bad, Bad);
361 }
362}
363
9cc50fc6
SL
364#[test]
365fn test_clone() {
366 let mut map = BTreeMap::new();
367 let size = 100;
368 assert_eq!(map.len(), 0);
369
370 for i in 0..size {
371 assert_eq!(map.insert(i, 10*i), None);
372 assert_eq!(map.len(), i + 1);
373 assert_eq!(map, map.clone());
374 }
375
376 for i in 0..size {
377 assert_eq!(map.insert(i, 100*i), Some(10*i));
378 assert_eq!(map.len(), size);
379 assert_eq!(map, map.clone());
380 }
381
382 for i in 0..size/2 {
383 assert_eq!(map.remove(&(i*2)), Some(i*200));
384 assert_eq!(map.len(), size - i - 1);
385 assert_eq!(map, map.clone());
386 }
387
388 for i in 0..size/2 {
389 assert_eq!(map.remove(&(2*i)), None);
390 assert_eq!(map.remove(&(2*i+1)), Some(i*200 + 100));
391 assert_eq!(map.len(), size/2 - i - 1);
392 assert_eq!(map, map.clone());
393 }
394}
395
396#[test]
7453a54e 397#[allow(dead_code)]
9cc50fc6
SL
398fn test_variance() {
399 use std::collections::btree_map::{Iter, IntoIter, Range, Keys, Values};
400
401 fn map_key<'new>(v: BTreeMap<&'static str, ()>) -> BTreeMap<&'new str, ()> { v }
402 fn map_val<'new>(v: BTreeMap<(), &'static str>) -> BTreeMap<(), &'new str> { v }
403 fn iter_key<'a, 'new>(v: Iter<'a, &'static str, ()>) -> Iter<'a, &'new str, ()> { v }
404 fn iter_val<'a, 'new>(v: Iter<'a, (), &'static str>) -> Iter<'a, (), &'new str> { v }
405 fn into_iter_key<'new>(v: IntoIter<&'static str, ()>) -> IntoIter<&'new str, ()> { v }
406 fn into_iter_val<'new>(v: IntoIter<(), &'static str>) -> IntoIter<(), &'new str> { v }
407 fn range_key<'a, 'new>(v: Range<'a, &'static str, ()>) -> Range<'a, &'new str, ()> { v }
408 fn range_val<'a, 'new>(v: Range<'a, (), &'static str>) -> Range<'a, (), &'new str> { v }
409 fn keys<'a, 'new>(v: Keys<'a, &'static str, ()>) -> Keys<'a, &'new str, ()> { v }
410 fn vals<'a, 'new>(v: Values<'a, (), &'static str>) -> Values<'a, (), &'new str> { v }
411}
412
54a0048b
SL
413#[test]
414fn test_occupied_entry_key() {
415 let mut a = BTreeMap::new();
416 let key = "hello there";
417 let value = "value goes here";
418 assert!(a.is_empty());
419 a.insert(key.clone(), value.clone());
420 assert_eq!(a.len(), 1);
421 assert_eq!(a[key], value);
422
423 match a.entry(key.clone()) {
424 Vacant(_) => panic!(),
425 Occupied(e) => assert_eq!(key, *e.key()),
426 }
427 assert_eq!(a.len(), 1);
428 assert_eq!(a[key], value);
429}
430
431#[test]
432fn test_vacant_entry_key() {
433 let mut a = BTreeMap::new();
434 let key = "hello there";
435 let value = "value goes here";
436
437 assert!(a.is_empty());
438 match a.entry(key.clone()) {
439 Occupied(_) => panic!(),
440 Vacant(e) => {
441 assert_eq!(key, *e.key());
442 e.insert(value.clone());
443 },
444 }
445 assert_eq!(a.len(), 1);
446 assert_eq!(a[key], value);
447}
448
c34b1796
AL
449mod bench {
450 use std::collections::BTreeMap;
9346a6ac 451 use std::__rand::{Rng, thread_rng};
c34b1796
AL
452
453 use test::{Bencher, black_box};
454
455 map_insert_rand_bench!{insert_rand_100, 100, BTreeMap}
456 map_insert_rand_bench!{insert_rand_10_000, 10_000, BTreeMap}
457
458 map_insert_seq_bench!{insert_seq_100, 100, BTreeMap}
459 map_insert_seq_bench!{insert_seq_10_000, 10_000, BTreeMap}
460
461 map_find_rand_bench!{find_rand_100, 100, BTreeMap}
462 map_find_rand_bench!{find_rand_10_000, 10_000, BTreeMap}
463
464 map_find_seq_bench!{find_seq_100, 100, BTreeMap}
465 map_find_seq_bench!{find_seq_10_000, 10_000, BTreeMap}
466
467 fn bench_iter(b: &mut Bencher, size: i32) {
468 let mut map = BTreeMap::<i32, i32>::new();
9346a6ac 469 let mut rng = thread_rng();
c34b1796
AL
470
471 for _ in 0..size {
472 map.insert(rng.gen(), rng.gen());
473 }
474
475 b.iter(|| {
476 for entry in &map {
477 black_box(entry);
478 }
479 });
480 }
481
482 #[bench]
483 pub fn iter_20(b: &mut Bencher) {
484 bench_iter(b, 20);
485 }
486
487 #[bench]
488 pub fn iter_1000(b: &mut Bencher) {
489 bench_iter(b, 1000);
490 }
491
492 #[bench]
493 pub fn iter_100000(b: &mut Bencher) {
494 bench_iter(b, 100000);
495 }
496}