Skip to content

Instantly share code, notes, and snippets.

@oconnor663
Created March 1, 2024 08:46
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save oconnor663/a8d795b0055d04e055bdfe348ee0ff20 to your computer and use it in GitHub Desktop.
Save oconnor663/a8d795b0055d04e055bdfe348ee0ff20 to your computer and use it in GitHub Desktop.
Too Many Linked Lists, Miri failure
use std::ptr;
pub struct List<T> {
head: Link<T>,
tail: *mut Node<T>, // DANGER DANGER
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
impl<T> List<T> {
pub fn new() -> Self {
List {
head: None,
tail: ptr::null_mut(),
}
}
pub fn push(&mut self, elem: T) {
let mut new_tail = Box::new(Node { elem, next: None });
let raw_tail: *mut _ = &mut *new_tail;
if !self.tail.is_null() {
// Hello Compiler, I Know I Am Doing Something Dangerous And
// I Promise To Be A Good Programmer Who Never Makes Mistakes.
unsafe {
(*self.tail).next = Some(new_tail);
}
} else {
self.head = Some(new_tail);
}
self.tail = raw_tail;
}
pub fn pop(&mut self) -> Option<T> {
self.head.take().map(|head| {
let head = *head;
self.head = head.next;
if self.head.is_none() {
self.tail = ptr::null_mut();
}
head.elem
})
}
}
#[cfg(test)]
mod test {
use super::List;
#[test]
fn basics() {
let mut list = List::new();
// Check empty list behaves right
assert_eq!(list.pop(), None);
// Populate list
list.push(1);
list.push(2);
list.push(3);
// Check normal removal
assert_eq!(list.pop(), Some(1));
assert_eq!(list.pop(), Some(2));
// Push some more just to make sure nothing's corrupted
list.push(4);
list.push(5);
// Check normal removal
assert_eq!(list.pop(), Some(3));
assert_eq!(list.pop(), Some(4));
// Check exhaustion
assert_eq!(list.pop(), Some(5));
assert_eq!(list.pop(), None);
// Check the exhaustion case fixed the pointer right
list.push(6);
list.push(7);
// Check normal removal
assert_eq!(list.pop(), Some(6));
assert_eq!(list.pop(), Some(7));
assert_eq!(list.pop(), None);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment