summary refs log tree commit diff
path: root/library/alloc/src/collections
AgeCommit message (Collapse)AuthorLines
2021-02-06Rollup merge of #81610 - ssomers:btree_emphasize_ord_bound, r=dtolnayMara Bos-54/+191
BTreeMap: make Ord bound explicit, compile-test its absence Most `BTreeMap` and `BTreeSet` members are subject to an `Ord` bound but a fair number of methods are not. To better convey and perhaps later tune the `Ord` bound, make it stand out in individual `where` clauses, instead of once far away at the beginning of an `impl` block. This PR does not introduce or remove any bounds. Also adds compilation test cases checking that the bound doesn't creep in unintended on the historically unbounded methods.
2021-02-04Revert "Avoid leaking block expression values"Felix S. Klock II-1/+1
This reverts commit 4fef39113a514bb270f5661a82fdba17d3e41dbb.
2021-02-02Rollup merge of #81588 - xfix:delete-doc-alias, r=Mark-SimulacrumJack Huey-0/+2
Add doc aliases for "delete" This patch adds doc aliases for "delete". The added aliases are supposed to reference usages `delete` in other programming languages. - `HashMap::remove`, `BTreeMap::remove` -> `Map#delete` and `delete` keyword in JavaScript. - `HashSet::remove`, `BTreeSet::remove` -> `Set#delete` in JavaScript. - `mem::drop` -> `delete` keyword in C++. - `fs::remove_file`, `fs::remove_dir`, `fs::remove_dir_all`-> `File#delete` in Java, `File#delete` and `Dir#delete` in Ruby. Before this change, searching for "delete" in documentation returned no results.
2021-02-02BTreeMap: make Ord bound explicit, compile-test its absenceStein Somers-54/+191
2021-01-31Add doc aliases for "delete"Konrad Borowski-0/+2
This patch adds doc aliases for "delete". The added aliases are supposed to reference usages `delete` in other programming languages. - `HashMap::remove`, `BTreeMap::remove` -> `Map#delete` and `delete` keyword in JavaScript. - `HashSet::remove`, `BTreeSet::remove` -> `Set#delete` in JavaScript. - `mem::drop` -> `delete` keyword in C++. - `fs::remove_file`, `fs::remove_dir`, `fs::remove_dir_all` -> `File#delete` in Java, `File#delete` and `Dir#delete` in Ruby. Before this change, searching for "delete" in documentation returned no results.
2021-01-30Rollup merge of #80886 - RalfJung:stable-raw-ref-macros, r=m-ou-seYuki Okushi-2/+2
Stabilize raw ref macros This stabilizes `raw_ref_macros` (https://github.com/rust-lang/rust/issues/73394), which is possible now that https://github.com/rust-lang/rust/issues/74355 is fixed. However, as I already said in https://github.com/rust-lang/rust/issues/73394#issuecomment-751342185, I am not particularly happy with the current names of the macros. So I propose we also change them, which means I am proposing to stabilize the following in `core::ptr`: ```rust pub macro const_addr_of($e:expr) { &raw const $e } pub macro mut_addr_of($e:expr) { &raw mut $e } ``` The macro name change means we need another round of FCP. Cc `````@rust-lang/libs````` Fixes #73394
2021-01-29rename raw_const/mut -> const/mut_addr_of, and stabilize themRalf Jung-2/+2
2021-01-29Auto merge of #81073 - ssomers:btree_owned_root_vs_dying, r=Mark-Simulacrumbors-32/+73
BTreeMap: prevent tree from ever being owned by non-root node This introduces a new marker type, `Dying`, which is used to note trees which are in the process of deallocation. On such trees, some fields may be in an inconsistent state as we are deallocating the tree. Unfortunately, there's not a great way to express conditional unsafety, so the methods for traversal can cause UB if not invoked correctly, but not marked as such. This is not a regression from the previous state, but rather isolates the destructive methods to solely being called on the dying state.
2021-01-27Auto merge of #81335 - thomwiggers:no-panic-shrink-to, r=Mark-Simulacrumbors-8/+5
Trying to shrink_to greater than capacity should be no-op Per the discussion in https://github.com/rust-lang/rust/issues/56431, `shrink_to` shouldn't panic if you try to make a vector shrink to a capacity greater than its current capacity.
2021-01-27Rollup merge of #81191 - ssomers:btree_more_order_chaos, r=Mark-SimulacrumYuki Okushi-1/+87
BTreeMap: test all borrowing interfaces and test more chaotic order behavior Inspired by #81169, test what happens if you mess up order of the type with which you search (as opposed to the key type). r? `@Mark-Simulacrum`
2021-01-26BTreeMap: stop tree from being owned by non-root nodeStein Somers-32/+73
2021-01-26shrink_to shouldn't panic on len greater than capacityThom Wiggers-8/+5
2021-01-26Auto merge of #81217 - ssomers:btree_bring_back_the_slice, r=Mark-Simulacrumbors-43/+23
BTreeMap: bring back the key slice for immutable lookup Pave the way for binary search, by reverting a bit of #73971, which banned `keys` for misbehaving while it was defined for every `BorrowType`. Adding some `debug_assert`s along the way. r? `@Mark-Simulacrum`
2021-01-23Rollup merge of #81170 - xfix:vecdeque-bug-fix, r=sfacklerJonas Schievink-3/+47
Avoid hash_slice in VecDeque's Hash implementation Fixes #80303.
2021-01-20BTreeMap: bring back the key slice for immutable lookupStein Somers-43/+23
2021-01-19BTreeMap: compile-test all borrowing interfaces and test more chaotic orderStein Somers-1/+87
2021-01-19Rollup merge of #81115 - ssomers:btree_drainy_refactor_4, r=Mark-SimulacrumGuillaume Gomez-121/+8
BTreeMap: prefer bulk_steal functions over specialized ones The `steal_` functions (apart from their return value) are basically specializations of the more general `bulk_steal_` functions. This PR removes the specializations. The library/alloc benchmarks say this is never slower and up to 6% faster. r? ``@Mark-Simulacrum``
2021-01-18Fix soundness issue for `replace_range` and `range`dylni-3/+10
2021-01-18Avoid hash_slice in VecDeque's Hash implementationKonrad Borowski-3/+47
Fixes #80303.
2021-01-18BTreeMap: prefer bulk_steal functions over specialized onesStein Somers-121/+8
2021-01-18BTreeMap: convert search functions to methodsStein Somers-83/+83
2021-01-18Auto merge of #81090 - ssomers:btree_drainy_refactor_2, r=Mark-Simulacrumbors-34/+60
BTreeMap: offer merge in variants with more clarity r? `@Mark-Simulacrum`
2021-01-17Rollup merge of #81082 - ssomers:btree_cleanup_comments, r=Mark-SimulacrumMara Bos-6/+8
BTreeMap: clean up a few more comments And mark `pop` as unsafe. r? ```@Mark-Simulacrum```
2021-01-17Auto merge of #81083 - ssomers:btree_drainy_refactor_1, r=Mark-Simulacrumbors-13/+14
BTreeMap: expose new_internal function and sanitize from_new_internal `new_internal` is the functional core of the imperative `push_internal_level`, and `from_new_internal` can easily do a proper job instead of returning a half-baked node. r? `@Mark-Simulacrum`
2021-01-16BTreeMap: offer merge in variants with more clarityStein Somers-34/+60
2021-01-16Rollup merge of #80681 - ChrisJefferson:logic-error-doc, r=m-ou-seMara Bos-1/+10
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
2021-01-16BTreeMap: expose new_internal function and sanitize from_new_internalStein Somers-13/+14
2021-01-16BTreeMap: clean up a few more commentsStein Somers-6/+8
2021-01-16Auto merge of #77435 - hanmertens:binary_heap_append, r=scottmcmbors-2/+8
Always use extend in BinaryHeap::append This is faster, see #77433. Fixes #77433
2021-01-16Clarify what the effects of a 'logic error' areChris Jefferson-1/+10
2021-01-16Auto merge of #80873 - ssomers:btree_cleanup_slices_4, r=Mark-Simulacrumbors-81/+88
BTreeMap: tougher checks on code using raw into_kv_pointers r? `@Mark-Simulacrum`
2021-01-15Change rebuild heuristic in BinaryHeap::appendHan Mertens-2/+8
See #77433 for why the new heuristic was chosen. Fixes #77433
2021-01-15Rollup merge of #80834 - bugadani:vecdeque, r=oli-obkYuki Okushi-5/+4
Remove unreachable panics from VecDeque::{front/back}[_mut] `VecDeque`'s `front`, `front_mut`, `back` and `back_mut` methods are implemented in terms of the index operator, which causes these functions to contain [unreachable panic calls](https://rust.godbolt.org/z/MTnq1o). This PR reimplements these methods in terms of `get[_mut]` instead.
2021-01-14Remove unreachable panics from VecDequeDániel Buga-5/+4
2021-01-11Add another test case for #79808Yuki Okushi-0/+15
Taken from #80293.
2021-01-10BTreeMap: tougher checks on code using raw into_kv_pointersStein Somers-81/+88
2021-01-08BTreeMap: tougher checks on most uses of copy_nonoverlappingStein Somers-26/+32
2020-12-28Rollup merge of #80448 - m-ou-se:deque-range-version, r=m-ou-seMara Bos-2/+2
Fix stabilization version of deque_range feature. See https://github.com/rust-lang/rust/pull/79022#issuecomment-751315315
2020-12-28Rollup merge of #80430 - xfix:add-length-as-doc-alias, r=steveklabnikMara Bos-0/+5
Add "length" as doc alias to len methods Currently when searching for `length` there are no results: https://doc.rust-lang.org/std/?search=length. This makes `len` methods appear when searching for `length`.
2020-12-28Rollup merge of #80390 - ssomers:btree_cleanup_slices_2, r=Mark-SimulacrumMara Bos-50/+48
BTreeMap: rename the area access methods r? `@Mark-Simulacrum`
2020-12-28Fix stabilization version of deque_range feature.Mara Bos-2/+2
2020-12-28Rollup merge of #80353 - ssomers:btree_test_split_off, r=Mark-SimulacrumDylan DPC-7/+38
BTreeMap: test split_off (and append) more thoroughly Using DeterministicRng as a poor man's property based testing rig. r? ``@Mark-Simulacrum``
2020-12-28Add "length" as doc alias to len methodsKonrad Borowski-0/+5
2020-12-26BTreeMap: rename the area access methodsStein Somers-50/+48
2020-12-26Auto merge of #79520 - ssomers:btree_cleanup_1, r=Mark-Simulacrumbors-64/+17
BTreeMap: clean up access to MaybeUninit arrays Stop exposing and using immutable access to `MaybeUninit` slices when we need and have exclusive access to the tree. r? `@Mark-Simulacrum`
2020-12-26Auto merge of #80354 - ssomers:btree_test_compact, r=Mark-Simulacrumbors-9/+33
BTreeMap: test full nodes a little more r? `@Mark-Simulacrum`
2020-12-26Auto merge of #79022 - SpyrosRoum:stabilize-deque_range, r=m-ou-sebors-6/+2
stabilize deque_range Make #74217 stable, stabilizing `VecDeque::range` and `VecDeque::range_mut`. Pr: #74099 r? `@m-ou-se`
2020-12-25BTreeMap: declare exclusive access to arrays when copying from themStein Somers-64/+17
2020-12-25Rollup merge of #80352 - ssomers:btree_test_diagnostics, r=Mark-SimulacrumDylan DPC-5/+9
BTreeMap: make test cases more explicit on failure r? `@Mark-Simulacrum`
2020-12-24BTreeMap: test full nodes a little moreStein Somers-9/+33
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-07-08 01:53:13 +0000