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`. get_value( &self, link: <Self::LinkOps as LinkOps>::LinkPtr, ) -> *const <Self::PointerOps as PointerOps>::Value55 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. get_link( &self, value: *const <Self::PointerOps as PointerOps>::Value, ) -> <Self::LinkOps as LinkOps>::LinkPtr65 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. link_ops(&self) -> &Self::LinkOps71 fn link_ops(&self) -> &Self::LinkOps; 72 73 /// Returns a reference to the mutable link operations. link_ops_mut(&mut self) -> &mut Self::LinkOps74 fn link_ops_mut(&mut self) -> &mut Self::LinkOps; 75 76 /// Returns a reference to the pointer converter. pointer_ops(&self) -> &Self::PointerOps77 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 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)] 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 } 282