summary refs log tree commit diff
path: root/library/alloc/src/collections
AgeCommit message (Collapse)AuthorLines
2022-12-05Auto merge of #105046 - scottmcm:vecdeque-vs-vec, r=Mark-Simulacrumbors-5/+12
Send `VecDeque::from_iter` via `Vec::from_iter` Since it's O(1) to convert between them now, might as well reuse the logic. Mostly for the various specializations it does, but might also save some monomorphization work if, say, people collect slice iterators into both `Vec`s and `VecDeque`s.
2022-12-01Fix typo in commentMarkus Everling-1/+1
2022-12-01Make `VecDeque::new_in` unstably constMarkus Everling-2/+1
2022-11-29Send `VecDeque::from_iter` via `Vec::from_iter`Scott McMurray-5/+12
Since it's O(1) to convert between them now, might as well reuse the logic. Mostly for the various specializations it does, but might also save some monomorphization work if, say, people collect slice iterators into both `Vec`s and `VecDeque`s.
2022-11-28Auto merge of #102991 - Sp00ph:master, r=scottmcmbors-1277/+925
Update VecDeque implementation to use head+len instead of head+tail (See #99805) This changes `alloc::collections::VecDeque`'s internal representation from using head and tail indices to using a head index and a length field. It has a few advantages over the current design: * It allows the buffer to be of length 0, which means the `VecDeque::new` new longer has to allocate and could be changed to a `const fn` * It allows the `VecDeque` to fill the buffer completely, unlike the old implementation, which always had to leave a free space * It removes the restriction for the size to be a power of two, allowing it to properly `shrink_to_fit`, unlike the old `VecDeque` * The above points also combine to allow the `Vec<T> -> VecDeque<T>` conversion to be very cheap and guaranteed O(1). I mention this in the `From<Vec<T>>` impl, but it's not a strong guarantee just yet, as that would likely need some form of API change proposal. All the tests seem to pass for the new `VecDeque`, with some slight adjustments. r? `@scottmcm`
2022-11-26Add second test case in `make_contiguous_head_to_end`Markus Everling-10/+49
2022-11-26Improve slow path in `make_contiguous`Markus Everling-36/+76
2022-11-26Don't use `Take` in `SpecExtend` implMarkus Everling-21/+23
2022-11-25Changes according to code reviewMarkus Everling-144/+181
2022-11-20replace unusual grammarTshepang Mbambo-2/+2
2022-11-20Update VecDeque implementationMarkus Everling-1230/+760
2022-11-15`VecDeque::resize` should re-use the buffer in the passed-in elementScott McMurray-2/+7
Today it always copies it for *every* appended element, but one of those clones is avoidable.
2022-11-14Auto merge of #103858 - Mark-Simulacrum:bump-bootstrap, r=pietroalbinibors-12/+12
Bump bootstrap compiler to 1.66 This PR: - Bumps version placeholders to release - Bumps to latest beta - cfg-steps code r? `@pietroalbini`
2022-11-08Rollup merge of #104097 - RalfJung:miri-alloc-benches, r=thomccGuillaume Gomez-15/+19
run alloc benchmarks in Miri and fix UB Miri since recently has a "fake monotonic clock" that works even with isolation. Its measurements are not very meaningful but it means we can run these benches and check them for UB. And that's a good thing since there was UB here: fixes https://github.com/rust-lang/rust/issues/104096. r? ``@thomcc``
2022-11-08Rollup merge of #104093 - RalfJung:test-sizes, r=thomccGuillaume Gomez-0/+1
disable btree size tests on Miri Seems fine not to run these in Miri, they can't have UB anyway. And this lets us do layout randomization in Miri. r? ``@thomcc``
2022-11-07fmtRalf Jung-5/+5
2022-11-07run alloc benchmarks in Miri and fix UBRalf Jung-15/+19
2022-11-07disable btree size tests on MiriRalf Jung-0/+1
2022-11-07Modify comment syntax errorwanghaha-dev-1/+1
2022-11-06Bump version placeholders to releaseMark Rousskov-12/+12
2022-10-15Documentation BTreeMap::append's behavior for already existing keysphilipp-3/+6
2022-10-14more dupe word typosRageking8-1/+1
2022-10-11Rollup merge of #101727 - est31:stabilize_map_first_last, r=m-ou-seMatthias Krüger-20/+10
Stabilize map_first_last Stabilizes the following functions: ```Rust impl<T> BTreeSet<T> { pub fn first(&self) -> Option<&T> where T: Ord; pub fn last(&self) -> Option<&T> where T: Ord; pub fn pop_first(&mut self) -> Option<T> where T: Ord; pub fn pop_last(&mut self) -> Option<T> where T: Ord; } impl<K, V> BTreeMap<K, V> { pub fn first_key_value(&self) -> Option<(&K, &V)> where K: Ord; pub fn last_key_value(&self) -> Option<(&K, &V)> where K: Ord; pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>> where K: Ord; pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>> where K: Ord; pub fn pop_first(&mut self) -> Option<(K, V)> where K: Ord; pub fn pop_last(&mut self) -> Option<(K, V)> where K: Ord; } ``` Closes #62924 ~~Blocked on the [FCP](https://github.com/rust-lang/rust/issues/62924#issuecomment-1179489929) finishing.~~ Edit: It finished!
2022-10-05Fix overconstrained Send impls in btree internalsDavid Tolnay-3/+3
2022-10-01Make `feature(const_btree_len)` implied by `feature(const_btree_new)`Maybe Waffle-4/+20
2022-09-30Stabilize map_first_lastest31-20/+10
2022-09-26remove cfg(bootstrap)Pietro Albini-2/+0
2022-09-26Rollup merge of #102197 - Nilstrieb:const-new-🌲, r=Mark-Simulacrumfee1-dead-6/+6
Stabilize const `BTree{Map,Set}::new` The FCP was completed in #71835. Since `len` and `is_empty` are not const stable yet, this also creates a new feature for them since they previously used the same `const_btree_new` feature.
2022-09-23Put back one of the `use`s for intra-doc mentionsScott McMurray-0/+6
2022-09-23Stabilize const `BTree{Map,Set}::new`Nilstrieb-6/+6
Since `len` and `is_empty` are not const stable yet, this also creates a new feature for them since they previously used the same `const_btree_new` feature.
2022-09-22Make ZST checks in core/alloc more readableScott McMurray-4/+4
There's a bunch of these checks because of special handing for ZSTs in various unsafe implementations of stuff. This lets them be `T::IS_ZST` instead of `mem::size_of::<T>() == 0` every time, making them both more readable and more terse. *Not* proposed for stabilization at this time. Would be `pub(crate)` except `alloc` wants to use it too. (And while it doesn't matter now, if we ever get something like 85836 making it a const can help codegen be simpler.)
2022-09-10Alternate approach; just modify DrainBen Kimock-52/+59
2022-09-10Remove &[T] from vec_deque::DrainBen Kimock-23/+41
2022-09-02Fix internal doc linkChris Denton-1/+3
The doc link from `DedupSortedIter` to `BTreeMap::bulk_build_from_sorted_iter` was broken when building internal documentation,
2022-08-31Fix a bunch of typoDezhi Wu-1/+1
This PR will fix some typos detected by [typos]. I only picked the ones I was sure were spelling errors to fix, mostly in the comments. [typos]: https://github.com/crate-ci/typos
2022-08-26Rollup merge of #95005 - ssomers:btree_static_assert, r=thomccGuillaume Gomez-7/+9
BTree: evaluate static type-related check at compile time `assert`s like the ones replaced here would only go off when you run the right test cases, if the code were ever incorrectly changed such that rhey would trigger. But [inspired on a nice forum question](https://users.rust-lang.org/t/compile-time-const-generic-parameter-check/69202), they can be checked at compile time.
2022-08-23Auto merge of #99917 - yaahc:error-in-core-move, r=thomccbors-0/+15
Move Error trait into core This PR moves the error trait from the standard library into a new unstable `error` module within the core library. The goal of this PR is to help unify error reporting across the std and no_std ecosystems, as well as open the door to integrating the error trait into the panic reporting system when reporting panics whose source is an errors (such as via `expect`). This PR is a rewrite of https://github.com/rust-lang/rust/pull/90328 using new compiler features that have been added to support error in core.
2022-08-22Move error trait into coreJane Losare-Lusby-0/+15
2022-08-22Rollup merge of #100331 - lo48576:try-reserve-preserve-on-failure, r=thomccDylan DPC-2/+4
Guarantee `try_reserve` preserves the contents on error Update doc comments to make the guarantee explicit. However, some implementations does not have the statement though. * `HashMap`, `HashSet`: require guarantees on hashbrown side. * `PathBuf`: simply redirecting to `OsString`. Fixes #99606.
2022-08-21Replace most uses of `pointer::offset` with `add` and `sub`Maybe Waffle-2/+2
2022-08-10Guarantee `try_reserve` preserves the contents on errorYOSHIOKA Takuma-2/+4
Update doc comments to make the guarantee explicit. However, some implementations does not have the statement though. * `HashMap`, `HashSet`: require guarantees on hashbrown side. * `PathBuf`: simply redirecting to `OsString`. Fixes #99606.
2022-07-18Add `PhantomData` marker for dropck to `BTreeMap`Frank Steffahn-4/+26
closes #99408
2022-06-24Rollup merge of #98039 - tnballo:master, r=thomccYuki Okushi-13/+117
Fix `panic` message for `BTreeSet`'s `range` API and document `panic` cases Currently, the `panic` cases for [`BTreeSet`'s `range` API](https://doc.rust-lang.org/std/collections/struct.BTreeSet.html#method.range) are undocumented and produce a slightly wrong `panic` message (says `BTreeMap` instead of `BTreeSet`). Panic case 1 code: ```rust use std::collections::BTreeSet; use std::ops::Bound::Excluded; fn main() { let mut set = BTreeSet::new(); set.insert(3); set.insert(5); set.insert(8); for &elem in set.range((Excluded(&3), Excluded(&3))) { println!("{elem}"); } } ``` Panic case 1 message: ``` thread 'main' panicked at 'range start and end are equal and excluded in BTreeMap', /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/alloc/src/collections/btree/search.rs:105:17 note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace ``` Panic case 2 code: ```rust use std::collections::BTreeSet; use std::ops::Bound::Included; fn main() { let mut set = BTreeSet::new(); set.insert(3); set.insert(5); set.insert(8); for &elem in set.range((Included(&8), Included(&3))) { println!("{elem}"); } } ``` Panic case 2: ``` thread 'main' panicked at 'range start is greater than range end in BTreeMap', /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/alloc/src/collections/btree/search.rs:110:17 note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace ``` This PR fixes the output messages to say `BTreeSet`, adds the relevant unit tests, and updates the documentation for the API.
2022-06-23Fix BTreeSet's range API panic message, documenttnballo-13/+117
2022-06-23Rollup merge of #96173 - jmaargh:jmaargh/with-capacity-doc-fix, r=Dylan-DPCMichael Goulet-30/+37
Fix documentation for `with_capacity` and `reserve` families of methods Fixes #95614 Documentation for the following methods - `with_capacity` - `with_capacity_in` - `with_capacity_and_hasher` - `reserve` - `reserve_exact` - `try_reserve` - `try_reserve_exact` was inconsistent and often not entirely correct where they existed on the following types - `Vec` - `VecDeque` - `String` - `OsString` - `PathBuf` - `BinaryHeap` - `HashSet` - `HashMap` - `BufWriter` - `LineWriter` since the allocator is allowed to allocate more than the requested capacity in all such cases, and will frequently "allocate" much more in the case of zero-sized types (I also checked `BufReader`, but there the docs appear to be accurate as it appears to actually allocate the exact capacity). Some effort was made to make the documentation more consistent between types as well.
2022-06-21remove use of &Alloc in btree testsRalf Jung-6/+6
2022-06-19Fix documentation for with_capacity and reserve families of methodsjmaargh-30/+37
Documentation for the following methods with_capacity with_capacity_in with_capacity_and_hasher reserve reserve_exact try_reserve try_reserve_exact was inconsistent and often not entirely correct where they existed on the following types Vec VecDeque String OsString PathBuf BinaryHeap HashSet HashMap BufWriter LineWriter since the allocator is allowed to allocate more than the requested capacity in all such cases, and will frequently "allocate" much more in the case of zero-sized types (I also checked BufReader, but there the docs appear to be accurate as it appears to actually allocate the exact capacity). Some effort was made to make the documentation more consistent between types as well. Fix with_capacity* methods for Vec Fix *reserve* methods for Vec Fix docs for *reserve* methods of VecDeque Fix docs for String::with_capacity Fix docs for *reserve* methods of String Fix docs for OsString::with_capacity Fix docs for *reserve* methods on OsString Fix docs for with_capacity* methods on HashSet Fix docs for *reserve methods of HashSet Fix docs for with_capacity* methods of HashMap Fix docs for *reserve methods on HashMap Fix expect messages about OOM in doctests Fix docs for BinaryHeap::with_capacity Fix docs for *reserve* methods of BinaryHeap Fix typos Fix docs for with_capacity on BufWriter and LineWriter Fix consistent use of `hasher` between `HashMap` and `HashSet` Fix warning in doc test Add test for capacity of vec with ZST Fix doc test error
2022-06-19Rollup merge of #98233 - RalfJung:ref-alloc, r=thomccDylan DPC-6/+6
Remove accidental uses of `&A: Allocator` Cc https://github.com/rust-lang/rust/issues/98232 Fixes https://github.com/rust-lang/rust/issues/98176 (for real this time)
2022-06-18make btree not use &A: Allocator instanceRalf Jung-6/+6
2022-06-18Auto merge of #98004 - paolobarbolini:vecdeque-extend-trustedlen, r=the8472bors-0/+175
Add VecDeque::extend from TrustedLen specialization Continuation of #95904 Inspired by how [`VecDeque::copy_slice` works](https://github.com/rust-lang/rust/blob/c08b235a5ce10167632bb0fddcd0c5d67f2d42e3/library/alloc/src/collections/vec_deque/mod.rs#L437-L454). ## Benchmarks Before ``` test vec_deque::bench_extend_chained_bytes ... bench: 1,026 ns/iter (+/- 17) test vec_deque::bench_extend_chained_trustedlen ... bench: 1,024 ns/iter (+/- 40) test vec_deque::bench_extend_trustedlen ... bench: 637 ns/iter (+/- 693) ``` After ``` test vec_deque::bench_extend_chained_bytes ... bench: 828 ns/iter (+/- 24) test vec_deque::bench_extend_chained_trustedlen ... bench: 25 ns/iter (+/- 1) test vec_deque::bench_extend_trustedlen ... bench: 21 ns/iter (+/- 0) ``` ## Why do it this way https://rust.godbolt.org/z/15qY1fMYh The Compiler Explorer example shows how "just" removing the capacity check, like the [`Vec` `TrustedLen` specialization](https://github.com/rust-lang/rust/blob/c08b235a5ce10167632bb0fddcd0c5d67f2d42e3/library/alloc/src/vec/spec_extend.rs#L22-L58) does, wouldn't have been enough for `VecDeque`. `wrap_add` would still have greatly limited what LLVM could do while optimizing. --- r? `@the8472`
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-07-04 04:52:29 +0000