about summary refs log tree commit diff
path: root/src/libstd/collections
AgeCommit message (Collapse)AuthorLines
2016-11-05Auto merge of #37470 - arthurprs:sip-smaller, r=alexcrichtonbors-14/+12
Don't reuse RandomState seeds cc #36481
2016-11-02Rollup merge of #37498 - sanxiyn:unused-type-alias, r=eddybJonathan Turner-4/+0
Remove unused type aliases Found by extending the dead code lint. The lint itself is work in progress because of false positives. cc #37455.
2016-10-31Auto merge of #36595 - bluss:hashmap-usize-for-hash, r=alexcrichtonbors-25/+44
hashmap: Store hashes as usize internally We can't use more than usize's bits of a hash to select a bucket anyway, so we only need to store that part in the table. This should be an improvement for the size of the data structure on 32-bit platforms. Smaller data means better cache utilization and hopefully better performance. Fixes #36567
2016-10-31Don't reuse RandomState seedsarthurprs-14/+12
2016-10-31Remove unused type aliasesSeo Sanghyeon-4/+0
2016-10-20Add missing urls in collections moduleGuillaume Gomez-55/+65
2016-10-17std::collections: Reexport libcollections's range moduleUlrik Sverdrup-0/+3
This is overdue, even if range and RangeArgument is still unstable. The stability attributes are the same ones as the other unstable item (Bound) here, they don't seem to matter.
2016-10-17hashmap: Store hashes as usize internallyUlrik Sverdrup-25/+44
We can't use more than usize's bits of a hash to select a bucket anyway, so we only need to store that part in the table. This should be an improvement for the size of the data structure on 32-bit platforms. Smaller data means better cache utilization and hopefully better performance.
2016-10-12Cache conscious hashmap tablearthurprs-88/+68
2016-10-06Auto merge of #36753 - srinivasreddy:hash, r=nrcbors-279/+438
run rustfmt on libstd/collections/hash folder
2016-10-04Rollup merge of #36902 - ollie27:stab_impls, r=alexcrichtonManish Goregaokar-3/+3
std: Correct stability attributes for some implementations These are displayed by rustdoc so should be correct.
2016-10-03Auto merge of #36815 - alexcrichton:stabilize-1.13, r=aturonbors-2/+26
std: Stabilize and deprecate APIs for 1.13 This commit is intended to be backported to the 1.13 branch, and works with the following APIs: Stabilized * `i32::checked_abs` * `i32::wrapping_abs` * `i32::overflowing_abs` * `RefCell::try_borrow` * `RefCell::try_borrow_mut` Deprecated * `BinaryHeap::push_pop` * `BinaryHeap::replace` * `SipHash13` * `SipHash24` * `SipHasher` - use `DefaultHasher` instead in the `std::collections::hash_map` module Closes #28147 Closes #34767 Closes #35057 Closes #35070
2016-10-03std: Stabilize and deprecate APIs for 1.13Alex Crichton-2/+26
This commit is intended to be backported to the 1.13 branch, and works with the following APIs: Stabilized * `i32::checked_abs` * `i32::wrapping_abs` * `i32::overflowing_abs` * `RefCell::try_borrow` * `RefCell::try_borrow_mut` * `DefaultHasher` * `DefaultHasher::new` * `DefaultHasher::default` Deprecated * `BinaryHeap::push_pop` * `BinaryHeap::replace` * `SipHash13` * `SipHash24` * `SipHasher` - use `DefaultHasher` instead in the `std::collections::hash_map` module Closes #28147 Closes #34767 Closes #35057 Closes #35070
2016-10-03Auto merge of #36766 - nnethercote:hash-span-capacity, r=blussbors-90/+122
Clarify HashMap's capacity handling. HashMap has two notions of "capacity": - "Usable capacity": the number of elements a hash map can hold without resizing. This is the meaning of "capacity" used in HashMap's API, e.g. the `with_capacity()` function. - "Internal capacity": the number of allocated slots. Except for the zero case, it is always larger than the usable capacity (because some slots must be left empty) and is always a power of two. HashMap's code is confusing because it does a poor job of distinguishing these two meanings. I propose using two different terms for these two concepts. Because "capacity" is already used in HashMap's API to mean "usable capacity", I will use a different word for "internal capacity". I propose "span", though I'm happy to consider other names.
2016-10-03Avoid overflow check in `HashMap::reserve`'s fast path.Nicholas Nethercote-2/+3
2016-10-01std: Correct stability attributes for some implementationsOliver Middleton-3/+3
These are displayed by rustdoc so should be correct.
2016-09-29Auto merge of #36557 - sfackler:fix-hashdos-docs, r=alexcrichtonbors-8/+22
Clean up hasher discussion on HashMap * We never want to make guarantees about protecting against attacks. * "True randomness" is not the right terminology to be using in this context. * There is significantly more nuance to the performance of SipHash than "somewhat slow". r? @steveklabnik Follow up to discussion on #35371
2016-09-29Mention FNVSteven Fackler-1/+1
2016-09-29Clarify HashMap's capacity handling.Nicholas Nethercote-90/+121
This commit does the following. - Changes the terminology for capacities used within HashMap's code. "Internal capacity" is now consistently "raw capacity", and "usable capacity" is now consistently just "capacity". This makes the code easier to understand. - Reworks capacity and raw capacity computations. Raw capacity computations are now handled in a single place: `DefaultResizePolicy::raw_capacity()`. This function correctly returns zero when given zero, which means that the following cases now result in a capacity of zero when they previously did not. * `Hash{Map,Set}::with_capacity(0)` * `Hash{Map,Set}::with_capacity_and_hasher(0)` * `Hash{Map,Set}::shrink_to_fit()`, when used with a hash map/set whose elements have all been removed - Strengthens the language used in the comments describing the above functions, to make it clearer when they will result in a map/set with a capacity of zero. The new language is based on the language used for the corresponding functions in `Vec`. - Adds tests for the above zero-capacity cases. - Removes `test_resize_policy` because it is no longer useful.
2016-09-28Rollup merge of #36811 - brson:bootstrap, r=alexcrichtonJonathan Turner-1/+0
Update bootstrap compiler
2016-09-28Remove stage0 hacksBrian Anderson-1/+0
2016-09-28Rollup merge of #36740 - frehberg:apidoc, r=steveklabnikJonathan Turner-0/+30
Document init of HashSet/HashMap from vector
2016-09-27Update set.rsFrank Rehberger-0/+2
2016-09-27Update map.rsFrank Rehberger-4/+6
2016-09-27run rustfmt on libstd/collections/hash folderSrinivas Reddy Thatiparthy-279/+438
2016-09-26Update set.rsFrank Rehberger-1/+1
2016-09-26Update map.rsFrank Rehberger-1/+1
2016-09-26Update set.rsFrank Rehberger-4/+2
2016-09-26Update map.rsFrank Rehberger-5/+2
2016-09-26Document init of HashSet/HashMap from vectorFrank Rehberger-0/+31
2016-09-26Don't allocate during default HashSet creation.Nicholas Nethercote-8/+34
The following `HashMap` creation functions don't allocate heap storage for elements. ``` HashMap::new() HashMap::default() HashMap::with_hasher() ``` This is good, because it's surprisingly common to create a HashMap and never use it. So that case should be cheap. However, `HashSet` does not have the same behaviour. The corresponding creation functions *do* allocate heap storage for the default number of non-zero elements (which is 32 slots for 29 elements). ``` HashMap::new() HashMap::default() HashMap::with_hasher() ``` This commit gives `HashSet` the same behaviour as `HashMap`, by simply calling the corresponding `HashMap` functions (something `HashSet` already does for `with_capacity` and `with_capacity_and_hasher`). It also reformats one existing `HashSet` construction to use a consistent single-line format. This speeds up rustc itself by 1.01--1.04x on most of the non-tiny rustc-benchmarks.
2016-09-17Clean up hasher discussion on HashMapSteven Fackler-8/+22
* We never want to make guarantees about protecting against attacks. * "True randomness" is not the right terminology to be using in this context. * There is significantly more nuance to the performance of SipHash than "somewhat slow".
2016-09-11Documentation for default types modifiedathulappadan-2/+2
2016-09-11Documentation of what does for each typeathulappadan-0/+3
2016-09-06Add missing urlsggomez-18/+42
2016-08-25Auto merge of #35906 - jseyfried:local_prelude, r=eddybbors-4/+0
Use `#[prelude_import]` in `libcore` and `libstd` r? @eddyb
2016-08-24Use `#[prelude_import]` in `libstd`.Jeffrey Seyfried-4/+0
2016-08-24Remove drop flags from structs and enums implementing Drop.Eduard Burtescu-2/+2
2016-08-23Auto merge of #35656 - Stebalien:fused, r=alexcrichtonbors-2/+43
Implement 1581 (FusedIterator) * [ ] Implement on patterns. See https://github.com/rust-lang/rust/issues/27721#issuecomment-239638642. * [ ] Handle OS Iterators. A bunch of iterators (`Args`, `Env`, etc.) in libstd wrap platform specific iterators. The current ones all appear to be well-behaved but can we assume that future ones will be? * [ ] Does someone want to audit this? On first glance, all of the iterators on which I implemented `FusedIterator` appear to be well-behaved but there are a *lot* of them so a second pair of eyes would be nice. * I haven't touched rustc internal iterators (or the internal rand) because rustc doesn't actually call `fuse()`. * `FusedIterator` can't be implemented on `std::io::{Bytes, Chars}`. Closes: #35602 (Tracking Issue) Implements: rust-lang/rfcs#1581
2016-08-19std: Stabilize APIs for the 1.12 releaseAlex Crichton-8/+11
Stabilized * `Cell::as_ptr` * `RefCell::as_ptr` * `IpAddr::is_{unspecified,loopback,multicast}` * `Ipv6Addr::octets` * `LinkedList::contains` * `VecDeque::contains` * `ExitStatusExt::from_raw` - both on Unix and Windows * `Receiver::recv_timeout` * `RecvTimeoutError` * `BinaryHeap::peek_mut` * `PeekMut` * `iter::Product` * `iter::Sum` * `OccupiedEntry::remove_entry` * `VacantEntry::into_key` Deprecated * `Cell::as_unsafe_cell` * `RefCell::as_unsafe_cell` * `OccupiedEntry::remove_pair` Closes #27708 cc #27709 Closes #32313 Closes #32630 Closes #32713 Closes #34029 Closes #34392 Closes #34285 Closes #34529
2016-08-18Add a FusedIterator trait.Steven Allen-2/+43
This trait can be used to avoid the overhead of a fuse wrapper when an iterator is already well-behaved. Conforming to: RFC 1581 Closes: #35602
2016-08-16Auto merge of #35354 - tomgarcia:covariant-drain, r=alexcrichtonbors-6/+13
Made vec_deque::Drain, hash_map::Drain, and hash_set::Drain covariant Fixed the rest of the Drain iterators.
2016-08-05Update HashMap docs regarding DoS protectionMichael Gattozzi-7/+6
Because of changes to how Rust acquires randomness HashMap is not guaranteed to be DoS resistant. This commit reflects these changes in the docs themselves and provides an alternative method to creating a hash that is resistant if needed.
2016-08-04Made vec_deque::Drain, hash_map::Drain, and hash_set::Drain covariantThomas Garcia-6/+13
2016-07-26Rollup merge of #35001 - rdwilliamson:patch-1, r=alexcrichtonSteve Klabnik-1/+1
Fix HashMap's values_mut example to use println! Fix HashMap's values_mut example to use println!
2016-07-26Rollup merge of #34935 - GuillaumeGomez:hash_map_doc, r=steveklabnikSteve Klabnik-5/+198
Add HashMap Entry enums examples Part of #29348. r? @steveklabnik
2016-07-24Rollup merge of #34975 - GuillaumeGomez:random_state_doc, r=steveklabnikManish Goregaokar-0/+19
Add Random state doc Last part of #29348. r? @steveklabnik
2016-07-23Fix HashMap's values_mut example to use println!Robert Williamson-1/+1
2016-07-22Add Random state docggomez-0/+19
2016-07-22Add HashMap Entry enums examplesggomez-5/+198
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-28 17:02:56 +0000