1 //! An intrusive double linked list of data 2 //! 3 //! The data structure supports tracking pinned nodes. Most of the data 4 //! structure's APIs are `unsafe` as they require the caller to ensure the 5 //! specified node is actually contained by the list. 6 7 use core::fmt; 8 use core::mem::ManuallyDrop; 9 use core::ptr::NonNull; 10 11 /// An intrusive linked list. 12 /// 13 /// Currently, the list is not emptied on drop. It is the caller's 14 /// responsibility to ensure the list is empty before dropping it. 15 pub(crate) struct LinkedList<T: Link> { 16 /// Linked list head 17 head: Option<NonNull<T::Target>>, 18 19 /// Linked list tail 20 tail: Option<NonNull<T::Target>>, 21 } 22 23 unsafe impl<T: Link> Send for LinkedList<T> where T::Target: Send {} 24 unsafe impl<T: Link> Sync for LinkedList<T> where T::Target: Sync {} 25 26 /// Defines how a type is tracked within a linked list. 27 /// 28 /// In order to support storing a single type within multiple lists, accessing 29 /// the list pointers is decoupled from the entry type. 30 /// 31 /// # Safety 32 /// 33 /// Implementations must guarantee that `Target` types are pinned in memory. In 34 /// other words, when a node is inserted, the value will not be moved as long as 35 /// it is stored in the list. 36 pub(crate) unsafe trait Link { 37 /// Handle to the list entry. 38 /// 39 /// This is usually a pointer-ish type. 40 type Handle; 41 42 /// Node type 43 type Target; 44 45 /// Convert the handle to a raw pointer without consuming the handle as_raw(handle: &Self::Handle) -> NonNull<Self::Target>46 fn as_raw(handle: &Self::Handle) -> NonNull<Self::Target>; 47 48 /// Convert the raw pointer to a handle from_raw(ptr: NonNull<Self::Target>) -> Self::Handle49 unsafe fn from_raw(ptr: NonNull<Self::Target>) -> Self::Handle; 50 51 /// Return the pointers for a node pointers(target: NonNull<Self::Target>) -> NonNull<Pointers<Self::Target>>52 unsafe fn pointers(target: NonNull<Self::Target>) -> NonNull<Pointers<Self::Target>>; 53 } 54 55 /// Previous / next pointers 56 pub(crate) struct Pointers<T> { 57 /// The previous node in the list. null if there is no previous node. 58 prev: Option<NonNull<T>>, 59 60 /// The next node in the list. null if there is no previous node. 61 next: Option<NonNull<T>>, 62 } 63 64 unsafe impl<T: Send> Send for Pointers<T> {} 65 unsafe impl<T: Sync> Sync for Pointers<T> {} 66 67 // ===== impl LinkedList ===== 68 69 impl<T: Link> LinkedList<T> { 70 /// Creates an empty linked list new() -> LinkedList<T>71 pub(crate) fn new() -> LinkedList<T> { 72 LinkedList { 73 head: None, 74 tail: None, 75 } 76 } 77 78 /// Adds an element first in the list. push_front(&mut self, val: T::Handle)79 pub(crate) fn push_front(&mut self, val: T::Handle) { 80 // The value should not be dropped, it is being inserted into the list 81 let val = ManuallyDrop::new(val); 82 let ptr = T::as_raw(&*val); 83 assert_ne!(self.head, Some(ptr)); 84 unsafe { 85 T::pointers(ptr).as_mut().next = self.head; 86 T::pointers(ptr).as_mut().prev = None; 87 88 if let Some(head) = self.head { 89 T::pointers(head).as_mut().prev = Some(ptr); 90 } 91 92 self.head = Some(ptr); 93 94 if self.tail.is_none() { 95 self.tail = Some(ptr); 96 } 97 } 98 } 99 100 /// Removes the last element from a list and returns it, or None if it is 101 /// empty. pop_back(&mut self) -> Option<T::Handle>102 pub(crate) fn pop_back(&mut self) -> Option<T::Handle> { 103 unsafe { 104 let last = self.tail?; 105 self.tail = T::pointers(last).as_ref().prev; 106 107 if let Some(prev) = T::pointers(last).as_ref().prev { 108 T::pointers(prev).as_mut().next = None; 109 } else { 110 self.head = None 111 } 112 113 T::pointers(last).as_mut().prev = None; 114 T::pointers(last).as_mut().next = None; 115 116 Some(T::from_raw(last)) 117 } 118 } 119 120 /// Returns whether the linked list doesn not contain any node is_empty(&self) -> bool121 pub(crate) fn is_empty(&self) -> bool { 122 if self.head.is_some() { 123 return false; 124 } 125 126 assert!(self.tail.is_none()); 127 true 128 } 129 130 /// Removes the specified node from the list 131 /// 132 /// # Safety 133 /// 134 /// The caller **must** ensure that `node` is currently contained by 135 /// `self` or not contained by any other list. remove(&mut self, node: NonNull<T::Target>) -> Option<T::Handle>136 pub(crate) unsafe fn remove(&mut self, node: NonNull<T::Target>) -> Option<T::Handle> { 137 if let Some(prev) = T::pointers(node).as_ref().prev { 138 debug_assert_eq!(T::pointers(prev).as_ref().next, Some(node)); 139 T::pointers(prev).as_mut().next = T::pointers(node).as_ref().next; 140 } else { 141 if self.head != Some(node) { 142 return None; 143 } 144 145 self.head = T::pointers(node).as_ref().next; 146 } 147 148 if let Some(next) = T::pointers(node).as_ref().next { 149 debug_assert_eq!(T::pointers(next).as_ref().prev, Some(node)); 150 T::pointers(next).as_mut().prev = T::pointers(node).as_ref().prev; 151 } else { 152 // This might be the last item in the list 153 if self.tail != Some(node) { 154 return None; 155 } 156 157 self.tail = T::pointers(node).as_ref().prev; 158 } 159 160 T::pointers(node).as_mut().next = None; 161 T::pointers(node).as_mut().prev = None; 162 163 Some(T::from_raw(node)) 164 } 165 } 166 167 impl<T: Link> fmt::Debug for LinkedList<T> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result168 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 169 f.debug_struct("LinkedList") 170 .field("head", &self.head) 171 .field("tail", &self.tail) 172 .finish() 173 } 174 } 175 176 cfg_sync! { 177 impl<T: Link> LinkedList<T> { 178 pub(crate) fn last(&self) -> Option<&T::Target> { 179 let tail = self.tail.as_ref()?; 180 unsafe { 181 Some(&*tail.as_ptr()) 182 } 183 } 184 } 185 } 186 187 // ===== impl Iter ===== 188 189 cfg_rt_threaded! { 190 pub(crate) struct Iter<'a, T: Link> { 191 curr: Option<NonNull<T::Target>>, 192 _p: core::marker::PhantomData<&'a T>, 193 } 194 195 impl<T: Link> LinkedList<T> { 196 pub(crate) fn iter(&self) -> Iter<'_, T> { 197 Iter { 198 curr: self.head, 199 _p: core::marker::PhantomData, 200 } 201 } 202 } 203 204 impl<'a, T: Link> Iterator for Iter<'a, T> { 205 type Item = &'a T::Target; 206 207 fn next(&mut self) -> Option<&'a T::Target> { 208 let curr = self.curr?; 209 // safety: the pointer references data contained by the list 210 self.curr = unsafe { T::pointers(curr).as_ref() }.next; 211 212 // safety: the value is still owned by the linked list. 213 Some(unsafe { &*curr.as_ptr() }) 214 } 215 } 216 } 217 218 // ===== impl Pointers ===== 219 220 impl<T> Pointers<T> { 221 /// Create a new set of empty pointers new() -> Pointers<T>222 pub(crate) fn new() -> Pointers<T> { 223 Pointers { 224 prev: None, 225 next: None, 226 } 227 } 228 } 229 230 impl<T> fmt::Debug for Pointers<T> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result231 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 232 f.debug_struct("Pointers") 233 .field("prev", &self.prev) 234 .field("next", &self.next) 235 .finish() 236 } 237 } 238 239 #[cfg(test)] 240 #[cfg(not(loom))] 241 mod tests { 242 use super::*; 243 244 use std::pin::Pin; 245 246 #[derive(Debug)] 247 struct Entry { 248 pointers: Pointers<Entry>, 249 val: i32, 250 } 251 252 unsafe impl<'a> Link for &'a Entry { 253 type Handle = Pin<&'a Entry>; 254 type Target = Entry; 255 as_raw(handle: &Pin<&'_ Entry>) -> NonNull<Entry>256 fn as_raw(handle: &Pin<&'_ Entry>) -> NonNull<Entry> { 257 NonNull::from(handle.get_ref()) 258 } 259 from_raw(ptr: NonNull<Entry>) -> Pin<&'a Entry>260 unsafe fn from_raw(ptr: NonNull<Entry>) -> Pin<&'a Entry> { 261 Pin::new(&*ptr.as_ptr()) 262 } 263 pointers(mut target: NonNull<Entry>) -> NonNull<Pointers<Entry>>264 unsafe fn pointers(mut target: NonNull<Entry>) -> NonNull<Pointers<Entry>> { 265 NonNull::from(&mut target.as_mut().pointers) 266 } 267 } 268 entry(val: i32) -> Pin<Box<Entry>>269 fn entry(val: i32) -> Pin<Box<Entry>> { 270 Box::pin(Entry { 271 pointers: Pointers::new(), 272 val, 273 }) 274 } 275 ptr(r: &Pin<Box<Entry>>) -> NonNull<Entry>276 fn ptr(r: &Pin<Box<Entry>>) -> NonNull<Entry> { 277 r.as_ref().get_ref().into() 278 } 279 collect_list(list: &mut LinkedList<&'_ Entry>) -> Vec<i32>280 fn collect_list(list: &mut LinkedList<&'_ Entry>) -> Vec<i32> { 281 let mut ret = vec![]; 282 283 while let Some(entry) = list.pop_back() { 284 ret.push(entry.val); 285 } 286 287 ret 288 } 289 push_all<'a>(list: &mut LinkedList<&'a Entry>, entries: &[Pin<&'a Entry>])290 fn push_all<'a>(list: &mut LinkedList<&'a Entry>, entries: &[Pin<&'a Entry>]) { 291 for entry in entries.iter() { 292 list.push_front(*entry); 293 } 294 } 295 296 macro_rules! assert_clean { 297 ($e:ident) => {{ 298 assert!($e.pointers.next.is_none()); 299 assert!($e.pointers.prev.is_none()); 300 }}; 301 } 302 303 macro_rules! assert_ptr_eq { 304 ($a:expr, $b:expr) => {{ 305 // Deal with mapping a Pin<&mut T> -> Option<NonNull<T>> 306 assert_eq!(Some($a.as_ref().get_ref().into()), $b) 307 }}; 308 } 309 310 #[test] push_and_drain()311 fn push_and_drain() { 312 let a = entry(5); 313 let b = entry(7); 314 let c = entry(31); 315 316 let mut list = LinkedList::new(); 317 assert!(list.is_empty()); 318 319 list.push_front(a.as_ref()); 320 assert!(!list.is_empty()); 321 list.push_front(b.as_ref()); 322 list.push_front(c.as_ref()); 323 324 let items: Vec<i32> = collect_list(&mut list); 325 assert_eq!([5, 7, 31].to_vec(), items); 326 327 assert!(list.is_empty()); 328 } 329 330 #[test] push_pop_push_pop()331 fn push_pop_push_pop() { 332 let a = entry(5); 333 let b = entry(7); 334 335 let mut list = LinkedList::<&Entry>::new(); 336 337 list.push_front(a.as_ref()); 338 339 let entry = list.pop_back().unwrap(); 340 assert_eq!(5, entry.val); 341 assert!(list.is_empty()); 342 343 list.push_front(b.as_ref()); 344 345 let entry = list.pop_back().unwrap(); 346 assert_eq!(7, entry.val); 347 348 assert!(list.is_empty()); 349 assert!(list.pop_back().is_none()); 350 } 351 352 #[test] remove_by_address()353 fn remove_by_address() { 354 let a = entry(5); 355 let b = entry(7); 356 let c = entry(31); 357 358 unsafe { 359 // Remove first 360 let mut list = LinkedList::new(); 361 362 push_all(&mut list, &[c.as_ref(), b.as_ref(), a.as_ref()]); 363 assert!(list.remove(ptr(&a)).is_some()); 364 assert_clean!(a); 365 // `a` should be no longer there and can't be removed twice 366 assert!(list.remove(ptr(&a)).is_none()); 367 assert!(!list.is_empty()); 368 369 assert!(list.remove(ptr(&b)).is_some()); 370 assert_clean!(b); 371 // `b` should be no longer there and can't be removed twice 372 assert!(list.remove(ptr(&b)).is_none()); 373 assert!(!list.is_empty()); 374 375 assert!(list.remove(ptr(&c)).is_some()); 376 assert_clean!(c); 377 // `b` should be no longer there and can't be removed twice 378 assert!(list.remove(ptr(&c)).is_none()); 379 assert!(list.is_empty()); 380 } 381 382 unsafe { 383 // Remove middle 384 let mut list = LinkedList::new(); 385 386 push_all(&mut list, &[c.as_ref(), b.as_ref(), a.as_ref()]); 387 388 assert!(list.remove(ptr(&a)).is_some()); 389 assert_clean!(a); 390 391 assert_ptr_eq!(b, list.head); 392 assert_ptr_eq!(c, b.pointers.next); 393 assert_ptr_eq!(b, c.pointers.prev); 394 395 let items = collect_list(&mut list); 396 assert_eq!([31, 7].to_vec(), items); 397 } 398 399 unsafe { 400 // Remove middle 401 let mut list = LinkedList::new(); 402 403 push_all(&mut list, &[c.as_ref(), b.as_ref(), a.as_ref()]); 404 405 assert!(list.remove(ptr(&b)).is_some()); 406 assert_clean!(b); 407 408 assert_ptr_eq!(c, a.pointers.next); 409 assert_ptr_eq!(a, c.pointers.prev); 410 411 let items = collect_list(&mut list); 412 assert_eq!([31, 5].to_vec(), items); 413 } 414 415 unsafe { 416 // Remove last 417 // Remove middle 418 let mut list = LinkedList::new(); 419 420 push_all(&mut list, &[c.as_ref(), b.as_ref(), a.as_ref()]); 421 422 assert!(list.remove(ptr(&c)).is_some()); 423 assert_clean!(c); 424 425 assert!(b.pointers.next.is_none()); 426 assert_ptr_eq!(b, list.tail); 427 428 let items = collect_list(&mut list); 429 assert_eq!([7, 5].to_vec(), items); 430 } 431 432 unsafe { 433 // Remove first of two 434 let mut list = LinkedList::new(); 435 436 push_all(&mut list, &[b.as_ref(), a.as_ref()]); 437 438 assert!(list.remove(ptr(&a)).is_some()); 439 440 assert_clean!(a); 441 442 // a should be no longer there and can't be removed twice 443 assert!(list.remove(ptr(&a)).is_none()); 444 445 assert_ptr_eq!(b, list.head); 446 assert_ptr_eq!(b, list.tail); 447 448 assert!(b.pointers.next.is_none()); 449 assert!(b.pointers.prev.is_none()); 450 451 let items = collect_list(&mut list); 452 assert_eq!([7].to_vec(), items); 453 } 454 455 unsafe { 456 // Remove last of two 457 let mut list = LinkedList::new(); 458 459 push_all(&mut list, &[b.as_ref(), a.as_ref()]); 460 461 assert!(list.remove(ptr(&b)).is_some()); 462 463 assert_clean!(b); 464 465 assert_ptr_eq!(a, list.head); 466 assert_ptr_eq!(a, list.tail); 467 468 assert!(a.pointers.next.is_none()); 469 assert!(a.pointers.prev.is_none()); 470 471 let items = collect_list(&mut list); 472 assert_eq!([5].to_vec(), items); 473 } 474 475 unsafe { 476 // Remove last item 477 let mut list = LinkedList::new(); 478 479 push_all(&mut list, &[a.as_ref()]); 480 481 assert!(list.remove(ptr(&a)).is_some()); 482 assert_clean!(a); 483 484 assert!(list.head.is_none()); 485 assert!(list.tail.is_none()); 486 let items = collect_list(&mut list); 487 assert!(items.is_empty()); 488 } 489 490 unsafe { 491 // Remove missing 492 let mut list = LinkedList::<&Entry>::new(); 493 494 list.push_front(b.as_ref()); 495 list.push_front(a.as_ref()); 496 497 assert!(list.remove(ptr(&c)).is_none()); 498 } 499 } 500 501 #[test] iter()502 fn iter() { 503 let a = entry(5); 504 let b = entry(7); 505 506 let mut list = LinkedList::<&Entry>::new(); 507 508 assert_eq!(0, list.iter().count()); 509 510 list.push_front(a.as_ref()); 511 list.push_front(b.as_ref()); 512 513 let mut i = list.iter(); 514 assert_eq!(7, i.next().unwrap().val); 515 assert_eq!(5, i.next().unwrap().val); 516 assert!(i.next().is_none()); 517 } 518 519 proptest::proptest! { 520 #[test] 521 fn fuzz_linked_list(ops: Vec<usize>) { 522 run_fuzz(ops); 523 } 524 } 525 run_fuzz(ops: Vec<usize>)526 fn run_fuzz(ops: Vec<usize>) { 527 use std::collections::VecDeque; 528 529 #[derive(Debug)] 530 enum Op { 531 Push, 532 Pop, 533 Remove(usize), 534 } 535 536 let ops = ops 537 .iter() 538 .map(|i| match i % 3 { 539 0 => Op::Push, 540 1 => Op::Pop, 541 2 => Op::Remove(i / 3), 542 _ => unreachable!(), 543 }) 544 .collect::<Vec<_>>(); 545 546 let mut ll = LinkedList::<&Entry>::new(); 547 let mut reference = VecDeque::new(); 548 549 let entries: Vec<_> = (0..ops.len()).map(|i| entry(i as i32)).collect(); 550 551 for (i, op) in ops.iter().enumerate() { 552 match op { 553 Op::Push => { 554 reference.push_front(i as i32); 555 assert_eq!(entries[i].val, i as i32); 556 557 ll.push_front(entries[i].as_ref()); 558 } 559 Op::Pop => { 560 if reference.is_empty() { 561 assert!(ll.is_empty()); 562 continue; 563 } 564 565 let v = reference.pop_back(); 566 assert_eq!(v, ll.pop_back().map(|v| v.val)); 567 } 568 Op::Remove(n) => { 569 if reference.is_empty() { 570 assert!(ll.is_empty()); 571 continue; 572 } 573 574 let idx = n % reference.len(); 575 let expect = reference.remove(idx).unwrap(); 576 577 unsafe { 578 let entry = ll.remove(ptr(&entries[expect as usize])).unwrap(); 579 assert_eq!(expect, entry.val); 580 } 581 } 582 } 583 } 584 } 585 } 586