compiler/rustc_data_structures/src/tiny_list.rs

   1 //! A singly-linked list.
   2 //!
   3 //! Using this data structure only makes sense under very specific
   4 //! circumstances:
   5 //!
   6 //! - If you have a list that rarely stores more than one element, then this
   7 //!   data-structure can store the element without allocating and only uses as
   8 //!   much space as an `Option<(T, usize)>`. If T can double as the `Option`
   9 //!   discriminant, it will even only be as large as `T, usize`.
  10 //!
  11 //! If you expect to store more than 1 element in the common case, steer clear
  12 //! and use a `Vec<T>`, `Box<[T]>`, or a `SmallVec<T>`.
  13
  14 #[cfg(test)]
  15 mod tests;
  16
  17 #[derive(Clone)]
  18 pub struct TinyList<T> {
  19     head: Option<Element<T>>,
  20 }
  21
  22 impl<T: PartialEq> TinyList<T> {
  23     #[inline]
  24     pub fn new() -> TinyList<T> {
  25         TinyList { head: None }
  26     }
  27
  28     #[inline]
  29     pub fn new_single(data: T) -> TinyList<T> {
  30         TinyList { head: Some(Element { data, next: None }) }
  31     }
  32
  33     #[inline]
  34     pub fn insert(&mut self, data: T) {
  35         self.head = Some(Element { data, next: self.head.take().map(Box::new) });
  36     }
  37
  38     #[inline]
  39     pub fn remove(&mut self, data: &T) -> bool {
  40         self.head = match self.head {
  41             Some(ref mut head) if head.data == *data => head.next.take().map(|x| *x),
  42             Some(ref mut head) => return head.remove_next(data),
  43             None => return false,
  44         };
  45         true
  46     }
  47
  48     #[inline]
  49     pub fn contains(&self, data: &T) -> bool {
  50         let mut elem = self.head.as_ref();
  51         while let Some(ref e) = elem {
  52             if &e.data == data {
  53                 return true;
  54             }
  55             elem = e.next.as_deref();
  56         }
  57         false
  58     }
  59 }
  60
  61 #[derive(Clone)]
  62 struct Element<T> {
  63     data: T,
  64     next: Option<Box<Element<T>>>,
  65 }
  66
  67 impl<T: PartialEq> Element<T> {
  68     fn remove_next(&mut self, data: &T) -> bool {
  69         let mut n = self;
  70         loop {
  71             match n.next {
  72                 Some(ref mut next) if next.data == *data => {
  73                     n.next = next.next.take();
  74                     return true;
  75                 }
  76                 Some(ref mut next) => n = next,
  77                 None => return false,
  78             }
  79         }
  80     }
  81 }