about summary refs log tree commit diff
path: root/library/alloc/src/collections/btree
AgeCommit message (Collapse)AuthorLines
2020-12-17Rollup merge of #80006 - ssomers:btree_cleanup_6, r=Mark-SimulacrumGuillaume Gomez-28/+27
BTreeMap: more expressive local variables in merge r? ```````@Mark-Simulacrum```````
2020-12-14BTreeSet: simplify implementation of pop_first/pop_lastStein Somers-2/+2
2020-12-13Auto merge of #80005 - ssomers:btree_cleanup_3, r=Mark-Simulacrumbors-10/+11
BTreeMap: declare clear_parent_link directly on the root it needs r? `@Mark-Simulacrum`
2020-12-13Auto merge of #79987 - ssomers:btree_cleanup_4, r=Mark-Simulacrumbors-0/+2
BTreeMap: detect bulk_steal's count-1 underflow in release builds too r? `@Mark-Simulacrum`
2020-12-13Auto merge of #79376 - ssomers:btree_choose_parent_kv, r=Mark-Simulacrumbors-12/+14
BTreeMap: clarify comments and panics around choose_parent_kv Fixes a lie in recent code: `unreachable!("empty non-root node")` should shout "empty internal node", but it might as well be good and keep quiet r? `@Mark-Simulacrum`
2020-12-13BTreeMap: more expressive local variables in mergeStein Somers-28/+27
2020-12-13BTreeMap: declare clear_parent_link directly on the root it needsStein Somers-10/+11
2020-12-13BTreeMap: capture a recurring use pattern as replace_kvStein Somers-8/+10
2020-12-13BTreeMap: detect bulk_steal's count-1 underflow in release builds tooStein Somers-0/+2
2020-12-12BTreeMap: clarify comments and panics surrounding choose_parent_kvStein Somers-12/+14
2020-12-07Removed spurious linebreak from new documentationChai T. Rex-1/+1
2020-12-07Improved documentation for HashMap/BTreeMap Entry's .or_insert_with_key methodChai T. Rex-3/+6
2020-12-05Auto merge of #78373 - matthewjasper:drop-on-into, r=pnkfelixbors-1/+1
Don't leak return value after panic in drop Closes #47949
2020-12-04Avoid leaking block expression valuesMatthew Jasper-1/+1
2020-12-04 Rename `AllocRef` to `Allocator` and `(de)alloc` to `(de)allocate`Tim Diekmann-5/+5
2020-12-01Update rustc version that or_insert_with_key landedChai T. Rex-1/+1
2020-11-28BTreeMap: try to enhance various comments & local identifiersStein Somers-89/+118
2020-11-24Rollup merge of #79358 - ssomers:btree_public_comments, r=Mark-SimulacrumJonas Schievink-4/+6
BTreeMap/BTreeSet: make public doc more consistent Tweaks #72876 and #73667 and propagate them to `BTreeSet`.
2020-11-24Rollup merge of #79354 - ssomers:btree_bereave_BoxedNode, r=Mark-SimulacrumJonas Schievink-38/+12
BTreeMap: cut out the ceremony around BoxedNode The opposite direction of #79093. r? ``@Mark-Simulacrum``
2020-11-23BTreeMap/BTreeSet: make public doc more consistentStein Somers-4/+6
2020-11-23BTreeMap: cut out the ceremony around BoxedNodeStein Somers-38/+12
2020-11-23doc typooliver-2/+2
plus a small edit for clarity
2020-11-22Rollup merge of #79297 - ssomers:btree_post_redux, r=Mark-SimulacrumMara Bos-14/+14
BTreeMap: swap the names of NodeRef::new and Root::new_leaf #78104 preserved the name of Root::new_leaf to minimize changes, but the resulting names are confusing. r? `@Mark-Simulacrum`
2020-11-22Rollup merge of #79295 - ssomers:btree_fix_78903, r=Mark-SimulacrumMara Bos-16/+15
BTreeMap: fix minor testing mistakes in #78903 Mostly a duplicate test case r? `@Mark-Simulacrum`
2020-11-22Rollup merge of #79267 - ssomers:btree_namespaces, r=Mark-SimulacrumMara Bos-35/+33
BTreeMap: address namespace conflicts Fix an annoyance popping up whenever synchronizing the test cases with a version capable of miri-track-raw-pointers. r? `@Mark-Simulacrum`
2020-11-22BTreeMap: swap the names of NodeRef::new and Root::new_leafStein Somers-14/+14
2020-11-22BTreeMap: fix minor testing mistakes in #78903Stein Somers-16/+15
2020-11-21More consistently use spaces after commas in lists in docsCarol (Nichols || Goulding)-1/+1
2020-11-21BTreeMap: address namespace conflictsStein Somers-35/+33
2020-11-18BTreeMap: reuse NodeRef as Root, keep BoxedNode for edges only, ban UniqueStein Somers-141/+132
2020-11-16Rollup merge of #78903 - ssomers:btree_order_chaos_testing, r=Mark-SimulacrumMara Bos-26/+201
BTreeMap: test chaotic ordering & other bits & bobs r? `@Mark-Simulacrum`
2020-11-16Auto merge of #78631 - ssomers:btree-alias_for_underfull, r=Mark-Simulacrumbors-203/+320
BTreeMap: fix pointer provenance rules in underfullness Continuing on #78480, and for readability, and possibly for performance: avoid aliasing when handling underfull nodes, and consolidate the code doing that. In particular: - Avoid the rather explicit aliasing for internal nodes in `remove_kv_tracking`. - Climb down to the root to handle underfull nodes using a reborrowed handle, rather than one copied with `ptr::read`, before resuming on the leaf level. - Integrate the code tracking leaf edge position into the functions performing changes, rather than bolting it on. r? `@Mark-Simulacrum`
2020-11-13Add BTreeMap::retain and BTreeSet::retainMatt Brubeck-0/+70
2020-11-12BTreeMap: test chaotic ordering & other bits & bobsStein Somers-26/+201
2020-11-12BTreeMap: avoid aliasing while handling underfull nodesStein Somers-203/+320
2020-11-11Rollup merge of #78417 - ssomers:btree_chop_up_2, r=Mark-SimulacrumJonas Schievink-114/+176
BTreeMap: split off most code of append To complete #78056, move the last single-purpose pieces of code out of map.rs into a separate module. Also, tweaked documentation and safeness - I doubt think this code would be safe if the iterators passed in wouldn't be as sorted as the method says they should be - and bounds on MergeIterInner. r? ```@Mark-Simulacrum```
2020-11-09BTreeMap: fix pointer provenance rules, make borrowing explicitStein Somers-247/+327
2020-11-09Rollup merge of #78476 - RalfJung:btree-alias, r=Mark-SimulacrumDylan DPC-4/+8
fix some incorrect aliasing in the BTree This line is wrong: ``` ptr::copy(slice.as_ptr().add(idx), slice.as_mut_ptr().add(idx + 1), slice.len() - idx); ``` When `slice.as_mut_ptr()` is called, that creates a mutable reference to the entire slice, which invalidates the raw pointer previously returned by `slice.as_ptr()`. (Miri currently misses this because raw pointers are not tracked properly.) Cc ````````@ssomers````````
2020-11-09Rollup merge of #78437 - ssomers:btree_no_ord_at_node_level, r=Mark-SimulacrumDylan DPC-41/+22
BTreeMap: stop mistaking node for an orderly place A second mistake in #77612 was to ignore the node module's rightful comment "this module doesn't care whether the entries are sorted". And there's a much simpler way to visit the keys in order, if you check this separately from a single pass checking everything. r? ````````@Mark-Simulacrum````````
2020-11-08BTreeMap: split off most code of append, slightly improve interfacesStein Somers-114/+176
2020-11-07Rollup merge of #78538 - ssomers:btree_testing_rng, r=Mark-SimulacrumYuki Okushi-0/+3
BTreeMap: document a curious assumption in test cases r? ```@Mark-Simulacrum```
2020-10-30Constantify more BTreeMap and BTreeSet functionsBenoît du Garreau-4/+22
- BTreeMap::len - BTreeMap::is_empty - BTreeSet::len - BTreeSet::is_empty
2020-10-29BTreeMap: document a curious assumption in test casesStein Somers-0/+3
2020-10-28fix some incorrect aliasing in the BTreeRalf Jung-4/+8
2020-10-27BTreeMap: stop mistaking node for an orderly placeStein Somers-41/+22
2020-10-27Auto merge of #78359 - ssomers:btree_cleanup_mem, r=Mark-Simulacrumbors-40/+42
BTreeMap: move generic support functions out of navigate.rs A preparatory step chipped off #78104, useful in general (if at all). r? `@Mark-Simulacrum`
2020-10-26Auto merge of #77187 - TimDiekmann:box-alloc, r=Amanieubors-1/+1
Support custom allocators in `Box` r? `@Amanieu` This pull request requires a crater run. ### Prior work: - #71873 - #58457 - [`alloc-wg`](https://github.com/TimDiekmann/alloc-wg)-crate Currently blocked on: - ~#77118~ - ~https://github.com/rust-lang/chalk/issues/615 (#77515)~
2020-10-26BTreeMap: move generic functions out of navigate.rsStein Somers-40/+42
2020-10-25Auto merge of #78015 - ssomers:btree_merge_mergers, r=Mark-Simulacrumbors-97/+111
btree: merge the implementations of MergeIter Also remove the gratuitous Copy bounds. Same benchmark performance. r? `@Mark-Simulacrum`
2020-10-25Merge remote-tracking branch 'upstream/master' into box-allocTim Diekmann-822/+873
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-07-10 21:29:25 +0000