| Age | Commit message (Collapse) | Author | Lines |
|---|
|
BTreeMap: split off most code of append
To complete #78056, move the last single-purpose pieces of code out of map.rs into a separate module. Also, tweaked documentation and safeness - I doubt think this code would be safe if the iterators passed in wouldn't be as sorted as the method says they should be - and bounds on MergeIterInner.
r? ```@Mark-Simulacrum```
|
|
|
|
fix some incorrect aliasing in the BTree
This line is wrong:
```
ptr::copy(slice.as_ptr().add(idx), slice.as_mut_ptr().add(idx + 1), slice.len() - idx);
```
When `slice.as_mut_ptr()` is called, that creates a mutable reference to the entire slice, which invalidates the raw pointer previously returned by `slice.as_ptr()`. (Miri currently misses this because raw pointers are not tracked properly.)
Cc ````````@ssomers````````
|
|
BTreeMap: stop mistaking node for an orderly place
A second mistake in #77612 was to ignore the node module's rightful comment "this module doesn't care whether the entries are sorted". And there's a much simpler way to visit the keys in order, if you check this separately from a single pass checking everything.
r? ````````@Mark-Simulacrum````````
|
|
|
|
BTreeMap: document a curious assumption in test cases
r? ```@Mark-Simulacrum```
|
|
- BTreeMap::len
- BTreeMap::is_empty
- BTreeSet::len
- BTreeSet::is_empty
|
|
|
|
|
|
|
|
BTreeMap: move generic support functions out of navigate.rs
A preparatory step chipped off #78104, useful in general (if at all).
r? `@Mark-Simulacrum`
|
|
Support custom allocators in `Box`
r? `@Amanieu`
This pull request requires a crater run.
### Prior work:
- #71873
- #58457
- [`alloc-wg`](https://github.com/TimDiekmann/alloc-wg)-crate
Currently blocked on:
- ~#77118~
- ~https://github.com/rust-lang/chalk/issues/615 (#77515)~
|
|
|
|
btree: merge the implementations of MergeIter
Also remove the gratuitous Copy bounds. Same benchmark performance.
r? `@Mark-Simulacrum`
|
|
|
|
|
|
|
|
BTreeMap: split off most code of remove and split_off
Putting map.rs on a diet, in addition to #77851.
r? @dtolnay
|
|
|
|
|
|
|
|
|
|
BTreeMap: refactor Entry out of map.rs into its own file
btree/map.rs is approaching the 3000 line mark, splitting out the entry
code buys about 500 lines of headroom.
I've created this PR because the changes I've made in #77438 will push `map.rs` over the 3000 line limit and cause tidy to complain.
I picked `Entry` to factor out because it feels less tightly coupled to the rest of `BTreeMap` than the various iterator implementations.
Related: #60302
|
|
BTreeMap: improve gdb introspection of BTreeMap with ZST keys or values
I accidentally pushed an earlier revision in #77788: it changes the index of tuples for BTreeSet from ""[{}]".format(i) to "key{}".format(i). Which doesn't seem to make the slightest difference on my linux box nor on CI. In fact, gdb doesn't make any distinction between "key{}" and "val{}" for a BTreeMap either, leading to confusing output if you test more. But easy to improve.
r? @Mark-Simulacrum
|
|
|
|
|
|
|
|
BTreeMap: type-specific variants of node_as_mut and cast_unchecked
Improves debug checking and shortens some expressions. Extracted from #77408
|
|
btree/map.rs is approaching the 3000 line mark, splitting out the entry
code buys about 500 lines of headroom
|
|
BTreeMap: comment why drain_filter's size_hint is somewhat pessimistic
The `size_hint` of the `DrainFilter` iterator doesn't adjust as you iterate. This hardly seems important to me, but there has been a comparable PR #64383 in the past. I guess a scenario is that you first iterate half the map manually and keep most of the key/value pairs in the map, and then tell the predicate to drain most of the key/value pairs and `.collect` the iterator over the remaining half of the map.
I am totally ambivalent whether this is better or not.
r? @Mark-Simulacrum
|
|
Remove `Box::leak_with_alloc`
Add leak-test for box with allocator
Rename `AllocErr` to `AllocError` in leak-test
Add `Box::alloc` and adjust examples to use the new API
|
|
|
|
BTreeMap: refactoring around edges, missed spots
Tweaks from #77244 (and more) that are really inconsistencies in #77005.
r? @Mark-Simulacrum
|
|
r=Mark-Simulacrum
BTreeMap: admit the existence of leaf edges in comments
The btree code is ambiguous about leaf edges (i.e., edges within leaf nodes). Iteration relies on them heavily, but some of the comments suggest there are no leaf edges (extracted from #77025)
r? @Mark-Simulacrum
|
|
BTreeMap: complete the compile-time test_variance test case
Some of the items added to the new `test_sync` belonged in the old `test_variance` as well. And fixed inconsistent paths to nearby modules.
r? @Mark-Simulacrum
|
|
BTreeMap: document DrainFilterInner better
r? @Mark-Simulacrum
|
|
|
|
|
|
|
|
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).
|
|
|
|
|
|
|
|
|
|
|
