Snap for 8249732 from e6ce8ba539a0986e2ee611e4a715b4aaa7c0ae5b to tm-release
Change-Id: Ie507af1dd7e3e8da0f0647a9f4dc0f7be758a6ee
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
index b9b4b0c..f08b5a6 100644
--- a/.cargo_vcs_info.json
+++ b/.cargo_vcs_info.json
@@ -1,5 +1,6 @@
{
"git": {
- "sha1": "2d89ebc111d7c3955dba15faec57ad4dbcd49d26"
- }
-}
+ "sha1": "9a11a214a4efe29f61202ffa92e110b466e516c3"
+ },
+ "path_in_vcs": ""
+}
\ No newline at end of file
diff --git a/Android.bp b/Android.bp
index 6cf914d..e056d9c 100644
--- a/Android.bp
+++ b/Android.bp
@@ -45,7 +45,7 @@
host_supported: true,
crate_name: "intrusive_collections",
cargo_env_compat: true,
- cargo_pkg_version: "0.9.2",
+ cargo_pkg_version: "0.9.3",
srcs: ["src/lib.rs"],
edition: "2018",
features: [
diff --git a/Cargo.toml b/Cargo.toml
index 1b8f9ee..49d1efd 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -3,17 +3,16 @@
# When uploading crates to the registry Cargo will automatically
# "normalize" Cargo.toml files for maximal compatibility
# with all versions of Cargo and also rewrite `path` dependencies
-# to registry (e.g., crates.io) dependencies
+# to registry (e.g., crates.io) dependencies.
#
-# If you believe there's an error in this file please file an
-# issue against the rust-lang/cargo repository. If you're
-# editing this file be aware that the upstream Cargo.toml
-# will likely look very different (and much more reasonable)
+# If you are reading this file be aware that the original Cargo.toml
+# will likely look very different (and much more reasonable).
+# See Cargo.toml.orig for the original contents.
[package]
edition = "2018"
name = "intrusive-collections"
-version = "0.9.2"
+version = "0.9.3"
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/Cargo.toml.orig b/Cargo.toml.orig
index ea5413d..909123e 100644
--- a/Cargo.toml.orig
+++ b/Cargo.toml.orig
@@ -1,6 +1,6 @@
[package]
name = "intrusive-collections"
-version = "0.9.2"
+version = "0.9.3"
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 3ddaf5c..0439bd7 100644
--- a/METADATA
+++ b/METADATA
@@ -7,13 +7,13 @@
}
url {
type: ARCHIVE
- value: "https://static.crates.io/crates/intrusive-collections/intrusive-collections-0.9.2.crate"
+ value: "https://static.crates.io/crates/intrusive-collections/intrusive-collections-0.9.3.crate"
}
- version: "0.9.2"
+ version: "0.9.3"
license_type: NOTICE
last_upgrade_date {
- year: 2021
- month: 7
- day: 15
+ year: 2022
+ month: 3
+ day: 1
}
}
diff --git a/src/lib.rs b/src/lib.rs
index b873910..3352ba9 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -292,14 +292,18 @@
pub use crate::adapter::Adapter;
pub use crate::key_adapter::KeyAdapter;
pub use crate::link_ops::{DefaultLinkOps, LinkOps};
+pub use crate::linked_list::AtomicLink as LinkedListAtomicLink;
pub use crate::linked_list::Link as LinkedListLink;
pub use crate::linked_list::LinkedList;
pub use crate::pointer_ops::{DefaultPointerOps, PointerOps};
+pub use crate::rbtree::AtomicLink as RBTreeAtomicLink;
pub use crate::rbtree::Link as RBTreeLink;
pub use crate::rbtree::RBTree;
+pub use crate::singly_linked_list::AtomicLink as SinglyLinkedListAtomicLink;
pub use crate::singly_linked_list::Link as SinglyLinkedListLink;
pub use crate::singly_linked_list::SinglyLinkedList;
pub use crate::unsafe_ref::UnsafeRef;
+pub use crate::xor_linked_list::AtomicLink as XorLinkedListAtomicLink;
pub use crate::xor_linked_list::Link as XorLinkedListLink;
pub use crate::xor_linked_list::XorLinkedList;
pub use memoffset::offset_of;
diff --git a/src/linked_list.rs b/src/linked_list.rs
index efda06a..7b8e5fb 100644
--- a/src/linked_list.rs
+++ b/src/linked_list.rs
@@ -10,7 +10,8 @@
use core::cell::Cell;
use core::fmt;
-use core::ptr::NonNull;
+use core::ptr::{null_mut, NonNull};
+use core::sync::atomic::{AtomicPtr, Ordering};
use crate::link_ops::{self, DefaultLinkOps};
use crate::pointer_ops::PointerOps;
@@ -267,6 +268,243 @@
}
}
+// =============================================================================
+// AtomicLink
+// =============================================================================
+
+/// Intrusive atomic link that allows an object to be inserted into a
+/// `LinkedList`. This link allows the structure to be shared between threads.
+#[repr(align(2))]
+pub struct AtomicLink {
+ next: AtomicPtr<AtomicLink>,
+ prev: Cell<Option<NonNull<AtomicLink>>>,
+}
+
+// Use a special value to indicate an unlinked node
+const ATOMIC_UNLINKED_MARKER_PTR: *mut AtomicLink = 1 as *mut AtomicLink;
+
+// Use a special value to indicate an unlinked node
+const ATOMIC_UNLINKED_MARKER: Option<NonNull<AtomicLink>> =
+ unsafe { Some(NonNull::new_unchecked(ATOMIC_UNLINKED_MARKER_PTR)) };
+
+impl AtomicLink {
+ /// Creates a new `AtomicLink`.
+ #[inline]
+ pub const fn new() -> AtomicLink {
+ Self {
+ next: AtomicPtr::new(ATOMIC_UNLINKED_MARKER_PTR),
+ prev: Cell::new(ATOMIC_UNLINKED_MARKER),
+ }
+ }
+
+ /// Checks whether the `AtomicLink` is linked into a `LinkedList`.
+ #[inline]
+ pub fn is_linked(&self) -> bool {
+ self.next.load(Ordering::Relaxed) != ATOMIC_UNLINKED_MARKER_PTR
+ }
+
+ /// Forcibly unlinks an object from a `LinkedList`.
+ ///
+ /// # Safety
+ ///
+ /// It is undefined behavior to call this function while still linked into a
+ /// `LinkedList`. The only situation where this function is useful is
+ /// after calling `fast_clear` on a `LinkedList`, since this clears
+ /// the collection without marking the nodes as unlinked.
+ #[inline]
+ pub unsafe fn force_unlink(&self) {
+ self.next
+ .store(ATOMIC_UNLINKED_MARKER_PTR, Ordering::Release)
+ }
+
+ /// Access the `next` pointer in an exclusive context.
+ ///
+ /// # Safety
+ ///
+ /// This can only be called after `acquire_link` has been succesfully called.
+ #[inline]
+ unsafe fn next_exclusive(&self) -> &Cell<Option<NonNull<AtomicLink>>> {
+ // This is safe because currently AtomicPtr<AtomicLink> has the same representation Cell<Option<NonNull<AtomicLink>>>.
+ core::mem::transmute(&self.next)
+ }
+}
+
+impl DefaultLinkOps for AtomicLink {
+ type Ops = AtomicLinkOps;
+
+ const NEW: Self::Ops = AtomicLinkOps;
+}
+
+// An object containing a link can be sent to another thread since `acquire_link` is atomic.
+unsafe impl Send for AtomicLink {}
+
+// An object containing a link can be shared between threads since `acquire_link` is atomic.
+unsafe impl Sync for AtomicLink {}
+
+impl Clone for AtomicLink {
+ #[inline]
+ fn clone(&self) -> AtomicLink {
+ AtomicLink::new()
+ }
+}
+
+impl Default for AtomicLink {
+ #[inline]
+ fn default() -> AtomicLink {
+ AtomicLink::new()
+ }
+}
+
+// Provide an implementation of Debug so that structs containing a link can
+// still derive Debug.
+impl fmt::Debug for AtomicLink {
+ #[inline]
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ // There isn't anything sensible to print here except whether the link
+ // is currently in a list.
+ if self.is_linked() {
+ write!(f, "linked")
+ } else {
+ write!(f, "unlinked")
+ }
+ }
+}
+
+// =============================================================================
+// AtomicLinkOps
+// =============================================================================
+
+/// Default `AtomicLinkOps` implementation for `LinkedList`.
+#[derive(Clone, Copy, Default)]
+pub struct AtomicLinkOps;
+
+unsafe impl link_ops::LinkOps for AtomicLinkOps {
+ type LinkPtr = NonNull<AtomicLink>;
+
+ #[inline]
+ unsafe fn acquire_link(&mut self, ptr: Self::LinkPtr) -> bool {
+ ptr.as_ref()
+ .next
+ .compare_exchange(
+ ATOMIC_UNLINKED_MARKER_PTR,
+ null_mut(),
+ Ordering::Acquire,
+ Ordering::Relaxed,
+ )
+ .is_ok()
+ }
+
+ #[inline]
+ unsafe fn release_link(&mut self, ptr: Self::LinkPtr) {
+ ptr.as_ref()
+ .next
+ .store(ATOMIC_UNLINKED_MARKER_PTR, Ordering::Release)
+ }
+}
+
+unsafe impl LinkedListOps for AtomicLinkOps {
+ #[inline]
+ unsafe fn next(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
+ ptr.as_ref().next_exclusive().get()
+ }
+
+ #[inline]
+ unsafe fn prev(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
+ ptr.as_ref().prev.get()
+ }
+
+ #[inline]
+ unsafe fn set_next(&mut self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>) {
+ ptr.as_ref().next_exclusive().set(next);
+ }
+
+ #[inline]
+ unsafe fn set_prev(&mut self, ptr: Self::LinkPtr, prev: Option<Self::LinkPtr>) {
+ ptr.as_ref().prev.set(prev);
+ }
+}
+
+unsafe impl SinglyLinkedListOps for AtomicLinkOps {
+ #[inline]
+ unsafe fn next(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
+ ptr.as_ref().next_exclusive().get()
+ }
+
+ #[inline]
+ unsafe fn set_next(&mut self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>) {
+ ptr.as_ref().next_exclusive().set(next);
+ }
+}
+
+unsafe impl XorLinkedListOps for AtomicLinkOps {
+ #[inline]
+ unsafe fn next(
+ &self,
+ ptr: Self::LinkPtr,
+ prev: Option<Self::LinkPtr>,
+ ) -> Option<Self::LinkPtr> {
+ let packed = ptr
+ .as_ref()
+ .next_exclusive()
+ .get()
+ .map(|x| x.as_ptr() as usize)
+ .unwrap_or(0);
+ let raw = packed ^ prev.map(|x| x.as_ptr() as usize).unwrap_or(0);
+ NonNull::new(raw as *mut _)
+ }
+
+ #[inline]
+ unsafe fn prev(
+ &self,
+ ptr: Self::LinkPtr,
+ next: Option<Self::LinkPtr>,
+ ) -> Option<Self::LinkPtr> {
+ let packed = ptr
+ .as_ref()
+ .next_exclusive()
+ .get()
+ .map(|x| x.as_ptr() as usize)
+ .unwrap_or(0);
+ let raw = packed ^ next.map(|x| x.as_ptr() as usize).unwrap_or(0);
+ NonNull::new(raw as *mut _)
+ }
+
+ #[inline]
+ unsafe fn set(
+ &mut self,
+ ptr: Self::LinkPtr,
+ prev: Option<Self::LinkPtr>,
+ next: Option<Self::LinkPtr>,
+ ) {
+ let new_packed = prev.map(|x| x.as_ptr() as usize).unwrap_or(0)
+ ^ next.map(|x| x.as_ptr() as usize).unwrap_or(0);
+
+ let new_next = NonNull::new(new_packed as *mut _);
+ ptr.as_ref().next_exclusive().set(new_next);
+ }
+
+ #[inline]
+ unsafe fn replace_next_or_prev(
+ &mut self,
+ ptr: Self::LinkPtr,
+ old: Option<Self::LinkPtr>,
+ new: Option<Self::LinkPtr>,
+ ) {
+ let packed = ptr
+ .as_ref()
+ .next_exclusive()
+ .get()
+ .map(|x| x.as_ptr() as usize)
+ .unwrap_or(0);
+ let new_packed = packed
+ ^ old.map(|x| x.as_ptr() as usize).unwrap_or(0)
+ ^ new.map(|x| x.as_ptr() as usize).unwrap_or(0);
+
+ let new_next = NonNull::new(new_packed as *mut _);
+ ptr.as_ref().next_exclusive().set(new_next);
+ }
+}
+
#[inline]
unsafe fn link_between<T: LinkedListOps>(
link_ops: &mut T,
diff --git a/src/rbtree.rs b/src/rbtree.rs
index ad8f861..f9facfc 100644
--- a/src/rbtree.rs
+++ b/src/rbtree.rs
@@ -14,6 +14,7 @@
use core::fmt;
use core::mem;
use core::ptr::NonNull;
+use core::sync::atomic::{self, AtomicUsize};
use crate::Bound::{self, Excluded, Included, Unbounded};
@@ -358,6 +359,293 @@
}
}
+// =============================================================================
+// AtomicLink
+// =============================================================================
+
+/// Intrusive link that allows an object to be inserted into a
+/// `RBTree`. This link allows the structure to be shared between threads.
+
+#[repr(align(2))]
+pub struct AtomicLink {
+ left: Cell<Option<NonNull<AtomicLink>>>,
+ right: Cell<Option<NonNull<AtomicLink>>>,
+ parent_color: AtomicUsize,
+}
+
+impl AtomicLink {
+ #[inline]
+ /// Creates a new `AtomicLink`.
+ pub const fn new() -> AtomicLink {
+ AtomicLink {
+ left: Cell::new(None),
+ right: Cell::new(None),
+ parent_color: AtomicUsize::new(UNLINKED_MARKER),
+ }
+ }
+
+ /// Checks whether the `AtomicLink` is linked into a `RBTree`.
+ #[inline]
+ pub fn is_linked(&self) -> bool {
+ self.parent_color.load(atomic::Ordering::Relaxed) != UNLINKED_MARKER
+ }
+
+ /// Forcibly unlinks an object from a `RBTree`.
+ ///
+ /// # Safety
+ ///
+ /// It is undefined behavior to call this function while still linked into a
+ /// `RBTree`. The only situation where this function is useful is
+ /// after calling `fast_clear` on a `RBTree`, since this clears
+ /// the collection without marking the nodes as unlinked.
+ #[inline]
+ pub unsafe fn force_unlink(&self) {
+ self.parent_color
+ .store(UNLINKED_MARKER, atomic::Ordering::Release);
+ }
+
+ /// Access `parent_color` in an exclusive context.
+ ///
+ /// # Safety
+ ///
+ /// This can only be called after `acquire_link` has been succesfully called.
+ #[inline]
+ unsafe fn parent_color_exclusive(&self) -> &Cell<usize> {
+ // This is safe because currently AtomicUsize has the same representation Cell<usize>.
+ core::mem::transmute(&self.parent_color)
+ }
+}
+
+impl DefaultLinkOps for AtomicLink {
+ type Ops = AtomicLinkOps;
+
+ const NEW: Self::Ops = AtomicLinkOps;
+}
+
+// An object containing a link can be sent to another thread since `acquire_link` is atomic.
+unsafe impl Send for AtomicLink {}
+
+// An object containing a link can be shared between threads since `acquire_link` is atomic.
+unsafe impl Sync for AtomicLink {}
+
+impl Clone for AtomicLink {
+ #[inline]
+ fn clone(&self) -> AtomicLink {
+ AtomicLink::new()
+ }
+}
+
+impl Default for AtomicLink {
+ #[inline]
+ fn default() -> AtomicLink {
+ AtomicLink::new()
+ }
+}
+
+// Provide an implementation of Debug so that structs containing a link can
+// still derive Debug.
+impl fmt::Debug for AtomicLink {
+ #[inline]
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ // There isn't anything sensible to print here except whether the link
+ // is currently in a list.
+ if self.is_linked() {
+ write!(f, "linked")
+ } else {
+ write!(f, "unlinked")
+ }
+ }
+}
+
+// =============================================================================
+// AtomicLinkOps
+// =============================================================================
+
+/// Default `LinkOps` implementation for `RBTree`.
+#[derive(Clone, Copy, Default)]
+pub struct AtomicLinkOps;
+
+impl AtomicLinkOps {
+ #[inline]
+ unsafe fn set_parent_color(
+ self,
+ ptr: <Self as link_ops::LinkOps>::LinkPtr,
+ parent: Option<<Self as link_ops::LinkOps>::LinkPtr>,
+ color: Color,
+ ) {
+ assert!(mem::align_of::<Link>() >= 2);
+ let bit = match color {
+ Color::Red => 0,
+ Color::Black => 1,
+ };
+ let parent_usize = parent.map(|x| x.as_ptr() as usize).unwrap_or(0);
+ ptr.as_ref()
+ .parent_color_exclusive()
+ .set((parent_usize & !1) | bit);
+ }
+}
+
+const LINKED_DEFAULT_VALUE: usize = 1;
+
+unsafe impl link_ops::LinkOps for AtomicLinkOps {
+ type LinkPtr = NonNull<AtomicLink>;
+
+ #[inline]
+ unsafe fn acquire_link(&mut self, ptr: Self::LinkPtr) -> bool {
+ ptr.as_ref()
+ .parent_color
+ .compare_exchange(
+ UNLINKED_MARKER,
+ LINKED_DEFAULT_VALUE,
+ atomic::Ordering::Acquire,
+ atomic::Ordering::Relaxed,
+ )
+ .is_ok()
+ }
+
+ #[inline]
+ unsafe fn release_link(&mut self, ptr: Self::LinkPtr) {
+ ptr.as_ref()
+ .parent_color
+ .store(UNLINKED_MARKER, atomic::Ordering::Release)
+ }
+}
+
+unsafe impl RBTreeOps for AtomicLinkOps {
+ #[inline]
+ unsafe fn left(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
+ ptr.as_ref().left.get()
+ }
+
+ #[inline]
+ unsafe fn right(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
+ ptr.as_ref().right.get()
+ }
+
+ #[inline]
+ unsafe fn parent(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
+ let parent_usize = ptr.as_ref().parent_color_exclusive().get() & !1;
+ NonNull::new(parent_usize as *mut AtomicLink)
+ }
+
+ #[inline]
+ unsafe fn color(&self, ptr: Self::LinkPtr) -> Color {
+ if ptr.as_ref().parent_color_exclusive().get() & 1 == 1 {
+ Color::Black
+ } else {
+ Color::Red
+ }
+ }
+
+ #[inline]
+ unsafe fn set_left(&mut self, ptr: Self::LinkPtr, left: Option<Self::LinkPtr>) {
+ ptr.as_ref().left.set(left);
+ }
+
+ #[inline]
+ unsafe fn set_right(&mut self, ptr: Self::LinkPtr, right: Option<Self::LinkPtr>) {
+ ptr.as_ref().right.set(right);
+ }
+
+ #[inline]
+ unsafe fn set_parent(&mut self, ptr: Self::LinkPtr, parent: Option<Self::LinkPtr>) {
+ self.set_parent_color(ptr, parent, self.color(ptr));
+ }
+
+ #[inline]
+ unsafe fn set_color(&mut self, ptr: Self::LinkPtr, color: Color) {
+ self.set_parent_color(ptr, self.parent(ptr), color);
+ }
+}
+
+unsafe impl SinglyLinkedListOps for AtomicLinkOps {
+ #[inline]
+ unsafe fn next(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
+ self.right(ptr)
+ }
+
+ #[inline]
+ unsafe fn set_next(&mut self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>) {
+ self.set_right(ptr, next);
+ }
+}
+
+unsafe impl LinkedListOps for AtomicLinkOps {
+ #[inline]
+ unsafe fn next(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
+ self.right(ptr)
+ }
+
+ #[inline]
+ unsafe fn prev(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
+ self.left(ptr)
+ }
+
+ #[inline]
+ unsafe fn set_next(&mut self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>) {
+ self.set_right(ptr, next);
+ }
+
+ #[inline]
+ unsafe fn set_prev(&mut self, ptr: Self::LinkPtr, prev: Option<Self::LinkPtr>) {
+ self.set_left(ptr, prev);
+ }
+}
+
+unsafe impl XorLinkedListOps for AtomicLinkOps {
+ #[inline]
+ unsafe fn next(
+ &self,
+ ptr: Self::LinkPtr,
+ prev: Option<Self::LinkPtr>,
+ ) -> Option<Self::LinkPtr> {
+ let packed = self.right(ptr).map(|x| x.as_ptr() as usize).unwrap_or(0);
+ let raw = packed ^ prev.map(|x| x.as_ptr() as usize).unwrap_or(0);
+ NonNull::new(raw as *mut _)
+ }
+
+ #[inline]
+ unsafe fn prev(
+ &self,
+ ptr: Self::LinkPtr,
+ next: Option<Self::LinkPtr>,
+ ) -> Option<Self::LinkPtr> {
+ let packed = self.right(ptr).map(|x| x.as_ptr() as usize).unwrap_or(0);
+ let raw = packed ^ next.map(|x| x.as_ptr() as usize).unwrap_or(0);
+ NonNull::new(raw as *mut _)
+ }
+
+ #[inline]
+ unsafe fn set(
+ &mut self,
+ ptr: Self::LinkPtr,
+ prev: Option<Self::LinkPtr>,
+ next: Option<Self::LinkPtr>,
+ ) {
+ let new_packed = prev.map(|x| x.as_ptr() as usize).unwrap_or(0)
+ ^ next.map(|x| x.as_ptr() as usize).unwrap_or(0);
+
+ let new_next = NonNull::new(new_packed as *mut _);
+ self.set_right(ptr, new_next);
+ }
+
+ #[inline]
+ unsafe fn replace_next_or_prev(
+ &mut self,
+ ptr: Self::LinkPtr,
+ old: Option<Self::LinkPtr>,
+ new: Option<Self::LinkPtr>,
+ ) {
+ let packed = self.right(ptr).map(|x| x.as_ptr() as usize).unwrap_or(0);
+ let new_packed = packed
+ ^ old.map(|x| x.as_ptr() as usize).unwrap_or(0)
+ ^ new.map(|x| x.as_ptr() as usize).unwrap_or(0);
+
+ let new_next = NonNull::new(new_packed as *mut _);
+ self.set_right(ptr, new_next);
+ }
+}
+
#[inline]
unsafe fn is_left_child<T: RBTreeOps>(link_ops: &T, ptr: T::LinkPtr, parent: T::LinkPtr) -> bool {
link_ops.left(parent) == Some(ptr)
diff --git a/src/singly_linked_list.rs b/src/singly_linked_list.rs
index 29feeab..fa93e10 100644
--- a/src/singly_linked_list.rs
+++ b/src/singly_linked_list.rs
@@ -10,7 +10,8 @@
use core::cell::Cell;
use core::fmt;
-use core::ptr::NonNull;
+use core::ptr::{null_mut, NonNull};
+use core::sync::atomic::{AtomicPtr, Ordering};
use crate::link_ops::{self, DefaultLinkOps};
use crate::pointer_ops::PointerOps;
@@ -230,6 +231,213 @@
}
}
+// =============================================================================
+// AtomicLink
+// =============================================================================
+
+/// Intrusive link that allows an object to be inserted into a
+/// `SinglyLinkedList`. This link allows the structure to be shared between threads.
+#[repr(align(2))]
+pub struct AtomicLink {
+ next: AtomicPtr<AtomicLink>,
+}
+const ATOMIC_UNLINKED_MARKER: *mut AtomicLink = 1 as *mut AtomicLink;
+
+impl AtomicLink {
+ /// Creates a new `AtomicLink`.
+ #[inline]
+ pub const fn new() -> AtomicLink {
+ AtomicLink {
+ next: AtomicPtr::new(ATOMIC_UNLINKED_MARKER),
+ }
+ }
+
+ /// Checks whether the `AtomicLink` is linked into a `SinglyLinkedList`.
+ #[inline]
+ pub fn is_linked(&self) -> bool {
+ self.next.load(Ordering::Relaxed) != ATOMIC_UNLINKED_MARKER
+ }
+
+ /// Forcibly unlinks an object from a `SinglyLinkedList`.
+ ///
+ /// # Safety
+ ///
+ /// It is undefined behavior to call this function while still linked into a
+ /// `SinglyLinkedList`. The only situation where this function is useful is
+ /// after calling `fast_clear` on a `SinglyLinkedList`, since this clears
+ /// the collection without marking the nodes as unlinked.
+ #[inline]
+ pub unsafe fn force_unlink(&self) {
+ self.next.store(ATOMIC_UNLINKED_MARKER, Ordering::Release);
+ }
+
+ /// Access the `next` pointer in an exclusive context.
+ ///
+ /// # Safety
+ ///
+ /// This can only be called after `acquire_link` has been succesfully called.
+ #[inline]
+ unsafe fn next_exclusive(&self) -> &Cell<Option<NonNull<AtomicLink>>> {
+ // This is safe because currently AtomicPtr<AtomicLink> has the same representation Cell<Option<NonNull<AtomicLink>>>.
+ core::mem::transmute(&self.next)
+ }
+}
+
+impl DefaultLinkOps for AtomicLink {
+ type Ops = AtomicLinkOps;
+
+ const NEW: Self::Ops = AtomicLinkOps;
+}
+
+// An object containing a link can be sent to another thread since `acquire_link` is atomic.
+unsafe impl Send for AtomicLink {}
+
+// An object containing a link can be shared between threads since `acquire_link` is atomic.
+unsafe impl Sync for AtomicLink {}
+
+impl Clone for AtomicLink {
+ #[inline]
+ fn clone(&self) -> AtomicLink {
+ AtomicLink::new()
+ }
+}
+
+impl Default for AtomicLink {
+ #[inline]
+ fn default() -> AtomicLink {
+ AtomicLink::new()
+ }
+}
+
+// Provide an implementation of Debug so that structs containing a link can
+// still derive Debug.
+impl fmt::Debug for AtomicLink {
+ #[inline]
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ // There isn't anything sensible to print here except whether the link
+ // is currently in a list.
+ if self.is_linked() {
+ write!(f, "linked")
+ } else {
+ write!(f, "unlinked")
+ }
+ }
+}
+
+// =============================================================================
+// AtomicLinkOps
+// =============================================================================
+
+/// Default `AtomicLinkOps` implementation for `LinkedList`.
+#[derive(Clone, Copy, Default)]
+pub struct AtomicLinkOps;
+
+unsafe impl link_ops::LinkOps for AtomicLinkOps {
+ type LinkPtr = NonNull<AtomicLink>;
+
+ #[inline]
+ unsafe fn acquire_link(&mut self, ptr: Self::LinkPtr) -> bool {
+ ptr.as_ref()
+ .next
+ .compare_exchange(
+ ATOMIC_UNLINKED_MARKER,
+ null_mut(),
+ Ordering::Acquire,
+ Ordering::Relaxed,
+ )
+ .is_ok()
+ }
+
+ #[inline]
+ unsafe fn release_link(&mut self, ptr: Self::LinkPtr) {
+ ptr.as_ref()
+ .next
+ .store(ATOMIC_UNLINKED_MARKER, Ordering::Release)
+ }
+}
+
+unsafe impl SinglyLinkedListOps for AtomicLinkOps {
+ #[inline]
+ unsafe fn next(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
+ ptr.as_ref().next_exclusive().get()
+ }
+
+ #[inline]
+ unsafe fn set_next(&mut self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>) {
+ ptr.as_ref().next_exclusive().set(next);
+ }
+}
+
+unsafe impl XorLinkedListOps for AtomicLinkOps {
+ #[inline]
+ unsafe fn next(
+ &self,
+ ptr: Self::LinkPtr,
+ prev: Option<Self::LinkPtr>,
+ ) -> Option<Self::LinkPtr> {
+ let packed = ptr
+ .as_ref()
+ .next_exclusive()
+ .get()
+ .map(|x| x.as_ptr() as usize)
+ .unwrap_or(0);
+ let raw = packed ^ prev.map(|x| x.as_ptr() as usize).unwrap_or(0);
+
+ NonNull::new(raw as *mut _)
+ }
+
+ #[inline]
+ unsafe fn prev(
+ &self,
+ ptr: Self::LinkPtr,
+ next: Option<Self::LinkPtr>,
+ ) -> Option<Self::LinkPtr> {
+ let packed = ptr
+ .as_ref()
+ .next_exclusive()
+ .get()
+ .map(|x| x.as_ptr() as usize)
+ .unwrap_or(0);
+ let raw = packed ^ next.map(|x| x.as_ptr() as usize).unwrap_or(0);
+ NonNull::new(raw as *mut _)
+ }
+
+ #[inline]
+ unsafe fn set(
+ &mut self,
+ ptr: Self::LinkPtr,
+ prev: Option<Self::LinkPtr>,
+ next: Option<Self::LinkPtr>,
+ ) {
+ let new_packed = prev.map(|x| x.as_ptr() as usize).unwrap_or(0)
+ ^ next.map(|x| x.as_ptr() as usize).unwrap_or(0);
+
+ let new_next = NonNull::new(new_packed as *mut _);
+ ptr.as_ref().next_exclusive().set(new_next);
+ }
+
+ #[inline]
+ unsafe fn replace_next_or_prev(
+ &mut self,
+ ptr: Self::LinkPtr,
+ old: Option<Self::LinkPtr>,
+ new: Option<Self::LinkPtr>,
+ ) {
+ let packed = ptr
+ .as_ref()
+ .next_exclusive()
+ .get()
+ .map(|x| x.as_ptr() as usize)
+ .unwrap_or(0);
+ let new_packed = packed
+ ^ old.map(|x| x.as_ptr() as usize).unwrap_or(0)
+ ^ new.map(|x| x.as_ptr() as usize).unwrap_or(0);
+
+ let new_next = NonNull::new(new_packed as *mut _);
+ ptr.as_ref().next_exclusive().set(new_next);
+ }
+}
+
#[inline]
unsafe fn link_between<T: SinglyLinkedListOps>(
link_ops: &mut T,
diff --git a/src/xor_linked_list.rs b/src/xor_linked_list.rs
index 4e53ff4..cb0e177 100644
--- a/src/xor_linked_list.rs
+++ b/src/xor_linked_list.rs
@@ -14,6 +14,7 @@
use core::cell::Cell;
use core::fmt;
use core::ptr::NonNull;
+use core::sync::atomic::{AtomicUsize, Ordering};
use crate::link_ops::{self, DefaultLinkOps};
use crate::pointer_ops::PointerOps;
@@ -255,6 +256,197 @@
}
}
+// =============================================================================
+// AtomicLink
+// =============================================================================
+
+/// Intrusive link that allows an object to be inserted into a
+/// `XorLinkedList`. This link allows the structure to be shared between threads.
+#[repr(align(2))]
+pub struct AtomicLink {
+ packed: AtomicUsize,
+}
+
+impl AtomicLink {
+ /// Creates a new `Link`.
+ #[inline]
+ pub const fn new() -> AtomicLink {
+ AtomicLink {
+ packed: AtomicUsize::new(UNLINKED_MARKER),
+ }
+ }
+
+ /// Checks whether the `Link` is linked into a `XorLinkedList`.
+ #[inline]
+ pub fn is_linked(&self) -> bool {
+ self.packed.load(core::sync::atomic::Ordering::Relaxed) != UNLINKED_MARKER
+ }
+
+ /// Forcibly unlinks an object from a `XorLinkedList`.
+ ///
+ /// # Safety
+ ///
+ /// It is undefined behavior to call this function while still linked into a
+ /// `XorLinkedList`. The only situation where this function is useful is
+ /// after calling `fast_clear` on a `XorLinkedList`, since this clears
+ /// the collection without marking the nodes as unlinked.
+ #[inline]
+ pub unsafe fn force_unlink(&self) {
+ self.packed.store(UNLINKED_MARKER, Ordering::Release);
+ }
+
+ /// Access the `packed` pointer in an exclusive context.
+ ///
+ /// # Safety
+ ///
+ /// This can only be called after `acquire_link` has been succesfully called.
+ #[inline]
+ unsafe fn packed_exclusive(&self) -> &Cell<usize> {
+ // This is safe because currently AtomicUsize has the same representation Cell<usize>.
+ core::mem::transmute(&self.packed)
+ }
+}
+
+impl DefaultLinkOps for AtomicLink {
+ type Ops = AtomicLinkOps;
+
+ const NEW: Self::Ops = AtomicLinkOps;
+}
+
+// An object containing a link can be sent to another thread since `acquire_link` is atomic.
+unsafe impl Send for AtomicLink {}
+
+// An object containing a link can be shared between threads since `acquire_link` is atomic.
+unsafe impl Sync for AtomicLink {}
+
+impl Clone for AtomicLink {
+ #[inline]
+ fn clone(&self) -> AtomicLink {
+ AtomicLink::new()
+ }
+}
+
+impl Default for AtomicLink {
+ #[inline]
+ fn default() -> AtomicLink {
+ AtomicLink::new()
+ }
+}
+
+// Provide an implementation of Debug so that structs containing a link can
+// still derive Debug.
+impl fmt::Debug for AtomicLink {
+ #[inline]
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ // There isn't anything sensible to print here except whether the link
+ // is currently in a list.
+ if self.is_linked() {
+ write!(f, "linked")
+ } else {
+ write!(f, "unlinked")
+ }
+ }
+}
+
+// =============================================================================
+// AtomicLinkOps
+// =============================================================================
+
+/// Default `AtomicLinkOps` implementation for `LinkedList`.
+#[derive(Clone, Copy, Default)]
+pub struct AtomicLinkOps;
+
+const LINKED_DEFAULT_VALUE: usize = 0;
+
+unsafe impl link_ops::LinkOps for AtomicLinkOps {
+ type LinkPtr = NonNull<AtomicLink>;
+
+ #[inline]
+ unsafe fn acquire_link(&mut self, ptr: Self::LinkPtr) -> bool {
+ ptr.as_ref()
+ .packed
+ .compare_exchange(
+ UNLINKED_MARKER,
+ LINKED_DEFAULT_VALUE,
+ Ordering::Acquire,
+ Ordering::Relaxed,
+ )
+ .is_ok()
+ }
+
+ #[inline]
+ unsafe fn release_link(&mut self, ptr: Self::LinkPtr) {
+ ptr.as_ref()
+ .packed
+ .store(UNLINKED_MARKER, Ordering::Release)
+ }
+}
+
+unsafe impl XorLinkedListOps for AtomicLinkOps {
+ #[inline]
+ unsafe fn next(
+ &self,
+ ptr: Self::LinkPtr,
+ prev: Option<Self::LinkPtr>,
+ ) -> Option<Self::LinkPtr> {
+ let raw =
+ ptr.as_ref().packed_exclusive().get() ^ prev.map(|x| x.as_ptr() as usize).unwrap_or(0);
+ NonNull::new(raw as *mut _)
+ }
+
+ #[inline]
+ unsafe fn prev(
+ &self,
+ ptr: Self::LinkPtr,
+ next: Option<Self::LinkPtr>,
+ ) -> Option<Self::LinkPtr> {
+ let raw =
+ ptr.as_ref().packed_exclusive().get() ^ next.map(|x| x.as_ptr() as usize).unwrap_or(0);
+ NonNull::new(raw as *mut _)
+ }
+
+ #[inline]
+ unsafe fn set(
+ &mut self,
+ ptr: Self::LinkPtr,
+ prev: Option<Self::LinkPtr>,
+ next: Option<Self::LinkPtr>,
+ ) {
+ let new_packed = prev.map(|x| x.as_ptr() as usize).unwrap_or(0)
+ ^ next.map(|x| x.as_ptr() as usize).unwrap_or(0);
+ ptr.as_ref().packed_exclusive().set(new_packed);
+ }
+
+ #[inline]
+ unsafe fn replace_next_or_prev(
+ &mut self,
+ ptr: Self::LinkPtr,
+ old: Option<Self::LinkPtr>,
+ new: Option<Self::LinkPtr>,
+ ) {
+ let new_packed = ptr.as_ref().packed_exclusive().get()
+ ^ old.map(|x| x.as_ptr() as usize).unwrap_or(0)
+ ^ new.map(|x| x.as_ptr() as usize).unwrap_or(0);
+
+ ptr.as_ref().packed_exclusive().set(new_packed);
+ }
+}
+
+unsafe impl SinglyLinkedListOps for AtomicLinkOps {
+ #[inline]
+ unsafe fn next(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
+ let raw = ptr.as_ref().packed_exclusive().get();
+ NonNull::new(raw as *mut _)
+ }
+
+ #[inline]
+ unsafe fn set_next(&mut self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>) {
+ ptr.as_ref()
+ .packed_exclusive()
+ .set(next.map(|x| x.as_ptr() as usize).unwrap_or(0));
+ }
+}
+
#[inline]
unsafe fn link_between<T: XorLinkedListOps>(
link_ops: &mut T,