intrusive_collections/
adapter.rs

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
9use crate::link_ops::LinkOps;
10use 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`.
41pub 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]
100macro_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]
166macro_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            fn clone(&self) -> Self {
183                *self
184            }
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            pub fn new() -> Self {
200                Self::NEW
201            }
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            unsafe fn get_value(&self, link: <Self::LinkOps as $crate::LinkOps>::LinkPtr) -> *const <Self::PointerOps as $crate::PointerOps>::Value {
210                $crate::container_of!(link.as_ptr(), $value, $field)
211            }
212            #[inline]
213            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                let ptr = (value as *const u8).add($crate::offset_of!($value, $field));
217                core::ptr::NonNull::new_unchecked(ptr as *mut _)
218            }
219            #[inline]
220            fn link_ops(&self) -> &Self::LinkOps {
221                &self.link_ops
222            }
223            #[inline]
224            fn link_ops_mut(&mut self) -> &mut Self::LinkOps {
225                &mut self.link_ops
226            }
227            #[inline]
228            fn pointer_ops(&self) -> &Self::PointerOps {
229                &self.pointer_ops
230            }
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)]
269mod 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}
intrusive_collections/adapter.rs

intrusive_collections/
adapter.rs
