src/libcollectionstest/btree/map.rs

   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
  11 use std::collections::BTreeMap;
  12 use std::collections::Bound::{self, Excluded, Included, Unbounded};
  13 use std::collections::btree_map::Entry::{Occupied, Vacant};
  14 use std::rc::Rc;
  15
  16 use std::iter::FromIterator;
  17 use super::DeterministicRng;
  18
  19 #[test]
  20 fn test_basic_large() {
  21     let mut map = BTreeMap::new();
  22     let size = 10000;
  23     assert_eq!(map.len(), 0);
  24
  25     for i in 0..size {
  26         assert_eq!(map.insert(i, 10 * i), None);
  27         assert_eq!(map.len(), i + 1);
  28     }
  29
  30     for i in 0..size {
  31         assert_eq!(map.get(&i).unwrap(), &(i * 10));
  32     }
  33
  34     for i in size..size * 2 {
  35         assert_eq!(map.get(&i), None);
  36     }
  37
  38     for i in 0..size {
  39         assert_eq!(map.insert(i, 100 * i), Some(10 * i));
  40         assert_eq!(map.len(), size);
  41     }
  42
  43     for i in 0..size {
  44         assert_eq!(map.get(&i).unwrap(), &(i * 100));
  45     }
  46
  47     for i in 0..size / 2 {
  48         assert_eq!(map.remove(&(i * 2)), Some(i * 200));
  49         assert_eq!(map.len(), size - i - 1);
  50     }
  51
  52     for i in 0..size / 2 {
  53         assert_eq!(map.get(&(2 * i)), None);
  54         assert_eq!(map.get(&(2 * i + 1)).unwrap(), &(i * 200 + 100));
  55     }
  56
  57     for i in 0..size / 2 {
  58         assert_eq!(map.remove(&(2 * i)), None);
  59         assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
  60         assert_eq!(map.len(), size / 2 - i - 1);
  61     }
  62 }
  63
  64 #[test]
  65 fn test_basic_small() {
  66     let mut map = BTreeMap::new();
  67     assert_eq!(map.remove(&1), None);
  68     assert_eq!(map.get(&1), None);
  69     assert_eq!(map.insert(1, 1), None);
  70     assert_eq!(map.get(&1), Some(&1));
  71     assert_eq!(map.insert(1, 2), Some(1));
  72     assert_eq!(map.get(&1), Some(&2));
  73     assert_eq!(map.insert(2, 4), None);
  74     assert_eq!(map.get(&2), Some(&4));
  75     assert_eq!(map.remove(&1), Some(2));
  76     assert_eq!(map.remove(&2), Some(4));
  77     assert_eq!(map.remove(&1), None);
  78 }
  79
  80 #[test]
  81 fn test_iter() {
  82     let size = 10000;
  83
  84     // Forwards
  85     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
  86
  87     fn test<T>(size: usize, mut iter: T)
  88         where T: Iterator<Item = (usize, usize)>
  89     {
  90         for i in 0..size {
  91             assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
  92             assert_eq!(iter.next().unwrap(), (i, i));
  93         }
  94         assert_eq!(iter.size_hint(), (0, Some(0)));
  95         assert_eq!(iter.next(), None);
  96     }
  97     test(size, map.iter().map(|(&k, &v)| (k, v)));
  98     test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
  99     test(size, map.into_iter());
 100 }
 101
 102 #[test]
 103 fn test_iter_rev() {
 104     let size = 10000;
 105
 106     // Forwards
 107     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 108
 109     fn test<T>(size: usize, mut iter: T)
 110         where T: Iterator<Item = (usize, usize)>
 111     {
 112         for i in 0..size {
 113             assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
 114             assert_eq!(iter.next().unwrap(), (size - i - 1, size - i - 1));
 115         }
 116         assert_eq!(iter.size_hint(), (0, Some(0)));
 117         assert_eq!(iter.next(), None);
 118     }
 119     test(size, map.iter().rev().map(|(&k, &v)| (k, v)));
 120     test(size, map.iter_mut().rev().map(|(&k, &mut v)| (k, v)));
 121     test(size, map.into_iter().rev());
 122 }
 123
 124 #[test]
 125 fn test_values_mut() {
 126     let mut a = BTreeMap::new();
 127     a.insert(1, String::from("hello"));
 128     a.insert(2, String::from("goodbye"));
 129
 130     for value in a.values_mut() {
 131         value.push_str("!");
 132     }
 133
 134     let values: Vec<String> = a.values().cloned().collect();
 135     assert_eq!(values, [String::from("hello!"), String::from("goodbye!")]);
 136 }
 137
 138 #[test]
 139 fn test_iter_mixed() {
 140     let size = 10000;
 141
 142     // Forwards
 143     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 144
 145     fn test<T>(size: usize, mut iter: T)
 146         where T: Iterator<Item = (usize, usize)> + DoubleEndedIterator
 147     {
 148         for i in 0..size / 4 {
 149             assert_eq!(iter.size_hint(), (size - i * 2, Some(size - i * 2)));
 150             assert_eq!(iter.next().unwrap(), (i, i));
 151             assert_eq!(iter.next_back().unwrap(), (size - i - 1, size - i - 1));
 152         }
 153         for i in size / 4..size * 3 / 4 {
 154             assert_eq!(iter.size_hint(), (size * 3 / 4 - i, Some(size * 3 / 4 - i)));
 155             assert_eq!(iter.next().unwrap(), (i, i));
 156         }
 157         assert_eq!(iter.size_hint(), (0, Some(0)));
 158         assert_eq!(iter.next(), None);
 159     }
 160     test(size, map.iter().map(|(&k, &v)| (k, v)));
 161     test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
 162     test(size, map.into_iter());
 163 }
 164
 165 #[test]
 166 fn test_range_small() {
 167     let size = 5;
 168
 169     // Forwards
 170     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 171
 172     let mut j = 0;
 173     for ((&k, &v), i) in map.range(Included(&2), Unbounded).zip(2..size) {
 174         assert_eq!(k, i);
 175         assert_eq!(v, i);
 176         j += 1;
 177     }
 178     assert_eq!(j, size - 2);
 179 }
 180
 181 #[test]
 182 fn test_range_1000() {
 183     let size = 1000;
 184     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 185
 186     fn test(map: &BTreeMap<u32, u32>, size: u32, min: Bound<&u32>, max: Bound<&u32>) {
 187         let mut kvs = map.range(min, max).map(|(&k, &v)| (k, v));
 188         let mut pairs = (0..size).map(|i| (i, i));
 189
 190         for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
 191             assert_eq!(kv, pair);
 192         }
 193         assert_eq!(kvs.next(), None);
 194         assert_eq!(pairs.next(), None);
 195     }
 196     test(&map, size, Included(&0), Excluded(&size));
 197     test(&map, size, Unbounded, Excluded(&size));
 198     test(&map, size, Included(&0), Included(&(size - 1)));
 199     test(&map, size, Unbounded, Included(&(size - 1)));
 200     test(&map, size, Included(&0), Unbounded);
 201     test(&map, size, Unbounded, Unbounded);
 202 }
 203
 204 #[test]
 205 fn test_range() {
 206     let size = 200;
 207     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 208
 209     for i in 0..size {
 210         for j in i..size {
 211             let mut kvs = map.range(Included(&i), Included(&j)).map(|(&k, &v)| (k, v));
 212             let mut pairs = (i..j + 1).map(|i| (i, i));
 213
 214             for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
 215                 assert_eq!(kv, pair);
 216             }
 217             assert_eq!(kvs.next(), None);
 218             assert_eq!(pairs.next(), None);
 219         }
 220     }
 221 }
 222
 223 #[test]
 224 fn test_borrow() {
 225     // make sure these compile -- using the Borrow trait
 226     {
 227         let mut map = BTreeMap::new();
 228         map.insert("0".to_string(), 1);
 229         assert_eq!(map["0"], 1);
 230     }
 231
 232     {
 233         let mut map = BTreeMap::new();
 234         map.insert(Box::new(0), 1);
 235         assert_eq!(map[&0], 1);
 236     }
 237
 238     {
 239         let mut map = BTreeMap::new();
 240         map.insert(Box::new([0, 1]) as Box<[i32]>, 1);
 241         assert_eq!(map[&[0, 1][..]], 1);
 242     }
 243
 244     {
 245         let mut map = BTreeMap::new();
 246         map.insert(Rc::new(0), 1);
 247         assert_eq!(map[&0], 1);
 248     }
 249 }
 250
 251 #[test]
 252 fn test_entry() {
 253     let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
 254
 255     let mut map: BTreeMap<_, _> = xs.iter().cloned().collect();
 256
 257     // Existing key (insert)
 258     match map.entry(1) {
 259         Vacant(_) => unreachable!(),
 260         Occupied(mut view) => {
 261             assert_eq!(view.get(), &10);
 262             assert_eq!(view.insert(100), 10);
 263         }
 264     }
 265     assert_eq!(map.get(&1).unwrap(), &100);
 266     assert_eq!(map.len(), 6);
 267
 268
 269     // Existing key (update)
 270     match map.entry(2) {
 271         Vacant(_) => unreachable!(),
 272         Occupied(mut view) => {
 273             let v = view.get_mut();
 274             *v *= 10;
 275         }
 276     }
 277     assert_eq!(map.get(&2).unwrap(), &200);
 278     assert_eq!(map.len(), 6);
 279
 280     // Existing key (take)
 281     match map.entry(3) {
 282         Vacant(_) => unreachable!(),
 283         Occupied(view) => {
 284             assert_eq!(view.remove(), 30);
 285         }
 286     }
 287     assert_eq!(map.get(&3), None);
 288     assert_eq!(map.len(), 5);
 289
 290
 291     // Inexistent key (insert)
 292     match map.entry(10) {
 293         Occupied(_) => unreachable!(),
 294         Vacant(view) => {
 295             assert_eq!(*view.insert(1000), 1000);
 296         }
 297     }
 298     assert_eq!(map.get(&10).unwrap(), &1000);
 299     assert_eq!(map.len(), 6);
 300 }
 301
 302 #[test]
 303 fn test_extend_ref() {
 304     let mut a = BTreeMap::new();
 305     a.insert(1, "one");
 306     let mut b = BTreeMap::new();
 307     b.insert(2, "two");
 308     b.insert(3, "three");
 309
 310     a.extend(&b);
 311
 312     assert_eq!(a.len(), 3);
 313     assert_eq!(a[&1], "one");
 314     assert_eq!(a[&2], "two");
 315     assert_eq!(a[&3], "three");
 316 }
 317
 318 #[test]
 319 fn test_zst() {
 320     let mut m = BTreeMap::new();
 321     assert_eq!(m.len(), 0);
 322
 323     assert_eq!(m.insert((), ()), None);
 324     assert_eq!(m.len(), 1);
 325
 326     assert_eq!(m.insert((), ()), Some(()));
 327     assert_eq!(m.len(), 1);
 328     assert_eq!(m.iter().count(), 1);
 329
 330     m.clear();
 331     assert_eq!(m.len(), 0);
 332
 333     for _ in 0..100 {
 334         m.insert((), ());
 335     }
 336
 337     assert_eq!(m.len(), 1);
 338     assert_eq!(m.iter().count(), 1);
 339 }
 340
 341 // This test's only purpose is to ensure that zero-sized keys with nonsensical orderings
 342 // do not cause segfaults when used with zero-sized values. All other map behavior is
 343 // undefined.
 344 #[test]
 345 fn test_bad_zst() {
 346     use std::cmp::Ordering;
 347
 348     struct Bad;
 349
 350     impl PartialEq for Bad {
 351         fn eq(&self, _: &Self) -> bool {
 352             false
 353         }
 354     }
 355
 356     impl Eq for Bad {}
 357
 358     impl PartialOrd for Bad {
 359         fn partial_cmp(&self, _: &Self) -> Option<Ordering> {
 360             Some(Ordering::Less)
 361         }
 362     }
 363
 364     impl Ord for Bad {
 365         fn cmp(&self, _: &Self) -> Ordering {
 366             Ordering::Less
 367         }
 368     }
 369
 370     let mut m = BTreeMap::new();
 371
 372     for _ in 0..100 {
 373         m.insert(Bad, Bad);
 374     }
 375 }
 376
 377 #[test]
 378 fn test_clone() {
 379     let mut map = BTreeMap::new();
 380     let size = 100;
 381     assert_eq!(map.len(), 0);
 382
 383     for i in 0..size {
 384         assert_eq!(map.insert(i, 10 * i), None);
 385         assert_eq!(map.len(), i + 1);
 386         assert_eq!(map, map.clone());
 387     }
 388
 389     for i in 0..size {
 390         assert_eq!(map.insert(i, 100 * i), Some(10 * i));
 391         assert_eq!(map.len(), size);
 392         assert_eq!(map, map.clone());
 393     }
 394
 395     for i in 0..size / 2 {
 396         assert_eq!(map.remove(&(i * 2)), Some(i * 200));
 397         assert_eq!(map.len(), size - i - 1);
 398         assert_eq!(map, map.clone());
 399     }
 400
 401     for i in 0..size / 2 {
 402         assert_eq!(map.remove(&(2 * i)), None);
 403         assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
 404         assert_eq!(map.len(), size / 2 - i - 1);
 405         assert_eq!(map, map.clone());
 406     }
 407 }
 408
 409 #[test]
 410 #[allow(dead_code)]
 411 fn test_variance() {
 412     use std::collections::btree_map::{Iter, IntoIter, Range, Keys, Values};
 413
 414     fn map_key<'new>(v: BTreeMap<&'static str, ()>) -> BTreeMap<&'new str, ()> {
 415         v
 416     }
 417     fn map_val<'new>(v: BTreeMap<(), &'static str>) -> BTreeMap<(), &'new str> {
 418         v
 419     }
 420     fn iter_key<'a, 'new>(v: Iter<'a, &'static str, ()>) -> Iter<'a, &'new str, ()> {
 421         v
 422     }
 423     fn iter_val<'a, 'new>(v: Iter<'a, (), &'static str>) -> Iter<'a, (), &'new str> {
 424         v
 425     }
 426     fn into_iter_key<'new>(v: IntoIter<&'static str, ()>) -> IntoIter<&'new str, ()> {
 427         v
 428     }
 429     fn into_iter_val<'new>(v: IntoIter<(), &'static str>) -> IntoIter<(), &'new str> {
 430         v
 431     }
 432     fn range_key<'a, 'new>(v: Range<'a, &'static str, ()>) -> Range<'a, &'new str, ()> {
 433         v
 434     }
 435     fn range_val<'a, 'new>(v: Range<'a, (), &'static str>) -> Range<'a, (), &'new str> {
 436         v
 437     }
 438     fn keys<'a, 'new>(v: Keys<'a, &'static str, ()>) -> Keys<'a, &'new str, ()> {
 439         v
 440     }
 441     fn vals<'a, 'new>(v: Values<'a, (), &'static str>) -> Values<'a, (), &'new str> {
 442         v
 443     }
 444 }
 445
 446 #[test]
 447 fn test_occupied_entry_key() {
 448     let mut a = BTreeMap::new();
 449     let key = "hello there";
 450     let value = "value goes here";
 451     assert!(a.is_empty());
 452     a.insert(key.clone(), value.clone());
 453     assert_eq!(a.len(), 1);
 454     assert_eq!(a[key], value);
 455
 456     match a.entry(key.clone()) {
 457         Vacant(_) => panic!(),
 458         Occupied(e) => assert_eq!(key, *e.key()),
 459     }
 460     assert_eq!(a.len(), 1);
 461     assert_eq!(a[key], value);
 462 }
 463
 464 #[test]
 465 fn test_vacant_entry_key() {
 466     let mut a = BTreeMap::new();
 467     let key = "hello there";
 468     let value = "value goes here";
 469
 470     assert!(a.is_empty());
 471     match a.entry(key.clone()) {
 472         Occupied(_) => panic!(),
 473         Vacant(e) => {
 474             assert_eq!(key, *e.key());
 475             e.insert(value.clone());
 476         }
 477     }
 478     assert_eq!(a.len(), 1);
 479     assert_eq!(a[key], value);
 480 }
 481
 482 macro_rules! create_append_test {
 483     ($name:ident, $len:expr) => {
 484         #[test]
 485         fn $name() {
 486             let mut a = BTreeMap::new();
 487             for i in 0..8 {
 488                 a.insert(i, i);
 489             }
 490
 491             let mut b = BTreeMap::new();
 492             for i in 5..$len {
 493                 b.insert(i, 2*i);
 494             }
 495
 496             a.append(&mut b);
 497
 498             assert_eq!(a.len(), $len);
 499             assert_eq!(b.len(), 0);
 500
 501             for i in 0..$len {
 502                 if i < 5 {
 503                     assert_eq!(a[&i], i);
 504                 } else {
 505                     assert_eq!(a[&i], 2*i);
 506                 }
 507             }
 508
 509             assert_eq!(a.remove(&($len-1)), Some(2*($len-1)));
 510             assert_eq!(a.insert($len-1, 20), None);
 511         }
 512     };
 513 }
 514
 515 // These are mostly for testing the algorithm that "fixes" the right edge after insertion.
 516 // Single node.
 517 create_append_test!(test_append_9, 9);
 518 // Two leafs that don't need fixing.
 519 create_append_test!(test_append_17, 17);
 520 // Two leafs where the second one ends up underfull and needs stealing at the end.
 521 create_append_test!(test_append_14, 14);
 522 // Two leafs where the second one ends up empty because the insertion finished at the root.
 523 create_append_test!(test_append_12, 12);
 524 // Three levels; insertion finished at the root.
 525 create_append_test!(test_append_144, 144);
 526 // Three levels; insertion finished at leaf while there is an empty node on the second level.
 527 create_append_test!(test_append_145, 145);
 528 // Tests for several randomly chosen sizes.
 529 create_append_test!(test_append_170, 170);
 530 create_append_test!(test_append_181, 181);
 531 create_append_test!(test_append_239, 239);
 532 create_append_test!(test_append_1700, 1700);
 533
 534 fn rand_data(len: usize) -> Vec<(u32, u32)> {
 535     let mut rng = DeterministicRng::new();
 536     Vec::from_iter((0..len).map(|_| (rng.next(), rng.next())))
 537 }
 538
 539 #[test]
 540 fn test_split_off_empty_right() {
 541     let mut data = rand_data(173);
 542
 543     let mut map = BTreeMap::from_iter(data.clone());
 544     let right = map.split_off(&(data.iter().max().unwrap().0 + 1));
 545
 546     data.sort();
 547     assert!(map.into_iter().eq(data));
 548     assert!(right.into_iter().eq(None));
 549 }
 550
 551 #[test]
 552 fn test_split_off_empty_left() {
 553     let mut data = rand_data(314);
 554
 555     let mut map = BTreeMap::from_iter(data.clone());
 556     let right = map.split_off(&data.iter().min().unwrap().0);
 557
 558     data.sort();
 559     assert!(map.into_iter().eq(None));
 560     assert!(right.into_iter().eq(data));
 561 }
 562
 563 #[test]
 564 fn test_split_off_large_random_sorted() {
 565     let mut data = rand_data(1529);
 566     // special case with maximum height.
 567     data.sort();
 568
 569     let mut map = BTreeMap::from_iter(data.clone());
 570     let key = data[data.len() / 2].0;
 571     let right = map.split_off(&key);
 572
 573     assert!(map.into_iter().eq(data.clone().into_iter().filter(|x| x.0 < key)));
 574     assert!(right.into_iter().eq(data.into_iter().filter(|x| x.0 >= key)));
 575 }
 576
 577 mod bench {
 578     use std::collections::BTreeMap;
 579     use std::__rand::{Rng, thread_rng};
 580
 581     use test::{Bencher, black_box};
 582
 583     map_insert_rand_bench!{insert_rand_100,    100,    BTreeMap}
 584     map_insert_rand_bench!{insert_rand_10_000, 10_000, BTreeMap}
 585
 586     map_insert_seq_bench!{insert_seq_100,    100,    BTreeMap}
 587     map_insert_seq_bench!{insert_seq_10_000, 10_000, BTreeMap}
 588
 589     map_find_rand_bench!{find_rand_100,    100,    BTreeMap}
 590     map_find_rand_bench!{find_rand_10_000, 10_000, BTreeMap}
 591
 592     map_find_seq_bench!{find_seq_100,    100,    BTreeMap}
 593     map_find_seq_bench!{find_seq_10_000, 10_000, BTreeMap}
 594
 595     fn bench_iter(b: &mut Bencher, size: i32) {
 596         let mut map = BTreeMap::<i32, i32>::new();
 597         let mut rng = thread_rng();
 598
 599         for _ in 0..size {
 600             map.insert(rng.gen(), rng.gen());
 601         }
 602
 603         b.iter(|| {
 604             for entry in &map {
 605                 black_box(entry);
 606             }
 607         });
 608     }
 609
 610     #[bench]
 611     pub fn iter_20(b: &mut Bencher) {
 612         bench_iter(b, 20);
 613     }
 614
 615     #[bench]
 616     pub fn iter_1000(b: &mut Bencher) {
 617         bench_iter(b, 1000);
 618     }
 619
 620     #[bench]
 621     pub fn iter_100000(b: &mut Bencher) {
 622         bench_iter(b, 100000);
 623     }
 624 }