src/librustc_data_structures/tiny_list.rs

   1 // Copyright 2018 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11
  12 //! A singly-linked list.
  13 //!
  14 //! Using this data structure only makes sense under very specific
  15 //! circumstances:
  16 //!
  17 //! - If you have a list that rarely stores more than one element, then this
  18 //!   data-structure can store the element without allocating and only uses as
  19 //!   much space as a `Option<(T, usize)>`. If T can double as the `Option`
  20 //!   discriminant, it will even only be as large as `T, usize`.
  21 //!
  22 //! If you expect to store more than 1 element in the common case, steer clear
  23 //! and use a `Vec<T>`, `Box<[T]>`, or a `SmallVec<T>`.
  24
  25 use std::mem;
  26
  27 #[derive(Clone, Hash, Debug, PartialEq)]
  28 pub struct TinyList<T: PartialEq> {
  29     head: Option<Element<T>>
  30 }
  31
  32 impl<T: PartialEq> TinyList<T> {
  33
  34     #[inline]
  35     pub fn new() -> TinyList<T> {
  36         TinyList {
  37             head: None
  38         }
  39     }
  40
  41     #[inline]
  42     pub fn new_single(data: T) -> TinyList<T> {
  43         TinyList {
  44             head: Some(Element {
  45                 data,
  46                 next: None,
  47             })
  48         }
  49     }
  50
  51     #[inline]
  52     pub fn insert(&mut self, data: T) {
  53         self.head = Some(Element {
  54             data,
  55             next: mem::replace(&mut self.head, None).map(Box::new),
  56         });
  57     }
  58
  59     #[inline]
  60     pub fn remove(&mut self, data: &T) -> bool {
  61         self.head = match self.head {
  62             Some(ref mut head) if head.data == *data => {
  63                 mem::replace(&mut head.next, None).map(|x| *x)
  64             }
  65             Some(ref mut head) => return head.remove_next(data),
  66             None => return false,
  67         };
  68         true
  69     }
  70
  71     #[inline]
  72     pub fn contains(&self, data: &T) -> bool {
  73         if let Some(ref head) = self.head {
  74             head.contains(data)
  75         } else {
  76             false
  77         }
  78     }
  79
  80     #[inline]
  81     pub fn len(&self) -> usize {
  82         if let Some(ref head) = self.head {
  83             head.len()
  84         } else {
  85             0
  86         }
  87     }
  88 }
  89
  90 #[derive(Clone, Hash, Debug, PartialEq)]
  91 struct Element<T: PartialEq> {
  92     data: T,
  93     next: Option<Box<Element<T>>>,
  94 }
  95
  96 impl<T: PartialEq> Element<T> {
  97
  98     fn remove_next(&mut self, data: &T) -> bool {
  99         let new_next = if let Some(ref mut next) = self.next {
 100             if next.data != *data {
 101                 return next.remove_next(data)
 102             } else {
 103                 mem::replace(&mut next.next, None)
 104             }
 105         } else {
 106             return false
 107         };
 108
 109         self.next = new_next;
 110
 111         true
 112     }
 113
 114     fn len(&self) -> usize {
 115         if let Some(ref next) = self.next {
 116             1 + next.len()
 117         } else {
 118             1
 119         }
 120     }
 121
 122     fn contains(&self, data: &T) -> bool {
 123         if self.data == *data {
 124             return true
 125         }
 126
 127         if let Some(ref next) = self.next {
 128             next.contains(data)
 129         } else {
 130             false
 131         }
 132     }
 133 }
 134
 135 #[cfg(test)]
 136 mod test {
 137     use super::*;
 138     extern crate test;
 139     use self::test::Bencher;
 140
 141     #[test]
 142     fn test_contains_and_insert() {
 143         fn do_insert(i : u32) -> bool {
 144             i % 2 == 0
 145         }
 146
 147         let mut list = TinyList::new();
 148
 149         for i in 0 .. 10 {
 150             for j in 0 .. i {
 151                 if do_insert(j) {
 152                     assert!(list.contains(&j));
 153                 } else {
 154                     assert!(!list.contains(&j));
 155                 }
 156             }
 157
 158             assert!(!list.contains(&i));
 159
 160             if do_insert(i) {
 161                 list.insert(i);
 162                 assert!(list.contains(&i));
 163             }
 164         }
 165     }
 166
 167     #[test]
 168     fn test_remove_first() {
 169         let mut list = TinyList::new();
 170         list.insert(1);
 171         list.insert(2);
 172         list.insert(3);
 173         list.insert(4);
 174         assert_eq!(list.len(), 4);
 175
 176         assert!(list.remove(&4));
 177         assert!(!list.contains(&4));
 178
 179         assert_eq!(list.len(), 3);
 180         assert!(list.contains(&1));
 181         assert!(list.contains(&2));
 182         assert!(list.contains(&3));
 183     }
 184
 185     #[test]
 186     fn test_remove_last() {
 187         let mut list = TinyList::new();
 188         list.insert(1);
 189         list.insert(2);
 190         list.insert(3);
 191         list.insert(4);
 192         assert_eq!(list.len(), 4);
 193
 194         assert!(list.remove(&1));
 195         assert!(!list.contains(&1));
 196
 197         assert_eq!(list.len(), 3);
 198         assert!(list.contains(&2));
 199         assert!(list.contains(&3));
 200         assert!(list.contains(&4));
 201     }
 202
 203     #[test]
 204     fn test_remove_middle() {
 205         let mut list = TinyList::new();
 206         list.insert(1);
 207         list.insert(2);
 208         list.insert(3);
 209         list.insert(4);
 210         assert_eq!(list.len(), 4);
 211
 212         assert!(list.remove(&2));
 213         assert!(!list.contains(&2));
 214
 215         assert_eq!(list.len(), 3);
 216         assert!(list.contains(&1));
 217         assert!(list.contains(&3));
 218         assert!(list.contains(&4));
 219     }
 220
 221     #[test]
 222     fn test_remove_single() {
 223         let mut list = TinyList::new();
 224         list.insert(1);
 225         assert_eq!(list.len(), 1);
 226
 227         assert!(list.remove(&1));
 228         assert!(!list.contains(&1));
 229
 230         assert_eq!(list.len(), 0);
 231     }
 232
 233     #[bench]
 234     fn bench_insert_empty(b: &mut Bencher) {
 235         b.iter(|| {
 236             let mut list = TinyList::new();
 237             list.insert(1);
 238         })
 239     }
 240
 241     #[bench]
 242     fn bench_insert_one(b: &mut Bencher) {
 243         b.iter(|| {
 244             let mut list = TinyList::new_single(0);
 245             list.insert(1);
 246         })
 247     }
 248
 249     #[bench]
 250     fn bench_remove_empty(b: &mut Bencher) {
 251         b.iter(|| {
 252             TinyList::new().remove(&1)
 253         });
 254     }
 255
 256     #[bench]
 257     fn bench_remove_unknown(b: &mut Bencher) {
 258         b.iter(|| {
 259             TinyList::new_single(0).remove(&1)
 260         });
 261     }
 262
 263     #[bench]
 264     fn bench_remove_one(b: &mut Bencher) {
 265         b.iter(|| {
 266             TinyList::new_single(1).remove(&1)
 267         });
 268     }
 269 }