1 use std::collections::btree_map::Entry::{Occupied, Vacant};
2 use std::collections::BTreeMap;
3 use std::convert::TryFrom;
5 use std::iter::FromIterator;
7 use std::ops::Bound::{self, Excluded, Included, Unbounded};
8 use std::ops::RangeBounds;
9 use std::panic::{catch_unwind, AssertUnwindSafe};
11 use std::sync::atomic::{AtomicUsize, Ordering};
13 use super::DeterministicRng;
15 // Value of node::CAPACITY, thus capacity of a tree with a single level,
16 // i.e. a tree who's root is a leaf node at height 0.
17 const NODE_CAPACITY: usize = 11;
19 // Minimum number of elements to insert in order to guarantee a tree with 2 levels,
20 // i.e. a tree who's root is an internal node at height 1, with edges to leaf nodes.
21 // It's not the minimum size: removing an element from such a tree does not always reduce height.
22 const MIN_INSERTS_HEIGHT_1: usize = NODE_CAPACITY + 1;
24 // Minimum number of elements to insert in order to guarantee a tree with 3 levels,
25 // i.e. a tree who's root is an internal node at height 2, with edges to more internal nodes.
26 // It's not the minimum size: removing an element from such a tree does not always reduce height.
27 const MIN_INSERTS_HEIGHT_2: usize = NODE_CAPACITY + (NODE_CAPACITY + 1) * NODE_CAPACITY + 1;
29 // Gather all references from a mutable iterator and make sure Miri notices if
30 // using them is dangerous.
31 fn test_all_refs<'a, T: 'a>(dummy: &mut T, iter: impl Iterator<Item = &'a mut T>) {
32 // Gather all those references.
33 let mut refs: Vec<&mut T> = iter.collect();
34 // Use them all. Twice, to be sure we got all interleavings.
35 for r in refs.iter_mut() {
44 fn test_basic_large() {
45 let mut map = BTreeMap::new();
47 let size = if cfg!(miri) { MIN_INSERTS_HEIGHT_2 } else { 10000 };
48 assert_eq!(map.len(), 0);
51 assert_eq!(map.insert(i, 10 * i), None);
52 assert_eq!(map.len(), i + 1);
55 assert_eq!(map.first_key_value(), Some((&0, &0)));
56 assert_eq!(map.last_key_value(), Some((&(size - 1), &(10 * (size - 1)))));
57 assert_eq!(map.first_entry().unwrap().key(), &0);
58 assert_eq!(map.last_entry().unwrap().key(), &(size - 1));
61 assert_eq!(map.get(&i).unwrap(), &(i * 10));
64 for i in size..size * 2 {
65 assert_eq!(map.get(&i), None);
69 assert_eq!(map.insert(i, 100 * i), Some(10 * i));
70 assert_eq!(map.len(), size);
74 assert_eq!(map.get(&i).unwrap(), &(i * 100));
77 for i in 0..size / 2 {
78 assert_eq!(map.remove(&(i * 2)), Some(i * 200));
79 assert_eq!(map.len(), size - i - 1);
82 for i in 0..size / 2 {
83 assert_eq!(map.get(&(2 * i)), None);
84 assert_eq!(map.get(&(2 * i + 1)).unwrap(), &(i * 200 + 100));
87 for i in 0..size / 2 {
88 assert_eq!(map.remove(&(2 * i)), None);
89 assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
90 assert_eq!(map.len(), size / 2 - i - 1);
95 fn test_basic_small() {
96 let mut map = BTreeMap::new();
97 // Empty, root is absent (None):
98 assert_eq!(map.remove(&1), None);
99 assert_eq!(map.len(), 0);
100 assert_eq!(map.get(&1), None);
101 assert_eq!(map.get_mut(&1), None);
102 assert_eq!(map.first_key_value(), None);
103 assert_eq!(map.last_key_value(), None);
104 assert_eq!(map.keys().count(), 0);
105 assert_eq!(map.values().count(), 0);
106 assert_eq!(map.range(..).next(), None);
107 assert_eq!(map.range(..1).next(), None);
108 assert_eq!(map.range(1..).next(), None);
109 assert_eq!(map.range(1..=1).next(), None);
110 assert_eq!(map.range(1..2).next(), None);
111 assert_eq!(map.insert(1, 1), None);
114 assert_eq!(map.len(), 1);
115 assert_eq!(map.get(&1), Some(&1));
116 assert_eq!(map.get_mut(&1), Some(&mut 1));
117 assert_eq!(map.first_key_value(), Some((&1, &1)));
118 assert_eq!(map.last_key_value(), Some((&1, &1)));
119 assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1]);
120 assert_eq!(map.values().collect::<Vec<_>>(), vec![&1]);
121 assert_eq!(map.insert(1, 2), Some(1));
122 assert_eq!(map.len(), 1);
123 assert_eq!(map.get(&1), Some(&2));
124 assert_eq!(map.get_mut(&1), Some(&mut 2));
125 assert_eq!(map.first_key_value(), Some((&1, &2)));
126 assert_eq!(map.last_key_value(), Some((&1, &2)));
127 assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1]);
128 assert_eq!(map.values().collect::<Vec<_>>(), vec![&2]);
129 assert_eq!(map.insert(2, 4), None);
131 // 2 key-value pairs:
132 assert_eq!(map.len(), 2);
133 assert_eq!(map.get(&2), Some(&4));
134 assert_eq!(map.get_mut(&2), Some(&mut 4));
135 assert_eq!(map.first_key_value(), Some((&1, &2)));
136 assert_eq!(map.last_key_value(), Some((&2, &4)));
137 assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1, &2]);
138 assert_eq!(map.values().collect::<Vec<_>>(), vec![&2, &4]);
139 assert_eq!(map.remove(&1), Some(2));
142 assert_eq!(map.len(), 1);
143 assert_eq!(map.get(&1), None);
144 assert_eq!(map.get_mut(&1), None);
145 assert_eq!(map.get(&2), Some(&4));
146 assert_eq!(map.get_mut(&2), Some(&mut 4));
147 assert_eq!(map.first_key_value(), Some((&2, &4)));
148 assert_eq!(map.last_key_value(), Some((&2, &4)));
149 assert_eq!(map.keys().collect::<Vec<_>>(), vec![&2]);
150 assert_eq!(map.values().collect::<Vec<_>>(), vec![&4]);
151 assert_eq!(map.remove(&2), Some(4));
153 // Empty but root is owned (Some(...)):
154 assert_eq!(map.len(), 0);
155 assert_eq!(map.get(&1), None);
156 assert_eq!(map.get_mut(&1), None);
157 assert_eq!(map.first_key_value(), None);
158 assert_eq!(map.last_key_value(), None);
159 assert_eq!(map.keys().count(), 0);
160 assert_eq!(map.values().count(), 0);
161 assert_eq!(map.range(..).next(), None);
162 assert_eq!(map.range(..1).next(), None);
163 assert_eq!(map.range(1..).next(), None);
164 assert_eq!(map.range(1..=1).next(), None);
165 assert_eq!(map.range(1..2).next(), None);
166 assert_eq!(map.remove(&1), None);
172 let size = if cfg!(miri) { 200 } else { 10000 };
174 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
176 fn test<T>(size: usize, mut iter: T)
178 T: Iterator<Item = (usize, usize)>,
181 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
182 assert_eq!(iter.next().unwrap(), (i, i));
184 assert_eq!(iter.size_hint(), (0, Some(0)));
185 assert_eq!(iter.next(), None);
187 test(size, map.iter().map(|(&k, &v)| (k, v)));
188 test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
189 test(size, map.into_iter());
195 let size = if cfg!(miri) { 200 } else { 10000 };
197 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
199 fn test<T>(size: usize, mut iter: T)
201 T: Iterator<Item = (usize, usize)>,
204 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
205 assert_eq!(iter.next().unwrap(), (size - i - 1, size - i - 1));
207 assert_eq!(iter.size_hint(), (0, Some(0)));
208 assert_eq!(iter.next(), None);
210 test(size, map.iter().rev().map(|(&k, &v)| (k, v)));
211 test(size, map.iter_mut().rev().map(|(&k, &mut v)| (k, v)));
212 test(size, map.into_iter().rev());
215 /// Specifically tests iter_mut's ability to mutate the value of pairs in-line
216 fn do_test_iter_mut_mutation<T>(size: usize)
218 T: Copy + Debug + Ord + TryFrom<usize>,
219 <T as std::convert::TryFrom<usize>>::Error: std::fmt::Debug,
221 let zero = T::try_from(0).unwrap();
222 let mut map: BTreeMap<T, T> = (0..size).map(|i| (T::try_from(i).unwrap(), zero)).collect();
224 // Forward and backward iteration sees enough pairs (also tested elsewhere)
225 assert_eq!(map.iter_mut().count(), size);
226 assert_eq!(map.iter_mut().rev().count(), size);
228 // Iterate forwards, trying to mutate to unique values
229 for (i, (k, v)) in map.iter_mut().enumerate() {
230 assert_eq!(*k, T::try_from(i).unwrap());
231 assert_eq!(*v, zero);
232 *v = T::try_from(i + 1).unwrap();
235 // Iterate backwards, checking that mutations succeeded and trying to mutate again
236 for (i, (k, v)) in map.iter_mut().rev().enumerate() {
237 assert_eq!(*k, T::try_from(size - i - 1).unwrap());
238 assert_eq!(*v, T::try_from(size - i).unwrap());
239 *v = T::try_from(2 * size - i).unwrap();
242 // Check that backward mutations succeeded
243 for (i, (k, v)) in map.iter_mut().enumerate() {
244 assert_eq!(*k, T::try_from(i).unwrap());
245 assert_eq!(*v, T::try_from(size + i + 1).unwrap());
249 #[derive(Clone, Copy, Debug, Eq, PartialEq, PartialOrd, Ord)]
251 struct Align32(usize);
253 impl TryFrom<usize> for Align32 {
256 fn try_from(s: usize) -> Result<Align32, ()> {
262 fn test_iter_mut_mutation() {
263 // Check many alignments and trees with roots at various heights.
264 do_test_iter_mut_mutation::<u8>(0);
265 do_test_iter_mut_mutation::<u8>(1);
266 do_test_iter_mut_mutation::<u8>(MIN_INSERTS_HEIGHT_1);
267 do_test_iter_mut_mutation::<u8>(127); // not enough unique values to test MIN_INSERTS_HEIGHT_2
268 do_test_iter_mut_mutation::<u16>(1);
269 do_test_iter_mut_mutation::<u16>(MIN_INSERTS_HEIGHT_1);
270 do_test_iter_mut_mutation::<u16>(MIN_INSERTS_HEIGHT_2);
271 do_test_iter_mut_mutation::<u32>(1);
272 do_test_iter_mut_mutation::<u32>(MIN_INSERTS_HEIGHT_1);
273 do_test_iter_mut_mutation::<u32>(MIN_INSERTS_HEIGHT_2);
274 do_test_iter_mut_mutation::<u64>(1);
275 do_test_iter_mut_mutation::<u64>(MIN_INSERTS_HEIGHT_1);
276 do_test_iter_mut_mutation::<u64>(MIN_INSERTS_HEIGHT_2);
277 do_test_iter_mut_mutation::<u128>(1);
278 do_test_iter_mut_mutation::<u128>(MIN_INSERTS_HEIGHT_1);
279 do_test_iter_mut_mutation::<u128>(MIN_INSERTS_HEIGHT_2);
280 do_test_iter_mut_mutation::<Align32>(1);
281 do_test_iter_mut_mutation::<Align32>(MIN_INSERTS_HEIGHT_1);
282 do_test_iter_mut_mutation::<Align32>(MIN_INSERTS_HEIGHT_2);
286 #[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915>
287 fn test_values_mut() {
288 let mut a: BTreeMap<_, _> = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)).collect();
289 test_all_refs(&mut 13, a.values_mut());
293 fn test_values_mut_mutation() {
294 let mut a = BTreeMap::new();
295 a.insert(1, String::from("hello"));
296 a.insert(2, String::from("goodbye"));
298 for value in a.values_mut() {
302 let values: Vec<String> = a.values().cloned().collect();
303 assert_eq!(values, [String::from("hello!"), String::from("goodbye!")]);
307 #[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915>
308 fn test_iter_entering_root_twice() {
309 let mut map: BTreeMap<_, _> = (0..2).map(|i| (i, i)).collect();
310 let mut it = map.iter_mut();
311 let front = it.next().unwrap();
312 let back = it.next_back().unwrap();
313 assert_eq!(front, (&0, &mut 0));
314 assert_eq!(back, (&1, &mut 1));
317 assert_eq!(front, (&0, &mut 24));
318 assert_eq!(back, (&1, &mut 42));
322 #[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915>
323 fn test_iter_descending_to_same_node_twice() {
324 let mut map: BTreeMap<_, _> = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i)).collect();
325 let mut it = map.iter_mut();
326 // Descend into first child.
327 let front = it.next().unwrap();
328 // Descend into first child again, after running through second child.
329 while it.next_back().is_some() {}
330 // Check immutable access.
331 assert_eq!(front, (&0, &mut 0));
332 // Perform mutable access.
337 fn test_iter_mixed() {
339 let size = if cfg!(miri) { 200 } else { 10000 };
341 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
343 fn test<T>(size: usize, mut iter: T)
345 T: Iterator<Item = (usize, usize)> + DoubleEndedIterator,
347 for i in 0..size / 4 {
348 assert_eq!(iter.size_hint(), (size - i * 2, Some(size - i * 2)));
349 assert_eq!(iter.next().unwrap(), (i, i));
350 assert_eq!(iter.next_back().unwrap(), (size - i - 1, size - i - 1));
352 for i in size / 4..size * 3 / 4 {
353 assert_eq!(iter.size_hint(), (size * 3 / 4 - i, Some(size * 3 / 4 - i)));
354 assert_eq!(iter.next().unwrap(), (i, i));
356 assert_eq!(iter.size_hint(), (0, Some(0)));
357 assert_eq!(iter.next(), None);
359 test(size, map.iter().map(|(&k, &v)| (k, v)));
360 test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
361 test(size, map.into_iter());
365 #[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915>
366 fn test_iter_min_max() {
367 let mut a = BTreeMap::new();
368 assert_eq!(a.iter().min(), None);
369 assert_eq!(a.iter().max(), None);
370 assert_eq!(a.iter_mut().min(), None);
371 assert_eq!(a.iter_mut().max(), None);
372 assert_eq!(a.range(..).min(), None);
373 assert_eq!(a.range(..).max(), None);
374 assert_eq!(a.range_mut(..).min(), None);
375 assert_eq!(a.range_mut(..).max(), None);
376 assert_eq!(a.keys().min(), None);
377 assert_eq!(a.keys().max(), None);
378 assert_eq!(a.values().min(), None);
379 assert_eq!(a.values().max(), None);
380 assert_eq!(a.values_mut().min(), None);
381 assert_eq!(a.values_mut().max(), None);
384 assert_eq!(a.iter().min(), Some((&1, &42)));
385 assert_eq!(a.iter().max(), Some((&2, &24)));
386 assert_eq!(a.iter_mut().min(), Some((&1, &mut 42)));
387 assert_eq!(a.iter_mut().max(), Some((&2, &mut 24)));
388 assert_eq!(a.range(..).min(), Some((&1, &42)));
389 assert_eq!(a.range(..).max(), Some((&2, &24)));
390 assert_eq!(a.range_mut(..).min(), Some((&1, &mut 42)));
391 assert_eq!(a.range_mut(..).max(), Some((&2, &mut 24)));
392 assert_eq!(a.keys().min(), Some(&1));
393 assert_eq!(a.keys().max(), Some(&2));
394 assert_eq!(a.values().min(), Some(&24));
395 assert_eq!(a.values().max(), Some(&42));
396 assert_eq!(a.values_mut().min(), Some(&mut 24));
397 assert_eq!(a.values_mut().max(), Some(&mut 42));
400 fn range_keys(map: &BTreeMap<i32, i32>, range: impl RangeBounds<i32>) -> Vec<i32> {
410 fn test_range_small() {
413 let map: BTreeMap<_, _> = (1..=size).map(|i| (i, i)).collect();
414 let all: Vec<_> = (1..=size).collect();
415 let (first, last) = (vec![all[0]], vec![all[size as usize - 1]]);
417 assert_eq!(range_keys(&map, (Excluded(0), Excluded(size + 1))), all);
418 assert_eq!(range_keys(&map, (Excluded(0), Included(size + 1))), all);
419 assert_eq!(range_keys(&map, (Excluded(0), Included(size))), all);
420 assert_eq!(range_keys(&map, (Excluded(0), Unbounded)), all);
421 assert_eq!(range_keys(&map, (Included(0), Excluded(size + 1))), all);
422 assert_eq!(range_keys(&map, (Included(0), Included(size + 1))), all);
423 assert_eq!(range_keys(&map, (Included(0), Included(size))), all);
424 assert_eq!(range_keys(&map, (Included(0), Unbounded)), all);
425 assert_eq!(range_keys(&map, (Included(1), Excluded(size + 1))), all);
426 assert_eq!(range_keys(&map, (Included(1), Included(size + 1))), all);
427 assert_eq!(range_keys(&map, (Included(1), Included(size))), all);
428 assert_eq!(range_keys(&map, (Included(1), Unbounded)), all);
429 assert_eq!(range_keys(&map, (Unbounded, Excluded(size + 1))), all);
430 assert_eq!(range_keys(&map, (Unbounded, Included(size + 1))), all);
431 assert_eq!(range_keys(&map, (Unbounded, Included(size))), all);
432 assert_eq!(range_keys(&map, ..), all);
434 assert_eq!(range_keys(&map, (Excluded(0), Excluded(1))), vec![]);
435 assert_eq!(range_keys(&map, (Excluded(0), Included(0))), vec![]);
436 assert_eq!(range_keys(&map, (Included(0), Included(0))), vec![]);
437 assert_eq!(range_keys(&map, (Included(0), Excluded(1))), vec![]);
438 assert_eq!(range_keys(&map, (Unbounded, Excluded(1))), vec![]);
439 assert_eq!(range_keys(&map, (Unbounded, Included(0))), vec![]);
440 assert_eq!(range_keys(&map, (Excluded(0), Excluded(2))), first);
441 assert_eq!(range_keys(&map, (Excluded(0), Included(1))), first);
442 assert_eq!(range_keys(&map, (Included(0), Excluded(2))), first);
443 assert_eq!(range_keys(&map, (Included(0), Included(1))), first);
444 assert_eq!(range_keys(&map, (Included(1), Excluded(2))), first);
445 assert_eq!(range_keys(&map, (Included(1), Included(1))), first);
446 assert_eq!(range_keys(&map, (Unbounded, Excluded(2))), first);
447 assert_eq!(range_keys(&map, (Unbounded, Included(1))), first);
448 assert_eq!(range_keys(&map, (Excluded(size - 1), Excluded(size + 1))), last);
449 assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size + 1))), last);
450 assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size))), last);
451 assert_eq!(range_keys(&map, (Excluded(size - 1), Unbounded)), last);
452 assert_eq!(range_keys(&map, (Included(size), Excluded(size + 1))), last);
453 assert_eq!(range_keys(&map, (Included(size), Included(size + 1))), last);
454 assert_eq!(range_keys(&map, (Included(size), Included(size))), last);
455 assert_eq!(range_keys(&map, (Included(size), Unbounded)), last);
456 assert_eq!(range_keys(&map, (Excluded(size), Excluded(size + 1))), vec![]);
457 assert_eq!(range_keys(&map, (Excluded(size), Included(size))), vec![]);
458 assert_eq!(range_keys(&map, (Excluded(size), Unbounded)), vec![]);
459 assert_eq!(range_keys(&map, (Included(size + 1), Excluded(size + 1))), vec![]);
460 assert_eq!(range_keys(&map, (Included(size + 1), Included(size + 1))), vec![]);
461 assert_eq!(range_keys(&map, (Included(size + 1), Unbounded)), vec![]);
463 assert_eq!(range_keys(&map, ..3), vec![1, 2]);
464 assert_eq!(range_keys(&map, 3..), vec![3, 4]);
465 assert_eq!(range_keys(&map, 2..=3), vec![2, 3]);
469 fn test_range_height_1() {
470 // Tests tree with a root and 2 leaves. Depending on details we don't want or need
471 // to rely upon, the single key at the root will be 6 or 7.
473 let map: BTreeMap<_, _> = (1..=MIN_INSERTS_HEIGHT_1 as i32).map(|i| (i, i)).collect();
474 for &root in &[6, 7] {
475 assert_eq!(range_keys(&map, (Excluded(root), Excluded(root + 1))), vec![]);
476 assert_eq!(range_keys(&map, (Excluded(root), Included(root + 1))), vec![root + 1]);
477 assert_eq!(range_keys(&map, (Included(root), Excluded(root + 1))), vec![root]);
478 assert_eq!(range_keys(&map, (Included(root), Included(root + 1))), vec![root, root + 1]);
480 assert_eq!(range_keys(&map, (Excluded(root - 1), Excluded(root))), vec![]);
481 assert_eq!(range_keys(&map, (Included(root - 1), Excluded(root))), vec![root - 1]);
482 assert_eq!(range_keys(&map, (Excluded(root - 1), Included(root))), vec![root]);
483 assert_eq!(range_keys(&map, (Included(root - 1), Included(root))), vec![root - 1, root]);
488 fn test_range_large() {
491 let map: BTreeMap<_, _> = (1..=size).map(|i| (i, i)).collect();
492 let all: Vec<_> = (1..=size).collect();
493 let (first, last) = (vec![all[0]], vec![all[size as usize - 1]]);
495 assert_eq!(range_keys(&map, (Excluded(0), Excluded(size + 1))), all);
496 assert_eq!(range_keys(&map, (Excluded(0), Included(size + 1))), all);
497 assert_eq!(range_keys(&map, (Excluded(0), Included(size))), all);
498 assert_eq!(range_keys(&map, (Excluded(0), Unbounded)), all);
499 assert_eq!(range_keys(&map, (Included(0), Excluded(size + 1))), all);
500 assert_eq!(range_keys(&map, (Included(0), Included(size + 1))), all);
501 assert_eq!(range_keys(&map, (Included(0), Included(size))), all);
502 assert_eq!(range_keys(&map, (Included(0), Unbounded)), all);
503 assert_eq!(range_keys(&map, (Included(1), Excluded(size + 1))), all);
504 assert_eq!(range_keys(&map, (Included(1), Included(size + 1))), all);
505 assert_eq!(range_keys(&map, (Included(1), Included(size))), all);
506 assert_eq!(range_keys(&map, (Included(1), Unbounded)), all);
507 assert_eq!(range_keys(&map, (Unbounded, Excluded(size + 1))), all);
508 assert_eq!(range_keys(&map, (Unbounded, Included(size + 1))), all);
509 assert_eq!(range_keys(&map, (Unbounded, Included(size))), all);
510 assert_eq!(range_keys(&map, ..), all);
512 assert_eq!(range_keys(&map, (Excluded(0), Excluded(1))), vec![]);
513 assert_eq!(range_keys(&map, (Excluded(0), Included(0))), vec![]);
514 assert_eq!(range_keys(&map, (Included(0), Included(0))), vec![]);
515 assert_eq!(range_keys(&map, (Included(0), Excluded(1))), vec![]);
516 assert_eq!(range_keys(&map, (Unbounded, Excluded(1))), vec![]);
517 assert_eq!(range_keys(&map, (Unbounded, Included(0))), vec![]);
518 assert_eq!(range_keys(&map, (Excluded(0), Excluded(2))), first);
519 assert_eq!(range_keys(&map, (Excluded(0), Included(1))), first);
520 assert_eq!(range_keys(&map, (Included(0), Excluded(2))), first);
521 assert_eq!(range_keys(&map, (Included(0), Included(1))), first);
522 assert_eq!(range_keys(&map, (Included(1), Excluded(2))), first);
523 assert_eq!(range_keys(&map, (Included(1), Included(1))), first);
524 assert_eq!(range_keys(&map, (Unbounded, Excluded(2))), first);
525 assert_eq!(range_keys(&map, (Unbounded, Included(1))), first);
526 assert_eq!(range_keys(&map, (Excluded(size - 1), Excluded(size + 1))), last);
527 assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size + 1))), last);
528 assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size))), last);
529 assert_eq!(range_keys(&map, (Excluded(size - 1), Unbounded)), last);
530 assert_eq!(range_keys(&map, (Included(size), Excluded(size + 1))), last);
531 assert_eq!(range_keys(&map, (Included(size), Included(size + 1))), last);
532 assert_eq!(range_keys(&map, (Included(size), Included(size))), last);
533 assert_eq!(range_keys(&map, (Included(size), Unbounded)), last);
534 assert_eq!(range_keys(&map, (Excluded(size), Excluded(size + 1))), vec![]);
535 assert_eq!(range_keys(&map, (Excluded(size), Included(size))), vec![]);
536 assert_eq!(range_keys(&map, (Excluded(size), Unbounded)), vec![]);
537 assert_eq!(range_keys(&map, (Included(size + 1), Excluded(size + 1))), vec![]);
538 assert_eq!(range_keys(&map, (Included(size + 1), Included(size + 1))), vec![]);
539 assert_eq!(range_keys(&map, (Included(size + 1), Unbounded)), vec![]);
541 fn check<'a, L, R>(lhs: L, rhs: R)
543 L: IntoIterator<Item = (&'a i32, &'a i32)>,
544 R: IntoIterator<Item = (&'a i32, &'a i32)>,
546 let lhs: Vec<_> = lhs.into_iter().collect();
547 let rhs: Vec<_> = rhs.into_iter().collect();
548 assert_eq!(lhs, rhs);
551 check(map.range(..=100), map.range(..101));
552 check(map.range(5..=8), vec![(&5, &5), (&6, &6), (&7, &7), (&8, &8)]);
553 check(map.range(-1..=2), vec![(&1, &1), (&2, &2)]);
557 fn test_range_inclusive_max_value() {
558 let max = usize::MAX;
559 let map: BTreeMap<_, _> = vec![(max, 0)].into_iter().collect();
561 assert_eq!(map.range(max..=max).collect::<Vec<_>>(), &[(&max, &0)]);
565 fn test_range_equal_empty_cases() {
566 let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
567 assert_eq!(map.range((Included(2), Excluded(2))).next(), None);
568 assert_eq!(map.range((Excluded(2), Included(2))).next(), None);
573 fn test_range_equal_excluded() {
574 let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
575 map.range((Excluded(2), Excluded(2)));
580 fn test_range_backwards_1() {
581 let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
582 map.range((Included(3), Included(2)));
587 fn test_range_backwards_2() {
588 let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
589 map.range((Included(3), Excluded(2)));
594 fn test_range_backwards_3() {
595 let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
596 map.range((Excluded(3), Included(2)));
601 fn test_range_backwards_4() {
602 let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
603 map.range((Excluded(3), Excluded(2)));
607 fn test_range_1000() {
609 let size = if cfg!(miri) { MIN_INSERTS_HEIGHT_2 as u32 } else { 1000 };
610 let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
612 fn test(map: &BTreeMap<u32, u32>, size: u32, min: Bound<&u32>, max: Bound<&u32>) {
613 let mut kvs = map.range((min, max)).map(|(&k, &v)| (k, v));
614 let mut pairs = (0..size).map(|i| (i, i));
616 for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
617 assert_eq!(kv, pair);
619 assert_eq!(kvs.next(), None);
620 assert_eq!(pairs.next(), None);
622 test(&map, size, Included(&0), Excluded(&size));
623 test(&map, size, Unbounded, Excluded(&size));
624 test(&map, size, Included(&0), Included(&(size - 1)));
625 test(&map, size, Unbounded, Included(&(size - 1)));
626 test(&map, size, Included(&0), Unbounded);
627 test(&map, size, Unbounded, Unbounded);
631 fn test_range_borrowed_key() {
632 let mut map = BTreeMap::new();
633 map.insert("aardvark".to_string(), 1);
634 map.insert("baboon".to_string(), 2);
635 map.insert("coyote".to_string(), 3);
636 map.insert("dingo".to_string(), 4);
637 // NOTE: would like to use simply "b".."d" here...
638 let mut iter = map.range::<str, _>((Included("b"), Excluded("d")));
639 assert_eq!(iter.next(), Some((&"baboon".to_string(), &2)));
640 assert_eq!(iter.next(), Some((&"coyote".to_string(), &3)));
641 assert_eq!(iter.next(), None);
648 let step = if cfg!(miri) { 66 } else { 1 };
649 let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
651 for i in (0..size).step_by(step) {
652 for j in (i..size).step_by(step) {
653 let mut kvs = map.range((Included(&i), Included(&j))).map(|(&k, &v)| (k, v));
654 let mut pairs = (i..=j).map(|i| (i, i));
656 for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
657 assert_eq!(kv, pair);
659 assert_eq!(kvs.next(), None);
660 assert_eq!(pairs.next(), None);
666 fn test_range_mut() {
669 let step = if cfg!(miri) { 66 } else { 1 };
670 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
672 for i in (0..size).step_by(step) {
673 for j in (i..size).step_by(step) {
674 let mut kvs = map.range_mut((Included(&i), Included(&j))).map(|(&k, &mut v)| (k, v));
675 let mut pairs = (i..=j).map(|i| (i, i));
677 for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
678 assert_eq!(kv, pair);
680 assert_eq!(kvs.next(), None);
681 assert_eq!(pairs.next(), None);
686 mod test_drain_filter {
691 let mut map: BTreeMap<i32, i32> = BTreeMap::new();
692 map.drain_filter(|_, _| unreachable!("there's nothing to decide on"));
693 assert!(map.is_empty());
697 fn consuming_nothing() {
698 let pairs = (0..3).map(|i| (i, i));
699 let mut map: BTreeMap<_, _> = pairs.collect();
700 assert!(map.drain_filter(|_, _| false).eq(std::iter::empty()));
705 let pairs = (0..3).map(|i| (i, i));
706 let mut map: BTreeMap<_, _> = pairs.clone().collect();
707 assert!(map.drain_filter(|_, _| true).eq(pairs));
711 fn mutating_and_keeping() {
712 let pairs = (0..3).map(|i| (i, i));
713 let mut map: BTreeMap<_, _> = pairs.collect();
715 map.drain_filter(|_, v| {
719 .eq(std::iter::empty())
721 assert!(map.keys().copied().eq(0..3));
722 assert!(map.values().copied().eq(6..9));
726 fn mutating_and_removing() {
727 let pairs = (0..3).map(|i| (i, i));
728 let mut map: BTreeMap<_, _> = pairs.collect();
730 map.drain_filter(|_, v| {
734 .eq((0..3).map(|i| (i, i + 6)))
736 assert!(map.is_empty());
740 fn underfull_keeping_all() {
741 let pairs = (0..3).map(|i| (i, i));
742 let mut map: BTreeMap<_, _> = pairs.collect();
743 map.drain_filter(|_, _| false);
744 assert!(map.keys().copied().eq(0..3));
748 fn underfull_removing_one() {
749 let pairs = (0..3).map(|i| (i, i));
751 let mut map: BTreeMap<_, _> = pairs.clone().collect();
752 map.drain_filter(|i, _| *i == doomed);
753 assert_eq!(map.len(), 2);
758 fn underfull_keeping_one() {
759 let pairs = (0..3).map(|i| (i, i));
761 let mut map: BTreeMap<_, _> = pairs.clone().collect();
762 map.drain_filter(|i, _| *i != sacred);
763 assert!(map.keys().copied().eq(sacred..=sacred));
768 fn underfull_removing_all() {
769 let pairs = (0..3).map(|i| (i, i));
770 let mut map: BTreeMap<_, _> = pairs.collect();
771 map.drain_filter(|_, _| true);
772 assert!(map.is_empty());
776 fn height_0_keeping_all() {
777 let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
778 let mut map: BTreeMap<_, _> = pairs.collect();
779 map.drain_filter(|_, _| false);
780 assert!(map.keys().copied().eq(0..NODE_CAPACITY));
784 fn height_0_removing_one() {
785 let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
786 for doomed in 0..NODE_CAPACITY {
787 let mut map: BTreeMap<_, _> = pairs.clone().collect();
788 map.drain_filter(|i, _| *i == doomed);
789 assert_eq!(map.len(), NODE_CAPACITY - 1);
794 fn height_0_keeping_one() {
795 let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
796 for sacred in 0..NODE_CAPACITY {
797 let mut map: BTreeMap<_, _> = pairs.clone().collect();
798 map.drain_filter(|i, _| *i != sacred);
799 assert!(map.keys().copied().eq(sacred..=sacred));
804 fn height_0_removing_all() {
805 let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
806 let mut map: BTreeMap<_, _> = pairs.collect();
807 map.drain_filter(|_, _| true);
808 assert!(map.is_empty());
812 fn height_0_keeping_half() {
813 let mut map: BTreeMap<_, _> = (0..16).map(|i| (i, i)).collect();
814 assert_eq!(map.drain_filter(|i, _| *i % 2 == 0).count(), 8);
815 assert_eq!(map.len(), 8);
819 fn height_1_removing_all() {
820 let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i));
821 let mut map: BTreeMap<_, _> = pairs.collect();
822 map.drain_filter(|_, _| true);
823 assert!(map.is_empty());
827 fn height_1_removing_one() {
828 let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i));
829 for doomed in 0..MIN_INSERTS_HEIGHT_1 {
830 let mut map: BTreeMap<_, _> = pairs.clone().collect();
831 map.drain_filter(|i, _| *i == doomed);
832 assert_eq!(map.len(), MIN_INSERTS_HEIGHT_1 - 1);
837 fn height_1_keeping_one() {
838 let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i));
839 for sacred in 0..MIN_INSERTS_HEIGHT_1 {
840 let mut map: BTreeMap<_, _> = pairs.clone().collect();
841 map.drain_filter(|i, _| *i != sacred);
842 assert!(map.keys().copied().eq(sacred..=sacred));
846 #[cfg(not(miri))] // Miri is too slow
848 fn height_2_removing_one() {
849 let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
850 for doomed in (0..MIN_INSERTS_HEIGHT_2).step_by(12) {
851 let mut map: BTreeMap<_, _> = pairs.clone().collect();
852 map.drain_filter(|i, _| *i == doomed);
853 assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2 - 1);
857 #[cfg(not(miri))] // Miri is too slow
859 fn height_2_keeping_one() {
860 let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
861 for sacred in (0..MIN_INSERTS_HEIGHT_2).step_by(12) {
862 let mut map: BTreeMap<_, _> = pairs.clone().collect();
863 map.drain_filter(|i, _| *i != sacred);
864 assert!(map.keys().copied().eq(sacred..=sacred));
869 fn height_2_removing_all() {
870 let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
871 let mut map: BTreeMap<_, _> = pairs.collect();
872 map.drain_filter(|_, _| true);
873 assert!(map.is_empty());
877 fn drop_panic_leak() {
878 static PREDS: AtomicUsize = AtomicUsize::new(0);
879 static DROPS: AtomicUsize = AtomicUsize::new(0);
884 if DROPS.fetch_add(1, Ordering::SeqCst) == 1 {
885 panic!("panic in `drop`");
890 // Keys are multiples of 4, so that each key is counted by a hexadecimal digit.
891 let mut map = (0..3).map(|i| (i * 4, D)).collect::<BTreeMap<_, _>>();
893 catch_unwind(move || {
894 drop(map.drain_filter(|i, _| {
895 PREDS.fetch_add(1usize << i, Ordering::SeqCst);
901 assert_eq!(PREDS.load(Ordering::SeqCst), 0x011);
902 assert_eq!(DROPS.load(Ordering::SeqCst), 3);
906 fn pred_panic_leak() {
907 static PREDS: AtomicUsize = AtomicUsize::new(0);
908 static DROPS: AtomicUsize = AtomicUsize::new(0);
913 DROPS.fetch_add(1, Ordering::SeqCst);
917 // Keys are multiples of 4, so that each key is counted by a hexadecimal digit.
918 let mut map = (0..3).map(|i| (i * 4, D)).collect::<BTreeMap<_, _>>();
920 catch_unwind(AssertUnwindSafe(|| {
921 drop(map.drain_filter(|i, _| {
922 PREDS.fetch_add(1usize << i, Ordering::SeqCst);
931 assert_eq!(PREDS.load(Ordering::SeqCst), 0x011);
932 assert_eq!(DROPS.load(Ordering::SeqCst), 1);
933 assert_eq!(map.len(), 2);
934 assert_eq!(map.first_entry().unwrap().key(), &4);
935 assert_eq!(map.last_entry().unwrap().key(), &8);
938 // Same as above, but attempt to use the iterator again after the panic in the predicate
940 fn pred_panic_reuse() {
941 static PREDS: AtomicUsize = AtomicUsize::new(0);
942 static DROPS: AtomicUsize = AtomicUsize::new(0);
947 DROPS.fetch_add(1, Ordering::SeqCst);
951 // Keys are multiples of 4, so that each key is counted by a hexadecimal digit.
952 let mut map = (0..3).map(|i| (i * 4, D)).collect::<BTreeMap<_, _>>();
955 let mut it = map.drain_filter(|i, _| {
956 PREDS.fetch_add(1usize << i, Ordering::SeqCst);
962 catch_unwind(AssertUnwindSafe(|| while it.next().is_some() {})).unwrap_err();
963 // Iterator behaviour after a panic is explicitly unspecified,
964 // so this is just the current implementation:
965 let result = catch_unwind(AssertUnwindSafe(|| it.next()));
966 assert!(matches!(result, Ok(None)));
969 assert_eq!(PREDS.load(Ordering::SeqCst), 0x011);
970 assert_eq!(DROPS.load(Ordering::SeqCst), 1);
971 assert_eq!(map.len(), 2);
972 assert_eq!(map.first_entry().unwrap().key(), &4);
973 assert_eq!(map.last_entry().unwrap().key(), &8);
979 // make sure these compile -- using the Borrow trait
981 let mut map = BTreeMap::new();
982 map.insert("0".to_string(), 1);
983 assert_eq!(map["0"], 1);
987 let mut map = BTreeMap::new();
988 map.insert(Box::new(0), 1);
989 assert_eq!(map[&0], 1);
993 let mut map = BTreeMap::new();
994 map.insert(Box::new([0, 1]) as Box<[i32]>, 1);
995 assert_eq!(map[&[0, 1][..]], 1);
999 let mut map = BTreeMap::new();
1000 map.insert(Rc::new(0), 1);
1001 assert_eq!(map[&0], 1);
1007 let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
1009 let mut map: BTreeMap<_, _> = xs.iter().cloned().collect();
1011 // Existing key (insert)
1012 match map.entry(1) {
1013 Vacant(_) => unreachable!(),
1014 Occupied(mut view) => {
1015 assert_eq!(view.get(), &10);
1016 assert_eq!(view.insert(100), 10);
1019 assert_eq!(map.get(&1).unwrap(), &100);
1020 assert_eq!(map.len(), 6);
1022 // Existing key (update)
1023 match map.entry(2) {
1024 Vacant(_) => unreachable!(),
1025 Occupied(mut view) => {
1026 let v = view.get_mut();
1030 assert_eq!(map.get(&2).unwrap(), &200);
1031 assert_eq!(map.len(), 6);
1033 // Existing key (take)
1034 match map.entry(3) {
1035 Vacant(_) => unreachable!(),
1037 assert_eq!(view.remove(), 30);
1040 assert_eq!(map.get(&3), None);
1041 assert_eq!(map.len(), 5);
1043 // Inexistent key (insert)
1044 match map.entry(10) {
1045 Occupied(_) => unreachable!(),
1047 assert_eq!(*view.insert(1000), 1000);
1050 assert_eq!(map.get(&10).unwrap(), &1000);
1051 assert_eq!(map.len(), 6);
1055 fn test_extend_ref() {
1056 let mut a = BTreeMap::new();
1058 let mut b = BTreeMap::new();
1060 b.insert(3, "three");
1064 assert_eq!(a.len(), 3);
1065 assert_eq!(a[&1], "one");
1066 assert_eq!(a[&2], "two");
1067 assert_eq!(a[&3], "three");
1072 let mut m = BTreeMap::new();
1073 assert_eq!(m.len(), 0);
1075 assert_eq!(m.insert((), ()), None);
1076 assert_eq!(m.len(), 1);
1078 assert_eq!(m.insert((), ()), Some(()));
1079 assert_eq!(m.len(), 1);
1080 assert_eq!(m.iter().count(), 1);
1083 assert_eq!(m.len(), 0);
1089 assert_eq!(m.len(), 1);
1090 assert_eq!(m.iter().count(), 1);
1093 // This test's only purpose is to ensure that zero-sized keys with nonsensical orderings
1094 // do not cause segfaults when used with zero-sized values. All other map behavior is
1098 use std::cmp::Ordering;
1102 impl PartialEq for Bad {
1103 fn eq(&self, _: &Self) -> bool {
1110 impl PartialOrd for Bad {
1111 fn partial_cmp(&self, _: &Self) -> Option<Ordering> {
1112 Some(Ordering::Less)
1117 fn cmp(&self, _: &Self) -> Ordering {
1122 let mut m = BTreeMap::new();
1131 let mut map = BTreeMap::new();
1132 let size = MIN_INSERTS_HEIGHT_1;
1133 assert_eq!(map.len(), 0);
1136 assert_eq!(map.insert(i, 10 * i), None);
1137 assert_eq!(map.len(), i + 1);
1138 assert_eq!(map, map.clone());
1142 assert_eq!(map.insert(i, 100 * i), Some(10 * i));
1143 assert_eq!(map.len(), size);
1144 assert_eq!(map, map.clone());
1147 for i in 0..size / 2 {
1148 assert_eq!(map.remove(&(i * 2)), Some(i * 200));
1149 assert_eq!(map.len(), size - i - 1);
1150 assert_eq!(map, map.clone());
1153 for i in 0..size / 2 {
1154 assert_eq!(map.remove(&(2 * i)), None);
1155 assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
1156 assert_eq!(map.len(), size / 2 - i - 1);
1157 assert_eq!(map, map.clone());
1160 // Test a tree with 2 chock-full levels and a tree with 3 levels.
1161 map = (1..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)).collect();
1162 assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2 - 1);
1163 assert_eq!(map, map.clone());
1165 assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2);
1166 assert_eq!(map, map.clone());
1170 fn test_clone_from() {
1171 let mut map1 = BTreeMap::new();
1172 let max_size = MIN_INSERTS_HEIGHT_1;
1174 // Range to max_size inclusive, because i is the size of map1 being tested.
1175 for i in 0..=max_size {
1176 let mut map2 = BTreeMap::new();
1178 let mut map1_copy = map2.clone();
1179 map1_copy.clone_from(&map1); // small cloned from large
1180 assert_eq!(map1_copy, map1);
1181 let mut map2_copy = map1.clone();
1182 map2_copy.clone_from(&map2); // large cloned from small
1183 assert_eq!(map2_copy, map2);
1184 map2.insert(100 * j + 1, 2 * j + 1);
1186 map2.clone_from(&map1); // same length
1187 assert_eq!(map2, map1);
1188 map1.insert(i, 10 * i);
1194 fn test_variance() {
1195 use std::collections::btree_map::{IntoIter, Iter, Keys, Range, Values};
1197 fn map_key<'new>(v: BTreeMap<&'static str, ()>) -> BTreeMap<&'new str, ()> {
1200 fn map_val<'new>(v: BTreeMap<(), &'static str>) -> BTreeMap<(), &'new str> {
1203 fn iter_key<'a, 'new>(v: Iter<'a, &'static str, ()>) -> Iter<'a, &'new str, ()> {
1206 fn iter_val<'a, 'new>(v: Iter<'a, (), &'static str>) -> Iter<'a, (), &'new str> {
1209 fn into_iter_key<'new>(v: IntoIter<&'static str, ()>) -> IntoIter<&'new str, ()> {
1212 fn into_iter_val<'new>(v: IntoIter<(), &'static str>) -> IntoIter<(), &'new str> {
1215 fn range_key<'a, 'new>(v: Range<'a, &'static str, ()>) -> Range<'a, &'new str, ()> {
1218 fn range_val<'a, 'new>(v: Range<'a, (), &'static str>) -> Range<'a, (), &'new str> {
1221 fn keys<'a, 'new>(v: Keys<'a, &'static str, ()>) -> Keys<'a, &'new str, ()> {
1224 fn vals<'a, 'new>(v: Values<'a, (), &'static str>) -> Values<'a, (), &'new str> {
1230 fn test_occupied_entry_key() {
1231 let mut a = BTreeMap::new();
1232 let key = "hello there";
1233 let value = "value goes here";
1234 assert!(a.is_empty());
1235 a.insert(key.clone(), value.clone());
1236 assert_eq!(a.len(), 1);
1237 assert_eq!(a[key], value);
1239 match a.entry(key.clone()) {
1240 Vacant(_) => panic!(),
1241 Occupied(e) => assert_eq!(key, *e.key()),
1243 assert_eq!(a.len(), 1);
1244 assert_eq!(a[key], value);
1248 fn test_vacant_entry_key() {
1249 let mut a = BTreeMap::new();
1250 let key = "hello there";
1251 let value = "value goes here";
1253 assert!(a.is_empty());
1254 match a.entry(key.clone()) {
1255 Occupied(_) => panic!(),
1257 assert_eq!(key, *e.key());
1258 e.insert(value.clone());
1261 assert_eq!(a.len(), 1);
1262 assert_eq!(a[key], value);
1266 fn test_first_last_entry() {
1267 let mut a = BTreeMap::new();
1268 assert!(a.first_entry().is_none());
1269 assert!(a.last_entry().is_none());
1271 assert_eq!(a.first_entry().unwrap().key(), &1);
1272 assert_eq!(a.last_entry().unwrap().key(), &1);
1274 assert_eq!(a.first_entry().unwrap().key(), &1);
1275 assert_eq!(a.last_entry().unwrap().key(), &2);
1277 assert_eq!(a.first_entry().unwrap().key(), &0);
1278 assert_eq!(a.last_entry().unwrap().key(), &2);
1279 let (k1, v1) = a.first_entry().unwrap().remove_entry();
1282 let (k2, v2) = a.last_entry().unwrap().remove_entry();
1285 assert_eq!(a.first_entry().unwrap().key(), &1);
1286 assert_eq!(a.last_entry().unwrap().key(), &1);
1289 macro_rules! create_append_test {
1290 ($name:ident, $len:expr) => {
1293 let mut a = BTreeMap::new();
1298 let mut b = BTreeMap::new();
1305 assert_eq!(a.len(), $len);
1306 assert_eq!(b.len(), 0);
1310 assert_eq!(a[&i], i);
1312 assert_eq!(a[&i], 2 * i);
1316 assert_eq!(a.remove(&($len - 1)), Some(2 * ($len - 1)));
1317 assert_eq!(a.insert($len - 1, 20), None);
1322 // These are mostly for testing the algorithm that "fixes" the right edge after insertion.
1324 create_append_test!(test_append_9, 9);
1325 // Two leafs that don't need fixing.
1326 create_append_test!(test_append_17, 17);
1327 // Two leafs where the second one ends up underfull and needs stealing at the end.
1328 create_append_test!(test_append_14, 14);
1329 // Two leafs where the second one ends up empty because the insertion finished at the root.
1330 create_append_test!(test_append_12, 12);
1331 // Three levels; insertion finished at the root.
1332 create_append_test!(test_append_144, 144);
1333 // Three levels; insertion finished at leaf while there is an empty node on the second level.
1334 create_append_test!(test_append_145, 145);
1335 // Tests for several randomly chosen sizes.
1336 create_append_test!(test_append_170, 170);
1337 create_append_test!(test_append_181, 181);
1338 #[cfg(not(miri))] // Miri is too slow
1339 create_append_test!(test_append_239, 239);
1340 #[cfg(not(miri))] // Miri is too slow
1341 create_append_test!(test_append_1700, 1700);
1343 fn rand_data(len: usize) -> Vec<(u32, u32)> {
1344 let mut rng = DeterministicRng::new();
1345 Vec::from_iter((0..len).map(|_| (rng.next(), rng.next())))
1349 fn test_split_off_empty_right() {
1350 let mut data = rand_data(173);
1352 let mut map = BTreeMap::from_iter(data.clone());
1353 let right = map.split_off(&(data.iter().max().unwrap().0 + 1));
1356 assert!(map.into_iter().eq(data));
1357 assert!(right.into_iter().eq(None));
1361 fn test_split_off_empty_left() {
1362 let mut data = rand_data(314);
1364 let mut map = BTreeMap::from_iter(data.clone());
1365 let right = map.split_off(&data.iter().min().unwrap().0);
1368 assert!(map.into_iter().eq(None));
1369 assert!(right.into_iter().eq(data));
1372 // In a tree with 3 levels, if all but a part of the first leaf node is split off,
1373 // make sure fix_top eliminates both top levels.
1375 fn test_split_off_tiny_left_height_2() {
1376 let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
1377 let mut left: BTreeMap<_, _> = pairs.clone().collect();
1378 let right = left.split_off(&1);
1379 assert_eq!(left.len(), 1);
1380 assert_eq!(right.len(), MIN_INSERTS_HEIGHT_2 - 1);
1381 assert_eq!(*left.first_key_value().unwrap().0, 0);
1382 assert_eq!(*right.first_key_value().unwrap().0, 1);
1385 // In a tree with 3 levels, if only part of the last leaf node is split off,
1386 // make sure fix_top eliminates both top levels.
1388 fn test_split_off_tiny_right_height_2() {
1389 let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
1390 let last = MIN_INSERTS_HEIGHT_2 - 1;
1391 let mut left: BTreeMap<_, _> = pairs.clone().collect();
1392 assert_eq!(*left.last_key_value().unwrap().0, last);
1393 let right = left.split_off(&last);
1394 assert_eq!(left.len(), MIN_INSERTS_HEIGHT_2 - 1);
1395 assert_eq!(right.len(), 1);
1396 assert_eq!(*left.last_key_value().unwrap().0, last - 1);
1397 assert_eq!(*right.last_key_value().unwrap().0, last);
1401 fn test_split_off_large_random_sorted() {
1403 let mut data = if cfg!(miri) { rand_data(529) } else { rand_data(1529) };
1404 // special case with maximum height.
1407 let mut map = BTreeMap::from_iter(data.clone());
1408 let key = data[data.len() / 2].0;
1409 let right = map.split_off(&key);
1411 assert!(map.into_iter().eq(data.clone().into_iter().filter(|x| x.0 < key)));
1412 assert!(right.into_iter().eq(data.into_iter().filter(|x| x.0 >= key)));
1416 fn test_into_iter_drop_leak_height_0() {
1417 static DROPS: AtomicUsize = AtomicUsize::new(0);
1422 fn drop(&mut self) {
1423 if DROPS.fetch_add(1, Ordering::SeqCst) == 3 {
1424 panic!("panic in `drop`");
1429 let mut map = BTreeMap::new();
1436 catch_unwind(move || drop(map.into_iter())).unwrap_err();
1438 assert_eq!(DROPS.load(Ordering::SeqCst), 5);
1442 fn test_into_iter_drop_leak_height_1() {
1443 let size = MIN_INSERTS_HEIGHT_1;
1444 static DROPS: AtomicUsize = AtomicUsize::new(0);
1445 static PANIC_POINT: AtomicUsize = AtomicUsize::new(0);
1449 fn drop(&mut self) {
1450 if DROPS.fetch_add(1, Ordering::SeqCst) == PANIC_POINT.load(Ordering::SeqCst) {
1451 panic!("panic in `drop`");
1456 for panic_point in vec![0, 1, size - 2, size - 1] {
1457 DROPS.store(0, Ordering::SeqCst);
1458 PANIC_POINT.store(panic_point, Ordering::SeqCst);
1459 let map: BTreeMap<_, _> = (0..size).map(|i| (i, D)).collect();
1460 catch_unwind(move || drop(map.into_iter())).unwrap_err();
1461 assert_eq!(DROPS.load(Ordering::SeqCst), size);