Snap for 10453563 from 52a25c5a6a55a55b1fb617cfd856988d4ccee621 to mainline-art-release
Change-Id: I54ed22f5dbbc583033758cbcd26fadc6158df3a0
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
diff --git a/Android.bp b/Android.bp
index 6c87c6e..0560e54 100644
--- a/Android.bp
+++ b/Android.bp
@@ -23,7 +23,7 @@
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 @@
],
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 @@
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 @@
"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)
diff --git a/Cargo.toml b/Cargo.toml
index e1cca93..8823fb8 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -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 @@
[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 @@
# - 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 @@
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"
diff --git a/METADATA b/METADATA
index 6ca4640..447f06a 100644
--- a/METADATA
+++ b/METADATA
@@ -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 @@
}
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
}
}
diff --git a/README.md b/README.md
index edbbe03..4281389 100644
--- a/README.md
+++ b/README.md
@@ -7,7 +7,7 @@
[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,6 +5,18 @@
"path": "external/rust/crates/anyhow"
},
{
+ "path": "external/rust/crates/async-stream"
+ },
+ {
+ "path": "external/rust/crates/futures-channel"
+ },
+ {
+ "path": "external/rust/crates/futures-executor"
+ },
+ {
+ "path": "external/rust/crates/futures-test"
+ },
+ {
"path": "external/rust/crates/futures-util"
},
{
@@ -12,40 +24,34 @@
},
{
"path": "external/rust/crates/tokio-test"
+ },
+ {
+ "path": "packages/modules/DnsResolver"
+ },
+ {
+ "path": "packages/modules/Virtualization/authfs"
+ },
+ {
+ "path": "packages/modules/Virtualization/virtualizationmanager"
+ },
+ {
+ "path": "packages/modules/Virtualization/zipfuse"
+ },
+ {
+ "path": "system/security/keystore2"
+ },
+ {
+ "path": "system/security/keystore2/legacykeystore"
}
],
"presubmit": [
{
- "name": "ZipFuseTest"
- },
- {
- "name": "authfs_device_test_src_lib"
- },
- {
- "name": "doh_unit_test"
- },
- {
"name": "slab_test_tests_slab"
- },
- {
- "name": "virtualizationservice_device_test"
}
],
"presubmit-rust": [
{
- "name": "ZipFuseTest"
- },
- {
- "name": "authfs_device_test_src_lib"
- },
- {
- "name": "doh_unit_test"
- },
- {
"name": "slab_test_tests_slab"
- },
- {
- "name": "virtualizationservice_device_test"
}
]
}
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
+ }
+}
diff --git a/src/lib.rs b/src/lib.rs
index 271c1db..e23ead9 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -118,6 +118,8 @@
#[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 @@
/// 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 @@
///
/// # Panics
///
- /// Panics if the new capacity overflows `usize`.
+ /// Panics if the new capacity exceeds `isize::MAX` bytes.
///
/// # Examples
///
@@ -326,7 +349,7 @@
///
/// # Panics
///
- /// Panics if the new capacity overflows `usize`.
+ /// Panics if the new capacity exceeds `isize::MAX` bytes.
///
/// # Examples
///
@@ -419,17 +442,21 @@
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 @@
/// ```
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 @@
/// 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 @@
/// 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 @@
/// 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 @@
///
/// # 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 @@
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 @@
/// 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> 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 @@
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 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
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_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_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 @@
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();
+}
