about summary refs log tree commit diff
path: root/src/liballoc/collections/btree/node.rs
AgeCommit message (Collapse)AuthorLines
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-3/+22
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-14split MaybeUninit into several features, expand docs a bitRalf Jung-2/+2
2019-02-13fix invalidating references in BTree iteratorsRalf Jung-1/+1
2019-02-13fix overlapping mutable and shared references in BTreeMap's into_slices_mutRalf Jung-3/+22
2019-02-10libs: doc commentsAlexander Regueiro-2/+2
2019-02-10tests: doc commentsAlexander Regueiro-3/+3
2019-02-03liballoc: revert nested imports style changes.Mazdak Farrokhzad-10/+6
2019-02-02liballoc: fix some idiom lints.Mazdak Farrokhzad-10/+10
2019-02-02liballoc: refactor & fix some imports.Mazdak Farrokhzad-6/+10
2019-02-02liballoc: cargo check passes on 2018Mazdak Farrokhzad-2/+2
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-25Remove licensesMark Rousskov-10/+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-02avoid MaybeUninit::get_mut where it is not neededRalf Jung-2/+2
2018-11-13fix various typos in doc commentsAndy Russell-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-06-29Move some alloc crate top-level items to a new alloc::collections moduleSimon Sapin-0/+1622
This matches std::collections