diff options
-rw-r--r-- | .cargo_vcs_info.json | 7 | ||||
-rw-r--r-- | Android.bp | 9 | ||||
-rw-r--r-- | CHANGELOG.md | 22 | ||||
-rw-r--r-- | Cargo.toml | 25 | ||||
-rw-r--r-- | Cargo.toml.orig | 10 | ||||
-rw-r--r-- | METADATA | 12 | ||||
-rw-r--r-- | README.md | 2 | ||||
-rw-r--r-- | TEST_MAPPING | 44 | ||||
-rw-r--r-- | build.rs | 24 | ||||
-rw-r--r-- | cargo2android.json | 2 | ||||
-rw-r--r-- | src/builder.rs | 63 | ||||
-rw-r--r-- | src/lib.rs | 130 | ||||
-rw-r--r-- | src/serde.rs | 47 | ||||
-rw-r--r-- | tests/slab.rs | 18 |
14 files changed, 273 insertions, 142 deletions
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json index 90db974..4866a89 100644 --- a/.cargo_vcs_info.json +++ b/.cargo_vcs_info.json @@ -1,5 +1,6 @@ { "git": { - "sha1": "c512385b1a70100c8597f0f519390c80e90c9529" - } -} + "sha1": "151a9cea914bb8017470caeb467a208fd1ad99b3" + }, + "path_in_vcs": "" +}
\ No newline at end of file @@ -23,7 +23,7 @@ rust_library { host_supported: true, crate_name: "slab", cargo_env_compat: true, - cargo_pkg_version: "0.4.5", + cargo_pkg_version: "0.4.8", srcs: ["src/lib.rs"], edition: "2018", features: [ @@ -32,10 +32,12 @@ rust_library { ], apex_available: [ "//apex_available:platform", - "com.android.bluetooth", + "com.android.btservices", "com.android.resolv", "com.android.virt", ], + product_available: true, + vendor_available: true, min_sdk_version: "29", } @@ -44,7 +46,7 @@ rust_test { host_supported: true, crate_name: "slab", cargo_env_compat: true, - cargo_pkg_version: "0.4.5", + cargo_pkg_version: "0.4.8", srcs: ["tests/slab.rs"], test_suites: ["general-tests"], auto_gen_config: true, @@ -61,4 +63,5 @@ rust_test { "libserde_test", "libslab", ], + proc_macros: ["librustversion"], } diff --git a/CHANGELOG.md b/CHANGELOG.md index 501a25c..db54582 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -1,8 +1,24 @@ +# 0.4.8 (January 20, 2022) + +* Fixed documentation about overflow (#124) +* Document panic in `get2_mut` (#131) +* Refactoring (#129, #132) + +# 0.4.7 (July 19, 2022) + +* Use `#[track_caller]` on Rust 1.46+ (#119) +* Make `Slab::new` const on Rust 1.39+ (#119) + +# 0.4.6 (April 2, 2022) + +* Add `Slab::vacant_key` (#114) +* Fix stacked borrows violation in `Slab::get2_unchecked_mut` (#115) + # 0.4.5 (October 13, 2021) - * Add alternate debug output for listing items in the slab (#108) - * Fix typo in debug output of IntoIter (#109) - * Impl 'Clone' for 'Iter' (#110) +* Add alternate debug output for listing items in the slab (#108) +* Fix typo in debug output of IntoIter (#109) +* Impl 'Clone' for 'Iter' (#110) # 0.4.4 (August 06, 2021) @@ -11,23 +11,35 @@ [package] edition = "2018" +rust-version = "1.31" name = "slab" -version = "0.4.5" +version = "0.4.8" authors = ["Carl Lerche <me@carllerche.com>"] exclude = ["/.*"] description = "Pre-allocated storage for a uniform data type" -homepage = "https://github.com/tokio-rs/slab" -documentation = "https://docs.rs/slab" readme = "README.md" -keywords = ["slab", "allocator", "no_std"] -categories = ["memory-management", "data-structures", "no-std"] +keywords = [ + "slab", + "allocator", + "no_std", +] +categories = [ + "memory-management", + "data-structures", + "no-std", +] license = "MIT" repository = "https://github.com/tokio-rs/slab" + [dependencies.serde] version = "1.0.95" features = ["alloc"] optional = true default-features = false + +[dev-dependencies.rustversion] +version = "1" + [dev-dependencies.serde] version = "1" features = ["derive"] @@ -35,6 +47,9 @@ features = ["derive"] [dev-dependencies.serde_test] version = "1" +[build-dependencies.autocfg] +version = "1" + [features] default = ["std"] std = [] diff --git a/Cargo.toml.orig b/Cargo.toml.orig index bc25be8..ae94bb4 100644 --- a/Cargo.toml.orig +++ b/Cargo.toml.orig @@ -6,15 +6,13 @@ name = "slab" # - README.md # - Update CHANGELOG.md # - Create git tag -version = "0.4.5" +version = "0.4.8" authors = ["Carl Lerche <me@carllerche.com>"] edition = "2018" +rust-version = "1.31" license = "MIT" description = "Pre-allocated storage for a uniform data type" -documentation = "https://docs.rs/slab" -homepage = "https://github.com/tokio-rs/slab" repository = "https://github.com/tokio-rs/slab" -readme = "README.md" keywords = ["slab", "allocator", "no_std"] categories = ["memory-management", "data-structures", "no-std"] exclude = ["/.*"] @@ -23,9 +21,13 @@ exclude = ["/.*"] std = [] default = ["std"] +[build-dependencies] +autocfg = "1" + [dependencies] serde = { version = "1.0.95", optional = true, default-features = false, features = ["alloc"] } [dev-dependencies] +rustversion = "1" serde = { version = "1", features = ["derive"] } serde_test = "1" @@ -1,3 +1,7 @@ +# This project was upgraded with external_updater. +# Usage: tools/external_updater/updater.sh update rust/crates/slab +# For more info, check https://cs.android.com/android/platform/superproject/+/master:tools/external_updater/README.md + name: "slab" description: "Pre-allocated storage for a uniform data type" third_party { @@ -7,13 +11,13 @@ third_party { } url { type: ARCHIVE - value: "https://static.crates.io/crates/slab/slab-0.4.5.crate" + value: "https://static.crates.io/crates/slab/slab-0.4.8.crate" } - version: "0.4.5" + version: "0.4.8" license_type: NOTICE last_upgrade_date { - year: 2022 + year: 2023 month: 3 - day: 1 + day: 6 } } @@ -7,7 +7,7 @@ Pre-allocated storage for a uniform data type. [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-badge]: https://img.shields.io/github/actions/workflow/status/tokio-rs/slab/ci.yml?branch=master [ci-url]: https://github.com/tokio-rs/slab/actions [Documentation](https://docs.rs/slab) diff --git a/TEST_MAPPING b/TEST_MAPPING index 9af5cdc..b755779 100644 --- a/TEST_MAPPING +++ b/TEST_MAPPING @@ -5,47 +5,53 @@ "path": "external/rust/crates/anyhow" }, { - "path": "external/rust/crates/futures-util" + "path": "external/rust/crates/async-stream" }, { - "path": "external/rust/crates/tokio" + "path": "external/rust/crates/futures-channel" }, { - "path": "external/rust/crates/tokio-test" - } - ], - "presubmit": [ + "path": "external/rust/crates/futures-executor" + }, { - "name": "ZipFuseTest" + "path": "external/rust/crates/futures-test" }, { - "name": "authfs_device_test_src_lib" + "path": "external/rust/crates/futures-util" }, { - "name": "doh_unit_test" + "path": "external/rust/crates/tokio" }, { - "name": "slab_test_tests_slab" + "path": "external/rust/crates/tokio-test" }, { - "name": "virtualizationservice_device_test" - } - ], - "presubmit-rust": [ + "path": "packages/modules/DnsResolver" + }, { - "name": "ZipFuseTest" + "path": "packages/modules/Virtualization/authfs" }, { - "name": "authfs_device_test_src_lib" + "path": "packages/modules/Virtualization/virtualizationmanager" }, { - "name": "doh_unit_test" + "path": "packages/modules/Virtualization/zipfuse" }, { - "name": "slab_test_tests_slab" + "path": "system/security/keystore2" }, { - "name": "virtualizationservice_device_test" + "path": "system/security/keystore2/legacykeystore" + } + ], + "presubmit": [ + { + "name": "slab_test_tests_slab" + } + ], + "presubmit-rust": [ + { + "name": "slab_test_tests_slab" } ] } diff --git a/build.rs b/build.rs new file mode 100644 index 0000000..b60351a --- /dev/null +++ b/build.rs @@ -0,0 +1,24 @@ +fn main() { + let cfg = match autocfg::AutoCfg::new() { + Ok(cfg) => cfg, + Err(e) => { + // If we couldn't detect the compiler version and features, just + // print a warning. This isn't a fatal error: we can still build + // Slab, we just can't enable cfgs automatically. + println!( + "cargo:warning=slab: failed to detect compiler features: {}", + e + ); + return; + } + }; + // Note that this is `no_`*, not `has_*`. This allows treating as the latest + // stable rustc is used when the build script doesn't run. This is useful + // for non-cargo build systems that don't run the build script. + if !cfg.probe_rustc_version(1, 39) { + println!("cargo:rustc-cfg=slab_no_const_vec_new"); + } + if !cfg.probe_rustc_version(1, 46) { + println!("cargo:rustc-cfg=slab_no_track_caller"); + } +} diff --git a/cargo2android.json b/cargo2android.json index 5b266a6..b98d10b 100644 --- a/cargo2android.json +++ b/cargo2android.json @@ -1,7 +1,7 @@ { "apex-available": [ "//apex_available:platform", - "com.android.bluetooth", + "com.android.btservices", "com.android.resolv", "com.android.virt" ], diff --git a/src/builder.rs b/src/builder.rs new file mode 100644 index 0000000..8e50a20 --- /dev/null +++ b/src/builder.rs @@ -0,0 +1,63 @@ +use crate::{Entry, Slab}; + +// Building `Slab` from pairs (usize, T). +pub(crate) struct Builder<T> { + slab: Slab<T>, + vacant_list_broken: bool, + first_vacant_index: Option<usize>, +} + +impl<T> Builder<T> { + pub(crate) fn with_capacity(capacity: usize) -> Self { + Self { + slab: Slab::with_capacity(capacity), + vacant_list_broken: false, + first_vacant_index: None, + } + } + pub(crate) fn pair(&mut self, key: usize, value: T) { + let slab = &mut self.slab; + if key < slab.entries.len() { + // iterator is not sorted, might need to recreate vacant list + if let Entry::Vacant(_) = slab.entries[key] { + self.vacant_list_broken = true; + slab.len += 1; + } + // if an element with this key already exists, replace it. + // This is consistent with HashMap and BtreeMap + slab.entries[key] = Entry::Occupied(value); + } else { + if self.first_vacant_index.is_none() && slab.entries.len() < key { + self.first_vacant_index = Some(slab.entries.len()); + } + // 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; + } + } + + pub(crate) fn build(self) -> Slab<T> { + let mut slab = self.slab; + if slab.len == slab.entries.len() { + // no vacant entries, so next might not have been updated + slab.next = slab.entries.len(); + } else if self.vacant_list_broken { + slab.recreate_vacant_list(); + } else if let Some(first_vacant_index) = self.first_vacant_index { + let next = slab.entries.len(); + match &mut slab.entries[first_vacant_index] { + Entry::Vacant(n) => *n = next, + _ => unreachable!(), + } + } else { + unreachable!() + } + slab + } +} @@ -118,6 +118,8 @@ extern crate std as alloc; #[cfg(feature = "serde")] mod serde; +mod builder; + use alloc::vec::{self, Vec}; use core::iter::{self, FromIterator, FusedIterator}; use core::{fmt, mem, ops, slice}; @@ -219,14 +221,35 @@ impl<T> Slab<T> { /// The function does not allocate and the returned slab will have no /// capacity until `insert` is called or capacity is explicitly reserved. /// + /// This is `const fn` on Rust 1.39+. + /// /// # Examples /// /// ``` /// # use slab::*; /// let slab: Slab<i32> = Slab::new(); /// ``` - pub fn new() -> Slab<T> { - Slab::with_capacity(0) + #[cfg(not(slab_no_const_vec_new))] + pub const fn new() -> Self { + Self { + entries: Vec::new(), + next: 0, + len: 0, + } + } + /// Construct a new, empty `Slab`. + /// + /// The function does not allocate and the returned slab will have no + /// capacity until `insert` is called or capacity is explicitly reserved. + /// + /// This is `const fn` on Rust 1.39+. + #[cfg(slab_no_const_vec_new)] + pub fn new() -> Self { + Self { + entries: Vec::new(), + next: 0, + len: 0, + } } /// Construct a new, empty `Slab` with the specified capacity. @@ -292,7 +315,7 @@ impl<T> Slab<T> { /// /// # Panics /// - /// Panics if the new capacity overflows `usize`. + /// Panics if the new capacity exceeds `isize::MAX` bytes. /// /// # Examples /// @@ -326,7 +349,7 @@ impl<T> Slab<T> { /// /// # Panics /// - /// Panics if the new capacity overflows `usize`. + /// Panics if the new capacity exceeds `isize::MAX` bytes. /// /// # Examples /// @@ -419,17 +442,21 @@ impl<T> Slab<T> { self.next = self.entries.len(); // We can stop once we've found all vacant entries let mut remaining_vacant = self.entries.len() - self.len; + if remaining_vacant == 0 { + return; + } + // 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; + if remaining_vacant == 0 { + break; + } } } } @@ -665,7 +692,7 @@ impl<T> Slab<T> { /// ``` pub fn get(&self, key: usize) -> Option<&T> { match self.entries.get(key) { - Some(&Entry::Occupied(ref val)) => Some(val), + Some(Entry::Occupied(val)) => Some(val), _ => None, } } @@ -703,6 +730,10 @@ impl<T> Slab<T> { /// 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. /// + /// # Panics + /// + /// This function will panic if `key1` and `key2` are the same. + /// /// # Examples /// /// ``` @@ -830,8 +861,10 @@ impl<T> Slab<T> { /// 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>; + debug_assert_ne!(key1, key2); + let ptr = self.entries.as_mut_ptr(); + let ptr1 = ptr.add(key1); + let ptr2 = ptr.add(key2); match (&mut *ptr1, &mut *ptr2) { (&mut Entry::Occupied(ref mut val1), &mut Entry::Occupied(ref mut val2)) => { (val1, val2) @@ -875,6 +908,7 @@ impl<T> Slab<T> { /// slab.key_of(bad); // this will panic /// unreachable!(); /// ``` + #[cfg_attr(not(slab_no_track_caller), track_caller)] 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; @@ -899,7 +933,7 @@ impl<T> Slab<T> { /// /// # Panics /// - /// Panics if the number of elements in the vector overflows a `usize`. + /// Panics if the new storage in the vector exceeds `isize::MAX` bytes. /// /// # Examples /// @@ -917,6 +951,30 @@ impl<T> Slab<T> { key } + /// Returns the key of the next vacant entry. + /// + /// This function returns the key of the vacant entry which will be used + /// for the next insertion. This is equivalent to + /// `slab.vacant_entry().key()`, but it doesn't require mutable access. + /// + /// # Examples + /// + /// ``` + /// # use slab::*; + /// let mut slab = Slab::new(); + /// assert_eq!(slab.vacant_key(), 0); + /// + /// slab.insert(0); + /// assert_eq!(slab.vacant_key(), 1); + /// + /// slab.insert(1); + /// slab.remove(0); + /// assert_eq!(slab.vacant_key(), 0); + /// ``` + pub fn vacant_key(&self) -> usize { + self.next + } + /// Return a handle to a vacant entry allowing for further manipulation. /// /// This function is useful when creating values that must contain their @@ -1019,6 +1077,7 @@ impl<T> Slab<T> { /// assert_eq!(slab.remove(hello), "hello"); /// assert!(!slab.contains(hello)); /// ``` + #[cfg_attr(not(slab_no_track_caller), track_caller)] pub fn remove(&mut self, key: usize) -> T { self.try_remove(key).expect("invalid key") } @@ -1126,15 +1185,17 @@ impl<T> Slab<T> { impl<T> ops::Index<usize> for Slab<T> { type Output = T; + #[cfg_attr(not(slab_no_track_caller), track_caller)] fn index(&self, key: usize) -> &T { match self.entries.get(key) { - Some(&Entry::Occupied(ref v)) => v, + Some(Entry::Occupied(v)) => v, _ => panic!("invalid key"), } } } impl<T> ops::IndexMut<usize> for Slab<T> { + #[cfg_attr(not(slab_no_track_caller), track_caller)] fn index_mut(&mut self, key: usize) -> &mut T { match self.entries.get_mut(key) { Some(&mut Entry::Occupied(ref mut v)) => v, @@ -1209,51 +1270,12 @@ impl<T> FromIterator<(usize, T)> for Slab<T> { I: IntoIterator<Item = (usize, T)>, { let iterator = iterable.into_iter(); - let mut slab = Self::with_capacity(iterator.size_hint().0); + let mut builder = builder::Builder::with_capacity(iterator.size_hint().0); - let mut vacant_list_broken = false; - let mut first_vacant_index = None; 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 consistent with HashMap and BtreeMap - slab.entries[key] = Entry::Occupied(value); - } else { - if first_vacant_index.is_none() && slab.entries.len() < key { - first_vacant_index = Some(slab.entries.len()); - } - // 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; - } + builder.pair(key, value) } - if slab.len == slab.entries.len() { - // no vacant entries, so next might not have been updated - slab.next = slab.entries.len(); - } else if vacant_list_broken { - slab.recreate_vacant_list(); - } else if let Some(first_vacant_index) = first_vacant_index { - let next = slab.entries.len(); - match &mut slab.entries[first_vacant_index] { - Entry::Vacant(n) => *n = next, - _ => unreachable!(), - } - } else { - unreachable!() - } - - slab + builder.build() } } diff --git a/src/serde.rs b/src/serde.rs index 7ffe8e0..894d59c 100644 --- a/src/serde.rs +++ b/src/serde.rs @@ -4,7 +4,7 @@ use core::marker::PhantomData; use serde::de::{Deserialize, Deserializer, MapAccess, Visitor}; use serde::ser::{Serialize, SerializeMap, Serializer}; -use super::{Entry, Slab}; +use super::{builder::Builder, Slab}; impl<T> Serialize for Slab<T> where @@ -39,52 +39,13 @@ where where A: MapAccess<'de>, { - let mut slab = Slab::with_capacity(map.size_hint().unwrap_or(0)); + let mut builder = Builder::with_capacity(map.size_hint().unwrap_or(0)); - // same as FromIterator impl - let mut vacant_list_broken = false; - let mut first_vacant_index = None; 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 consistent with HashMap and BtreeMap - slab.entries[key] = Entry::Occupied(value); - } else { - if first_vacant_index.is_none() && slab.entries.len() < key { - first_vacant_index = Some(slab.entries.len()); - } - // 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 entries, so next might not have been updated - slab.next = slab.entries.len(); - } else if vacant_list_broken { - slab.recreate_vacant_list(); - } else if let Some(first_vacant_index) = first_vacant_index { - let next = slab.entries.len(); - match &mut slab.entries[first_vacant_index] { - Entry::Vacant(n) => *n = next, - _ => unreachable!(), - } - } else { - unreachable!() + builder.pair(key, value) } - Ok(slab) + Ok(builder.build()) } } diff --git a/tests/slab.rs b/tests/slab.rs index 8b03c1e..f446350 100644 --- a/tests/slab.rs +++ b/tests/slab.rs @@ -196,7 +196,15 @@ fn reserve_exact_does_not_allocate_if_available() { fn reserve_does_panic_with_capacity_overflow() { let mut slab = Slab::with_capacity(10); slab.insert(true); - slab.reserve(std::usize::MAX); + slab.reserve(std::isize::MAX as usize); +} + +#[test] +#[should_panic(expected = "capacity overflow")] +fn reserve_does_panic_with_capacity_overflow_bytes() { + let mut slab = Slab::with_capacity(10); + slab.insert(1u16); + slab.reserve((std::isize::MAX as usize) / 2); } #[test] @@ -204,7 +212,7 @@ fn reserve_does_panic_with_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); + slab.reserve_exact(std::isize::MAX as usize); } #[test] @@ -698,3 +706,9 @@ fn try_remove() { assert_eq!(slab.try_remove(key), None); assert_eq!(slab.get(key), None); } + +#[rustversion::since(1.39)] +#[test] +fn const_new() { + static _SLAB: Slab<()> = Slab::new(); +} |