| Age | Commit message (Collapse) | Author | Lines |
|---|
|
Add example of using the indexing operator to HashMap docs
Fixes #52575
|
|
|
|
Stabilize Vec(Deque)::resize_with
Closes #41758
|
|
Add unstable VecDeque::rotate_{left|right}
Like the ones on slices, but more efficient because vecdeque is a circular buffer.
Issue that proposed this: https://github.com/rust-lang/rust/issues/56686
~~:bomb: Please someone look very carefully at the `unsafe` in this! The `wrap_copy` seems to be exactly what this method needs, and the `len` passed to it is never more than half the length of the deque, but I haven't managed to prove to myself that it's correct :bomb:~~ I think I proved that this code meets the requirement of the unsafe code it's calling; please double-check, of course.
|
|
Closes #41758
|
|
Document time of back operations of a Linked List
Popping and pushing from the end of a linked list is constant time. This
documentation is already there for popping and pushing from the front.
@bors: r+ 38fe8d2 rollup
|
|
Fix BTreeMap UB
BTreeMap currently causes UB by created a shared reference to a too-small allocation. This PR fixes that by introducing a `NodeHeader` type and using that until we really need access to the key/value arrays. Avoiding run-time checks in `into_key_slice` was somewhat tricky, see the comments embedded in the code.
I also adjusted `as_leaf_mut` to return a raw pointer, because creating a mutable reference asserts that there are no aliases to the pointee, but that's not always correct: We use `as_leaf_mut` twice to create two mutable slices for keys and values; the second call overlaps with the first slice and hence is not a unique pointer.
Fixes https://github.com/rust-lang/rust/issues/54957
Cc @nikomatsakis @Gankro
|
|
|
|
|
|
VecDeque: fix for stacked borrows
`VecDeque` violates a version of stacked borrows where creating a shared reference is not enough to make a location *mutably accessible* from raw pointers (and I think that is the version we want). There are two problems:
* Creating a `NonNull<T>` from `&mut T` goes through `&T` (inferred for a `_`), then `*const T`, then `NonNull<T>`. That means in this stricter version of Stacked Borrows, we cannot actually write to such a `NonNull` because it was created from a shared reference! This PR fixes that by going from `&mut T` to `*mut T` to `*const T`.
* `VecDeque::drain` creates the `Drain` struct by *first* creating a `NonNull` from `self` (which is an `&mut VecDeque`), and *then* calling `self.buffer_as_mut_slice()`. The latter reborrows `self`, asserting that `self` is currently the unique pointer to access this `VecDeque`, and hence invalidating the `NonNull` that was created earlier. This PR fixes that by instead using `self.buffer_as_slice()`, which only performs read accesses and creates only shared references, meaning the raw pointer (`NonNull`) remains valid.
It is possible that other methods on `VecDeque` do something similar, miri's test coverage of `VecDeque` is sparse to say the least.
Cc @nikomatsakis @Gankro
|
|
Co-Authored-By: RalfJung <post@ralfj.de>
|
|
Popping and pushing from the end of a linked list is constant time. This
documentation is already there for popping and pushing from the front.
@bors: r+ 38fe8d2 rollup
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Update issue number of `shrink_to` methods to point the tracking issue
Tracking issue: #56431
|
|
Move VecDeque::resize_with out of the impl<T:Clone> block
I put this in the wrong `impl` block in https://github.com/rust-lang/rust/pull/56016, so fixing.
Tracking issue for the unstable method: https://github.com/rust-lang/rust/issues/41758#issuecomment-443077953
|
|
|
|
|
|
|
|
|
|
fix various typos in doc comments
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
This reverts commit 6ce76acae455a32113116cd2f95f8076388fc2d3.
|
|
This reverts commit 11e488b64fed181820280d494d4fcc157ee1adc5.
|
|
This reverts commit 1a1a7f6167edf18b8a0ab488e651f7748cc2e9d3.
|
|
This reverts commit 1908892d3f60008f265dfc25ac46db387c0ad6a0.
|
|
This reverts commit 21d2a6c9868541ec9829ced9a5bae936b18741c5.
|
|
This reverts commit c6e3d7fa3113aaa64602507f39d4627c427742ff, reversing
changes made to 4591a245c7eec9f70d668982b1383cd2a6854af5.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
