about summary refs log tree commit diff
path: root/src/libcore/slice.rs
AgeCommit message (Collapse)AuthorLines
2017-03-21Implement feature sort_unstableStjepan Glavina-2382/+0
2017-03-14Link core::slice to std::slicesteveklabnik-1/+3
2017-02-16Additional docs for Vec, String, and slice trait implsMatt Brubeck-0/+2
2017-02-08Remove unnecessary specialization for [u8]Stjepan Glavina-7/+0
2017-02-08Simplify by calling SliceOrd::compareStjepan Glavina-15/+1
2017-02-08Specialize `PartialOrd<A> for [A] where A: Ord`Stjepan Glavina-0/+22
This way we can call `cmp` instead of `partial_cmp` in the loop, removing some burden of optimizing `Option`s away from the compiler. PR #39538 introduced a regression where sorting slices suddenly became slower, since `slice1.lt(slice2)` was much slower than `slice1.cmp(slice2) == Less`. This problem is now fixed. To verify, I benchmarked this simple program: ```rust fn main() { let mut v = (0..2_000_000).map(|x| x * x * x * 18913515181).map(|x| vec![x, x ^ 3137831591]).collect::<Vec<_>>(); v.sort(); } ``` Before this PR, it would take 0.95 sec, and now it takes 0.58 sec. I also tried changing the `is_less` lambda to use `cmp` and `partial_cmp`. Now all three versions (`lt`, `cmp`, `partial_cmp`) are equally performant for sorting slices - all of them take 0.58 sec on the benchmark.
2017-01-29Fix a few impl stability attributesOliver Middleton-7/+7
The versions show up in rustdoc.
2017-01-17Auto merge of #37972 - bluss:iter-find-is-on-a-roll, r=sfacklerbors-14/+185
Improve the slice iterator's searching methods Improve all, any, find, position, rposition by explicitly unrolling the loop for the slice iterators. - Introduce a few extension methods and functions for raw pointers make the new code easy to express - Introduce helper methods `search_while, rsearch_while` that generalize all the searching methods LLVM doesn't unroll the loop in `.find()` by default (clang is the same), so performance benefits a lot from explicit unrolling here. An iterator method without conditional exits (like `.fold()`) does not need this on the other hand. One of the raw pointer extension methods is `fn post_inc(&mut self) -> Self` which is the rustic equivalent of “`ptr++`”, and it is a nice way to express the raw pointer loop (see commit 3). Specific development notes about `search_while`: I tried both computing an end pointer "rounded" to 4, as well as the `ptrdistance >= 4` loop condition, ptrdistance was better. I tried handling the last 0-3 elements unrolled or with a while loop, the loop was better.
2016-12-30Add links to methods on all slice iterator struct docsCurtis McEnroe-0/+45
2016-12-20Rollup merge of #37761 - christophebiocca:borrow-stdlib-fn-refactor, ↵Alex Crichton-9/+13
r=alexcrichton Use Borrow for binary_search and contains methods in the standard library Fixes all standard library methods in #32822 that can be fixed without backwards compatibility issues.
2016-11-27Add borrow support for slice binary search methods.Christophe Biocca-9/+13
2016-11-26Overload get{,_mut}{,_unchecked}Steven Fackler-168/+331
2016-11-24core: Unroll the loop in the slice iterator search methodsUlrik Sverdrup-0/+118
Introduce a helper method .search_while() that generalizes internal iteration (Iterator's all, find, position, fold and so on). The compiler does not unroll loops with conditional exits; we can do this manually instead to improve the performance of for example Iterator::find and Iterator::position when used on the slice iterators. The unrolling is patterned on libstdc++'s implementation of std::find_if.
2016-11-24core: Add ptrdistance to slice moduleUlrik Sverdrup-3/+10
2016-11-24core: Convert utility macros for the slice iterator into a traitUlrik Sverdrup-11/+57
Use an extension trait for the slice iterator's pointer manipulations.
2016-11-23core, collections: Implement better .is_empty() for slice and vec iteratorsUlrik Sverdrup-2/+10
These iterators can use a pointer comparison instead of computing the length.
2016-11-04Link the tracking issue for TrustedLenUlrik Sverdrup-2/+2
2016-10-20Introduce iterator trait TrustedLenUlrik Sverdrup-0/+6
2016-10-17Expand .zip() specialization to .map() and .cloned()Ulrik Sverdrup-0/+2
Implement .zip() specialization for Map and Cloned. The crucial thing for transparent specialization is that we want to preserve the potential side effects. The simplest example is that in this code snippet: `(0..6).map(f).zip((0..4).map(g)).count()` `f` will be called five times, and `g` four times. The last time for `f` is when the other iterator is at its end, so this element is unused. This side effect can be preserved without disturbing code generation for simple uses of `.map()`. The `Zip::next_back()` case is even more complicated, unfortunately.
2016-09-15Rollup merge of #36454 - bluss:slice-primitive-index, r=alexcrichtonManish Goregaokar-4/+4
Use primitive indexing in slice's Index/IndexMut [T]'s Index implementation is normally not used for indexing, instead the compiler supplied indexing is used. Use the compiler supplied version in Index/IndexMut. This removes an inconsistency: Compiler supplied bound check failures look like this: thread 'main' panicked at 'index out of bounds: the len is 3 but the index is 4' If you convince Rust to use the Index impl for slices, bounds check failure looks like this instead: thread 'main' panicked at 'assertion failed: index < self.len()' The latter is used if you for example use Index generically: ```rust use std::ops::Index; fn foo<T: ?Sized>(x: &T) where T: Index<usize> { &x[4]; } foo(&[1, 2, 3][..]) ```
2016-09-14core: Use primitive indexing in slice's Index/IndexMutUlrik Sverdrup-4/+4
[T]'s Index implementation is normally not used for indexing, instead the compiler supplied indexing is used. Use the compiler supplied version in Index/IndexMut. This removes an inconsistency: Compiler supplied bound check failures look like this: thread 'main' panicked at 'index out of bounds: the len is 3 but the index is 4' If you convince Rust to use the Index impl for slices, bounds check failure looks like this instead: thread 'main' panicked at 'assertion failed: index < self.len()' The latter is used if you for example use Index generically:: use std::ops::Index; fn foo<T: ?Sized>(x: &T) where T: Index<usize> { &x[4]; } foo(&[1, 2, 3][..])
2016-09-11Documentation for default types modifiedathulappadan-2/+2
2016-09-11Documentation of what does for each typeathulappadan-0/+2
2016-09-06remove the extraneous not_equal implementation for slices.Justin LeFebvre-19/+2
2016-08-24Use `#[prelude_import]` in `libcore`.Jeffrey Seyfried-12/+3
2016-08-18Add a FusedIterator trait.Steven Allen-0/+25
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-16Implement `AsRef<[T]>` for `std::slice::Iter`.Corey Farwell-0/+8
`AsRef` is designed for conversions that are "cheap" (as per the API docs). It is the case that retrieving the underlying data of `std::slice::Iter` is cheap. In my opinion, there's no ambiguity about what slice data will be returned, otherwise, I would be more cautious about implementing `AsRef`.
2016-08-09extend lifetime on binary_search_by_key of SliceExt traitRahul Sharma-8/+8
2016-07-17Indicate where `std::slice` structs originate from.Corey Farwell-0/+10
2016-06-23Use `len` instead of `size_hint` where appropiateTobias Bucher-4/+4
This makes it clearer that we're not just looking for a lower bound but rather know that the iterator is an `ExactSizeIterator`.
2016-06-14specialize zip: Implement TrustedRandomAccess for slice iteratorsUlrik Sverdrup-0/+15
2016-06-01Rollup merge of #33892 - seanmonstar:slice-eq-ptr, r=alexcrichtonManish Goregaokar-0/+3
core: check pointer equality when comparing byte slices If pointer address and length are the same, it should be the same slice. In experiments, I've seen that this doesn't happen as often in debug builds, but release builds seem to optimize to using a single pointer more often.
2016-05-30Correct grammar; and remove redundant commentSrinivas Reddy Thatiparthy-2/+1
2016-05-26core: check pointer equality when comparing byte slicesSean McArthur-0/+3
2016-05-25Auto merge of #33699 - alexcrichton:stabilize-1.10, r=aturonbors-5/+4
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-5/+4
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-18address review commentsAriel Ben-Yehuda-12/+12
2016-05-18implement fuzzy matching in on_unimplementedAriel Ben-Yehuda-5/+12
2016-05-11Improve error message for Index trait on slicesGuillaume Gomez-0/+4
2016-04-16Auto merge of #32909 - sanxiyn:unused-trait-import-2, r=alexcrichtonbors-1/+1
Remove unused trait imports
2016-04-15slice: Add tracking issue for slice_binary_search_by_keyKamal Marhubi-1/+1
2016-04-12collections: Add slice::binary_search_by_keyKamal Marhubi-0/+13
This method adds to the family of `_by_key` methods, and is the counterpart of `slice::sort_by_key`. It was mentioned on #30423 but was not implemented at that time. Refs #30423
2016-04-12Remove unused trait importsSeo Sanghyeon-1/+1
2016-04-12Auto merge of #32804 - alexcrichton:stabilize-1.9, r=brsonbors-8/+14
std: Stabilize APIs for the 1.9 release 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-11std: Stabilize APIs for the 1.9 releaseAlex Crichton-8/+14
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-11Rollup merge of #32768 - GuillaumeGomez:slice_doc, r=steveklabnikSteve Klabnik-0/+81
Add doc examples for Iter and IterMut Fixes #29374. r? @steveklabnik
2016-04-08Add doc example for Iter and IterMutGuillaume Gomez-4/+162
2016-04-06slice: Use doc(hidden) on private traitsUlrik Sverdrup-0/+4
This should avoid the trait impls showing up in rustdoc.
2016-04-05Specialize equality for [T] and comparison for [u8]Ulrik Sverdrup-16/+135
Where T is a type that can be compared for equality bytewise, we can use memcmp. We can also use memcmp for PartialOrd, Ord for [u8] and by extension &str. This is an improvement for example for the comparison [u8] == [u8] that used to emit a loop that compared the slices byte by byte. One worry here could be that this introduces function calls to memcmp in contexts where it should really inline the comparison or even optimize it out, but llvm takes care of recognizing memcmp specifically.
2016-03-21Auto merge of #32054 - seanmonstar:impl-debug-core, r=alexcrichtonbors-0/+79
libcore: add Debug implementations to most missing types Also adds `#![deny(missing_debug_implementations)]` to the core crate. cc #31869
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-25 11:30:09 +0000