1 // SPDX-License-Identifier: GPL-2.0 1 // SPDX-License-Identifier: GPL-2.0
2 2
3 // Copyright (C) 2024 Google LLC. 3 // Copyright (C) 2024 Google LLC.
4 4
5 //! A linked list implementation. 5 //! A linked list implementation.
6 6
7 use crate::init::PinInit; 7 use crate::init::PinInit;
8 use crate::sync::ArcBorrow; 8 use crate::sync::ArcBorrow;
9 use crate::types::Opaque; 9 use crate::types::Opaque;
10 use core::iter::{DoubleEndedIterator, FusedIte 10 use core::iter::{DoubleEndedIterator, FusedIterator};
11 use core::marker::PhantomData; 11 use core::marker::PhantomData;
12 use core::ptr; 12 use core::ptr;
13 13
14 mod impl_list_item_mod; 14 mod impl_list_item_mod;
15 pub use self::impl_list_item_mod::{ 15 pub use self::impl_list_item_mod::{
16 impl_has_list_links, impl_has_list_links_s 16 impl_has_list_links, impl_has_list_links_self_ptr, impl_list_item, HasListLinks, HasSelfPtr,
17 }; 17 };
18 18
19 mod arc; 19 mod arc;
20 pub use self::arc::{impl_list_arc_safe, Atomic 20 pub use self::arc::{impl_list_arc_safe, AtomicTracker, ListArc, ListArcSafe, TryNewListArc};
21 21
22 mod arc_field; 22 mod arc_field;
23 pub use self::arc_field::{define_list_arc_fiel 23 pub use self::arc_field::{define_list_arc_field_getter, ListArcField};
24 24
25 /// A linked list. 25 /// A linked list.
26 /// 26 ///
27 /// All elements in this linked list will be [ 27 /// All elements in this linked list will be [`ListArc`] references to the value. Since a value can
28 /// only have one `ListArc` (for each pair of 28 /// only have one `ListArc` (for each pair of prev/next pointers), this ensures that the same
29 /// prev/next pointers are not used for severa 29 /// prev/next pointers are not used for several linked lists.
30 /// 30 ///
31 /// # Invariants 31 /// # Invariants
32 /// 32 ///
33 /// * If the list is empty, then `first` is nu 33 /// * If the list is empty, then `first` is null. Otherwise, `first` points at the `ListLinks`
34 /// field of the first element in the list. 34 /// field of the first element in the list.
35 /// * All prev/next pointers in `ListLinks` fi 35 /// * All prev/next pointers in `ListLinks` fields of items in the list are valid and form a cycle.
36 /// * For every item in the list, the list own 36 /// * For every item in the list, the list owns the associated [`ListArc`] reference and has
37 /// exclusive access to the `ListLinks` fiel 37 /// exclusive access to the `ListLinks` field.
38 pub struct List<T: ?Sized + ListItem<ID>, cons 38 pub struct List<T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
39 first: *mut ListLinksFields, 39 first: *mut ListLinksFields,
40 _ty: PhantomData<ListArc<T, ID>>, 40 _ty: PhantomData<ListArc<T, ID>>,
41 } 41 }
42 42
43 // SAFETY: This is a container of `ListArc<T, 43 // SAFETY: This is a container of `ListArc<T, ID>`, and access to the container allows the same
44 // type of access to the `ListArc<T, ID>` elem 44 // type of access to the `ListArc<T, ID>` elements.
45 unsafe impl<T, const ID: u64> Send for List<T, 45 unsafe impl<T, const ID: u64> Send for List<T, ID>
46 where 46 where
47 ListArc<T, ID>: Send, 47 ListArc<T, ID>: Send,
48 T: ?Sized + ListItem<ID>, 48 T: ?Sized + ListItem<ID>,
49 { 49 {
50 } 50 }
51 // SAFETY: This is a container of `ListArc<T, 51 // SAFETY: This is a container of `ListArc<T, ID>`, and access to the container allows the same
52 // type of access to the `ListArc<T, ID>` elem 52 // type of access to the `ListArc<T, ID>` elements.
53 unsafe impl<T, const ID: u64> Sync for List<T, 53 unsafe impl<T, const ID: u64> Sync for List<T, ID>
54 where 54 where
55 ListArc<T, ID>: Sync, 55 ListArc<T, ID>: Sync,
56 T: ?Sized + ListItem<ID>, 56 T: ?Sized + ListItem<ID>,
57 { 57 {
58 } 58 }
59 59
60 /// Implemented by types where a [`ListArc<Sel 60 /// Implemented by types where a [`ListArc<Self>`] can be inserted into a [`List`].
61 /// 61 ///
62 /// # Safety 62 /// # Safety
63 /// 63 ///
64 /// Implementers must ensure that they provide 64 /// Implementers must ensure that they provide the guarantees documented on methods provided by
65 /// this trait. 65 /// this trait.
66 /// 66 ///
67 /// [`ListArc<Self>`]: ListArc 67 /// [`ListArc<Self>`]: ListArc
68 pub unsafe trait ListItem<const ID: u64 = 0>: 68 pub unsafe trait ListItem<const ID: u64 = 0>: ListArcSafe<ID> {
69 /// Views the [`ListLinks`] for this value 69 /// Views the [`ListLinks`] for this value.
70 /// 70 ///
71 /// # Guarantees 71 /// # Guarantees
72 /// 72 ///
73 /// If there is a previous call to `prepar 73 /// If there is a previous call to `prepare_to_insert` and there is no call to `post_remove`
74 /// since the most recent such call, then 74 /// since the most recent such call, then this returns the same pointer as the one returned by
75 /// the most recent call to `prepare_to_in 75 /// the most recent call to `prepare_to_insert`.
76 /// 76 ///
77 /// Otherwise, the returned pointer points 77 /// Otherwise, the returned pointer points at a read-only [`ListLinks`] with two null pointers.
78 /// 78 ///
79 /// # Safety 79 /// # Safety
80 /// 80 ///
81 /// The provided pointer must point at a v 81 /// The provided pointer must point at a valid value. (It need not be in an `Arc`.)
82 unsafe fn view_links(me: *const Self) -> * 82 unsafe fn view_links(me: *const Self) -> *mut ListLinks<ID>;
83 83
84 /// View the full value given its [`ListLi 84 /// View the full value given its [`ListLinks`] field.
85 /// 85 ///
86 /// Can only be used when the value is in 86 /// Can only be used when the value is in a list.
87 /// 87 ///
88 /// # Guarantees 88 /// # Guarantees
89 /// 89 ///
90 /// * Returns the same pointer as the one 90 /// * Returns the same pointer as the one passed to the most recent call to `prepare_to_insert`.
91 /// * The returned pointer is valid until 91 /// * The returned pointer is valid until the next call to `post_remove`.
92 /// 92 ///
93 /// # Safety 93 /// # Safety
94 /// 94 ///
95 /// * The provided pointer must originate 95 /// * The provided pointer must originate from the most recent call to `prepare_to_insert`, or
96 /// from a call to `view_links` that hap 96 /// from a call to `view_links` that happened after the most recent call to
97 /// `prepare_to_insert`. 97 /// `prepare_to_insert`.
98 /// * Since the most recent call to `prepa 98 /// * Since the most recent call to `prepare_to_insert`, the `post_remove` method must not have
99 /// been called. 99 /// been called.
100 unsafe fn view_value(me: *mut ListLinks<ID 100 unsafe fn view_value(me: *mut ListLinks<ID>) -> *const Self;
101 101
102 /// This is called when an item is inserte 102 /// This is called when an item is inserted into a [`List`].
103 /// 103 ///
104 /// # Guarantees 104 /// # Guarantees
105 /// 105 ///
106 /// The caller is granted exclusive access 106 /// The caller is granted exclusive access to the returned [`ListLinks`] until `post_remove` is
107 /// called. 107 /// called.
108 /// 108 ///
109 /// # Safety 109 /// # Safety
110 /// 110 ///
111 /// * The provided pointer must point at a 111 /// * The provided pointer must point at a valid value in an [`Arc`].
112 /// * Calls to `prepare_to_insert` and `po 112 /// * Calls to `prepare_to_insert` and `post_remove` on the same value must alternate.
113 /// * The caller must own the [`ListArc`] 113 /// * The caller must own the [`ListArc`] for this value.
114 /// * The caller must not give up ownershi 114 /// * The caller must not give up ownership of the [`ListArc`] unless `post_remove` has been
115 /// called after this call to `prepare_t 115 /// called after this call to `prepare_to_insert`.
116 /// 116 ///
117 /// [`Arc`]: crate::sync::Arc 117 /// [`Arc`]: crate::sync::Arc
118 unsafe fn prepare_to_insert(me: *const Sel 118 unsafe fn prepare_to_insert(me: *const Self) -> *mut ListLinks<ID>;
119 119
120 /// This undoes a previous call to `prepar 120 /// This undoes a previous call to `prepare_to_insert`.
121 /// 121 ///
122 /// # Guarantees 122 /// # Guarantees
123 /// 123 ///
124 /// The returned pointer is the pointer th 124 /// The returned pointer is the pointer that was originally passed to `prepare_to_insert`.
125 /// 125 ///
126 /// # Safety 126 /// # Safety
127 /// 127 ///
128 /// The provided pointer must be the point 128 /// The provided pointer must be the pointer returned by the most recent call to
129 /// `prepare_to_insert`. 129 /// `prepare_to_insert`.
130 unsafe fn post_remove(me: *mut ListLinks<I 130 unsafe fn post_remove(me: *mut ListLinks<ID>) -> *const Self;
131 } 131 }
132 132
133 #[repr(C)] 133 #[repr(C)]
134 #[derive(Copy, Clone)] 134 #[derive(Copy, Clone)]
135 struct ListLinksFields { 135 struct ListLinksFields {
136 next: *mut ListLinksFields, 136 next: *mut ListLinksFields,
137 prev: *mut ListLinksFields, 137 prev: *mut ListLinksFields,
138 } 138 }
139 139
140 /// The prev/next pointers for an item in a li 140 /// The prev/next pointers for an item in a linked list.
141 /// 141 ///
142 /// # Invariants 142 /// # Invariants
143 /// 143 ///
144 /// The fields are null if and only if this it 144 /// The fields are null if and only if this item is not in a list.
145 #[repr(transparent)] 145 #[repr(transparent)]
146 pub struct ListLinks<const ID: u64 = 0> { 146 pub struct ListLinks<const ID: u64 = 0> {
147 // This type is `!Unpin` for aliasing reas 147 // This type is `!Unpin` for aliasing reasons as the pointers are part of an intrusive linked
148 // list. 148 // list.
149 inner: Opaque<ListLinksFields>, 149 inner: Opaque<ListLinksFields>,
150 } 150 }
151 151
152 // SAFETY: The only way to access/modify the p 152 // SAFETY: The only way to access/modify the pointers inside of `ListLinks<ID>` is via holding the
153 // associated `ListArc<T, ID>`. Since that typ 153 // associated `ListArc<T, ID>`. Since that type correctly implements `Send`, it is impossible to
154 // move this an instance of this type to a dif 154 // move this an instance of this type to a different thread if the pointees are `!Send`.
155 unsafe impl<const ID: u64> Send for ListLinks< 155 unsafe impl<const ID: u64> Send for ListLinks<ID> {}
156 // SAFETY: The type is opaque so immutable ref 156 // SAFETY: The type is opaque so immutable references to a ListLinks are useless. Therefore, it's
157 // okay to have immutable access to a ListLink 157 // okay to have immutable access to a ListLinks from several threads at once.
158 unsafe impl<const ID: u64> Sync for ListLinks< 158 unsafe impl<const ID: u64> Sync for ListLinks<ID> {}
159 159
160 impl<const ID: u64> ListLinks<ID> { 160 impl<const ID: u64> ListLinks<ID> {
161 /// Creates a new initializer for this typ 161 /// Creates a new initializer for this type.
162 pub fn new() -> impl PinInit<Self> { 162 pub fn new() -> impl PinInit<Self> {
163 // INVARIANT: Pin-init initializers ca 163 // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will
164 // not be constructed in an `Arc` that 164 // not be constructed in an `Arc` that already has a `ListArc`.
165 ListLinks { 165 ListLinks {
166 inner: Opaque::new(ListLinksFields 166 inner: Opaque::new(ListLinksFields {
167 prev: ptr::null_mut(), 167 prev: ptr::null_mut(),
168 next: ptr::null_mut(), 168 next: ptr::null_mut(),
169 }), 169 }),
170 } 170 }
171 } 171 }
172 172
173 /// # Safety 173 /// # Safety
174 /// 174 ///
175 /// `me` must be dereferenceable. 175 /// `me` must be dereferenceable.
176 #[inline] 176 #[inline]
177 unsafe fn fields(me: *mut Self) -> *mut Li 177 unsafe fn fields(me: *mut Self) -> *mut ListLinksFields {
178 // SAFETY: The caller promises that th 178 // SAFETY: The caller promises that the pointer is valid.
179 unsafe { Opaque::raw_get(ptr::addr_of! 179 unsafe { Opaque::raw_get(ptr::addr_of!((*me).inner)) }
180 } 180 }
181 181
182 /// # Safety 182 /// # Safety
183 /// 183 ///
184 /// `me` must be dereferenceable. 184 /// `me` must be dereferenceable.
185 #[inline] 185 #[inline]
186 unsafe fn from_fields(me: *mut ListLinksFi 186 unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self {
187 me.cast() 187 me.cast()
188 } 188 }
189 } 189 }
190 190
191 /// Similar to [`ListLinks`], but also contain 191 /// Similar to [`ListLinks`], but also contains a pointer to the full value.
192 /// 192 ///
193 /// This type can be used instead of [`ListLin 193 /// This type can be used instead of [`ListLinks`] to support lists with trait objects.
194 #[repr(C)] 194 #[repr(C)]
195 pub struct ListLinksSelfPtr<T: ?Sized, const I 195 pub struct ListLinksSelfPtr<T: ?Sized, const ID: u64 = 0> {
196 /// The `ListLinks` field inside this valu 196 /// The `ListLinks` field inside this value.
197 /// 197 ///
198 /// This is public so that it can be used 198 /// This is public so that it can be used with `impl_has_list_links!`.
199 pub inner: ListLinks<ID>, 199 pub inner: ListLinks<ID>,
200 // UnsafeCell is not enough here because w 200 // UnsafeCell is not enough here because we use `Opaque::uninit` as a dummy value, and
201 // `ptr::null()` doesn't work for `T: ?Siz 201 // `ptr::null()` doesn't work for `T: ?Sized`.
202 self_ptr: Opaque<*const T>, 202 self_ptr: Opaque<*const T>,
203 } 203 }
204 204
205 // SAFETY: The fields of a ListLinksSelfPtr ca 205 // SAFETY: The fields of a ListLinksSelfPtr can be moved across thread boundaries.
206 unsafe impl<T: ?Sized + Send, const ID: u64> S 206 unsafe impl<T: ?Sized + Send, const ID: u64> Send for ListLinksSelfPtr<T, ID> {}
207 // SAFETY: The type is opaque so immutable ref 207 // SAFETY: The type is opaque so immutable references to a ListLinksSelfPtr are useless. Therefore,
208 // it's okay to have immutable access to a Lis 208 // it's okay to have immutable access to a ListLinks from several threads at once.
209 // 209 //
210 // Note that `inner` being a public field does 210 // Note that `inner` being a public field does not prevent this type from being opaque, since
211 // `inner` is a opaque type. 211 // `inner` is a opaque type.
212 unsafe impl<T: ?Sized + Sync, const ID: u64> S 212 unsafe impl<T: ?Sized + Sync, const ID: u64> Sync for ListLinksSelfPtr<T, ID> {}
213 213
214 impl<T: ?Sized, const ID: u64> ListLinksSelfPt 214 impl<T: ?Sized, const ID: u64> ListLinksSelfPtr<T, ID> {
215 /// The offset from the [`ListLinks`] to t 215 /// The offset from the [`ListLinks`] to the self pointer field.
216 pub const LIST_LINKS_SELF_PTR_OFFSET: usiz 216 pub const LIST_LINKS_SELF_PTR_OFFSET: usize = core::mem::offset_of!(Self, self_ptr);
217 217
218 /// Creates a new initializer for this typ 218 /// Creates a new initializer for this type.
219 pub fn new() -> impl PinInit<Self> { 219 pub fn new() -> impl PinInit<Self> {
220 // INVARIANT: Pin-init initializers ca 220 // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will
221 // not be constructed in an `Arc` that 221 // not be constructed in an `Arc` that already has a `ListArc`.
222 Self { 222 Self {
223 inner: ListLinks { 223 inner: ListLinks {
224 inner: Opaque::new(ListLinksFi 224 inner: Opaque::new(ListLinksFields {
225 prev: ptr::null_mut(), 225 prev: ptr::null_mut(),
226 next: ptr::null_mut(), 226 next: ptr::null_mut(),
227 }), 227 }),
228 }, 228 },
229 self_ptr: Opaque::uninit(), 229 self_ptr: Opaque::uninit(),
230 } 230 }
231 } 231 }
232 } 232 }
233 233
234 impl<T: ?Sized + ListItem<ID>, const ID: u64> 234 impl<T: ?Sized + ListItem<ID>, const ID: u64> List<T, ID> {
235 /// Creates a new empty list. 235 /// Creates a new empty list.
236 pub const fn new() -> Self { 236 pub const fn new() -> Self {
237 Self { 237 Self {
238 first: ptr::null_mut(), 238 first: ptr::null_mut(),
239 _ty: PhantomData, 239 _ty: PhantomData,
240 } 240 }
241 } 241 }
242 242
243 /// Returns whether this list is empty. 243 /// Returns whether this list is empty.
244 pub fn is_empty(&self) -> bool { 244 pub fn is_empty(&self) -> bool {
245 self.first.is_null() 245 self.first.is_null()
246 } 246 }
247 247
248 /// Add the provided item to the back of t 248 /// Add the provided item to the back of the list.
249 pub fn push_back(&mut self, item: ListArc< 249 pub fn push_back(&mut self, item: ListArc<T, ID>) {
250 let raw_item = ListArc::into_raw(item) 250 let raw_item = ListArc::into_raw(item);
251 // SAFETY: 251 // SAFETY:
252 // * We just got `raw_item` from a `Li 252 // * We just got `raw_item` from a `ListArc`, so it's in an `Arc`.
253 // * Since we have ownership of the `L 253 // * Since we have ownership of the `ListArc`, `post_remove` must have been called after
254 // the most recent call to `prepare_ 254 // the most recent call to `prepare_to_insert`, if any.
255 // * We own the `ListArc`. 255 // * We own the `ListArc`.
256 // * Removing items from this list is 256 // * Removing items from this list is always done using `remove_internal_inner`, which
257 // calls `post_remove` before giving 257 // calls `post_remove` before giving up ownership.
258 let list_links = unsafe { T::prepare_t 258 let list_links = unsafe { T::prepare_to_insert(raw_item) };
259 // SAFETY: We have not yet called `pos 259 // SAFETY: We have not yet called `post_remove`, so `list_links` is still valid.
260 let item = unsafe { ListLinks::fields( 260 let item = unsafe { ListLinks::fields(list_links) };
261 261
262 if self.first.is_null() { 262 if self.first.is_null() {
263 self.first = item; 263 self.first = item;
264 // SAFETY: The caller just gave us 264 // SAFETY: The caller just gave us ownership of these fields.
265 // INVARIANT: A linked list with o 265 // INVARIANT: A linked list with one item should be cyclic.
266 unsafe { 266 unsafe {
267 (*item).next = item; 267 (*item).next = item;
268 (*item).prev = item; 268 (*item).prev = item;
269 } 269 }
270 } else { 270 } else {
271 let next = self.first; 271 let next = self.first;
272 // SAFETY: By the type invariant, 272 // SAFETY: By the type invariant, this pointer is valid or null. We just checked that
273 // it's not null, so it must be va 273 // it's not null, so it must be valid.
274 let prev = unsafe { (*next).prev } 274 let prev = unsafe { (*next).prev };
275 // SAFETY: Pointers in a linked li 275 // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us
276 // ownership of the fields on `ite 276 // ownership of the fields on `item`.
277 // INVARIANT: This correctly inser 277 // INVARIANT: This correctly inserts `item` between `prev` and `next`.
278 unsafe { 278 unsafe {
279 (*item).next = next; 279 (*item).next = next;
280 (*item).prev = prev; 280 (*item).prev = prev;
281 (*prev).next = item; 281 (*prev).next = item;
282 (*next).prev = item; 282 (*next).prev = item;
283 } 283 }
284 } 284 }
285 } 285 }
286 286
287 /// Add the provided item to the front of 287 /// Add the provided item to the front of the list.
288 pub fn push_front(&mut self, item: ListArc 288 pub fn push_front(&mut self, item: ListArc<T, ID>) {
289 let raw_item = ListArc::into_raw(item) 289 let raw_item = ListArc::into_raw(item);
290 // SAFETY: 290 // SAFETY:
291 // * We just got `raw_item` from a `Li 291 // * We just got `raw_item` from a `ListArc`, so it's in an `Arc`.
292 // * If this requirement is violated, 292 // * If this requirement is violated, then the previous caller of `prepare_to_insert`
293 // violated the safety requirement t 293 // violated the safety requirement that they can't give up ownership of the `ListArc`
294 // until they call `post_remove`. 294 // until they call `post_remove`.
295 // * We own the `ListArc`. 295 // * We own the `ListArc`.
296 // * Removing items] from this list is 296 // * Removing items] from this list is always done using `remove_internal_inner`, which
297 // calls `post_remove` before giving 297 // calls `post_remove` before giving up ownership.
298 let list_links = unsafe { T::prepare_t 298 let list_links = unsafe { T::prepare_to_insert(raw_item) };
299 // SAFETY: We have not yet called `pos 299 // SAFETY: We have not yet called `post_remove`, so `list_links` is still valid.
300 let item = unsafe { ListLinks::fields( 300 let item = unsafe { ListLinks::fields(list_links) };
301 301
302 if self.first.is_null() { 302 if self.first.is_null() {
303 // SAFETY: The caller just gave us 303 // SAFETY: The caller just gave us ownership of these fields.
304 // INVARIANT: A linked list with o 304 // INVARIANT: A linked list with one item should be cyclic.
305 unsafe { 305 unsafe {
306 (*item).next = item; 306 (*item).next = item;
307 (*item).prev = item; 307 (*item).prev = item;
308 } 308 }
309 } else { 309 } else {
310 let next = self.first; 310 let next = self.first;
311 // SAFETY: We just checked that `n 311 // SAFETY: We just checked that `next` is non-null.
312 let prev = unsafe { (*next).prev } 312 let prev = unsafe { (*next).prev };
313 // SAFETY: Pointers in a linked li 313 // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us
314 // ownership of the fields on `ite 314 // ownership of the fields on `item`.
315 // INVARIANT: This correctly inser 315 // INVARIANT: This correctly inserts `item` between `prev` and `next`.
316 unsafe { 316 unsafe {
317 (*item).next = next; 317 (*item).next = next;
318 (*item).prev = prev; 318 (*item).prev = prev;
319 (*prev).next = item; 319 (*prev).next = item;
320 (*next).prev = item; 320 (*next).prev = item;
321 } 321 }
322 } 322 }
323 self.first = item; 323 self.first = item;
324 } 324 }
325 325
326 /// Removes the last item from this list. 326 /// Removes the last item from this list.
327 pub fn pop_back(&mut self) -> Option<ListA 327 pub fn pop_back(&mut self) -> Option<ListArc<T, ID>> {
328 if self.first.is_null() { 328 if self.first.is_null() {
329 return None; 329 return None;
330 } 330 }
331 331
332 // SAFETY: We just checked that the li 332 // SAFETY: We just checked that the list is not empty.
333 let last = unsafe { (*self.first).prev 333 let last = unsafe { (*self.first).prev };
334 // SAFETY: The last item of this list 334 // SAFETY: The last item of this list is in this list.
335 Some(unsafe { self.remove_internal(las 335 Some(unsafe { self.remove_internal(last) })
336 } 336 }
337 337
338 /// Removes the first item from this list. 338 /// Removes the first item from this list.
339 pub fn pop_front(&mut self) -> Option<List 339 pub fn pop_front(&mut self) -> Option<ListArc<T, ID>> {
340 if self.first.is_null() { 340 if self.first.is_null() {
341 return None; 341 return None;
342 } 342 }
343 343
344 // SAFETY: The first item of this list 344 // SAFETY: The first item of this list is in this list.
345 Some(unsafe { self.remove_internal(sel 345 Some(unsafe { self.remove_internal(self.first) })
346 } 346 }
347 347
348 /// Removes the provided item from this li 348 /// Removes the provided item from this list and returns it.
349 /// 349 ///
350 /// This returns `None` if the item is not 350 /// This returns `None` if the item is not in the list. (Note that by the safety requirements,
351 /// this means that the item is not in any 351 /// this means that the item is not in any list.)
352 /// 352 ///
353 /// # Safety 353 /// # Safety
354 /// 354 ///
355 /// `item` must not be in a different link 355 /// `item` must not be in a different linked list (with the same id).
356 pub unsafe fn remove(&mut self, item: &T) 356 pub unsafe fn remove(&mut self, item: &T) -> Option<ListArc<T, ID>> {
357 let mut item = unsafe { ListLinks::fie 357 let mut item = unsafe { ListLinks::fields(T::view_links(item)) };
358 // SAFETY: The user provided a referen 358 // SAFETY: The user provided a reference, and reference are never dangling.
359 // 359 //
360 // As for why this is not a data race, 360 // As for why this is not a data race, there are two cases:
361 // 361 //
362 // * If `item` is not in any list, th 362 // * If `item` is not in any list, then these fields are read-only and null.
363 // * If `item` is in this list, then 363 // * If `item` is in this list, then we have exclusive access to these fields since we
364 // have a mutable reference to the 364 // have a mutable reference to the list.
365 // 365 //
366 // In either case, there's no race. 366 // In either case, there's no race.
367 let ListLinksFields { next, prev } = u 367 let ListLinksFields { next, prev } = unsafe { *item };
368 368
369 debug_assert_eq!(next.is_null(), prev. 369 debug_assert_eq!(next.is_null(), prev.is_null());
370 if !next.is_null() { 370 if !next.is_null() {
371 // This is really a no-op, but thi 371 // This is really a no-op, but this ensures that `item` is a raw pointer that was
372 // obtained without going through 372 // obtained without going through a pointer->reference->pointer conversion roundtrip.
373 // This ensures that the list is v 373 // This ensures that the list is valid under the more restrictive strict provenance
374 // ruleset. 374 // ruleset.
375 // 375 //
376 // SAFETY: We just checked that `n 376 // SAFETY: We just checked that `next` is not null, and it's not dangling by the
377 // list invariants. 377 // list invariants.
378 unsafe { 378 unsafe {
379 debug_assert_eq!(item, (*next) 379 debug_assert_eq!(item, (*next).prev);
380 item = (*next).prev; 380 item = (*next).prev;
381 } 381 }
382 382
383 // SAFETY: We just checked that `i 383 // SAFETY: We just checked that `item` is in a list, so the caller guarantees that it
384 // is in this list. The pointers a 384 // is in this list. The pointers are in the right order.
385 Some(unsafe { self.remove_internal 385 Some(unsafe { self.remove_internal_inner(item, next, prev) })
386 } else { 386 } else {
387 None 387 None
388 } 388 }
389 } 389 }
390 390
391 /// Removes the provided item from the lis 391 /// Removes the provided item from the list.
392 /// 392 ///
393 /// # Safety 393 /// # Safety
394 /// 394 ///
395 /// `item` must point at an item in this l 395 /// `item` must point at an item in this list.
396 unsafe fn remove_internal(&mut self, item: 396 unsafe fn remove_internal(&mut self, item: *mut ListLinksFields) -> ListArc<T, ID> {
397 // SAFETY: The caller promises that th 397 // SAFETY: The caller promises that this pointer is not dangling, and there's no data race
398 // since we have a mutable reference t 398 // since we have a mutable reference to the list containing `item`.
399 let ListLinksFields { next, prev } = u 399 let ListLinksFields { next, prev } = unsafe { *item };
400 // SAFETY: The pointers are ok and in 400 // SAFETY: The pointers are ok and in the right order.
401 unsafe { self.remove_internal_inner(it 401 unsafe { self.remove_internal_inner(item, next, prev) }
402 } 402 }
403 403
404 /// Removes the provided item from the lis 404 /// Removes the provided item from the list.
405 /// 405 ///
406 /// # Safety 406 /// # Safety
407 /// 407 ///
408 /// The `item` pointer must point at an it 408 /// The `item` pointer must point at an item in this list, and we must have `(*item).next ==
409 /// next` and `(*item).prev == prev`. 409 /// next` and `(*item).prev == prev`.
410 unsafe fn remove_internal_inner( 410 unsafe fn remove_internal_inner(
411 &mut self, 411 &mut self,
412 item: *mut ListLinksFields, 412 item: *mut ListLinksFields,
413 next: *mut ListLinksFields, 413 next: *mut ListLinksFields,
414 prev: *mut ListLinksFields, 414 prev: *mut ListLinksFields,
415 ) -> ListArc<T, ID> { 415 ) -> ListArc<T, ID> {
416 // SAFETY: We have exclusive access to 416 // SAFETY: We have exclusive access to the pointers of items in the list, and the prev/next
417 // pointers are always valid for items 417 // pointers are always valid for items in a list.
418 // 418 //
419 // INVARIANT: There are three cases: 419 // INVARIANT: There are three cases:
420 // * If the list has at least three i 420 // * If the list has at least three items, then after removing the item, `prev` and `next`
421 // will be next to each other. 421 // will be next to each other.
422 // * If the list has two items, then 422 // * If the list has two items, then the remaining item will point at itself.
423 // * If the list has one item, then ` 423 // * If the list has one item, then `next == prev == item`, so these writes have no
424 // effect. The list remains unchang 424 // effect. The list remains unchanged and `item` is still in the list for now.
425 unsafe { 425 unsafe {
426 (*next).prev = prev; 426 (*next).prev = prev;
427 (*prev).next = next; 427 (*prev).next = next;
428 } 428 }
429 // SAFETY: We have exclusive access to 429 // SAFETY: We have exclusive access to items in the list.
430 // INVARIANT: `item` is being removed, 430 // INVARIANT: `item` is being removed, so the pointers should be null.
431 unsafe { 431 unsafe {
432 (*item).prev = ptr::null_mut(); 432 (*item).prev = ptr::null_mut();
433 (*item).next = ptr::null_mut(); 433 (*item).next = ptr::null_mut();
434 } 434 }
435 // INVARIANT: There are three cases: 435 // INVARIANT: There are three cases:
436 // * If `item` was not the first item 436 // * If `item` was not the first item, then `self.first` should remain unchanged.
437 // * If `item` was the first item and 437 // * If `item` was the first item and there is another item, then we just updated
438 // `prev->next` to `next`, which is 438 // `prev->next` to `next`, which is the new first item, and setting `item->next` to null
439 // did not modify `prev->next`. 439 // did not modify `prev->next`.
440 // * If `item` was the only item in t 440 // * If `item` was the only item in the list, then `prev == item`, and we just set
441 // `item->next` to null, so this co 441 // `item->next` to null, so this correctly sets `first` to null now that the list is
442 // empty. 442 // empty.
443 if self.first == item { 443 if self.first == item {
444 // SAFETY: The `prev` pointer is t 444 // SAFETY: The `prev` pointer is the value that `item->prev` had when it was in this
445 // list, so it must be valid. Ther 445 // list, so it must be valid. There is no race since `prev` is still in the list and we
446 // still have exclusive access to 446 // still have exclusive access to the list.
447 self.first = unsafe { (*prev).next 447 self.first = unsafe { (*prev).next };
448 } 448 }
449 449
450 // SAFETY: `item` used to be in the li 450 // SAFETY: `item` used to be in the list, so it is dereferenceable by the type invariants
451 // of `List`. 451 // of `List`.
452 let list_links = unsafe { ListLinks::f 452 let list_links = unsafe { ListLinks::from_fields(item) };
453 // SAFETY: Any pointer in the list ori 453 // SAFETY: Any pointer in the list originates from a `prepare_to_insert` call.
454 let raw_item = unsafe { T::post_remove 454 let raw_item = unsafe { T::post_remove(list_links) };
455 // SAFETY: The above call to `post_rem 455 // SAFETY: The above call to `post_remove` guarantees that we can recreate the `ListArc`.
456 unsafe { ListArc::from_raw(raw_item) } 456 unsafe { ListArc::from_raw(raw_item) }
457 } 457 }
458 458
459 /// Moves all items from `other` into `sel 459 /// Moves all items from `other` into `self`.
460 /// 460 ///
461 /// The items of `other` are added to the 461 /// The items of `other` are added to the back of `self`, so the last item of `other` becomes
462 /// the last item of `self`. 462 /// the last item of `self`.
463 pub fn push_all_back(&mut self, other: &mu 463 pub fn push_all_back(&mut self, other: &mut List<T, ID>) {
464 // First, we insert the elements into 464 // First, we insert the elements into `self`. At the end, we make `other` empty.
465 if self.is_empty() { 465 if self.is_empty() {
466 // INVARIANT: All of the elements 466 // INVARIANT: All of the elements in `other` become elements of `self`.
467 self.first = other.first; 467 self.first = other.first;
468 } else if !other.is_empty() { 468 } else if !other.is_empty() {
469 let other_first = other.first; 469 let other_first = other.first;
470 // SAFETY: The other list is not e 470 // SAFETY: The other list is not empty, so this pointer is valid.
471 let other_last = unsafe { (*other_ 471 let other_last = unsafe { (*other_first).prev };
472 let self_first = self.first; 472 let self_first = self.first;
473 // SAFETY: The self list is not em 473 // SAFETY: The self list is not empty, so this pointer is valid.
474 let self_last = unsafe { (*self_fi 474 let self_last = unsafe { (*self_first).prev };
475 475
476 // SAFETY: We have exclusive acces 476 // SAFETY: We have exclusive access to both lists, so we can update the pointers.
477 // INVARIANT: This correctly sets 477 // INVARIANT: This correctly sets the pointers to merge both lists. We do not need to
478 // update `self.first` because the 478 // update `self.first` because the first element of `self` does not change.
479 unsafe { 479 unsafe {
480 (*self_first).prev = other_las 480 (*self_first).prev = other_last;
481 (*other_last).next = self_firs 481 (*other_last).next = self_first;
482 (*self_last).next = other_firs 482 (*self_last).next = other_first;
483 (*other_first).prev = self_las 483 (*other_first).prev = self_last;
484 } 484 }
485 } 485 }
486 486
487 // INVARIANT: The other list is now em 487 // INVARIANT: The other list is now empty, so update its pointer.
488 other.first = ptr::null_mut(); 488 other.first = ptr::null_mut();
489 } 489 }
490 490
491 /// Returns a cursor to the first element 491 /// Returns a cursor to the first element of the list.
492 /// 492 ///
493 /// If the list is empty, this returns `No 493 /// If the list is empty, this returns `None`.
494 pub fn cursor_front(&mut self) -> Option<C 494 pub fn cursor_front(&mut self) -> Option<Cursor<'_, T, ID>> {
495 if self.first.is_null() { 495 if self.first.is_null() {
496 None 496 None
497 } else { 497 } else {
498 Some(Cursor { 498 Some(Cursor {
499 current: self.first, 499 current: self.first,
500 list: self, 500 list: self,
501 }) 501 })
502 } 502 }
503 } 503 }
504 504
505 /// Creates an iterator over the list. 505 /// Creates an iterator over the list.
506 pub fn iter(&self) -> Iter<'_, T, ID> { 506 pub fn iter(&self) -> Iter<'_, T, ID> {
507 // INVARIANT: If the list is empty, bo 507 // INVARIANT: If the list is empty, both pointers are null. Otherwise, both pointers point
508 // at the first element of the same li 508 // at the first element of the same list.
509 Iter { 509 Iter {
510 current: self.first, 510 current: self.first,
511 stop: self.first, 511 stop: self.first,
512 _ty: PhantomData, 512 _ty: PhantomData,
513 } 513 }
514 } 514 }
515 } 515 }
516 516
517 impl<T: ?Sized + ListItem<ID>, const ID: u64> 517 impl<T: ?Sized + ListItem<ID>, const ID: u64> Default for List<T, ID> {
518 fn default() -> Self { 518 fn default() -> Self {
519 List::new() 519 List::new()
520 } 520 }
521 } 521 }
522 522
523 impl<T: ?Sized + ListItem<ID>, const ID: u64> 523 impl<T: ?Sized + ListItem<ID>, const ID: u64> Drop for List<T, ID> {
524 fn drop(&mut self) { 524 fn drop(&mut self) {
525 while let Some(item) = self.pop_front( 525 while let Some(item) = self.pop_front() {
526 drop(item); 526 drop(item);
527 } 527 }
528 } 528 }
529 } 529 }
530 530
531 /// An iterator over a [`List`]. 531 /// An iterator over a [`List`].
532 /// 532 ///
533 /// # Invariants 533 /// # Invariants
534 /// 534 ///
535 /// * There must be a [`List`] that is immutab 535 /// * There must be a [`List`] that is immutably borrowed for the duration of `'a`.
536 /// * The `current` pointer is null or points 536 /// * The `current` pointer is null or points at a value in that [`List`].
537 /// * The `stop` pointer is equal to the `firs 537 /// * The `stop` pointer is equal to the `first` field of that [`List`].
538 #[derive(Clone)] 538 #[derive(Clone)]
539 pub struct Iter<'a, T: ?Sized + ListItem<ID>, 539 pub struct Iter<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
540 current: *mut ListLinksFields, 540 current: *mut ListLinksFields,
541 stop: *mut ListLinksFields, 541 stop: *mut ListLinksFields,
542 _ty: PhantomData<&'a ListArc<T, ID>>, 542 _ty: PhantomData<&'a ListArc<T, ID>>,
543 } 543 }
544 544
545 impl<'a, T: ?Sized + ListItem<ID>, const ID: u 545 impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Iterator for Iter<'a, T, ID> {
546 type Item = ArcBorrow<'a, T>; 546 type Item = ArcBorrow<'a, T>;
547 547
548 fn next(&mut self) -> Option<ArcBorrow<'a, 548 fn next(&mut self) -> Option<ArcBorrow<'a, T>> {
549 if self.current.is_null() { 549 if self.current.is_null() {
550 return None; 550 return None;
551 } 551 }
552 552
553 let current = self.current; 553 let current = self.current;
554 554
555 // SAFETY: We just checked that `curre 555 // SAFETY: We just checked that `current` is not null, so it is in a list, and hence not
556 // dangling. There's no race because t 556 // dangling. There's no race because the iterator holds an immutable borrow to the list.
557 let next = unsafe { (*current).next }; 557 let next = unsafe { (*current).next };
558 // INVARIANT: If `current` was the las 558 // INVARIANT: If `current` was the last element of the list, then this updates it to null.
559 // Otherwise, we update it to the next 559 // Otherwise, we update it to the next element.
560 self.current = if next != self.stop { 560 self.current = if next != self.stop {
561 next 561 next
562 } else { 562 } else {
563 ptr::null_mut() 563 ptr::null_mut()
564 }; 564 };
565 565
566 // SAFETY: The `current` pointer point 566 // SAFETY: The `current` pointer points at a value in the list.
567 let item = unsafe { T::view_value(List 567 let item = unsafe { T::view_value(ListLinks::from_fields(current)) };
568 // SAFETY: 568 // SAFETY:
569 // * All values in a list are stored i 569 // * All values in a list are stored in an `Arc`.
570 // * The value cannot be removed from 570 // * The value cannot be removed from the list for the duration of the lifetime annotated
571 // on the returned `ArcBorrow`, beca 571 // on the returned `ArcBorrow`, because removing it from the list would require mutable
572 // access to the list. However, the 572 // access to the list. However, the `ArcBorrow` is annotated with the iterator's
573 // lifetime, and the list is immutab 573 // lifetime, and the list is immutably borrowed for that lifetime.
574 // * Values in a list never have a `Un 574 // * Values in a list never have a `UniqueArc` reference.
575 Some(unsafe { ArcBorrow::from_raw(item 575 Some(unsafe { ArcBorrow::from_raw(item) })
576 } 576 }
577 } 577 }
578 578
579 /// A cursor into a [`List`]. 579 /// A cursor into a [`List`].
580 /// 580 ///
581 /// # Invariants 581 /// # Invariants
582 /// 582 ///
583 /// The `current` pointer points a value in `l 583 /// The `current` pointer points a value in `list`.
584 pub struct Cursor<'a, T: ?Sized + ListItem<ID> 584 pub struct Cursor<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
585 current: *mut ListLinksFields, 585 current: *mut ListLinksFields,
586 list: &'a mut List<T, ID>, 586 list: &'a mut List<T, ID>,
587 } 587 }
588 588
589 impl<'a, T: ?Sized + ListItem<ID>, const ID: u 589 impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Cursor<'a, T, ID> {
590 /// Access the current element of this cur 590 /// Access the current element of this cursor.
591 pub fn current(&self) -> ArcBorrow<'_, T> 591 pub fn current(&self) -> ArcBorrow<'_, T> {
592 // SAFETY: The `current` pointer point 592 // SAFETY: The `current` pointer points a value in the list.
593 let me = unsafe { T::view_value(ListLi 593 let me = unsafe { T::view_value(ListLinks::from_fields(self.current)) };
594 // SAFETY: 594 // SAFETY:
595 // * All values in a list are stored i 595 // * All values in a list are stored in an `Arc`.
596 // * The value cannot be removed from 596 // * The value cannot be removed from the list for the duration of the lifetime annotated
597 // on the returned `ArcBorrow`, beca 597 // on the returned `ArcBorrow`, because removing it from the list would require mutable
598 // access to the cursor or the list. 598 // access to the cursor or the list. However, the `ArcBorrow` holds an immutable borrow
599 // on the cursor, which in turn hold 599 // on the cursor, which in turn holds a mutable borrow on the list, so any such
600 // mutable access requires first rel 600 // mutable access requires first releasing the immutable borrow on the cursor.
601 // * Values in a list never have a `Un 601 // * Values in a list never have a `UniqueArc` reference, because the list has a `ListArc`
602 // reference, and `UniqueArc` refere 602 // reference, and `UniqueArc` references must be unique.
603 unsafe { ArcBorrow::from_raw(me) } 603 unsafe { ArcBorrow::from_raw(me) }
604 } 604 }
605 605
606 /// Move the cursor to the next element. 606 /// Move the cursor to the next element.
607 pub fn next(self) -> Option<Cursor<'a, T, 607 pub fn next(self) -> Option<Cursor<'a, T, ID>> {
608 // SAFETY: The `current` field is alwa 608 // SAFETY: The `current` field is always in a list.
609 let next = unsafe { (*self.current).ne 609 let next = unsafe { (*self.current).next };
610 610
611 if next == self.list.first { 611 if next == self.list.first {
612 None 612 None
613 } else { 613 } else {
614 // INVARIANT: Since `self.current` 614 // INVARIANT: Since `self.current` is in the `list`, its `next` pointer is also in the
615 // `list`. 615 // `list`.
616 Some(Cursor { 616 Some(Cursor {
617 current: next, 617 current: next,
618 list: self.list, 618 list: self.list,
619 }) 619 })
620 } 620 }
621 } 621 }
622 622
623 /// Move the cursor to the previous elemen 623 /// Move the cursor to the previous element.
624 pub fn prev(self) -> Option<Cursor<'a, T, 624 pub fn prev(self) -> Option<Cursor<'a, T, ID>> {
625 // SAFETY: The `current` field is alwa 625 // SAFETY: The `current` field is always in a list.
626 let prev = unsafe { (*self.current).pr 626 let prev = unsafe { (*self.current).prev };
627 627
628 if self.current == self.list.first { 628 if self.current == self.list.first {
629 None 629 None
630 } else { 630 } else {
631 // INVARIANT: Since `self.current` 631 // INVARIANT: Since `self.current` is in the `list`, its `prev` pointer is also in the
632 // `list`. 632 // `list`.
633 Some(Cursor { 633 Some(Cursor {
634 current: prev, 634 current: prev,
635 list: self.list, 635 list: self.list,
636 }) 636 })
637 } 637 }
638 } 638 }
639 639
640 /// Remove the current element from the li 640 /// Remove the current element from the list.
641 pub fn remove(self) -> ListArc<T, ID> { 641 pub fn remove(self) -> ListArc<T, ID> {
642 // SAFETY: The `current` pointer alway 642 // SAFETY: The `current` pointer always points at a member of the list.
643 unsafe { self.list.remove_internal(sel 643 unsafe { self.list.remove_internal(self.current) }
644 } 644 }
645 } 645 }
646 646
647 impl<'a, T: ?Sized + ListItem<ID>, const ID: u 647 impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> FusedIterator for Iter<'a, T, ID> {}
648 648
649 impl<'a, T: ?Sized + ListItem<ID>, const ID: u 649 impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for &'a List<T, ID> {
650 type IntoIter = Iter<'a, T, ID>; 650 type IntoIter = Iter<'a, T, ID>;
651 type Item = ArcBorrow<'a, T>; 651 type Item = ArcBorrow<'a, T>;
652 652
653 fn into_iter(self) -> Iter<'a, T, ID> { 653 fn into_iter(self) -> Iter<'a, T, ID> {
654 self.iter() 654 self.iter()
655 } 655 }
656 } 656 }
657 657
658 /// An owning iterator into a [`List`]. 658 /// An owning iterator into a [`List`].
659 pub struct IntoIter<T: ?Sized + ListItem<ID>, 659 pub struct IntoIter<T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
660 list: List<T, ID>, 660 list: List<T, ID>,
661 } 661 }
662 662
663 impl<T: ?Sized + ListItem<ID>, const ID: u64> 663 impl<T: ?Sized + ListItem<ID>, const ID: u64> Iterator for IntoIter<T, ID> {
664 type Item = ListArc<T, ID>; 664 type Item = ListArc<T, ID>;
665 665
666 fn next(&mut self) -> Option<ListArc<T, ID 666 fn next(&mut self) -> Option<ListArc<T, ID>> {
667 self.list.pop_front() 667 self.list.pop_front()
668 } 668 }
669 } 669 }
670 670
671 impl<T: ?Sized + ListItem<ID>, const ID: u64> 671 impl<T: ?Sized + ListItem<ID>, const ID: u64> FusedIterator for IntoIter<T, ID> {}
672 672
673 impl<T: ?Sized + ListItem<ID>, const ID: u64> 673 impl<T: ?Sized + ListItem<ID>, const ID: u64> DoubleEndedIterator for IntoIter<T, ID> {
674 fn next_back(&mut self) -> Option<ListArc< 674 fn next_back(&mut self) -> Option<ListArc<T, ID>> {
675 self.list.pop_back() 675 self.list.pop_back()
676 } 676 }
677 } 677 }
678 678
679 impl<T: ?Sized + ListItem<ID>, const ID: u64> 679 impl<T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for List<T, ID> {
680 type IntoIter = IntoIter<T, ID>; 680 type IntoIter = IntoIter<T, ID>;
681 type Item = ListArc<T, ID>; 681 type Item = ListArc<T, ID>;
682 682
683 fn into_iter(self) -> IntoIter<T, ID> { 683 fn into_iter(self) -> IntoIter<T, ID> {
684 IntoIter { list: self } 684 IntoIter { list: self }
685 } 685 }
686 } 686 }
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.