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