/rust/registry/src/index.crates.io-1949cf8c6b5b557f/intrusive-collections-0.9.6/src/adapter.rs

Source
// Copyright 2016 Amanieu d'Antras
// Copyright 2020 Amari Robinson
//
// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
// http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
// http://opensource.org/licenses/MIT>, at your option. This file may not be
// copied, modified, or distributed except according to those terms.

use crate::link_ops::LinkOps;
use crate::pointer_ops::PointerOps;

/// Trait for a adapter which allows a type to be inserted into an intrusive
/// collection.
///
/// `LinkOps` implements the collection-specific operations which
/// allows an object to be inserted into an intrusive collection. This type
/// needs to implement the appropriate trait for the collection type
/// (eg. `LinkedListOps` for inserting into a `LinkedList`).
/// `LinkOps` type may be stateful, allowing custom link types.
///
/// `PointerOps` implements the collection-specific pointer conversions which
/// allow an object to be inserted into an intrusive collection.
/// `PointerOps` type may be stateful, allowing custom pointer types.
///
/// A single object type may have multiple adapters, which allows it to be part
/// of multiple intrusive collections simultaneously.
///
/// In most cases you do not need to implement this trait manually: the
/// `intrusive_adapter!` macro will generate the necessary implementation for a
/// given type and its link field. However it is possible to implement it
/// manually if the intrusive link is not a direct field of the object type.
///
/// It is also possible to create stateful adapters.
/// This allows links and containers to be separated and avoids the need for objects to be modified to
/// contain a link.
///
/// # Safety
///
/// It must be possible to get back a reference to the container by passing a
/// pointer returned by `get_link` to `get_container`.
pub unsafe trait Adapter {
    /// Collection-specific link operations which allow an object to be inserted in
    /// an intrusive collection.
    type LinkOps: LinkOps;

    /// Collection-specific pointer conversions which allow an object to
    /// be inserted in an intrusive collection.
    type PointerOps: PointerOps;

    /// Gets a reference to an object from a reference to a link in that object.
    ///
    /// # Safety
    ///
    /// `link` must be a valid pointer previously returned by `get_link`.
    unsafe fn get_value(
        &self,
        link: <Self::LinkOps as LinkOps>::LinkPtr,
    ) -> *const <Self::PointerOps as PointerOps>::Value;

    /// Gets a reference to the link for the given object.
    ///
    /// # Safety
    ///
    /// `value` must be a valid pointer.
    unsafe fn get_link(
        &self,
        value: *const <Self::PointerOps as PointerOps>::Value,
    ) -> <Self::LinkOps as LinkOps>::LinkPtr;

    /// Returns a reference to the link operations.
    fn link_ops(&self) -> &Self::LinkOps;

    /// Returns a reference to the mutable link operations.
    fn link_ops_mut(&mut self) -> &mut Self::LinkOps;

    /// Returns a reference to the pointer converter.
    fn pointer_ops(&self) -> &Self::PointerOps;
}

/// Unsafe macro to get a raw pointer to an outer object from a pointer to one
/// of its fields.
///
/// # Examples
///
/// ```
/// use intrusive_collections::container_of;
///
/// struct S { x: u32, y: u32 };
/// let container = S { x: 1, y: 2 };
/// let field = &container.x;
/// let container2: *const S = unsafe { container_of!(field, S, x) };
/// assert_eq!(&container as *const S, container2);
/// ```
///
/// # Safety
///
/// This is unsafe because it assumes that the given expression is a valid
/// pointer to the specified field of some container type.
#[macro_export]
macro_rules! container_of {
    ($ptr:expr, $container:path, $field:ident) => {
        #[allow(clippy::cast_ptr_alignment)]
        {
            ($ptr as *const _ as *const u8).sub($crate::offset_of!($container, $field))
                as *const $container
        }
    };
}

