Upgrade crossbeam-deque to 0.8.3 am: 7757653066
Original change: https://android-review.googlesource.com/c/platform/external/rust/crates/crossbeam-deque/+/2470803
Change-Id: Ib9ddf00c88f22a0bf8dec0048de8a3add026d6df
Signed-off-by: Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com>
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
index db5e432..ee1b175 100644
--- a/.cargo_vcs_info.json
+++ b/.cargo_vcs_info.json
@@ -1,6 +1,6 @@
{
"git": {
- "sha1": "5e0f59a9990c032c33e1db16a6bfc64b4ab6102d"
+ "sha1": "721382b00b5dadd81954ed66764d547e2f1bb7a3"
},
"path_in_vcs": "crossbeam-deque"
}
\ No newline at end of file
diff --git a/Android.bp b/Android.bp
index 0f95e90..677e584 100644
--- a/Android.bp
+++ b/Android.bp
@@ -43,7 +43,7 @@
name: "crossbeam-deque_test_defaults",
crate_name: "crossbeam_deque",
cargo_env_compat: true,
- cargo_pkg_version: "0.8.2",
+ cargo_pkg_version: "0.8.3",
test_suites: ["general-tests"],
auto_gen_config: true,
edition: "2018",
@@ -107,7 +107,7 @@
host_supported: true,
crate_name: "crossbeam_deque",
cargo_env_compat: true,
- cargo_pkg_version: "0.8.2",
+ cargo_pkg_version: "0.8.3",
srcs: ["src/lib.rs"],
edition: "2018",
features: [
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 855b714..0937d19 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,3 +1,8 @@
+# Version 0.8.3
+
+- Add `Stealer::{steal_batch_with_limit, steal_batch_with_limit_and_pop}` methods. (#903)
+- Add `Injector::{steal_batch_with_limit, steal_batch_with_limit_and_pop}` methods. (#903)
+
# Version 0.8.2
- Bump the minimum supported Rust version to 1.38. (#877)
diff --git a/Cargo.toml b/Cargo.toml
index 4ff10b3..ea7bab2 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -13,7 +13,7 @@
edition = "2018"
rust-version = "1.38"
name = "crossbeam-deque"
-version = "0.8.2"
+version = "0.8.3"
description = "Concurrent work-stealing deque"
homepage = "https://github.com/crossbeam-rs/crossbeam/tree/master/crossbeam-deque"
readme = "README.md"
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
index f8199e7..805a7e0 100644
--- a/Cargo.toml.orig
+++ b/Cargo.toml.orig
@@ -4,7 +4,7 @@
# - Update CHANGELOG.md
# - Update README.md
# - Create "crossbeam-deque-X.Y.Z" git tag
-version = "0.8.2"
+version = "0.8.3"
edition = "2018"
rust-version = "1.38"
license = "MIT OR Apache-2.0"
diff --git a/METADATA b/METADATA
index ee4080b..904cef6 100644
--- a/METADATA
+++ b/METADATA
@@ -11,13 +11,13 @@
}
url {
type: ARCHIVE
- value: "https://static.crates.io/crates/crossbeam-deque/crossbeam-deque-0.8.2.crate"
+ value: "https://static.crates.io/crates/crossbeam-deque/crossbeam-deque-0.8.3.crate"
}
- version: "0.8.2"
+ version: "0.8.3"
license_type: NOTICE
last_upgrade_date {
- year: 2022
- month: 12
- day: 8
+ year: 2023
+ month: 3
+ day: 6
}
}
diff --git a/src/deque.rs b/src/deque.rs
index bda3bf8..8afe15f 100644
--- a/src/deque.rs
+++ b/src/deque.rs
@@ -693,6 +693,45 @@
/// assert_eq!(w2.pop(), Some(2));
/// ```
pub fn steal_batch(&self, dest: &Worker<T>) -> Steal<()> {
+ self.steal_batch_with_limit(dest, MAX_BATCH)
+ }
+
+ /// Steals no more than `limit` of tasks and pushes them into another worker.
+ ///
+ /// How many tasks exactly will be stolen is not specified. That said, this method will try to
+ /// steal around half of the tasks in the queue, but also not more than the given limit.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use crossbeam_deque::Worker;
+ ///
+ /// let w1 = Worker::new_fifo();
+ /// w1.push(1);
+ /// w1.push(2);
+ /// w1.push(3);
+ /// w1.push(4);
+ /// w1.push(5);
+ /// w1.push(6);
+ ///
+ /// let s = w1.stealer();
+ /// let w2 = Worker::new_fifo();
+ ///
+ /// let _ = s.steal_batch_with_limit(&w2, 2);
+ /// assert_eq!(w2.pop(), Some(1));
+ /// assert_eq!(w2.pop(), Some(2));
+ /// assert_eq!(w2.pop(), None);
+ ///
+ /// w1.push(7);
+ /// w1.push(8);
+ /// // Setting a large limit does not guarantee that all elements will be popped. In this case,
+ /// // half of the elements are currently popped, but the number of popped elements is considered
+ /// // an implementation detail that may be changed in the future.
+ /// let _ = s.steal_batch_with_limit(&w2, std::usize::MAX);
+ /// assert_eq!(w2.len(), 3);
+ /// ```
+ pub fn steal_batch_with_limit(&self, dest: &Worker<T>, limit: usize) -> Steal<()> {
+ assert!(limit > 0);
if Arc::ptr_eq(&self.inner, &dest.inner) {
if dest.is_empty() {
return Steal::Empty;
@@ -725,7 +764,7 @@
}
// Reserve capacity for the stolen batch.
- let batch_size = cmp::min((len as usize + 1) / 2, MAX_BATCH);
+ let batch_size = cmp::min((len as usize + 1) / 2, limit);
dest.reserve(batch_size);
let mut batch_size = batch_size as isize;
@@ -891,6 +930,47 @@
/// assert_eq!(w2.pop(), Some(2));
/// ```
pub fn steal_batch_and_pop(&self, dest: &Worker<T>) -> Steal<T> {
+ self.steal_batch_with_limit_and_pop(dest, MAX_BATCH)
+ }
+
+ /// Steals no more than `limit` of tasks, pushes them into another worker, and pops a task from
+ /// that worker.
+ ///
+ /// How many tasks exactly will be stolen is not specified. That said, this method will try to
+ /// steal around half of the tasks in the queue, but also not more than the given limit.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use crossbeam_deque::{Steal, Worker};
+ ///
+ /// let w1 = Worker::new_fifo();
+ /// w1.push(1);
+ /// w1.push(2);
+ /// w1.push(3);
+ /// w1.push(4);
+ /// w1.push(5);
+ /// w1.push(6);
+ ///
+ /// let s = w1.stealer();
+ /// let w2 = Worker::new_fifo();
+ ///
+ /// assert_eq!(s.steal_batch_with_limit_and_pop(&w2, 2), Steal::Success(1));
+ /// assert_eq!(w2.pop(), Some(2));
+ /// assert_eq!(w2.pop(), None);
+ ///
+ /// w1.push(7);
+ /// w1.push(8);
+ /// // Setting a large limit does not guarantee that all elements will be popped. In this case,
+ /// // half of the elements are currently popped, but the number of popped elements is considered
+ /// // an implementation detail that may be changed in the future.
+ /// assert_eq!(s.steal_batch_with_limit_and_pop(&w2, std::usize::MAX), Steal::Success(3));
+ /// assert_eq!(w2.pop(), Some(4));
+ /// assert_eq!(w2.pop(), Some(5));
+ /// assert_eq!(w2.pop(), None);
+ /// ```
+ pub fn steal_batch_with_limit_and_pop(&self, dest: &Worker<T>, limit: usize) -> Steal<T> {
+ assert!(limit > 0);
if Arc::ptr_eq(&self.inner, &dest.inner) {
match dest.pop() {
None => return Steal::Empty,
@@ -922,7 +1002,7 @@
}
// Reserve capacity for the stolen batch.
- let batch_size = cmp::min((len as usize - 1) / 2, MAX_BATCH - 1);
+ let batch_size = cmp::min((len as usize - 1) / 2, limit - 1);
dest.reserve(batch_size);
let mut batch_size = batch_size as isize;
@@ -1444,6 +1524,43 @@
/// assert_eq!(w.pop(), Some(2));
/// ```
pub fn steal_batch(&self, dest: &Worker<T>) -> Steal<()> {
+ self.steal_batch_with_limit(dest, MAX_BATCH)
+ }
+
+ /// Steals no more than of tasks and pushes them into a worker.
+ ///
+ /// How many tasks exactly will be stolen is not specified. That said, this method will try to
+ /// steal around half of the tasks in the queue, but also not more than some constant limit.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use crossbeam_deque::{Injector, Worker};
+ ///
+ /// let q = Injector::new();
+ /// q.push(1);
+ /// q.push(2);
+ /// q.push(3);
+ /// q.push(4);
+ /// q.push(5);
+ /// q.push(6);
+ ///
+ /// let w = Worker::new_fifo();
+ /// let _ = q.steal_batch_with_limit(&w, 2);
+ /// assert_eq!(w.pop(), Some(1));
+ /// assert_eq!(w.pop(), Some(2));
+ /// assert_eq!(w.pop(), None);
+ ///
+ /// q.push(7);
+ /// q.push(8);
+ /// // Setting a large limit does not guarantee that all elements will be popped. In this case,
+ /// // half of the elements are currently popped, but the number of popped elements is considered
+ /// // an implementation detail that may be changed in the future.
+ /// let _ = q.steal_batch_with_limit(&w, std::usize::MAX);
+ /// assert_eq!(w.len(), 3);
+ /// ```
+ pub fn steal_batch_with_limit(&self, dest: &Worker<T>, limit: usize) -> Steal<()> {
+ assert!(limit > 0);
let mut head;
let mut block;
let mut offset;
@@ -1481,15 +1598,15 @@
if (head >> SHIFT) / LAP != (tail >> SHIFT) / LAP {
new_head |= HAS_NEXT;
// We can steal all tasks till the end of the block.
- advance = (BLOCK_CAP - offset).min(MAX_BATCH);
+ advance = (BLOCK_CAP - offset).min(limit);
} else {
let len = (tail - head) >> SHIFT;
// Steal half of the available tasks.
- advance = ((len + 1) / 2).min(MAX_BATCH);
+ advance = ((len + 1) / 2).min(limit);
}
} else {
// We can steal all tasks till the end of the block.
- advance = (BLOCK_CAP - offset).min(MAX_BATCH);
+ advance = (BLOCK_CAP - offset).min(limit);
}
new_head += advance << SHIFT;
@@ -1603,6 +1720,45 @@
/// assert_eq!(w.pop(), Some(2));
/// ```
pub fn steal_batch_and_pop(&self, dest: &Worker<T>) -> Steal<T> {
+ // TODO: we use `MAX_BATCH + 1` as the hard limit for Injecter as the performance is slightly
+ // better, but we may change it in the future to be compatible with the same method in Stealer.
+ self.steal_batch_with_limit_and_pop(dest, MAX_BATCH + 1)
+ }
+
+ /// Steals no more than `limit` of tasks, pushes them into a worker, and pops a task from that worker.
+ ///
+ /// How many tasks exactly will be stolen is not specified. That said, this method will try to
+ /// steal around half of the tasks in the queue, but also not more than the given limit.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use crossbeam_deque::{Injector, Steal, Worker};
+ ///
+ /// let q = Injector::new();
+ /// q.push(1);
+ /// q.push(2);
+ /// q.push(3);
+ /// q.push(4);
+ /// q.push(5);
+ /// q.push(6);
+ ///
+ /// let w = Worker::new_fifo();
+ /// assert_eq!(q.steal_batch_with_limit_and_pop(&w, 2), Steal::Success(1));
+ /// assert_eq!(w.pop(), Some(2));
+ /// assert_eq!(w.pop(), None);
+ ///
+ /// q.push(7);
+ /// // Setting a large limit does not guarantee that all elements will be popped. In this case,
+ /// // half of the elements are currently popped, but the number of popped elements is considered
+ /// // an implementation detail that may be changed in the future.
+ /// assert_eq!(q.steal_batch_with_limit_and_pop(&w, std::usize::MAX), Steal::Success(3));
+ /// assert_eq!(w.pop(), Some(4));
+ /// assert_eq!(w.pop(), Some(5));
+ /// assert_eq!(w.pop(), None);
+ /// ```
+ pub fn steal_batch_with_limit_and_pop(&self, dest: &Worker<T>, limit: usize) -> Steal<T> {
+ assert!(limit > 0);
let mut head;
let mut block;
let mut offset;
@@ -1639,15 +1795,15 @@
if (head >> SHIFT) / LAP != (tail >> SHIFT) / LAP {
new_head |= HAS_NEXT;
// We can steal all tasks till the end of the block.
- advance = (BLOCK_CAP - offset).min(MAX_BATCH + 1);
+ advance = (BLOCK_CAP - offset).min(limit);
} else {
let len = (tail - head) >> SHIFT;
// Steal half of the available tasks.
- advance = ((len + 1) / 2).min(MAX_BATCH + 1);
+ advance = ((len + 1) / 2).min(limit);
}
} else {
// We can steal all tasks till the end of the block.
- advance = (BLOCK_CAP - offset).min(MAX_BATCH + 1);
+ advance = (BLOCK_CAP - offset).min(limit);
}
new_head += advance << SHIFT;
diff --git a/src/lib.rs b/src/lib.rs
index b696b5f..16bc728 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -95,7 +95,6 @@
rust_2018_idioms,
unreachable_pub
)]
-#![allow(clippy::question_mark)] // https://github.com/rust-lang/rust-clippy/issues/8281
#![cfg_attr(not(feature = "std"), no_std)]
use cfg_if::cfg_if;
