about summary refs log tree commit diff
path: root/library/alloc/src/collections
AgeCommit message (Collapse)AuthorLines
2020-11-07Remove useless branches from sift_down_range loopGiacomo Stevanato-6/+6
2020-11-07Remove branches from sift_down_to_bottom loopGiacomo Stevanato-6/+5
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-11-01Rollup merge of #78602 - RalfJung:raw-ptr-aliasing-issues, r=m-ou-seMara Bos-2/+3
fix various aliasing issues in the standard library This fixes various cases where the standard library either used raw pointers after they were already invalidated by using the original reference again, or created raw pointers for one element of a slice and used it to access neighboring elements.
2020-10-31fix aliasing issue in binary_heapRalf Jung-2/+3
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-824/+1012
2020-10-24BTreeMap: stop mistaking node::MIN_LEN as a node level constraintStein Somers-55/+55
2020-10-22BTreeMap/Set: merge the implementations of MergeIterStein Somers-97/+111
2020-10-21Rollup merge of #78056 - ssomers:btree_chop_up_1, r=dtolnayYuki Okushi-222/+239
BTreeMap: split off most code of remove and split_off Putting map.rs on a diet, in addition to #77851. r? @dtolnay
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-20Rollup merge of #77612 - ssomers:btree_cleanup_2, r=Mark-SimulacrumYuki Okushi-79/+115
BTreeMap: test invariants more thoroughly and more readably r? @Mark-Simulacrum
2020-10-19BTreeMap: test invariants more thoroughly and more readablyStein Somers-79/+115
2020-10-18Stabilize or_insert_with_keyChai T. Rex-2/+1
2020-10-18Auto merge of #76885 - dylni:move-slice-check-range-to-range-bounds, r=KodrAusbors-1/+1
Move `slice::check_range` to `RangeBounds` Since this method doesn't take a slice anymore (#76662), it makes more sense to define it on `RangeBounds`. Questions: - Should the new method be `assert_len` or `assert_length`?
2020-10-18BTreeMap: split off most code of remove and split_offStein Somers-222/+239
2020-10-18Rollup merge of #77851 - exrook:split-btreemap, r=dtolnayYuki Okushi-468/+480
BTreeMap: refactor Entry out of map.rs into its own file btree/map.rs is approaching the 3000 line mark, splitting out the entry code buys about 500 lines of headroom. I've created this PR because the changes I've made in #77438 will push `map.rs` over the 3000 line limit and cause tidy to complain. I picked `Entry` to factor out because it feels less tightly coupled to the rest of `BTreeMap` than the various iterator implementations. Related: #60302
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-17Rollup merge of #77751 - vojtechkral:vecdeque-binary-search, r=scottmcm,dtolnayDylan DPC-1/+138
liballoc: VecDeque: Add binary search functions I am submitting rust-lang/rfcs#2997 as a PR as suggested by @scottmcm I haven't yet created a tracking issue - if there's a favorable feedback I'll create one and update the issue links in the unstable attribs.
2020-10-16liballoc: VecDeque: Simplify binary_search_by()Vojtech Kral-15/+4
2020-10-16liballoc: VecDeque: Add tracking issue for binary search fnsVojtech Kral-3/+3
2020-10-16Merge branch 'master' into box-allocTim Diekmann-31/+94
2020-10-14BTreeMap: making PartialCmp/PartialEq explicit and testedStein Somers-7/+62
2020-10-14BTreeMap: improve gdb introspection of BTreeMap with ZST keys or valuesStein Somers-1/+0
2020-10-14Rollup merge of #77569 - ssomers:btree_cleanup_1, r=Mark-SimulacrumYuki Okushi-24/+28
BTreeMap: type-specific variants of node_as_mut and cast_unchecked Improves debug checking and shortens some expressions. Extracted from #77408
2020-10-12BTreeMap: refactor Entry out of map.rs into its own fileJacob Hughes-468/+480
btree/map.rs is approaching the 3000 line mark, splitting out the entry code buys about 500 lines of headroom
2020-10-09liballoc: VecDeque: Add binary search functionsVojtech Kral-1/+149
2020-10-08Rollup merge of #77449 - ssomers:btree_drain_filter_size_hint, r=Mark-SimulacrumJonas Schievink-0/+4
BTreeMap: comment why drain_filter's size_hint is somewhat pessimistic The `size_hint` of the `DrainFilter` iterator doesn't adjust as you iterate. This hardly seems important to me, but there has been a comparable PR #64383 in the past. I guess a scenario is that you first iterate half the map manually and keep most of the key/value pairs in the map, and then tell the predicate to drain most of the key/value pairs and `.collect` the iterator over the remaining half of the map. I am totally ambivalent whether this is better or not. r? @Mark-Simulacrum
2020-10-08Rename LayoutErr to LayoutError outside of coreJacob Hughes-3/+3
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-06avoid unnecessary intermediate reference and improve safety commentsRalf Jung-6/+11
2020-10-05BTreeMap: derive type-specific variants of node_as_mut and cast_uncheckedStein Somers-24/+28
2020-10-05make IterMut Send/Sync againRalf Jung-0/+7
2020-10-05VecDeque: avoid more aliasing issues by working with raw pointers instead of ↵Ralf Jung-12/+31
references
2020-10-05VecDeque: fix incorrect &mut aliasing in IterMut::next/next_backRalf Jung-7/+24
2020-10-05Rollup merge of #77514 - scottmcm:less-once-chain-once, r=estebankDylan DPC-2/+3
Replace some once(x).chain(once(y)) with [x, y] IntoIter Now that we have by-value array iterators that are [already used](https://github.com/rust-lang/rust/blob/25c8c53dd994acb3f4f7c02fe6bb46076393f8b0/compiler/rustc_hir/src/def.rs#L305-L307)... For example, ```diff - once(self.type_ns).chain(once(self.value_ns)).chain(once(self.macro_ns)).filter_map(|it| it) + IntoIter::new([self.type_ns, self.value_ns, self.macro_ns]).filter_map(|it| it) ```
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-04Rollup merge of #77445 - ssomers:btree_cleanup_7, r=Mark-SimulacrumJonas Schievink-27/+118
BTreeMap: complete the compile-time test_variance test case Some of the items added to the new `test_sync` belonged in the old `test_variance` as well. And fixed inconsistent paths to nearby modules. r? @Mark-Simulacrum
2020-10-04Rollup merge of #77447 - ssomers:btree_cleanup_8, r=Mark-SimulacrumYuki Okushi-2/+6
BTreeMap: document DrainFilterInner better r? @Mark-Simulacrum
2020-10-03Replace some once(x).chain(once(y)) with [x, y] IntoIterScott McMurray-2/+3
Now that we have by-value array iterators...
2020-10-04BTreeMap/Set: complete the compile-time test casesStein Somers-27/+118
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-27 21:35:39 +0000