about summary refs log tree commit diff
path: root/src/liballoc
AgeCommit message (Collapse)AuthorLines
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/+106
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 #68592 - pdbrito:master, r=jonas-schievinkYuki Okushi-1/+1
fix: typo in vec.rs
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-28Include empty BTreeMap in clone_from testsCharles Gleason-2/+2
2020-01-28Format safety comment as per tidyCharles Gleason-1/+1
Co-Authored-By: Ashley Mannix <ashleymannix@live.com.au>
2020-01-28Auto merge of #68529 - TimDiekmann:rename-alloc, r=Amanieubors-26/+26
Rename `Alloc` to `AllocRef` The allocator-wg has decided to merge this change upstream in https://github.com/rust-lang/wg-allocators/issues/8#issuecomment-577122958. This renames `Alloc` to `AllocRef` because types that implement `Alloc` are a reference, smart pointer, or ZSTs. It is not possible to have an allocator like `MyAlloc([u8; N])`, that owns the memory and also implements `Alloc`, since that would mean, that moving a `Vec<T, MyAlloc>` would need to correct the internal pointer, which is not possible as we don't have move constructors. For further explanation please see https://github.com/rust-lang/wg-allocators/issues/8#issuecomment-489464843 and the comments after that one. Additionally it clarifies the semantics of `Clone` on an allocator. In the case of `AllocRef`, it is clear that the cloned handle still points to the same allocator instance, and that you can free data allocated from one handle with another handle. The initial proposal was to rename `Alloc` to `AllocHandle`, but `Ref` expresses the semantics better than `Handle`. Also, the only appearance of `Handle` in `std` are for windows specific resources, which might be confusing. Blocked on https://github.com/rust-lang/miri/pull/1160
2020-01-28fix: typo in vec.rsPedro de Brito-1/+1
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-28Auto merge of #68234 - CAD97:slice-from-raw-parts, r=KodrAusbors-1/+0
Stabilize ptr::slice_from_raw_parts[_mut] Closes #36925, the tracking issue. Initial impl: #60667 r? @rust-lang/libs In addition to stabilizing, I've adjusted the example of `ptr::slice_from_raw_parts` to use `slice_from_raw_parts` instead of `slice_from_raw_parts_mut`, which was unnecessary for the example as written.
2020-01-27Rename `Alloc` to `AllocRef`Tim Diekmann-26/+26
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-21Auto merge of #68154 - ssomers:btreemap_navigation_benches, r=Mark-Simulacrumbors-8/+69
Add more BTreeMap/BTreeSet benchmarks regarding iteration Serving #67073 or other developments
2020-01-19Auto merge of #67758 - ssomers:testing_range, r=Mark-Simulacrumbors-31/+150
More thorough testing of BTreeMap::range Test more of the paths in the `range_search` function in map.rs
2020-01-17Allow added string.insert benchmarks to compileStein Somers-1/+1
2020-01-16Auto merge of #67339 - CAD97:rc-provenance, r=sfacklerbors-4/+24
Use pointer offset instead of deref for A/Rc::into_raw Internals thread: https://internals.rust-lang.org/t/rc-and-internal-mutability/11463/2?u=cad97 The current implementation of (`A`)`Rc::into_raw` uses the `Deref::deref` implementation to get the pointer-to-data that is returned. This is problematic in the proposed Stacked Borrow rules, as this only gets shared provenance over the data location. (Note that the strong/weak counts are `UnsafeCell` (`Cell`/`Atomic`) so shared provenance can still mutate them, but the data itself is not.) When promoted back to a real reference counted pointer, the restored pointer can be used for mutation through `::get_mut` (if it is the only surviving reference). However, this mutates through a pointer ultimately derived from a `&T` borrow, violating the Stacked Borrow rules. There are three known potential solutions to this issue: - Stacked Borrows is wrong, liballoc is correct. - Fully admit (`A`)`Rc` as an "internal mutability" type and store the data payload in an `UnsafeCell` like the strong/weak counts are. (Note: this is not needed generally since the `RcBox`/`ArcInner` is stored behind a shared `NonNull` which maintains shared write provenance as a raw pointer.) - Adjust `into_raw` to do direct manipulation of the pointer (like `from_raw`) so that it maintains write provenance and doesn't derive the pointer from a reference. This PR implements the third option, as recommended by @RalfJung. Potential future work: provide `as_raw` and `clone_raw` associated functions to allow the [`&T` -> (`A`)`Rc<T>` pattern](https://internals.rust-lang.org/t/rc-and-internal-mutability/11463/2?u=cad97) to be used soundly without creating (`A`)`Rc` from references.
2020-01-15Rollup merge of #68123 - crlf0710:linked_list_cursor, r=AmanieuDylan DPC-24/+707
Implement Cursor for linked lists. (RFC 2570). cc. #58533 cc. @Gankra r? @Amanieu
2020-01-14Stabilize ptr::slice_from_raw_parts[_mut]CAD97-1/+0
2020-01-14Update APIs according to RFC change suggestions.Charles Lew-18/+85
2020-01-12Add more BTreeMap/BTreeSet benchmarks regarding iterationStein Somers-8/+69
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-11Revert "Rollup merge of #67727 - Dylan-DPC:stabilise/remove_item, ↵Lzu Tao-1/+3
r=alexcrichton" This reverts commit 4ed415b5478c74094c2859abfddb959588cd6bb1, reversing changes made to 3cce950743e8aa74a4378dfdefbbc80223a00865.
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-07Auto merge of #67312 - cuviper:clone-box-slice, r=SimonSapinbors-42/+1
Simplify Clone for Box<[T]> The bespoke `BoxBuilder` was basically a very simple `Vec`. Instead, let's clone to a real `Vec`, with all of its specialization for the task, then convert back to `Box<[T]>`.
2020-01-07Rollup merge of #67929 - mgrachev:patch-1, r=jonas-schievinkYuki Okushi-1/+1
Formatting an example for method Vec.retain
2020-01-06oh the one that was left behinddylan_DPC-1/+0
2020-01-06stabilise itdylan_DPC-1/+1
2020-01-06stabilise remove_itemdylan_DPC-1/+0
2020-01-06Formatting an example for method Vec.retainGrachev Mikhail-1/+1
2020-01-06Rollup merge of #67873 - Dylan-DPC:feature/change-remove-to-partial, r=AmanieuDylan DPC-1/+22
change remove to have a PartialEq bound Addresses [comment](https://github.com/rust-lang/rust/pull/67727#issuecomment-570660301). References #40062 r? @Amanieu
2020-01-05add feature gatedylan_DPC-0/+1
2020-01-05removed blank linedylan_DPC-1/+0
2020-01-04ef em ti ... :Pdylan_DPC-7/+6
2020-01-04Rollup merge of #67812 - ssomers:btreemap_internal_doc, r=rkruppeDylan DPC-15/+39
Tweak and extend internal BTreeMap documentation, including debug asserts. Gathered from work on various other pull requests (e.g. #67725, #67686).
2020-01-04add testsdylan_DPC-0/+15
2020-01-04add partial eq bound to remove_itemdylan_DPC-1/+8
2020-01-04Tweak and extend internal documentation, including debug asserts.Stein Somers-15/+39
Co-Authored-By: Robin Kruppe <robin.kruppe@gmail.com>
2020-01-02Use drop instead of the toilet closure `|_| ()`Lzu Tao-2/+2
2019-12-31More thorough testing of BTreeMap::rangeStein Somers-31/+150
2019-12-28Auto merge of #67459 - ssomers:#67438, r=RalfJungbors-25/+152
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-28Rollup merge of #67629 - kraai:remove-redundant-link-texts, r=steveklabnikOliver Scherer-8/+8
Remove redundant link texts Most of these links are followed by a parenthesized expression. I think that the redundant link texts were added to prevent interpretation as an inline link. This is unnecessary since the closing square bracket and opening parenthesis are separated by whitespace.
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-26 03:15:47 +0000