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 #[derive(Clone, Hash, Debug, PartialEq)]
  15 pub struct TinyList<T: PartialEq> {
  16     head: Option<Element<T>>
  17 }
  18
  19 impl<T: PartialEq> TinyList<T> {
  20
  21     #[inline]
  22     pub fn new() -> TinyList<T> {
  23         TinyList {
  24             head: None
  25         }
  26     }
  27
  28     #[inline]
  29     pub fn new_single(data: T) -> TinyList<T> {
  30         TinyList {
  31             head: Some(Element {
  32                 data,
  33                 next: None,
  34             })
  35         }
  36     }
  37
  38     #[inline]
  39     pub fn insert(&mut self, data: T) {
  40         self.head = Some(Element {
  41             data,
  42             next: self.head.take().map(Box::new)
  43         });
  44     }
  45
  46     #[inline]
  47     pub fn remove(&mut self, data: &T) -> bool {
  48         self.head = match self.head {
  49             Some(ref mut head) if head.data == *data => {
  50                 head.next.take().map(|x| *x)
  51             }
  52             Some(ref mut head) => return head.remove_next(data),
  53             None => return false,
  54         };
  55         true
  56     }
  57
  58     #[inline]
  59     pub fn contains(&self, data: &T) -> bool {
  60         if let Some(ref head) = self.head {
  61             head.contains(data)
  62         } else {
  63             false
  64         }
  65     }
  66
  67     #[inline]
  68     pub fn len(&self) -> usize {
  69         if let Some(ref head) = self.head {
  70             head.len()
  71         } else {
  72             0
  73         }
  74     }
  75 }
  76
  77 #[derive(Clone, Hash, Debug, PartialEq)]
  78 struct Element<T: PartialEq> {
  79     data: T,
  80     next: Option<Box<Element<T>>>,
  81 }
  82
  83 impl<T: PartialEq> Element<T> {
  84
  85     fn remove_next(&mut self, data: &T) -> bool {
  86         let new_next = if let Some(ref mut next) = self.next {
  87             if next.data != *data {
  88                 return next.remove_next(data)
  89             } else {
  90                 next.next.take()
  91             }
  92         } else {
  93             return false
  94         };
  95
  96         self.next = new_next;
  97
  98         true
  99     }
 100
 101     fn len(&self) -> usize {
 102         if let Some(ref next) = self.next {
 103             1 + next.len()
 104         } else {
 105             1
 106         }
 107     }
 108
 109     fn contains(&self, data: &T) -> bool {
 110         if self.data == *data {
 111             return true
 112         }
 113
 114         if let Some(ref next) = self.next {
 115             next.contains(data)
 116         } else {
 117             false
 118         }
 119     }
 120 }
 121
 122 #[cfg(test)]
 123 mod test {
 124     use super::*;
 125     extern crate test;
 126     use test::Bencher;
 127
 128     #[test]
 129     fn test_contains_and_insert() {
 130         fn do_insert(i : u32) -> bool {
 131             i % 2 == 0
 132         }
 133
 134         let mut list = TinyList::new();
 135
 136         for i in 0 .. 10 {
 137             for j in 0 .. i {
 138                 if do_insert(j) {
 139                     assert!(list.contains(&j));
 140                 } else {
 141                     assert!(!list.contains(&j));
 142                 }
 143             }
 144
 145             assert!(!list.contains(&i));
 146
 147             if do_insert(i) {
 148                 list.insert(i);
 149                 assert!(list.contains(&i));
 150             }
 151         }
 152     }
 153
 154     #[test]
 155     fn test_remove_first() {
 156         let mut list = TinyList::new();
 157         list.insert(1);
 158         list.insert(2);
 159         list.insert(3);
 160         list.insert(4);
 161         assert_eq!(list.len(), 4);
 162
 163         assert!(list.remove(&4));
 164         assert!(!list.contains(&4));
 165
 166         assert_eq!(list.len(), 3);
 167         assert!(list.contains(&1));
 168         assert!(list.contains(&2));
 169         assert!(list.contains(&3));
 170     }
 171
 172     #[test]
 173     fn test_remove_last() {
 174         let mut list = TinyList::new();
 175         list.insert(1);
 176         list.insert(2);
 177         list.insert(3);
 178         list.insert(4);
 179         assert_eq!(list.len(), 4);
 180
 181         assert!(list.remove(&1));
 182         assert!(!list.contains(&1));
 183
 184         assert_eq!(list.len(), 3);
 185         assert!(list.contains(&2));
 186         assert!(list.contains(&3));
 187         assert!(list.contains(&4));
 188     }
 189
 190     #[test]
 191     fn test_remove_middle() {
 192         let mut list = TinyList::new();
 193         list.insert(1);
 194         list.insert(2);
 195         list.insert(3);
 196         list.insert(4);
 197         assert_eq!(list.len(), 4);
 198
 199         assert!(list.remove(&2));
 200         assert!(!list.contains(&2));
 201
 202         assert_eq!(list.len(), 3);
 203         assert!(list.contains(&1));
 204         assert!(list.contains(&3));
 205         assert!(list.contains(&4));
 206     }
 207
 208     #[test]
 209     fn test_remove_single() {
 210         let mut list = TinyList::new();
 211         list.insert(1);
 212         assert_eq!(list.len(), 1);
 213
 214         assert!(list.remove(&1));
 215         assert!(!list.contains(&1));
 216
 217         assert_eq!(list.len(), 0);
 218     }
 219
 220     #[bench]
 221     fn bench_insert_empty(b: &mut Bencher) {
 222         b.iter(|| {
 223             let mut list = TinyList::new();
 224             list.insert(1);
 225         })
 226     }
 227
 228     #[bench]
 229     fn bench_insert_one(b: &mut Bencher) {
 230         b.iter(|| {
 231             let mut list = TinyList::new_single(0);
 232             list.insert(1);
 233         })
 234     }
 235
 236     #[bench]
 237     fn bench_remove_empty(b: &mut Bencher) {
 238         b.iter(|| {
 239             TinyList::new().remove(&1)
 240         });
 241     }
 242
 243     #[bench]
 244     fn bench_remove_unknown(b: &mut Bencher) {
 245         b.iter(|| {
 246             TinyList::new_single(0).remove(&1)
 247         });
 248     }
 249
 250     #[bench]
 251     fn bench_remove_one(b: &mut Bencher) {
 252         b.iter(|| {
 253             TinyList::new_single(1).remove(&1)
 254         });
 255     }
 256 }