summary refs log tree commit diff
path: root/src/libstd/collections/hash/table.rs
AgeCommit message (Collapse)AuthorLines
2018-04-02Use Alloc and Layout from core::heap.Mike Hommey-1/+2
94d1970bba87f2d2893f6e934e4c3f02ed50604d moved the alloc::allocator module to core::heap, moving e.g. Alloc and Layout out of the alloc crate. While alloc::heap reexports them, it's better to use them from where they really come from.
2018-03-14implementing fallible allocation API (try_reserve) for Vec, String and HashMapsnf-16/+41
2018-01-20Rename std::ptr::Shared to NonNullSimon Sapin-3/+3
`Shared` is now a deprecated `type` alias. CC https://github.com/rust-lang/rust/issues/27730#issuecomment-352800629
2017-12-13Remove Sync and Send implementation for RawTableKonrad Borowski-3/+0
The implementation was introduced when changing hash storage from Unique to *mut, but it was changed back to Unique.
2017-10-14std: Set probe length tag on cloned hashmapsManish Goregaokar-0/+1
This isn't strictly necessary for hashmap cloning to work. The tag is used to hint for an upcoming resize, so it's good to copy this information over. (We can do cleverer things like actually resizing the hashmap when we see the tag, or even cleaning up the entry order, but this requires more thought and might not be worth it)
2017-10-14std: Get rid of hash_offet in RawTableManish Goregaokar-16/+15
This offset is always zero, and we don't consistently take it into account. This is okay, because it's zero, but if it ever changes we're going to have bugs (e.g. in the `dealloc` call, where we don't take it into account). It's better to remove this for now; if we ever have a need for a nonzero offset we can add it back, and handle it properly when we do so.
2017-09-30address some `FIXME`s whose associated issues were marked as closedNiv Kaminer-2/+2
remove FIXME(#13101) since `assert_receiver_is_total_eq` stays. remove FIXME(#19649) now that stability markers render. remove FIXME(#13642) now the benchmarks were moved. remove FIXME(#6220) now that floating points can be formatted. remove FIXME(#18248) and write tests for `Rc<str>` and `Rc<[u8]>` remove reference to irelevent issues in FIXME(#1697, #2178...) update FIXME(#5516) to point to getopts issue 7 update FIXME(#7771) to point to RFC 628 update FIXME(#19839) to point to issue 26925
2017-08-15use field init shorthand EVERYWHEREZack M. Davis-7/+7
Like #43008 (f668999), but _much more aggressive_.
2017-08-01Fixed extra cases found in better checking.Isaac van Bakel-1/+1
2017-07-22Add conversions from references to NonZero pointers, Unique, and SharedSimon Sapin-1/+1
2017-07-22Rename {NonZero,Shared,Unique}::new to new_uncheckedSimon Sapin-3/+3
2017-07-05rustc: Implement the #[global_allocator] attributeAlex Crichton-6/+5
This PR is an implementation of [RFC 1974] which specifies a new method of defining a global allocator for a program. This obsoletes the old `#![allocator]` attribute and also removes support for it. [RFC 1974]: https://github.com/rust-lang/rfcs/pull/197 The new `#[global_allocator]` attribute solves many issues encountered with the `#![allocator]` attribute such as composition and restrictions on the crate graph itself. The compiler now has much more control over the ABI of the allocator and how it's implemented, allowing much more freedom in terms of how this feature is implemented. cc #27389
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
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-03-01 21:42:52 +0000