about summary refs log tree commit diff
path: root/src/libstd/collections
AgeCommit message (Collapse)AuthorLines
2015-01-15add a section on performance to collection docsAlexis-2/+52
2015-01-10Add ExactSizeIterator impls for Hash{Map, Set, Table}Chase Southwood-30/+98
This commit also changes the return types of all `size_hint()` impls in these files from (uint, Option<uint>) to (usize, Option<usize>).
2015-01-08Improvements to feature stagingBrian Anderson-1/+1
This gets rid of the 'experimental' level, removes the non-staged_api case (i.e. stability levels for out-of-tree crates), and lets the staged_api attributes use 'unstable' and 'deprecated' lints. This makes the transition period to the full feature staging design a bit nicer.
2015-01-07rollup merge of #20654: alexcrichton/stabilize-hashAlex Crichton-154/+341
This commit aims to prepare the `std::hash` module for alpha by formalizing its current interface whileholding off on adding `#[stable]` to the new APIs. The current usage with the `HashMap` and `HashSet` types is also reconciled by separating out composable parts of the design. The primary goal of this slight redesign is to separate the concepts of a hasher's state from a hashing algorithm itself. The primary change of this commit is to separate the `Hasher` trait into a `Hasher` and a `HashState` trait. Conceptually the old `Hasher` trait was actually just a factory for various states, but hashing had very little control over how these states were used. Additionally the old `Hasher` trait was actually fairly unrelated to hashing. This commit redesigns the existing `Hasher` trait to match what the notion of a `Hasher` normally implies with the following definition: trait Hasher { type Output; fn reset(&mut self); fn finish(&self) -> Output; } This `Hasher` trait emphasizes that hashing algorithms may produce outputs other than a `u64`, so the output type is made generic. Other than that, however, very little is assumed about a particular hasher. It is left up to implementors to provide specific methods or trait implementations to feed data into a hasher. The corresponding `Hash` trait becomes: trait Hash<H: Hasher> { fn hash(&self, &mut H); } The old default of `SipState` was removed from this trait as it's not something that we're willing to stabilize until the end of time, but the type parameter is always required to implement `Hasher`. Note that the type parameter `H` remains on the trait to enable multidispatch for specialization of hashing for particular hashers. Note that `Writer` is not mentioned in either of `Hash` or `Hasher`, it is simply used as part `derive` and the implementations for all primitive types. With these definitions, the old `Hasher` trait is realized as a new `HashState` trait in the `collections::hash_state` module as an unstable addition for now. The current definition looks like: trait HashState { type Hasher: Hasher; fn hasher(&self) -> Hasher; } The purpose of this trait is to emphasize that the one piece of functionality for implementors is that new instances of `Hasher` can be created. This conceptually represents the two keys from which more instances of a `SipHasher` can be created, and a `HashState` is what's stored in a `HashMap`, not a `Hasher`. Implementors of custom hash algorithms should implement the `Hasher` trait, and only hash algorithms intended for use in hash maps need to implement or worry about the `HashState` trait. The entire module and `HashState` infrastructure remains `#[unstable]` due to it being recently redesigned, but some other stability decision made for the `std::hash` module are: * The `Writer` trait remains `#[experimental]` as it's intended to be replaced with an `io::Writer` (more details soon). * The top-level `hash` function is `#[unstable]` as it is intended to be generic over the hashing algorithm instead of hardwired to `SipHasher` * The inner `sip` module is now private as its one export, `SipHasher` is reexported in the `hash` module. And finally, a few changes were made to the default parameters on `HashMap`. * The `RandomSipHasher` default type parameter was renamed to `RandomState`. This renaming emphasizes that it is not a hasher, but rather just state to generate hashers. It also moves away from the name "sip" as it may not always be implemented as `SipHasher`. This type lives in the `std::collections::hash_map` module as `#[unstable]` * The associated `Hasher` type of `RandomState` is creatively called... `Hasher`! This concrete structure lives next to `RandomState` as an implemenation of the "default hashing algorithm" used for a `HashMap`. Under the hood this is currently implemented as `SipHasher`, but it draws an explicit interface for now and allows us to modify the implementation over time if necessary. There are many breaking changes outlined above, and as a result this commit is a: [breaking-change]
2015-01-07std: Stabilize the std::hash moduleAlex Crichton-154/+341
This commit aims to prepare the `std::hash` module for alpha by formalizing its current interface whileholding off on adding `#[stable]` to the new APIs. The current usage with the `HashMap` and `HashSet` types is also reconciled by separating out composable parts of the design. The primary goal of this slight redesign is to separate the concepts of a hasher's state from a hashing algorithm itself. The primary change of this commit is to separate the `Hasher` trait into a `Hasher` and a `HashState` trait. Conceptually the old `Hasher` trait was actually just a factory for various states, but hashing had very little control over how these states were used. Additionally the old `Hasher` trait was actually fairly unrelated to hashing. This commit redesigns the existing `Hasher` trait to match what the notion of a `Hasher` normally implies with the following definition: trait Hasher { type Output; fn reset(&mut self); fn finish(&self) -> Output; } This `Hasher` trait emphasizes that hashing algorithms may produce outputs other than a `u64`, so the output type is made generic. Other than that, however, very little is assumed about a particular hasher. It is left up to implementors to provide specific methods or trait implementations to feed data into a hasher. The corresponding `Hash` trait becomes: trait Hash<H: Hasher> { fn hash(&self, &mut H); } The old default of `SipState` was removed from this trait as it's not something that we're willing to stabilize until the end of time, but the type parameter is always required to implement `Hasher`. Note that the type parameter `H` remains on the trait to enable multidispatch for specialization of hashing for particular hashers. Note that `Writer` is not mentioned in either of `Hash` or `Hasher`, it is simply used as part `derive` and the implementations for all primitive types. With these definitions, the old `Hasher` trait is realized as a new `HashState` trait in the `collections::hash_state` module as an unstable addition for now. The current definition looks like: trait HashState { type Hasher: Hasher; fn hasher(&self) -> Hasher; } The purpose of this trait is to emphasize that the one piece of functionality for implementors is that new instances of `Hasher` can be created. This conceptually represents the two keys from which more instances of a `SipHasher` can be created, and a `HashState` is what's stored in a `HashMap`, not a `Hasher`. Implementors of custom hash algorithms should implement the `Hasher` trait, and only hash algorithms intended for use in hash maps need to implement or worry about the `HashState` trait. The entire module and `HashState` infrastructure remains `#[unstable]` due to it being recently redesigned, but some other stability decision made for the `std::hash` module are: * The `Writer` trait remains `#[experimental]` as it's intended to be replaced with an `io::Writer` (more details soon). * The top-level `hash` function is `#[unstable]` as it is intended to be generic over the hashing algorithm instead of hardwired to `SipHasher` * The inner `sip` module is now private as its one export, `SipHasher` is reexported in the `hash` module. And finally, a few changes were made to the default parameters on `HashMap`. * The `RandomSipHasher` default type parameter was renamed to `RandomState`. This renaming emphasizes that it is not a hasher, but rather just state to generate hashers. It also moves away from the name "sip" as it may not always be implemented as `SipHasher`. This type lives in the `std::collections::hash_map` module as `#[unstable]` * The associated `Hasher` type of `RandomState` is creatively called... `Hasher`! This concrete structure lives next to `RandomState` as an implemenation of the "default hashing algorithm" used for a `HashMap`. Under the hood this is currently implemented as `SipHasher`, but it draws an explicit interface for now and allows us to modify the implementation over time if necessary. There are many breaking changes outlined above, and as a result this commit is a: [breaking-change]
2015-01-07Merge pull request #20674 from jbcrail/fix-misspelled-commentsbors-1/+1
Fix misspelled comments. Reviewed-by: steveklabnik
2015-01-06More test fixesAlex Crichton-2/+3
2015-01-06Fix misspelled comments.Joseph Crail-1/+1
I cleaned up comments prior to the 1.0 alpha release.
2015-01-06rollup merge of #20607: nrc/kindsAlex Crichton-3/+3
Conflicts: src/libcore/array.rs src/libcore/cell.rs src/libcore/prelude.rs src/libstd/path/posix.rs src/libstd/prelude/v1.rs src/test/compile-fail/dst-sized-trait-param.rs
2015-01-06rollup merge of #20593: nikomatsakis/unused-tps-in-implAlex Crichton-0/+25
Conflicts: src/libcollections/lib.rs src/librustc/lib.rs src/libserialize/lib.rs src/libstd/lib.rs
2015-01-06rollup merge of #20653: alexcrichton/entry-unstableAlex Crichton-38/+29
There's been some debate over the precise form that these APIs should take, and they've undergone some changes recently, so these APIs are going to be left unstable for now to be fleshed out during the next release cycle.
2015-01-06Register new snapshotsAlex Crichton-3/+0
Conflicts: src/librbml/lib.rs src/libserialize/json_stage0.rs src/libserialize/serialize_stage0.rs src/libsyntax/ast.rs src/libsyntax/ext/deriving/generic/mod.rs src/libsyntax/parse/token.rs
2015-01-07markers -> markerNick Cameron-13/+13
2015-01-06core: split into fmt::Show and fmt::StringSean McArthur-12/+12
fmt::Show is for debugging, and can and should be implemented for all public types. This trait is used with `{:?}` syntax. There still exists #[derive(Show)]. fmt::String is for types that faithfully be represented as a String. Because of this, there is no way to derive fmt::String, all implementations must be purposeful. It is used by the default format syntax, `{}`. This will break most instances of `{}`, since that now requires the type to impl fmt::String. In most cases, replacing `{}` with `{:?}` is the correct fix. Types that were being printed specifically for users should receive a fmt::String implementation to fix this. Part of #20013 [breaking-change]
2015-01-06Fix fallout in libs. For the most part I just tagged impls as ↵Niko Matsakis-0/+25
`#[old_impl_check]`.
2015-01-07Change `std::kinds` to `std::markers`; flatten `std::kinds::marker`Nick Cameron-13/+13
[breaking-change]
2015-01-06std: Revert stability of Entry-based APIsAlex Crichton-11/+7
There's been some debate over the precise form that these APIs should take, and they've undergone some changes recently, so these APIs are going to be left unstable for now to be fleshed out during the next release cycle.
2015-01-06[breaking change] Revert Entry behaviour to take keys by value.Dylan Ede-27/+22
2015-01-05Revert "Remove i suffix in docs"Alex Crichton-14/+14
This reverts commit f031671c6ea79391eeb3e1ad8f06fe0e436103fb. Conflicts: src/libcollections/slice.rs src/libcore/iter.rs src/libstd/sync/mpsc/mod.rs src/libstd/sync/rwlock.rs
2015-01-05rollup merge of #20482: kmcallister/macro-reformAlex Crichton-1/+3
Conflicts: src/libflate/lib.rs src/libstd/lib.rs src/libstd/macros.rs src/libsyntax/feature_gate.rs src/libsyntax/parse/parser.rs src/libsyntax/show_span.rs src/test/auxiliary/macro_crate_test.rs src/test/compile-fail/lint-stability.rs src/test/run-pass/intrinsics-math.rs src/test/run-pass/tcp-connect-timeouts.rs
2015-01-05Merge remote-tracking branch 'nrc/sized-2' into rollupAlex Crichton-18/+18
Conflicts: src/liballoc/boxed.rs src/libcollections/btree/map.rs src/libcollections/slice.rs src/libcore/borrow.rs src/libcore/cmp.rs src/libcore/ops.rs src/libstd/c_str.rs src/libstd/collections/hash/map.rs src/libsyntax/parse/obsolete.rs src/test/compile-fail/unboxed-closure-sugar-default.rs src/test/compile-fail/unboxed-closure-sugar-equiv.rs src/test/compile-fail/unboxed-closure-sugar-lifetime-elision.rs src/test/compile-fail/unboxed-closure-sugar-region.rs src/test/compile-fail/unsized3.rs src/test/run-pass/associated-types-conditional-dispatch.rs
2015-01-05rollup merge of #20581: apasel422/extendAlex Crichton-2/+2
2015-01-05rollup merge of #20560: aturon/stab-2-iter-ops-sliceAlex Crichton-2/+4
Conflicts: src/libcollections/slice.rs src/libcore/iter.rs src/libstd/sync/mpsc/mod.rs src/libstd/sync/rwlock.rs
2015-01-05rollup merge of #20434: steveklabnik/five_eyeAlex Crichton-14/+14
This takes advantage of integer fallback to stop recomending `i` so much.
2015-01-06FalloutNick Cameron-20/+20
2015-01-05Remove i suffix in docsSteve Klabnik-14/+14
2015-01-05Stabilization of impls and fallout from stabilizationAaron Turon-1/+1
2015-01-05register snapshotJorge Aparicio-26/+0
2015-01-05Stabilize collection modulesAaron Turon-1/+3
The earlier collections stabilization did not cover the modules themselves. This commit marks as stable those modules whose types have been stabilized.
2015-01-05Use $crate and macro reexport to reduce duplicated codeKeegan McAllister-1/+3
Many of libstd's macros are now re-exported from libcore and libcollections. Their libstd definitions have moved to a macros_stage0 module and can disappear after the next snapshot. Where the two crates had already diverged, I took the libstd versions as they're generally newer and better-tested. See e.g. d3c831b, which was a fix to libstd's assert_eq!() that didn't make it into libcore's. Fixes #16806.
2015-01-05remove unnecessary `Default` bound from `Hash{Map,Set}`'s `Extend` implAndrew Paseltiner-2/+2
2015-01-05auto merge of #20163 : bfops/rust/master, r=Gankrobors-33/+61
TODOs: - ~~Entry is still `<'a, K, V>` instead of `<'a, O, V>`~~ - ~~BTreeMap is still outstanding~~. - ~~Transform appropriate things into `.entry(...).get().or_else(|e| ...)`~~ Things that make me frowny face: - I'm not happy about the fact that this `clone`s the key even when it's already owned. - With small keys (e.g. `int`s), taking a reference seems wasteful. r? @Gankro cc: @cgaebel
2015-01-04Merge pull request #20464 from ranma42/improve-make-hashbors-8/+6
Improve `make_hash` function Reviewed-by: Gankro, Gankro
2015-01-04[breaking change] Update entry API as part of RFC 509.Ben Foppa-33/+61
2015-01-03Remove deprecated functionalityAlex Crichton-148/+5
This removes a large array of deprecated functionality, regardless of how recently it was deprecated. The purpose of this commit is to clean out the standard libraries and compiler for the upcoming alpha release. Some notable compiler changes were to enable warnings for all now-deprecated command line arguments (previously the deprecated versions were silently accepted) as well as removing deriving(Zero) entirely (the trait was removed). The distribution no longer contains the libtime or libregex_macros crates. Both of these have been deprecated for some time and are available externally.
2015-01-03sed -i -s 's/#\[deriving(/#\[derive(/g' **/*.rsJorge Aparicio-13/+13
2015-01-03sed -i -s 's/\bmod}/self}/g' **/*.rsJorge Aparicio-1/+1
2015-01-03sed -i -s 's/\bmod,/self,/g' **/*.rsJorge Aparicio-5/+5
2015-01-03std: fix falloutJorge Aparicio-0/+30
2015-01-03use assoc types in binop traitsJorge Aparicio-4/+12
2015-01-03std: fix falloutJorge Aparicio-23/+61
2015-01-03Improve `make_hash` functionAndrea Canciani-8/+6
The `make_hash` function is used to prevent hashes of non-empty buckets to collide with `EMPTY_HASH = 0u64`. Ideally this function also preserve the uniform distribution of hashes and is cheap to compute. The new implementation reduces the input hash size by one bit, simply by setting the most significant bit. This obviously prevent output hashes to collide with `EMPTY_HASH` and guarantees that the uniform distribution is preserved. Moreover, the new function is simpler (no comparisons, just an OR) and (under the same assumptions as the old function, i.e. only the least significant bit will contribute to the bucket index) no additional collisions are caused.
2015-01-02rollup merge of #20410: japaric/assoc-typesAlex Crichton-9/+9
Conflicts: src/liballoc/lib.rs src/libcollections/lib.rs src/libcollections/slice.rs src/libcore/ops.rs src/libcore/prelude.rs src/libcore/ptr.rs src/librustc/middle/traits/project.rs src/libstd/c_str.rs src/libstd/io/mem.rs src/libstd/io/mod.rs src/libstd/lib.rs src/libstd/path/posix.rs src/libstd/path/windows.rs src/libstd/prelude.rs src/libstd/rt/exclusive.rs src/libsyntax/lib.rs src/test/compile-fail/issue-18566.rs src/test/run-pass/deref-mut-on-ref.rs src/test/run-pass/deref-on-ref.rs src/test/run-pass/dst-deref-mut.rs src/test/run-pass/dst-deref.rs src/test/run-pass/fixup-deref-mut.rs src/test/run-pass/issue-13264.rs src/test/run-pass/overloaded-autoderef-indexing.rs
2015-01-02core: use assoc types in `Deref[Mut]`Jorge Aparicio-9/+9
2015-01-02rollup merge of #20273: alexcrichton/second-pass-commAlex Crichton-1/+2
Conflicts: src/doc/guide.md src/libcollections/bit.rs src/libcollections/btree/node.rs src/libcollections/slice.rs src/libcore/ops.rs src/libcore/prelude.rs src/librand/rand_impls.rs src/librustc/middle/check_match.rs src/librustc/middle/infer/region_inference/mod.rs src/librustc_driver/lib.rs src/librustdoc/test.rs src/libstd/bitflags.rs src/libstd/io/comm_adapters.rs src/libstd/io/mem.rs src/libstd/io/mod.rs src/libstd/io/net/pipe.rs src/libstd/io/net/tcp.rs src/libstd/io/net/udp.rs src/libstd/io/pipe.rs src/libstd/io/process.rs src/libstd/io/stdio.rs src/libstd/io/timer.rs src/libstd/io/util.rs src/libstd/macros.rs src/libstd/os.rs src/libstd/path/posix.rs src/libstd/path/windows.rs src/libstd/prelude/v1.rs src/libstd/rand/mod.rs src/libstd/rand/os.rs src/libstd/sync/barrier.rs src/libstd/sync/condvar.rs src/libstd/sync/future.rs src/libstd/sync/mpsc/mod.rs src/libstd/sync/mpsc/mpsc_queue.rs src/libstd/sync/mpsc/select.rs src/libstd/sync/mpsc/spsc_queue.rs src/libstd/sync/mutex.rs src/libstd/sync/once.rs src/libstd/sync/rwlock.rs src/libstd/sync/semaphore.rs src/libstd/sync/task_pool.rs src/libstd/sys/common/helper_thread.rs src/libstd/sys/unix/process.rs src/libstd/sys/unix/timer.rs src/libstd/sys/windows/c.rs src/libstd/sys/windows/timer.rs src/libstd/sys/windows/tty.rs src/libstd/thread.rs src/libstd/thread_local/mod.rs src/libstd/thread_local/scoped.rs src/libtest/lib.rs src/test/auxiliary/cci_capture_clause.rs src/test/bench/shootout-reverse-complement.rs src/test/bench/shootout-spectralnorm.rs src/test/compile-fail/array-old-syntax-2.rs src/test/compile-fail/bind-by-move-no-guards.rs src/test/compile-fail/builtin-superkinds-self-type.rs src/test/compile-fail/comm-not-freeze-receiver.rs src/test/compile-fail/comm-not-freeze.rs src/test/compile-fail/issue-12041.rs src/test/compile-fail/unsendable-class.rs src/test/run-pass/builtin-superkinds-capabilities-transitive.rs src/test/run-pass/builtin-superkinds-capabilities-xc.rs src/test/run-pass/builtin-superkinds-capabilities.rs src/test/run-pass/builtin-superkinds-self-type.rs src/test/run-pass/capturing-logging.rs src/test/run-pass/closure-bounds-can-capture-chan.rs src/test/run-pass/comm.rs src/test/run-pass/core-run-destroy.rs src/test/run-pass/drop-trait-enum.rs src/test/run-pass/hashmap-memory.rs src/test/run-pass/issue-13494.rs src/test/run-pass/issue-3609.rs src/test/run-pass/issue-4446.rs src/test/run-pass/issue-4448.rs src/test/run-pass/issue-8827.rs src/test/run-pass/issue-9396.rs src/test/run-pass/ivec-tag.rs src/test/run-pass/rust-log-filter.rs src/test/run-pass/send-resource.rs src/test/run-pass/send-type-inference.rs src/test/run-pass/sendable-class.rs src/test/run-pass/spawn-types.rs src/test/run-pass/task-comm-0.rs src/test/run-pass/task-comm-10.rs src/test/run-pass/task-comm-11.rs src/test/run-pass/task-comm-13.rs src/test/run-pass/task-comm-14.rs src/test/run-pass/task-comm-15.rs src/test/run-pass/task-comm-16.rs src/test/run-pass/task-comm-3.rs src/test/run-pass/task-comm-4.rs src/test/run-pass/task-comm-5.rs src/test/run-pass/task-comm-6.rs src/test/run-pass/task-comm-7.rs src/test/run-pass/task-comm-9.rs src/test/run-pass/task-comm-chan-nil.rs src/test/run-pass/task-spawn-move-and-copy.rs src/test/run-pass/task-stderr.rs src/test/run-pass/tcp-accept-stress.rs src/test/run-pass/tcp-connect-timeouts.rs src/test/run-pass/tempfile.rs src/test/run-pass/trait-bounds-in-arc.rs src/test/run-pass/trivial-message.rs src/test/run-pass/unique-send-2.rs src/test/run-pass/unique-send.rs src/test/run-pass/unwind-resource.rs
2015-01-02std: Stabilize the prelude moduleAlex Crichton-4/+5
This commit is an implementation of [RFC 503][rfc] which is a stabilization story for the prelude. Most of the RFC was directly applied, removing reexports. Some reexports are kept around, however: * `range` remains until range syntax has landed to reduce churn. * `Path` and `GenericPath` remain until path reform lands. This is done to prevent many imports of `GenericPath` which will soon be removed. * All `io` traits remain until I/O reform lands so imports can be rewritten all at once to `std::io::prelude::*`. This is a breaking change because many prelude reexports have been removed, and the RFC can be consulted for the exact list of removed reexports, as well as to find the locations of where to import them. [rfc]: https://github.com/rust-lang/rfcs/blob/master/text/0503-prelude-stabilization.md [breaking-change] Closes #20068
2014-12-31stabilize more of collectionsAlexis Beingessner-43/+83
2014-12-31Test fixes and rebase conflictsAlex Crichton-6/+6
2014-12-30rollup merge of #20328: huonw/attack-of-the-clonesAlex Crichton-0/+50
It's useful to be able to save state.
2014-12-30Stabilize cmpAaron Turon-0/+4
This patch marks `PartialEq`, `Eq`, `PartialOrd`, and `Ord` as `#[stable]`, as well as the majorify of manual implementaitons of these traits. The traits match the [reform RFC](https://github.com/rust-lang/rfcs/pull/439). Along the way, two changes are made: * The recently-added type parameters for `Ord` and `Eq` are removed. These were mistakenly added while adding them to `PartialOrd` and `PartialEq`, but they don't make sense given the laws that are required for (and use cases for) `Ord` and `Eq`. * More explicit laws are added for `PartialEq` and `PartialOrd`, connecting them to their associated mathematical concepts. In the future, many of the impls should be generalized; see since generalizing later is not a breaking change. [breaking-change]
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-25 23:31:12 +0000