about summary refs log tree commit diff
path: root/src/liballoc/collections/btree
AgeCommit message (Collapse)AuthorLines
2019-03-29improve worst-case performance of BTreeSet difference and intersectionStein Somers-65/+233
2019-03-26adjust MaybeUninit API to discussionsRalf Jung-5/+5
uninitialized -> uninit into_initialized -> assume_init read_initialized -> read set -> write
2019-02-22Rollup merge of #58431 - RalfJung:btree, r=Mark-SimulacrumMazdak Farrokhzad-15/+42
fix overlapping references in BTree This fixes two kinds of overlapping references in BTree (both found by running the BTree test suite in Miri). In `into_slices_mut`, we did `k.into_key_slice_mut()` followed by `self.into_val_slice_mut()` (where `k` is a copy of `self`). Calling `into_val_slice_mut` calls `self.len()`, which creates a shared reference to `NodeHeader`, which unfortunately (due to padding) overlaps with the mutable reference returned by `into_key_slice_mut`. Hence the key slice got (partially) invalidated. The fix is to avoid creating an `&NodeHeader` after the first slice got created. In the iterators, we used to first create the references that will be returned, and then perform the walk on the tree. Walking the tree creates references (such as `&mut InternalNode`) that overlap with all of the keys and values stored in a pointer; in particular, they overlap with the references the iterator will later return. This is fixed by reordering the operations of walking the tree and obtaining the inner references. The test suite still passes (and it passes in Miri now!), but there is a lot of code here that I do not understand...
2019-02-20Rollup merge of #58553 - scottmcm:more-ihle, r=Centrilkennytm-20/+20
Use more impl header lifetime elision Inspired by seeing explicit lifetimes on these two: - https://doc.rust-lang.org/nightly/std/slice/struct.Iter.html#impl-FusedIterator - https://doc.rust-lang.org/nightly/std/primitive.u32.html#impl-Not And a follow-up to https://github.com/rust-lang/rust/pull/54687, that started using IHLE in libcore. Most of the changes in here fall into two big categories: - Removing lifetimes from common traits that can essentially never user a lifetime from an input (particularly `Drop`, `Debug`, and `Clone`) - Forwarding impls that are only possible because the lifetime doesn't matter (like `impl<R: Read + ?Sized> Read for &mut R`) I omitted things that seemed like they could be more controversial, like the handful of iterators that have a `Item: 'static` despite the iterator having a lifetime or the `PartialEq` implementations [where the flipped one cannot elide the lifetime](https://internals.rust-lang.org/t/impl-type-parameter-aliases/9403/2?u=scottmcm). I also removed two lifetimes that turned out to be completely unused; see https://github.com/rust-lang/rust/issues/41960#issuecomment-464557423
2019-02-17Use more impl header lifetime elisionScott McMurray-20/+20
There are two big categories of changes in here - Removing lifetimes from common traits that can essentially never user a lifetime from an input (particularly `Drop` & `Debug`) - Forwarding impls that are only possible because the lifetime doesn't matter (like `impl<R: Read + ?Sized> Read for &mut R`) I omitted things that seemed like they could be more controversial, like the handful of iterators that have a `Item: 'static` despite the iterator having a lifetime or the `PartialEq` implementations where the flipped one cannot elide the lifetime.
2019-02-14split MaybeUninit into several features, expand docs a bitRalf Jung-2/+2
2019-02-13fix invalidating references in BTree iteratorsRalf Jung-13/+21
2019-02-13fix overlapping mutable and shared references in BTreeMap's into_slices_mutRalf Jung-3/+22
2019-02-10libs: doc commentsAlexander Regueiro-5/+5
2019-02-10tests: doc commentsAlexander Regueiro-3/+3
2019-02-03liballoc: revert nested imports style changes.Mazdak Farrokhzad-42/+26
2019-02-02liballoc: fix some idiom lints.Mazdak Farrokhzad-35/+35
2019-02-02liballoc: elide some lifetimes.Mazdak Farrokhzad-38/+37
2019-02-02liballoc: apply uniform_paths.Mazdak Farrokhzad-2/+3
2019-02-02liballoc: prefer imports of borrow from libcore.Mazdak Farrokhzad-9/+7
2019-02-02liballoc: refactor & fix some imports.Mazdak Farrokhzad-33/+42
2019-02-02liballoc: cargo check passes on 2018Mazdak Farrokhzad-6/+6
2019-01-28rename first_mut_ptr -> first_ptr_mutRalf Jung-5/+5
2019-01-28add macro for creating uninitialized arrayRalf Jung-9/+3
2019-01-28avoid some raw ptr casts in BTreeMapRalf Jung-7/+10
2019-01-28avoid mem::uninitialized in BTreeMapRalf Jung-9/+16
2018-12-28Auto merge of #55519 - fhartwig:hashmap-index-example, r=Centrilbors-0/+3
Add example of using the indexing operator to HashMap docs Fixes #52575
2018-12-25Remove licensesMark Rousskov-50/+0
2018-12-11TypoAlexis Beingessner-1/+1
Co-Authored-By: RalfJung <post@ralfj.de>
2018-12-09avoid as_leaf_mut asserting exclusive accessRalf Jung-30/+33
2018-12-09fix BTree creating shared references that are not entirely in-boundsRalf Jung-29/+86
2018-12-07Various minor/cosmetic improvements to codeAlexander Regueiro-6/+6
2018-12-07Fix broken doc testCorey Farwell-1/+1
2018-12-05Fix typo in variable nameCorey Farwell-1/+1
2018-12-04Add example of using the indexing operator to BTreeMap docsCorey Farwell-0/+3
2018-12-02avoid MaybeUninit::get_mut where it is not neededRalf Jung-2/+2
2018-11-15Rollup merge of #55901 - euclio:speling, r=petrochenkovPietro Albini-1/+1
fix various typos in doc comments
2018-11-13fix various typos in doc commentsAndy Russell-1/+1
2018-11-06Format BtreeMap::range_mut examplekngwyu-3/+4
2018-10-23fix typos in various placesMatthias Krüger-1/+1
2018-10-10remove a now outdated commentRalf Jung-3/+0
2018-10-09address RalfJung's commentJorge Aparicio-6/+6
2018-10-09alloc: fix deprecated warningsJorge Aparicio-20/+20
2018-09-29Revert "Auto merge of #53508 - japaric:maybe-uninit, r=RalfJung"Ralf Jung-20/+20
This reverts commit c6e3d7fa3113aaa64602507f39d4627c427742ff, reversing changes made to 4591a245c7eec9f70d668982b1383cd2a6854af5.
2018-09-22address RalfJung's commentJorge Aparicio-6/+6
2018-09-22alloc: fix deprecated warningsJorge Aparicio-20/+20
2018-08-20Replace usages of ptr::offset with ptr::{add,sub}.Corey Farwell-24/+24
2018-07-20data_structures: Add a reference wrapper for pointer-indexed maps/setsVadim Petrochenkov-1/+1
Use `ptr::eq` for comparing pointers
2018-07-02add outlives annotations to `BTreeMap`Niko Matsakis-7/+10
nll requires these annotations, I believe because of https://github.com/rust-lang/rust/issues/29149
2018-07-02Make `BTreeMap::clone()` not allocate when cloning an empty tree.Nicholas Nethercote-1/+10
2018-06-29Move some alloc crate top-level items to a new alloc::collections moduleSimon Sapin-0/+5451
This matches std::collections
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-26 06:45:59 +0000