diff options
author | Joel Galenson <jgalenson@google.com> | 2021-06-09 21:17:11 +0000 |
---|---|---|
committer | Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com> | 2021-06-09 21:17:11 +0000 |
commit | 202d85cc4f1e7bf05e0c9c5857f419a75e708c20 (patch) | |
tree | 0dcab013f19a5df6b8d8fc42f5ec73b39ca3dc22 | |
parent | e150d913b5eaaa59e3e1fa87d2ec3d64de16f19b (diff) | |
parent | d54dec1dcbf804b1c1fe04ed890f118dcd9e436f (diff) | |
download | slab-202d85cc4f1e7bf05e0c9c5857f419a75e708c20.tar.gz |
Upgrade rust/crates/slab to 0.4.3 am: c03c72f058 am: 2a4ca8c887 am: c1c74762db am: d54dec1dcb
Original change: https://android-review.googlesource.com/c/platform/external/rust/crates/slab/+/1713268
Change-Id: I788c2d707b889330851370e682785fb6fc5f89a0
-rw-r--r-- | .cargo_vcs_info.json | 2 | ||||
-rw-r--r-- | .clippy.toml | 1 | ||||
-rw-r--r-- | .github/workflows/ci.yml | 73 | ||||
-rw-r--r-- | .travis.yml | 39 | ||||
-rw-r--r-- | Android.bp | 45 | ||||
-rw-r--r-- | CHANGELOG.md | 13 | ||||
-rw-r--r-- | Cargo.toml | 29 | ||||
-rw-r--r-- | Cargo.toml.orig | 24 | ||||
-rw-r--r-- | METADATA | 10 | ||||
-rw-r--r-- | README.md | 13 | ||||
-rw-r--r-- | TEST_MAPPING | 256 | ||||
-rw-r--r-- | patches/disable_panic_tests_on_android.patch | 13 | ||||
-rw-r--r-- | src/lib.rs | 604 | ||||
-rw-r--r-- | src/serde.rs | 91 | ||||
-rw-r--r-- | tests/serde.rs | 50 | ||||
-rw-r--r-- | tests/slab.rs | 376 |
16 files changed, 1504 insertions, 135 deletions
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json index 11ad1ab..c04db22 100644 --- a/.cargo_vcs_info.json +++ b/.cargo_vcs_info.json @@ -1,5 +1,5 @@ { "git": { - "sha1": "e6b8676a1526f9eed997c9f4db82386ba33e007c" + "sha1": "c0bc5dc5cd55d54ae618f06cf4c7550c8bbccf76" } } diff --git a/.clippy.toml b/.clippy.toml new file mode 100644 index 0000000..f4b2f18 --- /dev/null +++ b/.clippy.toml @@ -0,0 +1 @@ +msrv = "1.27" diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml new file mode 100644 index 0000000..08eae51 --- /dev/null +++ b/.github/workflows/ci.yml @@ -0,0 +1,73 @@ +name: CI + +on: + pull_request: + branches: + - master + push: + branches: + - master + +env: + RUSTFLAGS: -Dwarnings + RUST_BACKTRACE: 1 + +jobs: + test: + strategy: + matrix: + rust: + - stable + - nightly + runs-on: ubuntu-latest + steps: + - uses: actions/checkout@v2 + - name: Install Rust + run: rustup update ${{ matrix.rust }} && rustup default ${{ matrix.rust }} + - name: Install cargo-hack + run: cargo install cargo-hack + - run: cargo hack build --feature-powerset --optional-deps --no-dev-deps + - run: cargo test --all-features + + minrust: + strategy: + matrix: + rust: + # This is the minimum supported Rust version of this crate. + - 1.27.0 + runs-on: ubuntu-latest + steps: + - uses: actions/checkout@v2 + - name: Install Rust + run: rustup update ${{ matrix.rust }} && rustup default ${{ matrix.rust }} + - run: cargo build + + no-std: + strategy: + matrix: + rust: + # This is the minimum supported Rust version for "no_std" + - 1.36.0 + runs-on: ubuntu-latest + steps: + - uses: actions/checkout@v2 + - name: Install Rust + run: rustup update ${{ matrix.rust }} && rustup default ${{ matrix.rust }} + - run: rustup target add thumbv7m-none-eabi + - run: cargo build --no-default-features --target thumbv7m-none-eabi + + clippy: + runs-on: ubuntu-latest + steps: + - uses: actions/checkout@v2 + - name: Install Rust + run: rustup update stable && rustup default stable + - run: cargo clippy --all-features + + rustfmt: + runs-on: ubuntu-latest + steps: + - uses: actions/checkout@v2 + - name: Install Rust + run: rustup update stable && rustup default stable + - run: cargo fmt --all -- --check diff --git a/.travis.yml b/.travis.yml deleted file mode 100644 index bc2955e..0000000 --- a/.travis.yml +++ /dev/null @@ -1,39 +0,0 @@ -language: rust -matrix: - include: - - rust: nightly - - rust: stable - env: RUSTFMT=1 - - # Minimum supported Rust version - - rust: 1.6.0 - script: - - cargo build - -before_script: - - if [ "$RUSTFMT" = 1 ]; then rustup component add rustfmt; fi - -script: - - if [ "$RUSTFMT" = 1 ]; then cargo fmt -- --check; fi - - cargo test - - cargo doc --no-deps - -# Deploy documentation to S3 for specific branches. At some -# point, it would be nice to also support building docs for -# a specific tag -deploy: - provider: s3 - access_key_id: AKIAIXM3KLI7WZS4ZA3Q - secret_access_key: - secure: WyYzM8PxSKC3HQ+jINE50KOu5j3taOA4chJJ9zfAhM8Eug/Z1bK8taHnm73xrCUsvh4bv1C3XWAnSTl4YO/HykYulTIVPPs6go+ssk/59PDV6dGPhheLj2tKcSrjKd4q8H668MAPiAlNt9Rvq/GkkdAW2GXG1+otPMVFBrnR+kld6WaX5EB18SjApKgl5NwSRj9wiSIPYJTBnZQhCsaM4YRMkpFbFoHUWjSjm7N9f/6A3a3jRzW7/ZtqXvMaMazMSBAlN0/LH2UMTKCuj7nywKJt1NkpEF8mA9IEUCDBCnQs+e58v6BpkDZ2nhCJ7vdm0bISuZB6jXhg+sOycZbdb7mbn5n4mPBMa1c8WnsfmVxm7bV7G3sRpcGU8HvRT35lCCuCt4bFBX1O2abuTtVqS7XgtyChBmrSG6I/z+lw+u44Dk5bYK9A2hZSOEPFr09R8f2YRe9cqAq+uI6rNPyY7DC0eATCRCX5CxjYR6DG2bDoDFfPsBlRLQJJUl/BOM5pWYdm97iaqobxlPmKaxuxTSHw1D3Z9OvuQVeB2z+4G9xMhBBTJ0N671oZhUajpBy8OW4k9c8jl+joe01W+SScfk+qPV8ivjirTPYsUYRT3gtUgO/X/XuZ+EXGcnx+Brpu6FQtW6qSKH4Q+cofM4aohoopSIAP9dZ5zpQqQTACKyE= - bucket: rust-doc - endpoint: rust-doc.s3-website-us-east-1.amazonaws.com - skip_cleanup: true - local-dir: target/doc - upload-dir: slab/${TRAVIS_BRANCH} - acl: public_read - on: - condition: $TRAVIS_RUST_VERSION == "1.3.0" && $TRAVIS_OS_NAME == "linux" - repo: carllerche/slab - branch: - - master @@ -24,6 +24,10 @@ rust_library { crate_name: "slab", srcs: ["src/lib.rs"], edition: "2015", + features: [ + "default", + "std", + ], apex_available: [ "//apex_available:platform", "com.android.virt", @@ -37,6 +41,14 @@ rust_defaults { test_suites: ["general-tests"], auto_gen_config: true, edition: "2015", + features: [ + "default", + "std", + ], + rustlibs: [ + "libserde", + "libserde_test", + ], } rust_test_host { @@ -55,18 +67,39 @@ rust_test { rust_defaults { name: "slab_defaults_slab", crate_name: "slab", - srcs: ["tests/slab.rs"], test_suites: ["general-tests"], auto_gen_config: true, edition: "2015", + features: [ + "default", + "std", + ], rustlibs: [ + "libserde", + "libserde_test", "libslab", ], } rust_test_host { + name: "slab_host_test_tests_serde", + defaults: ["slab_defaults_slab"], + srcs: ["tests/serde.rs"], + test_options: { + unit_test: true, + }, +} + +rust_test { + name: "slab_device_test_tests_serde", + defaults: ["slab_defaults_slab"], + srcs: ["tests/serde.rs"], +} + +rust_test_host { name: "slab_host_test_tests_slab", defaults: ["slab_defaults_slab"], + srcs: ["tests/slab.rs"], test_options: { unit_test: true, }, @@ -75,4 +108,14 @@ rust_test_host { rust_test { name: "slab_device_test_tests_slab", defaults: ["slab_defaults_slab"], + srcs: ["tests/slab.rs"], } + +// dependent_library ["feature_list"] +// proc-macro2-1.0.27 "default,proc-macro" +// quote-1.0.9 "default,proc-macro" +// serde-1.0.126 "default,derive,serde_derive,std" +// serde_derive-1.0.126 "default" +// serde_test-1.0.126 +// syn-1.0.72 "clone-impls,default,derive,parsing,printing,proc-macro,quote" +// unicode-xid-0.2.2 "default" diff --git a/CHANGELOG.md b/CHANGELOG.md index 9a222b4..952e7d4 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -1,3 +1,16 @@ +# 0.4.3 (February 6, 2021) + +* Add no_std support for Rust 1.36 and above (#71). +* Add `get2_mut` and `get2_unchecked_mut` methods (#65). +* Make `shrink_to_fit()` remove trailing vacant entries (#62). +* Implement `FromIterator<(usize, T)>` (#62). +* Implement `IntoIterator<Item = (usize, T)>` (#62). +* Provide `size_hint()` of the iterators (#62). +* Make all iterators reversible (#62). +* Add `key_of()` method (#61) +* Add `compact()` method (#60) +* Add support for serde (#85) + # 0.4.2 (January 11, 2019) * Add `Slab::drain` (#56). @@ -3,7 +3,7 @@ # When uploading crates to the registry Cargo will automatically # "normalize" Cargo.toml files for maximal compatibility # with all versions of Cargo and also rewrite `path` dependencies -# to registry (e.g. crates.io) dependencies +# to registry (e.g., crates.io) dependencies # # If you believe there's an error in this file please file an # issue against the rust-lang/cargo repository. If you're @@ -12,13 +12,28 @@ [package] name = "slab" -version = "0.4.2" +version = "0.4.3" authors = ["Carl Lerche <me@carllerche.com>"] description = "Pre-allocated storage for a uniform data type" -homepage = "https://github.com/carllerche/slab" -documentation = "https://docs.rs/slab/0.4.2/slab/" +homepage = "https://github.com/tokio-rs/slab" +documentation = "https://docs.rs/slab/0.4.3/slab/" readme = "README.md" -keywords = ["slab", "allocator"] -categories = ["memory-management", "data-structures"] +keywords = ["slab", "allocator", "no_std"] +categories = ["memory-management", "data-structures", "no-std"] license = "MIT" -repository = "https://github.com/carllerche/slab" +repository = "https://github.com/tokio-rs/slab" +[dependencies.serde] +version = "1.0.95" +features = ["alloc"] +optional = true +default-features = false +[dev-dependencies.serde] +version = "1" +features = ["derive"] + +[dev-dependencies.serde_test] +version = "1" + +[features] +default = ["std"] +std = [] diff --git a/Cargo.toml.orig b/Cargo.toml.orig index 88da41f..7684a02 100644 --- a/Cargo.toml.orig +++ b/Cargo.toml.orig @@ -3,20 +3,30 @@ name = "slab" # When releasing to crates.io: # - Update version number -# - lib.rs: html_root_url. # - README.md # - Update CHANGELOG.md # - Update doc URL. # - Cargo.toml # - README.md # - Create git tag -version = "0.4.2" +version = "0.4.3" license = "MIT" authors = ["Carl Lerche <me@carllerche.com>"] description = "Pre-allocated storage for a uniform data type" -documentation = "https://docs.rs/slab/0.4.2/slab/" -homepage = "https://github.com/carllerche/slab" -repository = "https://github.com/carllerche/slab" +documentation = "https://docs.rs/slab/0.4.3/slab/" +homepage = "https://github.com/tokio-rs/slab" +repository = "https://github.com/tokio-rs/slab" readme = "README.md" -keywords = ["slab", "allocator"] -categories = ["memory-management", "data-structures"] +keywords = ["slab", "allocator", "no_std"] +categories = ["memory-management", "data-structures", "no-std"] + +[features] +std = [] +default = ["std"] + +[dependencies] +serde = { version = "1.0.95", optional = true, default-features = false, features = ["alloc"] } + +[dev-dependencies] +serde = { version = "1", features = ["derive"] } +serde_test = "1" @@ -7,13 +7,13 @@ third_party { } url { type: ARCHIVE - value: "https://static.crates.io/crates/slab/slab-0.4.2.crate" + value: "https://static.crates.io/crates/slab/slab-0.4.3.crate" } - version: "0.4.2" + version: "0.4.3" license_type: NOTICE last_upgrade_date { - year: 2020 - month: 3 - day: 17 + year: 2021 + month: 6 + day: 8 } } @@ -2,10 +2,15 @@ Pre-allocated storage for a uniform data type. -[![Crates.io](https://img.shields.io/crates/v/slab.svg?maxAge=2592000)](https://crates.io/crates/slab) -[![Build Status](https://travis-ci.org/carllerche/slab.svg?branch=master)](https://travis-ci.org/carllerche/slab) +[![Crates.io][crates-badge]][crates-url] +[![Build Status][ci-badge]][ci-url] -[Documentation](https://docs.rs/slab/0.4.2/slab/) +[crates-badge]: https://img.shields.io/crates/v/slab +[crates-url]: https://crates.io/crates/slab +[ci-badge]: https://img.shields.io/github/workflow/status/tokio-rs/slab/CI/master +[ci-url]: https://github.com/tokio-rs/slab/actions + +[Documentation](https://docs.rs/slab/0.4.3/slab/) ## Usage @@ -13,7 +18,7 @@ To use `slab`, first add this to your `Cargo.toml`: ```toml [dependencies] -slab = "0.4.2" +slab = "0.4.3" ``` Next, add this to your crate: diff --git a/TEST_MAPPING b/TEST_MAPPING index 3c4c00c..fd129ed 100644 --- a/TEST_MAPPING +++ b/TEST_MAPPING @@ -1,14 +1,266 @@ -// Generated by cargo2android.py for tests in Android.bp +// Generated by update_crate_tests.py for tests that depend on this crate. { "presubmit": [ { + "name": "ZipFuseTest" + }, + { + "name": "anyhow_device_test_src_lib" + }, + { + "name": "anyhow_device_test_tests_test_autotrait" + }, + { + "name": "anyhow_device_test_tests_test_boxed" + }, + { + "name": "anyhow_device_test_tests_test_chain" + }, + { + "name": "anyhow_device_test_tests_test_context" + }, + { + "name": "anyhow_device_test_tests_test_convert" + }, + { + "name": "anyhow_device_test_tests_test_downcast" + }, + { + "name": "anyhow_device_test_tests_test_ffi" + }, + { + "name": "anyhow_device_test_tests_test_fmt" + }, + { + "name": "anyhow_device_test_tests_test_macros" + }, + { + "name": "anyhow_device_test_tests_test_repr" + }, + { + "name": "anyhow_device_test_tests_test_source" + }, + { + "name": "authfs_device_test_src_lib" + }, + { + "name": "futures-util_device_test_src_lib" + }, + { "name": "slab_device_test_src_lib" }, { + "name": "slab_device_test_tests_serde" + }, + { "name": "slab_device_test_tests_slab" }, { - "name": "futures-util_device_test_src_lib" + "name": "tokio-test_device_test_src_lib" + }, + { + "name": "tokio-test_device_test_tests_block_on" + }, + { + "name": "tokio-test_device_test_tests_io" + }, + { + "name": "tokio-test_device_test_tests_macros" + }, + { + "name": "tokio_device_test_tests__require_full" + }, + { + "name": "tokio_device_test_tests_buffered" + }, + { + "name": "tokio_device_test_tests_io_async_fd" + }, + { + "name": "tokio_device_test_tests_io_async_read" + }, + { + "name": "tokio_device_test_tests_io_chain" + }, + { + "name": "tokio_device_test_tests_io_copy" + }, + { + "name": "tokio_device_test_tests_io_copy_bidirectional" + }, + { + "name": "tokio_device_test_tests_io_driver" + }, + { + "name": "tokio_device_test_tests_io_driver_drop" + }, + { + "name": "tokio_device_test_tests_io_lines" + }, + { + "name": "tokio_device_test_tests_io_mem_stream" + }, + { + "name": "tokio_device_test_tests_io_read" + }, + { + "name": "tokio_device_test_tests_io_read_buf" + }, + { + "name": "tokio_device_test_tests_io_read_exact" + }, + { + "name": "tokio_device_test_tests_io_read_line" + }, + { + "name": "tokio_device_test_tests_io_read_to_end" + }, + { + "name": "tokio_device_test_tests_io_read_to_string" + }, + { + "name": "tokio_device_test_tests_io_read_until" + }, + { + "name": "tokio_device_test_tests_io_split" + }, + { + "name": "tokio_device_test_tests_io_take" + }, + { + "name": "tokio_device_test_tests_io_write" + }, + { + "name": "tokio_device_test_tests_io_write_all" + }, + { + "name": "tokio_device_test_tests_io_write_buf" + }, + { + "name": "tokio_device_test_tests_io_write_int" + }, + { + "name": "tokio_device_test_tests_macros_join" + }, + { + "name": "tokio_device_test_tests_macros_pin" + }, + { + "name": "tokio_device_test_tests_macros_select" + }, + { + "name": "tokio_device_test_tests_macros_test" + }, + { + "name": "tokio_device_test_tests_macros_try_join" + }, + { + "name": "tokio_device_test_tests_net_bind_resource" + }, + { + "name": "tokio_device_test_tests_net_lookup_host" + }, + { + "name": "tokio_device_test_tests_no_rt" + }, + { + "name": "tokio_device_test_tests_process_kill_on_drop" + }, + { + "name": "tokio_device_test_tests_rt_basic" + }, + { + "name": "tokio_device_test_tests_rt_common" + }, + { + "name": "tokio_device_test_tests_rt_threaded" + }, + { + "name": "tokio_device_test_tests_sync_barrier" + }, + { + "name": "tokio_device_test_tests_sync_broadcast" + }, + { + "name": "tokio_device_test_tests_sync_errors" + }, + { + "name": "tokio_device_test_tests_sync_mpsc" + }, + { + "name": "tokio_device_test_tests_sync_mutex" + }, + { + "name": "tokio_device_test_tests_sync_mutex_owned" + }, + { + "name": "tokio_device_test_tests_sync_notify" + }, + { + "name": "tokio_device_test_tests_sync_oneshot" + }, + { + "name": "tokio_device_test_tests_sync_rwlock" + }, + { + "name": "tokio_device_test_tests_sync_semaphore" + }, + { + "name": "tokio_device_test_tests_sync_semaphore_owned" + }, + { + "name": "tokio_device_test_tests_sync_watch" + }, + { + "name": "tokio_device_test_tests_task_abort" + }, + { + "name": "tokio_device_test_tests_task_blocking" + }, + { + "name": "tokio_device_test_tests_task_local" + }, + { + "name": "tokio_device_test_tests_task_local_set" + }, + { + "name": "tokio_device_test_tests_tcp_accept" + }, + { + "name": "tokio_device_test_tests_tcp_connect" + }, + { + "name": "tokio_device_test_tests_tcp_echo" + }, + { + "name": "tokio_device_test_tests_tcp_into_split" + }, + { + "name": "tokio_device_test_tests_tcp_into_std" + }, + { + "name": "tokio_device_test_tests_tcp_peek" + }, + { + "name": "tokio_device_test_tests_tcp_shutdown" + }, + { + "name": "tokio_device_test_tests_tcp_socket" + }, + { + "name": "tokio_device_test_tests_tcp_split" + }, + { + "name": "tokio_device_test_tests_time_rt" + }, + { + "name": "tokio_device_test_tests_udp" + }, + { + "name": "tokio_device_test_tests_uds_cred" + }, + { + "name": "tokio_device_test_tests_uds_split" } ] } diff --git a/patches/disable_panic_tests_on_android.patch b/patches/disable_panic_tests_on_android.patch new file mode 100644 index 0000000..4333952 --- /dev/null +++ b/patches/disable_panic_tests_on_android.patch @@ -0,0 +1,13 @@ +diff --git a/tests/slab.rs b/tests/slab.rs +index c1570fa..8ba3064 100644 +--- a/tests/slab.rs ++++ b/tests/slab.rs +@@ -580,6 +580,8 @@ fn compact_doesnt_move_if_closure_errors() { + } + + #[test] ++// Android aborts on panic and this test relies on stack unwinding. ++#[cfg(not(target_os = "android"))] + fn compact_handles_closure_panic() { + let mut slab = Slab::new(); + for i in 0..10 { @@ -1,6 +1,6 @@ -#![doc(html_root_url = "https://docs.rs/slab/0.4.2")] -#![deny(warnings, missing_docs, missing_debug_implementations)] -#![cfg_attr(test, deny(warnings, unreachable_pub))] +#![warn(missing_docs, missing_debug_implementations)] +#![cfg_attr(test, warn(unreachable_pub))] +#![cfg_attr(not(feature = "std"), no_std)] //! Pre-allocated storage for a uniform data type. //! @@ -102,10 +102,26 @@ //! //! [`Slab::with_capacity`]: struct.Slab.html#with_capacity -use std::iter::IntoIterator; -use std::ops; +#[cfg(not(feature = "std"))] +extern crate alloc; +#[cfg(feature = "std")] +extern crate core; + +#[cfg(feature = "serde")] +mod serde; + +#[cfg(not(feature = "std"))] +use alloc::vec::Vec; + +#[cfg(not(feature = "std"))] +use alloc::vec; + +use core::iter::FromIterator; + +use core::{fmt, mem, ops, slice}; + +#[cfg(feature = "std")] use std::vec; -use std::{fmt, mem}; /// Pre-allocated storage for a uniform data type /// @@ -159,15 +175,21 @@ pub struct VacantEntry<'a, T: 'a> { key: usize, } +/// A consuming iterator over the values stored in a `Slab` +pub struct IntoIter<T> { + entries: vec::IntoIter<Entry<T>>, + curr: usize, +} + /// An iterator over the values stored in the `Slab` pub struct Iter<'a, T: 'a> { - entries: std::slice::Iter<'a, Entry<T>>, + entries: slice::Iter<'a, Entry<T>>, curr: usize, } /// A mutable iterator over the values stored in the `Slab` pub struct IterMut<'a, T: 'a> { - entries: std::slice::IterMut<'a, Entry<T>>, + entries: slice::IterMut<'a, Entry<T>>, curr: usize, } @@ -274,7 +296,7 @@ impl<T> Slab<T> { if self.capacity() - self.len >= additional { return; } - let need_add = self.len + additional - self.entries.len(); + let need_add = additional - (self.entries.len() - self.len); self.entries.reserve(need_add); } @@ -308,16 +330,19 @@ impl<T> Slab<T> { if self.capacity() - self.len >= additional { return; } - let need_add = self.len + additional - self.entries.len(); + let need_add = additional - (self.entries.len() - self.len); self.entries.reserve_exact(need_add); } - /// Shrink the capacity of the slab as much as possible. + /// Shrink the capacity of the slab as much as possible without invalidating keys. /// - /// It will drop down as close as possible to the length but the allocator - /// may still inform the vector that there is space for a few more elements. - /// Also, since values are not moved, the slab cannot shrink past any stored - /// values. + /// Because values cannot be moved to a different index, the slab cannot + /// shrink past any stored values. + /// It will drop down as close as possible to the length but the allocator may + /// still inform the underlying vector that there is space for a few more elements. + /// + /// This function can take O(n) time even when the capacity cannot be reduced + /// or the allocation is shrunk in place. Repeated calls run in O(1) though. /// /// # Examples /// @@ -329,33 +354,171 @@ impl<T> Slab<T> { /// slab.insert(i); /// } /// - /// assert_eq!(slab.capacity(), 10); /// slab.shrink_to_fit(); - /// assert!(slab.capacity() >= 3); + /// assert!(slab.capacity() >= 3 && slab.capacity() < 10); /// ``` /// - /// In this case, even though two values are removed, the slab cannot shrink - /// past the last value. + /// The slab cannot shrink past the last present value even if previous + /// values are removed: /// /// ``` /// # use slab::*; /// let mut slab = Slab::with_capacity(10); /// - /// for i in 0..3 { + /// for i in 0..4 { /// slab.insert(i); /// } /// /// slab.remove(0); - /// slab.remove(1); + /// slab.remove(3); /// - /// assert_eq!(slab.capacity(), 10); /// slab.shrink_to_fit(); - /// assert!(slab.capacity() >= 3); + /// assert!(slab.capacity() >= 3 && slab.capacity() < 10); /// ``` pub fn shrink_to_fit(&mut self) { + // Remove all vacant entries after the last occupied one, so that + // the capacity can be reduced to what is actually needed. + // If the slab is empty the vector can simply be cleared, but that + // optimization would not affect time complexity when T: Drop. + let len_before = self.entries.len(); + while let Some(&Entry::Vacant(_)) = self.entries.last() { + self.entries.pop(); + } + + // Removing entries breaks the list of vacant entries, + // so it must be repaired + if self.entries.len() != len_before { + // Some vacant entries were removed, so the list now likely¹ + // either contains references to the removed entries, or has an + // invalid end marker. Fix this by recreating the list. + self.recreate_vacant_list(); + // ¹: If the removed entries formed the tail of the list, with the + // most recently popped entry being the head of them, (so that its + // index is now the end marker) the list is still valid. + // Checking for that unlikely scenario of this infrequently called + // is not worth the code complexity. + } + self.entries.shrink_to_fit(); } + /// Iterate through all entries to recreate and repair the vacant list. + /// self.len must be correct and is not modified. + fn recreate_vacant_list(&mut self) { + self.next = self.entries.len(); + // We can stop once we've found all vacant entries + let mut remaining_vacant = self.entries.len() - self.len; + // Iterate in reverse order so that lower keys are at the start of + // the vacant list. This way future shrinks are more likely to be + // able to remove vacant entries. + for (i, entry) in self.entries.iter_mut().enumerate().rev() { + if remaining_vacant == 0 { + break; + } + if let Entry::Vacant(ref mut next) = *entry { + *next = self.next; + self.next = i; + remaining_vacant -= 1; + } + } + } + + /// Reduce the capacity as much as possible, changing the key for elements when necessary. + /// + /// To allow updating references to the elements which must be moved to a new key, + /// this function takes a closure which is called before moving each element. + /// The second and third parameters to the closure are the current key and + /// new key respectively. + /// In case changing the key for one element turns out not to be possible, + /// the move can be cancelled by returning `false` from the closure. + /// In that case no further attempts at relocating elements is made. + /// If the closure unwinds, the slab will be left in a consistent state, + /// but the value that the closure panicked on might be removed. + /// + /// # Examples + /// + /// ``` + /// # use slab::*; + /// + /// let mut slab = Slab::with_capacity(10); + /// let a = slab.insert('a'); + /// slab.insert('b'); + /// slab.insert('c'); + /// slab.remove(a); + /// slab.compact(|&mut value, from, to| { + /// assert_eq!((value, from, to), ('c', 2, 0)); + /// true + /// }); + /// assert!(slab.capacity() >= 2 && slab.capacity() < 10); + /// ``` + /// + /// The value is not moved when the closure returns `Err`: + /// + /// ``` + /// # use slab::*; + /// + /// let mut slab = Slab::with_capacity(100); + /// let a = slab.insert('a'); + /// let b = slab.insert('b'); + /// slab.remove(a); + /// slab.compact(|&mut value, from, to| false); + /// assert_eq!(slab.iter().next(), Some((b, &'b'))); + /// ``` + pub fn compact<F>(&mut self, mut rekey: F) + where + F: FnMut(&mut T, usize, usize) -> bool, + { + // If the closure unwinds, we need to restore a valid list of vacant entries + struct CleanupGuard<'a, T: 'a> { + slab: &'a mut Slab<T>, + decrement: bool, + } + impl<'a, T: 'a> Drop for CleanupGuard<'a, T> { + fn drop(&mut self) { + if self.decrement { + // Value was popped and not pushed back on + self.slab.len -= 1; + } + self.slab.recreate_vacant_list(); + } + } + let mut guard = CleanupGuard { + slab: self, + decrement: true, + }; + + let mut occupied_until = 0; + // While there are vacant entries + while guard.slab.entries.len() > guard.slab.len { + // Find a value that needs to be moved, + // by popping entries until we find an occopied one. + // (entries cannot be empty because 0 is not greater than anything) + if let Some(Entry::Occupied(mut value)) = guard.slab.entries.pop() { + // Found one, now find a vacant entry to move it to + while let Some(&Entry::Occupied(_)) = guard.slab.entries.get(occupied_until) { + occupied_until += 1; + } + // Let the caller try to update references to the key + if !rekey(&mut value, guard.slab.entries.len(), occupied_until) { + // Changing the key failed, so push the entry back on at its old index. + guard.slab.entries.push(Entry::Occupied(value)); + guard.decrement = false; + guard.slab.entries.shrink_to_fit(); + return; + // Guard drop handles cleanup + } + // Put the value in its new spot + guard.slab.entries[occupied_until] = Entry::Occupied(value); + // ... and mark it as occupied (this is optional) + occupied_until += 1; + } + } + guard.slab.next = guard.slab.len; + guard.slab.entries.shrink_to_fit(); + // Normal cleanup is not necessary + mem::forget(guard); + } + /// Clear the slab of all values. /// /// # Examples @@ -520,11 +683,62 @@ impl<T> Slab<T> { } } + /// Return two mutable references to the values associated with the two + /// given keys simultaneously. + /// + /// If any one of the given keys is not associated with a value, then `None` + /// is returned. + /// + /// This function can be used to get two mutable references out of one slab, + /// so that you can manipulate both of them at the same time, eg. swap them. + /// + /// # Examples + /// + /// ``` + /// # use slab::*; + /// use std::mem; + /// + /// let mut slab = Slab::new(); + /// let key1 = slab.insert(1); + /// let key2 = slab.insert(2); + /// let (value1, value2) = slab.get2_mut(key1, key2).unwrap(); + /// mem::swap(value1, value2); + /// assert_eq!(slab[key1], 2); + /// assert_eq!(slab[key2], 1); + /// ``` + pub fn get2_mut(&mut self, key1: usize, key2: usize) -> Option<(&mut T, &mut T)> { + assert!(key1 != key2); + + let (entry1, entry2); + + if key1 > key2 { + let (slice1, slice2) = self.entries.split_at_mut(key1); + entry1 = slice2.get_mut(0); + entry2 = slice1.get_mut(key2); + } else { + let (slice1, slice2) = self.entries.split_at_mut(key2); + entry1 = slice1.get_mut(key1); + entry2 = slice2.get_mut(0); + } + + match (entry1, entry2) { + ( + Some(&mut Entry::Occupied(ref mut val1)), + Some(&mut Entry::Occupied(ref mut val2)), + ) => Some((val1, val2)), + _ => None, + } + } + /// Return a reference to the value associated with the given key without /// performing bounds checking. /// /// This function should be used with care. /// + /// # Safety + /// + /// The key must be within bounds. + /// /// # Examples /// /// ``` @@ -548,6 +762,10 @@ impl<T> Slab<T> { /// /// This function should be used with care. /// + /// # Safety + /// + /// The key must be within bounds. + /// /// # Examples /// /// ``` @@ -569,6 +787,93 @@ impl<T> Slab<T> { } } + /// Return two mutable references to the values associated with the two + /// given keys simultaneously without performing bounds checking and safety + /// condition checking. + /// + /// This function should be used with care. + /// + /// # Safety + /// + /// - Both keys must be within bounds. + /// - The condition `key1 != key2` must hold. + /// + /// # Examples + /// + /// ``` + /// # use slab::*; + /// use std::mem; + /// + /// let mut slab = Slab::new(); + /// let key1 = slab.insert(1); + /// let key2 = slab.insert(2); + /// let (value1, value2) = unsafe { slab.get2_unchecked_mut(key1, key2) }; + /// mem::swap(value1, value2); + /// assert_eq!(slab[key1], 2); + /// assert_eq!(slab[key2], 1); + /// ``` + pub unsafe fn get2_unchecked_mut(&mut self, key1: usize, key2: usize) -> (&mut T, &mut T) { + let ptr1 = self.entries.get_unchecked_mut(key1) as *mut Entry<T>; + let ptr2 = self.entries.get_unchecked_mut(key2) as *mut Entry<T>; + match (&mut *ptr1, &mut *ptr2) { + (&mut Entry::Occupied(ref mut val1), &mut Entry::Occupied(ref mut val2)) => { + (val1, val2) + } + _ => unreachable!(), + } + } + + /// Get the key for an element in the slab. + /// + /// The reference must point to an element owned by the slab. + /// Otherwise this function will panic. + /// This is a constant-time operation because the key can be calculated + /// from the reference with pointer arithmetic. + /// + /// # Panics + /// + /// This function will panic if the reference does not point to an element + /// of the slab. + /// + /// # Examples + /// + /// ``` + /// # use slab::*; + /// + /// let mut slab = Slab::new(); + /// let key = slab.insert(String::from("foo")); + /// let value = &slab[key]; + /// assert_eq!(slab.key_of(value), key); + /// ``` + /// + /// Values are not compared, so passing a reference to a different locaton + /// will result in a panic: + /// + /// ```should_panic + /// # use slab::*; + /// + /// let mut slab = Slab::new(); + /// let key = slab.insert(0); + /// let bad = &0; + /// slab.key_of(bad); // this will panic + /// unreachable!(); + /// ``` + pub fn key_of(&self, present_element: &T) -> usize { + let element_ptr = present_element as *const T as usize; + let base_ptr = self.entries.as_ptr() as usize; + // Use wrapping subtraction in case the reference is bad + let byte_offset = element_ptr.wrapping_sub(base_ptr); + // The division rounds away any offset of T inside Entry + // The size of Entry<T> is never zero even if T is due to Vacant(usize) + let key = byte_offset / mem::size_of::<Entry<T>>(); + // Prevent returning unspecified (but out of bounds) values + if key >= self.entries.len() { + panic!("The reference points to a value outside this slab"); + } + // The reference cannot point to a vacant entry, because then it would not be valid + key + } + /// Insert a value in the slab, returning key assigned to the value. /// /// The returned key can later be used to retrieve or remove the value using indexed @@ -632,14 +937,11 @@ impl<T> Slab<T> { self.entries.push(Entry::Occupied(val)); self.next = key + 1; } else { - let prev = mem::replace(&mut self.entries[key], Entry::Occupied(val)); - - match prev { - Entry::Vacant(next) => { - self.next = next; - } + self.next = match self.entries.get(key) { + Some(&Entry::Vacant(next)) => next, _ => unreachable!(), - } + }; + self.entries[key] = Entry::Occupied(val); } } @@ -664,21 +966,23 @@ impl<T> Slab<T> { /// assert!(!slab.contains(hello)); /// ``` pub fn remove(&mut self, key: usize) -> T { - // Swap the entry at the provided value - let prev = mem::replace(&mut self.entries[key], Entry::Vacant(self.next)); - - match prev { - Entry::Occupied(val) => { - self.len -= 1; - self.next = key; - val - } - _ => { - // Woops, the entry is actually vacant, restore the state - self.entries[key] = prev; - panic!("invalid key"); + if let Some(entry) = self.entries.get_mut(key) { + // Swap the entry at the provided value + let prev = mem::replace(entry, Entry::Vacant(self.next)); + + match prev { + Entry::Occupied(val) => { + self.len -= 1; + self.next = key; + return val; + } + _ => { + // Woops, the entry is actually vacant, restore the state + *entry = prev; + } } } + panic!("invalid key"); } /// Return `true` if a value is associated with the given key. @@ -697,13 +1001,10 @@ impl<T> Slab<T> { /// assert!(!slab.contains(hello)); /// ``` pub fn contains(&self, key: usize) -> bool { - self.entries - .get(key) - .map(|e| match *e { - Entry::Occupied(_) => true, - _ => false, - }) - .unwrap_or(false) + match self.entries.get(key) { + Some(&Entry::Occupied(_)) => true, + _ => false, + } } /// Retain only the elements specified by the predicate. @@ -784,8 +1085,8 @@ impl<T> ops::Index<usize> for Slab<T> { type Output = T; fn index(&self, key: usize) -> &T { - match self.entries[key] { - Entry::Occupied(ref v) => v, + match self.entries.get(key) { + Some(&Entry::Occupied(ref v)) => v, _ => panic!("invalid key"), } } @@ -793,13 +1094,25 @@ impl<T> ops::Index<usize> for Slab<T> { impl<T> ops::IndexMut<usize> for Slab<T> { fn index_mut(&mut self, key: usize) -> &mut T { - match self.entries[key] { - Entry::Occupied(ref mut v) => v, + match self.entries.get_mut(key) { + Some(&mut Entry::Occupied(ref mut v)) => v, _ => panic!("invalid key"), } } } +impl<T> IntoIterator for Slab<T> { + type Item = (usize, T); + type IntoIter = IntoIter<T>; + + fn into_iter(self) -> IntoIter<T> { + IntoIter { + entries: self.entries.into_iter(), + curr: 0, + } + } +} + impl<'a, T> IntoIterator for &'a Slab<T> { type Item = (usize, &'a T); type IntoIter = Iter<'a, T>; @@ -818,17 +1131,98 @@ impl<'a, T> IntoIterator for &'a mut Slab<T> { } } +/// Create a slab from an iterator of key-value pairs. +/// +/// If the iterator produces duplicate keys, the previous value is replaced with the later one. +/// The keys does not need to be sorted beforehand, and this function always +/// takes O(n) time. +/// Note that the returned slab will use space proportional to the largest key, +/// so don't use `Slab` with untrusted keys. +/// +/// # Examples +/// +/// ``` +/// # use slab::*; +/// +/// let vec = vec![(2,'a'), (6,'b'), (7,'c')]; +/// let slab = vec.into_iter().collect::<Slab<char>>(); +/// assert_eq!(slab.len(), 3); +/// assert!(slab.capacity() >= 8); +/// assert_eq!(slab[2], 'a'); +/// ``` +/// +/// With duplicate and unsorted keys: +/// +/// ``` +/// # use slab::*; +/// +/// let vec = vec![(20,'a'), (10,'b'), (11,'c'), (10,'d')]; +/// let slab = vec.into_iter().collect::<Slab<char>>(); +/// assert_eq!(slab.len(), 3); +/// assert_eq!(slab[10], 'd'); +/// ``` +impl<T> FromIterator<(usize, T)> for Slab<T> { + fn from_iter<I>(iterable: I) -> Self + where + I: IntoIterator<Item = (usize, T)>, + { + let iterator = iterable.into_iter(); + let mut slab = Self::with_capacity(iterator.size_hint().0); + + let mut vacant_list_broken = false; + for (key, value) in iterator { + if key < slab.entries.len() { + // iterator is not sorted, might need to recreate vacant list + if let Entry::Vacant(_) = slab.entries[key] { + vacant_list_broken = true; + slab.len += 1; + } + // if an element with this key already exists, replace it. + // This is consisent with HashMap and BtreeMap + slab.entries[key] = Entry::Occupied(value); + } else { + // insert holes as necessary + while slab.entries.len() < key { + // add the entry to the start of the vacant list + let next = slab.next; + slab.next = slab.entries.len(); + slab.entries.push(Entry::Vacant(next)); + } + slab.entries.push(Entry::Occupied(value)); + slab.len += 1; + } + } + if slab.len == slab.entries.len() { + // no vacant enries, so next might not have been updated + slab.next = slab.entries.len(); + } else if vacant_list_broken { + slab.recreate_vacant_list(); + } + slab + } +} + impl<T> fmt::Debug for Slab<T> where T: fmt::Debug, { fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { - write!( - fmt, - "Slab {{ len: {}, cap: {} }}", - self.len, - self.capacity() - ) + fmt.debug_struct("Slab") + .field("len", &self.len) + .field("cap", &self.capacity()) + .finish() + } +} + +impl<T> fmt::Debug for IntoIter<T> +where + T: fmt::Debug, +{ + fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + fmt.debug_struct("Iter") + .field("curr", &self.curr) + .field("remaining", &self.entries.len()) + .finish() } } @@ -890,8 +1284,8 @@ impl<'a, T> VacantEntry<'a, T> { pub fn insert(self, val: T) -> &'a mut T { self.slab.insert_at(self.key, val); - match self.slab.entries[self.key] { - Entry::Occupied(ref mut v) => v, + match self.slab.entries.get_mut(self.key) { + Some(&mut Entry::Occupied(ref mut v)) => v, _ => unreachable!(), } } @@ -922,6 +1316,42 @@ impl<'a, T> VacantEntry<'a, T> { } } +// ===== IntoIter ===== + +impl<T> Iterator for IntoIter<T> { + type Item = (usize, T); + + fn next(&mut self) -> Option<(usize, T)> { + while let Some(entry) = self.entries.next() { + let curr = self.curr; + self.curr += 1; + + if let Entry::Occupied(v) = entry { + return Some((curr, v)); + } + } + + None + } + + fn size_hint(&self) -> (usize, Option<usize>) { + (0, Some(self.entries.len())) + } +} + +impl<T> DoubleEndedIterator for IntoIter<T> { + fn next_back(&mut self) -> Option<(usize, T)> { + while let Some(entry) = self.entries.next_back() { + if let Entry::Occupied(v) = entry { + let key = self.curr + self.entries.len(); + return Some((key, v)); + } + } + + None + } +} + // ===== Iter ===== impl<'a, T> Iterator for Iter<'a, T> { @@ -939,6 +1369,23 @@ impl<'a, T> Iterator for Iter<'a, T> { None } + + fn size_hint(&self) -> (usize, Option<usize>) { + (0, Some(self.entries.len())) + } +} + +impl<'a, T> DoubleEndedIterator for Iter<'a, T> { + fn next_back(&mut self) -> Option<(usize, &'a T)> { + while let Some(entry) = self.entries.next_back() { + if let Entry::Occupied(ref v) = *entry { + let key = self.curr + self.entries.len(); + return Some((key, v)); + } + } + + None + } } // ===== IterMut ===== @@ -958,6 +1405,23 @@ impl<'a, T> Iterator for IterMut<'a, T> { None } + + fn size_hint(&self) -> (usize, Option<usize>) { + (0, Some(self.entries.len())) + } +} + +impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { + fn next_back(&mut self) -> Option<(usize, &'a mut T)> { + while let Some(entry) = self.entries.next_back() { + if let Entry::Occupied(ref mut v) = *entry { + let key = self.curr + self.entries.len(); + return Some((key, v)); + } + } + + None + } } // ===== Drain ===== @@ -974,4 +1438,20 @@ impl<'a, T> Iterator for Drain<'a, T> { None } + + fn size_hint(&self) -> (usize, Option<usize>) { + (0, Some(self.0.len())) + } +} + +impl<'a, T> DoubleEndedIterator for Drain<'a, T> { + fn next_back(&mut self) -> Option<T> { + while let Some(entry) = self.0.next_back() { + if let Entry::Occupied(v) = entry { + return Some(v); + } + } + + None + } } diff --git a/src/serde.rs b/src/serde.rs new file mode 100644 index 0000000..4fb18e9 --- /dev/null +++ b/src/serde.rs @@ -0,0 +1,91 @@ +extern crate serde; + +use core::fmt; +use core::marker::PhantomData; + +use self::serde::de::{Deserialize, Deserializer, MapAccess, Visitor}; +use self::serde::ser::{Serialize, SerializeMap, Serializer}; + +use super::{Entry, Slab}; + +impl<T> Serialize for Slab<T> +where + T: Serialize, +{ + fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> + where + S: Serializer, + { + let mut map_serializer = serializer.serialize_map(Some(self.len()))?; + for (key, value) in self { + map_serializer.serialize_key(&key)?; + map_serializer.serialize_value(value)?; + } + map_serializer.end() + } +} + +struct SlabVisitor<T>(PhantomData<T>); + +impl<'de, T> Visitor<'de> for SlabVisitor<T> +where + T: Deserialize<'de>, +{ + type Value = Slab<T>; + + fn expecting(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + write!(fmt, "a map") + } + + fn visit_map<A>(self, mut map: A) -> Result<Self::Value, A::Error> + where + A: MapAccess<'de>, + { + let mut slab = Slab::with_capacity(map.size_hint().unwrap_or(0)); + + // same as FromIterator impl + let mut vacant_list_broken = false; + while let Some((key, value)) = map.next_entry()? { + if key < slab.entries.len() { + // iterator is not sorted, might need to recreate vacant list + if let Entry::Vacant(_) = slab.entries[key] { + vacant_list_broken = true; + slab.len += 1; + } + // if an element with this key already exists, replace it. + // This is consisent with HashMap and BtreeMap + slab.entries[key] = Entry::Occupied(value); + } else { + // insert holes as necessary + while slab.entries.len() < key { + // add the entry to the start of the vacant list + let next = slab.next; + slab.next = slab.entries.len(); + slab.entries.push(Entry::Vacant(next)); + } + slab.entries.push(Entry::Occupied(value)); + slab.len += 1; + } + } + if slab.len == slab.entries.len() { + // no vacant enries, so next might not have been updated + slab.next = slab.entries.len(); + } else if vacant_list_broken { + slab.recreate_vacant_list(); + } + + Ok(slab) + } +} + +impl<'de, T> Deserialize<'de> for Slab<T> +where + T: Deserialize<'de>, +{ + fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> + where + D: Deserializer<'de>, + { + deserializer.deserialize_map(SlabVisitor(PhantomData)) + } +} diff --git a/tests/serde.rs b/tests/serde.rs new file mode 100644 index 0000000..d8eb682 --- /dev/null +++ b/tests/serde.rs @@ -0,0 +1,50 @@ +#![cfg(feature = "serde")] + +extern crate serde; +extern crate serde_test; +extern crate slab; + +use serde::{Deserialize, Serialize}; +use serde_test::{assert_tokens, Token}; +use slab::Slab; + +#[derive(Debug, Serialize, Deserialize)] +#[serde(transparent)] +struct SlabPartialEq<T>(Slab<T>); + +impl<T: PartialEq> PartialEq for SlabPartialEq<T> { + fn eq(&self, other: &Self) -> bool { + self.0 + .iter() + .zip(other.0.iter()) + .all(|(this, other)| this.0 == other.0 && this.1 == other.1) + } +} + +#[test] +fn test_serde_empty() { + let slab = Slab::<usize>::new(); + assert_tokens( + &SlabPartialEq(slab), + &[Token::Map { len: Some(0) }, Token::MapEnd], + ); +} + +#[test] +fn test_serde() { + let vec = vec![(1, 2), (3, 4), (5, 6)]; + let slab: Slab<_> = vec.iter().cloned().collect(); + assert_tokens( + &SlabPartialEq(slab), + &[ + Token::Map { len: Some(3) }, + Token::U64(1), + Token::I32(2), + Token::U64(3), + Token::I32(4), + Token::U64(5), + Token::I32(6), + Token::MapEnd, + ], + ); +} diff --git a/tests/slab.rs b/tests/slab.rs index 5203c95..8ba3064 100644 --- a/tests/slab.rs +++ b/tests/slab.rs @@ -2,6 +2,8 @@ extern crate slab; use slab::*; +use std::panic::{catch_unwind, resume_unwind, AssertUnwindSafe}; + #[test] fn insert_get_remove_one() { let mut slab = Slab::new(); @@ -82,14 +84,21 @@ fn get_vacant_entry_without_using() { } #[test] -#[should_panic] +#[should_panic(expected = "invalid key")] fn invalid_get_panics() { let slab = Slab::<usize>::with_capacity(1); - slab[0]; + let _ = &slab[0]; } #[test] -#[should_panic] +#[should_panic(expected = "invalid key")] +fn invalid_get_mut_panics() { + let mut slab = Slab::<usize>::new(); + let _ = &mut slab[0]; +} + +#[test] +#[should_panic(expected = "invalid key")] fn double_remove_panics() { let mut slab = Slab::<usize>::with_capacity(1); let key = slab.insert(123); @@ -98,7 +107,7 @@ fn double_remove_panics() { } #[test] -#[should_panic] +#[should_panic(expected = "invalid key")] fn invalid_remove_panics() { let mut slab = Slab::<usize>::with_capacity(1); slab.remove(0); @@ -117,6 +126,34 @@ fn slab_get_mut() { } #[test] +fn key_of_tagged() { + let mut slab = Slab::new(); + slab.insert(0); + assert_eq!(slab.key_of(&slab[0]), 0); +} + +#[test] +fn key_of_layout_optimizable() { + // Entry<&str> doesn't need a discriminant tag because it can use the + // nonzero-ness of ptr and store Vacant's next at the same offset as len + let mut slab = Slab::new(); + slab.insert("foo"); + slab.insert("bar"); + let third = slab.insert("baz"); + slab.insert("quux"); + assert_eq!(slab.key_of(&slab[third]), third); +} + +#[test] +fn key_of_zst() { + let mut slab = Slab::new(); + slab.insert(()); + let second = slab.insert(()); + slab.insert(()); + assert_eq!(slab.key_of(&slab[second]), second); +} + +#[test] fn reserve_does_not_allocate_if_available() { let mut slab = Slab::with_capacity(10); let mut keys = vec![]; @@ -150,11 +187,27 @@ fn reserve_exact_does_not_allocate_if_available() { assert!(slab.capacity() - slab.len() == 8); - slab.reserve(8); + slab.reserve_exact(8); assert_eq!(10, slab.capacity()); } #[test] +#[should_panic(expected = "capacity overflow")] +fn reserve_does_panic_with_capacity_overflow() { + let mut slab = Slab::with_capacity(10); + slab.insert(true); + slab.reserve(std::usize::MAX); +} + +#[test] +#[should_panic(expected = "capacity overflow")] +fn reserve_exact_does_panic_with_capacity_overflow() { + let mut slab = Slab::with_capacity(10); + slab.insert(true); + slab.reserve_exact(std::usize::MAX); +} + +#[test] fn retain() { let mut slab = Slab::with_capacity(2); @@ -185,6 +238,43 @@ fn retain() { } #[test] +fn into_iter() { + let mut slab = Slab::new(); + + for i in 0..8 { + slab.insert(i); + } + slab.remove(0); + slab.remove(4); + slab.remove(5); + slab.remove(7); + + let vals: Vec<_> = slab + .into_iter() + .inspect(|&(key, val)| assert_eq!(key, val)) + .map(|(_, val)| val) + .collect(); + assert_eq!(vals, vec![1, 2, 3, 6]); +} + +#[test] +fn into_iter_rev() { + let mut slab = Slab::new(); + + for i in 0..4 { + slab.insert(i); + } + + let mut iter = slab.into_iter(); + assert_eq!(iter.next_back(), Some((3, 3))); + assert_eq!(iter.next_back(), Some((2, 2))); + assert_eq!(iter.next(), Some((0, 0))); + assert_eq!(iter.next_back(), Some((1, 1))); + assert_eq!(iter.next_back(), None); + assert_eq!(iter.next(), None); +} + +#[test] fn iter() { let mut slab = Slab::new(); @@ -209,6 +299,19 @@ fn iter() { } #[test] +fn iter_rev() { + let mut slab = Slab::new(); + + for i in 0..4 { + slab.insert(i); + } + slab.remove(0); + + let vals = slab.iter().rev().collect::<Vec<_>>(); + assert_eq!(vals, vec![(3, &3), (2, &2), (1, &1)]); +} + +#[test] fn iter_mut() { let mut slab = Slab::new(); @@ -218,7 +321,7 @@ fn iter_mut() { for (i, (key, e)) in slab.iter_mut().enumerate() { assert_eq!(i, key); - *e = *e + 1; + *e += 1; } let vals: Vec<_> = slab.iter().map(|(_, r)| *r).collect(); @@ -227,7 +330,7 @@ fn iter_mut() { slab.remove(2); for (_, e) in slab.iter_mut() { - *e = *e + 1; + *e += 1; } let vals: Vec<_> = slab.iter().map(|(_, r)| *r).collect(); @@ -235,6 +338,72 @@ fn iter_mut() { } #[test] +fn iter_mut_rev() { + let mut slab = Slab::new(); + + for i in 0..4 { + slab.insert(i); + } + slab.remove(2); + + { + let mut iter = slab.iter_mut(); + assert_eq!(iter.next(), Some((0, &mut 0))); + let mut prev_key = !0; + for (key, e) in iter.rev() { + *e += 10; + assert!(prev_key > key); + prev_key = key; + } + } + + assert_eq!(slab[0], 0); + assert_eq!(slab[1], 11); + assert_eq!(slab[3], 13); + assert!(!slab.contains(2)); +} + +#[test] +fn from_iterator_sorted() { + let mut slab = (0..5).map(|i| (i, i)).collect::<Slab<_>>(); + assert_eq!(slab.len(), 5); + assert_eq!(slab[0], 0); + assert_eq!(slab[2], 2); + assert_eq!(slab[4], 4); + assert_eq!(slab.vacant_entry().key(), 5); +} + +#[test] +fn from_iterator_new_in_order() { + // all new keys come in increasing order, but existing keys are overwritten + let mut slab = [(0, 'a'), (1, 'a'), (1, 'b'), (0, 'b'), (9, 'a'), (0, 'c')] + .iter() + .cloned() + .collect::<Slab<_>>(); + assert_eq!(slab.len(), 3); + assert_eq!(slab[0], 'c'); + assert_eq!(slab[1], 'b'); + assert_eq!(slab[9], 'a'); + assert_eq!(slab.get(5), None); + assert_eq!(slab.vacant_entry().key(), 8); +} + +#[test] +fn from_iterator_unordered() { + let mut slab = vec![(1, "one"), (50, "fifty"), (3, "three"), (20, "twenty")] + .into_iter() + .collect::<Slab<_>>(); + assert_eq!(slab.len(), 4); + assert_eq!(slab.vacant_entry().key(), 0); + let mut iter = slab.iter(); + assert_eq!(iter.next(), Some((1, &"one"))); + assert_eq!(iter.next(), Some((3, &"three"))); + assert_eq!(iter.next(), Some((20, &"twenty"))); + assert_eq!(iter.next(), Some((50, &"fifty"))); + assert_eq!(iter.next(), None); +} + +#[test] fn clear() { let mut slab = Slab::new(); @@ -266,6 +435,187 @@ fn clear() { } #[test] +fn shrink_to_fit_empty() { + let mut slab = Slab::<bool>::with_capacity(20); + slab.shrink_to_fit(); + assert_eq!(slab.capacity(), 0); +} + +#[test] +fn shrink_to_fit_no_vacant() { + let mut slab = Slab::with_capacity(20); + slab.insert(String::new()); + slab.shrink_to_fit(); + assert!(slab.capacity() < 10); +} + +#[test] +fn shrink_to_fit_doesnt_move() { + let mut slab = Slab::with_capacity(8); + slab.insert("foo"); + let bar = slab.insert("bar"); + slab.insert("baz"); + let quux = slab.insert("quux"); + slab.remove(quux); + slab.remove(bar); + slab.shrink_to_fit(); + assert_eq!(slab.len(), 2); + assert!(slab.capacity() >= 3); + assert_eq!(slab.get(0), Some(&"foo")); + assert_eq!(slab.get(2), Some(&"baz")); + assert_eq!(slab.vacant_entry().key(), bar); +} + +#[test] +fn shrink_to_fit_doesnt_recreate_list_when_nothing_can_be_done() { + let mut slab = Slab::with_capacity(16); + for i in 0..4 { + slab.insert(Box::new(i)); + } + slab.remove(0); + slab.remove(2); + slab.remove(1); + assert_eq!(slab.vacant_entry().key(), 1); + slab.shrink_to_fit(); + assert_eq!(slab.len(), 1); + assert!(slab.capacity() >= 4); + assert_eq!(slab.vacant_entry().key(), 1); +} + +#[test] +fn compact_empty() { + let mut slab = Slab::new(); + slab.compact(|_, _, _| panic!()); + assert_eq!(slab.len(), 0); + assert_eq!(slab.capacity(), 0); + slab.reserve(20); + slab.compact(|_, _, _| panic!()); + assert_eq!(slab.len(), 0); + assert_eq!(slab.capacity(), 0); + slab.insert(0); + slab.insert(1); + slab.insert(2); + slab.remove(1); + slab.remove(2); + slab.remove(0); + slab.compact(|_, _, _| panic!()); + assert_eq!(slab.len(), 0); + assert_eq!(slab.capacity(), 0); +} + +#[test] +fn compact_no_moves_needed() { + let mut slab = Slab::new(); + for i in 0..10 { + slab.insert(i); + } + slab.remove(8); + slab.remove(9); + slab.remove(6); + slab.remove(7); + slab.compact(|_, _, _| panic!()); + assert_eq!(slab.len(), 6); + for ((index, &value), want) in slab.iter().zip(0..6) { + assert!(index == value); + assert_eq!(index, want); + } + assert!(slab.capacity() >= 6 && slab.capacity() < 10); +} + +#[test] +fn compact_moves_successfully() { + let mut slab = Slab::with_capacity(20); + for i in 0..10 { + slab.insert(i); + } + for &i in &[0, 5, 9, 6, 3] { + slab.remove(i); + } + let mut moved = 0; + slab.compact(|&mut v, from, to| { + assert!(from > to); + assert!(from >= 5); + assert!(to < 5); + assert_eq!(from, v); + moved += 1; + true + }); + assert_eq!(slab.len(), 5); + assert_eq!(moved, 2); + assert_eq!(slab.vacant_entry().key(), 5); + assert!(slab.capacity() >= 5 && slab.capacity() < 20); + let mut iter = slab.iter(); + assert_eq!(iter.next(), Some((0, &8))); + assert_eq!(iter.next(), Some((1, &1))); + assert_eq!(iter.next(), Some((2, &2))); + assert_eq!(iter.next(), Some((3, &7))); + assert_eq!(iter.next(), Some((4, &4))); + assert_eq!(iter.next(), None); +} + +#[test] +fn compact_doesnt_move_if_closure_errors() { + let mut slab = Slab::with_capacity(20); + for i in 0..10 { + slab.insert(i); + } + for &i in &[9, 3, 1, 4, 0] { + slab.remove(i); + } + slab.compact(|&mut v, from, to| { + assert!(from > to); + assert_eq!(from, v); + v != 6 + }); + assert_eq!(slab.len(), 5); + assert!(slab.capacity() >= 7 && slab.capacity() < 20); + assert_eq!(slab.vacant_entry().key(), 3); + let mut iter = slab.iter(); + assert_eq!(iter.next(), Some((0, &8))); + assert_eq!(iter.next(), Some((1, &7))); + assert_eq!(iter.next(), Some((2, &2))); + assert_eq!(iter.next(), Some((5, &5))); + assert_eq!(iter.next(), Some((6, &6))); + assert_eq!(iter.next(), None); +} + +#[test] +// Android aborts on panic and this test relies on stack unwinding. +#[cfg(not(target_os = "android"))] +fn compact_handles_closure_panic() { + let mut slab = Slab::new(); + for i in 0..10 { + slab.insert(i); + } + for i in 1..6 { + slab.remove(i); + } + let result = catch_unwind(AssertUnwindSafe(|| { + slab.compact(|&mut v, from, to| { + assert!(from > to); + assert_eq!(from, v); + if v == 7 { + panic!("test"); + } + true + }) + })); + match result { + Err(ref payload) if payload.downcast_ref() == Some(&"test") => {} + Err(bug) => resume_unwind(bug), + Ok(()) => unreachable!(), + } + assert_eq!(slab.len(), 5 - 1); + assert_eq!(slab.vacant_entry().key(), 3); + let mut iter = slab.iter(); + assert_eq!(iter.next(), Some((0, &0))); + assert_eq!(iter.next(), Some((1, &9))); + assert_eq!(iter.next(), Some((2, &8))); + assert_eq!(iter.next(), Some((6, &6))); + assert_eq!(iter.next(), None); +} + +#[test] fn fully_consumed_drain() { let mut slab = Slab::new(); @@ -299,3 +649,15 @@ fn partially_consumed_drain() { assert!(slab.is_empty()) } + +#[test] +fn drain_rev() { + let mut slab = Slab::new(); + for i in 0..10 { + slab.insert(i); + } + slab.remove(9); + + let vals: Vec<u64> = slab.drain().rev().collect(); + assert_eq!(vals, (0..9).rev().collect::<Vec<u64>>()); +} |