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 {
  26             head: None
  27         }
  28     }
  29
  30     #[inline]
  31     pub fn new_single(data: T) -> TinyList<T> {
  32         TinyList {
  33             head: Some(Element {
  34                 data,
  35                 next: None,
  36             })
  37         }
  38     }
  39
  40     #[inline]
  41     pub fn insert(&mut self, data: T) {
  42         self.head = Some(Element {
  43             data,
  44             next: self.head.take().map(Box::new)
  45         });
  46     }
  47
  48     #[inline]
  49     pub fn remove(&mut self, data: &T) -> bool {
  50         self.head = match self.head {
  51             Some(ref mut head) if head.data == *data => {
  52                 head.next.take().map(|x| *x)
  53             }
  54             Some(ref mut head) => return head.remove_next(data),
  55             None => return false,
  56         };
  57         true
  58     }
  59
  60     #[inline]
  61     pub fn contains(&self, data: &T) -> bool {
  62         let mut elem = self.head.as_ref();
  63         while let Some(ref e) = elem {
  64             if &e.data == data {
  65                 return true;
  66             }
  67             elem = e.next.as_ref().map(|e| &**e);
  68         }
  69         false
  70     }
  71
  72     #[inline]
  73     pub fn len(&self) -> usize {
  74         let (mut elem, mut count) = (self.head.as_ref(), 0);
  75         while let Some(ref e) = elem {
  76             count += 1;
  77             elem = e.next.as_ref().map(|e| &**e);
  78         }
  79         count
  80     }
  81 }
  82
  83 #[derive(Clone)]
  84 struct Element<T: PartialEq> {
  85     data: T,
  86     next: Option<Box<Element<T>>>,
  87 }
  88
  89 impl<T: PartialEq> Element<T> {
  90     fn remove_next(&mut self, data: &T) -> bool {
  91         let new_next = match self.next {
  92             Some(ref mut next) if next.data == *data => next.next.take(),
  93             Some(ref mut next) => return next.remove_next(data),
  94             None => return false,
  95         };
  96         self.next = new_next;
  97         true
  98     }
  99 }