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, Hash, Debug, PartialEq)]
  18 pub struct TinyList<T: PartialEq> {
  19     head: Option<Element<T>>
  20 }
  21
  22 impl<T: PartialEq> TinyList<T> {
  23
  24     #[inline]
  25     pub fn new() -> TinyList<T> {
  26         TinyList {
  27             head: None
  28         }
  29     }
  30
  31     #[inline]
  32     pub fn new_single(data: T) -> TinyList<T> {
  33         TinyList {
  34             head: Some(Element {
  35                 data,
  36                 next: None,
  37             })
  38         }
  39     }
  40
  41     #[inline]
  42     pub fn insert(&mut self, data: T) {
  43         self.head = Some(Element {
  44             data,
  45             next: self.head.take().map(Box::new)
  46         });
  47     }
  48
  49     #[inline]
  50     pub fn remove(&mut self, data: &T) -> bool {
  51         self.head = match self.head {
  52             Some(ref mut head) if head.data == *data => {
  53                 head.next.take().map(|x| *x)
  54             }
  55             Some(ref mut head) => return head.remove_next(data),
  56             None => return false,
  57         };
  58         true
  59     }
  60
  61     #[inline]
  62     pub fn contains(&self, data: &T) -> bool {
  63         if let Some(ref head) = self.head {
  64             head.contains(data)
  65         } else {
  66             false
  67         }
  68     }
  69
  70     #[inline]
  71     pub fn len(&self) -> usize {
  72         if let Some(ref head) = self.head {
  73             head.len()
  74         } else {
  75             0
  76         }
  77     }
  78 }
  79
  80 #[derive(Clone, Hash, Debug, PartialEq)]
  81 struct Element<T: PartialEq> {
  82     data: T,
  83     next: Option<Box<Element<T>>>,
  84 }
  85
  86 impl<T: PartialEq> Element<T> {
  87
  88     fn remove_next(&mut self, data: &T) -> bool {
  89         let new_next = if let Some(ref mut next) = self.next {
  90             if next.data != *data {
  91                 return next.remove_next(data)
  92             } else {
  93                 next.next.take()
  94             }
  95         } else {
  96             return false
  97         };
  98
  99         self.next = new_next;
 100
 101         true
 102     }
 103
 104     fn len(&self) -> usize {
 105         if let Some(ref next) = self.next {
 106             1 + next.len()
 107         } else {
 108             1
 109         }
 110     }
 111
 112     fn contains(&self, data: &T) -> bool {
 113         if self.data == *data {
 114             return true
 115         }
 116
 117         if let Some(ref next) = self.next {
 118             next.contains(data)
 119         } else {
 120             false
 121         }
 122     }
 123 }