1 use super::super::testing
::crash_test
::{CrashTestDummy, Panic}
;
2 use super::super::testing
::ord_chaos
::{Cyclic3, Governed, Governor}
;
3 use super::super::testing
::rng
::DeterministicRng
;
4 use super::Entry
::{Occupied, Vacant}
;
9 use crate::string
::{String, ToString}
;
11 use std
::cmp
::Ordering
;
12 use std
::convert
::TryFrom
;
13 use std
::iter
::{self, FromIterator}
;
15 use std
::ops
::Bound
::{self, Excluded, Included, Unbounded}
;
16 use std
::ops
::RangeBounds
;
17 use std
::panic
::{catch_unwind, AssertUnwindSafe}
;
18 use std
::sync
::atomic
::{AtomicUsize, Ordering::SeqCst}
;
20 // 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
;
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;
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;
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() {
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();
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();
59 // Check consistency of `length` with what navigation code encounters.
60 assert_eq
!(self.length
, root_node
.calc_length());
62 // Lastly, check the invariant causing the least harm.
63 root_node
.assert_min_len(if root_node
.height() > 0 { 1 }
else { 0 }
);
65 assert_eq
!(self.length
, 0);
68 // Check that `assert_strictly_ascending` will encounter all keys.
69 assert_eq
!(self.length
, self.keys().count());
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.
80 self.check_invariants();
81 self.assert_strictly_ascending();
84 // Returns the height of the root, if any.
85 fn height(&self) -> Option
<usize> {
86 self.root
.as_ref().map(node
::Root
::height
)
89 fn dump_keys(&self) -> String
93 if let Some(root
) = self.root
.as_ref() {
94 root
.reborrow().dump_keys()
96 String
::from("not yet allocated")
100 // Panics if the keys are not in strictly ascending order.
101 fn assert_strictly_ascending(&self)
105 let mut keys
= self.keys();
106 if let Some(mut previous
) = keys
.next() {
108 assert
!(previous
< next
, "{:?} >= {:?}", previous
, next
);
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)
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
);
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
);
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.
144 let mut map
= BTreeMap
::new();
146 assert_eq
!(map
.height(), None
);
147 assert_eq
!(map
.len(), 0);
150 while map
.height() == Some(0) {
151 let last_key
= *map
.last_key_value().unwrap().0;
152 map
.insert(last_key
+ 1, ());
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());
162 while map
.height() == Some(1) {
163 let last_key
= *map
.last_key_value().unwrap().0;
164 map
.insert(last_key
+ 1, ());
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());
178 // Ensures the testing infrastructure usually notices order violations.
181 fn test_check_ord_chaos() {
182 let gov
= Governor
::new();
183 let map
: BTreeMap
<_
, _
> = (0..2).map(|i
| (Governed(i
, &gov
), ())).collect();
188 // Ensures the testing infrastructure doesn't always mind order violations.
190 fn test_check_invariants_ord_chaos() {
191 let gov
= Governor
::new();
192 let map
: BTreeMap
<_
, _
> = (0..2).map(|i
| (Governed(i
, &gov
), ())).collect();
194 map
.check_invariants();
198 fn test_basic_large() {
199 let mut map
= BTreeMap
::new();
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);
206 assert_eq
!(map
.insert(i
, 10 * i
), None
);
207 assert_eq
!(map
.len(), i
+ 1);
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));
216 assert_eq
!(map
.get(&i
).unwrap(), &(i
* 10));
219 for i
in size
..size
* 2 {
220 assert_eq
!(map
.get(&i
), None
);
224 assert_eq
!(map
.insert(i
, 100 * i
), Some(10 * i
));
225 assert_eq
!(map
.len(), size
);
229 assert_eq
!(map
.get(&i
).unwrap(), &(i
* 100));
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);
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));
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);
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));
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));
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));
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));
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));
339 let size
= if cfg
!(miri
) { 200 }
else { 10000 }
;
341 let mut map
: BTreeMap
<_
, _
> = (0..size
).map(|i
| (i
, i
)).collect();
343 fn test
<T
>(size
: usize, mut iter
: T
)
345 T
: Iterator
<Item
= (usize, usize)>,
348 assert_eq
!(iter
.size_hint(), (size
- i
, Some(size
- i
)));
349 assert_eq
!(iter
.next().unwrap(), (i
, i
));
351 assert_eq
!(iter
.size_hint(), (0, Some(0)));
352 assert_eq
!(iter
.next(), None
);
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());
362 let size
= if cfg
!(miri
) { 200 }
else { 10000 }
;
364 let mut map
: BTreeMap
<_
, _
> = (0..size
).map(|i
| (i
, i
)).collect();
366 fn test
<T
>(size
: usize, mut iter
: T
)
368 T
: Iterator
<Item
= (usize, usize)>,
371 assert_eq
!(iter
.size_hint(), (size
- i
, Some(size
- i
)));
372 assert_eq
!(iter
.next().unwrap(), (size
- i
- 1, size
- i
- 1));
374 assert_eq
!(iter
.size_hint(), (0, Some(0)));
375 assert_eq
!(iter
.next(), None
);
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());
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)
385 T
: Copy
+ Debug
+ Ord
+ TryFrom
<usize>,
386 <T
as TryFrom
<usize>>::Error
: Debug
,
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();
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
);
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();
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();
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());
417 #[derive(Clone, Copy, Debug, Eq, PartialEq, PartialOrd, Ord)]
419 struct Align32(usize);
421 impl TryFrom
<usize> for Align32
{
424 fn try_from(s
: usize) -> Result
<Align32
, ()> {
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
);
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());
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"));
466 for value
in a
.values_mut() {
470 let values
: Vec
<String
> = a
.values().cloned().collect();
471 assert_eq
!(values
, [String
::from("hello!"), String
::from("goodbye!")]);
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));
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
);
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.
508 fn test_iter_mixed() {
510 let size
= if cfg
!(miri
) { 200 }
else { 10000 }
;
512 let mut map
: BTreeMap
<_
, _
> = (0..size
).map(|i
| (i
, i
)).collect();
514 fn test
<T
>(size
: usize, mut iter
: T
)
516 T
: Iterator
<Item
= (usize, usize)> + DoubleEndedIterator
,
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));
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
));
527 assert_eq
!(iter
.size_hint(), (0, Some(0)));
528 assert_eq
!(iter
.next(), None
);
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());
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
);
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));
571 fn range_keys(map
: &BTreeMap
<i32, i32>, range
: impl RangeBounds
<i32>) -> Vec
<i32> {
581 fn test_range_small() {
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]]);
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
);
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
![]);
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]);
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.
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]);
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
]);
660 fn test_range_large() {
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]]);
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
);
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
![]);
713 fn check
<'a
, L
, R
>(lhs
: L
, rhs
: R
)
715 L
: IntoIterator
<Item
= (&'a
i32, &'a
i32)>,
716 R
: IntoIterator
<Item
= (&'a
i32, &'a
i32)>,
718 let lhs
: Vec
<_
> = lhs
.into_iter().collect();
719 let rhs
: Vec
<_
> = rhs
.into_iter().collect();
720 assert_eq
!(lhs
, rhs
);
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)]);
729 fn test_range_inclusive_max_value() {
730 let max
= usize::MAX
;
731 let map
: BTreeMap
<_
, _
> = vec
![(max
, 0)].into_iter().collect();
733 assert_eq
!(map
.range(max
..=max
).collect
::<Vec
<_
>>(), &[(&max
, &0)]);
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
);
745 fn test_range_equal_excluded() {
746 let map
: BTreeMap
<_
, _
> = (0..5).map(|i
| (i
, i
)).collect();
747 map
.range((Excluded(2), Excluded(2)));
752 fn test_range_backwards_1() {
753 let map
: BTreeMap
<_
, _
> = (0..5).map(|i
| (i
, i
)).collect();
754 map
.range((Included(3), Included(2)));
759 fn test_range_backwards_2() {
760 let map
: BTreeMap
<_
, _
> = (0..5).map(|i
| (i
, i
)).collect();
761 map
.range((Included(3), Excluded(2)));
766 fn test_range_backwards_3() {
767 let map
: BTreeMap
<_
, _
> = (0..5).map(|i
| (i
, i
)).collect();
768 map
.range((Excluded(3), Included(2)));
773 fn test_range_backwards_4() {
774 let map
: BTreeMap
<_
, _
> = (0..5).map(|i
| (i
, i
)).collect();
775 map
.range((Excluded(3), Excluded(2)));
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
);
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);
797 impl PartialOrd
for EvilTwin
{
798 fn partial_cmp(&self, other
: &Self) -> Option
<Ordering
> {
799 Some(self.cmp(other
))
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 }
811 impl PartialEq
for EvilTwin
{
812 fn eq(&self, other
: &Self) -> bool
{
817 impl Eq
for EvilTwin {}
819 #[derive(PartialEq, Eq, PartialOrd, Ord)]
820 struct CompositeKey(i32, EvilTwin
);
822 impl Borrow
<EvilTwin
> for CompositeKey
{
823 fn borrow(&self) -> &EvilTwin
{
828 let map
= (0..12).map(|i
| (CompositeKey(i
, EvilTwin(i
)), ())).collect
::<BTreeMap
<_
, _
>>();
829 map
.range(EvilTwin(5)..=EvilTwin(7));
833 fn test_range_1000() {
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();
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
));
842 for (kv
, pair
) in kvs
.by_ref().zip(pairs
.by_ref()) {
843 assert_eq
!(kv
, pair
);
845 assert_eq
!(kvs
.next(), None
);
846 assert_eq
!(pairs
.next(), None
);
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
);
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
);
874 let step
= if cfg
!(miri
) { 66 }
else { 1 }
;
875 let map
: BTreeMap
<_
, _
> = (0..size
).map(|i
| (i
, i
)).collect();
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
));
882 for (kv
, pair
) in kvs
.by_ref().zip(pairs
.by_ref()) {
883 assert_eq
!(kv
, pair
);
885 assert_eq
!(kvs
.next(), None
);
886 assert_eq
!(pairs
.next(), None
);
892 fn test_range_mut() {
895 let step
= if cfg
!(miri
) { 66 }
else { 1 }
;
896 let mut map
: BTreeMap
<_
, _
> = (0..size
).map(|i
| (i
, i
)).collect();
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
));
903 for (kv
, pair
) in kvs
.by_ref().zip(pairs
.by_ref()) {
904 assert_eq
!(kv
, pair
);
906 assert_eq
!(kvs
.next(), None
);
907 assert_eq
!(pairs
.next(), None
);
915 let mut map
: BTreeMap
<i32, i32> = (0..100).map(|x
| (x
, x
* 10)).collect();
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);
924 mod test_drain_filter
{
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());
935 // Explicitly consumes the iterator, where most test cases drop it instantly.
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()));
944 // Explicitly consumes the iterator, where most test cases drop it instantly.
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());
954 // Explicitly consumes the iterator and modifies values through it.
956 fn mutating_and_keeping() {
957 let pairs
= (0..3).map(|i
| (i
, i
));
958 let mut map
: BTreeMap
<_
, _
> = pairs
.collect();
960 map
.drain_filter(|_
, v
| {
966 assert
!(map
.keys().copied().eq(0..3));
967 assert
!(map
.values().copied().eq(6..9));
971 // Explicitly consumes the iterator and modifies values through it.
973 fn mutating_and_removing() {
974 let pairs
= (0..3).map(|i
| (i
, i
));
975 let mut map
: BTreeMap
<_
, _
> = pairs
.collect();
977 map
.drain_filter(|_
, v
| {
981 .eq((0..3).map(|i
| (i
, i
+ 6)))
983 assert
!(map
.is_empty());
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));
997 fn underfull_removing_one() {
998 let pairs
= (0..3).map(|i
| (i
, i
));
1000 let mut map
: BTreeMap
<_
, _
> = pairs
.clone().collect();
1001 map
.drain_filter(|i
, _
| *i
== doomed
);
1002 assert_eq
!(map
.len(), 2);
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
));
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());
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
));
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);
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
));
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());
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);
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());
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);
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
));
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);
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
));
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());
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
), ());
1147 catch_unwind(move || drop(map
.drain_filter(|dummy
, _
| dummy
.query(true)))).unwrap_err();
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);
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
), ());
1167 catch_unwind(AssertUnwindSafe(|| drop(map
.drain_filter(|dummy
, _
| dummy
.query(true)))))
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);
1182 // Same as above, but attempt to use the iterator again after the panic in the predicate
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
), ());
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
)));
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);
1217 // make sure these compile -- using the Borrow trait
1219 let mut map
= BTreeMap
::new();
1220 map
.insert("0".to_string(), 1);
1221 assert_eq
!(map
["0"], 1);
1225 let mut map
= BTreeMap
::new();
1226 map
.insert(Box
::new(0), 1);
1227 assert_eq
!(map
[&0], 1);
1231 let mut map
= BTreeMap
::new();
1232 map
.insert(Box
::new([0, 1]) as Box
<[i32]>, 1);
1233 assert_eq
!(map
[&[0, 1][..]], 1);
1237 let mut map
= BTreeMap
::new();
1238 map
.insert(Rc
::new(0), 1);
1239 assert_eq
!(map
[&0], 1);
1243 fn get
<T
: Ord
>(v
: &BTreeMap
<Box
<T
>, ()>, t
: &T
) {
1248 fn get_mut
<T
: Ord
>(v
: &mut BTreeMap
<Box
<T
>, ()>, t
: &T
) {
1253 fn get_key_value
<T
: Ord
>(v
: &BTreeMap
<Box
<T
>, ()>, t
: &T
) {
1258 fn contains_key
<T
: Ord
>(v
: &BTreeMap
<Box
<T
>, ()>, t
: &T
) {
1263 fn range
<T
: Ord
>(v
: &BTreeMap
<Box
<T
>, ()>, t
: T
) {
1268 fn range_mut
<T
: Ord
>(v
: &mut BTreeMap
<Box
<T
>, ()>, t
: T
) {
1273 fn remove
<T
: Ord
>(v
: &mut BTreeMap
<Box
<T
>, ()>, t
: &T
) {
1278 fn remove_entry
<T
: Ord
>(v
: &mut BTreeMap
<Box
<T
>, ()>, t
: &T
) {
1283 fn split_off
<T
: Ord
>(v
: &mut BTreeMap
<Box
<T
>, ()>, t
: &T
) {
1290 let xs
= [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
1292 let mut map
: BTreeMap
<_
, _
> = xs
.iter().cloned().collect();
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);
1302 assert_eq
!(map
.get(&1).unwrap(), &100);
1303 assert_eq
!(map
.len(), 6);
1305 // Existing key (update)
1306 match map
.entry(2) {
1307 Vacant(_
) => unreachable
!(),
1308 Occupied(mut view
) => {
1309 let v
= view
.get_mut();
1313 assert_eq
!(map
.get(&2).unwrap(), &200);
1314 assert_eq
!(map
.len(), 6);
1317 // Existing key (take)
1318 match map
.entry(3) {
1319 Vacant(_
) => unreachable
!(),
1321 assert_eq
!(view
.remove(), 30);
1324 assert_eq
!(map
.get(&3), None
);
1325 assert_eq
!(map
.len(), 5);
1328 // Inexistent key (insert)
1329 match map
.entry(10) {
1330 Occupied(_
) => unreachable
!(),
1332 assert_eq
!(*view
.insert(1000), 1000);
1335 assert_eq
!(map
.get(&10).unwrap(), &1000);
1336 assert_eq
!(map
.len(), 6);
1341 fn test_extend_ref() {
1342 let mut a
= BTreeMap
::new();
1344 let mut b
= BTreeMap
::new();
1346 b
.insert(3, "three");
1350 assert_eq
!(a
.len(), 3);
1351 assert_eq
!(a
[&1], "one");
1352 assert_eq
!(a
[&2], "two");
1353 assert_eq
!(a
[&3], "three");
1359 let mut m
= BTreeMap
::new();
1360 assert_eq
!(m
.len(), 0);
1362 assert_eq
!(m
.insert((), ()), None
);
1363 assert_eq
!(m
.len(), 1);
1365 assert_eq
!(m
.insert((), ()), Some(()));
1366 assert_eq
!(m
.len(), 1);
1367 assert_eq
!(m
.iter().count(), 1);
1370 assert_eq
!(m
.len(), 0);
1376 assert_eq
!(m
.len(), 1);
1377 assert_eq
!(m
.iter().count(), 1);
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
1386 #[derive(Clone, Copy, Debug)]
1389 impl PartialEq
for Bad
{
1390 fn eq(&self, _
: &Self) -> bool
{
1397 impl PartialOrd
for Bad
{
1398 fn partial_cmp(&self, _
: &Self) -> Option
<Ordering
> {
1399 Some(Ordering
::Less
)
1404 fn cmp(&self, _
: &Self) -> Ordering
{
1409 let mut m
= BTreeMap
::new();
1419 let mut map
= BTreeMap
::new();
1420 for &len
in &[MIN_INSERTS_HEIGHT_1
, MIN_INSERTS_HEIGHT_2
, 0, NODE_CAPACITY
] {
1424 assert_eq
!(map
.len(), len
);
1427 assert
!(map
.is_empty());
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);
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
), ());
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);
1449 assert_eq
!(a
.dropped(), 1);
1450 assert_eq
!(b
.dropped(), 1);
1451 assert_eq
!(c
.dropped(), 1);
1456 let mut map
= BTreeMap
::new();
1457 let size
= MIN_INSERTS_HEIGHT_1
;
1458 assert_eq
!(map
.len(), 0);
1461 assert_eq
!(map
.insert(i
, 10 * i
), None
);
1462 assert_eq
!(map
.len(), i
+ 1);
1464 assert_eq
!(map
, map
.clone());
1468 assert_eq
!(map
.insert(i
, 100 * i
), Some(10 * i
));
1469 assert_eq
!(map
.len(), size
);
1471 assert_eq
!(map
, map
.clone());
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);
1478 assert_eq
!(map
, map
.clone());
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);
1486 assert_eq
!(map
, map
.clone());
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());
1494 assert_eq
!(map
.len(), MIN_INSERTS_HEIGHT_2
);
1495 assert_eq
!(map
, map
.clone());
1500 fn test_clone_panic_leak() {
1501 let a
= CrashTestDummy
::new(0);
1502 let b
= CrashTestDummy
::new(1);
1503 let c
= CrashTestDummy
::new(2);
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
), ());
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);
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);
1529 fn test_clone_from() {
1530 let mut map1
= BTreeMap
::new();
1531 let max_size
= MIN_INSERTS_HEIGHT_1
;
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();
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);
1545 map2
.clone_from(&map1
); // same length
1547 assert_eq
!(map2
, map1
);
1548 map1
.insert(i
, 10 * i
);
1554 fn test_variance() {
1555 fn map_key
<'new
>(v
: BTreeMap
<&'
static str, ()>) -> BTreeMap
<&'new
str, ()> {
1558 fn map_val
<'new
>(v
: BTreeMap
<(), &'
static str>) -> BTreeMap
<(), &'new
str> {
1562 fn iter_key
<'a
, 'new
>(v
: Iter
<'a
, &'
static str, ()>) -> Iter
<'a
, &'new
str, ()> {
1565 fn iter_val
<'a
, 'new
>(v
: Iter
<'a
, (), &'
static str>) -> Iter
<'a
, (), &'new
str> {
1569 fn into_iter_key
<'new
>(v
: IntoIter
<&'
static str, ()>) -> IntoIter
<&'new
str, ()> {
1572 fn into_iter_val
<'new
>(v
: IntoIter
<(), &'
static str>) -> IntoIter
<(), &'new
str> {
1576 fn into_keys_key
<'new
>(v
: IntoKeys
<&'
static str, ()>) -> IntoKeys
<&'new
str, ()> {
1579 fn into_keys_val
<'new
>(v
: IntoKeys
<(), &'
static str>) -> IntoKeys
<(), &'new
str> {
1583 fn into_values_key
<'new
>(v
: IntoValues
<&'
static str, ()>) -> IntoValues
<&'new
str, ()> {
1586 fn into_values_val
<'new
>(v
: IntoValues
<(), &'
static str>) -> IntoValues
<(), &'new
str> {
1590 fn range_key
<'a
, 'new
>(v
: Range
<'a
, &'
static str, ()>) -> Range
<'a
, &'new
str, ()> {
1593 fn range_val
<'a
, 'new
>(v
: Range
<'a
, (), &'
static str>) -> Range
<'a
, (), &'new
str> {
1597 fn keys_key
<'a
, 'new
>(v
: Keys
<'a
, &'
static str, ()>) -> Keys
<'a
, &'new
str, ()> {
1600 fn keys_val
<'a
, 'new
>(v
: Keys
<'a
, (), &'
static str>) -> Keys
<'a
, (), &'new
str> {
1604 fn values_key
<'a
, 'new
>(v
: Values
<'a
, &'
static str, ()>) -> Values
<'a
, &'new
str, ()> {
1607 fn values_val
<'a
, 'new
>(v
: Values
<'a
, (), &'
static str>) -> Values
<'a
, (), &'new
str> {
1614 fn map
<T
: Sync
>(v
: &BTreeMap
<T
, T
>) -> impl Sync
+ '_
{
1618 fn into_iter
<T
: Sync
>(v
: BTreeMap
<T
, T
>) -> impl Sync
{
1622 fn into_keys
<T
: Sync
+ Ord
>(v
: BTreeMap
<T
, T
>) -> impl Sync
{
1626 fn into_values
<T
: Sync
+ Ord
>(v
: BTreeMap
<T
, T
>) -> impl Sync
{
1630 fn drain_filter
<T
: Sync
+ Ord
>(v
: &mut BTreeMap
<T
, T
>) -> impl Sync
+ '_
{
1631 v
.drain_filter(|_
, _
| false)
1634 fn iter
<T
: Sync
>(v
: &BTreeMap
<T
, T
>) -> impl Sync
+ '_
{
1638 fn iter_mut
<T
: Sync
>(v
: &mut BTreeMap
<T
, T
>) -> impl Sync
+ '_
{
1642 fn keys
<T
: Sync
>(v
: &BTreeMap
<T
, T
>) -> impl Sync
+ '_
{
1646 fn values
<T
: Sync
>(v
: &BTreeMap
<T
, T
>) -> impl Sync
+ '_
{
1650 fn values_mut
<T
: Sync
>(v
: &mut BTreeMap
<T
, T
>) -> impl Sync
+ '_
{
1654 fn range
<T
: Sync
+ Ord
>(v
: &BTreeMap
<T
, T
>) -> impl Sync
+ '_
{
1658 fn range_mut
<T
: Sync
+ Ord
>(v
: &mut BTreeMap
<T
, T
>) -> impl Sync
+ '_
{
1662 fn entry
<T
: Sync
+ Ord
+ Default
>(v
: &mut BTreeMap
<T
, T
>) -> impl Sync
+ '_
{
1663 v
.entry(Default
::default())
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
!(),
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
!(),
1683 fn map
<T
: Send
>(v
: BTreeMap
<T
, T
>) -> impl Send
{
1687 fn into_iter
<T
: Send
>(v
: BTreeMap
<T
, T
>) -> impl Send
{
1691 fn into_keys
<T
: Send
+ Ord
>(v
: BTreeMap
<T
, T
>) -> impl Send
{
1695 fn into_values
<T
: Send
+ Ord
>(v
: BTreeMap
<T
, T
>) -> impl Send
{
1699 fn drain_filter
<T
: Send
+ Ord
>(v
: &mut BTreeMap
<T
, T
>) -> impl Send
+ '_
{
1700 v
.drain_filter(|_
, _
| false)
1703 fn iter
<T
: Send
+ Sync
>(v
: &BTreeMap
<T
, T
>) -> impl Send
+ '_
{
1707 fn iter_mut
<T
: Send
>(v
: &mut BTreeMap
<T
, T
>) -> impl Send
+ '_
{
1711 fn keys
<T
: Send
+ Sync
>(v
: &BTreeMap
<T
, T
>) -> impl Send
+ '_
{
1715 fn values
<T
: Send
+ Sync
>(v
: &BTreeMap
<T
, T
>) -> impl Send
+ '_
{
1719 fn values_mut
<T
: Send
>(v
: &mut BTreeMap
<T
, T
>) -> impl Send
+ '_
{
1723 fn range
<T
: Send
+ Sync
+ Ord
>(v
: &BTreeMap
<T
, T
>) -> impl Send
+ '_
{
1727 fn range_mut
<T
: Send
+ Ord
>(v
: &mut BTreeMap
<T
, T
>) -> impl Send
+ '_
{
1731 fn entry
<T
: Send
+ Ord
+ Default
>(v
: &mut BTreeMap
<T
, T
>) -> impl Send
+ '_
{
1732 v
.entry(Default
::default())
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
!(),
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
!(),
1751 fn test_ord_absence() {
1752 fn map
<K
>(mut map
: BTreeMap
<K
, ()>) {
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());
1778 format
!("{:?}", map
.into_iter());
1780 format
!("{:?}", map
.into_keys());
1782 format
!("{:?}", map
.into_values());
1786 fn map_clone
<K
: Clone
>(mut map
: BTreeMap
<K
, ()>) {
1787 map
.clone_from(&map
.clone());
1793 const MAP
: &'
static BTreeMap
<(), ()> = &BTreeMap
::new();
1794 const LEN
: usize = MAP
.len();
1795 const IS_EMPTY
: bool
= MAP
.is_empty();
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
);
1808 match a
.entry(key
) {
1809 Vacant(_
) => panic
!(),
1810 Occupied(e
) => assert_eq
!(key
, *e
.key()),
1812 assert_eq
!(a
.len(), 1);
1813 assert_eq
!(a
[key
], value
);
1818 fn test_vacant_entry_key() {
1819 let mut a
= BTreeMap
::new();
1820 let key
= "hello there";
1821 let value
= "value goes here";
1823 assert
!(a
.is_empty());
1824 match a
.entry(key
) {
1825 Occupied(_
) => panic
!(),
1827 assert_eq
!(key
, *e
.key());
1831 assert_eq
!(a
.len(), 1);
1832 assert_eq
!(a
[key
], value
);
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());
1842 assert_eq
!(a
.first_entry().unwrap().key(), &1);
1843 assert_eq
!(a
.last_entry().unwrap().key(), &1);
1845 assert_eq
!(a
.first_entry().unwrap().key(), &1);
1846 assert_eq
!(a
.last_entry().unwrap().key(), &2);
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();
1853 let (k2
, v2
) = a
.last_entry().unwrap().remove_entry();
1856 assert_eq
!(a
.first_entry().unwrap().key(), &1);
1857 assert_eq
!(a
.last_entry().unwrap().key(), &1);
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());
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();
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
);
1882 assert
!(map
.insert(pos
* 2, ()).is_none());
1887 macro_rules
! create_append_test
{
1888 ($name
:ident
, $len
:expr
) => {
1891 let mut a
= BTreeMap
::new();
1896 let mut b
= BTreeMap
::new();
1903 assert_eq
!(a
.len(), $len
);
1904 assert_eq
!(b
.len(), 0);
1908 assert_eq
!(a
[&i
], i
);
1910 assert_eq
!(a
[&i
], 2 * i
);
1915 assert_eq
!(a
.remove(&($len
- 1)), Some(2 * ($len
- 1)));
1916 assert_eq
!(a
.insert($len
- 1, 20), None
);
1922 // These are mostly for testing the algorithm that "fixes" the right edge after insertion.
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);
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
), ());
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);
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
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);
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())))
1989 fn test_split_off_empty_right() {
1990 let mut data
= rand_data(173);
1992 let mut map
= BTreeMap
::from_iter(data
.clone());
1993 let right
= map
.split_off(&(data
.iter().max().unwrap().0 + 1));
1998 assert
!(map
.into_iter().eq(data
));
1999 assert
!(right
.into_iter().eq(None
));
2003 fn test_split_off_empty_left() {
2004 let mut data
= rand_data(314);
2006 let mut map
= BTreeMap
::from_iter(data
.clone());
2007 let right
= map
.split_off(&data
.iter().min().unwrap().0);
2012 assert
!(map
.into_iter().eq(None
));
2013 assert
!(right
.into_iter().eq(data
));
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.
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);
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);
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.
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
);
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
);
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());
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
);
2062 assert
!(map
.keys().copied().eq(small_keys
));
2063 assert
!(right
.keys().copied().eq(large_keys
));
2068 fn test_split_off_large_random_sorted() {
2070 let mut data
= if cfg
!(miri
) { rand_data(529) }
else { rand_data(1529) }
;
2071 // special case with maximum height.
2074 let mut map
= BTreeMap
::from_iter(data
.clone());
2075 let key
= data
[data
.len() / 2].0;
2076 let right
= map
.split_off(&key
);
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
)));
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
));
2098 catch_unwind(move || drop(map
.into_iter())).unwrap_err();
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);
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
)
2114 let panic
= if i
== panic_point { Panic::InDrop }
else { Panic::Never }
;
2115 (dummies
[i
].spawn(Panic
::Never
), dummies
[i
].spawn(panic
))
2118 catch_unwind(move || drop(map
.into_iter())).unwrap_err();
2120 assert_eq
!(dummies
[i
].dropped(), 2);
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();
2131 assert_eq
!(keys
.len(), 3);
2132 assert
!(keys
.contains(&1));
2133 assert
!(keys
.contains(&2));
2134 assert
!(keys
.contains(&3));
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();
2143 assert_eq
!(values
.len(), 3);
2144 assert
!(values
.contains(&'a'
));
2145 assert
!(values
.contains(&'b'
));
2146 assert
!(values
.contains(&'c'
));
2150 fn test_insert_remove_intertwined() {
2151 let loops
= if cfg
!(miri
) { 100 }
else { 1_000_000 }
;
2152 let mut map
= BTreeMap
::new();
2154 let offset
= 165; // somewhat arbitrarily chosen to cover some code paths
2156 i
= (i
+ offset
) & 0xFF;
2158 map
.remove(&(0xFF - i
));
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();
2169 let offset
= 165; // more arbitrarily copied from above
2171 i
= (i
+ offset
) & 0xFF;
2172 map
.insert(Governed(i
, &gov
), ());
2173 map
.remove(&Governed(0xFF - i
, &gov
));
2176 map
.check_invariants();