summary refs log tree commit diff
path: root/src/libstd/collections
AgeCommit message (Collapse)AuthorLines
2016-10-10std: 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-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-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
2016-07-18Add debug for hash_map::{Entry, VacantEntry, OccupiedEntry}ggomez-0/+33
2016-06-29std: use siphash-1-3 for HashMapSean McArthur-4/+24
2016-06-17Add short summaries to btree modulesOliver Middleton-2/+4
Also improve hash_map and hash_set module short summaries.
2016-06-15Map::Entry::take() method to recover key and value togetherSean McArthur-0/+13
2016-06-11run rustfmt on libstd/collections/hash folderSrinivas Reddy Thatiparthy-167/+178
2016-05-25Auto merge of #33699 - alexcrichton:stabilize-1.10, r=aturonbors-9/+8
std: Stabilize APIs for the 1.10 release This commit applies the FCP decisions made by the libs team for the 1.10 cycle, including both new stabilizations and deprecations. Specifically, the list of APIs is: Stabilized: * `os::windows::fs::OpenOptionsExt::access_mode` * `os::windows::fs::OpenOptionsExt::share_mode` * `os::windows::fs::OpenOptionsExt::custom_flags` * `os::windows::fs::OpenOptionsExt::attributes` * `os::windows::fs::OpenOptionsExt::security_qos_flags` * `os::unix::fs::OpenOptionsExt::custom_flags` * `sync::Weak::new` * `Default for sync::Weak` * `panic::set_hook` * `panic::take_hook` * `panic::PanicInfo` * `panic::PanicInfo::payload` * `panic::PanicInfo::location` * `panic::Location` * `panic::Location::file` * `panic::Location::line` * `ffi::CStr::from_bytes_with_nul` * `ffi::CStr::from_bytes_with_nul_unchecked` * `ffi::FromBytesWithNulError` * `fs::Metadata::modified` * `fs::Metadata::accessed` * `fs::Metadata::created` * `sync::atomic::Atomic{Usize,Isize,Bool,Ptr}::compare_exchange` * `sync::atomic::Atomic{Usize,Isize,Bool,Ptr}::compare_exchange_weak` * `collections::{btree,hash}_map::{Occupied,Vacant,}Entry::key` * `os::unix::net::{UnixStream, UnixListener, UnixDatagram, SocketAddr}` * `SocketAddr::is_unnamed` * `SocketAddr::as_pathname` * `UnixStream::connect` * `UnixStream::pair` * `UnixStream::try_clone` * `UnixStream::local_addr` * `UnixStream::peer_addr` * `UnixStream::set_read_timeout` * `UnixStream::set_write_timeout` * `UnixStream::read_timeout` * `UnixStream::write_Timeout` * `UnixStream::set_nonblocking` * `UnixStream::take_error` * `UnixStream::shutdown` * Read/Write/RawFd impls for `UnixStream` * `UnixListener::bind` * `UnixListener::accept` * `UnixListener::try_clone` * `UnixListener::local_addr` * `UnixListener::set_nonblocking` * `UnixListener::take_error` * `UnixListener::incoming` * RawFd impls for `UnixListener` * `UnixDatagram::bind` * `UnixDatagram::unbound` * `UnixDatagram::pair` * `UnixDatagram::connect` * `UnixDatagram::try_clone` * `UnixDatagram::local_addr` * `UnixDatagram::peer_addr` * `UnixDatagram::recv_from` * `UnixDatagram::recv` * `UnixDatagram::send_to` * `UnixDatagram::send` * `UnixDatagram::set_read_timeout` * `UnixDatagram::set_write_timeout` * `UnixDatagram::read_timeout` * `UnixDatagram::write_timeout` * `UnixDatagram::set_nonblocking` * `UnixDatagram::take_error` * `UnixDatagram::shutdown` * RawFd impls for `UnixDatagram` * `{BTree,Hash}Map::values_mut` * `<[_]>::binary_search_by_key` Deprecated: * `StaticCondvar` - this, and all other static synchronization primitives below, are usable today through the lazy-static crate on stable Rust today. Additionally, we'd like the non-static versions to be directly usable in a static context one day, so they're unlikely to be the final forms of the APIs in any case. * `CONDVAR_INIT` * `StaticMutex` * `MUTEX_INIT` * `StaticRwLock` * `RWLOCK_INIT` * `iter::Peekable::is_empty` Closes #27717 Closes #27720 Closes #30014 Closes #30425 Closes #30449 Closes #31190 Closes #31399 Closes #31767 Closes #32111 Closes #32281 Closes #32312 Closes #32551 Closes #33018
2016-05-24std: Stabilize APIs for the 1.10 releaseAlex Crichton-9/+8
This commit applies the FCP decisions made by the libs team for the 1.10 cycle, including both new stabilizations and deprecations. Specifically, the list of APIs is: Stabilized: * `os::windows::fs::OpenOptionsExt::access_mode` * `os::windows::fs::OpenOptionsExt::share_mode` * `os::windows::fs::OpenOptionsExt::custom_flags` * `os::windows::fs::OpenOptionsExt::attributes` * `os::windows::fs::OpenOptionsExt::security_qos_flags` * `os::unix::fs::OpenOptionsExt::custom_flags` * `sync::Weak::new` * `Default for sync::Weak` * `panic::set_hook` * `panic::take_hook` * `panic::PanicInfo` * `panic::PanicInfo::payload` * `panic::PanicInfo::location` * `panic::Location` * `panic::Location::file` * `panic::Location::line` * `ffi::CStr::from_bytes_with_nul` * `ffi::CStr::from_bytes_with_nul_unchecked` * `ffi::FromBytesWithNulError` * `fs::Metadata::modified` * `fs::Metadata::accessed` * `fs::Metadata::created` * `sync::atomic::Atomic{Usize,Isize,Bool,Ptr}::compare_exchange` * `sync::atomic::Atomic{Usize,Isize,Bool,Ptr}::compare_exchange_weak` * `collections::{btree,hash}_map::{Occupied,Vacant,}Entry::key` * `os::unix::net::{UnixStream, UnixListener, UnixDatagram, SocketAddr}` * `SocketAddr::is_unnamed` * `SocketAddr::as_pathname` * `UnixStream::connect` * `UnixStream::pair` * `UnixStream::try_clone` * `UnixStream::local_addr` * `UnixStream::peer_addr` * `UnixStream::set_read_timeout` * `UnixStream::set_write_timeout` * `UnixStream::read_timeout` * `UnixStream::write_Timeout` * `UnixStream::set_nonblocking` * `UnixStream::take_error` * `UnixStream::shutdown` * Read/Write/RawFd impls for `UnixStream` * `UnixListener::bind` * `UnixListener::accept` * `UnixListener::try_clone` * `UnixListener::local_addr` * `UnixListener::set_nonblocking` * `UnixListener::take_error` * `UnixListener::incoming` * RawFd impls for `UnixListener` * `UnixDatagram::bind` * `UnixDatagram::unbound` * `UnixDatagram::pair` * `UnixDatagram::connect` * `UnixDatagram::try_clone` * `UnixDatagram::local_addr` * `UnixDatagram::peer_addr` * `UnixDatagram::recv_from` * `UnixDatagram::recv` * `UnixDatagram::send_to` * `UnixDatagram::send` * `UnixDatagram::set_read_timeout` * `UnixDatagram::set_write_timeout` * `UnixDatagram::read_timeout` * `UnixDatagram::write_timeout` * `UnixDatagram::set_nonblocking` * `UnixDatagram::take_error` * `UnixDatagram::shutdown` * RawFd impls for `UnixDatagram` * `{BTree,Hash}Map::values_mut` * `<[_]>::binary_search_by_key` Deprecated: * `StaticCondvar` - this, and all other static synchronization primitives below, are usable today through the lazy-static crate on stable Rust today. Additionally, we'd like the non-static versions to be directly usable in a static context one day, so they're unlikely to be the final forms of the APIs in any case. * `CONDVAR_INIT` * `StaticMutex` * `MUTEX_INIT` * `StaticRwLock` * `RWLOCK_INIT` * `iter::Peekable::is_empty` Closes #27717 Closes #27720 cc #27784 (but encode methods still exist) Closes #30014 Closes #30425 Closes #30449 Closes #31190 Closes #31399 Closes #31767 Closes #32111 Closes #32281 Closes #32312 Closes #32551 Closes #33018
2016-05-19std: Cache HashMap keys in TLSAlex Crichton-2/+27
This is a rebase and extension of #31356 where we cache the keys in thread local storage. This should give us a nice speed bost in creating hash maps along with mostly retaining the property that all maps have a nondeterministic iteration order. Closes #27243
2016-05-08Auto merge of #33091 - sanxiyn:unused-trait-import-3, r=nrcbors-1/+0
Warn unused trait imports, rebased Rebase of #30021. Fix #25730.
2016-05-06Auto merge of #33086 - cardoe:non-blocking-rand-read, r=alexcrichtonbors-2/+4
rand: don't block before random pool is initialized If we attempt a read with getrandom() on Linux the syscall can block before the random pool is initialized unless the GRND_NONBLOCK flag is passed. This flag causes getrandom() to instead return EAGAIN while the pool is uninitialized. To avoid downstream users of crate or std functionality that have no ability to avoid this blocking behavior this change causes Rust to read bytes from /dev/urandom while getrandom() would block and once getrandom() is available to use that. Fixes #32953. Signed-off-by: Doug Goldstein <cardoe@cardoe.com>
2016-05-03Remove unused trait imports flagged by lintSeo Sanghyeon-1/+0
2016-04-29Auto merge of #33148 - sfackler:entry-key, r=alexcrichtonbors-0/+9
Add Entry::key This method was present on both variants of Entry, but not the enum cc #32281 r? @alexcrichton
2016-04-28Rollup merge of #33152 - bwinterton:master, r=steveklabnikSteve Klabnik-2/+2
Make HashSet::Insert documentation more consistent I have made the HashSet::Insert documentation more consistent in the use of the term 'value' vs 'key'. Also clarified that if _this_ value is present true is returned, instead of the ambiguous 'a value present'. r? @steveklabnik
2016-04-24thread tighter span for closures aroundNiko Matsakis-3/+3
Track the span corresponding to the `|...|` part of the closure.
2016-04-22Make HashSet::Insert documentation more consistentBrayden Winterton-2/+2
2016-04-22Implement `append` for b-trees.Johannes Oertel-6/+4
The algorithm implemented here is linear in the size of the two b-trees. It firsts creates a `MergeIter` from the two b-trees and then builds a new b-tree by pushing key-value pairs from the `MergeIter` into nodes at the right heights. Three functions for stealing have been added to the implementation of `Handle` as well as a getter for the height of a `NodeRef`. The docs have been updated with performance information about `BTreeMap::append` and the remark about B has been removed now that it is the same for all instances of `BTreeMap`.
2016-04-21Add Entry::keySteven Fackler-0/+9
This method was present on both variants of Entry, but not the enum cc #32281
2016-04-20HashMap: add info to docs about random seed qualityDoug Goldstein-2/+4
The random functions that HashMap use make no guarantees about the quality of random data so this documents that to the user so that they are aware. This was brought about by the change to the Linux random code to not block until the urandom pool was initialized to avoid users of crates that internally use HashMap being caught unaware and having their application block until the urandom pool is initialized. Signed-off-by: Doug Goldstein <cardoe@cardoe.com>
2016-04-11std: Stabilize APIs for the 1.9 releaseAlex Crichton-7/+5
This commit applies all stabilizations, renamings, and deprecations that the library team has decided on for the upcoming 1.9 release. All tracking issues have gone through a cycle-long "final comment period" and the specific APIs stabilized/deprecated are: Stable * `std::panic` * `std::panic::catch_unwind` (renamed from `recover`) * `std::panic::resume_unwind` (renamed from `propagate`) * `std::panic::AssertUnwindSafe` (renamed from `AssertRecoverSafe`) * `std::panic::UnwindSafe` (renamed from `RecoverSafe`) * `str::is_char_boundary` * `<*const T>::as_ref` * `<*mut T>::as_ref` * `<*mut T>::as_mut` * `AsciiExt::make_ascii_uppercase` * `AsciiExt::make_ascii_lowercase` * `char::decode_utf16` * `char::DecodeUtf16` * `char::DecodeUtf16Error` * `char::DecodeUtf16Error::unpaired_surrogate` * `BTreeSet::take` * `BTreeSet::replace` * `BTreeSet::get` * `HashSet::take` * `HashSet::replace` * `HashSet::get` * `OsString::with_capacity` * `OsString::clear` * `OsString::capacity` * `OsString::reserve` * `OsString::reserve_exact` * `OsStr::is_empty` * `OsStr::len` * `std::os::unix::thread` * `RawPthread` * `JoinHandleExt` * `JoinHandleExt::as_pthread_t` * `JoinHandleExt::into_pthread_t` * `HashSet::hasher` * `HashMap::hasher` * `CommandExt::exec` * `File::try_clone` * `SocketAddr::set_ip` * `SocketAddr::set_port` * `SocketAddrV4::set_ip` * `SocketAddrV4::set_port` * `SocketAddrV6::set_ip` * `SocketAddrV6::set_port` * `SocketAddrV6::set_flowinfo` * `SocketAddrV6::set_scope_id` * `<[T]>::copy_from_slice` * `ptr::read_volatile` * `ptr::write_volatile` * The `#[deprecated]` attribute * `OpenOptions::create_new` Deprecated * `std::raw::Slice` - use raw parts of `slice` module instead * `std::raw::Repr` - use raw parts of `slice` module instead * `str::char_range_at` - use slicing plus `chars()` plus `len_utf8` * `str::char_range_at_reverse` - use slicing plus `chars().rev()` plus `len_utf8` * `str::char_at` - use slicing plus `chars()` * `str::char_at_reverse` - use slicing plus `chars().rev()` * `str::slice_shift_char` - use `chars()` plus `Chars::as_str` * `CommandExt::session_leader` - use `before_exec` instead. Closes #27719 cc #27751 (deprecating the `Slice` bits) Closes #27754 Closes #27780 Closes #27809 Closes #27811 Closes #27830 Closes #28050 Closes #29453 Closes #29791 Closes #29935 Closes #30014 Closes #30752 Closes #31262 cc #31398 (still need to deal with `before_exec`) Closes #31405 Closes #31572 Closes #31755 Closes #31756
2016-04-06Rollup merge of #32668 - frewsxcv:hashmap-address-fixme, r=alexcrichtonSteve Klabnik-8/+4
Address FIXMEs related to short lifetimes in `HashMap`. None
2016-04-01Implement `values_mut` on `HashMap`.Corey Farwell-0/+61
https://github.com/rust-lang/rust/issues/32551
2016-04-01Address FIXMEs related to short lifetimes in `HashMap`.Corey Farwell-8/+4
2016-03-30Test that HashMap, HashSet, and their iterators are properly covariantJonathan S-0/+29
2016-03-30Fix the variances of HashMap and HashSet iteratorsJonathan S-26/+20
2016-03-30Make HashMap's RawBucket covariantJonathan S-18/+23
2016-03-30Remove no longer necessary coercions to fn pointer types.Corey Farwell-12/+0
Originally added in 8fe9e4dff6d9d0fdd940835ae377edcb3754f8c1. Everything appears to build fine without the coercions, so they can presumably be removed.
2016-03-28style: Use `iter` for IntoIterator parameter namesKamal Marhubi-8/+8
This commit standardizes the codebase on `iter` for parameters with IntoIterator bounds. Previously about 40% of IntoIterator parameters were named `iterable`, with most of the rest being named `iter`. There was a single place where it was named `iterator`.
2016-03-22Auto merge of #32058 - pczarn:hashmap-initial-refactoring, r=apasel422bors-224/+250
Basic refactoring of HashMap
2016-03-22f clarification, docsPiotr Czarnecki-2/+10
2016-03-22f Put and DerefMutPiotr Czarnecki-14/+26
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-07-06 13:51:00 +0000