| Age | Commit message (Collapse) | Author | Lines |
|---|
|
|
|
|
|
|
|
Signed-off-by: TennyZhuang <zty0826@gmail.com>
|
|
|
|
The discussion is [here](https://internals.rust-lang.org/t/append-vec-to-binaryheap/15209/3)
|
|
Add #[must_use] to len and is_empty
Parent issue: #89692
r? `@joshtriplett`
|
|
|
|
Add #[must_use] to remaining alloc functions
I've run out of compelling reasons to group functions together across crates so I'm just going to go module-by-module. This is everything remaining from the `alloc` crate.
I ignored these because they might be used to purposefully leak memory... or other allocator shenanigans? I dunno. I'll add them if y'all tell me to.
```rust
alloc::alloc unsafe fn alloc(layout: Layout) -> *mut u8;
alloc::alloc unsafe fn alloc_zeroed(layout: Layout) -> *mut u8;
alloc::sync::Arc<T> fn into_raw(this: Self) -> *const T;
```
I don't know why clippy ignored these. I added them myself:
```rust
alloc::collections::btree_map::BTreeMap<K, V> fn range<T: ?Sized, R>(&self, range: R) -> Range<'_, K, V>;
alloc::collections::btree_set::BTreeSet<T> fn range<K: ?Sized, R>(&self, range: R) -> Range<'_, T>;
```
I added these non-mutating `mut` functions:
```rust
alloc::collections::btree_map::BTreeMap<K, V> fn range_mut<T: ?Sized, R>(&mut self, range: R) -> RangeMut<'_, K, V>;
alloc::collections::btree_map::BTreeMap<K, V> fn iter_mut(&mut self) -> IterMut<'_, K, V>;
alloc::collections::btree_map::BTreeMap<K, V> fn values_mut(&mut self) -> ValuesMut<'_, K, V>;
alloc::collections::linked_list::LinkedList<T> fn iter_mut(&mut self) -> IterMut<'_, T>;
alloc::collections::linked_list::LinkedList<T> fn cursor_front_mut(&mut self) -> CursorMut<'_, T>;
alloc::collections::linked_list::LinkedList<T> fn cursor_back_mut(&mut self) -> CursorMut<'_, T>;
alloc::collections::linked_list::LinkedList<T> fn front_mut(&mut self) -> Option<&mut T>;
alloc::collections::linked_list::LinkedList<T> fn back_mut(&mut self) -> Option<&mut T>;
alloc::collections::linked_list::CursorMut<'a, T> fn current(&mut self) -> Option<&mut T>;
alloc::collections::linked_list::CursorMut<'a, T> fn peek_next(&mut self) -> Option<&mut T>;
alloc::collections::linked_list::CursorMut<'a, T> fn peek_prev(&mut self) -> Option<&mut T>;
alloc::collections::linked_list::CursorMut<'a, T> fn front_mut(&mut self) -> Option<&mut T>;
alloc::collections::linked_list::CursorMut<'a, T> fn back_mut(&mut self) -> Option<&mut T>;
```
I moved a few existing `#[must_use]`s from functions onto the iterator types they return: `IntoIterSorted`, `IntoKeys`, `IntoValues`.
Parent issue: #89692
r? `@joshtriplett`
|
|
Previously, it wasn't clear whether "This could include" was referring
to logic errors, or undefined behaviour. Tweak wording to clarify this
sentence does not relate to UB.
|
|
|
|
Add #[must_use] to as_type conversions
Clippy missed these:
```rust
alloc::string::String fn as_mut_str(&mut self) -> &mut str;
core::mem::NonNull<T> unsafe fn as_uninit_mut<'a>(&mut self) -> &'a MaybeUninit<T>;
str unsafe fn as_bytes_mut(&mut self) -> &mut [u8];
str fn as_mut_ptr(&mut self) -> *mut u8;
```
Parent issue: #89692
r? ````@joshtriplett````
|
|
|
|
Add #[must_use] to alloc constructors
Added `#[must_use]`. to the various forms of `new`, `pin`, and `with_capacity` in the `alloc` crate. No extra explanations given as I couldn't think of anything useful to add.
I figure this deserves extra scrutiny compared to the other PRs I've done so far. In particular:
* The 4 `pin`/`pin_in` methods I touched. Are there legitimate use cases for pinning and not using the result? Pinning's a difficult concept I'm not very comfortable with.
* `Box`'s constructors. Do people ever create boxes just for the side effects... allocating or zeroing out memory?
Parent issue: #89692
r? ``@joshtriplett``
|
|
|
|
|
|
Consistent big O notation
This makes the big O time complexity notation in places with markdown support more consistent.
Inspired by #89210
|
|
|
|
|
|
|
|
same search
|
|
Stabilize Vec<T>::shrink_to
This PR stabilizes `shrink_to` feature and closes the corresponding issue. The second point was addressed already, and no `panic!` should occur.
Closes #56431.
|
|
|
|
Stabilize `impl From<[(K, V); N]> for HashMap` (and friends)
In addition to allowing HashMap to participate in Into/From conversion, this adds the long-requested ability to use constructor-like syntax for initializing a HashMap:
```rust
let map = HashMap::from([
(1, 2),
(3, 4),
(5, 6)
]);
```
This addition is highly motivated by existing precedence, e.g. it is already possible to similarly construct a Vec from a fixed-size array:
```rust
let vec = Vec::from([1, 2, 3]);
```
...and it is already possible to collect a Vec of tuples into a HashMap (and vice-versa):
```rust
let vec = Vec::from([(1, 2)]);
let map: HashMap<_, _> = vec.into_iter().collect();
let vec: Vec<(_, _)> = map.into_iter().collect();
```
...and of course it is likewise possible to collect a fixed-size array of tuples into a HashMap ([but not vice-versa just yet](https://github.com/rust-lang/rust/issues/81615)):
```rust
let arr = [(1, 2)];
let map: HashMap<_, _> = std::array::IntoIter::new(arr).collect();
```
Therefore this addition seems like a no-brainer.
As for any impl, this would be insta-stable.
|
|
|
|
|
|
|
|
|
|
|
|
It now doesn't fully rebuild the heap, but only the parts that are
necessary.
|
|
alloc: Added `as_slice` method to `BinaryHeap` collection
I initially asked about whether it is useful addition on https://internals.rust-lang.org/t/should-i-add-as-slice-method-to-binaryheap/13816, and it seems there were no objections, so went ahead with this PR.
> There is [`BinaryHeap::into_vec`](https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html#method.into_vec), but it consumes the value. I wonder if there is API design limitation that should be taken into account. Implementation-wise, the inner buffer is just a Vec, so it is trivial to expose as_slice from it.
Please, guide me through if I need to add tests or something else.
UPD: Tracking issue #83659
|
|
|
|
|
|
Improve sift_down performance in BinaryHeap
Replacing `child < end - 1` with `child <= end.saturating_sub(2)` in `BinaryHeap::sift_down_range` (surprisingly) results in a significant speedup of `BinaryHeap::into_sorted_vec`. The same substitution can be done for `BinaryHeap::sift_down_to_bottom`, which causes a slight but probably statistically insignificant speedup for `BinaryHeap::pop`. It's interesting that benchmarks aside from `bench_into_sorted_vec` are barely affected, even those that do use `sift_down_*` methods internally.
| Benchmark | Before (ns/iter) | After (ns/iter) | Speedup |
|--------------------------|------------------|-----------------|---------|
| bench_find_smallest_1000<sup>1</sup> | 392,617 | 385,200 | 1.02 |
| bench_from_vec<sup>1</sup> | 506,016 | 504,444 | 1.00 |
| bench_into_sorted_vec<sup>1</sup> | 476,869 | 384,458 | 1.24 |
| bench_peek_mut_deref_mut<sup>3</sup> | 518,753 | 519,792 | 1.00 |
| bench_pop<sup>2</sup> | 446,718 | 444,409 | 1.01 |
| bench_push<sup>3</sup> | 772,481 | 770,208 | 1.00 |
<sup>1</sup>: internally calls `sift_down_range`
<sup>2</sup>: internally calls `sift_down_to_bottom`
<sup>3</sup>: should not be affected
|
|
|
|
Because child > 0, the two statements are equivalent, but using
saturating_sub and <= yields in faster code. This is most notable in the
binary_heap::bench_into_sorted_vec benchmark, which shows a speedup of
1.26x, which uses sift_down_range internally. The speedup of pop (that
uses sift_down_to_bottom internally) is much less significant as the
sifting method is not called in a loop.
|
|
|
|
|
|
|
|
|
|
Clarify what the effects of a 'logic error' are
This clarifies what a 'logic error' is (which is a term used to describe what happens if you put things in a hash table or btree and then use something like a refcell to break the internal ordering). This tries to be as vague as possible, as we don't really want to promise what happens, except "bad things, but not UB". This was discussed in #80657
|
|
|
|
See #77433 for why the new heuristic was chosen.
Fixes #77433
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
