Sistemas de Baixo Nível & Memory Safety
Módulo 01
Doubly Linked List Manual com Safe Pointers
Uma análise detalhada da estrutura de dados mais infame da engenharia em Rust. Por exigir que múltiplos nós mantenham referências mutáveis bidirecionais simultâneas para o mesmo elemento, a Lista Duplamente Ligada força o desenvolvedor a lidar diretamente com os limites do Borrow Checker, invariantes de memória e encapsulamento estrito de blocos unsafe.
01. O Paradoxo de Rust: Aliasing XOR Mutability
O pilar central da segurança de memória em Rust resume-se à regra fundamental de ponteiros: ou você possui várias referências imutáveis (&T), ou você possui uma única referência mutável exclusiva (&mut T).
Em uma lista duplamente ligada típica, se um nó intermediário B está entre A e C:
A.next aponta para BC.prev aponta para B
Ambos precisam conseguir alterar B durante operações de inserção e remoção. Isso viola a exclusividade de empréstimo mutável da linguagem. Para resolver este paradoxo em nível de engenharia, existem três caminhos arquiteturais possíveis:
02. Decisão de Design: Por que descartamos Rc<RefCell<T>>?
1. Safe Abstraction
Rc<RefCell<Node<T>>>
Utiliza contagem de referências e checagem de empréstimo em tempo de execução.
❌ Alto overhead de memória por nó, overhead de CPU e risco de memory leaks por ciclos de referência sem Weak<T>.
2. Índices de Vetor
Vec<Node<T>> + usize
Aloca todos os nós em um vetor central contíguo e usa índices numéricos como ponteiros.
⚠️ Excelente localidade de cache, porém fragmenta memória na deleção e exige freelist manual de índices vazios.
3. Nossa Escolha (Idêntica à Stdlib)
NonNull<Node<T>>
Ponteiros crus encapsulados em tipos covariantes com otimização em tempo de compilação.
✅ Zero custo extra em memória, performance equivalente a C/C++ e encapsulamento 100% seguro na API pública.
03. Anatomia Interna & Smart Primitives
NonNull<T> e Null Pointer Optimization (NPO)
Diferente de um ponteiro bruto *mut T (que pode ser nulo), o tipo NonNull<T> assegura ao compilador que seu valor nunca é zero. Isso ativa a Null Pointer Optimization (NPO) do rustc: o enum Option<NonNull<T>> utiliza a representação de bits 0x0 para significar None. Consequentemente, o tamanho de Option<NonNull<T>> é de exatamente 8 bytes em arquiteturas de 64-bit (o mesmo tamanho de um ponteiro cru simples), sem o overhead de uma tag de discriminação.
PhantomData e o Drop Checker (eyepatch)
Como nossa struct utiliza ponteiros crus (NonNull), o compilador do Rust assume que ela não é dona dos dados apontados, mas apenas os observa. O marcador _marker: PhantomData<Box<Node<T>>> informa formalmente ao Drop Checker e ao analisador de variância que a struct DoublyLinkedList<T> é a proprietária legítima dos nós no Heap e é encarregada de descartá-los de forma segura.
Destruição Iterativa via Drop Trait (Evitando Stack Overflow)
Se a desalocação fosse baseada no destrutor recursivo padrão, a destruição de uma lista de 500.000 elementos geraria 500.000 frames de chamada na pilha de execução (drop() -> drop() -> drop()), estourando a memória de stack (Stack Overflow). Implementamos explicitamente a trait Drop com um loop iterativo while self.pop_front().is_some() {}, garantindo consumo constante de stack space ($O(1)$) ao desalocar cada nó individual da Heap.
04. Complexidade Assintótica & Hardware Reality
| Operação |
Complexidade de Tempo |
Uso de Memória |
Detalhe Operacional |
| push_front / push_back |
O(1) |
O(1) |
Alocação direta de nó isolado via Box::into_raw |
| pop_front / pop_back |
O(1) |
O(1) |
Reassociação de ponteiros e desalocação imediata |
| peek_front / peek_back |
O(1) |
O(1) |
Empréstimo imutável (&T) sem overhead de cópia |
| drop (Desalocação) |
O(n) |
O(1) stack |
Loop iterativo seguro com desalocação nó a nó |
💡 Por que a Linked List raramente é usada no mundo real?
Apesar do tempo de inserção $O(1)$ nas bordas, cada nó está espalhado em endereços aleatórios do Heap. CPUs modernas contam com linhas de cache L1/L2/L3 e prefetchers de hardware projetados para blocos sequenciais contíguos de memória. Navegar por nós ponteirados resulta em frequentes Cache Misses. Em 99% das aplicações reais em Rust, estruturas como Vec ou VecDeque superam uma lista ligada em ordens de magnitude na velocidade prática de execução.
use std::fmt::{self, Display, Formatter};
use std::marker::PhantomData;
use std::ptr::NonNull;
struct Node<T> {
val: T,
prev: Option<NonNull<Node<T>>>,
next: Option<NonNull<Node<T>>>,
}
impl<T> Node<T> {
fn new(val: T) -> Self {
Self {
val,
prev: None,
next: None,
}
}
}
pub struct DoublyLinkedList<T> {
head: Option<NonNull<Node<T>>>,
tail: Option<NonNull<Node<T>>>,
len: usize,
_marker: PhantomData<Box<Node<T>>>,
}
impl<T> DoublyLinkedList<T> {
pub fn new() -> Self {
Self {
head: None,
tail: None,
len: 0,
_marker: PhantomData,
}
}
pub fn len(&self) -> usize {
self.len
}
pub fn is_empty(&self) -> bool {
self.len == 0
}
pub fn push_front(&mut self, val: T) {
let new_node = Box::new(Node::new(val));
let new_ptr = NonNull::new(Box::into_raw(new_node));
unsafe {
match self.head {
None => {
self.head = new_ptr;
self.tail = new_ptr;
}
Some(old_head) => {
(*new_ptr.unwrap().as_ptr()).next = Some(old_head);
(*old_head.as_ptr()).prev = new_ptr;
self.head = new_ptr;
}
}
}
self.len += 1;
}
pub fn push_back(&mut self, val: T) {
let new_node = Box::new(Node::new(val));
let new_ptr = NonNull::new(Box::into_raw(new_node));
unsafe {
match self.tail {
None => {
self.head = new_ptr;
self.tail = new_ptr;
}
Some(old_tail) => {
(*new_ptr.unwrap().as_ptr()).prev = Some(old_tail);
(*old_tail.as_ptr()).next = new_ptr;
self.tail = new_ptr;
}
}
}
self.len += 1;
}
pub fn pop_front(&mut self) -> Option<T> {
self.head.map(|head_ptr| unsafe {
let boxed_node = Box::from_raw(head_ptr.as_ptr());
let result = boxed_node.val;
self.head = boxed_node.next;
match self.head {
None => self.tail = None,
Some(new_head) => (*new_head.as_ptr()).prev = None,
}
self.len -= 1;
result
})
}
pub fn pop_back(&mut self) -> Option<T> {
self.tail.map(|tail_ptr| unsafe {
let boxed_node = Box::from_raw(tail_ptr.as_ptr());
let result = boxed_node.val;
self.tail = boxed_node.prev;
match self.tail {
None => self.head = None,
Some(new_tail) => (*new_tail.as_ptr()).next = None,
}
self.len -= 1;
result
})
}
pub fn peek_front(&self) -> Option<&T> {
self.head.map(|ptr| unsafe { &(*ptr.as_ptr()).val })
}
pub fn peek_back(&self) -> Option<&T> {
self.tail.map(|ptr| unsafe { &(*ptr.as_ptr()).val })
}
}
impl<T> Drop for DoublyLinkedList<T> {
fn drop(&mut self) {
while self.pop_front().is_some() {}
}
}
impl<T: Display> Display for DoublyLinkedList<T> {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
write!(f, "[Head] <-> ")?;
let mut curr = self.head;
while let Some(ptr) = curr {
unsafe {
write!(f, "({}) <-> ", (*ptr.as_ptr()).val)?;
curr = (*ptr.as_ptr()).next;
}
}
write!(f, "[Tail]")
}
}
fn main() {
println!("============================================================");
println!("🦀 RUST DATA STRUCTURES: DOUBLY LINKED LIST (SAFE POINTERS)");
println!("============================================================");
let mut list: DoublyLinkedList<i32> = DoublyLinkedList::new();
println!("\n1. Inserindo elementos nas extremidades:");
println!(" -> push_back(20)");
list.push_back(20);
println!(" -> push_back(30)");
list.push_back(30);
println!(" -> push_front(10)");
list.push_front(10);
println!(" -> push_front(5)");
list.push_front(5);
println!("\n2. Estado da lista:");
println!(" {}", list);
println!(" Tamanho: {} nós", list.len());
println!("\n3. Inspeção de ponteiros:");
if let Some(front) = list.peek_front() {
println!(" Primeiro valor (peek_front): {}", front);
}
if let Some(back) = list.peek_back() {
println!(" Último valor (peek_back): {}", back);
}
println!("\n4. Removendo elementos:");
let popped_front = list.pop_front();
println!(" pop_front() -> {:?}", popped_front);
println!(" Lista: {}", list);
let popped_back = list.pop_back();
println!(" pop_back() -> {:?}", popped_back);
println!(" Lista: {}", list);
println!("\n5. Limpeza de memória (Drop):");
println!(" Liberando nós recursivamente da heap sem memory leaks!");
}