]> git.proxmox.com Git - rustc.git/blob - library/alloc/src/collections/btree/map/tests.rs
New upstream version 1.52.0~beta.3+dfsg1
[rustc.git] / library / alloc / src / collections / btree / map / tests.rs
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};
5 use super::*;
6 use crate::boxed::Box;
7 use crate::fmt::Debug;
8 use crate::rc::Rc;
9 use crate::string::{String, ToString};
10 use crate::vec::Vec;
11 use std::cmp::Ordering;
12 use std::convert::TryFrom;
13 use std::iter::{self, FromIterator};
14 use std::mem;
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};
19
20 // Capacity of a tree with a single level,
21 // i.e., a tree who's root is a leaf node at height 0.
22 const NODE_CAPACITY: usize = node::CAPACITY;
23
24 // Minimum number of elements to insert, to guarantee a tree with 2 levels,
25 // i.e., a tree who's root is an internal node at height 1, with edges to leaf 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_1: usize = NODE_CAPACITY + 1;
28
29 // Minimum number of elements to insert in ascending order, to guarantee a tree with 3 levels,
30 // i.e., a tree who's root is an internal node at height 2, with edges to more internal nodes.
31 // It's not the minimum size: removing an element from such a tree does not always reduce height.
32 const MIN_INSERTS_HEIGHT_2: usize = 89;
33
34 // Gathers all references from a mutable iterator and makes sure Miri notices if
35 // using them is dangerous.
36 fn test_all_refs<'a, T: 'a>(dummy: &mut T, iter: impl Iterator<Item = &'a mut T>) {
37 // Gather all those references.
38 let mut refs: Vec<&mut T> = iter.collect();
39 // Use them all. Twice, to be sure we got all interleavings.
40 for r in refs.iter_mut() {
41 mem::swap(dummy, r);
42 }
43 for r in refs {
44 mem::swap(dummy, r);
45 }
46 }
47
48 impl<K, V> BTreeMap<K, V> {
49 // Panics if the map (or the code navigating it) is corrupted.
50 fn check_invariants(&self) {
51 if let Some(root) = &self.root {
52 let root_node = root.reborrow();
53
54 // Check the back pointers top-down, before we attempt to rely on
55 // more serious navigation code.
56 assert!(root_node.ascend().is_err());
57 root_node.assert_back_pointers();
58
59 // Check consistency of `length` with what navigation code encounters.
60 assert_eq!(self.length, root_node.calc_length());
61
62 // Lastly, check the invariant causing the least harm.
63 root_node.assert_min_len(if root_node.height() > 0 { 1 } else { 0 });
64 } else {
65 assert_eq!(self.length, 0);
66 }
67
68 // Check that `assert_strictly_ascending` will encounter all keys.
69 assert_eq!(self.length, self.keys().count());
70 }
71
72 // Panics if the map is corrupted or if the keys are not in strictly
73 // ascending order, in the current opinion of the `Ord` implementation.
74 // If the `Ord` implementation violates transitivity, this method does not
75 // guarantee that all keys are unique, just that adjacent keys are unique.
76 fn check(&self)
77 where
78 K: Debug + Ord,
79 {
80 self.check_invariants();
81 self.assert_strictly_ascending();
82 }
83
84 // Returns the height of the root, if any.
85 fn height(&self) -> Option<usize> {
86 self.root.as_ref().map(node::Root::height)
87 }
88
89 fn dump_keys(&self) -> String
90 where
91 K: Debug,
92 {
93 if let Some(root) = self.root.as_ref() {
94 root.reborrow().dump_keys()
95 } else {
96 String::from("not yet allocated")
97 }
98 }
99
100 // Panics if the keys are not in strictly ascending order.
101 fn assert_strictly_ascending(&self)
102 where
103 K: Debug + Ord,
104 {
105 let mut keys = self.keys();
106 if let Some(mut previous) = keys.next() {
107 for next in keys {
108 assert!(previous < next, "{:?} >= {:?}", previous, next);
109 previous = next;
110 }
111 }
112 }
113
114 // Transform the tree to minimize wasted space, obtaining fewer nodes that
115 // are mostly filled up to their capacity. The same compact tree could have
116 // been obtained by inserting keys in a shrewd order.
117 fn compact(&mut self)
118 where
119 K: Ord,
120 {
121 let iter = mem::take(self).into_iter();
122 let root = BTreeMap::ensure_is_owned(&mut self.root);
123 root.bulk_push(iter, &mut self.length);
124 }
125 }
126
127 impl<'a, K: 'a, V: 'a> NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal> {
128 fn assert_min_len(self, min_len: usize) {
129 assert!(self.len() >= min_len, "node len {} < {}", self.len(), min_len);
130 if let node::ForceResult::Internal(node) = self.force() {
131 for idx in 0..=node.len() {
132 let edge = unsafe { Handle::new_edge(node, idx) };
133 edge.descend().assert_min_len(MIN_LEN);
134 }
135 }
136 }
137 }
138
139 // Tests our value of MIN_INSERTS_HEIGHT_2. Failure may mean you just need to
140 // adapt that value to match a change in node::CAPACITY or the choices made
141 // during insertion, otherwise other test cases may fail or be less useful.
142 #[test]
143 fn test_levels() {
144 let mut map = BTreeMap::new();
145 map.check();
146 assert_eq!(map.height(), None);
147 assert_eq!(map.len(), 0);
148
149 map.insert(0, ());
150 while map.height() == Some(0) {
151 let last_key = *map.last_key_value().unwrap().0;
152 map.insert(last_key + 1, ());
153 }
154 map.check();
155 // Structure:
156 // - 1 element in internal root node with 2 children
157 // - 6 elements in left leaf child
158 // - 5 elements in right leaf child
159 assert_eq!(map.height(), Some(1));
160 assert_eq!(map.len(), MIN_INSERTS_HEIGHT_1, "{}", map.dump_keys());
161
162 while map.height() == Some(1) {
163 let last_key = *map.last_key_value().unwrap().0;
164 map.insert(last_key + 1, ());
165 }
166 map.check();
167 // Structure:
168 // - 1 element in internal root node with 2 children
169 // - 6 elements in left internal child with 7 grandchildren
170 // - 42 elements in left child's 7 grandchildren with 6 elements each
171 // - 5 elements in right internal child with 6 grandchildren
172 // - 30 elements in right child's 5 first grandchildren with 6 elements each
173 // - 5 elements in right child's last grandchild
174 assert_eq!(map.height(), Some(2));
175 assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2, "{}", map.dump_keys());
176 }
177
178 // Ensures the testing infrastructure usually notices order violations.
179 #[test]
180 #[should_panic]
181 fn test_check_ord_chaos() {
182 let gov = Governor::new();
183 let map: BTreeMap<_, _> = (0..2).map(|i| (Governed(i, &gov), ())).collect();
184 gov.flip();
185 map.check();
186 }
187
188 // Ensures the testing infrastructure doesn't always mind order violations.
189 #[test]
190 fn test_check_invariants_ord_chaos() {
191 let gov = Governor::new();
192 let map: BTreeMap<_, _> = (0..2).map(|i| (Governed(i, &gov), ())).collect();
193 gov.flip();
194 map.check_invariants();
195 }
196
197 #[test]
198 fn test_basic_large() {
199 let mut map = BTreeMap::new();
200 // Miri is too slow
201 let size = if cfg!(miri) { MIN_INSERTS_HEIGHT_2 } else { 10000 };
202 let size = size + (size % 2); // round up to even number
203 assert_eq!(map.len(), 0);
204
205 for i in 0..size {
206 assert_eq!(map.insert(i, 10 * i), None);
207 assert_eq!(map.len(), i + 1);
208 }
209
210 assert_eq!(map.first_key_value(), Some((&0, &0)));
211 assert_eq!(map.last_key_value(), Some((&(size - 1), &(10 * (size - 1)))));
212 assert_eq!(map.first_entry().unwrap().key(), &0);
213 assert_eq!(map.last_entry().unwrap().key(), &(size - 1));
214
215 for i in 0..size {
216 assert_eq!(map.get(&i).unwrap(), &(i * 10));
217 }
218
219 for i in size..size * 2 {
220 assert_eq!(map.get(&i), None);
221 }
222
223 for i in 0..size {
224 assert_eq!(map.insert(i, 100 * i), Some(10 * i));
225 assert_eq!(map.len(), size);
226 }
227
228 for i in 0..size {
229 assert_eq!(map.get(&i).unwrap(), &(i * 100));
230 }
231
232 for i in 0..size / 2 {
233 assert_eq!(map.remove(&(i * 2)), Some(i * 200));
234 assert_eq!(map.len(), size - i - 1);
235 }
236
237 for i in 0..size / 2 {
238 assert_eq!(map.get(&(2 * i)), None);
239 assert_eq!(map.get(&(2 * i + 1)).unwrap(), &(i * 200 + 100));
240 }
241
242 for i in 0..size / 2 {
243 assert_eq!(map.remove(&(2 * i)), None);
244 assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
245 assert_eq!(map.len(), size / 2 - i - 1);
246 }
247 map.check();
248 }
249
250 #[test]
251 fn test_basic_small() {
252 let mut map = BTreeMap::new();
253 // Empty, root is absent (None):
254 assert_eq!(map.remove(&1), None);
255 assert_eq!(map.len(), 0);
256 assert_eq!(map.get(&1), None);
257 assert_eq!(map.get_mut(&1), None);
258 assert_eq!(map.first_key_value(), None);
259 assert_eq!(map.last_key_value(), None);
260 assert_eq!(map.keys().count(), 0);
261 assert_eq!(map.values().count(), 0);
262 assert_eq!(map.range(..).next(), None);
263 assert_eq!(map.range(..1).next(), None);
264 assert_eq!(map.range(1..).next(), None);
265 assert_eq!(map.range(1..=1).next(), None);
266 assert_eq!(map.range(1..2).next(), None);
267 assert_eq!(map.height(), None);
268 assert_eq!(map.insert(1, 1), None);
269 assert_eq!(map.height(), Some(0));
270 map.check();
271
272 // 1 key-value pair:
273 assert_eq!(map.len(), 1);
274 assert_eq!(map.get(&1), Some(&1));
275 assert_eq!(map.get_mut(&1), Some(&mut 1));
276 assert_eq!(map.first_key_value(), Some((&1, &1)));
277 assert_eq!(map.last_key_value(), Some((&1, &1)));
278 assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1]);
279 assert_eq!(map.values().collect::<Vec<_>>(), vec![&1]);
280 assert_eq!(map.insert(1, 2), Some(1));
281 assert_eq!(map.len(), 1);
282 assert_eq!(map.get(&1), Some(&2));
283 assert_eq!(map.get_mut(&1), Some(&mut 2));
284 assert_eq!(map.first_key_value(), Some((&1, &2)));
285 assert_eq!(map.last_key_value(), Some((&1, &2)));
286 assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1]);
287 assert_eq!(map.values().collect::<Vec<_>>(), vec![&2]);
288 assert_eq!(map.insert(2, 4), None);
289 assert_eq!(map.height(), Some(0));
290 map.check();
291
292 // 2 key-value pairs:
293 assert_eq!(map.len(), 2);
294 assert_eq!(map.get(&2), Some(&4));
295 assert_eq!(map.get_mut(&2), Some(&mut 4));
296 assert_eq!(map.first_key_value(), Some((&1, &2)));
297 assert_eq!(map.last_key_value(), Some((&2, &4)));
298 assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1, &2]);
299 assert_eq!(map.values().collect::<Vec<_>>(), vec![&2, &4]);
300 assert_eq!(map.remove(&1), Some(2));
301 assert_eq!(map.height(), Some(0));
302 map.check();
303
304 // 1 key-value pair:
305 assert_eq!(map.len(), 1);
306 assert_eq!(map.get(&1), None);
307 assert_eq!(map.get_mut(&1), None);
308 assert_eq!(map.get(&2), Some(&4));
309 assert_eq!(map.get_mut(&2), Some(&mut 4));
310 assert_eq!(map.first_key_value(), Some((&2, &4)));
311 assert_eq!(map.last_key_value(), Some((&2, &4)));
312 assert_eq!(map.keys().collect::<Vec<_>>(), vec![&2]);
313 assert_eq!(map.values().collect::<Vec<_>>(), vec![&4]);
314 assert_eq!(map.remove(&2), Some(4));
315 assert_eq!(map.height(), Some(0));
316 map.check();
317
318 // Empty but root is owned (Some(...)):
319 assert_eq!(map.len(), 0);
320 assert_eq!(map.get(&1), None);
321 assert_eq!(map.get_mut(&1), None);
322 assert_eq!(map.first_key_value(), None);
323 assert_eq!(map.last_key_value(), None);
324 assert_eq!(map.keys().count(), 0);
325 assert_eq!(map.values().count(), 0);
326 assert_eq!(map.range(..).next(), None);
327 assert_eq!(map.range(..1).next(), None);
328 assert_eq!(map.range(1..).next(), None);
329 assert_eq!(map.range(1..=1).next(), None);
330 assert_eq!(map.range(1..2).next(), None);
331 assert_eq!(map.remove(&1), None);
332 assert_eq!(map.height(), Some(0));
333 map.check();
334 }
335
336 #[test]
337 fn test_iter() {
338 // Miri is too slow
339 let size = if cfg!(miri) { 200 } else { 10000 };
340
341 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
342
343 fn test<T>(size: usize, mut iter: T)
344 where
345 T: Iterator<Item = (usize, usize)>,
346 {
347 for i in 0..size {
348 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
349 assert_eq!(iter.next().unwrap(), (i, i));
350 }
351 assert_eq!(iter.size_hint(), (0, Some(0)));
352 assert_eq!(iter.next(), None);
353 }
354 test(size, map.iter().map(|(&k, &v)| (k, v)));
355 test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
356 test(size, map.into_iter());
357 }
358
359 #[test]
360 fn test_iter_rev() {
361 // Miri is too slow
362 let size = if cfg!(miri) { 200 } else { 10000 };
363
364 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
365
366 fn test<T>(size: usize, mut iter: T)
367 where
368 T: Iterator<Item = (usize, usize)>,
369 {
370 for i in 0..size {
371 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
372 assert_eq!(iter.next().unwrap(), (size - i - 1, size - i - 1));
373 }
374 assert_eq!(iter.size_hint(), (0, Some(0)));
375 assert_eq!(iter.next(), None);
376 }
377 test(size, map.iter().rev().map(|(&k, &v)| (k, v)));
378 test(size, map.iter_mut().rev().map(|(&k, &mut v)| (k, v)));
379 test(size, map.into_iter().rev());
380 }
381
382 // Specifically tests iter_mut's ability to mutate the value of pairs in-line.
383 fn do_test_iter_mut_mutation<T>(size: usize)
384 where
385 T: Copy + Debug + Ord + TryFrom<usize>,
386 <T as TryFrom<usize>>::Error: Debug,
387 {
388 let zero = T::try_from(0).unwrap();
389 let mut map: BTreeMap<T, T> = (0..size).map(|i| (T::try_from(i).unwrap(), zero)).collect();
390
391 // Forward and backward iteration sees enough pairs (also tested elsewhere)
392 assert_eq!(map.iter_mut().count(), size);
393 assert_eq!(map.iter_mut().rev().count(), size);
394
395 // Iterate forwards, trying to mutate to unique values
396 for (i, (k, v)) in map.iter_mut().enumerate() {
397 assert_eq!(*k, T::try_from(i).unwrap());
398 assert_eq!(*v, zero);
399 *v = T::try_from(i + 1).unwrap();
400 }
401
402 // Iterate backwards, checking that mutations succeeded and trying to mutate again
403 for (i, (k, v)) in map.iter_mut().rev().enumerate() {
404 assert_eq!(*k, T::try_from(size - i - 1).unwrap());
405 assert_eq!(*v, T::try_from(size - i).unwrap());
406 *v = T::try_from(2 * size - i).unwrap();
407 }
408
409 // Check that backward mutations succeeded
410 for (i, (k, v)) in map.iter_mut().enumerate() {
411 assert_eq!(*k, T::try_from(i).unwrap());
412 assert_eq!(*v, T::try_from(size + i + 1).unwrap());
413 }
414 map.check();
415 }
416
417 #[derive(Clone, Copy, Debug, Eq, PartialEq, PartialOrd, Ord)]
418 #[repr(align(32))]
419 struct Align32(usize);
420
421 impl TryFrom<usize> for Align32 {
422 type Error = ();
423
424 fn try_from(s: usize) -> Result<Align32, ()> {
425 Ok(Align32(s))
426 }
427 }
428
429 #[test]
430 fn test_iter_mut_mutation() {
431 // Check many alignments and trees with roots at various heights.
432 do_test_iter_mut_mutation::<u8>(0);
433 do_test_iter_mut_mutation::<u8>(1);
434 do_test_iter_mut_mutation::<u8>(MIN_INSERTS_HEIGHT_1);
435 do_test_iter_mut_mutation::<u8>(MIN_INSERTS_HEIGHT_2);
436 do_test_iter_mut_mutation::<u16>(1);
437 do_test_iter_mut_mutation::<u16>(MIN_INSERTS_HEIGHT_1);
438 do_test_iter_mut_mutation::<u16>(MIN_INSERTS_HEIGHT_2);
439 do_test_iter_mut_mutation::<u32>(1);
440 do_test_iter_mut_mutation::<u32>(MIN_INSERTS_HEIGHT_1);
441 do_test_iter_mut_mutation::<u32>(MIN_INSERTS_HEIGHT_2);
442 do_test_iter_mut_mutation::<u64>(1);
443 do_test_iter_mut_mutation::<u64>(MIN_INSERTS_HEIGHT_1);
444 do_test_iter_mut_mutation::<u64>(MIN_INSERTS_HEIGHT_2);
445 do_test_iter_mut_mutation::<u128>(1);
446 do_test_iter_mut_mutation::<u128>(MIN_INSERTS_HEIGHT_1);
447 do_test_iter_mut_mutation::<u128>(MIN_INSERTS_HEIGHT_2);
448 do_test_iter_mut_mutation::<Align32>(1);
449 do_test_iter_mut_mutation::<Align32>(MIN_INSERTS_HEIGHT_1);
450 do_test_iter_mut_mutation::<Align32>(MIN_INSERTS_HEIGHT_2);
451 }
452
453 #[test]
454 fn test_values_mut() {
455 let mut a: BTreeMap<_, _> = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)).collect();
456 test_all_refs(&mut 13, a.values_mut());
457 a.check();
458 }
459
460 #[test]
461 fn test_values_mut_mutation() {
462 let mut a = BTreeMap::new();
463 a.insert(1, String::from("hello"));
464 a.insert(2, String::from("goodbye"));
465
466 for value in a.values_mut() {
467 value.push_str("!");
468 }
469
470 let values: Vec<String> = a.values().cloned().collect();
471 assert_eq!(values, [String::from("hello!"), String::from("goodbye!")]);
472 a.check();
473 }
474
475 #[test]
476 fn test_iter_entering_root_twice() {
477 let mut map: BTreeMap<_, _> = (0..2).map(|i| (i, i)).collect();
478 let mut it = map.iter_mut();
479 let front = it.next().unwrap();
480 let back = it.next_back().unwrap();
481 assert_eq!(front, (&0, &mut 0));
482 assert_eq!(back, (&1, &mut 1));
483 *front.1 = 24;
484 *back.1 = 42;
485 assert_eq!(front, (&0, &mut 24));
486 assert_eq!(back, (&1, &mut 42));
487 assert_eq!(it.next(), None);
488 assert_eq!(it.next_back(), None);
489 map.check();
490 }
491
492 #[test]
493 fn test_iter_descending_to_same_node_twice() {
494 let mut map: BTreeMap<_, _> = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i)).collect();
495 let mut it = map.iter_mut();
496 // Descend into first child.
497 let front = it.next().unwrap();
498 // Descend into first child again, after running through second child.
499 while it.next_back().is_some() {}
500 // Check immutable access.
501 assert_eq!(front, (&0, &mut 0));
502 // Perform mutable access.
503 *front.1 = 42;
504 map.check();
505 }
506
507 #[test]
508 fn test_iter_mixed() {
509 // Miri is too slow
510 let size = if cfg!(miri) { 200 } else { 10000 };
511
512 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
513
514 fn test<T>(size: usize, mut iter: T)
515 where
516 T: Iterator<Item = (usize, usize)> + DoubleEndedIterator,
517 {
518 for i in 0..size / 4 {
519 assert_eq!(iter.size_hint(), (size - i * 2, Some(size - i * 2)));
520 assert_eq!(iter.next().unwrap(), (i, i));
521 assert_eq!(iter.next_back().unwrap(), (size - i - 1, size - i - 1));
522 }
523 for i in size / 4..size * 3 / 4 {
524 assert_eq!(iter.size_hint(), (size * 3 / 4 - i, Some(size * 3 / 4 - i)));
525 assert_eq!(iter.next().unwrap(), (i, i));
526 }
527 assert_eq!(iter.size_hint(), (0, Some(0)));
528 assert_eq!(iter.next(), None);
529 }
530 test(size, map.iter().map(|(&k, &v)| (k, v)));
531 test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
532 test(size, map.into_iter());
533 }
534
535 #[test]
536 fn test_iter_min_max() {
537 let mut a = BTreeMap::new();
538 assert_eq!(a.iter().min(), None);
539 assert_eq!(a.iter().max(), None);
540 assert_eq!(a.iter_mut().min(), None);
541 assert_eq!(a.iter_mut().max(), None);
542 assert_eq!(a.range(..).min(), None);
543 assert_eq!(a.range(..).max(), None);
544 assert_eq!(a.range_mut(..).min(), None);
545 assert_eq!(a.range_mut(..).max(), None);
546 assert_eq!(a.keys().min(), None);
547 assert_eq!(a.keys().max(), None);
548 assert_eq!(a.values().min(), None);
549 assert_eq!(a.values().max(), None);
550 assert_eq!(a.values_mut().min(), None);
551 assert_eq!(a.values_mut().max(), None);
552 a.insert(1, 42);
553 a.insert(2, 24);
554 assert_eq!(a.iter().min(), Some((&1, &42)));
555 assert_eq!(a.iter().max(), Some((&2, &24)));
556 assert_eq!(a.iter_mut().min(), Some((&1, &mut 42)));
557 assert_eq!(a.iter_mut().max(), Some((&2, &mut 24)));
558 assert_eq!(a.range(..).min(), Some((&1, &42)));
559 assert_eq!(a.range(..).max(), Some((&2, &24)));
560 assert_eq!(a.range_mut(..).min(), Some((&1, &mut 42)));
561 assert_eq!(a.range_mut(..).max(), Some((&2, &mut 24)));
562 assert_eq!(a.keys().min(), Some(&1));
563 assert_eq!(a.keys().max(), Some(&2));
564 assert_eq!(a.values().min(), Some(&24));
565 assert_eq!(a.values().max(), Some(&42));
566 assert_eq!(a.values_mut().min(), Some(&mut 24));
567 assert_eq!(a.values_mut().max(), Some(&mut 42));
568 a.check();
569 }
570
571 fn range_keys(map: &BTreeMap<i32, i32>, range: impl RangeBounds<i32>) -> Vec<i32> {
572 map.range(range)
573 .map(|(&k, &v)| {
574 assert_eq!(k, v);
575 k
576 })
577 .collect()
578 }
579
580 #[test]
581 fn test_range_small() {
582 let size = 4;
583
584 let map: BTreeMap<_, _> = (1..=size).map(|i| (i, i)).collect();
585 let all: Vec<_> = (1..=size).collect();
586 let (first, last) = (vec![all[0]], vec![all[size as usize - 1]]);
587
588 assert_eq!(range_keys(&map, (Excluded(0), Excluded(size + 1))), all);
589 assert_eq!(range_keys(&map, (Excluded(0), Included(size + 1))), all);
590 assert_eq!(range_keys(&map, (Excluded(0), Included(size))), all);
591 assert_eq!(range_keys(&map, (Excluded(0), Unbounded)), all);
592 assert_eq!(range_keys(&map, (Included(0), Excluded(size + 1))), all);
593 assert_eq!(range_keys(&map, (Included(0), Included(size + 1))), all);
594 assert_eq!(range_keys(&map, (Included(0), Included(size))), all);
595 assert_eq!(range_keys(&map, (Included(0), Unbounded)), all);
596 assert_eq!(range_keys(&map, (Included(1), Excluded(size + 1))), all);
597 assert_eq!(range_keys(&map, (Included(1), Included(size + 1))), all);
598 assert_eq!(range_keys(&map, (Included(1), Included(size))), all);
599 assert_eq!(range_keys(&map, (Included(1), Unbounded)), all);
600 assert_eq!(range_keys(&map, (Unbounded, Excluded(size + 1))), all);
601 assert_eq!(range_keys(&map, (Unbounded, Included(size + 1))), all);
602 assert_eq!(range_keys(&map, (Unbounded, Included(size))), all);
603 assert_eq!(range_keys(&map, ..), all);
604
605 assert_eq!(range_keys(&map, (Excluded(0), Excluded(1))), vec![]);
606 assert_eq!(range_keys(&map, (Excluded(0), Included(0))), vec![]);
607 assert_eq!(range_keys(&map, (Included(0), Included(0))), vec![]);
608 assert_eq!(range_keys(&map, (Included(0), Excluded(1))), vec![]);
609 assert_eq!(range_keys(&map, (Unbounded, Excluded(1))), vec![]);
610 assert_eq!(range_keys(&map, (Unbounded, Included(0))), vec![]);
611 assert_eq!(range_keys(&map, (Excluded(0), Excluded(2))), first);
612 assert_eq!(range_keys(&map, (Excluded(0), Included(1))), first);
613 assert_eq!(range_keys(&map, (Included(0), Excluded(2))), first);
614 assert_eq!(range_keys(&map, (Included(0), Included(1))), first);
615 assert_eq!(range_keys(&map, (Included(1), Excluded(2))), first);
616 assert_eq!(range_keys(&map, (Included(1), Included(1))), first);
617 assert_eq!(range_keys(&map, (Unbounded, Excluded(2))), first);
618 assert_eq!(range_keys(&map, (Unbounded, Included(1))), first);
619 assert_eq!(range_keys(&map, (Excluded(size - 1), Excluded(size + 1))), last);
620 assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size + 1))), last);
621 assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size))), last);
622 assert_eq!(range_keys(&map, (Excluded(size - 1), Unbounded)), last);
623 assert_eq!(range_keys(&map, (Included(size), Excluded(size + 1))), last);
624 assert_eq!(range_keys(&map, (Included(size), Included(size + 1))), last);
625 assert_eq!(range_keys(&map, (Included(size), Included(size))), last);
626 assert_eq!(range_keys(&map, (Included(size), Unbounded)), last);
627 assert_eq!(range_keys(&map, (Excluded(size), Excluded(size + 1))), vec![]);
628 assert_eq!(range_keys(&map, (Excluded(size), Included(size))), vec![]);
629 assert_eq!(range_keys(&map, (Excluded(size), Unbounded)), vec![]);
630 assert_eq!(range_keys(&map, (Included(size + 1), Excluded(size + 1))), vec![]);
631 assert_eq!(range_keys(&map, (Included(size + 1), Included(size + 1))), vec![]);
632 assert_eq!(range_keys(&map, (Included(size + 1), Unbounded)), vec![]);
633
634 assert_eq!(range_keys(&map, ..3), vec![1, 2]);
635 assert_eq!(range_keys(&map, 3..), vec![3, 4]);
636 assert_eq!(range_keys(&map, 2..=3), vec![2, 3]);
637 }
638
639 #[test]
640 fn test_range_height_1() {
641 // Tests tree with a root and 2 leaves. The single key in the root node is
642 // close to the middle among the keys.
643
644 let map: BTreeMap<_, _> = (0..MIN_INSERTS_HEIGHT_1 as i32).map(|i| (i, i)).collect();
645 let middle = MIN_INSERTS_HEIGHT_1 as i32 / 2;
646 for root in middle - 2..=middle + 2 {
647 assert_eq!(range_keys(&map, (Excluded(root), Excluded(root + 1))), vec![]);
648 assert_eq!(range_keys(&map, (Excluded(root), Included(root + 1))), vec![root + 1]);
649 assert_eq!(range_keys(&map, (Included(root), Excluded(root + 1))), vec![root]);
650 assert_eq!(range_keys(&map, (Included(root), Included(root + 1))), vec![root, root + 1]);
651
652 assert_eq!(range_keys(&map, (Excluded(root - 1), Excluded(root))), vec![]);
653 assert_eq!(range_keys(&map, (Included(root - 1), Excluded(root))), vec![root - 1]);
654 assert_eq!(range_keys(&map, (Excluded(root - 1), Included(root))), vec![root]);
655 assert_eq!(range_keys(&map, (Included(root - 1), Included(root))), vec![root - 1, root]);
656 }
657 }
658
659 #[test]
660 fn test_range_large() {
661 let size = 200;
662
663 let map: BTreeMap<_, _> = (1..=size).map(|i| (i, i)).collect();
664 let all: Vec<_> = (1..=size).collect();
665 let (first, last) = (vec![all[0]], vec![all[size as usize - 1]]);
666
667 assert_eq!(range_keys(&map, (Excluded(0), Excluded(size + 1))), all);
668 assert_eq!(range_keys(&map, (Excluded(0), Included(size + 1))), all);
669 assert_eq!(range_keys(&map, (Excluded(0), Included(size))), all);
670 assert_eq!(range_keys(&map, (Excluded(0), Unbounded)), all);
671 assert_eq!(range_keys(&map, (Included(0), Excluded(size + 1))), all);
672 assert_eq!(range_keys(&map, (Included(0), Included(size + 1))), all);
673 assert_eq!(range_keys(&map, (Included(0), Included(size))), all);
674 assert_eq!(range_keys(&map, (Included(0), Unbounded)), all);
675 assert_eq!(range_keys(&map, (Included(1), Excluded(size + 1))), all);
676 assert_eq!(range_keys(&map, (Included(1), Included(size + 1))), all);
677 assert_eq!(range_keys(&map, (Included(1), Included(size))), all);
678 assert_eq!(range_keys(&map, (Included(1), Unbounded)), all);
679 assert_eq!(range_keys(&map, (Unbounded, Excluded(size + 1))), all);
680 assert_eq!(range_keys(&map, (Unbounded, Included(size + 1))), all);
681 assert_eq!(range_keys(&map, (Unbounded, Included(size))), all);
682 assert_eq!(range_keys(&map, ..), all);
683
684 assert_eq!(range_keys(&map, (Excluded(0), Excluded(1))), vec![]);
685 assert_eq!(range_keys(&map, (Excluded(0), Included(0))), vec![]);
686 assert_eq!(range_keys(&map, (Included(0), Included(0))), vec![]);
687 assert_eq!(range_keys(&map, (Included(0), Excluded(1))), vec![]);
688 assert_eq!(range_keys(&map, (Unbounded, Excluded(1))), vec![]);
689 assert_eq!(range_keys(&map, (Unbounded, Included(0))), vec![]);
690 assert_eq!(range_keys(&map, (Excluded(0), Excluded(2))), first);
691 assert_eq!(range_keys(&map, (Excluded(0), Included(1))), first);
692 assert_eq!(range_keys(&map, (Included(0), Excluded(2))), first);
693 assert_eq!(range_keys(&map, (Included(0), Included(1))), first);
694 assert_eq!(range_keys(&map, (Included(1), Excluded(2))), first);
695 assert_eq!(range_keys(&map, (Included(1), Included(1))), first);
696 assert_eq!(range_keys(&map, (Unbounded, Excluded(2))), first);
697 assert_eq!(range_keys(&map, (Unbounded, Included(1))), first);
698 assert_eq!(range_keys(&map, (Excluded(size - 1), Excluded(size + 1))), last);
699 assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size + 1))), last);
700 assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size))), last);
701 assert_eq!(range_keys(&map, (Excluded(size - 1), Unbounded)), last);
702 assert_eq!(range_keys(&map, (Included(size), Excluded(size + 1))), last);
703 assert_eq!(range_keys(&map, (Included(size), Included(size + 1))), last);
704 assert_eq!(range_keys(&map, (Included(size), Included(size))), last);
705 assert_eq!(range_keys(&map, (Included(size), Unbounded)), last);
706 assert_eq!(range_keys(&map, (Excluded(size), Excluded(size + 1))), vec![]);
707 assert_eq!(range_keys(&map, (Excluded(size), Included(size))), vec![]);
708 assert_eq!(range_keys(&map, (Excluded(size), Unbounded)), vec![]);
709 assert_eq!(range_keys(&map, (Included(size + 1), Excluded(size + 1))), vec![]);
710 assert_eq!(range_keys(&map, (Included(size + 1), Included(size + 1))), vec![]);
711 assert_eq!(range_keys(&map, (Included(size + 1), Unbounded)), vec![]);
712
713 fn check<'a, L, R>(lhs: L, rhs: R)
714 where
715 L: IntoIterator<Item = (&'a i32, &'a i32)>,
716 R: IntoIterator<Item = (&'a i32, &'a i32)>,
717 {
718 let lhs: Vec<_> = lhs.into_iter().collect();
719 let rhs: Vec<_> = rhs.into_iter().collect();
720 assert_eq!(lhs, rhs);
721 }
722
723 check(map.range(..=100), map.range(..101));
724 check(map.range(5..=8), vec![(&5, &5), (&6, &6), (&7, &7), (&8, &8)]);
725 check(map.range(-1..=2), vec![(&1, &1), (&2, &2)]);
726 }
727
728 #[test]
729 fn test_range_inclusive_max_value() {
730 let max = usize::MAX;
731 let map: BTreeMap<_, _> = vec![(max, 0)].into_iter().collect();
732
733 assert_eq!(map.range(max..=max).collect::<Vec<_>>(), &[(&max, &0)]);
734 }
735
736 #[test]
737 fn test_range_equal_empty_cases() {
738 let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
739 assert_eq!(map.range((Included(2), Excluded(2))).next(), None);
740 assert_eq!(map.range((Excluded(2), Included(2))).next(), None);
741 }
742
743 #[test]
744 #[should_panic]
745 fn test_range_equal_excluded() {
746 let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
747 map.range((Excluded(2), Excluded(2)));
748 }
749
750 #[test]
751 #[should_panic]
752 fn test_range_backwards_1() {
753 let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
754 map.range((Included(3), Included(2)));
755 }
756
757 #[test]
758 #[should_panic]
759 fn test_range_backwards_2() {
760 let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
761 map.range((Included(3), Excluded(2)));
762 }
763
764 #[test]
765 #[should_panic]
766 fn test_range_backwards_3() {
767 let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
768 map.range((Excluded(3), Included(2)));
769 }
770
771 #[test]
772 #[should_panic]
773 fn test_range_backwards_4() {
774 let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
775 map.range((Excluded(3), Excluded(2)));
776 }
777
778 #[test]
779 #[should_panic]
780 fn test_range_finding_ill_order_in_map() {
781 let mut map = BTreeMap::new();
782 map.insert(Cyclic3::B, ());
783 // Lacking static_assert, call `range` conditionally, to emphasise that
784 // we cause a different panic than `test_range_backwards_1` does.
785 // A more refined `should_panic` would be welcome.
786 if Cyclic3::C < Cyclic3::A {
787 map.range(Cyclic3::C..=Cyclic3::A);
788 }
789 }
790
791 #[test]
792 #[should_panic]
793 fn test_range_finding_ill_order_in_range_ord() {
794 // Has proper order the first time asked, then flips around.
795 struct EvilTwin(i32);
796
797 impl PartialOrd for EvilTwin {
798 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
799 Some(self.cmp(other))
800 }
801 }
802
803 static COMPARES: AtomicUsize = AtomicUsize::new(0);
804 impl Ord for EvilTwin {
805 fn cmp(&self, other: &Self) -> Ordering {
806 let ord = self.0.cmp(&other.0);
807 if COMPARES.fetch_add(1, SeqCst) > 0 { ord.reverse() } else { ord }
808 }
809 }
810
811 impl PartialEq for EvilTwin {
812 fn eq(&self, other: &Self) -> bool {
813 self.0.eq(&other.0)
814 }
815 }
816
817 impl Eq for EvilTwin {}
818
819 #[derive(PartialEq, Eq, PartialOrd, Ord)]
820 struct CompositeKey(i32, EvilTwin);
821
822 impl Borrow<EvilTwin> for CompositeKey {
823 fn borrow(&self) -> &EvilTwin {
824 &self.1
825 }
826 }
827
828 let map = (0..12).map(|i| (CompositeKey(i, EvilTwin(i)), ())).collect::<BTreeMap<_, _>>();
829 map.range(EvilTwin(5)..=EvilTwin(7));
830 }
831
832 #[test]
833 fn test_range_1000() {
834 // Miri is too slow
835 let size = if cfg!(miri) { MIN_INSERTS_HEIGHT_2 as u32 } else { 1000 };
836 let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
837
838 fn test(map: &BTreeMap<u32, u32>, size: u32, min: Bound<&u32>, max: Bound<&u32>) {
839 let mut kvs = map.range((min, max)).map(|(&k, &v)| (k, v));
840 let mut pairs = (0..size).map(|i| (i, i));
841
842 for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
843 assert_eq!(kv, pair);
844 }
845 assert_eq!(kvs.next(), None);
846 assert_eq!(pairs.next(), None);
847 }
848 test(&map, size, Included(&0), Excluded(&size));
849 test(&map, size, Unbounded, Excluded(&size));
850 test(&map, size, Included(&0), Included(&(size - 1)));
851 test(&map, size, Unbounded, Included(&(size - 1)));
852 test(&map, size, Included(&0), Unbounded);
853 test(&map, size, Unbounded, Unbounded);
854 }
855
856 #[test]
857 fn test_range_borrowed_key() {
858 let mut map = BTreeMap::new();
859 map.insert("aardvark".to_string(), 1);
860 map.insert("baboon".to_string(), 2);
861 map.insert("coyote".to_string(), 3);
862 map.insert("dingo".to_string(), 4);
863 // NOTE: would like to use simply "b".."d" here...
864 let mut iter = map.range::<str, _>((Included("b"), Excluded("d")));
865 assert_eq!(iter.next(), Some((&"baboon".to_string(), &2)));
866 assert_eq!(iter.next(), Some((&"coyote".to_string(), &3)));
867 assert_eq!(iter.next(), None);
868 }
869
870 #[test]
871 fn test_range() {
872 let size = 200;
873 // Miri is too slow
874 let step = if cfg!(miri) { 66 } else { 1 };
875 let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
876
877 for i in (0..size).step_by(step) {
878 for j in (i..size).step_by(step) {
879 let mut kvs = map.range((Included(&i), Included(&j))).map(|(&k, &v)| (k, v));
880 let mut pairs = (i..=j).map(|i| (i, i));
881
882 for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
883 assert_eq!(kv, pair);
884 }
885 assert_eq!(kvs.next(), None);
886 assert_eq!(pairs.next(), None);
887 }
888 }
889 }
890
891 #[test]
892 fn test_range_mut() {
893 let size = 200;
894 // Miri is too slow
895 let step = if cfg!(miri) { 66 } else { 1 };
896 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
897
898 for i in (0..size).step_by(step) {
899 for j in (i..size).step_by(step) {
900 let mut kvs = map.range_mut((Included(&i), Included(&j))).map(|(&k, &mut v)| (k, v));
901 let mut pairs = (i..=j).map(|i| (i, i));
902
903 for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
904 assert_eq!(kv, pair);
905 }
906 assert_eq!(kvs.next(), None);
907 assert_eq!(pairs.next(), None);
908 }
909 }
910 map.check();
911 }
912
913 #[test]
914 fn test_retain() {
915 let mut map: BTreeMap<i32, i32> = (0..100).map(|x| (x, x * 10)).collect();
916
917 map.retain(|&k, _| k % 2 == 0);
918 assert_eq!(map.len(), 50);
919 assert_eq!(map[&2], 20);
920 assert_eq!(map[&4], 40);
921 assert_eq!(map[&6], 60);
922 }
923
924 mod test_drain_filter {
925 use super::*;
926
927 #[test]
928 fn empty() {
929 let mut map: BTreeMap<i32, i32> = BTreeMap::new();
930 map.drain_filter(|_, _| unreachable!("there's nothing to decide on"));
931 assert!(map.is_empty());
932 map.check();
933 }
934
935 // Explicitly consumes the iterator, where most test cases drop it instantly.
936 #[test]
937 fn consumed_keeping_all() {
938 let pairs = (0..3).map(|i| (i, i));
939 let mut map: BTreeMap<_, _> = pairs.collect();
940 assert!(map.drain_filter(|_, _| false).eq(iter::empty()));
941 map.check();
942 }
943
944 // Explicitly consumes the iterator, where most test cases drop it instantly.
945 #[test]
946 fn consumed_removing_all() {
947 let pairs = (0..3).map(|i| (i, i));
948 let mut map: BTreeMap<_, _> = pairs.clone().collect();
949 assert!(map.drain_filter(|_, _| true).eq(pairs));
950 assert!(map.is_empty());
951 map.check();
952 }
953
954 // Explicitly consumes the iterator and modifies values through it.
955 #[test]
956 fn mutating_and_keeping() {
957 let pairs = (0..3).map(|i| (i, i));
958 let mut map: BTreeMap<_, _> = pairs.collect();
959 assert!(
960 map.drain_filter(|_, v| {
961 *v += 6;
962 false
963 })
964 .eq(iter::empty())
965 );
966 assert!(map.keys().copied().eq(0..3));
967 assert!(map.values().copied().eq(6..9));
968 map.check();
969 }
970
971 // Explicitly consumes the iterator and modifies values through it.
972 #[test]
973 fn mutating_and_removing() {
974 let pairs = (0..3).map(|i| (i, i));
975 let mut map: BTreeMap<_, _> = pairs.collect();
976 assert!(
977 map.drain_filter(|_, v| {
978 *v += 6;
979 true
980 })
981 .eq((0..3).map(|i| (i, i + 6)))
982 );
983 assert!(map.is_empty());
984 map.check();
985 }
986
987 #[test]
988 fn underfull_keeping_all() {
989 let pairs = (0..3).map(|i| (i, i));
990 let mut map: BTreeMap<_, _> = pairs.collect();
991 map.drain_filter(|_, _| false);
992 assert!(map.keys().copied().eq(0..3));
993 map.check();
994 }
995
996 #[test]
997 fn underfull_removing_one() {
998 let pairs = (0..3).map(|i| (i, i));
999 for doomed in 0..3 {
1000 let mut map: BTreeMap<_, _> = pairs.clone().collect();
1001 map.drain_filter(|i, _| *i == doomed);
1002 assert_eq!(map.len(), 2);
1003 map.check();
1004 }
1005 }
1006
1007 #[test]
1008 fn underfull_keeping_one() {
1009 let pairs = (0..3).map(|i| (i, i));
1010 for sacred in 0..3 {
1011 let mut map: BTreeMap<_, _> = pairs.clone().collect();
1012 map.drain_filter(|i, _| *i != sacred);
1013 assert!(map.keys().copied().eq(sacred..=sacred));
1014 map.check();
1015 }
1016 }
1017
1018 #[test]
1019 fn underfull_removing_all() {
1020 let pairs = (0..3).map(|i| (i, i));
1021 let mut map: BTreeMap<_, _> = pairs.collect();
1022 map.drain_filter(|_, _| true);
1023 assert!(map.is_empty());
1024 map.check();
1025 }
1026
1027 #[test]
1028 fn height_0_keeping_all() {
1029 let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
1030 let mut map: BTreeMap<_, _> = pairs.collect();
1031 map.drain_filter(|_, _| false);
1032 assert!(map.keys().copied().eq(0..NODE_CAPACITY));
1033 map.check();
1034 }
1035
1036 #[test]
1037 fn height_0_removing_one() {
1038 let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
1039 for doomed in 0..NODE_CAPACITY {
1040 let mut map: BTreeMap<_, _> = pairs.clone().collect();
1041 map.drain_filter(|i, _| *i == doomed);
1042 assert_eq!(map.len(), NODE_CAPACITY - 1);
1043 map.check();
1044 }
1045 }
1046
1047 #[test]
1048 fn height_0_keeping_one() {
1049 let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
1050 for sacred in 0..NODE_CAPACITY {
1051 let mut map: BTreeMap<_, _> = pairs.clone().collect();
1052 map.drain_filter(|i, _| *i != sacred);
1053 assert!(map.keys().copied().eq(sacred..=sacred));
1054 map.check();
1055 }
1056 }
1057
1058 #[test]
1059 fn height_0_removing_all() {
1060 let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
1061 let mut map: BTreeMap<_, _> = pairs.collect();
1062 map.drain_filter(|_, _| true);
1063 assert!(map.is_empty());
1064 map.check();
1065 }
1066
1067 #[test]
1068 fn height_0_keeping_half() {
1069 let mut map: BTreeMap<_, _> = (0..16).map(|i| (i, i)).collect();
1070 assert_eq!(map.drain_filter(|i, _| *i % 2 == 0).count(), 8);
1071 assert_eq!(map.len(), 8);
1072 map.check();
1073 }
1074
1075 #[test]
1076 fn height_1_removing_all() {
1077 let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i));
1078 let mut map: BTreeMap<_, _> = pairs.collect();
1079 map.drain_filter(|_, _| true);
1080 assert!(map.is_empty());
1081 map.check();
1082 }
1083
1084 #[test]
1085 fn height_1_removing_one() {
1086 let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i));
1087 for doomed in 0..MIN_INSERTS_HEIGHT_1 {
1088 let mut map: BTreeMap<_, _> = pairs.clone().collect();
1089 map.drain_filter(|i, _| *i == doomed);
1090 assert_eq!(map.len(), MIN_INSERTS_HEIGHT_1 - 1);
1091 map.check();
1092 }
1093 }
1094
1095 #[test]
1096 fn height_1_keeping_one() {
1097 let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i));
1098 for sacred in 0..MIN_INSERTS_HEIGHT_1 {
1099 let mut map: BTreeMap<_, _> = pairs.clone().collect();
1100 map.drain_filter(|i, _| *i != sacred);
1101 assert!(map.keys().copied().eq(sacred..=sacred));
1102 map.check();
1103 }
1104 }
1105
1106 #[test]
1107 fn height_2_removing_one() {
1108 let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
1109 for doomed in (0..MIN_INSERTS_HEIGHT_2).step_by(12) {
1110 let mut map: BTreeMap<_, _> = pairs.clone().collect();
1111 map.drain_filter(|i, _| *i == doomed);
1112 assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2 - 1);
1113 map.check();
1114 }
1115 }
1116
1117 #[test]
1118 fn height_2_keeping_one() {
1119 let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
1120 for sacred in (0..MIN_INSERTS_HEIGHT_2).step_by(12) {
1121 let mut map: BTreeMap<_, _> = pairs.clone().collect();
1122 map.drain_filter(|i, _| *i != sacred);
1123 assert!(map.keys().copied().eq(sacred..=sacred));
1124 map.check();
1125 }
1126 }
1127
1128 #[test]
1129 fn height_2_removing_all() {
1130 let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
1131 let mut map: BTreeMap<_, _> = pairs.collect();
1132 map.drain_filter(|_, _| true);
1133 assert!(map.is_empty());
1134 map.check();
1135 }
1136
1137 #[test]
1138 fn drop_panic_leak() {
1139 let a = CrashTestDummy::new(0);
1140 let b = CrashTestDummy::new(1);
1141 let c = CrashTestDummy::new(2);
1142 let mut map = BTreeMap::new();
1143 map.insert(a.spawn(Panic::Never), ());
1144 map.insert(b.spawn(Panic::InDrop), ());
1145 map.insert(c.spawn(Panic::Never), ());
1146
1147 catch_unwind(move || drop(map.drain_filter(|dummy, _| dummy.query(true)))).unwrap_err();
1148
1149 assert_eq!(a.queried(), 1);
1150 assert_eq!(b.queried(), 1);
1151 assert_eq!(c.queried(), 0);
1152 assert_eq!(a.dropped(), 1);
1153 assert_eq!(b.dropped(), 1);
1154 assert_eq!(c.dropped(), 1);
1155 }
1156
1157 #[test]
1158 fn pred_panic_leak() {
1159 let a = CrashTestDummy::new(0);
1160 let b = CrashTestDummy::new(1);
1161 let c = CrashTestDummy::new(2);
1162 let mut map = BTreeMap::new();
1163 map.insert(a.spawn(Panic::Never), ());
1164 map.insert(b.spawn(Panic::InQuery), ());
1165 map.insert(c.spawn(Panic::InQuery), ());
1166
1167 catch_unwind(AssertUnwindSafe(|| drop(map.drain_filter(|dummy, _| dummy.query(true)))))
1168 .unwrap_err();
1169
1170 assert_eq!(a.queried(), 1);
1171 assert_eq!(b.queried(), 1);
1172 assert_eq!(c.queried(), 0);
1173 assert_eq!(a.dropped(), 1);
1174 assert_eq!(b.dropped(), 0);
1175 assert_eq!(c.dropped(), 0);
1176 assert_eq!(map.len(), 2);
1177 assert_eq!(map.first_entry().unwrap().key().id(), 1);
1178 assert_eq!(map.last_entry().unwrap().key().id(), 2);
1179 map.check();
1180 }
1181
1182 // Same as above, but attempt to use the iterator again after the panic in the predicate
1183 #[test]
1184 fn pred_panic_reuse() {
1185 let a = CrashTestDummy::new(0);
1186 let b = CrashTestDummy::new(1);
1187 let c = CrashTestDummy::new(2);
1188 let mut map = BTreeMap::new();
1189 map.insert(a.spawn(Panic::Never), ());
1190 map.insert(b.spawn(Panic::InQuery), ());
1191 map.insert(c.spawn(Panic::InQuery), ());
1192
1193 {
1194 let mut it = map.drain_filter(|dummy, _| dummy.query(true));
1195 catch_unwind(AssertUnwindSafe(|| while it.next().is_some() {})).unwrap_err();
1196 // Iterator behaviour after a panic is explicitly unspecified,
1197 // so this is just the current implementation:
1198 let result = catch_unwind(AssertUnwindSafe(|| it.next()));
1199 assert!(matches!(result, Ok(None)));
1200 }
1201
1202 assert_eq!(a.queried(), 1);
1203 assert_eq!(b.queried(), 1);
1204 assert_eq!(c.queried(), 0);
1205 assert_eq!(a.dropped(), 1);
1206 assert_eq!(b.dropped(), 0);
1207 assert_eq!(c.dropped(), 0);
1208 assert_eq!(map.len(), 2);
1209 assert_eq!(map.first_entry().unwrap().key().id(), 1);
1210 assert_eq!(map.last_entry().unwrap().key().id(), 2);
1211 map.check();
1212 }
1213 }
1214
1215 #[test]
1216 fn test_borrow() {
1217 // make sure these compile -- using the Borrow trait
1218 {
1219 let mut map = BTreeMap::new();
1220 map.insert("0".to_string(), 1);
1221 assert_eq!(map["0"], 1);
1222 }
1223
1224 {
1225 let mut map = BTreeMap::new();
1226 map.insert(Box::new(0), 1);
1227 assert_eq!(map[&0], 1);
1228 }
1229
1230 {
1231 let mut map = BTreeMap::new();
1232 map.insert(Box::new([0, 1]) as Box<[i32]>, 1);
1233 assert_eq!(map[&[0, 1][..]], 1);
1234 }
1235
1236 {
1237 let mut map = BTreeMap::new();
1238 map.insert(Rc::new(0), 1);
1239 assert_eq!(map[&0], 1);
1240 }
1241
1242 #[allow(dead_code)]
1243 fn get<T: Ord>(v: &BTreeMap<Box<T>, ()>, t: &T) {
1244 v.get(t);
1245 }
1246
1247 #[allow(dead_code)]
1248 fn get_mut<T: Ord>(v: &mut BTreeMap<Box<T>, ()>, t: &T) {
1249 v.get_mut(t);
1250 }
1251
1252 #[allow(dead_code)]
1253 fn get_key_value<T: Ord>(v: &BTreeMap<Box<T>, ()>, t: &T) {
1254 v.get_key_value(t);
1255 }
1256
1257 #[allow(dead_code)]
1258 fn contains_key<T: Ord>(v: &BTreeMap<Box<T>, ()>, t: &T) {
1259 v.contains_key(t);
1260 }
1261
1262 #[allow(dead_code)]
1263 fn range<T: Ord>(v: &BTreeMap<Box<T>, ()>, t: T) {
1264 v.range(t..);
1265 }
1266
1267 #[allow(dead_code)]
1268 fn range_mut<T: Ord>(v: &mut BTreeMap<Box<T>, ()>, t: T) {
1269 v.range_mut(t..);
1270 }
1271
1272 #[allow(dead_code)]
1273 fn remove<T: Ord>(v: &mut BTreeMap<Box<T>, ()>, t: &T) {
1274 v.remove(t);
1275 }
1276
1277 #[allow(dead_code)]
1278 fn remove_entry<T: Ord>(v: &mut BTreeMap<Box<T>, ()>, t: &T) {
1279 v.remove_entry(t);
1280 }
1281
1282 #[allow(dead_code)]
1283 fn split_off<T: Ord>(v: &mut BTreeMap<Box<T>, ()>, t: &T) {
1284 v.split_off(t);
1285 }
1286 }
1287
1288 #[test]
1289 fn test_entry() {
1290 let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
1291
1292 let mut map: BTreeMap<_, _> = xs.iter().cloned().collect();
1293
1294 // Existing key (insert)
1295 match map.entry(1) {
1296 Vacant(_) => unreachable!(),
1297 Occupied(mut view) => {
1298 assert_eq!(view.get(), &10);
1299 assert_eq!(view.insert(100), 10);
1300 }
1301 }
1302 assert_eq!(map.get(&1).unwrap(), &100);
1303 assert_eq!(map.len(), 6);
1304
1305 // Existing key (update)
1306 match map.entry(2) {
1307 Vacant(_) => unreachable!(),
1308 Occupied(mut view) => {
1309 let v = view.get_mut();
1310 *v *= 10;
1311 }
1312 }
1313 assert_eq!(map.get(&2).unwrap(), &200);
1314 assert_eq!(map.len(), 6);
1315 map.check();
1316
1317 // Existing key (take)
1318 match map.entry(3) {
1319 Vacant(_) => unreachable!(),
1320 Occupied(view) => {
1321 assert_eq!(view.remove(), 30);
1322 }
1323 }
1324 assert_eq!(map.get(&3), None);
1325 assert_eq!(map.len(), 5);
1326 map.check();
1327
1328 // Inexistent key (insert)
1329 match map.entry(10) {
1330 Occupied(_) => unreachable!(),
1331 Vacant(view) => {
1332 assert_eq!(*view.insert(1000), 1000);
1333 }
1334 }
1335 assert_eq!(map.get(&10).unwrap(), &1000);
1336 assert_eq!(map.len(), 6);
1337 map.check();
1338 }
1339
1340 #[test]
1341 fn test_extend_ref() {
1342 let mut a = BTreeMap::new();
1343 a.insert(1, "one");
1344 let mut b = BTreeMap::new();
1345 b.insert(2, "two");
1346 b.insert(3, "three");
1347
1348 a.extend(&b);
1349
1350 assert_eq!(a.len(), 3);
1351 assert_eq!(a[&1], "one");
1352 assert_eq!(a[&2], "two");
1353 assert_eq!(a[&3], "three");
1354 a.check();
1355 }
1356
1357 #[test]
1358 fn test_zst() {
1359 let mut m = BTreeMap::new();
1360 assert_eq!(m.len(), 0);
1361
1362 assert_eq!(m.insert((), ()), None);
1363 assert_eq!(m.len(), 1);
1364
1365 assert_eq!(m.insert((), ()), Some(()));
1366 assert_eq!(m.len(), 1);
1367 assert_eq!(m.iter().count(), 1);
1368
1369 m.clear();
1370 assert_eq!(m.len(), 0);
1371
1372 for _ in 0..100 {
1373 m.insert((), ());
1374 }
1375
1376 assert_eq!(m.len(), 1);
1377 assert_eq!(m.iter().count(), 1);
1378 m.check();
1379 }
1380
1381 // This test's only purpose is to ensure that zero-sized keys with nonsensical orderings
1382 // do not cause segfaults when used with zero-sized values. All other map behavior is
1383 // undefined.
1384 #[test]
1385 fn test_bad_zst() {
1386 #[derive(Clone, Copy, Debug)]
1387 struct Bad;
1388
1389 impl PartialEq for Bad {
1390 fn eq(&self, _: &Self) -> bool {
1391 false
1392 }
1393 }
1394
1395 impl Eq for Bad {}
1396
1397 impl PartialOrd for Bad {
1398 fn partial_cmp(&self, _: &Self) -> Option<Ordering> {
1399 Some(Ordering::Less)
1400 }
1401 }
1402
1403 impl Ord for Bad {
1404 fn cmp(&self, _: &Self) -> Ordering {
1405 Ordering::Less
1406 }
1407 }
1408
1409 let mut m = BTreeMap::new();
1410
1411 for _ in 0..100 {
1412 m.insert(Bad, Bad);
1413 }
1414 m.check();
1415 }
1416
1417 #[test]
1418 fn test_clear() {
1419 let mut map = BTreeMap::new();
1420 for &len in &[MIN_INSERTS_HEIGHT_1, MIN_INSERTS_HEIGHT_2, 0, NODE_CAPACITY] {
1421 for i in 0..len {
1422 map.insert(i, ());
1423 }
1424 assert_eq!(map.len(), len);
1425 map.clear();
1426 map.check();
1427 assert!(map.is_empty());
1428 }
1429 }
1430
1431 #[test]
1432 fn test_clear_drop_panic_leak() {
1433 let a = CrashTestDummy::new(0);
1434 let b = CrashTestDummy::new(1);
1435 let c = CrashTestDummy::new(2);
1436
1437 let mut map = BTreeMap::new();
1438 map.insert(a.spawn(Panic::Never), ());
1439 map.insert(b.spawn(Panic::InDrop), ());
1440 map.insert(c.spawn(Panic::Never), ());
1441
1442 catch_unwind(AssertUnwindSafe(|| map.clear())).unwrap_err();
1443 assert_eq!(a.dropped(), 1);
1444 assert_eq!(b.dropped(), 1);
1445 assert_eq!(c.dropped(), 1);
1446 assert_eq!(map.len(), 0);
1447
1448 drop(map);
1449 assert_eq!(a.dropped(), 1);
1450 assert_eq!(b.dropped(), 1);
1451 assert_eq!(c.dropped(), 1);
1452 }
1453
1454 #[test]
1455 fn test_clone() {
1456 let mut map = BTreeMap::new();
1457 let size = MIN_INSERTS_HEIGHT_1;
1458 assert_eq!(map.len(), 0);
1459
1460 for i in 0..size {
1461 assert_eq!(map.insert(i, 10 * i), None);
1462 assert_eq!(map.len(), i + 1);
1463 map.check();
1464 assert_eq!(map, map.clone());
1465 }
1466
1467 for i in 0..size {
1468 assert_eq!(map.insert(i, 100 * i), Some(10 * i));
1469 assert_eq!(map.len(), size);
1470 map.check();
1471 assert_eq!(map, map.clone());
1472 }
1473
1474 for i in 0..size / 2 {
1475 assert_eq!(map.remove(&(i * 2)), Some(i * 200));
1476 assert_eq!(map.len(), size - i - 1);
1477 map.check();
1478 assert_eq!(map, map.clone());
1479 }
1480
1481 for i in 0..size / 2 {
1482 assert_eq!(map.remove(&(2 * i)), None);
1483 assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
1484 assert_eq!(map.len(), size / 2 - i - 1);
1485 map.check();
1486 assert_eq!(map, map.clone());
1487 }
1488
1489 // Test a tree with 2 semi-full levels and a tree with 3 levels.
1490 map = (1..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)).collect();
1491 assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2 - 1);
1492 assert_eq!(map, map.clone());
1493 map.insert(0, 0);
1494 assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2);
1495 assert_eq!(map, map.clone());
1496 map.check();
1497 }
1498
1499 #[test]
1500 fn test_clone_panic_leak() {
1501 let a = CrashTestDummy::new(0);
1502 let b = CrashTestDummy::new(1);
1503 let c = CrashTestDummy::new(2);
1504
1505 let mut map = BTreeMap::new();
1506 map.insert(a.spawn(Panic::Never), ());
1507 map.insert(b.spawn(Panic::InClone), ());
1508 map.insert(c.spawn(Panic::Never), ());
1509
1510 catch_unwind(|| map.clone()).unwrap_err();
1511 assert_eq!(a.cloned(), 1);
1512 assert_eq!(b.cloned(), 1);
1513 assert_eq!(c.cloned(), 0);
1514 assert_eq!(a.dropped(), 1);
1515 assert_eq!(b.dropped(), 0);
1516 assert_eq!(c.dropped(), 0);
1517 assert_eq!(map.len(), 3);
1518
1519 drop(map);
1520 assert_eq!(a.cloned(), 1);
1521 assert_eq!(b.cloned(), 1);
1522 assert_eq!(c.cloned(), 0);
1523 assert_eq!(a.dropped(), 2);
1524 assert_eq!(b.dropped(), 1);
1525 assert_eq!(c.dropped(), 1);
1526 }
1527
1528 #[test]
1529 fn test_clone_from() {
1530 let mut map1 = BTreeMap::new();
1531 let max_size = MIN_INSERTS_HEIGHT_1;
1532
1533 // Range to max_size inclusive, because i is the size of map1 being tested.
1534 for i in 0..=max_size {
1535 let mut map2 = BTreeMap::new();
1536 for j in 0..i {
1537 let mut map1_copy = map2.clone();
1538 map1_copy.clone_from(&map1); // small cloned from large
1539 assert_eq!(map1_copy, map1);
1540 let mut map2_copy = map1.clone();
1541 map2_copy.clone_from(&map2); // large cloned from small
1542 assert_eq!(map2_copy, map2);
1543 map2.insert(100 * j + 1, 2 * j + 1);
1544 }
1545 map2.clone_from(&map1); // same length
1546 map2.check();
1547 assert_eq!(map2, map1);
1548 map1.insert(i, 10 * i);
1549 map1.check();
1550 }
1551 }
1552
1553 #[allow(dead_code)]
1554 fn test_variance() {
1555 fn map_key<'new>(v: BTreeMap<&'static str, ()>) -> BTreeMap<&'new str, ()> {
1556 v
1557 }
1558 fn map_val<'new>(v: BTreeMap<(), &'static str>) -> BTreeMap<(), &'new str> {
1559 v
1560 }
1561
1562 fn iter_key<'a, 'new>(v: Iter<'a, &'static str, ()>) -> Iter<'a, &'new str, ()> {
1563 v
1564 }
1565 fn iter_val<'a, 'new>(v: Iter<'a, (), &'static str>) -> Iter<'a, (), &'new str> {
1566 v
1567 }
1568
1569 fn into_iter_key<'new>(v: IntoIter<&'static str, ()>) -> IntoIter<&'new str, ()> {
1570 v
1571 }
1572 fn into_iter_val<'new>(v: IntoIter<(), &'static str>) -> IntoIter<(), &'new str> {
1573 v
1574 }
1575
1576 fn into_keys_key<'new>(v: IntoKeys<&'static str, ()>) -> IntoKeys<&'new str, ()> {
1577 v
1578 }
1579 fn into_keys_val<'new>(v: IntoKeys<(), &'static str>) -> IntoKeys<(), &'new str> {
1580 v
1581 }
1582
1583 fn into_values_key<'new>(v: IntoValues<&'static str, ()>) -> IntoValues<&'new str, ()> {
1584 v
1585 }
1586 fn into_values_val<'new>(v: IntoValues<(), &'static str>) -> IntoValues<(), &'new str> {
1587 v
1588 }
1589
1590 fn range_key<'a, 'new>(v: Range<'a, &'static str, ()>) -> Range<'a, &'new str, ()> {
1591 v
1592 }
1593 fn range_val<'a, 'new>(v: Range<'a, (), &'static str>) -> Range<'a, (), &'new str> {
1594 v
1595 }
1596
1597 fn keys_key<'a, 'new>(v: Keys<'a, &'static str, ()>) -> Keys<'a, &'new str, ()> {
1598 v
1599 }
1600 fn keys_val<'a, 'new>(v: Keys<'a, (), &'static str>) -> Keys<'a, (), &'new str> {
1601 v
1602 }
1603
1604 fn values_key<'a, 'new>(v: Values<'a, &'static str, ()>) -> Values<'a, &'new str, ()> {
1605 v
1606 }
1607 fn values_val<'a, 'new>(v: Values<'a, (), &'static str>) -> Values<'a, (), &'new str> {
1608 v
1609 }
1610 }
1611
1612 #[allow(dead_code)]
1613 fn test_sync() {
1614 fn map<T: Sync>(v: &BTreeMap<T, T>) -> impl Sync + '_ {
1615 v
1616 }
1617
1618 fn into_iter<T: Sync>(v: BTreeMap<T, T>) -> impl Sync {
1619 v.into_iter()
1620 }
1621
1622 fn into_keys<T: Sync + Ord>(v: BTreeMap<T, T>) -> impl Sync {
1623 v.into_keys()
1624 }
1625
1626 fn into_values<T: Sync + Ord>(v: BTreeMap<T, T>) -> impl Sync {
1627 v.into_values()
1628 }
1629
1630 fn drain_filter<T: Sync + Ord>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ {
1631 v.drain_filter(|_, _| false)
1632 }
1633
1634 fn iter<T: Sync>(v: &BTreeMap<T, T>) -> impl Sync + '_ {
1635 v.iter()
1636 }
1637
1638 fn iter_mut<T: Sync>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ {
1639 v.iter_mut()
1640 }
1641
1642 fn keys<T: Sync>(v: &BTreeMap<T, T>) -> impl Sync + '_ {
1643 v.keys()
1644 }
1645
1646 fn values<T: Sync>(v: &BTreeMap<T, T>) -> impl Sync + '_ {
1647 v.values()
1648 }
1649
1650 fn values_mut<T: Sync>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ {
1651 v.values_mut()
1652 }
1653
1654 fn range<T: Sync + Ord>(v: &BTreeMap<T, T>) -> impl Sync + '_ {
1655 v.range(..)
1656 }
1657
1658 fn range_mut<T: Sync + Ord>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ {
1659 v.range_mut(..)
1660 }
1661
1662 fn entry<T: Sync + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ {
1663 v.entry(Default::default())
1664 }
1665
1666 fn occupied_entry<T: Sync + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ {
1667 match v.entry(Default::default()) {
1668 Occupied(entry) => entry,
1669 _ => unreachable!(),
1670 }
1671 }
1672
1673 fn vacant_entry<T: Sync + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ {
1674 match v.entry(Default::default()) {
1675 Vacant(entry) => entry,
1676 _ => unreachable!(),
1677 }
1678 }
1679 }
1680
1681 #[allow(dead_code)]
1682 fn test_send() {
1683 fn map<T: Send>(v: BTreeMap<T, T>) -> impl Send {
1684 v
1685 }
1686
1687 fn into_iter<T: Send>(v: BTreeMap<T, T>) -> impl Send {
1688 v.into_iter()
1689 }
1690
1691 fn into_keys<T: Send + Ord>(v: BTreeMap<T, T>) -> impl Send {
1692 v.into_keys()
1693 }
1694
1695 fn into_values<T: Send + Ord>(v: BTreeMap<T, T>) -> impl Send {
1696 v.into_values()
1697 }
1698
1699 fn drain_filter<T: Send + Ord>(v: &mut BTreeMap<T, T>) -> impl Send + '_ {
1700 v.drain_filter(|_, _| false)
1701 }
1702
1703 fn iter<T: Send + Sync>(v: &BTreeMap<T, T>) -> impl Send + '_ {
1704 v.iter()
1705 }
1706
1707 fn iter_mut<T: Send>(v: &mut BTreeMap<T, T>) -> impl Send + '_ {
1708 v.iter_mut()
1709 }
1710
1711 fn keys<T: Send + Sync>(v: &BTreeMap<T, T>) -> impl Send + '_ {
1712 v.keys()
1713 }
1714
1715 fn values<T: Send + Sync>(v: &BTreeMap<T, T>) -> impl Send + '_ {
1716 v.values()
1717 }
1718
1719 fn values_mut<T: Send>(v: &mut BTreeMap<T, T>) -> impl Send + '_ {
1720 v.values_mut()
1721 }
1722
1723 fn range<T: Send + Sync + Ord>(v: &BTreeMap<T, T>) -> impl Send + '_ {
1724 v.range(..)
1725 }
1726
1727 fn range_mut<T: Send + Ord>(v: &mut BTreeMap<T, T>) -> impl Send + '_ {
1728 v.range_mut(..)
1729 }
1730
1731 fn entry<T: Send + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Send + '_ {
1732 v.entry(Default::default())
1733 }
1734
1735 fn occupied_entry<T: Send + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Send + '_ {
1736 match v.entry(Default::default()) {
1737 Occupied(entry) => entry,
1738 _ => unreachable!(),
1739 }
1740 }
1741
1742 fn vacant_entry<T: Send + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Send + '_ {
1743 match v.entry(Default::default()) {
1744 Vacant(entry) => entry,
1745 _ => unreachable!(),
1746 }
1747 }
1748 }
1749
1750 #[allow(dead_code)]
1751 fn test_ord_absence() {
1752 fn map<K>(mut map: BTreeMap<K, ()>) {
1753 map.is_empty();
1754 map.len();
1755 map.clear();
1756 map.iter();
1757 map.iter_mut();
1758 map.keys();
1759 map.values();
1760 map.values_mut();
1761 if true {
1762 map.into_values();
1763 } else if true {
1764 map.into_iter();
1765 } else {
1766 map.into_keys();
1767 }
1768 }
1769
1770 fn map_debug<K: Debug>(mut map: BTreeMap<K, ()>) {
1771 format!("{:?}", map);
1772 format!("{:?}", map.iter());
1773 format!("{:?}", map.iter_mut());
1774 format!("{:?}", map.keys());
1775 format!("{:?}", map.values());
1776 format!("{:?}", map.values_mut());
1777 if true {
1778 format!("{:?}", map.into_iter());
1779 } else if true {
1780 format!("{:?}", map.into_keys());
1781 } else {
1782 format!("{:?}", map.into_values());
1783 }
1784 }
1785
1786 fn map_clone<K: Clone>(mut map: BTreeMap<K, ()>) {
1787 map.clone_from(&map.clone());
1788 }
1789 }
1790
1791 #[allow(dead_code)]
1792 fn test_const() {
1793 const MAP: &'static BTreeMap<(), ()> = &BTreeMap::new();
1794 const LEN: usize = MAP.len();
1795 const IS_EMPTY: bool = MAP.is_empty();
1796 }
1797
1798 #[test]
1799 fn test_occupied_entry_key() {
1800 let mut a = BTreeMap::new();
1801 let key = "hello there";
1802 let value = "value goes here";
1803 assert!(a.is_empty());
1804 a.insert(key, value);
1805 assert_eq!(a.len(), 1);
1806 assert_eq!(a[key], value);
1807
1808 match a.entry(key) {
1809 Vacant(_) => panic!(),
1810 Occupied(e) => assert_eq!(key, *e.key()),
1811 }
1812 assert_eq!(a.len(), 1);
1813 assert_eq!(a[key], value);
1814 a.check();
1815 }
1816
1817 #[test]
1818 fn test_vacant_entry_key() {
1819 let mut a = BTreeMap::new();
1820 let key = "hello there";
1821 let value = "value goes here";
1822
1823 assert!(a.is_empty());
1824 match a.entry(key) {
1825 Occupied(_) => panic!(),
1826 Vacant(e) => {
1827 assert_eq!(key, *e.key());
1828 e.insert(value);
1829 }
1830 }
1831 assert_eq!(a.len(), 1);
1832 assert_eq!(a[key], value);
1833 a.check();
1834 }
1835
1836 #[test]
1837 fn test_first_last_entry() {
1838 let mut a = BTreeMap::new();
1839 assert!(a.first_entry().is_none());
1840 assert!(a.last_entry().is_none());
1841 a.insert(1, 42);
1842 assert_eq!(a.first_entry().unwrap().key(), &1);
1843 assert_eq!(a.last_entry().unwrap().key(), &1);
1844 a.insert(2, 24);
1845 assert_eq!(a.first_entry().unwrap().key(), &1);
1846 assert_eq!(a.last_entry().unwrap().key(), &2);
1847 a.insert(0, 6);
1848 assert_eq!(a.first_entry().unwrap().key(), &0);
1849 assert_eq!(a.last_entry().unwrap().key(), &2);
1850 let (k1, v1) = a.first_entry().unwrap().remove_entry();
1851 assert_eq!(k1, 0);
1852 assert_eq!(v1, 6);
1853 let (k2, v2) = a.last_entry().unwrap().remove_entry();
1854 assert_eq!(k2, 2);
1855 assert_eq!(v2, 24);
1856 assert_eq!(a.first_entry().unwrap().key(), &1);
1857 assert_eq!(a.last_entry().unwrap().key(), &1);
1858 a.check();
1859 }
1860
1861 #[test]
1862 fn test_insert_into_full_height_0() {
1863 let size = NODE_CAPACITY;
1864 for pos in 0..=size {
1865 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i * 2 + 1, ())).collect();
1866 assert!(map.insert(pos * 2, ()).is_none());
1867 map.check();
1868 }
1869 }
1870
1871 #[test]
1872 fn test_insert_into_full_height_1() {
1873 let size = NODE_CAPACITY + 1 + NODE_CAPACITY;
1874 for pos in 0..=size {
1875 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i * 2 + 1, ())).collect();
1876 map.compact();
1877 let root_node = map.root.as_ref().unwrap().reborrow();
1878 assert_eq!(root_node.len(), 1);
1879 assert_eq!(root_node.first_leaf_edge().into_node().len(), NODE_CAPACITY);
1880 assert_eq!(root_node.last_leaf_edge().into_node().len(), NODE_CAPACITY);
1881
1882 assert!(map.insert(pos * 2, ()).is_none());
1883 map.check();
1884 }
1885 }
1886
1887 macro_rules! create_append_test {
1888 ($name:ident, $len:expr) => {
1889 #[test]
1890 fn $name() {
1891 let mut a = BTreeMap::new();
1892 for i in 0..8 {
1893 a.insert(i, i);
1894 }
1895
1896 let mut b = BTreeMap::new();
1897 for i in 5..$len {
1898 b.insert(i, 2 * i);
1899 }
1900
1901 a.append(&mut b);
1902
1903 assert_eq!(a.len(), $len);
1904 assert_eq!(b.len(), 0);
1905
1906 for i in 0..$len {
1907 if i < 5 {
1908 assert_eq!(a[&i], i);
1909 } else {
1910 assert_eq!(a[&i], 2 * i);
1911 }
1912 }
1913
1914 a.check();
1915 assert_eq!(a.remove(&($len - 1)), Some(2 * ($len - 1)));
1916 assert_eq!(a.insert($len - 1, 20), None);
1917 a.check();
1918 }
1919 };
1920 }
1921
1922 // These are mostly for testing the algorithm that "fixes" the right edge after insertion.
1923 // Single node.
1924 create_append_test!(test_append_9, 9);
1925 // Two leafs that don't need fixing.
1926 create_append_test!(test_append_17, 17);
1927 // Two leafs where the second one ends up underfull and needs stealing at the end.
1928 create_append_test!(test_append_14, 14);
1929 // Two leafs where the second one ends up empty because the insertion finished at the root.
1930 create_append_test!(test_append_12, 12);
1931 // Three levels; insertion finished at the root.
1932 create_append_test!(test_append_144, 144);
1933 // Three levels; insertion finished at leaf while there is an empty node on the second level.
1934 create_append_test!(test_append_145, 145);
1935 // Tests for several randomly chosen sizes.
1936 create_append_test!(test_append_170, 170);
1937 create_append_test!(test_append_181, 181);
1938 #[cfg(not(miri))] // Miri is too slow
1939 create_append_test!(test_append_239, 239);
1940 #[cfg(not(miri))] // Miri is too slow
1941 create_append_test!(test_append_1700, 1700);
1942
1943 #[test]
1944 fn test_append_drop_leak() {
1945 let a = CrashTestDummy::new(0);
1946 let b = CrashTestDummy::new(1);
1947 let c = CrashTestDummy::new(2);
1948 let mut left = BTreeMap::new();
1949 let mut right = BTreeMap::new();
1950 left.insert(a.spawn(Panic::Never), ());
1951 left.insert(b.spawn(Panic::InDrop), ()); // first duplicate key, dropped during append
1952 left.insert(c.spawn(Panic::Never), ());
1953 right.insert(b.spawn(Panic::Never), ());
1954 right.insert(c.spawn(Panic::Never), ());
1955
1956 catch_unwind(move || left.append(&mut right)).unwrap_err();
1957 assert_eq!(a.dropped(), 1);
1958 assert_eq!(b.dropped(), 1); // should be 2 were it not for Rust issue #47949
1959 assert_eq!(c.dropped(), 2);
1960 }
1961
1962 #[test]
1963 fn test_append_ord_chaos() {
1964 let mut map1 = BTreeMap::new();
1965 map1.insert(Cyclic3::A, ());
1966 map1.insert(Cyclic3::B, ());
1967 let mut map2 = BTreeMap::new();
1968 map2.insert(Cyclic3::A, ());
1969 map2.insert(Cyclic3::B, ());
1970 map2.insert(Cyclic3::C, ()); // lands first, before A
1971 map2.insert(Cyclic3::B, ()); // lands first, before C
1972 map1.check();
1973 map2.check(); // keys are not unique but still strictly ascending
1974 assert_eq!(map1.len(), 2);
1975 assert_eq!(map2.len(), 4);
1976 map1.append(&mut map2);
1977 assert_eq!(map1.len(), 5);
1978 assert_eq!(map2.len(), 0);
1979 map1.check();
1980 map2.check();
1981 }
1982
1983 fn rand_data(len: usize) -> Vec<(u32, u32)> {
1984 let mut rng = DeterministicRng::new();
1985 Vec::from_iter((0..len).map(|_| (rng.next(), rng.next())))
1986 }
1987
1988 #[test]
1989 fn test_split_off_empty_right() {
1990 let mut data = rand_data(173);
1991
1992 let mut map = BTreeMap::from_iter(data.clone());
1993 let right = map.split_off(&(data.iter().max().unwrap().0 + 1));
1994 map.check();
1995 right.check();
1996
1997 data.sort();
1998 assert!(map.into_iter().eq(data));
1999 assert!(right.into_iter().eq(None));
2000 }
2001
2002 #[test]
2003 fn test_split_off_empty_left() {
2004 let mut data = rand_data(314);
2005
2006 let mut map = BTreeMap::from_iter(data.clone());
2007 let right = map.split_off(&data.iter().min().unwrap().0);
2008 map.check();
2009 right.check();
2010
2011 data.sort();
2012 assert!(map.into_iter().eq(None));
2013 assert!(right.into_iter().eq(data));
2014 }
2015
2016 // In a tree with 3 levels, if all but a part of the first leaf node is split off,
2017 // make sure fix_top eliminates both top levels.
2018 #[test]
2019 fn test_split_off_tiny_left_height_2() {
2020 let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
2021 let mut left: BTreeMap<_, _> = pairs.clone().collect();
2022 let right = left.split_off(&1);
2023 left.check();
2024 right.check();
2025 assert_eq!(left.len(), 1);
2026 assert_eq!(right.len(), MIN_INSERTS_HEIGHT_2 - 1);
2027 assert_eq!(*left.first_key_value().unwrap().0, 0);
2028 assert_eq!(*right.first_key_value().unwrap().0, 1);
2029 }
2030
2031 // In a tree with 3 levels, if only part of the last leaf node is split off,
2032 // make sure fix_top eliminates both top levels.
2033 #[test]
2034 fn test_split_off_tiny_right_height_2() {
2035 let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
2036 let last = MIN_INSERTS_HEIGHT_2 - 1;
2037 let mut left: BTreeMap<_, _> = pairs.clone().collect();
2038 assert_eq!(*left.last_key_value().unwrap().0, last);
2039 let right = left.split_off(&last);
2040 left.check();
2041 right.check();
2042 assert_eq!(left.len(), MIN_INSERTS_HEIGHT_2 - 1);
2043 assert_eq!(right.len(), 1);
2044 assert_eq!(*left.last_key_value().unwrap().0, last - 1);
2045 assert_eq!(*right.last_key_value().unwrap().0, last);
2046 }
2047
2048 #[test]
2049 fn test_split_off_halfway() {
2050 let mut rng = DeterministicRng::new();
2051 for &len in &[NODE_CAPACITY, 25, 50, 75, 100] {
2052 let mut data = Vec::from_iter((0..len).map(|_| (rng.next(), ())));
2053 // Insertion in non-ascending order creates some variation in node length.
2054 let mut map = BTreeMap::from_iter(data.iter().copied());
2055 data.sort();
2056 let small_keys = data.iter().take(len / 2).map(|kv| kv.0);
2057 let large_keys = data.iter().skip(len / 2).map(|kv| kv.0);
2058 let split_key = large_keys.clone().next().unwrap();
2059 let right = map.split_off(&split_key);
2060 map.check();
2061 right.check();
2062 assert!(map.keys().copied().eq(small_keys));
2063 assert!(right.keys().copied().eq(large_keys));
2064 }
2065 }
2066
2067 #[test]
2068 fn test_split_off_large_random_sorted() {
2069 // Miri is too slow
2070 let mut data = if cfg!(miri) { rand_data(529) } else { rand_data(1529) };
2071 // special case with maximum height.
2072 data.sort();
2073
2074 let mut map = BTreeMap::from_iter(data.clone());
2075 let key = data[data.len() / 2].0;
2076 let right = map.split_off(&key);
2077 map.check();
2078 right.check();
2079
2080 assert!(map.into_iter().eq(data.clone().into_iter().filter(|x| x.0 < key)));
2081 assert!(right.into_iter().eq(data.into_iter().filter(|x| x.0 >= key)));
2082 }
2083
2084 #[test]
2085 fn test_into_iter_drop_leak_height_0() {
2086 let a = CrashTestDummy::new(0);
2087 let b = CrashTestDummy::new(1);
2088 let c = CrashTestDummy::new(2);
2089 let d = CrashTestDummy::new(3);
2090 let e = CrashTestDummy::new(4);
2091 let mut map = BTreeMap::new();
2092 map.insert("a", a.spawn(Panic::Never));
2093 map.insert("b", b.spawn(Panic::Never));
2094 map.insert("c", c.spawn(Panic::Never));
2095 map.insert("d", d.spawn(Panic::InDrop));
2096 map.insert("e", e.spawn(Panic::Never));
2097
2098 catch_unwind(move || drop(map.into_iter())).unwrap_err();
2099
2100 assert_eq!(a.dropped(), 1);
2101 assert_eq!(b.dropped(), 1);
2102 assert_eq!(c.dropped(), 1);
2103 assert_eq!(d.dropped(), 1);
2104 assert_eq!(e.dropped(), 1);
2105 }
2106
2107 #[test]
2108 fn test_into_iter_drop_leak_height_1() {
2109 let size = MIN_INSERTS_HEIGHT_1;
2110 for panic_point in vec![0, 1, size - 2, size - 1] {
2111 let dummies: Vec<_> = (0..size).map(|i| CrashTestDummy::new(i)).collect();
2112 let map: BTreeMap<_, _> = (0..size)
2113 .map(|i| {
2114 let panic = if i == panic_point { Panic::InDrop } else { Panic::Never };
2115 (dummies[i].spawn(Panic::Never), dummies[i].spawn(panic))
2116 })
2117 .collect();
2118 catch_unwind(move || drop(map.into_iter())).unwrap_err();
2119 for i in 0..size {
2120 assert_eq!(dummies[i].dropped(), 2);
2121 }
2122 }
2123 }
2124
2125 #[test]
2126 fn test_into_keys() {
2127 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
2128 let map: BTreeMap<_, _> = vec.into_iter().collect();
2129 let keys: Vec<_> = map.into_keys().collect();
2130
2131 assert_eq!(keys.len(), 3);
2132 assert!(keys.contains(&1));
2133 assert!(keys.contains(&2));
2134 assert!(keys.contains(&3));
2135 }
2136
2137 #[test]
2138 fn test_into_values() {
2139 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
2140 let map: BTreeMap<_, _> = vec.into_iter().collect();
2141 let values: Vec<_> = map.into_values().collect();
2142
2143 assert_eq!(values.len(), 3);
2144 assert!(values.contains(&'a'));
2145 assert!(values.contains(&'b'));
2146 assert!(values.contains(&'c'));
2147 }
2148
2149 #[test]
2150 fn test_insert_remove_intertwined() {
2151 let loops = if cfg!(miri) { 100 } else { 1_000_000 };
2152 let mut map = BTreeMap::new();
2153 let mut i = 1;
2154 let offset = 165; // somewhat arbitrarily chosen to cover some code paths
2155 for _ in 0..loops {
2156 i = (i + offset) & 0xFF;
2157 map.insert(i, i);
2158 map.remove(&(0xFF - i));
2159 }
2160 map.check();
2161 }
2162
2163 #[test]
2164 fn test_insert_remove_intertwined_ord_chaos() {
2165 let loops = if cfg!(miri) { 100 } else { 1_000_000 };
2166 let gov = Governor::new();
2167 let mut map = BTreeMap::new();
2168 let mut i = 1;
2169 let offset = 165; // more arbitrarily copied from above
2170 for _ in 0..loops {
2171 i = (i + offset) & 0xFF;
2172 map.insert(Governed(i, &gov), ());
2173 map.remove(&Governed(0xFF - i, &gov));
2174 gov.flip();
2175 }
2176 map.check_invariants();
2177 }