/// Macro to generate an implementation of `Adapter` for a given set of types.
/// In particular this will automatically generate implementations of the
/// `get_value` and `get_link` methods for a given named field in a struct.
///
/// The basic syntax to create an adapter is:
///
/// ```rust,ignore
/// intrusive_adapter!(Adapter = Pointer: Value { link_field: LinkType });
/// ```
///
/// You can create a new instance of an adapter using the `new` method or the
/// `NEW` associated constant. The adapter also implements the `Default` trait.
///
/// # Generics
///
/// This macro supports generic arguments:
///
/// ```rust,ignore
/// intrusive_adapter!(
///     Adapter<'lifetime, Type, Type2> =
///         Pointer: Value {
///             link_field: LinkType
///         }
///         where
///             Type: Copy,
///             Type2: ?Sized + 'lifetime
///     );
/// ```
///
/// Note that due to macro parsing limitations, `T: Trait` bounds are not
/// supported in the generic argument list. You must list any trait bounds in
/// a separate `where` clause at the end of the macro.
///
/// # Examples
///
/// ```
/// use intrusive_collections::{LinkedListLink, RBTreeLink};
/// use intrusive_collections::intrusive_adapter;
///
/// pub struct Test {
///     link: LinkedListLink,
///     link2: RBTreeLink,
/// }
/// intrusive_adapter!(MyAdapter = Box<Test>: Test { link: LinkedListLink });
/// intrusive_adapter!(pub MyAdapter2 = Box<Test>: Test { link2: RBTreeLink });
/// intrusive_adapter!(pub(crate) MyAdapter3 = Box<Test>: Test { link2: RBTreeLink });
///
/// pub struct Test2<T>
///     where T: Clone + ?Sized
/// {
///     link: LinkedListLink,
///     val: T,
/// }
/// intrusive_adapter!(MyAdapter4<'a, T> = &'a Test2<T>: Test2<T> { link: LinkedListLink } where T: ?Sized + Clone + 'a);
/// ```
#[macro_export]
macro_rules! intrusive_adapter {
    (@impl
        $(#[$attr:meta])* $vis:vis $name:ident ($($args:tt),*)
        = $pointer:ty: $value:path { $field:ident: $link:ty } $($where_:tt)*
    ) => {
        #[allow(explicit_outlives_requirements)]
        $(#[$attr])*
        $vis struct $name<$($args),*> $($where_)* {
            link_ops: <$link as $crate::DefaultLinkOps>::Ops,
            pointer_ops: $crate::DefaultPointerOps<$pointer>,
        }
        unsafe impl<$($args),*> Send for $name<$($args),*> $($where_)* {}
        unsafe impl<$($args),*> Sync for $name<$($args),*> $($where_)* {}
        impl<$($args),*> Copy for $name<$($args),*> $($where_)* {}
        impl<$($args),*> Clone for $name<$($args),*> $($where_)* {
            #[inline]
            fn clone(&self) -> Self {
                *self
            }
        }
        impl<$($args),*> Default for $name<$($args),*> $($where_)* {
            #[inline]
            fn default() -> Self {
                Self::NEW
            }
        }
        #[allow(dead_code)]
        impl<$($args),*> $name<$($args),*> $($where_)* {
            pub const NEW: Self = $name {
                link_ops: <$link as $crate::DefaultLinkOps>::NEW,
                pointer_ops: $crate::DefaultPointerOps::<$pointer>::new(),
            };
            #[inline]
            pub fn new() -> Self {
                Self::NEW
            }
        }
        #[allow(dead_code, unsafe_code)]
        unsafe impl<$($args),*> $crate::Adapter for $name<$($args),*> $($where_)* {
            type LinkOps = <$link as $crate::DefaultLinkOps>::Ops;
            type PointerOps = $crate::DefaultPointerOps<$pointer>;

            #[inline]
            unsafe fn get_value(&self, link: <Self::LinkOps as $crate::LinkOps>::LinkPtr) -> *const <Self::PointerOps as $crate::PointerOps>::Value {
                $crate::container_of!(link.as_ptr(), $value, $field)
            }
            #[inline]
            unsafe fn get_link(&self, value: *const <Self::PointerOps as $crate::PointerOps>::Value) -> <Self::LinkOps as $crate::LinkOps>::LinkPtr {
                // We need to do this instead of just accessing the field directly
                // to strictly follow the stack borrow rules.
                let ptr = (value as *const u8).add($crate::offset_of!($value, $field));
                core::ptr::NonNull::new_unchecked(ptr as *mut _)
            }
            #[inline]
            fn link_ops(&self) -> &Self::LinkOps {
                &self.link_ops
            }
            #[inline]
            fn link_ops_mut(&mut self) -> &mut Self::LinkOps {
                &mut self.link_ops
            }
            #[inline]
            fn pointer_ops(&self) -> &Self::PointerOps {
                &self.pointer_ops
            }
        }
    };
    (@find_generic
        $(#[$attr:meta])* $vis:vis $name:ident ($($prev:tt)*) > $($rest:tt)*
    ) => {
        intrusive_adapter!(@impl
            $(#[$attr])* $vis $name ($($prev)*) $($rest)*
        );
    };
    (@find_generic
        $(#[$attr:meta])* $vis:vis $name:ident ($($prev:tt)*) $cur:tt $($rest:tt)*
    ) => {
        intrusive_adapter!(@find_generic
            $(#[$attr])* $vis $name ($($prev)* $cur) $($rest)*
        );
    };
    (@find_if_generic
        $(#[$attr:meta])* $vis:vis $name:ident < $($rest:tt)*
    ) => {
        intrusive_adapter!(@find_generic
            $(#[$attr])* $vis $name () $($rest)*
        );
    };
    (@find_if_generic
        $(#[$attr:meta])* $vis:vis $name:ident $($rest:tt)*
    ) => {
        intrusive_adapter!(@impl
            $(#[$attr])* $vis $name () $($rest)*
        );
    };
    ($(#[$attr:meta])* $vis:vis $name:ident $($rest:tt)*) => {
        intrusive_adapter!(@find_if_generic
            $(#[$attr])* $vis $name $($rest)*
        );
    };
}

#[cfg(test)]
mod tests {
    use crate::LinkedListLink;
    use std::rc::Rc;

    struct Obj {
        link: LinkedListLink,
    }

    intrusive_adapter! {
        /// Test doc comment
        ObjAdapter1 = Rc<Obj>: Obj { link: LinkedListLink }
    }
}

Coverage Report

Created: 2025-11-16 06:34

Line	Count	Source
1		// Copyright 2016 Amanieu d'Antras
2		// Copyright 2020 Amari Robinson
3		//
4		// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
5		// http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
6		// http://opensource.org/licenses/MIT>, at your option. This file may not be
7		// copied, modified, or distributed except according to those terms.
8
9		use crate::link_ops::LinkOps;
10		use crate::pointer_ops::PointerOps;
11
12		/// Trait for a adapter which allows a type to be inserted into an intrusive
13		/// collection.
14		///
15		/// `LinkOps` implements the collection-specific operations which
16		/// allows an object to be inserted into an intrusive collection. This type
17		/// needs to implement the appropriate trait for the collection type
18		/// (eg. `LinkedListOps` for inserting into a `LinkedList`).
19		/// `LinkOps` type may be stateful, allowing custom link types.
20		///
21		/// `PointerOps` implements the collection-specific pointer conversions which
22		/// allow an object to be inserted into an intrusive collection.
23		/// `PointerOps` type may be stateful, allowing custom pointer types.
24		///
25		/// A single object type may have multiple adapters, which allows it to be part
26		/// of multiple intrusive collections simultaneously.
27		///
28		/// In most cases you do not need to implement this trait manually: the
29		/// `intrusive_adapter!` macro will generate the necessary implementation for a
30		/// given type and its link field. However it is possible to implement it
31		/// manually if the intrusive link is not a direct field of the object type.
32		///
33		/// It is also possible to create stateful adapters.
34		/// This allows links and containers to be separated and avoids the need for objects to be modified to
35		/// contain a link.
36		///
37		/// # Safety
38		///
39		/// It must be possible to get back a reference to the container by passing a
40		/// pointer returned by `get_link` to `get_container`.
41		pub unsafe trait Adapter {
42		/// Collection-specific link operations which allow an object to be inserted in
43		/// an intrusive collection.
44		type LinkOps: LinkOps;
45
46		/// Collection-specific pointer conversions which allow an object to
47		/// be inserted in an intrusive collection.
48		type PointerOps: PointerOps;
49
50		/// Gets a reference to an object from a reference to a link in that object.
51		///
52		/// # Safety
53		///
54		/// `link` must be a valid pointer previously returned by `get_link`.
55		unsafe fn get_value(
56		&self,
57		link: <Self::LinkOps as LinkOps>::LinkPtr,
58		) -> *const <Self::PointerOps as PointerOps>::Value;
59
60		/// Gets a reference to the link for the given object.
61		///
62		/// # Safety
63		///
64		/// `value` must be a valid pointer.
65		unsafe fn get_link(
66		&self,
67		value: *const <Self::PointerOps as PointerOps>::Value,
68		) -> <Self::LinkOps as LinkOps>::LinkPtr;
69
70		/// Returns a reference to the link operations.
71		fn link_ops(&self) -> &Self::LinkOps;
72
73		/// Returns a reference to the mutable link operations.
74		fn link_ops_mut(&mut self) -> &mut Self::LinkOps;
75
76		/// Returns a reference to the pointer converter.
77		fn pointer_ops(&self) -> &Self::PointerOps;
78		}
79
80		/// Unsafe macro to get a raw pointer to an outer object from a pointer to one
81		/// of its fields.
82		///
83		/// # Examples
84		///
85		/// ```
86		/// use intrusive_collections::container_of;
87		///
88		/// struct S { x: u32, y: u32 };
89		/// let container = S { x: 1, y: 2 };
90		/// let field = &container.x;
91		/// let container2: *const S = unsafe { container_of!(field, S, x) };
92		/// assert_eq!(&container as *const S, container2);
93		/// ```
94		///
95		/// # Safety
96		///
97		/// This is unsafe because it assumes that the given expression is a valid
98		/// pointer to the specified field of some container type.
99		#[macro_export]
100		macro_rules! container_of {
101		($ptr:expr, $container:path, $field:ident) => {
102		#[allow(clippy::cast_ptr_alignment)]
103		{
104		($ptr as const _ as const u8).sub($crate::offset_of!($container, $field))
105		as *const $container
106		}
107		};
108		}
109
110		/// Macro to generate an implementation of `Adapter` for a given set of types.
111		/// In particular this will automatically generate implementations of the
112		/// `get_value` and `get_link` methods for a given named field in a struct.
113		///
114		/// The basic syntax to create an adapter is:
115		///
116		/// ```rust,ignore
117		/// intrusive_adapter!(Adapter = Pointer: Value { link_field: LinkType });
118		/// ```
119		///
120		/// You can create a new instance of an adapter using the `new` method or the
121		/// `NEW` associated constant. The adapter also implements the `Default` trait.
122		///
123		/// # Generics
124		///
125		/// This macro supports generic arguments:
126		///
127		/// ```rust,ignore
128		/// intrusive_adapter!(
129		/// Adapter<'lifetime, Type, Type2> =
130		/// Pointer: Value {
131		/// link_field: LinkType
132		/// }
133		/// where
134		/// Type: Copy,
135		/// Type2: ?Sized + 'lifetime
136		/// );
137		/// ```
138		///
139		/// Note that due to macro parsing limitations, `T: Trait` bounds are not
140		/// supported in the generic argument list. You must list any trait bounds in
141		/// a separate `where` clause at the end of the macro.
142		///
143		/// # Examples
144		///
145		/// ```
146		/// use intrusive_collections::{LinkedListLink, RBTreeLink};
147		/// use intrusive_collections::intrusive_adapter;
148		///
149		/// pub struct Test {
150		/// link: LinkedListLink,
151		/// link2: RBTreeLink,
152		/// }
153		/// intrusive_adapter!(MyAdapter = Box<Test>: Test { link: LinkedListLink });
154		/// intrusive_adapter!(pub MyAdapter2 = Box<Test>: Test { link2: RBTreeLink });
155		/// intrusive_adapter!(pub(crate) MyAdapter3 = Box<Test>: Test { link2: RBTreeLink });
156		///
157		/// pub struct Test2<T>
158		/// where T: Clone + ?Sized
159		/// {
160		/// link: LinkedListLink,
161		/// val: T,
162		/// }
163		/// intrusive_adapter!(MyAdapter4<'a, T> = &'a Test2<T>: Test2<T> { link: LinkedListLink } where T: ?Sized + Clone + 'a);
164		/// ```
165		#[macro_export]
166		macro_rules! intrusive_adapter {
167		(@impl
168		$(#[$attr:meta])* $vis:vis $name:ident ($($args:tt),*)
169		= $pointer:ty: $value:path { $field:ident: $link:ty } $($where_:tt)*
170		) => {
171		#[allow(explicit_outlives_requirements)]
172		$(#[$attr])*
173		$vis struct $name<$($args),> $($where_) {
174		link_ops: <$link as $crate::DefaultLinkOps>::Ops,
175		pointer_ops: $crate::DefaultPointerOps<$pointer>,
176		}
177		unsafe impl<$($args),> Send for $name<$($args),> $($where_)* {}
178		unsafe impl<$($args),> Sync for $name<$($args),> $($where_)* {}
179		impl<$($args),> Copy for $name<$($args),> $($where_)* {}
180		impl<$($args),> Clone for $name<$($args),> $($where_)* {
181		#[inline]
182	0	fn clone(&self) -> Self {
183	0	*self
184	0	}
185		}
186		impl<$($args),> Default for $name<$($args),> $($where_)* {
187		#[inline]
188		fn default() -> Self {
189		Self::NEW
190		}
191		}
192		#[allow(dead_code)]
193		impl<$($args),> $name<$($args),> $($where_)* {
194		pub const NEW: Self = $name {
195		link_ops: <$link as $crate::DefaultLinkOps>::NEW,
196		pointer_ops: $crate::DefaultPointerOps::<$pointer>::new(),
197		};
198		#[inline]
199	992	pub fn new() -> Self {
200	992	Self::NEW
201	992	}
202		}
203		#[allow(dead_code, unsafe_code)]
204		unsafe impl<$($args),> $crate::Adapter for $name<$($args),> $($where_)* {
205		type LinkOps = <$link as $crate::DefaultLinkOps>::Ops;
206		type PointerOps = $crate::DefaultPointerOps<$pointer>;
207
208		#[inline]
209	0	unsafe fn get_value(&self, link: <Self::LinkOps as $crate::LinkOps>::LinkPtr) -> *const <Self::PointerOps as $crate::PointerOps>::Value {
210	0	$crate::container_of!(link.as_ptr(), $value, $field)
211	0	}
212		#[inline]
213	0	unsafe fn get_link(&self, value: *const <Self::PointerOps as $crate::PointerOps>::Value) -> <Self::LinkOps as $crate::LinkOps>::LinkPtr {
214		// We need to do this instead of just accessing the field directly
215		// to strictly follow the stack borrow rules.
216	0	let ptr = (value as *const u8).add($crate::offset_of!($value, $field));
217	0	core::ptr::NonNull::new_unchecked(ptr as *mut _)
218	0	}
219		#[inline]
220	0	fn link_ops(&self) -> &Self::LinkOps {
221	0	&self.link_ops
222	0	}
223		#[inline]
224	0	fn link_ops_mut(&mut self) -> &mut Self::LinkOps {
225	0	&mut self.link_ops
226	0	} Unexecuted instantiation: <cros_async::sync::waiter::WaiterAdapter as intrusive_collections::adapter::Adapter>::link_ops_mut Unexecuted instantiation: <cros_async::sync::waiter::WaiterAdapter as intrusive_collections::adapter::Adapter>::link_ops_mut
227		#[inline]
228	0	fn pointer_ops(&self) -> &Self::PointerOps {
229	0	&self.pointer_ops
230	0	}
231		}
232		};
233		(@find_generic
234		$(#[$attr:meta])* $vis:vis $name:ident ($($prev:tt)) > $($rest:tt)
235		) => {
236		intrusive_adapter!(@impl
237		$(#[$attr])* $vis $name ($($prev)) $($rest)
238		);
239		};
240		(@find_generic
241		$(#[$attr:meta])* $vis:vis $name:ident ($($prev:tt)) $cur:tt $($rest:tt)
242		) => {
243		intrusive_adapter!(@find_generic
244		$(#[$attr])* $vis $name ($($prev)* $cur) $($rest)*
245		);
246		};
247		(@find_if_generic
248		$(#[$attr:meta])* $vis:vis $name:ident < $($rest:tt)*
249		) => {
250		intrusive_adapter!(@find_generic
251		$(#[$attr])* $vis $name () $($rest)*
252		);
253		};
254		(@find_if_generic
255		$(#[$attr:meta])* $vis:vis $name:ident $($rest:tt)*
256		) => {
257		intrusive_adapter!(@impl
258		$(#[$attr])* $vis $name () $($rest)*
259		);
260		};
261		($(#[$attr:meta])* $vis:vis $name:ident $($rest:tt)*) => {
262		intrusive_adapter!(@find_if_generic
263		$(#[$attr])* $vis $name $($rest)*
264		);
265		};
266		}
267
268		#[cfg(test)]
269		mod tests {
270		use crate::LinkedListLink;
271		use std::rc::Rc;
272
273		struct Obj {
274		link: LinkedListLink,
275		}
276
277		intrusive_adapter! {
278		/// Test doc comment
279		ObjAdapter1 = Rc<Obj>: Obj { link: LinkedListLink }
280		}
281		}