src/librustc_data_structures/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 a `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: PartialEq> {
  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     #[inline]
  61     pub fn len(&self) -> usize {
  62         let (mut elem, mut count) = (self.head.as_ref(), 0);
  63         while let Some(ref e) = elem {
  64             count += 1;
  65             elem = e.next.as_deref();
  66         }
  67         count
  68     }
  69 }
  70
  71 #[derive(Clone)]
  72 struct Element<T: PartialEq> {
  73     data: T,
  74     next: Option<Box<Element<T>>>,
  75 }
  76
  77 impl<T: PartialEq> Element<T> {
  78     fn remove_next(&mut self, data: &T) -> bool {
  79         let mut n = self;
  80         loop {
  81             match n.next {
  82                 Some(ref mut next) if next.data == *data => {
  83                     n.next = next.next.take();
  84                     return true;
  85                 }
  86                 Some(ref mut next) => n = next,
  87                 None => return false,
  88             }
  89         }
  90     }
  91 }