about summary refs log tree commit diff
path: root/library/alloc/src/collections
AgeCommit message (Collapse)AuthorLines
2024-03-28Fix previous.Cai Bear-1/+2
2024-03-28Remove len argument from RawVec::reserve_for_push because it's always equal ↵Cai Bear-3/+2
to capacity. Also make Vec::insert use reserve_for_push.
2024-03-25lib: fix some unnecessary_cast clippy lintklensy-1/+1
warning: casting raw pointers to the same type and constness is unnecessary (`*mut V` -> `*mut V`) --> library\alloc\src\collections\btree\map\entry.rs:357:31 | 357 | let val_ptr = root.borrow_mut().push(self.key, value) as *mut V; | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: try: `root.borrow_mut().push (self.key, value)` | = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#unnecessary_cast warning: casting to the same type is unnecessary (`usize` -> `usize`) --> library\alloc\src\ffi\c_str.rs:411:56 | 411 | let slice = slice::from_raw_parts_mut(ptr, len as usize); | ^^^^^^^^^^^^ help: try: `len` | = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#unnecessary_cast warning: casting raw pointers to the same type and constness is unnecessary (`*mut T` -> `*mut T`) --> library\alloc\src\slice.rs:516:25 | 516 | (buf.as_mut_ptr() as *mut T).add(buf.len()), | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: try: `buf.as_mut_ptr()` | = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#unnecessary_cast warning: casting raw pointers to the same type and constness is unnecessary (`*mut T` -> `*mut T`) --> library\alloc\src\slice.rs:537:21 | 537 | (buf.as_mut_ptr() as *mut T).add(buf.len()), | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: try: `buf.as_mut_ptr()` | = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#unnecessary_cast warning: casting raw pointers to the same type and constness is unnecessary (`*const ()` -> `*const ()`) --> library\alloc\src\task.rs:151:13 | 151 | waker as *const (), | ^^^^^^^^^^^^^^^^^^ help: try: `waker` | = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#unnecessary_cast warning: casting raw pointers to the same type and constness is unnecessary (`*const ()` -> `*const ()`) --> library\alloc\src\task.rs:323:13 | 323 | waker as *const (), | ^^^^^^^^^^^^^^^^^^ help: try: `waker` | = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#unnecessary_cast warning: casting to the same type is unnecessary (`usize` -> `usize`) --> library\std\src\sys_common\net.rs:110:21 | 110 | assert!(len as usize >= mem::size_of::<c::sockaddr_in>()); | ^^^^^^^^^^^^ help: try: `len` | = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#unnecessary_cast warning: casting to the same type is unnecessary (`usize` -> `usize`) --> library\std\src\sys_common\net.rs:116:21 | 116 | assert!(len as usize >= mem::size_of::<c::sockaddr_in6>()); | ^^^^^^^^^^^^ help: try: `len` | = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#unnecessary_cast
2024-03-24clarify equivalency of binary_search and partition_pointAndy Kurnia-1/+3
2024-03-23improve example on inserting to a sorted vector to avoid shifting equal elementsAndy Kurnia-1/+1
2024-03-23Auto merge of #119552 - krtab:dead_code_priv_mod_pub_field, r=cjgillot,saethlinbors-8/+4
Replace visibility test with reachability test in dead code detection Fixes https://github.com/rust-lang/rust/issues/119545 Also included is a fix for an error now flagged by the lint
2024-03-21document into_iter in top level docs iterator ordering guaranteesultrabear-2/+2
2024-03-21document iteration ordering on into_iter method instead of IntoIterator ↵ultrabear-3/+2
implementation
2024-03-21BTree(Set|Map): Guarantee that `IntoIter` will iterate in sorted by key orderultrabear-2/+4
2024-03-12Remove unused fields in some structuresArthur Carcano-8/+4
The dead_code lint was previously eroneously missing those. Since this lint bug has been fixed, the unused fields need to be removed.
2024-03-09Rollup merge of #120504 - kornelski:try_with_capacity, r=AmanieuGuillaume Boisseau-0/+24
Vec::try_with_capacity Related to #91913 Implements try_with_capacity for `Vec`, `VecDeque`, and `String`. I can follow it up with more collections if desired. `Vec::try_with_capacity()` is functionally equivalent to the current stable: ```rust let mut v = Vec::new(); v.try_reserve_exact(n)? ``` However, `try_reserve` calls non-inlined `finish_grow`, which requires old and new `Layout`, and is designed to reallocate memory. There is benefit to using `try_with_capacity`, besides syntax convenience, because it generates much smaller code at the call site with a direct call to the allocator. There's codegen test included. It's also a very desirable functionality for users of `no_global_oom_handling` (Rust-for-Linux), since it makes a very commonly used function available in that environment (`with_capacity` is used much more frequently than all `(try_)reserve(_exact)`).
2024-03-08Document overrides of `clone_from()`Noa-12/+30
Specifically, when an override doesn't just forward to an inner type, document the behavior and that it's preferred over simply assigning a clone of source. Also, change instances where the second parameter is "other" to "source".
2024-03-06Add #[inline] to BTreeMap::new constructorUrgau-0/+1
2024-03-01try_with_capacity for Vec, VecDeque, StringKornel-0/+24
#91913
2024-03-01remove hidden use of GlobalAlexander-1/+1
2024-02-23remove repetitive wordscui fliter-6/+6
Signed-off-by: cui fliter <imcusg@gmail.com>
2024-02-22Add `rustc_confusables` annotations to some stdlib APIsEsteban Küber-0/+28
Help with common API confusion, like asking for `push` when the data structure really has `append`. ``` error[E0599]: no method named `size` found for struct `Vec<{integer}>` in the current scope --> $DIR/rustc_confusables_std_cases.rs:17:7 | LL | x.size(); | ^^^^ | help: you might have meant to use `len` | LL | x.len(); | ~~~ help: there is a method with a similar name | LL | x.resize(); | ~~~~~~ ``` #59450
2024-02-18Auto merge of #118264 - lukas-code:optimized-draining, r=the8472bors-56/+114
Optimize `VecDeque::drain` for (half-)open ranges The most common use cases of `VecDeque::drain` consume either the entire queue or elements from the front or back.[^1] This PR makes these operations faster by optimizing the generated code of the destructor of the drain: * `.drain(..)` is now the same as `.clear()`. * `.drain(n..)` is now (almost[^2]) the same as `.truncate(n)`. * `.drain(..n)` is now an efficient "advance" function. This operation is not provided by a dedicated function and optimizing it is my main motivation for this PR. Previously, all of these cases generated a function call to the destructor of the `DropGuard`, emitting a lot of unused machine code as well as unnecessary branches and loads/stores of stack variables. There are no algorithmic changes in this PR, but it simplifies the code enough to allow LLVM to recognize the special cases and optimize accordingly. Most notably, it allows elimination of the rather large [`wrap_copy`] function. Some [rudimentary microbenchmarks][benches] show a performance improvement of **~3x-4x** on my machine for the special cases and roughly equal performance for the general case. Best reviewed commit by commit. [^1]: source: GitHub code search: [full range `drain(..)` = 7.5k results][full], [from front `drain(..n)` = 3.2k results][front], [from back `drain(n..)` = 1.6k results][back], [from middle `drain(n..m)` = <500 results][middle] [^2]: `.drain(0..)` and `.clear()` reset the head to 0, but `.truncate(0)` does not. [full]: https://github.com/search?type=code&q=%2FVecDeque%28.%7C%5Cn%29%2B%5C.drain%5C%280%3F%5C.%5C.%5C%29%2F+lang%3ARust [front]: https://github.com/search?type=code&q=%2FVecDeque%28.%7C%5Cn%29%2B%5C.drain%5C%280%3F%5C.%5C.%5B%5E%29%5D.*%5C%29%2F+lang%3ARust [back]: https://github.com/search?type=code&q=%2FVecDeque%28.%7C%5Cn%29%2B%5C.drain%5C%28%5B%5E0%5D.*%5C.%5C.%5C%29%2F+lang%3ARust [middle]: https://github.com/search?type=code&q=%2FVecDeque%28.%7C%5Cn%29%2B%5C.drain%5C%28%5B%5E0%5D.*%5C.%5C.%5B%5E%29%5D.*%5C%29%2F+lang%3ARust [`wrap_copy`]: https://github.com/rust-lang/rust/blob/4fd68eb47bad1c121417ac4450b2f0456150db86/library/alloc/src/collections/vec_deque/mod.rs#L262-L391 [benches]: https://gist.github.com/lukas-code/c97bd707d074c4cc31f241edbc7fd2a2 <details> <summary>generated assembly</summary> before: ```asm clear: sub rsp, 40 mov rax, qword ptr [rdi + 24] mov qword ptr [rdi + 24], 0 mov qword ptr [rsp], rdi mov qword ptr [rsp + 8], rax xorps xmm0, xmm0 movups xmmword ptr [rsp + 16], xmm0 mov qword ptr [rsp + 32], rax test rax, rax je .LBB1_2 mov rcx, qword ptr [rdi] mov rdx, qword ptr [rdi + 16] xor esi, esi cmp rdx, rcx cmovae rsi, rcx sub rdx, rsi mov rsi, rcx sub rsi, rdx lea rdi, [rdx + rax] cmp rsi, rax cmovb rdi, rcx sub rdi, rdx mov qword ptr [rsp + 16], rdi mov qword ptr [rsp + 32], 0 .LBB1_2: mov rdi, rsp call core::ptr::drop_in_place<<alloc::collections::vec_deque::drain::Drain<T,A> as core::ops::drop::Drop>::drop::DropGuard<i32,alloc::alloc::Global>> add rsp, 40 ret truncate: mov rax, qword ptr [rdi + 24] sub rax, rsi jbe .LBB2_2 sub rsp, 40 mov qword ptr [rdi + 24], rsi mov qword ptr [rsp], rdi mov qword ptr [rsp + 8], rax mov rcx, qword ptr [rdi] mov rdx, qword ptr [rdi + 16] add rdx, rsi xor edi, edi cmp rdx, rcx cmovae rdi, rcx mov qword ptr [rsp + 24], 0 sub rdx, rdi mov rdi, rcx sub rdi, rdx lea r8, [rdx + rax] cmp rdi, rax cmovb r8, rcx sub rsi, rdx add rsi, r8 mov qword ptr [rsp + 16], rsi mov qword ptr [rsp + 32], 0 mov rdi, rsp call core::ptr::drop_in_place<<alloc::collections::vec_deque::drain::Drain<T,A> as core::ops::drop::Drop>::drop::DropGuard<i32,alloc::alloc::Global>> add rsp, 40 advance: mov rcx, qword ptr [rdi + 24] mov rax, rcx sub rax, rsi jbe .LBB3_1 sub rsp, 40 mov qword ptr [rdi + 24], 0 mov qword ptr [rsp], rdi mov qword ptr [rsp + 8], rsi mov qword ptr [rsp + 16], 0 mov qword ptr [rsp + 24], rax mov qword ptr [rsp + 32], rsi test rsi, rsi je .LBB3_6 mov rax, qword ptr [rdi] mov rcx, qword ptr [rdi + 16] xor edx, edx cmp rcx, rax cmovae rdx, rax sub rcx, rdx mov rdx, rax sub rdx, rcx lea rdi, [rcx + rsi] cmp rdx, rsi cmovb rdi, rax sub rdi, rcx mov qword ptr [rsp + 16], rdi mov qword ptr [rsp + 32], 0 .LBB3_6: mov rdi, rsp call core::ptr::drop_in_place<<alloc::collections::vec_deque::drain::Drain<T,A> as core::ops::drop::Drop>::drop::DropGuard<i32,alloc::alloc::Global>> add rsp, 40 ret .LBB3_1: test rcx, rcx je .LBB3_3 mov qword ptr [rdi + 24], 0 .LBB3_3: mov qword ptr [rdi + 16], 0 ret remove: sub rsp, 40 cmp rdx, rsi jb .LBB4_5 mov rax, qword ptr [rdi + 24] mov rcx, rax sub rcx, rdx jb .LBB4_6 mov qword ptr [rdi + 24], rsi mov qword ptr [rsp], rdi sub rdx, rsi mov qword ptr [rsp + 8], rdx mov qword ptr [rsp + 16], rsi mov qword ptr [rsp + 24], rcx mov qword ptr [rsp + 32], rdx je .LBB4_4 mov rax, qword ptr [rdi] mov rcx, qword ptr [rdi + 16] add rcx, rsi xor edi, edi cmp rcx, rax cmovae rdi, rax sub rcx, rdi mov rdi, rax sub rdi, rcx lea r8, [rcx + rdx] cmp rdi, rdx cmovb r8, rax sub rsi, rcx add rsi, r8 mov qword ptr [rsp + 16], rsi mov qword ptr [rsp + 32], 0 .LBB4_4: mov rdi, rsp call core::ptr::drop_in_place<<alloc::collections::vec_deque::drain::Drain<T,A> as core::ops::drop::Drop>::drop::DropGuard<i32,alloc::alloc::Global>> add rsp, 40 ret .LBB4_5: lea rax, [rip + .L__unnamed_2] mov rdi, rsi mov rsi, rdx mov rdx, rax call qword ptr [rip + core::slice::index::slice_index_order_fail@GOTPCREL] .LBB4_6: lea rcx, [rip + .L__unnamed_2] mov rdi, rdx mov rsi, rax mov rdx, rcx call qword ptr [rip + core::slice::index::slice_end_index_len_fail@GOTPCREL] core::ptr::drop_in_place<<alloc::collections::vec_deque::drain::Drain<T,A> as core::ops::drop::Drop>::drop::DropGuard<i32,alloc::alloc::Global>>: push rbp push r15 push r14 push r13 push r12 push rbx sub rsp, 24 mov rsi, qword ptr [rdi + 32] test rsi, rsi je .LBB0_2 mov rax, qword ptr [rdi + 16] add rsi, rax jb .LBB0_45 .LBB0_2: mov r13, qword ptr [rdi] mov rbp, qword ptr [rdi + 8] mov rbx, qword ptr [r13 + 24] lea r12, [rbx + rbp] mov r15, qword ptr [rdi + 24] lea rsi, [r15 + r12] test rbx, rbx je .LBB0_10 test r15, r15 je .LBB0_42 cmp rbx, r15 jbe .LBB0_12 mov r14, qword ptr [r13] mov rax, qword ptr [r13 + 16] add r12, rax xor ecx, ecx cmp r12, r14 mov rdx, r14 cmovb rdx, rcx sub r12, rdx add rbx, rax cmp rbx, r14 cmovae rcx, r14 sub rbx, rcx mov rcx, rbx sub rcx, r12 je .LBB0_42 mov rdi, qword ptr [r13 + 8] mov rax, rcx add rax, r14 cmovae rax, rcx mov r8, r14 sub r8, r12 mov rcx, r14 sub rcx, rbx mov rdx, r15 sub rdx, r8 mov qword ptr [rsp + 16], rsi jbe .LBB0_18 cmp rax, r15 jae .LBB0_24 mov rdx, r15 sub rdx, r8 shl rdx, 2 cmp r15, rcx jbe .LBB0_30 sub r8, rcx mov qword ptr [rsp], rdi mov rax, qword ptr [rsp] lea rdi, [rax + 4*r8] mov rsi, qword ptr [rsp] mov qword ptr [rsp + 8], rcx mov r15, r8 call qword ptr [rip + memmove@GOTPCREL] sub r14, r15 mov rax, qword ptr [rsp] lea rsi, [rax + 4*r14] shl r15, 2 mov rdi, qword ptr [rsp] mov rdx, r15 call qword ptr [rip + memmove@GOTPCREL] mov rdi, qword ptr [rsp] lea rsi, [rdi + 4*r12] lea rdi, [rdi + 4*rbx] mov r15, qword ptr [rsp + 8] jmp .LBB0_36 .LBB0_10: test r15, r15 je .LBB0_17 mov rax, qword ptr [r13] sub rsi, rbp add rbp, qword ptr [r13 + 16] xor ecx, ecx cmp rbp, rax cmovae rcx, rax sub rbp, rcx mov qword ptr [r13 + 16], rbp jmp .LBB0_43 .LBB0_12: mov rdx, qword ptr [r13 + 16] mov r15, qword ptr [r13] lea rax, [rdx + rbp] xor ecx, ecx cmp rax, r15 cmovae rcx, r15 mov r12, rax sub r12, rcx mov rcx, r12 sub rcx, rdx je .LBB0_41 mov rdi, qword ptr [r13 + 8] mov rax, rcx add rax, r15 cmovae rax, rcx mov r8, r15 sub r8, rdx mov rcx, r15 sub rcx, r12 mov r14, rbx sub r14, r8 mov qword ptr [rsp + 16], rsi jbe .LBB0_21 cmp rax, rbx jae .LBB0_26 mov qword ptr [rsp], rdx mov rdx, rbx sub rdx, r8 shl rdx, 2 cmp rbx, rcx jbe .LBB0_32 sub r8, rcx mov rbx, rdi lea rdi, [rdi + 4*r8] mov rsi, rbx mov qword ptr [rsp + 8], rcx mov r14, r8 call qword ptr [rip + memmove@GOTPCREL] sub r15, r14 lea rsi, [rbx + 4*r15] shl r14, 2 mov rdi, rbx mov rdx, r14 call qword ptr [rip + memmove@GOTPCREL] mov rdi, rbx mov rax, qword ptr [rsp] lea rsi, [rbx + 4*rax] lea rdi, [rbx + 4*r12] mov rbx, qword ptr [rsp + 8] jmp .LBB0_40 .LBB0_17: xorps xmm0, xmm0 movups xmmword ptr [r13 + 16], xmm0 jmp .LBB0_44 .LBB0_18: mov r14, r15 sub r14, rcx jbe .LBB0_28 cmp rax, r15 jae .LBB0_33 lea rax, [rcx + r12] sub r15, rcx lea rsi, [rdi + 4*rax] shl r15, 2 mov r14, rdi mov rdx, r15 mov r15, rcx jmp .LBB0_31 .LBB0_21: mov r14, rbx sub r14, rcx jbe .LBB0_29 cmp rax, rbx jae .LBB0_34 lea rax, [rcx + rdx] sub rbx, rcx lea rsi, [rdi + 4*rax] shl rbx, 2 mov r14, rdi mov r15, rdx mov rdx, rbx mov rbx, rcx call qword ptr [rip + memmove@GOTPCREL] mov rdi, r14 lea rsi, [r14 + 4*r15] lea rdi, [r14 + 4*r12] jmp .LBB0_40 .LBB0_24: sub r15, rcx jbe .LBB0_35 sub rcx, r8 mov qword ptr [rsp + 8], rcx lea rsi, [rdi + 4*r12] mov r12, rdi lea rdi, [rdi + 4*rbx] lea rdx, [4*r8] mov r14, r8 call qword ptr [rip + memmove@GOTPCREL] add r14, rbx lea rdi, [r12 + 4*r14] mov rbx, qword ptr [rsp + 8] lea rdx, [4*rbx] mov rsi, r12 call qword ptr [rip + memmove@GOTPCREL] mov rdi, r12 lea rsi, [r12 + 4*rbx] jmp .LBB0_36 .LBB0_26: sub rbx, rcx jbe .LBB0_37 sub rcx, r8 lea rsi, [rdi + 4*rdx] mov r15, rdi lea rdi, [rdi + 4*r12] lea rdx, [4*r8] mov r14, rcx mov qword ptr [rsp], r8 call qword ptr [rip + memmove@GOTPCREL] add r12, qword ptr [rsp] lea rdi, [r15 + 4*r12] lea rdx, [4*r14] mov rsi, r15 call qword ptr [rip + memmove@GOTPCREL] mov rdi, r15 lea rsi, [r15 + 4*r14] jmp .LBB0_40 .LBB0_28: lea rsi, [rdi + 4*r12] lea rdi, [rdi + 4*rbx] jmp .LBB0_36 .LBB0_29: lea rsi, [rdi + 4*rdx] lea rdi, [rdi + 4*r12] jmp .LBB0_40 .LBB0_30: lea rax, [r8 + rbx] mov r14, rdi lea rdi, [rdi + 4*rax] mov rsi, r14 mov r15, r8 .LBB0_31: call qword ptr [rip + memmove@GOTPCREL] mov rdi, r14 lea rsi, [r14 + 4*r12] lea rdi, [r14 + 4*rbx] jmp .LBB0_36 .LBB0_32: lea rax, [r12 + r8] mov rbx, rdi lea rdi, [rdi + 4*rax] mov rsi, rbx mov r14, r8 call qword ptr [rip + memmove@GOTPCREL] mov rdi, rbx mov rax, qword ptr [rsp] lea rsi, [rbx + 4*rax] jmp .LBB0_38 .LBB0_33: lea rsi, [rdi + 4*r12] mov r15, rdi lea rdi, [rdi + 4*rbx] lea rdx, [4*rcx] mov rbx, rcx call qword ptr [rip + memmove@GOTPCREL] mov rdi, r15 add rbx, r12 lea rsi, [r15 + 4*rbx] mov r15, r14 jmp .LBB0_36 .LBB0_34: lea rsi, [rdi + 4*rdx] mov rbx, rdi lea rdi, [rdi + 4*r12] mov r15, rdx lea rdx, [4*rcx] mov r12, rcx call qword ptr [rip + memmove@GOTPCREL] mov rdi, rbx add r12, r15 lea rsi, [rbx + 4*r12] jmp .LBB0_39 .LBB0_35: lea rsi, [rdi + 4*r12] mov r14, rdi lea rdi, [rdi + 4*rbx] mov r12, rdx lea rdx, [4*r8] mov r15, r8 call qword ptr [rip + memmove@GOTPCREL] add r15, rbx mov rsi, r14 lea rdi, [r14 + 4*r15] mov r15, r12 .LBB0_36: shl r15, 2 mov rdx, r15 call qword ptr [rip + memmove@GOTPCREL] mov rsi, qword ptr [rsp + 16] jmp .LBB0_42 .LBB0_37: lea rsi, [rdi + 4*rdx] mov rbx, rdi lea rdi, [rdi + 4*r12] lea rdx, [4*r8] mov r15, r8 call qword ptr [rip + memmove@GOTPCREL] add r12, r15 mov rsi, rbx .LBB0_38: lea rdi, [rbx + 4*r12] .LBB0_39: mov rbx, r14 .LBB0_40: shl rbx, 2 mov rdx, rbx call qword ptr [rip + memmove@GOTPCREL] mov r15, qword ptr [r13] mov rax, qword ptr [r13 + 16] add rax, rbp mov rsi, qword ptr [rsp + 16] .LBB0_41: xor ecx, ecx cmp rax, r15 cmovae rcx, r15 sub rax, rcx mov qword ptr [r13 + 16], rax .LBB0_42: sub rsi, rbp .LBB0_43: mov qword ptr [r13 + 24], rsi .LBB0_44: add rsp, 24 pop rbx pop r12 pop r13 pop r14 pop r15 pop rbp ret .LBB0_45: lea rdx, [rip + .L__unnamed_1] mov rdi, rax call qword ptr [rip + core::slice::index::slice_index_order_fail@GOTPCREL] ``` after: ```asm clear: movups xmmword ptr [rdi + 16], xmm0 ret truncate: cmp qword ptr [rdi + 24], rsi jbe .LBB2_4 test rsi, rsi jne .LBB2_3 mov qword ptr [rdi + 16], 0 .LBB2_3: mov qword ptr [rdi + 24], rsi .LBB2_4: ret advance: mov rcx, qword ptr [rdi + 24] mov rax, rcx sub rax, rsi jbe .LBB3_1 mov rcx, qword ptr [rdi] add rsi, qword ptr [rdi + 16] xor edx, edx cmp rsi, rcx cmovae rdx, rcx sub rsi, rdx mov qword ptr [rdi + 16], rsi mov qword ptr [rdi + 24], rax ret .LBB3_1: test rcx, rcx je .LBB3_3 mov qword ptr [rdi + 24], 0 .LBB3_3: mov qword ptr [rdi + 16], 0 ret remove: push rbp push r15 push r14 push r13 push r12 push rbx push rax mov r15, rsi mov r14, rdx sub r14, rsi jb .LBB4_9 mov rbx, rdi mov r12, qword ptr [rdi + 24] mov r13, r12 sub r13, rdx jb .LBB4_10 mov qword ptr [rbx + 24], r15 mov rbp, r12 sub rbp, r14 test r15, r15 je .LBB4_4 cmp rbp, r15 jne .LBB4_11 .LBB4_4: cmp r12, r14 jne .LBB4_6 .LBB4_5: mov qword ptr [rbx + 16], 0 jmp .LBB4_8 .LBB4_11: mov rdi, rbx mov rsi, r14 mov rdx, r15 mov rcx, r13 call <<alloc::collections::vec_deque::drain::Drain<T,A> as core::ops::drop::Drop>::drop::DropGuard<T,A> as core::ops::drop::Drop>::drop::copy_data cmp r12, r14 je .LBB4_5 .LBB4_6: cmp r13, r15 jbe .LBB4_8 mov rax, qword ptr [rbx] add r14, qword ptr [rbx + 16] xor ecx, ecx cmp r14, rax cmovae rcx, rax sub r14, rcx mov qword ptr [rbx + 16], r14 .LBB4_8: mov qword ptr [rbx + 24], rbp add rsp, 8 pop rbx pop r12 pop r13 pop r14 pop r15 pop rbp ret .LBB4_9: lea rax, [rip + .L__unnamed_1] mov rdi, r15 mov rsi, rdx mov rdx, rax call qword ptr [rip + core::slice::index::slice_index_order_fail@GOTPCREL] .LBB4_10: lea rax, [rip + .L__unnamed_1] mov rdi, rdx mov rsi, r12 mov rdx, rax call qword ptr [rip + core::slice::index::slice_end_index_len_fail@GOTPCREL] <<alloc::collections::vec_deque::drain::Drain<T,A> as core::ops::drop::Drop>::drop::DropGuard<T,A> as core::ops::drop::Drop>::drop::copy_data: push rbp push r15 push r14 push r13 push r12 push rbx push rax mov r14, rsi cmp rdx, rcx jae .LBB0_1 mov r12, qword ptr [rdi] mov rax, qword ptr [rdi + 16] add r14, rax xor ecx, ecx cmp r14, r12 cmovae rcx, r12 sub r14, rcx mov r15, rdx mov r13, r14 mov r14, rax mov rcx, r13 sub rcx, r14 je .LBB0_18 .LBB0_4: mov rdi, qword ptr [rdi + 8] mov rax, rcx add rax, r12 cmovae rax, rcx mov rbx, r12 sub rbx, r14 mov rcx, r12 sub rcx, r13 mov rbp, r15 sub rbp, rbx jbe .LBB0_5 cmp rax, r15 jae .LBB0_12 mov rdx, r15 sub rdx, rbx shl rdx, 2 cmp r15, rcx jbe .LBB0_16 sub rbx, rcx mov rbp, rdi lea rdi, [rdi + 4*rbx] mov r15, qword ptr [rip + memmove@GOTPCREL] mov rsi, rbp mov qword ptr [rsp], rcx call r15 sub r12, rbx lea rsi, [4*r12] add rsi, rbp shl rbx, 2 mov rdi, rbp mov rdx, rbx call r15 mov rdi, rbp lea rsi, [4*r14] add rsi, rbp lea rdi, [4*r13] add rdi, rbp mov r15, qword ptr [rsp] jmp .LBB0_7 .LBB0_1: mov r15, rcx add r14, rdx mov r12, qword ptr [rdi] mov r13, qword ptr [rdi + 16] add r14, r13 xor eax, eax cmp r14, r12 mov rcx, r12 cmovb rcx, rax sub r14, rcx add r13, rdx cmp r13, r12 cmovae rax, r12 sub r13, rax mov rcx, r13 sub rcx, r14 jne .LBB0_4 .LBB0_18: add rsp, 8 pop rbx pop r12 pop r13 pop r14 pop r15 pop rbp ret .LBB0_5: mov rbx, r15 sub rbx, rcx jbe .LBB0_6 cmp rax, r15 jae .LBB0_9 lea rax, [rcx + r14] sub r15, rcx lea rsi, [rdi + 4*rax] shl r15, 2 mov rbx, rdi mov rdx, r15 mov r15, rcx call qword ptr [rip + memmove@GOTPCREL] mov rdi, rbx lea rsi, [rbx + 4*r14] lea rdi, [rbx + 4*r13] jmp .LBB0_7 .LBB0_12: sub r15, rcx jbe .LBB0_13 sub rcx, rbx lea rsi, [rdi + 4*r14] mov r12, rdi lea rdi, [rdi + 4*r13] lea rdx, [4*rbx] mov r14, qword ptr [rip + memmove@GOTPCREL] mov rbp, rcx call r14 add rbx, r13 lea rdi, [r12 + 4*rbx] lea rdx, [4*rbp] mov rsi, r12 call r14 mov rdi, r12 lea rsi, [r12 + 4*rbp] jmp .LBB0_7 .LBB0_6: lea rsi, [rdi + 4*r14] lea rdi, [rdi + 4*r13] jmp .LBB0_7 .LBB0_16: lea rax, [rbx + r13] mov r15, rdi lea rdi, [rdi + 4*rax] mov rsi, r15 call qword ptr [rip + memmove@GOTPCREL] mov rdi, r15 lea rsi, [r15 + 4*r14] lea rdi, [r15 + 4*r13] mov r15, rbx jmp .LBB0_7 .LBB0_9: lea rsi, [rdi + 4*r14] mov r15, rdi lea rdi, [rdi + 4*r13] lea rdx, [4*rcx] mov r12, rcx call qword ptr [rip + memmove@GOTPCREL] mov rdi, r15 add r12, r14 lea rsi, [r15 + 4*r12] mov r15, rbx jmp .LBB0_7 .LBB0_13: lea rsi, [rdi + 4*r14] mov r14, rdi lea rdi, [rdi + 4*r13] lea rdx, [4*rbx] call qword ptr [rip + memmove@GOTPCREL] add rbx, r13 mov rsi, r14 lea rdi, [r14 + 4*rbx] mov r15, rbp .LBB0_7: shl r15, 2 mov rdx, r15 add rsp, 8 pop rbx pop r12 pop r13 pop r14 pop r15 pop rbp jmp qword ptr [rip + memmove@GOTPCREL] ``` </details>
2024-02-17Rollup merge of #121149 - SebastianJL:patch-1, r=Mark-SimulacrumMatthias Krüger-4/+4
Fix typo in VecDeque::handle_capacity_increase() doc comment. Strategies B and C both show a full buffer before the capacity increase, while strategy A had one empty element left. Filled the last element in.
2024-02-16address review commentsLukas Markeffsky-44/+99
2024-02-16outline large copiesLukas Markeffsky-7/+20
2024-02-16reduce branchinessLukas Markeffsky-31/+22
2024-02-16reduce amount of mathLukas Markeffsky-14/+12
2024-02-16simplify codegen for trivially droppable typesLukas Markeffsky-2/+3
2024-02-16Auto merge of #120486 - reitermarkus:use-generic-nonzero, r=dtolnaybors-16/+16
Use generic `NonZero` internally. Tracking issue: https://github.com/rust-lang/rust/issues/120257
2024-02-15Fix typo in VecDeque::handle_capacity_increase() doc comment.Johannes Lade-4/+4
Strategies B and C both show a full buffer before the capacity increase, while strategy A had one empty element left. Filled the last element in.
2024-02-15Rollup merge of #120505 - Amanieu:fix-btreemap-cursor-remove, r=m-ou-seGuillaume Gomez-0/+12
Fix BTreeMap's Cursor::remove_{next,prev} These would incorrectly leave `current` as `None` after a failed attempt to remove an element (due to the cursor already being at the start/end).
2024-02-15Replace `NonZero::<_>::new` with `NonZero::new`.Markus Reiter-5/+5
2024-02-15Use generic `NonZero` internally.Markus Reiter-16/+16
2024-02-11fix intra-doc linksripytide-12/+12
2024-02-11fix incorrect doctestripytide-2/+2
2024-02-11improve `btree_cursors` functions documentationripytide-87/+130
2024-01-30Fix BTreeMap's Cursor::remove_{next,prev}Amanieu d'Antras-0/+12
These would incorrectly leave `current` as `None` after a failed attempt to remove an element (due to the cursor already being at the start/end).
2024-01-25Rollup merge of #118208 - Amanieu:btree_cursor2, r=dtolnayMatthias Krüger-392/+549
Rewrite the BTreeMap cursor API using gaps Tracking issue: #107540 Currently, a `Cursor` points to a single element in the tree, and allows moving to the next or previous element while mutating the tree. However this was found to be confusing and hard to use. This PR completely refactors cursors to instead point to a gap between two elements in the tree. This eliminates the need for a "ghost" element that exists after the last element and before the first one. Additionally, `upper_bound` and `lower_bound` now have a much clearer meaning. The ability to mutate keys is also factored out into a separate `CursorMutKey` type which is unsafe to create. This makes the API easier to use since it avoids duplicated versions of each method with and without key mutation. API summary: ```rust impl<K, V> BTreeMap<K, V> { fn lower_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; fn lower_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; fn upper_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; fn upper_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; } struct Cursor<'a, K: 'a, V: 'a>; impl<'a, K, V> Cursor<'a, K, V> { fn next(&mut self) -> Option<(&'a K, &'a V)>; fn prev(&mut self) -> Option<(&'a K, &'a V)>; fn peek_next(&self) -> Option<(&'a K, &'a V)>; fn peek_prev(&self) -> Option<(&'a K, &'a V)>; } struct CursorMut<'a, K: 'a, V: 'a>; impl<'a, K, V> CursorMut<'a, K, V> { fn next(&mut self) -> Option<(&K, &mut V)>; fn prev(&mut self) -> Option<(&K, &mut V)>; fn peek_next(&mut self) -> Option<(&K, &mut V)>; fn peek_prev(&mut self) -> Option<(&K, &mut V)>; unsafe fn insert_after_unchecked(&mut self, key: K, value: V); unsafe fn insert_before_unchecked(&mut self, key: K, value: V); fn insert_after(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError>; fn insert_before(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError>; fn remove_next(&mut self) -> Option<(K, V)>; fn remove_prev(&mut self) -> Option<(K, V)>; fn as_cursor(&self) -> Cursor<'_, K, V>; unsafe fn with_mutable_key(self) -> CursorMutKey<'a, K, V, A>; } struct CursorMutKey<'a, K: 'a, V: 'a>; impl<'a, K, V> CursorMut<'a, K, V> { fn next(&mut self) -> Option<(&mut K, &mut V)>; fn prev(&mut self) -> Option<(&mut K, &mut V)>; fn peek_next(&mut self) -> Option<(&mut K, &mut V)>; fn peek_prev(&mut self) -> Option<(&mut K, &mut V)>; unsafe fn insert_after_unchecked(&mut self, key: K, value: V); unsafe fn insert_before_unchecked(&mut self, key: K, value: V); fn insert_after(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError>; fn insert_before(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError>; fn remove_next(&mut self) -> Option<(K, V)>; fn remove_prev(&mut self) -> Option<(K, V)>; fn as_cursor(&self) -> Cursor<'_, K, V>; unsafe fn with_mutable_key(self) -> CursorMutKey<'a, K, V, A>; } struct UnorderedKeyError; ```
2024-01-02Adjust library tests for unused_tuple_struct_fields -> dead_codeJake Goulding-2/+2
2023-12-21fix minor mistake in comments describing VecDeque resizingKent Ross-4/+4
2023-12-10remove redundant importssurechen-11/+1
detects redundant imports that can be eliminated. for #117772 : In order to facilitate review and modification, split the checking code and removing redundant imports code into two PR.
2023-12-09Auto merge of #114136 - TennyZhuang:linked-list-retain, r=thomccbors-0/+93
add LinkedList::{retain,retain_mut} Implement #114135 The API is consistent with other collections.
2023-11-29Rollup merge of #118398 - mu001999:std/add_cfgs, r=thomccMatthias Krüger-0/+1
Add proper cfgs in std Detected by #118257
2023-11-28Auto merge of #110353 - the8472:in-place-flatten-chunks, r=cuviperbors-2/+9
Expand in-place iteration specialization to Flatten, FlatMap and ArrayChunks This enables the following cases to collect in-place: ```rust let v = vec![[0u8; 4]; 1024] let v: Vec<_> = v.into_iter().flatten().collect(); let v: Vec<Option<NonZeroUsize>> = vec![NonZeroUsize::new(0); 1024]; let v: Vec<_> = v.into_iter().flatten().collect(); let v = vec![u8; 4096]; let v: Vec<_> = v.into_iter().array_chunks::<4>().collect(); ``` Especially the nicheful-option-flattening should be useful in real code.
2023-11-28Add proper cfgsr0cky-0/+1
2023-11-23Add UnorderedKeyErrorAmanieu d'Antras-31/+43
2023-11-23Update library/alloc/src/collections/btree/map.rsAmanieu d'Antras-1/+1
Co-authored-by: Joe ST <joe@fbstj.net>
2023-11-23Rewrite the BTreeMap cursor API using gapsAmanieu d'Antras-374/+519
Tracking issue: #107540 Currently, a `Cursor` points to a single element in the tree, and allows moving to the next or previous element while mutating the tree. However this was found to be confusing and hard to use. This PR completely refactors cursors to instead point to a gap between two elements in the tree. This eliminates the need for a "ghost" element that exists after the last element and before the first one. Additionally, `upper_bound` and `lower_bound` now have a much clearer meaning. The ability to mutate keys is also factored out into a separate `CursorMutKey` type which is unsafe to create. This makes the API easier to use since it avoids duplicated versions of each method with and without key mutation. API summary: ```rust impl<K, V> BTreeMap<K, V> { fn lower_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; fn lower_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; fn upper_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; fn upper_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; } struct Cursor<'a, K: 'a, V: 'a>; impl<'a, K, V> Cursor<'a, K, V> { fn next(&mut self) -> Option<(&'a K, &'a V)>; fn prev(&mut self) -> Option<(&'a K, &'a V)>; fn peek_next(&self) -> Option<(&'a K, &'a V)>; fn peek_prev(&self) -> Option<(&'a K, &'a V)>; } struct CursorMut<'a, K: 'a, V: 'a>; impl<'a, K, V> CursorMut<'a, K, V> { fn next(&mut self) -> Option<(&K, &mut V)>; fn prev(&mut self) -> Option<(&K, &mut V)>; fn peek_next(&mut self) -> Option<(&K, &mut V)>; fn peek_prev(&mut self) -> Option<(&K, &mut V)>; unsafe fn insert_after_unchecked(&mut self, key: K, value: V); unsafe fn insert_before_unchecked(&mut self, key: K, value: V); fn insert_after(&mut self, key: K, value: V); fn insert_before(&mut self, key: K, value: V); fn remove_next(&mut self) -> Option<(K, V)>; fn remove_prev(&mut self) -> Option<(K, V)>; fn as_cursor(&self) -> Cursor<'_, K, V>; unsafe fn with_mutable_key(self) -> CursorMutKey<'a, K, V, A>; } struct CursorMutKey<'a, K: 'a, V: 'a>; impl<'a, K, V> CursorMut<'a, K, V> { fn next(&mut self) -> Option<(&mut K, &mut V)>; fn prev(&mut self) -> Option<(&mut K, &mut V)>; fn peek_next(&mut self) -> Option<(&mut K, &mut V)>; fn peek_prev(&mut self) -> Option<(&mut K, &mut V)>; unsafe fn insert_after_unchecked(&mut self, key: K, value: V); unsafe fn insert_before_unchecked(&mut self, key: K, value: V); fn insert_after(&mut self, key: K, value: V); fn insert_before(&mut self, key: K, value: V); fn remove_next(&mut self) -> Option<(K, V)>; fn remove_prev(&mut self) -> Option<(K, V)>; fn as_cursor(&self) -> Cursor<'_, K, V>; unsafe fn with_mutable_key(self) -> CursorMutKey<'a, K, V, A>; } ```
2023-10-28mark constructor of `BinaryHeap` as const fncoekjan-2/+4
2023-10-09Make BTreeSet::new_in constSven Bartscher-1/+1
2023-10-09Make BTreeMap::new_in constSven Bartscher-1/+1
Closes rust-lang/wg-allocators#118
2023-10-04Fix misuses of a vs ancui fliter-1/+1
Signed-off-by: cui fliter <imcusg@gmail.com>
2023-09-16edit `std::collections::VecDeque` docsmxnkarou-2/+2
2023-09-03Expand in-place iteration specialization to Flatten, FlatMap and ArrayChunksThe 8472-2/+9
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-28 05:39:22 +0000