summary refs log tree commit diff
path: root/src/liballoc/collections
AgeCommit message (Collapse)AuthorLines
2020-02-26Auto merge of #67290 - jonas-schievink:leak-audit, r=KodrAusbors-112/+195
Audit liballoc for leaks in `Drop` impls when user destructor panics Inspired by https://github.com/rust-lang/rust/pull/67243 and https://github.com/rust-lang/rust/pull/67235, this audits and hopefully fixes the remaining `Drop` impls in liballoc for resource leaks in the presence of panics in destructors called by the affected `Drop` impl. This does not touch `Hash{Map,Set}` since they live in hashbrown. They have similar issues though. r? @KodrAus
2020-02-20Rollup merge of #68705 - BijanT:ll_remove, r=Mark-SimulacrumDylan DPC-0/+46
Add LinkedList::remove() LinkedList::remove() removes the element at the specified index and returns it. I added this because I think having a remove function would be useful to have, and similar functions are in other containers, like Vec and HashMap. I'm not sure if adding a feature like this requires an RFC or not, so I'm sorry if this PR is premature.
2020-02-19Add LinkedList::remove()Bijan Tabatabai-0/+46
LinkedList::remove() removes the element at the specified index and returns it. Signed-off-by: Bijan Tabatabai <bijan311@yahoo.com>
2020-02-16Fix comments outdated during #66648Stein Somers-5/+4
2020-02-09Rollup merge of #68834 - ssomers:btree_first_last_fix68829, r=KodrAusDylan DPC-10/+14
Fix and test implementation of BTreeMap's first/last_entry, pop_first/last Properly implement and test `first_entry` & `last_entry` to fix problem report #68829
2020-02-07Lift range_search up one level of abstractionStein Somers-42/+45
2020-02-04Fix and test implementation of BTreeMap's first_entry, last_entry, ↵Stein Somers-10/+14
pop_first, pop_last
2020-01-31Bundle and document 6 BTreeMap navigation algorithmsStein Somers-236/+314
2020-01-30Rollup merge of #68468 - ssomers:btreemap_prefer_middle, r=Mark-SimulacrumDylan DPC-119/+132
BTreeMap: tag and explain unsafe internal functions or assert preconditions #68418 concluded that it's not desirable to tag all internal functions with preconditions as being unsafe. This PR does it to some functions, documents why, and elsewhere enforces the preconditions with asserts.
2020-01-30Rollup merge of #66648 - crgl:btree-clone-from, r=AmanieuDylan DPC-9/+86
Implement clone_from for BTreeMap and BTreeSet See #28481. This results in up to 90% speedups on simple data types when `self` and `other` are the same size, and is generally comparable or faster. Some concerns: 1. This implementation requires an `Ord` bound on the `Clone` implementation for `BTreeMap` and `BTreeSet`. Since these structs can only be created externally for keys with `Ord` implemented, this should be fine? If not, there's certainly a less safe way to do this. 2. Changing `next_unchecked` on `RangeMut` to return mutable key references allows for replacing the entire overlapping portion of both maps without changing the external interface in any way. However, if `clone_from` fails it can leave the `BTreeMap` in an invalid state, which might be unacceptable. ~This probably needs an FCP since it changes a trait bound, but (as far as I know?) that change cannot break any external code.~
2020-01-29BTreeMap: tag and explain unsafe internal functions or assert preconditionsStein Somers-119/+132
Co-Authored-By: Mark Rousskov <mark.simulacrum@gmail.com>
2020-01-29Rollup merge of #68378 - billyrieger:btreemap-remove-entry, r=KodrAusYuki Okushi-1/+30
Add BTreeMap::remove_entry Implements https://github.com/rust-lang/rust/issues/66714.
2020-01-28Reformat truncation section of clone_fromCharles Gleason-10/+10
2020-01-28Add private is_empty method to RangeMutCharles Gleason-3/+7
2020-01-28Format safety comment as per tidyCharles Gleason-1/+1
Co-Authored-By: Ashley Mannix <ashleymannix@live.com.au>
2020-01-28Add BTreeMap::remove_entryBilly Rieger-1/+30
Mainly for API parity with HashMap. - Add BTreeMap::remove_entry - Rewrite BTreeMap::remove to use remove_entry - Use btreemap_remove_entry feature in doc comment
2020-01-27Rename `Alloc` to `AllocRef`Tim Diekmann-1/+1
2020-01-21Rollup merge of #67686 - ssomers:keys_start_slasher, r=Mark-SimulacrumMazdak Farrokhzad-65/+24
Simplify NodeHeader by avoiding slices in BTreeMaps with shared roots Simplify a complicated piece of code that creates slices of keys in node leaves.
2020-01-21Declare unsafe functions that can no longer handle shared rootsStein Somers-6/+6
2020-01-21trade in outdated comments for correct onesStein Somers-2/+2
2020-01-19FormatJonas Schievink-2/+5
2020-01-19Move VecDeque Drain iterator to new fileJonas Schievink-121/+131
2020-01-19Avoid leak in DrainFilter when a drop panicsJonas Schievink-1/+15
2020-01-19Fix leak in VecDeque::drain when drop panicsJonas Schievink-34/+48
2020-01-19Fix leak in btree_map::IntoIter when drop panicsJonas Schievink-1/+16
2020-01-19Fix `VecDeque::truncate` leak on drop panicJonas Schievink-1/+16
2020-01-19Fix `binary_heap::DrainSorted` drop leak on panicsJonas Schievink-2/+14
2020-01-14Update APIs according to RFC change suggestions.Charles Lew-18/+85
2020-01-12Address review comments.Charles Lew-2/+33
2020-01-12Address review comments.Charles Lew-83/+161
2020-01-12Implement Cursor for linked lists. (RFC 2570).Charles Lew-24/+531
2020-01-10Simplify NodeHeader by avoiding slices in BTreeMaps with shared rootsStein Somers-60/+19
2020-01-09Apply suggestions from code reviewStein Somers-1/+2
Co-Authored-By: Ralf Jung <post@ralfj.de>
2020-01-09Simplify into_key_slice_mut and document bits and bobsStein Somers-13/+20
2020-01-04Tweak and extend internal documentation, including debug asserts.Stein Somers-15/+39
Co-Authored-By: Robin Kruppe <robin.kruppe@gmail.com>
2019-12-28Auto merge of #67459 - ssomers:#67438, r=RalfJungbors-24/+30
prune ill-conceived BTreeMap iter_mut assertion and test its mutability Proposal to deal with #67438 (and I'm more sure now that this is the right thing to do). Passes testing with miri.
2019-12-26prune ill-conceived BTreeMap iter_mut assertion and test moreStein Somers-24/+30
2019-12-26Remove redundant link textsMatthew Kraai-5/+5
2019-12-23Implement clone_from for BTree collectionsCharles Gleason-1/+66
2019-12-23Make RangeMut::next_unchecked() output a mutable key referenceCharles Gleason-7/+15
2019-12-22Format the worldMark Rousskov-994/+657
2019-12-21Require issue = "none" over issue = "0" in unstable attributesRoss MacArthur-1/+1
2019-12-18Propagate cfg bootstrapMark Rousskov-4/+1
2019-12-14Auto merge of #67136 - oli-obk:const_stability, r=Centrilbors-0/+4
Require stable/unstable annotations for the constness of all stable fns with a const modifier r? @RalfJung @Centril Every `#[stable]` const fn now needs either a `#[rustc_const_unstable]` attribute or a `#[rustc_const_stable]` attribute. You can't silently stabilize the constness of a function anymore.
2019-12-13Rollup merge of #67235 - jonas-schievink:vecdeque-leak, r=KodrAusMazdak Farrokhzad-1/+13
VecDeque: drop remaining items on destructor panic Closes https://github.com/rust-lang/rust/issues/67232
2019-12-13Require stable/unstable annotations for the constness of all stable ↵Oliver Scherer-0/+4
functions with a `const` modifier
2019-12-13Rollup merge of #67243 - jonas-schievink:linkedlist-drop, r=KodrAusMazdak Farrokhzad-1/+15
LinkedList: drop remaining items when drop panics https://github.com/rust-lang/rust/pull/67235, but for `LinkedList`, which has the same issue. I've also copied over the other drop-related tests from `VecDeque` since AFAICT `LinkedList` didn't have any.
2019-12-13Rollup merge of #66341 - crgl:vec-deque-extend, r=AmanieuMazdak Farrokhzad-1/+16
Match `VecDeque::extend` to `Vec::extend_desugared` Currently, `VecDeque::extend` [does not reserve at all](https://github.com/rust-lang/rust/pull/65069#discussion_r333166522). This implementation still runs a check every iteration of the loop, but should reallocate at most once for the common cases where the `size_hint` lower bound is exact. Further optimizations in the future could improve this for some common cases, but given the complexity of the `Vec::extend` implementation it's not immediately clear that this would be worthwhile.
2019-12-12Add comment to `Dropper`Jonas Schievink-0/+2
2019-12-12LinkedList: drop remaining items when drop panicsJonas Schievink-1/+15
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-04-28 11:16:38 +0000