summary refs log tree commit diff
path: root/library/alloc/src/collections/btree/node.rs
AgeCommit message (Collapse)AuthorLines
2020-11-09BTreeMap: fix pointer provenance rules, make borrowing explicitStein Somers-246/+326
2020-10-28fix some incorrect aliasing in the BTreeRalf Jung-4/+8
2020-10-25Merge remote-tracking branch 'upstream/master' into box-allocTim Diekmann-54/+40
2020-10-24BTreeMap: stop mistaking node::MIN_LEN as a node level constraintStein Somers-1/+1
2020-10-20BTreeMap: less sharing, more similarity between leaf and internal nodesStein Somers-45/+36
2020-10-20BTreeMap: reuse BoxedNode instances directly instead of their contentsStein Somers-7/+3
2020-10-17Rollup merge of #77932 - ssomers:btree_cleanup_gdb, r=Mark-SimulacrumDylan DPC-1/+0
BTreeMap: improve gdb introspection of BTreeMap with ZST keys or values I accidentally pushed an earlier revision in #77788: it changes the index of tuples for BTreeSet from ""[{}]".format(i) to "key{}".format(i). Which doesn't seem to make the slightest difference on my linux box nor on CI. In fact, gdb doesn't make any distinction between "key{}" and "val{}" for a BTreeMap either, leading to confusing output if you test more. But easy to improve. r? @Mark-Simulacrum
2020-10-16Merge branch 'master' into box-allocTim Diekmann-31/+57
2020-10-14BTreeMap: making PartialCmp/PartialEq explicit and testedStein Somers-7/+29
2020-10-14BTreeMap: improve gdb introspection of BTreeMap with ZST keys or valuesStein Somers-1/+0
2020-10-07Support custom allocators in `Box`Tim Diekmann-1/+1
Remove `Box::leak_with_alloc` Add leak-test for box with allocator Rename `AllocErr` to `AllocError` in leak-test Add `Box::alloc` and adjust examples to use the new API
2020-10-05BTreeMap: derive type-specific variants of node_as_mut and cast_uncheckedStein Somers-24/+28
2020-10-05Rollup merge of #77471 - ssomers:btree_cleanup_3, r=Mark-SimulacrumDylan DPC-7/+7
BTreeMap: refactoring around edges, missed spots Tweaks from #77244 (and more) that are really inconsistencies in #77005. r? @Mark-Simulacrum
2020-10-05Rollup merge of #77395 - ssomers:btree_love_the_leaf_edge_comments, ↵Dylan DPC-22/+12
r=Mark-Simulacrum BTreeMap: admit the existence of leaf edges in comments The btree code is ambiguous about leaf edges (i.e., edges within leaf nodes). Iteration relies on them heavily, but some of the comments suggest there are no leaf edges (extracted from #77025) r? @Mark-Simulacrum
2020-10-03BTreeMap: refactoring around edges, missed spotsStein Somers-7/+7
2020-10-01BTreeMap: use Unique::from to avoid a cast where type information existsStein Somers-1/+1
2020-10-01BTreeMap: admit the existence of leaf edges in commentsStein Somers-22/+12
2020-09-25BTreeMap: various tweaksStein Somers-61/+50
2020-09-25BTreeMap: introduce edge methods similar to those of keys and valuesStein Somers-24/+34
2020-09-25BTreeMap: refactor correct_childrens_parent_linksStein Somers-26/+16
2020-09-20BTreeMap: extra testing unveiling mistakes in future PRStein Somers-6/+6
2020-09-20Rollup merge of #76926 - ssomers:btree_cleanup_1, r=Mark-SimulacrumRalf Jung-4/+4
BTreeMap: code readability tweaks Gathered over the past months r? @Mark-Simulacrum
2020-09-19BTreeMap: wrap node's raw parent pointer in NonNullStein Somers-20/+22
2020-09-19BTreeMap: code readability tweaksStein Somers-4/+4
2020-09-16BTreeMap: avoid slices even moreStein Somers-16/+29
2020-09-13Rollup merge of #76527 - fusion-engineering-forks:cleanup-uninit, ↵Jonas Schievink-3/+3
r=jonas-schievink Remove internal and unstable MaybeUninit::UNINIT. Looks like it is no longer necessary, as `uninit_array()` can be used instead in the few cases where it was needed. (I wanted to just add `#[doc(hidden)]` to remove clutter from the documentation, but looks like it can just be removed entirely.)
2020-09-10BTreeMap: pull the map's root out of NodeRefStein Somers-68/+27
2020-09-09Remove internal and unstable MaybeUninit::UNINIT.Mara Bos-3/+3
Looks like it is no longer necessary, as uninit_array() can be used instead in the few cases where it was needed.
2020-09-09BTreeMap: avoid aliasing by avoiding slicesStein Somers-150/+187
2020-09-09make as_leaf return a raw pointer, to reduce aliasing assumptionsRalf Jung-7/+12
2020-09-05rename MaybeUninit slice methodsRalf Jung-11/+15
first_ptr -> slice_as_ptr first_ptr_mut -> slice_as_mut_ptr slice_get_ref -> slice_assume_init_ref slice_get_mut -> slice_assume_init_mut
2020-08-19BTreeMap: introduce marker::ValMut and reserve marker::Mut for unique accessStein Somers-3/+35
2020-08-14Rollup merge of #75519 - ssomers:btree_splitpoint_cleanup, r=Mark-SimulacrumTyler Mandry-31/+11
BTreeMap: refactor splitpoint and move testing over to unit test r? @Mark-Simulacrum
2020-08-14Rollup merge of #75195 - ssomers:btree_split_up_into_kv_mut, r=Mark-SimulacrumTyler Mandry-6/+16
BTreeMap: purge innocent use of into_kv_mut Replace the use of `into_kv_mut` into more precise calls. This makes more sense if you know that the single remaining use of `into_kv_mut` is in fact evil and can be trialled in court (#75200) and sent to a correction facility (#73971). No real performance difference reported (but functions that might benefit a tiny constant bit like `BTreeMap::get_mut` aren't benchmarked): ``` benchcmp old new --threshold 5 name old ns/iter new ns/iter diff ns/iter diff % speedup btree::map::clone_fat_100 63,073 59,256 -3,817 -6.05% x 1.06 btree::map::iter_100 3,514 3,235 -279 -7.94% x 1.09 ```
2020-08-14BTreeMap: refactor splitpoint and move testing over to unit testStein Somers-31/+11
2020-08-14Auto merge of #74777 - ssomers:btree_cleanup_7, r=Mark-Simulacrumbors-20/+16
Stop BTreeMap casts from reborrowing Down in btree/node.rs, the interface and use of `cast_unchecked` look a bit shady. It's really just there for inverting `forget_type` which does not borrow. By borrowing we can't write the same `cast_unchecked` in the same way at the Handle level. No change in undefined behaviour or performance.
2020-08-13Stop BTreeMap casts from reborrowingStein Somers-20/+16
2020-08-12Somewhat complicated way to respect BTreeMap's node length invariantStein Somers-16/+65
2020-08-11BTreeMap: purge innocent use of into_kv_mutStein Somers-6/+16
2020-08-09BTreeMap: better distinguish the root holder from the root nodeStein Somers-9/+11
2020-08-07BTreeMap: better way to postpone root access in DrainFilterStein Somers-2/+2
2020-08-04Auto merge of #75058 - ssomers:btree_cleanup_insert_2, r=Mark-Simulacrumbors-44/+42
Clarify reuse of a BTreeMap insert support function and treat split support likewise r? @Mark-Simulacrum
2020-08-02Separate off a leafy insert function instead of lying, and split split similarlyStein Somers-44/+42
2020-08-02Move bulk of BTreeMap::insert method down to new method on handleStein Somers-5/+61
2020-08-03Rollup merge of #74874 - ssomers:btree_cleanup_8, r=Mark-SimulacrumYuki Okushi-6/+14
BTreeMap: define forget_type only when relevant Similar to `forget_node_type` for handles. No effect on generated code, apart maybe from the superfluous calls that might not have been optimized away. r? @Mark-Simulacrum
2020-08-03Rollup merge of #74762 - ssomers:btree_no_root_in_remove_kv_tracking, ↵Yuki Okushi-7/+9
r=Mark-Simulacrum BTreeMap::drain_filter should not touch the root during iteration Although Miri doesn't point it out, I believe there is undefined behaviour using `drain_filter` when draining the 11th-last element from a tree that was larger. When this happens, the last remaining child nodes are merged, the root becomes empty and is popped from the tree. That last step establishes a mutable reference to the node elected root and writes a pointer in `node::Root`, while iteration continues to visit the same node. This is mostly code from #74437, slightly adapted.
2020-08-01BTreeMap::drain_filter no longer touches the root during iterationStein Somers-7/+9
2020-08-01Define forget_type only when relevantStein Somers-6/+14
2020-07-28Remove into_slices and its unsafe blockStein Somers-10/+3
2020-07-27mv std libs to library/mark-0/+1488
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-07-06 22:18:03 +0000