diff options
author | Android Build Coastguard Worker <android-build-coastguard-worker@google.com> | 2023-07-07 04:43:37 +0000 |
---|---|---|
committer | Android Build Coastguard Worker <android-build-coastguard-worker@google.com> | 2023-07-07 04:43:37 +0000 |
commit | 71614aae52cf6c416de09d46a772dbcf09669207 (patch) | |
tree | 6661fde618cb39349154f39f024a54e7f424928a | |
parent | a4949ebcd4d6ed9fe6ae6b77ca3f0c9919f03fab (diff) | |
parent | 5ff96d26043478e5a2016f668f796f159df3ddfe (diff) | |
download | intrusive-collections-android14-mainline-art-release.tar.gz |
Snap for 10453563 from 5ff96d26043478e5a2016f668f796f159df3ddfe to mainline-art-releaseaml_art_341711000aml_art_341615020aml_art_341514450aml_art_341514410aml_art_341411300aml_art_341311100aml_art_341110110aml_art_341110060aml_art_341010050aml_art_340915060android14-mainline-art-release
Change-Id: Ic17d86444db9ab982b7d883a3438b40eed55a408
-rw-r--r-- | .cargo_vcs_info.json | 2 | ||||
-rw-r--r-- | .github/workflows/ci.yml | 2 | ||||
-rw-r--r-- | Android.bp | 4 | ||||
-rw-r--r-- | Cargo.toml | 18 | ||||
-rw-r--r-- | Cargo.toml.orig | 4 | ||||
-rw-r--r-- | METADATA | 14 | ||||
-rw-r--r-- | TEST_MAPPING | 21 | ||||
-rw-r--r-- | src/lib.rs | 6 | ||||
-rw-r--r-- | src/linked_list.rs | 18 | ||||
-rw-r--r-- | src/rbtree.rs | 65 | ||||
-rw-r--r-- | src/singly_linked_list.rs | 26 | ||||
-rw-r--r-- | src/xor_linked_list.rs | 18 |
12 files changed, 126 insertions, 72 deletions
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json index f08b5a6..b0613bc 100644 --- a/.cargo_vcs_info.json +++ b/.cargo_vcs_info.json @@ -1,6 +1,6 @@ { "git": { - "sha1": "9a11a214a4efe29f61202ffa92e110b466e516c3" + "sha1": "5b1d6a12c6eef1c94a94e5493cfb730edeee2ca2" }, "path_in_vcs": "" }
\ No newline at end of file diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml index 10c7d3a..420045e 100644 --- a/.github/workflows/ci.yml +++ b/.github/workflows/ci.yml @@ -8,7 +8,7 @@ jobs: strategy: fail-fast: false matrix: - rust: [1.39.0, stable, beta, nightly] + rust: [1.56.1, stable, beta, nightly] steps: - name: Checkout uses: actions/checkout@v2 @@ -45,7 +45,7 @@ rust_library { host_supported: true, crate_name: "intrusive_collections", cargo_env_compat: true, - cargo_pkg_version: "0.9.3", + cargo_pkg_version: "0.9.5", srcs: ["src/lib.rs"], edition: "2018", features: [ @@ -59,4 +59,6 @@ rust_library { "//apex_available:platform", "com.android.virt", ], + product_available: true, + vendor_available: true, } @@ -12,17 +12,27 @@ [package] edition = "2018" name = "intrusive-collections" -version = "0.9.3" +version = "0.9.5" authors = ["Amanieu d'Antras <amanieu@gmail.com>"] description = "Intrusive collections for Rust (linked list and red-black tree)" documentation = "https://docs.rs/intrusive-collections" readme = "README.md" -keywords = ["intrusive", "no_std", "list", "rbtree"] -categories = ["data-structures", "no-std"] +keywords = [ + "intrusive", + "no_std", + "list", + "rbtree", +] +categories = [ + "data-structures", + "no-std", +] license = "Apache-2.0/MIT" repository = "https://github.com/Amanieu/intrusive-rs" + [dependencies.memoffset] -version = "0.5.4" +version = "0.8" + [dev-dependencies.rand] version = "0.8.4" diff --git a/Cargo.toml.orig b/Cargo.toml.orig index 909123e..5bd16b0 100644 --- a/Cargo.toml.orig +++ b/Cargo.toml.orig @@ -1,6 +1,6 @@ [package] name = "intrusive-collections" -version = "0.9.3" +version = "0.9.5" authors = ["Amanieu d'Antras <amanieu@gmail.com>"] description = "Intrusive collections for Rust (linked list and red-black tree)" documentation = "https://docs.rs/intrusive-collections" @@ -17,7 +17,7 @@ alloc = [] default = ["alloc"] [dependencies] -memoffset = "0.5.4" +memoffset = "0.8" [dev-dependencies] rand = "0.8.4" @@ -1,3 +1,7 @@ +# This project was upgraded with external_updater. +# Usage: tools/external_updater/updater.sh update rust/crates/intrusive-collections +# For more info, check https://cs.android.com/android/platform/superproject/+/master:tools/external_updater/README.md + name: "intrusive-collections" description: "Intrusive collections for Rust (linked list and red-black tree)" third_party { @@ -7,13 +11,13 @@ third_party { } url { type: ARCHIVE - value: "https://static.crates.io/crates/intrusive-collections/intrusive-collections-0.9.3.crate" + value: "https://static.crates.io/crates/intrusive-collections/intrusive-collections-0.9.5.crate" } - version: "0.9.3" + version: "0.9.5" license_type: NOTICE last_upgrade_date { - year: 2022 - month: 3 - day: 1 + year: 2023 + month: 2 + day: 16 } } diff --git a/TEST_MAPPING b/TEST_MAPPING index fc8ec65..c727841 100644 --- a/TEST_MAPPING +++ b/TEST_MAPPING @@ -1,25 +1,8 @@ // Generated by update_crate_tests.py for tests that depend on this crate. { - "presubmit": [ + "imports": [ { - "name": "ZipFuseTest" - }, - { - "name": "authfs_device_test_src_lib" - }, - { - "name": "virtualizationservice_device_test" - } - ], - "presubmit-rust": [ - { - "name": "ZipFuseTest" - }, - { - "name": "authfs_device_test_src_lib" - }, - { - "name": "virtualizationservice_device_test" + "path": "packages/modules/Virtualization/virtualizationmanager" } ] } @@ -268,7 +268,11 @@ #![warn(rust_2018_idioms)] #![no_std] #![cfg_attr(feature = "nightly", feature(const_fn_trait_bound))] -#![allow(clippy::declare_interior_mutable_const, clippy::collapsible_if)] +#![allow( + clippy::declare_interior_mutable_const, + clippy::collapsible_if, + clippy::collapsible_else_if +)] #[cfg(feature = "alloc")] extern crate alloc; diff --git a/src/linked_list.rs b/src/linked_list.rs index 7b8e5fb..efcdb8a 100644 --- a/src/linked_list.rs +++ b/src/linked_list.rs @@ -1052,6 +1052,16 @@ where list } } + + /// Consumes `CursorMut` and returns a reference to the object that + /// the cursor is currently pointing to. Unlike [get](Self::get), + /// the returned reference's lifetime is tied to `LinkedList`'s lifetime. + /// + /// This returns None if the cursor is currently pointing to the null object. + #[inline] + pub fn into_ref(self) -> Option<&'a <A::PointerOps as PointerOps>::Value> { + Some(unsafe { &*self.list.adapter.get_value(self.current?) }) + } } // ============================================================================= @@ -1812,10 +1822,10 @@ mod tests { l1.cursor_mut().insert_before(b.clone()); l1.cursor_mut().insert_before(c.clone()); l1.cursor_mut().insert_before(d.clone()); - l2.cursor_mut().insert_after(a.clone()); - l2.cursor_mut().insert_after(b.clone()); - l2.cursor_mut().insert_after(c.clone()); - l2.cursor_mut().insert_after(d.clone()); + l2.cursor_mut().insert_after(a); + l2.cursor_mut().insert_after(b); + l2.cursor_mut().insert_after(c); + l2.cursor_mut().insert_after(d); assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 2, 3, 4]); assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), [4, 3, 2, 1]); } diff --git a/src/rbtree.rs b/src/rbtree.rs index f9facfc..87badec 100644 --- a/src/rbtree.rs +++ b/src/rbtree.rs @@ -856,7 +856,6 @@ unsafe fn post_insert<T: RBTreeOps>( x = link_ops.parent(x).unwrap_unchecked(); link_ops.set_color(x, Color::Red); rotate_right(link_ops, x, root); - break; } else { let y = link_ops.left(grandparent); if let Some(y) = y { @@ -882,8 +881,8 @@ unsafe fn post_insert<T: RBTreeOps>( x = link_ops.parent(x).unwrap_unchecked(); link_ops.set_color(x, Color::Red); rotate_left(link_ops, x, root); - break; } + break; } } @@ -1414,6 +1413,16 @@ where } } } + + /// Consumes `CursorMut` and returns a reference to the object that + /// the cursor is currently pointing to. Unlike [get](Self::get), + /// the returned reference's lifetime is tied to `RBTree`'s lifetime. + /// + /// This returns None if the cursor is currently pointing to the null object. + #[inline] + pub fn into_ref(self) -> Option<&'a <A::PointerOps as PointerOps>::Value> { + Some(unsafe { &*self.tree.adapter.get_value(self.current?) }) + } } impl<'a, A: for<'b> KeyAdapter<'b>> CursorMut<'a, A> @@ -1721,9 +1730,10 @@ where /// If multiple elements with an identical key are found then an arbitrary /// one is returned. #[inline] - pub fn find<'a, Q: ?Sized + Ord>(&'a self, key: &Q) -> Cursor<'a, A> + pub fn find<'a, 'b, Q: ?Sized + Ord>(&'a self, key: &Q) -> Cursor<'a, A> where - <A as KeyAdapter<'a>>::Key: Borrow<Q>, + <A as KeyAdapter<'b>>::Key: Borrow<Q>, + 'a: 'b, { Cursor { current: self.find_internal(key), @@ -1737,9 +1747,10 @@ where /// If multiple elements with an identical key are found then an arbitrary /// one is returned. #[inline] - pub fn find_mut<'a, Q: ?Sized + Ord>(&'a mut self, key: &Q) -> CursorMut<'a, A> + pub fn find_mut<'a, 'b, Q: ?Sized + Ord>(&'a mut self, key: &Q) -> CursorMut<'a, A> where - <A as KeyAdapter<'a>>::Key: Borrow<Q>, + <A as KeyAdapter<'b>>::Key: Borrow<Q>, + 'a: 'b, { CursorMut { current: self.find_internal(key), @@ -1781,9 +1792,10 @@ where /// the given bound. If no such element is found then a null cursor is /// returned. #[inline] - pub fn lower_bound<'a, Q: ?Sized + Ord>(&'a self, bound: Bound<&Q>) -> Cursor<'a, A> + pub fn lower_bound<'a, 'b, Q: ?Sized + Ord>(&'a self, bound: Bound<&Q>) -> Cursor<'a, A> where - <A as KeyAdapter<'a>>::Key: Borrow<Q>, + <A as KeyAdapter<'b>>::Key: Borrow<Q>, + 'a: 'b, { Cursor { current: self.lower_bound_internal(bound), @@ -1795,9 +1807,13 @@ where /// above the given bound. If no such element is found then a null /// cursor is returned. #[inline] - pub fn lower_bound_mut<'a, Q: ?Sized + Ord>(&'a mut self, bound: Bound<&Q>) -> CursorMut<'a, A> + pub fn lower_bound_mut<'a, 'b, Q: ?Sized + Ord>( + &'a mut self, + bound: Bound<&Q>, + ) -> CursorMut<'a, A> where - <A as KeyAdapter<'a>>::Key: Borrow<Q>, + <A as KeyAdapter<'b>>::Key: Borrow<Q>, + 'a: 'b, { CursorMut { current: self.lower_bound_internal(bound), @@ -1839,9 +1855,10 @@ where /// the given bound. If no such element is found then a null cursor is /// returned. #[inline] - pub fn upper_bound<'a, Q: ?Sized + Ord>(&'a self, bound: Bound<&Q>) -> Cursor<'a, A> + pub fn upper_bound<'a, 'b, Q: ?Sized + Ord>(&'a self, bound: Bound<&Q>) -> Cursor<'a, A> where - <A as KeyAdapter<'a>>::Key: Borrow<Q>, + <A as KeyAdapter<'b>>::Key: Borrow<Q>, + 'a: 'b, { Cursor { current: self.upper_bound_internal(bound), @@ -1853,9 +1870,13 @@ where /// below the given bound. If no such element is found then a null /// cursor is returned. #[inline] - pub fn upper_bound_mut<'a, Q: ?Sized + Ord>(&'a mut self, bound: Bound<&Q>) -> CursorMut<'a, A> + pub fn upper_bound_mut<'a, 'b, Q: ?Sized + Ord>( + &'a mut self, + bound: Bound<&Q>, + ) -> CursorMut<'a, A> where - <A as KeyAdapter<'a>>::Key: Borrow<Q>, + <A as KeyAdapter<'b>>::Key: Borrow<Q>, + 'a: 'b, { CursorMut { current: self.upper_bound_internal(bound), @@ -2471,19 +2492,19 @@ mod tests { let b2 = make_obj(2); let c2 = make_obj(3); assert_eq!( - cur.replace_with(a2.clone()).unwrap().as_ref() as *const _, + cur.replace_with(a2).unwrap().as_ref() as *const _, a.as_ref() as *const _ ); assert!(!a.link.is_linked()); cur.move_next(); assert_eq!( - cur.replace_with(b2.clone()).unwrap().as_ref() as *const _, + cur.replace_with(b2).unwrap().as_ref() as *const _, b.as_ref() as *const _ ); assert!(!b.link.is_linked()); cur.move_next(); assert_eq!( - cur.replace_with(c2.clone()).unwrap().as_ref() as *const _, + cur.replace_with(c2).unwrap().as_ref() as *const _, c.as_ref() as *const _ ); assert!(!c.link.is_linked()); @@ -2542,7 +2563,7 @@ mod tests { for i in indices { t.insert(v[i].clone()); expected.push(v[i].value); - expected[..].sort(); + expected[..].sort_unstable(); assert_eq!(t.iter().map(|x| x.value).collect::<Vec<_>>(), expected); } @@ -2580,7 +2601,7 @@ mod tests { c.insert_before(v[i].clone()); } expected.push(v[i].value); - expected[..].sort(); + expected[..].sort_unstable(); assert_eq!(t.iter().map(|x| x.value).collect::<Vec<_>>(), expected); } @@ -2608,7 +2629,7 @@ mod tests { c.insert_after(v[i].clone()); } expected.push(v[i].value); - expected[..].sort(); + expected[..].sort_unstable(); assert_eq!(t.iter().map(|x| x.value).collect::<Vec<_>>(), expected); } } @@ -3025,9 +3046,9 @@ mod tests { let d = make_obj(4); let e = make_obj(5); let f = make_obj(6); - t.entry(&3).or_insert(c.clone()); + t.entry(&3).or_insert(c); t.entry(&2).or_insert(b.clone()); - t.entry(&1).or_insert(a.clone()); + t.entry(&1).or_insert(a); match t.entry(&2) { Entry::Vacant(_) => unreachable!(), diff --git a/src/singly_linked_list.rs b/src/singly_linked_list.rs index fa93e10..fb0618e 100644 --- a/src/singly_linked_list.rs +++ b/src/singly_linked_list.rs @@ -828,6 +828,16 @@ where list } } + + /// Consumes `CursorMut` and returns a reference to the object that + /// the cursor is currently pointing to. Unlike [get](Self::get), + /// the returned reference's lifetime is tied to `SinglyLinkedList`'s lifetime. + /// + /// This returns None if the cursor is currently pointing to the null object. + #[inline] + pub fn into_ref(self) -> Option<&'a <A::PointerOps as PointerOps>::Value> { + Some(unsafe { &*self.list.adapter.get_value(self.current?) }) + } } // ============================================================================= @@ -1322,10 +1332,10 @@ mod tests { let b = make_obj(2); let c = make_obj(3); let d = make_obj(4); - l1.cursor_mut().insert_after(d.clone()); - l1.cursor_mut().insert_after(c.clone()); - l1.cursor_mut().insert_after(b.clone()); - l1.cursor_mut().insert_after(a.clone()); + l1.cursor_mut().insert_after(d); + l1.cursor_mut().insert_after(c); + l1.cursor_mut().insert_after(b); + l1.cursor_mut().insert_after(a); assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 2, 3, 4]); assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), []); assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), []); @@ -1471,10 +1481,10 @@ mod tests { l1.cursor_mut().insert_after(c.clone()); l1.cursor_mut().insert_after(b.clone()); l1.cursor_mut().insert_after(a.clone()); - l2.cursor_mut().insert_after(a.clone()); - l2.cursor_mut().insert_after(b.clone()); - l2.cursor_mut().insert_after(c.clone()); - l2.cursor_mut().insert_after(d.clone()); + l2.cursor_mut().insert_after(a); + l2.cursor_mut().insert_after(b); + l2.cursor_mut().insert_after(c); + l2.cursor_mut().insert_after(d); assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 2, 3, 4]); assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), [4, 3, 2, 1]); } diff --git a/src/xor_linked_list.rs b/src/xor_linked_list.rs index cb0e177..d5c2ca3 100644 --- a/src/xor_linked_list.rs +++ b/src/xor_linked_list.rs @@ -1070,6 +1070,16 @@ where list } } + + /// Consumes `CursorMut` and returns a reference to the object that + /// the cursor is currently pointing to. Unlike [get](Self::get), + /// the returned reference's lifetime is tied to `XorLinkedList`'s lifetime. + /// + /// This returns None if the cursor is currently pointing to the null object. + #[inline] + pub fn into_ref(self) -> Option<&'a <A::PointerOps as PointerOps>::Value> { + Some(unsafe { &*self.list.adapter.get_value(self.current?) }) + } } // ============================================================================= @@ -1979,10 +1989,10 @@ mod tests { l1.cursor_mut().insert_before(b.clone()); l1.cursor_mut().insert_before(c.clone()); l1.cursor_mut().insert_before(d.clone()); - l2.cursor_mut().insert_after(a.clone()); - l2.cursor_mut().insert_after(b.clone()); - l2.cursor_mut().insert_after(c.clone()); - l2.cursor_mut().insert_after(d.clone()); + l2.cursor_mut().insert_after(a); + l2.cursor_mut().insert_after(b); + l2.cursor_mut().insert_after(c); + l2.cursor_mut().insert_after(d); assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 2, 3, 4]); assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), [4, 3, 2, 1]); } |