| Age | Commit message (Collapse) | Author | Lines |
|---|
|
|
|
|
|
|
|
BTreeMap: check some invariants in unit tests
|
|
|
|
|
|
Don't panic in Vec::shrink_to_fit
We can help the compiler see that `Vec::shrink_to_fit` will never reach the panic case in `RawVec::shrink_to_fit`, just by guarding the call only for cases where the capacity is strictly greater. A capacity less than the length is only possible through an unsafe call to `set_len`, which would break the `Vec` invariants, so `shrink_to_fit` can just ignore that.
This removes the panicking code from the examples in both #71861 and #75636.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Revert the fundamental changes in #74762 and #75257
Before possibly going over to #75487. Also contains some added and fixed comments.
r? @Mark-Simulacrum
|
|
|
|
Migrate unit tests of btree collections to their native breeding ground
There's one BTreeSet test case that I couldn't easily convince to come along, maybe because it truly is an integration test. But leaving it in place would mean git wouldn't see the move so I also moved it to a new file.
r? @Mark-Simulacrum
|
|
BTreeMap: refactor splitpoint and move testing over to unit test
r? @Mark-Simulacrum
|
|
BTreeMap: purge innocent use of into_kv_mut
Replace the use of `into_kv_mut` into more precise calls. This makes more sense if you know that the single remaining use of `into_kv_mut` is in fact evil and can be trialled in court (#75200) and sent to a correction facility (#73971).
No real performance difference reported (but functions that might benefit a tiny constant bit like `BTreeMap::get_mut` aren't benchmarked):
```
benchcmp old new --threshold 5
name old ns/iter new ns/iter diff ns/iter diff % speedup
btree::map::clone_fat_100 63,073 59,256 -3,817 -6.05% x 1.06
btree::map::iter_100 3,514 3,235 -279 -7.94% x 1.09
```
|
|
Remove liballoc unneeded explicit link
|
|
|
|
|
|
|
|
Stop BTreeMap casts from reborrowing
Down in btree/node.rs, the interface and use of `cast_unchecked` look a bit shady. It's really just there for inverting `forget_type` which does not borrow. By borrowing we can't write the same `cast_unchecked` in the same way at the Handle level.
No change in undefined behaviour or performance.
|
|
|
|
Co-authored-by: Joshua Nelson <joshua@yottadb.com>
|
|
|
|
|
|
|
|
Hard way to respect BTreeMap's minimum node length
Resolves #74834 the hard way (though not the hardest imaginable).
Benchmarks (which are all biased/realistic, inserting keys in ascending order) say:
```
benchcmp r0 r1 --threshold 10
name r0 ns/iter r1 ns/iter diff ns/iter diff % speedup
btree::map::clone_slim_100_and_clear 2,183 2,723 540 24.74% x 0.80
btree::map::clone_slim_100_and_drain_all 3,652 4,173 521 14.27% x 0.88
btree::map::clone_slim_100_and_drain_half 3,320 3,940 620 18.67% x 0.84
btree::map::clone_slim_100_and_into_iter 2,154 2,717 563 26.14% x 0.79
btree::map::clone_slim_100_and_pop_all 3,372 3,870 498 14.77% x 0.87
btree::map::clone_slim_100_and_remove_all 5,111 5,647 536 10.49% x 0.91
btree::map::clone_slim_100_and_remove_half 3,259 3,821 562 17.24% x 0.85
btree::map::iter_0 1,733 1,509 -224 -12.93% x 1.15
btree::map::iter_100 2,714 3,739 1,025 37.77% x 0.73
btree::map::iter_10k 3,728 4,269 541 14.51% x 0.87
btree::map::range_unbounded_unbounded 28,426 36,631 8,205 28.86% x 0.78
btree::map::range_unbounded_vs_iter 28,808 34,056 5,248 18.22% x 0.85
```
This difference is not caused by the `debug_assert`-related code in the function `splitpoint`, it's the same without.
|
|
|
|
|
|
|
|
fix wrong word in documentation
Change "two" to "three", since there are three significantly different things printed below that sentence:
---
While these:
```rust
println!("{}, `{name:.*}` has 3 fractional digits", "Hello", 3, name=1234.56);
println!("{}, `{name:.*}` has 3 characters", "Hello", 3, name="1234.56");
println!("{}, `{name:>8.*}` has 3 right-aligned characters", "Hello", 3, name="1234.56");
```
print two significantly different things:
``` rust
Hello, `1234.560` has 3 fractional digits
Hello, `123` has 3 characters
Hello, ` 123` has 3 right-aligned characters
```
---
[`https://doc.rust-lang.org/std/fmt/#precision`](https://doc.rust-lang.org/std/fmt/#precision)
|
|
|
|
there are three significantly different things printed below
|
|
`range` is not an element, it is a variable.
|
|
|
|
Deriving debug prints all the values including keys. But ValuesMut
struct should only print the values.
|
|
|
|
|
|
|
|
*const T is also used in the same parts and also used for arith_offset.
|
|
|
|
Consistent variable name alloc for raw_vec
|
|
Implement `into_keys` and `into_values` for associative maps
This PR implements `into_keys` and `into_values` for HashMap and BTreeMap types. They are implemented as unstable, under `map_into_keys_values` feature.
Fixes #55214.
r? @dtolnay
|
|
|
|
|
|
BTreeMap: better way to postpone root access in DrainFilter
A slightly more elegant (in my opinion) adaptation of #74762. Benchmarks seem irrationally pleased to:
```
benchcmp old new --threshold 5
name old ns/iter new ns/iter diff ns/iter diff % speedup
btree::map::clone_fat_100_and_remove_all 215,182 185,052 -30,130 -14.00% x 1.16
btree::map::clone_fat_100_and_remove_half 139,667 127,945 -11,722 -8.39% x 1.09
btree::map::clone_fat_val_100_and_remove_all 96,755 81,279 -15,476 -16.00% x 1.19
btree::map::clone_fat_val_100_and_remove_half 64,678 56,911 -7,767 -12.01% x 1.14
btree::map::find_rand_100 18 17 -1 -5.56% x 1.06
btree::map::first_and_last_0 33 35 2 6.06% x 0.94
btree::map::first_and_last_100 40 54 14 35.00% x 0.74
btree::map::insert_rand_100 45 42 -3 -6.67% x 1.07
btree::map::insert_rand_10_000 45 41 -4 -8.89% x 1.10
btree::map::iter_0 2,010 1,759 -251 -12.49% x 1.14
btree::map::iter_100 3,514 2,764 -750 -21.34% x 1.27
btree::map::iter_10k 4,018 3,768 -250 -6.22% x 1.07
btree::map::range_unbounded_unbounded 37,269 28,929 -8,340 -22.38% x 1.29
btree::map::range_unbounded_vs_iter 31,518 28,814 -2,704 -8.58% x 1.09
```
r? @Mark-Simulacrum
|
