Merge "Upgrade intrusive-collections to 0.9.4"main-16k-with-phones

10 files changed, 118 insertions, 49 deletions

diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
index f08b5a6..bc4673c 100644
--- a/.cargo_vcs_info.json
+++ b/.cargo_vcs_info.json
@@ -1,6 +1,6 @@
 {
   "git": {
-    "sha1": "9a11a214a4efe29f61202ffa92e110b466e516c3"
+    "sha1": "4a4e84da9bc2036abff041d521eb67589128119f"
   },
   "path_in_vcs": ""
 }
\ No newline at end of file
diff --git a/Android.bp b/Android.bp
index e056d9c..66915a7 100644
--- a/Android.bp
+++ b/Android.bp
@@ -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.4",
     srcs: ["src/lib.rs"],
     edition: "2018",
     features: [
diff --git a/Cargo.toml b/Cargo.toml
index 49d1efd..06da551 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -12,17 +12,27 @@
 [package]
 edition = "2018"
 name = "intrusive-collections"
-version = "0.9.3"
+version = "0.9.4"
 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"
+
 [dev-dependencies.rand]
 version = "0.8.4"
 
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
index 909123e..8e6dede 100644
--- a/Cargo.toml.orig
+++ b/Cargo.toml.orig
@@ -1,6 +1,6 @@
 [package]
 name = "intrusive-collections"
-version = "0.9.3"
+version = "0.9.4"
 authors = ["Amanieu d'Antras <amanieu@gmail.com>"]
 description = "Intrusive collections for Rust (linked list and red-black tree)"
 documentation = "https://docs.rs/intrusive-collections"
diff --git a/METADATA b/METADATA
index 0439bd7..c7229d6 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/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.4.crate"
   }
-  version: "0.9.3"
+  version: "0.9.4"
   license_type: NOTICE
   last_upgrade_date {
     year: 2022
-    month: 3
-    day: 1
+    month: 12
+    day: 12
   }
 }
diff --git a/src/lib.rs b/src/lib.rs
index 3352ba9..9063de6 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -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]);
     }