diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:02:58 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:02:58 +0000 |
commit | 698f8c2f01ea549d77d7dc3338a12e04c11057b9 (patch) | |
tree | 173a775858bd501c378080a10dca74132f05bc50 /compiler/rustc_data_structures/src/tiny_list.rs | |
parent | Initial commit. (diff) | |
download | rustc-698f8c2f01ea549d77d7dc3338a12e04c11057b9.tar.xz rustc-698f8c2f01ea549d77d7dc3338a12e04c11057b9.zip |
Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'compiler/rustc_data_structures/src/tiny_list.rs')
-rw-r--r-- | compiler/rustc_data_structures/src/tiny_list.rs | 81 |
1 files changed, 81 insertions, 0 deletions
diff --git a/compiler/rustc_data_structures/src/tiny_list.rs b/compiler/rustc_data_structures/src/tiny_list.rs new file mode 100644 index 000000000..9b07f8684 --- /dev/null +++ b/compiler/rustc_data_structures/src/tiny_list.rs @@ -0,0 +1,81 @@ +//! A singly-linked list. +//! +//! Using this data structure only makes sense under very specific +//! circumstances: +//! +//! - If you have a list that rarely stores more than one element, then this +//! data-structure can store the element without allocating and only uses as +//! much space as an `Option<(T, usize)>`. If T can double as the `Option` +//! discriminant, it will even only be as large as `T, usize`. +//! +//! If you expect to store more than 1 element in the common case, steer clear +//! and use a `Vec<T>`, `Box<[T]>`, or a `SmallVec<T>`. + +#[cfg(test)] +mod tests; + +#[derive(Clone)] +pub struct TinyList<T> { + head: Option<Element<T>>, +} + +impl<T: PartialEq> TinyList<T> { + #[inline] + pub fn new() -> TinyList<T> { + TinyList { head: None } + } + + #[inline] + pub fn new_single(data: T) -> TinyList<T> { + TinyList { head: Some(Element { data, next: None }) } + } + + #[inline] + pub fn insert(&mut self, data: T) { + self.head = Some(Element { data, next: self.head.take().map(Box::new) }); + } + + #[inline] + pub fn remove(&mut self, data: &T) -> bool { + self.head = match self.head { + Some(ref mut head) if head.data == *data => head.next.take().map(|x| *x), + Some(ref mut head) => return head.remove_next(data), + None => return false, + }; + true + } + + #[inline] + pub fn contains(&self, data: &T) -> bool { + let mut elem = self.head.as_ref(); + while let Some(ref e) = elem { + if &e.data == data { + return true; + } + elem = e.next.as_deref(); + } + false + } +} + +#[derive(Clone)] +struct Element<T> { + data: T, + next: Option<Box<Element<T>>>, +} + +impl<T: PartialEq> Element<T> { + fn remove_next(&mut self, data: &T) -> bool { + let mut n = self; + loop { + match n.next { + Some(ref mut next) if next.data == *data => { + n.next = next.next.take(); + return true; + } + Some(ref mut next) => n = next, + None => return false, + } + } + } +} |