summary refs log tree commit diff
path: root/library/alloc/src/collections/btree
AgeCommit message (Collapse)AuthorLines
2022-03-20Auto merge of #92962 - frank-king:btree_entry_no_insert, r=Amanieubors-41/+86
BTreeMap::entry: Avoid allocating if no insertion This PR allows the `VacantEntry` to borrow from an empty tree with no root, and to lazily allocate a new root node when the user calls `.insert(value)`.
2022-03-15fix typosDylan DPC-1/+1
2022-03-11Rollup merge of #94826 - allgoewer:fix-retain-documentation, r=yaahcDylan DPC-2/+2
Improve doc wording for retain on some collections I found the documentation wording on the various retain methods on many collections to be unusual. I tried to invert the relation by switching `such that` with `for which` .
2022-03-11Improve doc wording for retain on some collectionsMaik Allgöwer-2/+2
2022-03-10Use implicit capture syntax in format_argsT-O-R-U-S-12/+12
This updates the standard library's documentation to use the new syntax. The documentation is worthwhile to update as it should be more idiomatic (particularly for features like this, which are nice for users to get acquainted with). The general codebase is likely more hassle than benefit to update: it'll hurt git blame, and generally updates can be done by folks updating the code if (and when) that makes things more readable with the new format. A few places in the compiler and library code are updated (mostly just due to already having been done when this commit was first authored).
2022-03-09BTreeMap::entry: Avoid allocating if no insertionFrank King-41/+86
2022-03-07BTree: remove dead data needlessly complicating insertStein Somers-40/+19
2022-02-28Rollup merge of #92399 - Veeupup:fix_vec_typo, r=Dylan-DPCMatthias Krüger-2/+2
fix typo in btree/vec doc: Self -> self this pr fixes #92345 the documentation refers to the object the method is called for, not the type, so it should be using the lower case self.
2022-02-20BTree: simplify test codeStein Somers-138/+118
2022-02-17Rollup merge of #89869 - kpreid:from-doc, r=yaahcMatthias Krüger-0/+4
Add documentation to more `From::from` implementations. For users looking at documentation through IDE popups, this gives them relevant information rather than the generic trait documentation wording “Performs the conversion”. For users reading the documentation for a specific type for any reason, this informs them when the conversion may allocate or copy significant memory versus when it is always a move or cheap copy. Notes on specific cases: * The new documentation for `From<T> for T` explains that it is not a conversion at all. * Also documented `impl<T, U> Into<U> for T where U: From<T>`, the other central blanket implementation of conversion. * The new documentation for construction of maps and sets from arrays of keys mentions the handling of duplicates. Future work could be to do this for *all* code paths that convert an iterable to a map or set. * I did not add documentation to conversions of a specific error type to a more general error type. * I did not add documentation to unstable code. This change was prepared by searching for the text "From<... for" and so may have missed some cases that for whatever reason did not match. I also looked for `Into` impls but did not find any worth documenting by the above criteria.
2022-01-18Replace iterator-based construction of collections by `Into<T>`Júnior Bassani-7/+5
2022-01-16Rollup merge of #92706 - umanwizard:btree, r=dtolnayMatthias Krüger-2/+9
Clarify explicitly that BTree{Map,Set} are ordered. One of the main reasons one would want to use a BTree{Map,Set} rather than a Hash{Map,Set} is because they maintain their keys in sorted order; but this was never explicitly stated in the top-level docs (it was only indirectly alluded to there, and stated explicitly in the docs for `iter`, `values`, etc.) This PR states the ordering guarantee more prominently.
2022-01-15Tweak btree iterator wording to not use 'yield'David Tolnay-4/+5
Yield means something else in the context of generators, which are sufficiently close to iterators that it's better to avoid the terminology collision here.
2022-01-11Address review commentsBrennan Vincent-4/+4
2022-01-11Auto merge of #92070 - rukai:replace_vec_into_iter_with_array_into_iter, ↵bors-2/+2
r=Mark-Simulacrum Replace usages of vec![].into_iter with [].into_iter `[].into_iter` is idiomatic over `vec![].into_iter` because its simpler and faster (unless the vec is optimized away in which case it would be the same) So we should change all the implementation, documentation and tests to use it. I skipped: * `src/tools` - Those are copied in from upstream * `src/test/ui` - Hard to tell if `vec![].into_iter` was used intentionally or not here and not much benefit to changing it. * any case where `vec![].into_iter` was used because we specifically needed a `Vec::IntoIter<T>` * any case where it looked like we were intentionally using `vec![].into_iter` to test it.
2022-01-09Clarify explicitly that BTree{Map,Set} are ordered.Brennan Vincent-2/+8
2022-01-09Compute most of Public/Exported access level in rustc_resolveLamb-0/+3
Mak DefId to AccessLevel map in resolve for export hir_id to accesslevel in resolve and applied in privacy using local def id removing tracing probes making function not recursive and adding comments Move most of Exported/Public res to rustc_resolve moving public/export res to resolve fix missing stability attributes in core, std and alloc move code to access_levels.rs return for some kinds instead of going through them Export correctness, macro changes, comments add comment for import binding add comment for import binding renmae to access level visitor, remove comments, move fn as closure, remove new_key fmt fix rebase fix rebase fmt fmt fix: move macro def to rustc_resolve fix: reachable AccessLevel for enum variants fmt fix: missing stability attributes for other architectures allow unreachable pub in rustfmt fix: missing impl access level + renaming export to reexport Missing impl access level was found thanks to a test in clippy
2022-01-09eplace usages of vec![].into_iter with [].into_iterLucas Kent-2/+2
2021-12-29fix typo in btree/vec doc: Self -> selfVeeupup-2/+2
2021-12-13Rollup merge of #91749 - ssomers:btree_comments, r=Mark-SimulacrumMatthias Krüger-55/+58
BTree: improve public descriptions and comments BTreeSet has always used the term "value" next to and meaning the same thing as "elements" (in the mathematical sense but also used for key-value pairs in BTreeMap), while in the BTreeMap sense these "values" are known as "keys" and definitely not "values". Today I had enough of that. r? `@Mark-Simulacrum`
2021-12-12Rollup merge of #91746 - ssomers:btree_tests, r=Mark-SimulacrumMatthias Krüger-6/+38
Btree: assert more API compatibility Introducing a member such as `BTreeSet::min()` would silently break compatibility if no code calls the existing `BTreeSet::min(set)`. `BTreeSet` is the only btree class silently bringing in stable members, apart from many occurrences of `#[derive(Debug)]` on iterators. r? `@Mark-Simulacrum`
2021-12-11Auto merge of #91761 - matthiaskrgr:rollup-bjowmvz, r=matthiaskrgrbors-19/+18
Rollup of 11 pull requests Successful merges: - #91668 (Remove the match on `ErrorKind::Other`) - #91678 (Add tests fixed by #90023) - #91679 (Move core/stream/stream/mod.rs to core/stream/stream.rs) - #91681 (fix typo in `intrinsics::raw_eq` docs) - #91686 (Fix `Vec::reserve_exact` documentation) - #91697 (Delete Utf8Lossy::from_str) - #91706 (Add unstable book entries for parts of asm that are not being stabilized) - #91709 (Replace iterator-based set construction by *Set::From<[T; N]>) - #91716 (Improve x.py logging and defaults a bit more) - #91747 (Add pierwill to .mailmap) - #91755 (Fix since attribute for const_linked_list_new feature) Failed merges: r? `@ghost` `@rustbot` modify labels: rollup
2021-12-10Rollup merge of #91482 - ↵Matthias Krüger-4/+5
JosephTLyons:update-HashMap-and-BTreeMap-documentation, r=yaahc Update documentation to use `from()` to initialize `HashMap`s and `BTreeMap`s As of Rust 1.56, `HashMap` and `BTreeMap` both have associated `from()` functions. I think using these in the documentation cleans things up a bit. It allows us to remove some of the `mut`s and avoids the Initialize-Then-Modify anti-pattern.
2021-12-10BTree: improve public descriptions and commentsStein Somers-55/+58
2021-12-10BTree: assert presence of derived functionsStein Somers-0/+32
2021-12-10BTree: rename compile-time assertions to match library/alloc/testsStein Somers-6/+6
2021-12-09Replace iterator-based set construction by *Set::From<[T; N]>Júnior Bassani-19/+18
2021-12-04Use IntoIterator for array impl everywhere.Mara Bos-5/+5
2021-12-04Add documentation to more `From::from` implementations.Kevin Reid-0/+4
For users looking at documentation through IDE popups, this gives them relevant information rather than the generic trait documentation wording “Performs the conversion”. For users reading the documentation for a specific type for any reason, this informs them when the conversion may allocate or copy significant memory versus when it is always a move or cheap copy. Notes on specific cases: * The new documentation for `From<T> for T` explains that it is not a conversion at all. * Also documented `impl<T, U> Into<U> for T where U: From<T>`, the other central blanket implementation of conversion. * I did not add documentation to conversions of a specific error type to a more general error type. * I did not add documentation to unstable code. This change was prepared by searching for the text "From<... for" and so may have missed some cases that for whatever reason did not match. I also looked for `Into` impls but did not find any worth documenting by the above criteria.
2021-12-02Use `BTreeMap::from()` instead of using `BTreeMap::new()` with ↵Joseph T Lyons-4/+5
`BTreeMap::insert()`
2021-10-31Rollup merge of #89786 - jkugelman:must-use-len-and-is_empty, r=joshtriplettMatthias Krüger-2/+6
Add #[must_use] to len and is_empty Parent issue: #89692 r? `@joshtriplett`
2021-10-31Rollup merge of #89835 - jkugelman:must-use-expensive-computations, ↵Matthias Krüger-0/+8
r=joshtriplett Add #[must_use] to expensive computations The unifying theme for this commit is weak, admittedly. I put together a list of "expensive" functions when I originally proposed this whole effort, but nobody's cared about that criterion. Still, it's a decent way to bite off a not-too-big chunk of work. Given the grab bag nature of this commit, the messages I used vary quite a bit. I'm open to wording changes. For some reason clippy flagged four `BTreeSet` methods but didn't say boo about equivalent ones on `HashSet`. I stared at them for a while but I can't figure out the difference so I added the `HashSet` ones in. ```rust // Flagged by clippy. alloc::collections::btree_set::BTreeSet<T> fn difference<'a>(&'a self, other: &'a BTreeSet<T>) -> Difference<'a, T>; alloc::collections::btree_set::BTreeSet<T> fn symmetric_difference<'a>(&'a self, other: &'a BTreeSet<T>) -> SymmetricDifference<'a, T> alloc::collections::btree_set::BTreeSet<T> fn intersection<'a>(&'a self, other: &'a BTreeSet<T>) -> Intersection<'a, T>; alloc::collections::btree_set::BTreeSet<T> fn union<'a>(&'a self, other: &'a BTreeSet<T>) -> Union<'a, T>; // Ignored by clippy, but not by me. std::collections::HashSet<T, S> fn difference<'a>(&'a self, other: &'a HashSet<T, S>) -> Difference<'a, T, S>; std::collections::HashSet<T, S> fn symmetric_difference<'a>(&'a self, other: &'a HashSet<T, S>) -> SymmetricDifference<'a, T, S> std::collections::HashSet<T, S> fn intersection<'a>(&'a self, other: &'a HashSet<T, S>) -> Intersection<'a, T, S>; std::collections::HashSet<T, S> fn union<'a>(&'a self, other: &'a HashSet<T, S>) -> Union<'a, T, S>; ``` Parent issue: #89692 r? ```@joshtriplett```
2021-10-30Add #[must_use] to len and is_emptyJohn Kugelman-4/+8
2021-10-31Rollup merge of #89899 - jkugelman:must-use-alloc, r=joshtriplettMatthias Krüger-17/+30
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`
2021-10-27Remove big O notationr00ster91-1/+1
2021-10-21Clarify undefined behaviour for binary heap, btree and hashsetWilfred Hughes-6/+6
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.
2021-10-15Add #[must_use] to remaining alloc functionsJohn Kugelman-17/+30
2021-10-12Add #[must_use] to expensive computationsJohn Kugelman-0/+8
The unifying theme for this commit is weak, admittedly. I put together a list of "expensive" functions when I originally proposed this whole effort, but nobody's cared about that criterion. Still, it's a decent way to bite off a not-too-big chunk of work. Given the grab bag nature of this commit, the messages I used vary quite a bit.
2021-10-11Rollup merge of #89726 - jkugelman:must-use-alloc-constructors, r=joshtriplettGuillaume Gomez-0/+2
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``
2021-10-11Auto merge of #89755 - jkugelman:must-use-conversions-that-move-self, ↵bors-10/+13
r=joshtriplett Add #[must_use] to conversions that move self Everything here got the same message. Is the wording okay? ```rust #[must_use = "`self` will be dropped if the result is not used"] ``` I want to draw attention to these methods in particular: ```rust alloc::sync::Arc<MaybeUninit<T>> unsafe fn assume_init(self) -> Arc<T>; alloc::sync::Arc<[MaybeUninit<T>]> unsafe fn assume_init(self) -> Arc<[T]>; core::pin::Pin<&'a mut T> const fn into_ref(self) -> Pin<&'a T>; core::pin::Pin<&'a mut T> const fn get_mut(self) -> &'a mut T; core::pin::Pin<&'a mut T> const unsafe fn get_unchecked_mut(self) -> &'a mut T; core::pin::Pin<&'a mut T> unsafe fn map_unchecked_mut(self, func: F) -> Pin<&'a mut U>; core::pin::Pin<&'a mut Pin<P>> fn as_deref_mut(self) -> Pin<&'a mut P::Target>; ``` Parent issue: #89692 r? `@joshtriplett`
2021-10-10Add #[must_use] to conversions that move selfJohn Kugelman-10/+13
2021-10-10Add #[must_use] to alloc constructorsJohn Kugelman-0/+2
2021-10-09Add #[must_use] to is_condition testsJohn Kugelman-0/+3
There's nothing insightful to say about these so I didn't write any extra explanations.
2021-10-04Rollup merge of #89443 - cuviper:btree-hash-len, r=dtolnayJubilee-0/+1
Include the length in BTree hashes This change makes it consistent with `Hash` for all other collections.
2021-10-03Rollup merge of #87679 - ssomers:btree_comments, r=joshtriplettManish Goregaokar-10/+8
BTree: refine some comments
2021-10-03Auto merge of #88086 - ssomers:btree_clone_testing, r=dtolnaybors-25/+32
BTree: toughen panicky test of clone() Test did not cover the second half of `clone_subtree` and why this clones key & value first.
2021-10-01Include the length in BTree hashesJosh Stone-0/+1
This change makes it consistent with `Hash` for all other collections.
2021-09-26Auto merge of #89144 - sexxi-goose:insig_stdlib, r=nikomatsakisbors-0/+2
2229: Mark insignificant dtor in stdlib I looked at all public [stdlib Drop implementations](https://doc.rust-lang.org/stable/std/ops/trait.Drop.html#implementors) and categorized them into Insigificant/Maybe/Significant Drop. Reasons are noted here: https://docs.google.com/spreadsheets/d/19edb9r5lo2UqMrCOVjV0fwcSdS-R7qvKNL76q7tO8VA/edit#gid=1838773501 One thing missing from this PR is tagging HashMap as insigificant destructor as that needs some discussion. r? `@Mark-Simulacrum` cc `@nikomatsakis`
2021-09-22PR fixupAman Arora-2/+2
2021-09-212229: Annotate stdlib with insignficant dtorsAman Arora-0/+2
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-07-15 02:36:33 +0000