summary refs log tree commit diff
path: root/src/libstd/collections/hash/table.rs
AgeCommit message (Collapse)AuthorLines
2017-05-20migrate everything to using mem::needs_dropAlexis Beingessner-2/+1
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-04Simplify HashMap Bucket interfacearthurprs-173/+151
* 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-17Stabilize rc_raw feature, closes #37197Aaron Turon-1/+1
2017-03-11Implement placement-in protocol for `HashMap`Charlie Fan-0/+27
2017-03-03Reduce size overhead of adaptative hashmaparthurprs-8/+66
Exposes a boolean flag in RawTable and use it instead of a bool field in HashMap. Fixes: #40042
2017-02-08std: Add retain method for HashMap and HashSetf001-7/+74
Fix #36648
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-0/+29
Part of https://github.com/rust-lang/rust/issues/31869. Also turn on the `missing_debug_implementations` lint at the crate level.
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-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-16/+12
run rustfmt on libstd/collections/hash folder
2016-09-28Remove stage0 hacksBrian Anderson-1/+0
2016-09-27run rustfmt on libstd/collections/hash folderSrinivas Reddy Thatiparthy-16/+12
2016-08-24Remove drop flags from structs and enums implementing Drop.Eduard Burtescu-2/+2
2016-08-04Made vec_deque::Drain, hash_map::Drain, and hash_set::Drain covariantThomas Garcia-6/+10
2016-06-11run rustfmt on libstd/collections/hash folderSrinivas Reddy Thatiparthy-167/+178
2016-03-30Make HashMap's RawBucket covariantJonathan S-18/+23
2016-03-22f clarification, docsPiotr Czarnecki-2/+5
2016-03-22f Put and DerefMutPiotr Czarnecki-14/+26
2016-03-21f dead codePiotr Czarnecki-10/+0
2016-03-05Use consistent syntaxPiotr Czarnecki-3/+3
2016-03-05Refactor fn robin_hoodPiotr Czarnecki-13/+39
2016-03-05Refactor fn Bucket::nextPiotr Czarnecki-15/+7
2016-03-05Add `InternalEntry` for use in all searches.Piotr Czarnecki-8/+10
2016-03-05Rename 'distance' -> 'displacement'Piotr Czarnecki-1/+1
2016-02-16Avoid iteration when dropping `HashMap`s whose items don't need droppingAndrew Paseltiner-1/+4
This changes the performance of `drop` from linear to constant time for such `HashMap`s. Closes #31711.
2016-01-26std: Stabilize custom hasher support in HashMapAlex Crichton-4/+3
This commit implements the stabilization of the custom hasher support intended for 1.7 but left out due to some last-minute questions that needed some decisions. A summary of the actions done in this PR are: Stable * `std::hash::BuildHasher` * `BuildHasher::Hasher` * `BuildHasher::build_hasher` * `std::hash::BuildHasherDefault` * `HashMap::with_hasher` * `HashMap::with_capacity_and_hasher` * `HashSet::with_hasher` * `HashSet::with_capacity_and_hasher` * `std::collections::hash_map::RandomState` * `RandomState::new` Deprecated * `std::collections::hash_state` * `std::collections::hash_state::HashState` - this trait was also moved into `std::hash` with a reexport here to ensure that we can have a blanket impl to prevent immediate breakage on nightly. Note that this is unstable in both location. * `HashMap::with_hash_state` - renamed * `HashMap::with_capacity_and_hash_state` - renamed * `HashSet::with_hash_state` - renamed * `HashSet::with_capacity_and_hash_state` - renamed Closes #27713
2016-01-16std: Stabilize APIs for the 1.7 releaseAlex Crichton-1/+0
This commit stabilizes and deprecates the FCP (final comment period) APIs for the upcoming 1.7 beta release. The specific APIs which changed were: Stabilized * `Path::strip_prefix` (renamed from `relative_from`) * `path::StripPrefixError` (new error type returned from `strip_prefix`) * `Ipv4Addr::is_loopback` * `Ipv4Addr::is_private` * `Ipv4Addr::is_link_local` * `Ipv4Addr::is_multicast` * `Ipv4Addr::is_broadcast` * `Ipv4Addr::is_documentation` * `Ipv6Addr::is_unspecified` * `Ipv6Addr::is_loopback` * `Ipv6Addr::is_unique_local` * `Ipv6Addr::is_multicast` * `Vec::as_slice` * `Vec::as_mut_slice` * `String::as_str` * `String::as_mut_str` * `<[T]>::clone_from_slice` - the `usize` return value is removed * `<[T]>::sort_by_key` * `i32::checked_rem` (and other signed types) * `i32::checked_neg` (and other signed types) * `i32::checked_shl` (and other signed types) * `i32::checked_shr` (and other signed types) * `i32::saturating_mul` (and other signed types) * `i32::overflowing_add` (and other signed types) * `i32::overflowing_sub` (and other signed types) * `i32::overflowing_mul` (and other signed types) * `i32::overflowing_div` (and other signed types) * `i32::overflowing_rem` (and other signed types) * `i32::overflowing_neg` (and other signed types) * `i32::overflowing_shl` (and other signed types) * `i32::overflowing_shr` (and other signed types) * `u32::checked_rem` (and other unsigned types) * `u32::checked_neg` (and other unsigned types) * `u32::checked_shl` (and other unsigned types) * `u32::saturating_mul` (and other unsigned types) * `u32::overflowing_add` (and other unsigned types) * `u32::overflowing_sub` (and other unsigned types) * `u32::overflowing_mul` (and other unsigned types) * `u32::overflowing_div` (and other unsigned types) * `u32::overflowing_rem` (and other unsigned types) * `u32::overflowing_neg` (and other unsigned types) * `u32::overflowing_shl` (and other unsigned types) * `u32::overflowing_shr` (and other unsigned types) * `ffi::IntoStringError` * `CString::into_string` * `CString::into_bytes` * `CString::into_bytes_with_nul` * `From<CString> for Vec<u8>` * `From<CString> for Vec<u8>` * `IntoStringError::into_cstring` * `IntoStringError::utf8_error` * `Error for IntoStringError` Deprecated * `Path::relative_from` - renamed to `strip_prefix` * `Path::prefix` - use `components().next()` instead * `os::unix::fs` constants - moved to the `libc` crate * `fmt::{radix, Radix, RadixFmt}` - not used enough to stabilize * `IntoCow` - conflicts with `Into` and may come back later * `i32::{BITS, BYTES}` (and other integers) - not pulling their weight * `DebugTuple::formatter` - will be removed * `sync::Semaphore` - not used enough and confused with system semaphores Closes #23284 cc #27709 (still lots more methods though) Closes #27712 Closes #27722 Closes #27728 Closes #27735 Closes #27729 Closes #27755 Closes #27782 Closes #27798
2015-12-18Fix the falloutVadim Petrochenkov-1/+1
2015-10-06Add RFC 1238's `unsafe_destructor_blind_to_params` (UGEH) where needed.Felix S. Klock II-0/+1
I needed it in `RawVec`, `Vec`, and `TypedArena` for `rustc` to bootstrap; but of course that alone was not sufficient for `make check`. Later I added `unsafe_destructor_blind_to_params` to collections, in particular `LinkedList` and `RawTable` (the backing representation for `HashMap` and `HashSet`), to get the regression tests exercising cyclic structure from PR #27185 building. ---- Note that the feature is `dropck_parametricity` (which is not the same as the attribute's name). We will almost certainly vary our strategy here in the future, so it makes some sense to have a not-as-ugly name for the feature gate. (The attribute name was deliberately selected to be ugly looking.)
2015-09-29Remove redundant uses of Iterator::by_ref()Ulrik Sverdrup-1/+1
2015-09-11std: Internalize almost all of `std::rt`Alex Crichton-8/+5
This commit does some refactoring to make almost all of the `std::rt` private. Specifically, the following items are no longer part of its API: * DEFAULT_ERROR_CODE * backtrace * unwind * args * at_exit * cleanup * heap (this is just alloc::heap) * min_stack * util The module is now tagged as `#[doc(hidden)]` as the only purpose it's serve is an entry point for the `panic!` macro via the `begin_unwind` and `begin_unwind_fmt` reexports.
2015-08-14Auto merge of #27822 - arielb1:inline-round-take-2, r=Gankrobors-0/+1
This speeds up rustc on #25916 from 1.36±0.022s to 1.326±0.025s Tests pass locally (even on 32-bit :-) r? @Gankro
2015-08-13Mark round_up_to_next as inline arielb1-0/+1
This speeds up rustc on #25916 from 1.36±0.022s to 1.326±0.025s Tests pass locally (even on 32-bit :-)
2015-08-11Add HashSet and HashMap testsGuillaume Gomez-3/+14
2015-08-10Add Send/Sync traits on Iter struct in hash/tableGuillaume Gomez-0/+3
2015-06-24Make `align_of` behave like `min_align_of`.Huon Wilson-11/+11
This removes a footgun, since it is a reasonable assumption to make that pointers to `T` will be aligned to `align_of::<T>()`. This also matches the behaviour of C/C++. `min_align_of` is now deprecated. Closes #21611.
2015-05-31Inline hash_table::calculate_offsets, used by iterators.Eduard Burtescu-0/+1
The `HashMap` and `HashSet` iterators use `RawTable::first_bucket_raw` which is generic and will get inlined cross-crate. However, `first_bucket_raw` calls `calculate_offsets` and the call doesn't get inlined, despite being a simple function. This missing `#[inline]` results in `hash_table::calculate_offsets` showing up at the top of a callgrind profile with 3 million calls (for the testcase in #25916).
2015-04-28Register new snapshotsTamir Duberstein-2/+0
2015-04-21std: Remove deprecated/unstable num functionalityAlex Crichton-1/+1
This commit removes all the old casting/generic traits from `std::num` that are no longer in use by the standard library. This additionally removes the old `strconv` module which has not seen much use in quite a long time. All generic functionality has been supplanted with traits in the `num` crate and the `strconv` module is supplanted with the [rust-strconv crate][rust-strconv]. [rust-strconv]: https://github.com/lifthrasiir/rust-strconv This is a breaking change due to the removal of these deprecated crates, and the alternative crates are listed above. [breaking-change]
2015-04-21Model lexer: Fix remaining issuesPiotr Czarnecki-2/+0
2015-04-01Fallout in public-facing and semi-public-facing libsNiko Matsakis-1/+7
2015-03-31std: Clean out #[deprecated] APIsAlex Crichton-1/+1
This commit cleans out a large amount of deprecated APIs from the standard library and some of the facade crates as well, updating all users in the compiler and in tests as it goes along.
2015-03-30std: Standardize (input, output) param orderingsAlex Crichton-2/+2
This functions swaps the order of arguments to a few functions that previously took (output, input) parameters, but now take (input, output) parameters (in that order). The affected functions are: * ptr::copy * ptr::copy_nonoverlapping * slice::bytes::copy_memory * intrinsics::copy * intrinsics::copy_nonoverlapping Closes #22890 [breaking-change]
2015-03-28Remove IteratorExtSteven Fackler-1/+1
All methods are inlined into Iterator with `Self: Sized` bounds to make sure Iterator is still object safe. [breaking-change]
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-07-07 11:30:18 +0000