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.
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.
12 //! A singly-linked list.
14 //! Using this data structure only makes sense under very specific
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`.
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>`.
27 #[derive(Clone, Hash, Debug, PartialEq)]
28 pub struct TinyList<T: PartialEq> {
29 head: Option<Element<T>>
32 impl<T: PartialEq> TinyList<T> {
35 pub fn new() -> TinyList<T> {
42 pub fn new_single(data: T) -> TinyList<T> {
52 pub fn insert(&mut self, data: T) {
53 self.head = Some(Element {
55 next: mem::replace(&mut self.head, None).map(Box::new),
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)
65 Some(ref mut head) => return head.remove_next(data),
72 pub fn contains(&self, data: &T) -> bool {
73 if let Some(ref head) = self.head {
81 pub fn len(&self) -> usize {
82 if let Some(ref head) = self.head {
90 #[derive(Clone, Hash, Debug, PartialEq)]
91 struct Element<T: PartialEq> {
93 next: Option<Box<Element<T>>>,
96 impl<T: PartialEq> Element<T> {
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)
103 mem::replace(&mut next.next, None)
109 self.next = new_next;
114 fn len(&self) -> usize {
115 if let Some(ref next) = self.next {
122 fn contains(&self, data: &T) -> bool {
123 if self.data == *data {
127 if let Some(ref next) = self.next {
139 use self::test::Bencher;
142 fn test_contains_and_insert() {
143 fn do_insert(i : u32) -> bool {
147 let mut list = TinyList::new();
152 assert!(list.contains(&j));
154 assert!(!list.contains(&j));
158 assert!(!list.contains(&i));
162 assert!(list.contains(&i));
168 fn test_remove_first() {
169 let mut list = TinyList::new();
174 assert_eq!(list.len(), 4);
176 assert!(list.remove(&4));
177 assert!(!list.contains(&4));
179 assert_eq!(list.len(), 3);
180 assert!(list.contains(&1));
181 assert!(list.contains(&2));
182 assert!(list.contains(&3));
186 fn test_remove_last() {
187 let mut list = TinyList::new();
192 assert_eq!(list.len(), 4);
194 assert!(list.remove(&1));
195 assert!(!list.contains(&1));
197 assert_eq!(list.len(), 3);
198 assert!(list.contains(&2));
199 assert!(list.contains(&3));
200 assert!(list.contains(&4));
204 fn test_remove_middle() {
205 let mut list = TinyList::new();
210 assert_eq!(list.len(), 4);
212 assert!(list.remove(&2));
213 assert!(!list.contains(&2));
215 assert_eq!(list.len(), 3);
216 assert!(list.contains(&1));
217 assert!(list.contains(&3));
218 assert!(list.contains(&4));
222 fn test_remove_single() {
223 let mut list = TinyList::new();
225 assert_eq!(list.len(), 1);
227 assert!(list.remove(&1));
228 assert!(!list.contains(&1));
230 assert_eq!(list.len(), 0);
234 fn bench_insert_empty(b: &mut Bencher) {
236 let mut list = TinyList::new();
242 fn bench_insert_one(b: &mut Bencher) {
244 let mut list = TinyList::new_single(0);
250 fn bench_remove_empty(b: &mut Bencher) {
252 TinyList::new().remove(&1)
257 fn bench_remove_unknown(b: &mut Bencher) {
259 TinyList::new_single(0).remove(&1)
264 fn bench_remove_one(b: &mut Bencher) {
266 TinyList::new_single(1).remove(&1)