use std::{mem, ptr};
pub struct DList<T> {
dummy: DNode<T>,
}
struct DNode<T> {
data: T,
next: *mut DNode<T>,
prev: *mut DNode<T>,
}
impl<T> DList<T> {
pub fn new() -> DList<T> {
unsafe {
let mut dummy = DNode {
data: mem::zeroed(),
next: ptr::null_mut(),
prev: ptr::null_mut(),
};
dummy.prev = &mut dummy;
dummy.next = &mut dummy;
DList { dummy }
}
}
pub fn push_front(&mut self, data: T) {
let mut new_node = DNode {
data,
next: ptr::null_mut(),
prev: ptr::null_mut(),
};
let old_front = self.dummy.next;
new_node.prev = &mut self.dummy;
self.dummy.next = &mut new_node;
new_node.next = old_front;
unsafe {
(*old_front).prev = &mut new_node;
}
}
pub fn pop_front(&mut self) -> T {
let front = self.dummy.next;
let new_front = unsafe { (*front).next };
self.dummy.next = new_front;
unsafe {
(*new_front).prev = &mut self.dummy;
front.read().data
}
}
}
I tried to implement a circular doubly linked list with unsafe rust. I design my data structure with pointers and decided to have a dummy node for convenience.
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_push_front_pop_front() {
let mut dlist = DList::new();
dlist.push_front(1);
dlist.push_front(2);
dlist.push_front(3);
assert_eq!(dlist.pop_front(), 3);
assert_eq!(dlist.pop_front(), 2);
assert_eq!(dlist.pop_front(), 1);
}
}
But when testing it, the doubly linked list does not pop the elements in the correct way. It always pops the last element added to it, which in this case is 3. I expected it to pop 3, 2 ,1, but it keeps popping 3.
I wonder if I'm using unsafe rust in a wrong way.
This:
pub fn push_front(&mut self, data: T) {
let mut new_node = DNode {
data,
next: ptr::null_mut(),
prev: ptr::null_mut(),
};
let old_front = self.dummy.next;
new_node.prev = &mut self.dummy;
self.dummy.next = &mut new_node;
new_node.next = old_front;
unsafe {
(*old_front).prev = &mut new_node;
}
}
is horribly broken: it's pushing a reference to a local variable in your linked list (new_node
), but that local variable is destroyed as soon as the function returns, leaving you with a dangling pointer. In this simple program, the memory is only reused the next time you call push_front
, where the new item winds up with the same address as the others, which is why pop_front
always sees the same value. In a more complicated example you would see seemingly random values, depending on what other functions you would have called.
A bit of advice: don't do linked lists, they are extremely hard to get right and they offer no benefits on modern computers. In safe Rust, at least the compiler keeps you from shooting yourself in the foot with them, but in unsafe Rust or most other languages you will only end up with faulty, hard to debug code.