about summary refs log tree commit diff
path: root/src/libstd/collections/hash
AgeCommit message (Collapse)AuthorLines
2017-05-04Deprecate heap::EMPTY in favour of Unique::empty or otherwise.Alexis Beingessner-1/+2
2017-05-04fallout from NonZero/Unique/Shared changesAlexis Beingessner-9/+12
2017-04-23Auto merge of #41437 - cuviper:remove-unstable-deprecated, r=alexcrichtonbors-7/+0
Remove items that are unstable and deprecated This removes unstable items that have been deprecated for more than one cycle. - Since 1.16.0, `#![feature(enumset)]` - All of `mod collections::enum_set` - Since 1.15.0, `#![feature(borrow_state)]` - `cell::BorrowState` - `RefCell::borrow_state()` - Since 1.15.0, `#![feature(is_unique)]` - `Rc::is_unique()` (made private like `Arc::is_unique()`) - Since 1.15.0, `#![feature(rc_would_unwrap)]` - `Rc::would_wrap()` - Since 1.13.0, `#![feature(binary_heap_extras)]` - `BinaryHeap::push_pop()` - `BinaryHeap::replace()` - Since 1.12.0, `#![feature(as_unsafe_cell)]` - `Cell::as_unsafe_cell()` - `RefCell::as_unsafe_cell()` - Since 1.12.0, `#![feature(map_entry_recover_keys)]` - `btree_map::OccupiedEntry::remove_pair()` - `hash_map::OccupiedEntry::remove_pair()` - Since 1.11.0, `#![feature(float_extras)]` - `Float::nan()` - `Float::infinity()` - `Float::neg_infinity()` - `Float::neg_zero()` - `Float::zero()` - `Float::one()` - `Float::integer_decode()` - `f32::integer_decode()` - `f32::ldexp()` - `f32::frexp()` - `f32::next_after()` - `f64::integer_decode()` - `f64::ldexp()` - `f64::frexp()` - `f64::next_after()` - Since 1.11.0, `#![feature(zero_one)]` - `num::Zero` - `num::One`
2017-04-22Fix invalid linkageGuillaume Gomez-2/+2
2017-04-20Remove OccupiedEntry::remove_pairJosh Stone-7/+0
[unstable, deprecated since 1.12.0]
2017-04-13Various consistency and phrasing fixes in std::collections' docslukaramu-10/+9
* Changed btree_map's and hash_map's Entry (etc.) docs to be consistent * Changed VecDeque's type and module summary sentences to be consistent with each other as well as with other summary sentences in the module * Changed HashMap's and HashSet's summary sentences to be less redundantly phrased and also more consistant with the other summary sentences in the module * Also, added an example to Bound
2017-04-13Various fixes throughout std::collections' docslukaramu-38/+60
* Added links where possible (limited because of facading) * Changed references to methods from `foo()` to `foo` in module docs * Changed references to methods from `HashMap::foo` to just `foo` in top-level docs for `HashMap` and the `default` doc for `DefaultHasher` * Various small other fixes
2017-04-13Update std::collections' docs to use iterator (etc.) boilerplatelukaramu-14/+98
This greatly improves consistency.
2017-04-04Simplify HashMap Bucket interfacearthurprs-191/+165
* Store capacity_mask instead of capacity * Move bucket index into RawBucket * Bucket index is now always within [0..table_capacity) * Clone RawTable using RawBucket * Simplify iterators by moving logic into RawBuckets * Make retain aware of the number of elements
2017-03-22Simplify hash table dropsJosh Stone-47/+18
This replaces the `std::collections::hash::table::RevMoveBuckets` iterator with a simpler `while` loop. This iterator was only used for dropping the remaining elements of a `RawTable`, so instead we can just loop through directly and drop them in place. This should be functionally equivalent to the former code, but a little easier to read. I was hoping it might have some performance benefit too, but it seems the optimizer was already good enough to see through the iterator -- the generated code is nearly the same. Maybe it will still help if an element type has more complicated drop code.
2017-03-19Rollup merge of #40621 - jswalden:dependant-spelling-fix, r=sfacklerCorey Farwell-2/+2
Fix a spelling error in HashMap documentation, and slightly reword surrounding text for precision Noticed while reading docs just now. It's possible that the prior wording *meant* to state that the seed's randomness depends on the exact instant that the system RNG was created, I guess. But unless there's an API guarantee that this is the case, the wording seems over-precise. Is there a formal API guarantee that would forbid, say, the system RNG from generating all output using the Intel RDRAND instruction? I don't think the quality of output in that case would depend on when the RNG was created. Yet it seems to me like it could well be a valid source of randomness when computing the initial seed. For that reason, tying the randomness of the seed, to the quality of the RNG's output *at the precise instant the seed is computed*, seems less confining. That instantaneous quality level could be determined by the quality at the instant the RNG was created -- but instantaneous quality need not be low for that precise reason.
2017-03-17Fix a spelling error in HashMap documentation, and slightly reword it to be ↵Jeff Walden-2/+2
more precise.
2017-03-17Stabilize rc_raw feature, closes #37197Aaron Turon-1/+1
2017-03-11Implement placement-in protocol for `HashMap`Charlie Fan-5/+182
2017-03-03Reduce size overhead of adaptative hashmaparthurprs-24/+74
Exposes a boolean flag in RawTable and use it instead of a bool field in HashMap. Fixes: #40042
2017-02-20Simplify adaptive hashmaparthurprs-23/+11
2017-02-18Fix spelling in commentsarthurprs-5/+5
2017-02-16Resize hashmap when long probes are detectedarthurprs-12/+105
2017-02-15Rollup merge of #39839 - king6cong:refine-doc, r=frewsxcvCorey Farwell-1/+1
make doc consistent with var name
2017-02-15Auto merge of #39560 - F001:retainHashMap, r=alexcrichtonbors-46/+182
std: Add retain method for HashMap and HashSet Fix #36648 r? @bluss
2017-02-15make doc consistent with var nameking6cong-1/+1
2017-02-09Update set operations documentationJethro Beekman-7/+13
Reminding people of set terminology.
2017-02-08std: Add retain method for HashMap and HashSetf001-46/+182
Fix #36648
2017-02-05Rollup merge of #39393 - ollie27:stab_impls, r=alexcrichtonCorey Farwell-15/+15
Fix a few impl stability attributes The versions show up in rustdoc.
2017-02-03Add missing urls in HashMapGuillaume Gomez-5/+12
2017-01-29Fix a few impl stability attributesOliver Middleton-15/+15
The versions show up in rustdoc.
2017-01-13Change `to_owned` to `to_string` in docsStjepan Glavina-2/+2
We should teach conversion from `str` to `String` using `to_string` rather than the legacy `to_owned`.
2016-12-28Replace uses of `#[unsafe_destructor_blind_to_params]` with `#[may_dangle]`Andrew Paseltiner-2/+1
CC #34761
2016-12-18Implement `fmt::Debug` for all structures in libstd.Corey Farwell-2/+187
Part of https://github.com/rust-lang/rust/issues/31869. Also turn on the `missing_debug_implementations` lint at the crate level.
2016-12-07Rollup merge of #38186 - frewsxcv:default, r=GuillaumeGomezGuillaume Gomez-0/+4
Add docs for last undocumented `Default` `impl`. Add doc comment for `Default` `impl` on `DefaultHasher`. Fixes https://github.com/rust-lang/rust/issues/36265.
2016-12-06Add doc comment for `Default` `impl` on `DefaultHasher`.Corey Farwell-0/+4
2016-12-06Auto merge of #38017 - arthurprs:hm-extend, r=blussbors-11/+16
Smarter HashMap/HashSet pre-allocation for extend/from_iter HashMap/HashSet from_iter and extend are making totally different assumptions. A more balanced decision may allocate half the lower hint (rounding up). For "well defined" iterators this effectively limits the worst case to two resizes (the initial reserve + one resize). cc #36579 cc @bluss
2016-12-06Smarter HashMap/HashSet extendarthurprs-11/+16
2016-11-27Use displacement instead of initial bucket in HashMap codearthurprs-18/+21
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-31Don't reuse RandomState seedsarthurprs-14/+12
2016-10-31Remove unused type aliasesSeo Sanghyeon-4/+0
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.
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-25 23:00:00 +0000