| Age | Commit message (Collapse) | Author | Lines |
|---|
|
Fix Debug implementations of some of the HashMap and BTreeMap iterator types
HashMap's `ValuesMut`, BTreeMaps `ValuesMut`, IntoValues and `IntoKeys` structs were printing both keys and values on their Debug implementations. But they are iterators over either keys or values. Irrelevant values should not be visible. With this PR, they only show relevant fields.
This fixes #75297.
[Here's an example code.](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=0c79356ed860e347a0c1a205616f93b7) This prints this on nightly:
```
ValuesMut { inner: IterMut { range: [(1, "hello"), (2, "goodbye")], length: 2 } }
IntoKeys { inner: [(1, "hello"), (2, "goodbye")] }
IntoValues { inner: [(1, "hello"), (2, "goodbye")] }
[(2, "goodbye"), (1, "hello")]
```
After the patch this example prints these instead:
```
["hello", "goodbye"]
["hello", "goodbye"]
[1, 2]
["hello", "goodbye"]
```
I didn't add test cases for them, since I couldn't see any tests for Debug implementations anywhere. But please let me know if I should add it to a specific place.
r? @dtolnay
|
|
|
|
BTreeMap: keep an eye out on the size of the main components
r? @Mark-Simulacrum
|
|
Previously, `BTreeMap` tried to link to `crate::collections`, intending
for the link to go to `std/collections/index.html`. But `BTreeMap` is
defined in `alloc`, so after the fix in the previous commit, the links
instead went to `alloc/collections/index.html`, which has almost no
information.
This changes it to link to `index.html`, which only works when viewing
from `std::collections::BTreeMap`, the most common place to visit the
docs. Fixing it to work from anywhere would require the docs for
`std::collections` to be duplicated in `alloc::collections`, which in
turn would require HashMap to be `alloc` for intra-doc links to work
(https://github.com/rust-lang/rust/issues/74481).
|
|
|
|
|
|
|
|
|
|
|
|
BTreeMap: code readability tweaks
Gathered over the past months
r? @Mark-Simulacrum
|
|
Move to intra-doc links in collections/btree/map.rs and collections/linked_list.rs
Helps with #75080.
@rustbot modify labels: T-doc, A-intra-doc-links
|
|
Test and fix Send and Sync traits of BTreeMap artefacts
Fixes #76686.
I'm not quite sure what all this implies. E.g. comparing with the definitions for `NodeRef` in node.rs, maybe an extra bound `T: 'a` is useful for something. The test compiles on stable/beta (apart from `drain_filter`) so I bet `Sync` is equally desirable.
r? @Mark-Simulacrum
|
|
|
|
|
|
|
|
|
|
|
|
r=jonas-schievink
Remove internal and unstable MaybeUninit::UNINIT.
Looks like it is no longer necessary, as `uninit_array()` can be used instead in the few cases where it was needed.
(I wanted to just add `#[doc(hidden)]` to remove clutter from the documentation, but looks like it can just be removed entirely.)
|
|
BTreeMap: move up reference to map's root from NodeRef
Since the introduction of `NodeRef` years ago, it also contained a mutable reference to the owner of the root node of the tree (somewhat disguised as *const). Its intent is to be used only when the rest of the `NodeRef` is no longer needed. Moving this to where it's actually used, thought me 2 things:
- Some sort of "postponed mutable reference" is required in most places that it is/was used, and that's exactly where we also need to store a reference to the length (number of elements) of the tree, for the same reason. The length reference can be a normal reference, because the tree code does not care about tree length (just length per node).
- It's downright obfuscation in `from_sorted_iter` (transplanted to #75329)
- It's one of the reasons for the scary notice on `reborrow_mut`, the other one being addressed in #73971.
This does repeat the raw pointer code in a few places, but it could be bundled up with the length reference.
r? `@Mark-Simulacrum`
|
|
|
|
|
|
Looks like it is no longer necessary, as uninit_array() can be used
instead in the few cases where it was needed.
|
|
|
|
|
|
first_ptr -> slice_as_ptr
first_ptr_mut -> slice_as_mut_ptr
slice_get_ref -> slice_assume_init_ref
slice_get_mut -> slice_assume_init_mut
|
|
|
|
|
|
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
```
|
|
|
|
|
|
|
|
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.
|
|
|
|
|
|
|
|
|
|
Deriving debug prints all the values including keys. But ValuesMut
struct should only print the values.
|
|
|
|
|
|
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
|
|
BTreeMap: enforce the panic rule imposed by `replace`
Also, reveal the unsafe parts in the closures fed to it.
r? @Mark-Simulacrum
|
|
|
|
|
|
|
