1 use super::super::testing::crash_test::{CrashTestDummy, Panic};
2 use super::super::testing::ord_chaos::{Cyclic3, Governed, Governor};
3 use super::super::testing::rng::DeterministicRng;
4 use super::Entry::{Occupied, Vacant};
9 use crate::string::{String, ToString};
11 use std::cmp::Ordering;
12 use std::convert::TryFrom;
13 use std::iter::{self, FromIterator};
15 use std::ops::Bound::{self, Excluded, Included, Unbounded};
16 use std::ops::RangeBounds;
17 use std::panic::{catch_unwind, AssertUnwindSafe};
18 use std::sync::atomic::{AtomicUsize, Ordering::SeqCst};
20 // Minimum number of elements to insert, to guarantee a tree with 2 levels,
21 // i.e., a tree who's root is an internal node at height 1, with edges to leaf nodes.
22 // It's not the minimum size: removing an element from such a tree does not always reduce height.
23 const MIN_INSERTS_HEIGHT_1: usize = node::CAPACITY + 1;
25 // Minimum number of elements to insert in ascending order, to guarantee a tree with 3 levels,
26 // i.e., a tree who's root is an internal node at height 2, with edges to more internal nodes.
27 // It's not the minimum size: removing an element from such a tree does not always reduce height.
28 const MIN_INSERTS_HEIGHT_2: usize = 89;
30 // Gathers all references from a mutable iterator and makes sure Miri notices if
31 // using them is dangerous.
32 fn test_all_refs<'a, T: 'a>(dummy: &mut T, iter: impl Iterator<Item = &'a mut T>) {
33 // Gather all those references.
34 let mut refs: Vec<&mut T> = iter.collect();
35 // Use them all. Twice, to be sure we got all interleavings.
36 for r in refs.iter_mut() {
44 impl<K, V> BTreeMap<K, V> {
45 // Panics if the map (or the code navigating it) is corrupted.
46 fn check_invariants(&self) {
47 if let Some(root) = &self.root {
48 let root_node = root.reborrow();
50 // Check the back pointers top-down, before we attempt to rely on
51 // more serious navigation code.
52 assert!(root_node.ascend().is_err());
53 root_node.assert_back_pointers();
55 // Check consistency of `length` with what navigation code encounters.
56 assert_eq!(self.length, root_node.calc_length());
58 // Lastly, check the invariant causing the least harm.
59 root_node.assert_min_len(if root_node.height() > 0 { 1 } else { 0 });
61 assert_eq!(self.length, 0);
64 // Check that `assert_strictly_ascending` will encounter all keys.
65 assert_eq!(self.length, self.keys().count());
68 // Panics if the map is corrupted or if the keys are not in strictly
69 // ascending order, in the current opinion of the `Ord` implementation.
70 // If the `Ord` implementation violates transitivity, this method does not
71 // guarantee that all keys are unique, just that adjacent keys are unique.
76 self.check_invariants();
77 self.assert_strictly_ascending();
80 // Returns the height of the root, if any.
81 fn height(&self) -> Option<usize> {
82 self.root.as_ref().map(node::Root::height)
85 fn dump_keys(&self) -> String
89 if let Some(root) = self.root.as_ref() {
90 root.reborrow().dump_keys()
92 String::from("not yet allocated")
96 // Panics if the keys are not in strictly ascending order.
97 fn assert_strictly_ascending(&self)
101 let mut keys = self.keys();
102 if let Some(mut previous) = keys.next() {
104 assert!(previous < next, "{:?} >= {:?}", previous, next);
110 // Transform the tree to minimize wasted space, obtaining fewer nodes that
111 // are mostly filled up to their capacity. The same compact tree could have
112 // been obtained by inserting keys in a shrewd order.
113 fn compact(&mut self)
117 let iter = mem::take(self).into_iter();
118 let root = BTreeMap::ensure_is_owned(&mut self.root);
119 root.bulk_push(iter, &mut self.length);
123 impl<'a, K: 'a, V: 'a> NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal> {
124 fn assert_min_len(self, min_len: usize) {
125 assert!(self.len() >= min_len, "node len {} < {}", self.len(), min_len);
126 if let node::ForceResult::Internal(node) = self.force() {
127 for idx in 0..=node.len() {
128 let edge = unsafe { Handle::new_edge(node, idx) };
129 edge.descend().assert_min_len(MIN_LEN);
135 // Tests our value of MIN_INSERTS_HEIGHT_2. Failure may mean you just need to
136 // adapt that value to match a change in node::CAPACITY or the choices made
137 // during insertion, otherwise other test cases may fail or be less useful.
140 let mut map = BTreeMap::new();
142 assert_eq!(map.height(), None);
143 assert_eq!(map.len(), 0);
146 while map.height() == Some(0) {
147 let last_key = *map.last_key_value().unwrap().0;
148 map.insert(last_key + 1, ());
152 // - 1 element in internal root node with 2 children
153 // - 6 elements in left leaf child
154 // - 5 elements in right leaf child
155 assert_eq!(map.height(), Some(1));
156 assert_eq!(map.len(), MIN_INSERTS_HEIGHT_1, "{}", map.dump_keys());
158 while map.height() == Some(1) {
159 let last_key = *map.last_key_value().unwrap().0;
160 map.insert(last_key + 1, ());
164 // - 1 element in internal root node with 2 children
165 // - 6 elements in left internal child with 7 grandchildren
166 // - 42 elements in left child's 7 grandchildren with 6 elements each
167 // - 5 elements in right internal child with 6 grandchildren
168 // - 30 elements in right child's 5 first grandchildren with 6 elements each
169 // - 5 elements in right child's last grandchild
170 assert_eq!(map.height(), Some(2));
171 assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2, "{}", map.dump_keys());
174 // Ensures the testing infrastructure usually notices order violations.
177 fn test_check_ord_chaos() {
178 let gov = Governor::new();
179 let map = BTreeMap::from([(Governed(1, &gov), ()), (Governed(2, &gov), ())]);
184 // Ensures the testing infrastructure doesn't always mind order violations.
186 fn test_check_invariants_ord_chaos() {
187 let gov = Governor::new();
188 let map = BTreeMap::from([(Governed(1, &gov), ()), (Governed(2, &gov), ())]);
190 map.check_invariants();
194 fn test_basic_large() {
195 let mut map = BTreeMap::new();
197 let size = if cfg!(miri) { MIN_INSERTS_HEIGHT_2 } else { 10000 };
198 let size = size + (size % 2); // round up to even number
199 assert_eq!(map.len(), 0);
202 assert_eq!(map.insert(i, 10 * i), None);
203 assert_eq!(map.len(), i + 1);
206 assert_eq!(map.first_key_value(), Some((&0, &0)));
207 assert_eq!(map.last_key_value(), Some((&(size - 1), &(10 * (size - 1)))));
208 assert_eq!(map.first_entry().unwrap().key(), &0);
209 assert_eq!(map.last_entry().unwrap().key(), &(size - 1));
212 assert_eq!(map.get(&i).unwrap(), &(i * 10));
215 for i in size..size * 2 {
216 assert_eq!(map.get(&i), None);
220 assert_eq!(map.insert(i, 100 * i), Some(10 * i));
221 assert_eq!(map.len(), size);
225 assert_eq!(map.get(&i).unwrap(), &(i * 100));
228 for i in 0..size / 2 {
229 assert_eq!(map.remove(&(i * 2)), Some(i * 200));
230 assert_eq!(map.len(), size - i - 1);
233 for i in 0..size / 2 {
234 assert_eq!(map.get(&(2 * i)), None);
235 assert_eq!(map.get(&(2 * i + 1)).unwrap(), &(i * 200 + 100));
238 for i in 0..size / 2 {
239 assert_eq!(map.remove(&(2 * i)), None);
240 assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
241 assert_eq!(map.len(), size / 2 - i - 1);
247 fn test_basic_small() {
248 let mut map = BTreeMap::new();
249 // Empty, root is absent (None):
250 assert_eq!(map.remove(&1), None);
251 assert_eq!(map.len(), 0);
252 assert_eq!(map.get(&1), None);
253 assert_eq!(map.get_mut(&1), None);
254 assert_eq!(map.first_key_value(), None);
255 assert_eq!(map.last_key_value(), None);
256 assert_eq!(map.keys().count(), 0);
257 assert_eq!(map.values().count(), 0);
258 assert_eq!(map.range(..).next(), None);
259 assert_eq!(map.range(..1).next(), None);
260 assert_eq!(map.range(1..).next(), None);
261 assert_eq!(map.range(1..=1).next(), None);
262 assert_eq!(map.range(1..2).next(), None);
263 assert_eq!(map.height(), None);
264 assert_eq!(map.insert(1, 1), None);
265 assert_eq!(map.height(), Some(0));
269 assert_eq!(map.len(), 1);
270 assert_eq!(map.get(&1), Some(&1));
271 assert_eq!(map.get_mut(&1), Some(&mut 1));
272 assert_eq!(map.first_key_value(), Some((&1, &1)));
273 assert_eq!(map.last_key_value(), Some((&1, &1)));
274 assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1]);
275 assert_eq!(map.values().collect::<Vec<_>>(), vec![&1]);
276 assert_eq!(map.insert(1, 2), Some(1));
277 assert_eq!(map.len(), 1);
278 assert_eq!(map.get(&1), Some(&2));
279 assert_eq!(map.get_mut(&1), Some(&mut 2));
280 assert_eq!(map.first_key_value(), Some((&1, &2)));
281 assert_eq!(map.last_key_value(), Some((&1, &2)));
282 assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1]);
283 assert_eq!(map.values().collect::<Vec<_>>(), vec![&2]);
284 assert_eq!(map.insert(2, 4), None);
285 assert_eq!(map.height(), Some(0));
288 // 2 key-value pairs:
289 assert_eq!(map.len(), 2);
290 assert_eq!(map.get(&2), Some(&4));
291 assert_eq!(map.get_mut(&2), Some(&mut 4));
292 assert_eq!(map.first_key_value(), Some((&1, &2)));
293 assert_eq!(map.last_key_value(), Some((&2, &4)));
294 assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1, &2]);
295 assert_eq!(map.values().collect::<Vec<_>>(), vec![&2, &4]);
296 assert_eq!(map.remove(&1), Some(2));
297 assert_eq!(map.height(), Some(0));
301 assert_eq!(map.len(), 1);
302 assert_eq!(map.get(&1), None);
303 assert_eq!(map.get_mut(&1), None);
304 assert_eq!(map.get(&2), Some(&4));
305 assert_eq!(map.get_mut(&2), Some(&mut 4));
306 assert_eq!(map.first_key_value(), Some((&2, &4)));
307 assert_eq!(map.last_key_value(), Some((&2, &4)));
308 assert_eq!(map.keys().collect::<Vec<_>>(), vec![&2]);
309 assert_eq!(map.values().collect::<Vec<_>>(), vec![&4]);
310 assert_eq!(map.remove(&2), Some(4));
311 assert_eq!(map.height(), Some(0));
314 // Empty but root is owned (Some(...)):
315 assert_eq!(map.len(), 0);
316 assert_eq!(map.get(&1), None);
317 assert_eq!(map.get_mut(&1), None);
318 assert_eq!(map.first_key_value(), None);
319 assert_eq!(map.last_key_value(), None);
320 assert_eq!(map.keys().count(), 0);
321 assert_eq!(map.values().count(), 0);
322 assert_eq!(map.range(..).next(), None);
323 assert_eq!(map.range(..1).next(), None);
324 assert_eq!(map.range(1..).next(), None);
325 assert_eq!(map.range(1..=1).next(), None);
326 assert_eq!(map.range(1..2).next(), None);
327 assert_eq!(map.remove(&1), None);
328 assert_eq!(map.height(), Some(0));
335 let size = if cfg!(miri) { 200 } else { 10000 };
336 let mut map = BTreeMap::from_iter((0..size).map(|i| (i, i)));
338 fn test<T>(size: usize, mut iter: T)
340 T: Iterator<Item = (usize, usize)>,
343 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
344 assert_eq!(iter.next().unwrap(), (i, i));
346 assert_eq!(iter.size_hint(), (0, Some(0)));
347 assert_eq!(iter.next(), None);
349 test(size, map.iter().map(|(&k, &v)| (k, v)));
350 test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
351 test(size, map.into_iter());
357 let size = if cfg!(miri) { 200 } else { 10000 };
358 let mut map = BTreeMap::from_iter((0..size).map(|i| (i, i)));
360 fn test<T>(size: usize, mut iter: T)
362 T: Iterator<Item = (usize, usize)>,
365 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
366 assert_eq!(iter.next().unwrap(), (size - i - 1, size - i - 1));
368 assert_eq!(iter.size_hint(), (0, Some(0)));
369 assert_eq!(iter.next(), None);
371 test(size, map.iter().rev().map(|(&k, &v)| (k, v)));
372 test(size, map.iter_mut().rev().map(|(&k, &mut v)| (k, v)));
373 test(size, map.into_iter().rev());
376 // Specifically tests iter_mut's ability to mutate the value of pairs in-line.
377 fn do_test_iter_mut_mutation<T>(size: usize)
379 T: Copy + Debug + Ord + TryFrom<usize>,
380 <T as TryFrom<usize>>::Error: Debug,
382 let zero = T::try_from(0).unwrap();
383 let mut map = BTreeMap::from_iter((0..size).map(|i| (T::try_from(i).unwrap(), zero)));
385 // Forward and backward iteration sees enough pairs (also tested elsewhere)
386 assert_eq!(map.iter_mut().count(), size);
387 assert_eq!(map.iter_mut().rev().count(), size);
389 // Iterate forwards, trying to mutate to unique values
390 for (i, (k, v)) in map.iter_mut().enumerate() {
391 assert_eq!(*k, T::try_from(i).unwrap());
392 assert_eq!(*v, zero);
393 *v = T::try_from(i + 1).unwrap();
396 // Iterate backwards, checking that mutations succeeded and trying to mutate again
397 for (i, (k, v)) in map.iter_mut().rev().enumerate() {
398 assert_eq!(*k, T::try_from(size - i - 1).unwrap());
399 assert_eq!(*v, T::try_from(size - i).unwrap());
400 *v = T::try_from(2 * size - i).unwrap();
403 // Check that backward mutations succeeded
404 for (i, (k, v)) in map.iter_mut().enumerate() {
405 assert_eq!(*k, T::try_from(i).unwrap());
406 assert_eq!(*v, T::try_from(size + i + 1).unwrap());
411 #[derive(Clone, Copy, Debug, Eq, PartialEq, PartialOrd, Ord)]
413 struct Align32(usize);
415 impl TryFrom<usize> for Align32 {
418 fn try_from(s: usize) -> Result<Align32, ()> {
424 fn test_iter_mut_mutation() {
425 // Check many alignments and trees with roots at various heights.
426 do_test_iter_mut_mutation::<u8>(0);
427 do_test_iter_mut_mutation::<u8>(1);
428 do_test_iter_mut_mutation::<u8>(MIN_INSERTS_HEIGHT_1);
429 do_test_iter_mut_mutation::<u8>(MIN_INSERTS_HEIGHT_2);
430 do_test_iter_mut_mutation::<u16>(1);
431 do_test_iter_mut_mutation::<u16>(MIN_INSERTS_HEIGHT_1);
432 do_test_iter_mut_mutation::<u16>(MIN_INSERTS_HEIGHT_2);
433 do_test_iter_mut_mutation::<u32>(1);
434 do_test_iter_mut_mutation::<u32>(MIN_INSERTS_HEIGHT_1);
435 do_test_iter_mut_mutation::<u32>(MIN_INSERTS_HEIGHT_2);
436 do_test_iter_mut_mutation::<u64>(1);
437 do_test_iter_mut_mutation::<u64>(MIN_INSERTS_HEIGHT_1);
438 do_test_iter_mut_mutation::<u64>(MIN_INSERTS_HEIGHT_2);
439 do_test_iter_mut_mutation::<u128>(1);
440 do_test_iter_mut_mutation::<u128>(MIN_INSERTS_HEIGHT_1);
441 do_test_iter_mut_mutation::<u128>(MIN_INSERTS_HEIGHT_2);
442 do_test_iter_mut_mutation::<Align32>(1);
443 do_test_iter_mut_mutation::<Align32>(MIN_INSERTS_HEIGHT_1);
444 do_test_iter_mut_mutation::<Align32>(MIN_INSERTS_HEIGHT_2);
448 fn test_values_mut() {
449 let mut a = BTreeMap::from_iter((0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)));
450 test_all_refs(&mut 13, a.values_mut());
455 fn test_values_mut_mutation() {
456 let mut a = BTreeMap::new();
457 a.insert(1, String::from("hello"));
458 a.insert(2, String::from("goodbye"));
460 for value in a.values_mut() {
464 let values = Vec::from_iter(a.values().cloned());
465 assert_eq!(values, [String::from("hello!"), String::from("goodbye!")]);
470 fn test_iter_entering_root_twice() {
471 let mut map = BTreeMap::from([(0, 0), (1, 1)]);
472 let mut it = map.iter_mut();
473 let front = it.next().unwrap();
474 let back = it.next_back().unwrap();
475 assert_eq!(front, (&0, &mut 0));
476 assert_eq!(back, (&1, &mut 1));
479 assert_eq!(front, (&0, &mut 24));
480 assert_eq!(back, (&1, &mut 42));
481 assert_eq!(it.next(), None);
482 assert_eq!(it.next_back(), None);
487 fn test_iter_descending_to_same_node_twice() {
488 let mut map = BTreeMap::from_iter((0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i)));
489 let mut it = map.iter_mut();
490 // Descend into first child.
491 let front = it.next().unwrap();
492 // Descend into first child again, after running through second child.
493 while it.next_back().is_some() {}
494 // Check immutable access.
495 assert_eq!(front, (&0, &mut 0));
496 // Perform mutable access.
502 fn test_iter_mixed() {
504 let size = if cfg!(miri) { 200 } else { 10000 };
506 let mut map = BTreeMap::from_iter((0..size).map(|i| (i, i)));
508 fn test<T>(size: usize, mut iter: T)
510 T: Iterator<Item = (usize, usize)> + DoubleEndedIterator,
512 for i in 0..size / 4 {
513 assert_eq!(iter.size_hint(), (size - i * 2, Some(size - i * 2)));
514 assert_eq!(iter.next().unwrap(), (i, i));
515 assert_eq!(iter.next_back().unwrap(), (size - i - 1, size - i - 1));
517 for i in size / 4..size * 3 / 4 {
518 assert_eq!(iter.size_hint(), (size * 3 / 4 - i, Some(size * 3 / 4 - i)));
519 assert_eq!(iter.next().unwrap(), (i, i));
521 assert_eq!(iter.size_hint(), (0, Some(0)));
522 assert_eq!(iter.next(), None);
524 test(size, map.iter().map(|(&k, &v)| (k, v)));
525 test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
526 test(size, map.into_iter());
530 fn test_iter_min_max() {
531 let mut a = BTreeMap::new();
532 assert_eq!(a.iter().min(), None);
533 assert_eq!(a.iter().max(), None);
534 assert_eq!(a.iter_mut().min(), None);
535 assert_eq!(a.iter_mut().max(), None);
536 assert_eq!(a.range(..).min(), None);
537 assert_eq!(a.range(..).max(), None);
538 assert_eq!(a.range_mut(..).min(), None);
539 assert_eq!(a.range_mut(..).max(), None);
540 assert_eq!(a.keys().min(), None);
541 assert_eq!(a.keys().max(), None);
542 assert_eq!(a.values().min(), None);
543 assert_eq!(a.values().max(), None);
544 assert_eq!(a.values_mut().min(), None);
545 assert_eq!(a.values_mut().max(), None);
548 assert_eq!(a.iter().min(), Some((&1, &42)));
549 assert_eq!(a.iter().max(), Some((&2, &24)));
550 assert_eq!(a.iter_mut().min(), Some((&1, &mut 42)));
551 assert_eq!(a.iter_mut().max(), Some((&2, &mut 24)));
552 assert_eq!(a.range(..).min(), Some((&1, &42)));
553 assert_eq!(a.range(..).max(), Some((&2, &24)));
554 assert_eq!(a.range_mut(..).min(), Some((&1, &mut 42)));
555 assert_eq!(a.range_mut(..).max(), Some((&2, &mut 24)));
556 assert_eq!(a.keys().min(), Some(&1));
557 assert_eq!(a.keys().max(), Some(&2));
558 assert_eq!(a.values().min(), Some(&24));
559 assert_eq!(a.values().max(), Some(&42));
560 assert_eq!(a.values_mut().min(), Some(&mut 24));
561 assert_eq!(a.values_mut().max(), Some(&mut 42));
565 fn range_keys(map: &BTreeMap<i32, i32>, range: impl RangeBounds<i32>) -> Vec<i32> {
566 Vec::from_iter(map.range(range).map(|(&k, &v)| {
573 fn test_range_small() {
576 let all = Vec::from_iter(1..=size);
577 let (first, last) = (vec![all[0]], vec![all[size as usize - 1]]);
578 let map = BTreeMap::from_iter(all.iter().copied().map(|i| (i, i)));
580 assert_eq!(range_keys(&map, (Excluded(0), Excluded(size + 1))), all);
581 assert_eq!(range_keys(&map, (Excluded(0), Included(size + 1))), all);
582 assert_eq!(range_keys(&map, (Excluded(0), Included(size))), all);
583 assert_eq!(range_keys(&map, (Excluded(0), Unbounded)), all);
584 assert_eq!(range_keys(&map, (Included(0), Excluded(size + 1))), all);
585 assert_eq!(range_keys(&map, (Included(0), Included(size + 1))), all);
586 assert_eq!(range_keys(&map, (Included(0), Included(size))), all);
587 assert_eq!(range_keys(&map, (Included(0), Unbounded)), all);
588 assert_eq!(range_keys(&map, (Included(1), Excluded(size + 1))), all);
589 assert_eq!(range_keys(&map, (Included(1), Included(size + 1))), all);
590 assert_eq!(range_keys(&map, (Included(1), Included(size))), all);
591 assert_eq!(range_keys(&map, (Included(1), Unbounded)), all);
592 assert_eq!(range_keys(&map, (Unbounded, Excluded(size + 1))), all);
593 assert_eq!(range_keys(&map, (Unbounded, Included(size + 1))), all);
594 assert_eq!(range_keys(&map, (Unbounded, Included(size))), all);
595 assert_eq!(range_keys(&map, ..), all);
597 assert_eq!(range_keys(&map, (Excluded(0), Excluded(1))), vec![]);
598 assert_eq!(range_keys(&map, (Excluded(0), Included(0))), vec![]);
599 assert_eq!(range_keys(&map, (Included(0), Included(0))), vec![]);
600 assert_eq!(range_keys(&map, (Included(0), Excluded(1))), vec![]);
601 assert_eq!(range_keys(&map, (Unbounded, Excluded(1))), vec![]);
602 assert_eq!(range_keys(&map, (Unbounded, Included(0))), vec![]);
603 assert_eq!(range_keys(&map, (Excluded(0), Excluded(2))), first);
604 assert_eq!(range_keys(&map, (Excluded(0), Included(1))), first);
605 assert_eq!(range_keys(&map, (Included(0), Excluded(2))), first);
606 assert_eq!(range_keys(&map, (Included(0), Included(1))), first);
607 assert_eq!(range_keys(&map, (Included(1), Excluded(2))), first);
608 assert_eq!(range_keys(&map, (Included(1), Included(1))), first);
609 assert_eq!(range_keys(&map, (Unbounded, Excluded(2))), first);
610 assert_eq!(range_keys(&map, (Unbounded, Included(1))), first);
611 assert_eq!(range_keys(&map, (Excluded(size - 1), Excluded(size + 1))), last);
612 assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size + 1))), last);
613 assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size))), last);
614 assert_eq!(range_keys(&map, (Excluded(size - 1), Unbounded)), last);
615 assert_eq!(range_keys(&map, (Included(size), Excluded(size + 1))), last);
616 assert_eq!(range_keys(&map, (Included(size), Included(size + 1))), last);
617 assert_eq!(range_keys(&map, (Included(size), Included(size))), last);
618 assert_eq!(range_keys(&map, (Included(size), Unbounded)), last);
619 assert_eq!(range_keys(&map, (Excluded(size), Excluded(size + 1))), vec![]);
620 assert_eq!(range_keys(&map, (Excluded(size), Included(size))), vec![]);
621 assert_eq!(range_keys(&map, (Excluded(size), Unbounded)), vec![]);
622 assert_eq!(range_keys(&map, (Included(size + 1), Excluded(size + 1))), vec![]);
623 assert_eq!(range_keys(&map, (Included(size + 1), Included(size + 1))), vec![]);
624 assert_eq!(range_keys(&map, (Included(size + 1), Unbounded)), vec![]);
626 assert_eq!(range_keys(&map, ..3), vec![1, 2]);
627 assert_eq!(range_keys(&map, 3..), vec![3, 4]);
628 assert_eq!(range_keys(&map, 2..=3), vec![2, 3]);
632 fn test_range_height_1() {
633 // Tests tree with a root and 2 leaves. We test around the middle of the
634 // keys because one of those is the single key in the root node.
635 let map = BTreeMap::from_iter((0..MIN_INSERTS_HEIGHT_1 as i32).map(|i| (i, i)));
636 let middle = MIN_INSERTS_HEIGHT_1 as i32 / 2;
637 for root in middle - 2..=middle + 2 {
638 assert_eq!(range_keys(&map, (Excluded(root), Excluded(root + 1))), vec![]);
639 assert_eq!(range_keys(&map, (Excluded(root), Included(root + 1))), vec![root + 1]);
640 assert_eq!(range_keys(&map, (Included(root), Excluded(root + 1))), vec![root]);
641 assert_eq!(range_keys(&map, (Included(root), Included(root + 1))), vec![root, root + 1]);
643 assert_eq!(range_keys(&map, (Excluded(root - 1), Excluded(root))), vec![]);
644 assert_eq!(range_keys(&map, (Included(root - 1), Excluded(root))), vec![root - 1]);
645 assert_eq!(range_keys(&map, (Excluded(root - 1), Included(root))), vec![root]);
646 assert_eq!(range_keys(&map, (Included(root - 1), Included(root))), vec![root - 1, root]);
651 fn test_range_large() {
654 let all = Vec::from_iter(1..=size);
655 let (first, last) = (vec![all[0]], vec![all[size as usize - 1]]);
656 let map = BTreeMap::from_iter(all.iter().copied().map(|i| (i, i)));
658 assert_eq!(range_keys(&map, (Excluded(0), Excluded(size + 1))), all);
659 assert_eq!(range_keys(&map, (Excluded(0), Included(size + 1))), all);
660 assert_eq!(range_keys(&map, (Excluded(0), Included(size))), all);
661 assert_eq!(range_keys(&map, (Excluded(0), Unbounded)), all);
662 assert_eq!(range_keys(&map, (Included(0), Excluded(size + 1))), all);
663 assert_eq!(range_keys(&map, (Included(0), Included(size + 1))), all);
664 assert_eq!(range_keys(&map, (Included(0), Included(size))), all);
665 assert_eq!(range_keys(&map, (Included(0), Unbounded)), all);
666 assert_eq!(range_keys(&map, (Included(1), Excluded(size + 1))), all);
667 assert_eq!(range_keys(&map, (Included(1), Included(size + 1))), all);
668 assert_eq!(range_keys(&map, (Included(1), Included(size))), all);
669 assert_eq!(range_keys(&map, (Included(1), Unbounded)), all);
670 assert_eq!(range_keys(&map, (Unbounded, Excluded(size + 1))), all);
671 assert_eq!(range_keys(&map, (Unbounded, Included(size + 1))), all);
672 assert_eq!(range_keys(&map, (Unbounded, Included(size))), all);
673 assert_eq!(range_keys(&map, ..), all);
675 assert_eq!(range_keys(&map, (Excluded(0), Excluded(1))), vec![]);
676 assert_eq!(range_keys(&map, (Excluded(0), Included(0))), vec![]);
677 assert_eq!(range_keys(&map, (Included(0), Included(0))), vec![]);
678 assert_eq!(range_keys(&map, (Included(0), Excluded(1))), vec![]);
679 assert_eq!(range_keys(&map, (Unbounded, Excluded(1))), vec![]);
680 assert_eq!(range_keys(&map, (Unbounded, Included(0))), vec![]);
681 assert_eq!(range_keys(&map, (Excluded(0), Excluded(2))), first);
682 assert_eq!(range_keys(&map, (Excluded(0), Included(1))), first);
683 assert_eq!(range_keys(&map, (Included(0), Excluded(2))), first);
684 assert_eq!(range_keys(&map, (Included(0), Included(1))), first);
685 assert_eq!(range_keys(&map, (Included(1), Excluded(2))), first);
686 assert_eq!(range_keys(&map, (Included(1), Included(1))), first);
687 assert_eq!(range_keys(&map, (Unbounded, Excluded(2))), first);
688 assert_eq!(range_keys(&map, (Unbounded, Included(1))), first);
689 assert_eq!(range_keys(&map, (Excluded(size - 1), Excluded(size + 1))), last);
690 assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size + 1))), last);
691 assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size))), last);
692 assert_eq!(range_keys(&map, (Excluded(size - 1), Unbounded)), last);
693 assert_eq!(range_keys(&map, (Included(size), Excluded(size + 1))), last);
694 assert_eq!(range_keys(&map, (Included(size), Included(size + 1))), last);
695 assert_eq!(range_keys(&map, (Included(size), Included(size))), last);
696 assert_eq!(range_keys(&map, (Included(size), Unbounded)), last);
697 assert_eq!(range_keys(&map, (Excluded(size), Excluded(size + 1))), vec![]);
698 assert_eq!(range_keys(&map, (Excluded(size), Included(size))), vec![]);
699 assert_eq!(range_keys(&map, (Excluded(size), Unbounded)), vec![]);
700 assert_eq!(range_keys(&map, (Included(size + 1), Excluded(size + 1))), vec![]);
701 assert_eq!(range_keys(&map, (Included(size + 1), Included(size + 1))), vec![]);
702 assert_eq!(range_keys(&map, (Included(size + 1), Unbounded)), vec![]);
704 fn check<'a, L, R>(lhs: L, rhs: R)
706 L: IntoIterator<Item = (&'a i32, &'a i32)>,
707 R: IntoIterator<Item = (&'a i32, &'a i32)>,
709 assert_eq!(Vec::from_iter(lhs), Vec::from_iter(rhs));
712 check(map.range(..=100), map.range(..101));
713 check(map.range(5..=8), vec![(&5, &5), (&6, &6), (&7, &7), (&8, &8)]);
714 check(map.range(-1..=2), vec![(&1, &1), (&2, &2)]);
718 fn test_range_inclusive_max_value() {
719 let max = usize::MAX;
720 let map = BTreeMap::from([(max, 0)]);
721 assert_eq!(Vec::from_iter(map.range(max..=max)), &[(&max, &0)]);
725 fn test_range_equal_empty_cases() {
726 let map = BTreeMap::from_iter((0..5).map(|i| (i, i)));
727 assert_eq!(map.range((Included(2), Excluded(2))).next(), None);
728 assert_eq!(map.range((Excluded(2), Included(2))).next(), None);
733 fn test_range_equal_excluded() {
734 let map = BTreeMap::from_iter((0..5).map(|i| (i, i)));
735 let _ = map.range((Excluded(2), Excluded(2)));
740 fn test_range_backwards_1() {
741 let map = BTreeMap::from_iter((0..5).map(|i| (i, i)));
742 let _ = map.range((Included(3), Included(2)));
747 fn test_range_backwards_2() {
748 let map = BTreeMap::from_iter((0..5).map(|i| (i, i)));
749 let _ = map.range((Included(3), Excluded(2)));
754 fn test_range_backwards_3() {
755 let map = BTreeMap::from_iter((0..5).map(|i| (i, i)));
756 let _ = map.range((Excluded(3), Included(2)));
761 fn test_range_backwards_4() {
762 let map = BTreeMap::from_iter((0..5).map(|i| (i, i)));
763 let _ = map.range((Excluded(3), Excluded(2)));
767 fn test_range_finding_ill_order_in_map() {
768 let mut map = BTreeMap::new();
769 map.insert(Cyclic3::B, ());
770 // Lacking static_assert, call `range` conditionally, to emphasise that
771 // we cause a different panic than `test_range_backwards_1` does.
772 // A more refined `should_panic` would be welcome.
773 if Cyclic3::C < Cyclic3::A {
774 let _ = map.range(Cyclic3::C..=Cyclic3::A);
779 fn test_range_finding_ill_order_in_range_ord() {
780 // Has proper order the first time asked, then flips around.
781 struct EvilTwin(i32);
783 impl PartialOrd for EvilTwin {
784 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
785 Some(self.cmp(other))
789 static COMPARES: AtomicUsize = AtomicUsize::new(0);
790 impl Ord for EvilTwin {
791 fn cmp(&self, other: &Self) -> Ordering {
792 let ord = self.0.cmp(&other.0);
793 if COMPARES.fetch_add(1, SeqCst) > 0 { ord.reverse() } else { ord }
797 impl PartialEq for EvilTwin {
798 fn eq(&self, other: &Self) -> bool {
803 impl Eq for EvilTwin {}
805 #[derive(PartialEq, Eq, PartialOrd, Ord)]
806 struct CompositeKey(i32, EvilTwin);
808 impl Borrow<EvilTwin> for CompositeKey {
809 fn borrow(&self) -> &EvilTwin {
814 let map = BTreeMap::from_iter((0..12).map(|i| (CompositeKey(i, EvilTwin(i)), ())));
815 let _ = map.range(EvilTwin(5)..=EvilTwin(7));
819 fn test_range_1000() {
821 let size = if cfg!(miri) { MIN_INSERTS_HEIGHT_2 as u32 } else { 1000 };
822 let map = BTreeMap::from_iter((0..size).map(|i| (i, i)));
824 fn test(map: &BTreeMap<u32, u32>, size: u32, min: Bound<&u32>, max: Bound<&u32>) {
825 let mut kvs = map.range((min, max)).map(|(&k, &v)| (k, v));
826 let mut pairs = (0..size).map(|i| (i, i));
828 for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
829 assert_eq!(kv, pair);
831 assert_eq!(kvs.next(), None);
832 assert_eq!(pairs.next(), None);
834 test(&map, size, Included(&0), Excluded(&size));
835 test(&map, size, Unbounded, Excluded(&size));
836 test(&map, size, Included(&0), Included(&(size - 1)));
837 test(&map, size, Unbounded, Included(&(size - 1)));
838 test(&map, size, Included(&0), Unbounded);
839 test(&map, size, Unbounded, Unbounded);
843 fn test_range_borrowed_key() {
844 let mut map = BTreeMap::new();
845 map.insert("aardvark".to_string(), 1);
846 map.insert("baboon".to_string(), 2);
847 map.insert("coyote".to_string(), 3);
848 map.insert("dingo".to_string(), 4);
849 // NOTE: would like to use simply "b".."d" here...
850 let mut iter = map.range::<str, _>((Included("b"), Excluded("d")));
851 assert_eq!(iter.next(), Some((&"baboon".to_string(), &2)));
852 assert_eq!(iter.next(), Some((&"coyote".to_string(), &3)));
853 assert_eq!(iter.next(), None);
860 let step = if cfg!(miri) { 66 } else { 1 };
861 let map = BTreeMap::from_iter((0..size).map(|i| (i, i)));
863 for i in (0..size).step_by(step) {
864 for j in (i..size).step_by(step) {
865 let mut kvs = map.range((Included(&i), Included(&j))).map(|(&k, &v)| (k, v));
866 let mut pairs = (i..=j).map(|i| (i, i));
868 for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
869 assert_eq!(kv, pair);
871 assert_eq!(kvs.next(), None);
872 assert_eq!(pairs.next(), None);
878 fn test_range_mut() {
881 let step = if cfg!(miri) { 66 } else { 1 };
882 let mut map = BTreeMap::from_iter((0..size).map(|i| (i, i)));
884 for i in (0..size).step_by(step) {
885 for j in (i..size).step_by(step) {
886 let mut kvs = map.range_mut((Included(&i), Included(&j))).map(|(&k, &mut v)| (k, v));
887 let mut pairs = (i..=j).map(|i| (i, i));
889 for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
890 assert_eq!(kv, pair);
892 assert_eq!(kvs.next(), None);
893 assert_eq!(pairs.next(), None);
901 let mut map = BTreeMap::from_iter((0..100).map(|x| (x, x * 10)));
903 map.retain(|&k, _| k % 2 == 0);
904 assert_eq!(map.len(), 50);
905 assert_eq!(map[&2], 20);
906 assert_eq!(map[&4], 40);
907 assert_eq!(map[&6], 60);
910 mod test_drain_filter {
915 let mut map: BTreeMap<i32, i32> = BTreeMap::new();
916 map.drain_filter(|_, _| unreachable!("there's nothing to decide on"));
917 assert!(map.is_empty());
921 // Explicitly consumes the iterator, where most test cases drop it instantly.
923 fn consumed_keeping_all() {
924 let pairs = (0..3).map(|i| (i, i));
925 let mut map = BTreeMap::from_iter(pairs);
926 assert!(map.drain_filter(|_, _| false).eq(iter::empty()));
930 // Explicitly consumes the iterator, where most test cases drop it instantly.
932 fn consumed_removing_all() {
933 let pairs = (0..3).map(|i| (i, i));
934 let mut map = BTreeMap::from_iter(pairs.clone());
935 assert!(map.drain_filter(|_, _| true).eq(pairs));
936 assert!(map.is_empty());
940 // Explicitly consumes the iterator and modifies values through it.
942 fn mutating_and_keeping() {
943 let pairs = (0..3).map(|i| (i, i));
944 let mut map = BTreeMap::from_iter(pairs);
946 map.drain_filter(|_, v| {
952 assert!(map.keys().copied().eq(0..3));
953 assert!(map.values().copied().eq(6..9));
957 // Explicitly consumes the iterator and modifies values through it.
959 fn mutating_and_removing() {
960 let pairs = (0..3).map(|i| (i, i));
961 let mut map = BTreeMap::from_iter(pairs);
963 map.drain_filter(|_, v| {
967 .eq((0..3).map(|i| (i, i + 6)))
969 assert!(map.is_empty());
974 fn underfull_keeping_all() {
975 let pairs = (0..3).map(|i| (i, i));
976 let mut map = BTreeMap::from_iter(pairs);
977 map.drain_filter(|_, _| false);
978 assert!(map.keys().copied().eq(0..3));
983 fn underfull_removing_one() {
984 let pairs = (0..3).map(|i| (i, i));
986 let mut map = BTreeMap::from_iter(pairs.clone());
987 map.drain_filter(|i, _| *i == doomed);
988 assert_eq!(map.len(), 2);
994 fn underfull_keeping_one() {
995 let pairs = (0..3).map(|i| (i, i));
997 let mut map = BTreeMap::from_iter(pairs.clone());
998 map.drain_filter(|i, _| *i != sacred);
999 assert!(map.keys().copied().eq(sacred..=sacred));
1005 fn underfull_removing_all() {
1006 let pairs = (0..3).map(|i| (i, i));
1007 let mut map = BTreeMap::from_iter(pairs);
1008 map.drain_filter(|_, _| true);
1009 assert!(map.is_empty());
1014 fn height_0_keeping_all() {
1015 let pairs = (0..node::CAPACITY).map(|i| (i, i));
1016 let mut map = BTreeMap::from_iter(pairs);
1017 map.drain_filter(|_, _| false);
1018 assert!(map.keys().copied().eq(0..node::CAPACITY));
1023 fn height_0_removing_one() {
1024 let pairs = (0..node::CAPACITY).map(|i| (i, i));
1025 for doomed in 0..node::CAPACITY {
1026 let mut map = BTreeMap::from_iter(pairs.clone());
1027 map.drain_filter(|i, _| *i == doomed);
1028 assert_eq!(map.len(), node::CAPACITY - 1);
1034 fn height_0_keeping_one() {
1035 let pairs = (0..node::CAPACITY).map(|i| (i, i));
1036 for sacred in 0..node::CAPACITY {
1037 let mut map = BTreeMap::from_iter(pairs.clone());
1038 map.drain_filter(|i, _| *i != sacred);
1039 assert!(map.keys().copied().eq(sacred..=sacred));
1045 fn height_0_removing_all() {
1046 let pairs = (0..node::CAPACITY).map(|i| (i, i));
1047 let mut map = BTreeMap::from_iter(pairs);
1048 map.drain_filter(|_, _| true);
1049 assert!(map.is_empty());
1054 fn height_0_keeping_half() {
1055 let mut map = BTreeMap::from_iter((0..16).map(|i| (i, i)));
1056 assert_eq!(map.drain_filter(|i, _| *i % 2 == 0).count(), 8);
1057 assert_eq!(map.len(), 8);
1062 fn height_1_removing_all() {
1063 let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i));
1064 let mut map = BTreeMap::from_iter(pairs);
1065 map.drain_filter(|_, _| true);
1066 assert!(map.is_empty());
1071 fn height_1_removing_one() {
1072 let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i));
1073 for doomed in 0..MIN_INSERTS_HEIGHT_1 {
1074 let mut map = BTreeMap::from_iter(pairs.clone());
1075 map.drain_filter(|i, _| *i == doomed);
1076 assert_eq!(map.len(), MIN_INSERTS_HEIGHT_1 - 1);
1082 fn height_1_keeping_one() {
1083 let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i));
1084 for sacred in 0..MIN_INSERTS_HEIGHT_1 {
1085 let mut map = BTreeMap::from_iter(pairs.clone());
1086 map.drain_filter(|i, _| *i != sacred);
1087 assert!(map.keys().copied().eq(sacred..=sacred));
1093 fn height_2_removing_one() {
1094 let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
1095 for doomed in (0..MIN_INSERTS_HEIGHT_2).step_by(12) {
1096 let mut map = BTreeMap::from_iter(pairs.clone());
1097 map.drain_filter(|i, _| *i == doomed);
1098 assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2 - 1);
1104 fn height_2_keeping_one() {
1105 let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
1106 for sacred in (0..MIN_INSERTS_HEIGHT_2).step_by(12) {
1107 let mut map = BTreeMap::from_iter(pairs.clone());
1108 map.drain_filter(|i, _| *i != sacred);
1109 assert!(map.keys().copied().eq(sacred..=sacred));
1115 fn height_2_removing_all() {
1116 let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
1117 let mut map = BTreeMap::from_iter(pairs);
1118 map.drain_filter(|_, _| true);
1119 assert!(map.is_empty());
1124 fn drop_panic_leak() {
1125 let a = CrashTestDummy::new(0);
1126 let b = CrashTestDummy::new(1);
1127 let c = CrashTestDummy::new(2);
1128 let mut map = BTreeMap::new();
1129 map.insert(a.spawn(Panic::Never), ());
1130 map.insert(b.spawn(Panic::InDrop), ());
1131 map.insert(c.spawn(Panic::Never), ());
1133 catch_unwind(move || drop(map.drain_filter(|dummy, _| dummy.query(true)))).unwrap_err();
1135 assert_eq!(a.queried(), 1);
1136 assert_eq!(b.queried(), 1);
1137 assert_eq!(c.queried(), 0);
1138 assert_eq!(a.dropped(), 1);
1139 assert_eq!(b.dropped(), 1);
1140 assert_eq!(c.dropped(), 1);
1144 fn pred_panic_leak() {
1145 let a = CrashTestDummy::new(0);
1146 let b = CrashTestDummy::new(1);
1147 let c = CrashTestDummy::new(2);
1148 let mut map = BTreeMap::new();
1149 map.insert(a.spawn(Panic::Never), ());
1150 map.insert(b.spawn(Panic::InQuery), ());
1151 map.insert(c.spawn(Panic::InQuery), ());
1153 catch_unwind(AssertUnwindSafe(|| drop(map.drain_filter(|dummy, _| dummy.query(true)))))
1156 assert_eq!(a.queried(), 1);
1157 assert_eq!(b.queried(), 1);
1158 assert_eq!(c.queried(), 0);
1159 assert_eq!(a.dropped(), 1);
1160 assert_eq!(b.dropped(), 0);
1161 assert_eq!(c.dropped(), 0);
1162 assert_eq!(map.len(), 2);
1163 assert_eq!(map.first_entry().unwrap().key().id(), 1);
1164 assert_eq!(map.last_entry().unwrap().key().id(), 2);
1168 // Same as above, but attempt to use the iterator again after the panic in the predicate
1170 fn pred_panic_reuse() {
1171 let a = CrashTestDummy::new(0);
1172 let b = CrashTestDummy::new(1);
1173 let c = CrashTestDummy::new(2);
1174 let mut map = BTreeMap::new();
1175 map.insert(a.spawn(Panic::Never), ());
1176 map.insert(b.spawn(Panic::InQuery), ());
1177 map.insert(c.spawn(Panic::InQuery), ());
1180 let mut it = map.drain_filter(|dummy, _| dummy.query(true));
1181 catch_unwind(AssertUnwindSafe(|| while it.next().is_some() {})).unwrap_err();
1182 // Iterator behaviour after a panic is explicitly unspecified,
1183 // so this is just the current implementation:
1184 let result = catch_unwind(AssertUnwindSafe(|| it.next()));
1185 assert!(matches!(result, Ok(None)));
1188 assert_eq!(a.queried(), 1);
1189 assert_eq!(b.queried(), 1);
1190 assert_eq!(c.queried(), 0);
1191 assert_eq!(a.dropped(), 1);
1192 assert_eq!(b.dropped(), 0);
1193 assert_eq!(c.dropped(), 0);
1194 assert_eq!(map.len(), 2);
1195 assert_eq!(map.first_entry().unwrap().key().id(), 1);
1196 assert_eq!(map.last_entry().unwrap().key().id(), 2);
1203 // make sure these compile -- using the Borrow trait
1205 let mut map = BTreeMap::new();
1206 map.insert("0".to_string(), 1);
1207 assert_eq!(map["0"], 1);
1211 let mut map = BTreeMap::new();
1212 map.insert(Box::new(0), 1);
1213 assert_eq!(map[&0], 1);
1217 let mut map = BTreeMap::new();
1218 map.insert(Box::new([0, 1]) as Box<[i32]>, 1);
1219 assert_eq!(map[&[0, 1][..]], 1);
1223 let mut map = BTreeMap::new();
1224 map.insert(Rc::new(0), 1);
1225 assert_eq!(map[&0], 1);
1229 fn get<T: Ord>(v: &BTreeMap<Box<T>, ()>, t: &T) {
1234 fn get_mut<T: Ord>(v: &mut BTreeMap<Box<T>, ()>, t: &T) {
1235 let _ = v.get_mut(t);
1239 fn get_key_value<T: Ord>(v: &BTreeMap<Box<T>, ()>, t: &T) {
1240 let _ = v.get_key_value(t);
1244 fn contains_key<T: Ord>(v: &BTreeMap<Box<T>, ()>, t: &T) {
1245 let _ = v.contains_key(t);
1249 fn range<T: Ord>(v: &BTreeMap<Box<T>, ()>, t: T) {
1250 let _ = v.range(t..);
1254 fn range_mut<T: Ord>(v: &mut BTreeMap<Box<T>, ()>, t: T) {
1255 let _ = v.range_mut(t..);
1259 fn remove<T: Ord>(v: &mut BTreeMap<Box<T>, ()>, t: &T) {
1264 fn remove_entry<T: Ord>(v: &mut BTreeMap<Box<T>, ()>, t: &T) {
1269 fn split_off<T: Ord>(v: &mut BTreeMap<Box<T>, ()>, t: &T) {
1276 let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
1278 let mut map = BTreeMap::from(xs);
1280 // Existing key (insert)
1281 match map.entry(1) {
1282 Vacant(_) => unreachable!(),
1283 Occupied(mut view) => {
1284 assert_eq!(view.get(), &10);
1285 assert_eq!(view.insert(100), 10);
1288 assert_eq!(map.get(&1).unwrap(), &100);
1289 assert_eq!(map.len(), 6);
1291 // Existing key (update)
1292 match map.entry(2) {
1293 Vacant(_) => unreachable!(),
1294 Occupied(mut view) => {
1295 let v = view.get_mut();
1299 assert_eq!(map.get(&2).unwrap(), &200);
1300 assert_eq!(map.len(), 6);
1303 // Existing key (take)
1304 match map.entry(3) {
1305 Vacant(_) => unreachable!(),
1307 assert_eq!(view.remove(), 30);
1310 assert_eq!(map.get(&3), None);
1311 assert_eq!(map.len(), 5);
1314 // Inexistent key (insert)
1315 match map.entry(10) {
1316 Occupied(_) => unreachable!(),
1318 assert_eq!(*view.insert(1000), 1000);
1321 assert_eq!(map.get(&10).unwrap(), &1000);
1322 assert_eq!(map.len(), 6);
1327 fn test_extend_ref() {
1328 let mut a = BTreeMap::new();
1330 let mut b = BTreeMap::new();
1332 b.insert(3, "three");
1336 assert_eq!(a.len(), 3);
1337 assert_eq!(a[&1], "one");
1338 assert_eq!(a[&2], "two");
1339 assert_eq!(a[&3], "three");
1345 let mut m = BTreeMap::new();
1346 assert_eq!(m.len(), 0);
1348 assert_eq!(m.insert((), ()), None);
1349 assert_eq!(m.len(), 1);
1351 assert_eq!(m.insert((), ()), Some(()));
1352 assert_eq!(m.len(), 1);
1353 assert_eq!(m.iter().count(), 1);
1356 assert_eq!(m.len(), 0);
1362 assert_eq!(m.len(), 1);
1363 assert_eq!(m.iter().count(), 1);
1367 // This test's only purpose is to ensure that zero-sized keys with nonsensical orderings
1368 // do not cause segfaults when used with zero-sized values. All other map behavior is
1372 #[derive(Clone, Copy, Debug)]
1375 impl PartialEq for Bad {
1376 fn eq(&self, _: &Self) -> bool {
1383 impl PartialOrd for Bad {
1384 fn partial_cmp(&self, _: &Self) -> Option<Ordering> {
1385 Some(Ordering::Less)
1390 fn cmp(&self, _: &Self) -> Ordering {
1395 let mut m = BTreeMap::new();
1405 let mut map = BTreeMap::new();
1406 for &len in &[MIN_INSERTS_HEIGHT_1, MIN_INSERTS_HEIGHT_2, 0, node::CAPACITY] {
1410 assert_eq!(map.len(), len);
1413 assert!(map.is_empty());
1418 fn test_clear_drop_panic_leak() {
1419 let a = CrashTestDummy::new(0);
1420 let b = CrashTestDummy::new(1);
1421 let c = CrashTestDummy::new(2);
1423 let mut map = BTreeMap::new();
1424 map.insert(a.spawn(Panic::Never), ());
1425 map.insert(b.spawn(Panic::InDrop), ());
1426 map.insert(c.spawn(Panic::Never), ());
1428 catch_unwind(AssertUnwindSafe(|| map.clear())).unwrap_err();
1429 assert_eq!(a.dropped(), 1);
1430 assert_eq!(b.dropped(), 1);
1431 assert_eq!(c.dropped(), 1);
1432 assert_eq!(map.len(), 0);
1435 assert_eq!(a.dropped(), 1);
1436 assert_eq!(b.dropped(), 1);
1437 assert_eq!(c.dropped(), 1);
1442 let mut map = BTreeMap::new();
1443 let size = MIN_INSERTS_HEIGHT_1;
1444 assert_eq!(map.len(), 0);
1447 assert_eq!(map.insert(i, 10 * i), None);
1448 assert_eq!(map.len(), i + 1);
1450 assert_eq!(map, map.clone());
1454 assert_eq!(map.insert(i, 100 * i), Some(10 * i));
1455 assert_eq!(map.len(), size);
1457 assert_eq!(map, map.clone());
1460 for i in 0..size / 2 {
1461 assert_eq!(map.remove(&(i * 2)), Some(i * 200));
1462 assert_eq!(map.len(), size - i - 1);
1464 assert_eq!(map, map.clone());
1467 for i in 0..size / 2 {
1468 assert_eq!(map.remove(&(2 * i)), None);
1469 assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
1470 assert_eq!(map.len(), size / 2 - i - 1);
1472 assert_eq!(map, map.clone());
1475 // Test a tree with 2 semi-full levels and a tree with 3 levels.
1476 map = BTreeMap::from_iter((1..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)));
1477 assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2 - 1);
1478 assert_eq!(map, map.clone());
1480 assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2);
1481 assert_eq!(map, map.clone());
1485 fn test_clone_panic_leak(size: usize) {
1487 let dummies = Vec::from_iter((0..size).map(|id| CrashTestDummy::new(id)));
1488 let map = BTreeMap::from_iter(dummies.iter().map(|dummy| {
1489 let panic = if dummy.id == i { Panic::InClone } else { Panic::Never };
1490 (dummy.spawn(panic), ())
1493 catch_unwind(|| map.clone()).unwrap_err();
1495 assert_eq!(d.cloned(), if d.id <= i { 1 } else { 0 }, "id={}/{}", d.id, i);
1496 assert_eq!(d.dropped(), if d.id < i { 1 } else { 0 }, "id={}/{}", d.id, i);
1498 assert_eq!(map.len(), size);
1502 assert_eq!(d.cloned(), if d.id <= i { 1 } else { 0 }, "id={}/{}", d.id, i);
1503 assert_eq!(d.dropped(), if d.id < i { 2 } else { 1 }, "id={}/{}", d.id, i);
1509 fn test_clone_panic_leak_height_0() {
1510 test_clone_panic_leak(3)
1514 fn test_clone_panic_leak_height_1() {
1515 test_clone_panic_leak(MIN_INSERTS_HEIGHT_1)
1519 fn test_clone_from() {
1520 let mut map1 = BTreeMap::new();
1521 let max_size = MIN_INSERTS_HEIGHT_1;
1523 // Range to max_size inclusive, because i is the size of map1 being tested.
1524 for i in 0..=max_size {
1525 let mut map2 = BTreeMap::new();
1527 let mut map1_copy = map2.clone();
1528 map1_copy.clone_from(&map1); // small cloned from large
1529 assert_eq!(map1_copy, map1);
1530 let mut map2_copy = map1.clone();
1531 map2_copy.clone_from(&map2); // large cloned from small
1532 assert_eq!(map2_copy, map2);
1533 map2.insert(100 * j + 1, 2 * j + 1);
1535 map2.clone_from(&map1); // same length
1537 assert_eq!(map2, map1);
1538 map1.insert(i, 10 * i);
1544 fn assert_covariance() {
1545 fn map_key<'new>(v: BTreeMap<&'static str, ()>) -> BTreeMap<&'new str, ()> {
1548 fn map_val<'new>(v: BTreeMap<(), &'static str>) -> BTreeMap<(), &'new str> {
1552 fn iter_key<'a, 'new>(v: Iter<'a, &'static str, ()>) -> Iter<'a, &'new str, ()> {
1555 fn iter_val<'a, 'new>(v: Iter<'a, (), &'static str>) -> Iter<'a, (), &'new str> {
1559 fn into_iter_key<'new>(v: IntoIter<&'static str, ()>) -> IntoIter<&'new str, ()> {
1562 fn into_iter_val<'new>(v: IntoIter<(), &'static str>) -> IntoIter<(), &'new str> {
1566 fn into_keys_key<'new>(v: IntoKeys<&'static str, ()>) -> IntoKeys<&'new str, ()> {
1569 fn into_keys_val<'new>(v: IntoKeys<(), &'static str>) -> IntoKeys<(), &'new str> {
1573 fn into_values_key<'new>(v: IntoValues<&'static str, ()>) -> IntoValues<&'new str, ()> {
1576 fn into_values_val<'new>(v: IntoValues<(), &'static str>) -> IntoValues<(), &'new str> {
1580 fn range_key<'a, 'new>(v: Range<'a, &'static str, ()>) -> Range<'a, &'new str, ()> {
1583 fn range_val<'a, 'new>(v: Range<'a, (), &'static str>) -> Range<'a, (), &'new str> {
1587 fn keys_key<'a, 'new>(v: Keys<'a, &'static str, ()>) -> Keys<'a, &'new str, ()> {
1590 fn keys_val<'a, 'new>(v: Keys<'a, (), &'static str>) -> Keys<'a, (), &'new str> {
1594 fn values_key<'a, 'new>(v: Values<'a, &'static str, ()>) -> Values<'a, &'new str, ()> {
1597 fn values_val<'a, 'new>(v: Values<'a, (), &'static str>) -> Values<'a, (), &'new str> {
1604 fn map<T: Sync>(v: &BTreeMap<T, T>) -> impl Sync + '_ {
1608 fn into_iter<T: Sync>(v: BTreeMap<T, T>) -> impl Sync {
1612 fn into_keys<T: Sync + Ord>(v: BTreeMap<T, T>) -> impl Sync {
1616 fn into_values<T: Sync + Ord>(v: BTreeMap<T, T>) -> impl Sync {
1620 fn drain_filter<T: Sync + Ord>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ {
1621 v.drain_filter(|_, _| false)
1624 fn iter<T: Sync>(v: &BTreeMap<T, T>) -> impl Sync + '_ {
1628 fn iter_mut<T: Sync>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ {
1632 fn keys<T: Sync>(v: &BTreeMap<T, T>) -> impl Sync + '_ {
1636 fn values<T: Sync>(v: &BTreeMap<T, T>) -> impl Sync + '_ {
1640 fn values_mut<T: Sync>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ {
1644 fn range<T: Sync + Ord>(v: &BTreeMap<T, T>) -> impl Sync + '_ {
1648 fn range_mut<T: Sync + Ord>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ {
1652 fn entry<T: Sync + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ {
1653 v.entry(Default::default())
1656 fn occupied_entry<T: Sync + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ {
1657 match v.entry(Default::default()) {
1658 Occupied(entry) => entry,
1659 _ => unreachable!(),
1663 fn vacant_entry<T: Sync + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ {
1664 match v.entry(Default::default()) {
1665 Vacant(entry) => entry,
1666 _ => unreachable!(),
1673 fn map<T: Send>(v: BTreeMap<T, T>) -> impl Send {
1677 fn into_iter<T: Send>(v: BTreeMap<T, T>) -> impl Send {
1681 fn into_keys<T: Send + Ord>(v: BTreeMap<T, T>) -> impl Send {
1685 fn into_values<T: Send + Ord>(v: BTreeMap<T, T>) -> impl Send {
1689 fn drain_filter<T: Send + Ord>(v: &mut BTreeMap<T, T>) -> impl Send + '_ {
1690 v.drain_filter(|_, _| false)
1693 fn iter<T: Send + Sync>(v: &BTreeMap<T, T>) -> impl Send + '_ {
1697 fn iter_mut<T: Send>(v: &mut BTreeMap<T, T>) -> impl Send + '_ {
1701 fn keys<T: Send + Sync>(v: &BTreeMap<T, T>) -> impl Send + '_ {
1705 fn values<T: Send + Sync>(v: &BTreeMap<T, T>) -> impl Send + '_ {
1709 fn values_mut<T: Send>(v: &mut BTreeMap<T, T>) -> impl Send + '_ {
1713 fn range<T: Send + Sync + Ord>(v: &BTreeMap<T, T>) -> impl Send + '_ {
1717 fn range_mut<T: Send + Ord>(v: &mut BTreeMap<T, T>) -> impl Send + '_ {
1721 fn entry<T: Send + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Send + '_ {
1722 v.entry(Default::default())
1725 fn occupied_entry<T: Send + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Send + '_ {
1726 match v.entry(Default::default()) {
1727 Occupied(entry) => entry,
1728 _ => unreachable!(),
1732 fn vacant_entry<T: Send + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Send + '_ {
1733 match v.entry(Default::default()) {
1734 Vacant(entry) => entry,
1735 _ => unreachable!(),
1741 fn test_ord_absence() {
1742 fn map<K>(mut map: BTreeMap<K, ()>) {
1743 let _ = map.is_empty();
1747 let _ = map.iter_mut();
1749 let _ = map.values();
1750 let _ = map.values_mut();
1752 let _ = map.into_values();
1754 let _ = map.into_iter();
1756 let _ = map.into_keys();
1760 fn map_debug<K: Debug>(mut map: BTreeMap<K, ()>) {
1761 format!("{:?}", map);
1762 format!("{:?}", map.iter());
1763 format!("{:?}", map.iter_mut());
1764 format!("{:?}", map.keys());
1765 format!("{:?}", map.values());
1766 format!("{:?}", map.values_mut());
1768 format!("{:?}", map.into_iter());
1770 format!("{:?}", map.into_keys());
1772 format!("{:?}", map.into_values());
1776 fn map_clone<K: Clone>(mut map: BTreeMap<K, ()>) {
1777 map.clone_from(&map.clone());
1780 #[derive(Debug, Clone)]
1782 map(BTreeMap::<NonOrd, _>::new());
1783 map_debug(BTreeMap::<NonOrd, _>::new());
1784 map_clone(BTreeMap::<NonOrd, _>::default());
1788 fn test_occupied_entry_key() {
1789 let mut a = BTreeMap::new();
1790 let key = "hello there";
1791 let value = "value goes here";
1792 assert!(a.is_empty());
1793 a.insert(key, value);
1794 assert_eq!(a.len(), 1);
1795 assert_eq!(a[key], value);
1797 match a.entry(key) {
1798 Vacant(_) => panic!(),
1799 Occupied(e) => assert_eq!(key, *e.key()),
1801 assert_eq!(a.len(), 1);
1802 assert_eq!(a[key], value);
1807 fn test_vacant_entry_key() {
1808 let mut a = BTreeMap::new();
1809 let key = "hello there";
1810 let value = "value goes here";
1812 assert!(a.is_empty());
1813 match a.entry(key) {
1814 Occupied(_) => panic!(),
1816 assert_eq!(key, *e.key());
1820 assert_eq!(a.len(), 1);
1821 assert_eq!(a[key], value);
1826 fn test_first_last_entry() {
1827 let mut a = BTreeMap::new();
1828 assert!(a.first_entry().is_none());
1829 assert!(a.last_entry().is_none());
1831 assert_eq!(a.first_entry().unwrap().key(), &1);
1832 assert_eq!(a.last_entry().unwrap().key(), &1);
1834 assert_eq!(a.first_entry().unwrap().key(), &1);
1835 assert_eq!(a.last_entry().unwrap().key(), &2);
1837 assert_eq!(a.first_entry().unwrap().key(), &0);
1838 assert_eq!(a.last_entry().unwrap().key(), &2);
1839 let (k1, v1) = a.first_entry().unwrap().remove_entry();
1842 let (k2, v2) = a.last_entry().unwrap().remove_entry();
1845 assert_eq!(a.first_entry().unwrap().key(), &1);
1846 assert_eq!(a.last_entry().unwrap().key(), &1);
1851 fn test_insert_into_full_height_0() {
1852 let size = node::CAPACITY;
1853 for pos in 0..=size {
1854 let mut map = BTreeMap::from_iter((0..size).map(|i| (i * 2 + 1, ())));
1855 assert!(map.insert(pos * 2, ()).is_none());
1861 fn test_insert_into_full_height_1() {
1862 let size = node::CAPACITY + 1 + node::CAPACITY;
1863 for pos in 0..=size {
1864 let mut map = BTreeMap::from_iter((0..size).map(|i| (i * 2 + 1, ())));
1866 let root_node = map.root.as_ref().unwrap().reborrow();
1867 assert_eq!(root_node.len(), 1);
1868 assert_eq!(root_node.first_leaf_edge().into_node().len(), node::CAPACITY);
1869 assert_eq!(root_node.last_leaf_edge().into_node().len(), node::CAPACITY);
1871 assert!(map.insert(pos * 2, ()).is_none());
1876 macro_rules! create_append_test {
1877 ($name:ident, $len:expr) => {
1880 let mut a = BTreeMap::new();
1885 let mut b = BTreeMap::new();
1892 assert_eq!(a.len(), $len);
1893 assert_eq!(b.len(), 0);
1897 assert_eq!(a[&i], i);
1899 assert_eq!(a[&i], 2 * i);
1904 assert_eq!(a.remove(&($len - 1)), Some(2 * ($len - 1)));
1905 assert_eq!(a.insert($len - 1, 20), None);
1911 // These are mostly for testing the algorithm that "fixes" the right edge after insertion.
1913 create_append_test!(test_append_9, 9);
1914 // Two leafs that don't need fixing.
1915 create_append_test!(test_append_17, 17);
1916 // Two leafs where the second one ends up underfull and needs stealing at the end.
1917 create_append_test!(test_append_14, 14);
1918 // Two leafs where the second one ends up empty because the insertion finished at the root.
1919 create_append_test!(test_append_12, 12);
1920 // Three levels; insertion finished at the root.
1921 create_append_test!(test_append_144, 144);
1922 // Three levels; insertion finished at leaf while there is an empty node on the second level.
1923 create_append_test!(test_append_145, 145);
1924 // Tests for several randomly chosen sizes.
1925 create_append_test!(test_append_170, 170);
1926 create_append_test!(test_append_181, 181);
1927 #[cfg(not(miri))] // Miri is too slow
1928 create_append_test!(test_append_239, 239);
1929 #[cfg(not(miri))] // Miri is too slow
1930 create_append_test!(test_append_1700, 1700);
1933 fn test_append_drop_leak() {
1934 let a = CrashTestDummy::new(0);
1935 let b = CrashTestDummy::new(1);
1936 let c = CrashTestDummy::new(2);
1937 let mut left = BTreeMap::new();
1938 let mut right = BTreeMap::new();
1939 left.insert(a.spawn(Panic::Never), ());
1940 left.insert(b.spawn(Panic::InDrop), ()); // first duplicate key, dropped during append
1941 left.insert(c.spawn(Panic::Never), ());
1942 right.insert(b.spawn(Panic::Never), ());
1943 right.insert(c.spawn(Panic::Never), ());
1945 catch_unwind(move || left.append(&mut right)).unwrap_err();
1946 assert_eq!(a.dropped(), 1);
1947 assert_eq!(b.dropped(), 1); // should be 2 were it not for Rust issue #47949
1948 assert_eq!(c.dropped(), 2);
1952 fn test_append_ord_chaos() {
1953 let mut map1 = BTreeMap::new();
1954 map1.insert(Cyclic3::A, ());
1955 map1.insert(Cyclic3::B, ());
1956 let mut map2 = BTreeMap::new();
1957 map2.insert(Cyclic3::A, ());
1958 map2.insert(Cyclic3::B, ());
1959 map2.insert(Cyclic3::C, ()); // lands first, before A
1960 map2.insert(Cyclic3::B, ()); // lands first, before C
1962 map2.check(); // keys are not unique but still strictly ascending
1963 assert_eq!(map1.len(), 2);
1964 assert_eq!(map2.len(), 4);
1965 map1.append(&mut map2);
1966 assert_eq!(map1.len(), 5);
1967 assert_eq!(map2.len(), 0);
1972 fn rand_data(len: usize) -> Vec<(u32, u32)> {
1973 let mut rng = DeterministicRng::new();
1974 Vec::from_iter((0..len).map(|_| (rng.next(), rng.next())))
1978 fn test_split_off_empty_right() {
1979 let mut data = rand_data(173);
1981 let mut map = BTreeMap::from_iter(data.clone());
1982 let right = map.split_off(&(data.iter().max().unwrap().0 + 1));
1987 assert!(map.into_iter().eq(data));
1988 assert!(right.into_iter().eq(None));
1992 fn test_split_off_empty_left() {
1993 let mut data = rand_data(314);
1995 let mut map = BTreeMap::from_iter(data.clone());
1996 let right = map.split_off(&data.iter().min().unwrap().0);
2001 assert!(map.into_iter().eq(None));
2002 assert!(right.into_iter().eq(data));
2005 // In a tree with 3 levels, if all but a part of the first leaf node is split off,
2006 // make sure fix_top eliminates both top levels.
2008 fn test_split_off_tiny_left_height_2() {
2009 let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
2010 let mut left = BTreeMap::from_iter(pairs.clone());
2011 let right = left.split_off(&1);
2014 assert_eq!(left.len(), 1);
2015 assert_eq!(right.len(), MIN_INSERTS_HEIGHT_2 - 1);
2016 assert_eq!(*left.first_key_value().unwrap().0, 0);
2017 assert_eq!(*right.first_key_value().unwrap().0, 1);
2020 // In a tree with 3 levels, if only part of the last leaf node is split off,
2021 // make sure fix_top eliminates both top levels.
2023 fn test_split_off_tiny_right_height_2() {
2024 let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
2025 let last = MIN_INSERTS_HEIGHT_2 - 1;
2026 let mut left = BTreeMap::from_iter(pairs.clone());
2027 assert_eq!(*left.last_key_value().unwrap().0, last);
2028 let right = left.split_off(&last);
2031 assert_eq!(left.len(), MIN_INSERTS_HEIGHT_2 - 1);
2032 assert_eq!(right.len(), 1);
2033 assert_eq!(*left.last_key_value().unwrap().0, last - 1);
2034 assert_eq!(*right.last_key_value().unwrap().0, last);
2038 fn test_split_off_halfway() {
2039 let mut rng = DeterministicRng::new();
2040 for &len in &[node::CAPACITY, 25, 50, 75, 100] {
2041 let mut data = Vec::from_iter((0..len).map(|_| (rng.next(), ())));
2042 // Insertion in non-ascending order creates some variation in node length.
2043 let mut map = BTreeMap::from_iter(data.iter().copied());
2045 let small_keys = data.iter().take(len / 2).map(|kv| kv.0);
2046 let large_keys = data.iter().skip(len / 2).map(|kv| kv.0);
2047 let split_key = large_keys.clone().next().unwrap();
2048 let right = map.split_off(&split_key);
2051 assert!(map.keys().copied().eq(small_keys));
2052 assert!(right.keys().copied().eq(large_keys));
2057 fn test_split_off_large_random_sorted() {
2059 let mut data = if cfg!(miri) { rand_data(529) } else { rand_data(1529) };
2060 // special case with maximum height.
2063 let mut map = BTreeMap::from_iter(data.clone());
2064 let key = data[data.len() / 2].0;
2065 let right = map.split_off(&key);
2069 assert!(map.into_iter().eq(data.clone().into_iter().filter(|x| x.0 < key)));
2070 assert!(right.into_iter().eq(data.into_iter().filter(|x| x.0 >= key)));
2074 fn test_into_iter_drop_leak_height_0() {
2075 let a = CrashTestDummy::new(0);
2076 let b = CrashTestDummy::new(1);
2077 let c = CrashTestDummy::new(2);
2078 let d = CrashTestDummy::new(3);
2079 let e = CrashTestDummy::new(4);
2080 let mut map = BTreeMap::new();
2081 map.insert("a", a.spawn(Panic::Never));
2082 map.insert("b", b.spawn(Panic::Never));
2083 map.insert("c", c.spawn(Panic::Never));
2084 map.insert("d", d.spawn(Panic::InDrop));
2085 map.insert("e", e.spawn(Panic::Never));
2087 catch_unwind(move || drop(map.into_iter())).unwrap_err();
2089 assert_eq!(a.dropped(), 1);
2090 assert_eq!(b.dropped(), 1);
2091 assert_eq!(c.dropped(), 1);
2092 assert_eq!(d.dropped(), 1);
2093 assert_eq!(e.dropped(), 1);
2097 fn test_into_iter_drop_leak_height_1() {
2098 let size = MIN_INSERTS_HEIGHT_1;
2099 for panic_point in vec![0, 1, size - 2, size - 1] {
2100 let dummies = Vec::from_iter((0..size).map(|i| CrashTestDummy::new(i)));
2101 let map = BTreeMap::from_iter((0..size).map(|i| {
2102 let panic = if i == panic_point { Panic::InDrop } else { Panic::Never };
2103 (dummies[i].spawn(Panic::Never), dummies[i].spawn(panic))
2105 catch_unwind(move || drop(map.into_iter())).unwrap_err();
2107 assert_eq!(dummies[i].dropped(), 2);
2113 fn test_into_keys() {
2114 let map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
2115 let keys = Vec::from_iter(map.into_keys());
2117 assert_eq!(keys.len(), 3);
2118 assert!(keys.contains(&1));
2119 assert!(keys.contains(&2));
2120 assert!(keys.contains(&3));
2124 fn test_into_values() {
2125 let map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
2126 let values = Vec::from_iter(map.into_values());
2128 assert_eq!(values.len(), 3);
2129 assert!(values.contains(&'a'));
2130 assert!(values.contains(&'b'));
2131 assert!(values.contains(&'c'));
2135 fn test_insert_remove_intertwined() {
2136 let loops = if cfg!(miri) { 100 } else { 1_000_000 };
2137 let mut map = BTreeMap::new();
2139 let offset = 165; // somewhat arbitrarily chosen to cover some code paths
2141 i = (i + offset) & 0xFF;
2143 map.remove(&(0xFF - i));
2149 fn test_insert_remove_intertwined_ord_chaos() {
2150 let loops = if cfg!(miri) { 100 } else { 1_000_000 };
2151 let gov = Governor::new();
2152 let mut map = BTreeMap::new();
2154 let offset = 165; // more arbitrarily copied from above
2156 i = (i + offset) & 0xFF;
2157 map.insert(Governed(i, &gov), ());
2158 map.remove(&Governed(0xFF - i, &gov));
2161 map.check_invariants();
2166 let map = BTreeMap::from([(1, 2), (3, 4)]);
2167 let unordered_duplicates = BTreeMap::from([(3, 4), (1, 2), (1, 2)]);
2168 assert_eq!(map, unordered_duplicates);