Introdução
O Ring Buffer (buffer circular) é uma estrutura de dados de tamanho fixo que utiliza um único array contíguo como se fosse circular. Quando o final do array é alcançado, a escrita “volta” para o início, sobrescrevendo dados antigos. É uma das estruturas mais eficientes para cenários de produtor-consumidor, onde dados são escritos continuamente e lidos na mesma ordem.
Ring buffers são onipresentes em sistemas de baixo nível: buffers de áudio em tempo real, FIFOs de hardware, logs circulares em sistemas embarcados, buffers de rede no kernel do Linux e muito mais. A biblioteca padrão do Rust utiliza internamente um ring buffer na implementação do VecDeque.
As operações de leitura e escrita são O(1) e extremamente eficientes em cache, pois os dados estão em memória contígua. Não há alocação dinâmica após a criação, tornando o ring buffer ideal para sistemas com restrições de memória ou requisitos de tempo real.
Nesta página, implementaremos um ring buffer completo em Rust, exploraremos o padrão produtor-consumidor e construiremos um exemplo prático de buffer de streaming de áudio.
Conceito e Teoria
Como Funciona o Ring Buffer
O ring buffer utiliza dois ponteiros — cabeça (head) e cauda (tail) — sobre um array de tamanho fixo. A cabeça indica a próxima posição de leitura e a cauda indica a próxima posição de escrita. O operador módulo (%) faz os ponteiros “voltarem” ao início quando atingem o final.
Ring Buffer — Visão Linear e Circular:
========================================
Visão LINEAR (como está na memória):
Índice: [0] [1] [2] [3] [4] [5] [6] [7]
Dados: [ ] [A] [B] [C] [D] [ ] [ ] [ ]
^ ^
| |
HEAD=1 TAIL=5
Elementos no buffer: TAIL - HEAD = 5 - 1 = 4 elementos
Visão CIRCULAR (como se comporta logicamente):
+-----+-----+-----+
/ [5] [6] [7] \
| vazio vazio vazio |
| |
[4] D| | [0] vazio
| |
| A B C |
\ [1] [2] [3] /
+-----+-----+-----+
HEAD=1 (leitura) TAIL=5 (escrita)
Comportamento de Wrap-Around
Quando o ponteiro de escrita atinge o final do array, ele volta ao início:
Wrap-Around (retorno ao início):
==================================
Antes — TAIL está no final:
[0] [1] [2] [3] [4] [5] [6] [7]
[ ] [ ] [ ] [X] [Y] [Z] [W] [?]
^ ^
HEAD=3 TAIL=7
Após escrever mais um elemento (TAIL = (7+1) % 8 = 0):
[0] [1] [2] [3] [4] [5] [6] [7]
[!] [ ] [ ] [X] [Y] [Z] [W] [?]
^ ^
TAIL=1 HEAD=3
O ponteiro "deu a volta"!
Buffer Cheio vs. Vazio
Um desafio clássico: como distinguir buffer cheio de buffer vazio, se ambos teriam HEAD == TAIL? Existem três estratégias comuns:
Estratégias para detectar cheio/vazio:
========================================
1. DESPERDIÇAR UM SLOT (usaremos esta):
- Vazio: head == tail
- Cheio: (tail + 1) % cap == head
- Capacidade útil = tamanho - 1
2. CONTADOR SEPARADO:
- Mantém variável `count` com o número de elementos
- Cheio: count == capacidade
- Vazio: count == 0
3. FLAG BOOLEANO:
- Mantém flag `cheio: bool`
- Distingue os dois estados quando head == tail
Conexão com VecDeque
O VecDeque da biblioteca padrão do Rust é essencialmente um ring buffer que cresce dinamicamente. Quando a capacidade é excedida, ele realoca (como Vec). Internamente usa a mesma lógica de head/tail com aritmética modular.
VecDeque internamente:
========================
VecDeque<T> {
buf: RawVec<T>, // Array contíguo (ring buffer)
head: usize, // Índice de leitura
len: usize, // Número de elementos
}
- push_front(): insere antes de head (head -= 1)
- push_back(): insere após head+len (tail += 1)
- pop_front(): remove de head (head += 1)
- pop_back(): remove de tail (len -= 1)
- Todos em O(1) amortizado!
Complexidade
| Operação | Tempo | Espaço | Observação |
|---|---|---|---|
escrever (push) | O(1) | O(1) | Escreve na posição da cauda |
ler (pop) | O(1) | O(1) | Lê da posição da cabeça |
espiar (peek) | O(1) | O(1) | Lê sem remover |
esta_cheio | O(1) | O(1) | Comparação de ponteiros |
esta_vazio | O(1) | O(1) | Comparação de ponteiros |
len | O(1) | O(1) | Aritmética com ponteiros |
| Espaço total | O(n) | n = capacidade fixa (sem realocação) |
Vantagens sobre Fila com Lista Ligada
| Critério | Ring Buffer | Lista Ligada |
|---|---|---|
| Cache-friendliness | Excelente (contíguo) | Ruim (ponteiros) |
| Alocação | Nenhuma (pré-alocado) | A cada inserção |
| Overhead por item | 0 bytes | 8-16 bytes (ponteiros) |
| Tamanho máximo | Fixo | Ilimitado |
| Fragmentação | Nenhuma | Possível |
Implementação em Rust
/// Ring Buffer (Buffer Circular) genérico de tamanho fixo.
///
/// Utiliza a estratégia de "desperdiçar um slot" para distinguir
/// buffer cheio de vazio. A capacidade útil é `tamanho_interno - 1`.
pub struct RingBuffer<T> {
buffer: Vec<Option<T>>,
cabeca: usize, // Índice de leitura (próximo a ser lido)
cauda: usize, // Índice de escrita (próxima posição livre)
capacidade: usize, // Tamanho interno do array (capacidade útil + 1)
}
impl<T> RingBuffer<T> {
/// Cria um novo Ring Buffer com a capacidade útil especificada.
///
/// Internamente aloca um slot extra para distinguir cheio de vazio.
pub fn novo(capacidade: usize) -> Self {
assert!(capacidade > 0, "Capacidade deve ser maior que zero");
let tamanho_interno = capacidade + 1;
let mut buffer = Vec::with_capacity(tamanho_interno);
for _ in 0..tamanho_interno {
buffer.push(None);
}
RingBuffer {
buffer,
cabeca: 0,
cauda: 0,
capacidade: tamanho_interno,
}
}
/// Escreve um elemento no buffer.
/// Retorna Err com o elemento se o buffer estiver cheio.
pub fn escrever(&mut self, item: T) -> Result<(), T> {
if self.esta_cheio() {
return Err(item);
}
self.buffer[self.cauda] = Some(item);
self.cauda = (self.cauda + 1) % self.capacidade;
Ok(())
}
/// Escreve um elemento, sobrescrevendo o mais antigo se cheio.
/// Retorna o elemento sobrescrito, se houver.
pub fn escrever_forcar(&mut self, item: T) -> Option<T> {
let sobrescrito = if self.esta_cheio() {
self.ler() // Remove o mais antigo
} else {
None
};
self.buffer[self.cauda] = Some(item);
self.cauda = (self.cauda + 1) % self.capacidade;
sobrescrito
}
/// Lê e remove o elemento mais antigo do buffer.
/// Retorna None se o buffer estiver vazio.
pub fn ler(&mut self) -> Option<T> {
if self.esta_vazio() {
return None;
}
let item = self.buffer[self.cabeca].take();
self.cabeca = (self.cabeca + 1) % self.capacidade;
item
}
/// Espia o próximo elemento sem removê-lo.
pub fn espiar(&self) -> Option<&T> {
if self.esta_vazio() {
None
} else {
self.buffer[self.cabeca].as_ref()
}
}
/// Verifica se o buffer está cheio.
pub fn esta_cheio(&self) -> bool {
(self.cauda + 1) % self.capacidade == self.cabeca
}
/// Verifica se o buffer está vazio.
pub fn esta_vazio(&self) -> bool {
self.cabeca == self.cauda
}
/// Retorna o número de elementos no buffer.
pub fn len(&self) -> usize {
if self.cauda >= self.cabeca {
self.cauda - self.cabeca
} else {
self.capacidade - self.cabeca + self.cauda
}
}
/// Retorna a capacidade útil do buffer.
pub fn capacidade(&self) -> usize {
self.capacidade - 1
}
/// Limpa o buffer, removendo todos os elementos.
pub fn limpar(&mut self) {
while self.ler().is_some() {}
}
/// Retorna um iterador sobre os elementos (sem consumir).
pub fn iter(&self) -> RingBufferIter<'_, T> {
RingBufferIter {
buffer: self,
posicao: self.cabeca,
restante: self.len(),
}
}
}
/// Iterador sobre o Ring Buffer.
pub struct RingBufferIter<'a, T> {
buffer: &'a RingBuffer<T>,
posicao: usize,
restante: usize,
}
impl<'a, T> Iterator for RingBufferIter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
if self.restante == 0 {
return None;
}
let item = self.buffer.buffer[self.posicao].as_ref();
self.posicao = (self.posicao + 1) % self.buffer.capacidade;
self.restante -= 1;
item
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.restante, Some(self.restante))
}
}
impl<T: std::fmt::Debug> std::fmt::Display for RingBuffer<T> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "RingBuffer[")?;
let mut primeiro = true;
for item in self.iter() {
if !primeiro {
write!(f, ", ")?;
}
write!(f, "{:?}", item)?;
primeiro = false;
}
write!(
f,
"] (len={}, cap={})",
self.len(),
self.capacidade()
)
}
}
fn main() {
println!("=== Demonstração do Ring Buffer ===\n");
let mut rb = RingBuffer::novo(5);
// Escrevendo elementos
println!("Escrevendo 1, 2, 3, 4, 5...");
for i in 1..=5 {
rb.escrever(i).unwrap();
}
println!("Buffer: {}", rb);
println!("Cheio? {}\n", rb.esta_cheio());
// Tentando escrever quando cheio
println!("Tentando escrever 6 (buffer cheio):");
match rb.escrever(6) {
Ok(()) => println!(" Sucesso"),
Err(v) => println!(" Erro: buffer cheio, {} rejeitado", v),
}
// Lendo alguns elementos
println!("\nLendo 2 elementos:");
println!(" Lido: {:?}", rb.ler());
println!(" Lido: {:?}", rb.ler());
println!("Buffer: {}", rb);
// Escrevendo com wrap-around
println!("\nEscrevendo 6, 7 (com wrap-around):");
rb.escrever(6).unwrap();
rb.escrever(7).unwrap();
println!("Buffer: {}", rb);
// Escrita forçada (sobrescreve o mais antigo)
println!("\nEscrita forçada de 8, 9 (sobrescreve antigos):");
let sobrescrito1 = rb.escrever_forcar(8);
let sobrescrito2 = rb.escrever_forcar(9);
println!(" Sobrescrito: {:?}, {:?}", sobrescrito1, sobrescrito2);
println!("Buffer: {}", rb);
// Iteração
println!("\nIteração sobre o buffer:");
for (i, valor) in rb.iter().enumerate() {
println!(" [{}] = {}", i, valor);
}
}
Ring Buffer com Escrita Forçada e Estatísticas
/// Ring Buffer especializado para logs com escrita sobrescritiva
/// e contagem de perdas.
pub struct LogBuffer<T> {
buffer: RingBuffer<T>,
total_escritas: u64,
total_perdas: u64,
}
impl<T: std::fmt::Debug> LogBuffer<T> {
pub fn novo(capacidade: usize) -> Self {
LogBuffer {
buffer: RingBuffer::novo(capacidade),
total_escritas: 0,
total_perdas: 0,
}
}
/// Registra um item. Se o buffer estiver cheio,
/// sobrescreve o mais antigo e incrementa o contador de perdas.
pub fn registrar(&mut self, item: T) {
self.total_escritas += 1;
if let Some(_perdido) = self.buffer.escrever_forcar(item) {
self.total_perdas += 1;
}
}
/// Drena todos os logs atuais em um vetor.
pub fn drenar(&mut self) -> Vec<T> {
let mut resultado = Vec::new();
while let Some(item) = self.buffer.ler() {
resultado.push(item);
}
resultado
}
/// Retorna estatísticas do buffer de log.
pub fn estatisticas(&self) -> String {
let taxa_perda = if self.total_escritas > 0 {
(self.total_perdas as f64 / self.total_escritas as f64) * 100.0
} else {
0.0
};
format!(
"Escritas: {} | Perdas: {} ({:.1}%) | Tamanho atual: {}/{}",
self.total_escritas,
self.total_perdas,
taxa_perda,
self.buffer.len(),
self.buffer.capacidade()
)
}
}
Exemplo Prático
Buffer de Streaming de Áudio
Um dos usos mais clássicos do ring buffer: processar amostras de áudio em tempo real. O produtor (placa de som / microfone) escreve amostras e o consumidor (processador de áudio) lê e processa.
use std::time::{Duration, Instant};
/// Uma amostra de áudio (simplificada).
#[derive(Debug, Clone, Copy)]
struct AmostraAudio {
canal_esquerdo: f32,
canal_direito: f32,
timestamp_ms: u64,
}
/// Buffer de áudio circular para streaming em tempo real.
/// Tamanho fixo para latência previsível.
struct BufferAudio {
amostras: Vec<Option<AmostraAudio>>,
cabeca: usize,
cauda: usize,
capacidade: usize,
taxa_amostragem: u32, // Hz (ex: 44100)
amostras_perdidas: u64,
total_processadas: u64,
}
impl BufferAudio {
/// Cria um buffer de áudio com latência especificada em milissegundos.
fn novo(taxa_amostragem: u32, latencia_ms: u32) -> Self {
// Calcula quantas amostras cabem na janela de latência
let num_amostras = (taxa_amostragem * latencia_ms / 1000) as usize;
let capacidade = num_amostras + 1; // +1 para a estratégia de slot vazio
let mut amostras = Vec::with_capacity(capacidade);
for _ in 0..capacidade {
amostras.push(None);
}
println!(
"Buffer de áudio criado: {} amostras ({} ms @ {} Hz)",
num_amostras, latencia_ms, taxa_amostragem
);
BufferAudio {
amostras,
cabeca: 0,
cauda: 0,
capacidade,
taxa_amostragem,
amostras_perdidas: 0,
total_processadas: 0,
}
}
/// Produtor: captura uma amostra do "microfone".
fn capturar(&mut self, amostra: AmostraAudio) {
let prox_cauda = (self.cauda + 1) % self.capacidade;
if prox_cauda == self.cabeca {
// Buffer cheio — descarta a amostra mais antiga
self.cabeca = (self.cabeca + 1) % self.capacidade;
self.amostras_perdidas += 1;
}
self.amostras[self.cauda] = Some(amostra);
self.cauda = prox_cauda;
}
/// Consumidor: processa o próximo bloco de amostras.
fn processar_bloco(&mut self, tamanho_bloco: usize) -> Vec<AmostraAudio> {
let mut bloco = Vec::with_capacity(tamanho_bloco);
for _ in 0..tamanho_bloco {
if self.cabeca == self.cauda {
break; // Buffer vazio — underrun
}
if let Some(amostra) = self.amostras[self.cabeca].take() {
bloco.push(amostra);
self.total_processadas += 1;
}
self.cabeca = (self.cabeca + 1) % self.capacidade;
}
bloco
}
/// Calcula o nível de preenchimento (0.0 a 1.0).
fn nivel_preenchimento(&self) -> f64 {
let len = if self.cauda >= self.cabeca {
self.cauda - self.cabeca
} else {
self.capacidade - self.cabeca + self.cauda
};
len as f64 / (self.capacidade - 1) as f64
}
/// Exibe o estado do buffer como medidor visual.
fn exibir_medidor(&self) {
let nivel = self.nivel_preenchimento();
let barras = (nivel * 30.0) as usize;
let vazio = 30 - barras;
let indicador = if nivel > 0.9 {
"PERIGO"
} else if nivel > 0.7 {
"ALTO"
} else if nivel > 0.3 {
"OK"
} else {
"BAIXO"
};
println!(
" [{}{}] {:.0}% ({}) | Perdas: {}",
"#".repeat(barras),
"-".repeat(vazio),
nivel * 100.0,
indicador,
self.amostras_perdidas
);
}
}
/// Aplica um efeito simples de volume ao bloco de áudio.
fn aplicar_volume(bloco: &mut [AmostraAudio], volume: f32) {
for amostra in bloco.iter_mut() {
amostra.canal_esquerdo *= volume;
amostra.canal_direito *= volume;
}
}
/// Calcula o nível RMS (Root Mean Square) do bloco.
fn calcular_rms(bloco: &[AmostraAudio]) -> f32 {
if bloco.is_empty() {
return 0.0;
}
let soma: f32 = bloco
.iter()
.map(|a| {
let media = (a.canal_esquerdo + a.canal_direito) / 2.0;
media * media
})
.sum();
(soma / bloco.len() as f32).sqrt()
}
fn main() {
println!("=== Simulação de Buffer de Áudio em Tempo Real ===\n");
// Cria buffer para 44.1 kHz com 50ms de latência
let mut buffer = BufferAudio::novo(44100, 50);
// Simula captura de amostras (produtor)
println!("\nFase 1: Capturando amostras do microfone...");
let mut timestamp = 0u64;
for i in 0..1500 {
// Gera uma onda senoidal simulada
let t = i as f32 / 44100.0;
let frequencia = 440.0; // Lá (A4)
let valor = (2.0 * std::f32::consts::PI * frequencia * t).sin();
buffer.capturar(AmostraAudio {
canal_esquerdo: valor * 0.8,
canal_direito: valor * 0.8,
timestamp_ms: timestamp,
});
timestamp += 1;
}
println!(" Amostras capturadas: 1500");
buffer.exibir_medidor();
// Simula processamento em blocos (consumidor)
println!("\nFase 2: Processando áudio em blocos de 256 amostras...");
let mut blocos_processados = 0;
loop {
let mut bloco = buffer.processar_bloco(256);
if bloco.is_empty() {
break;
}
// Aplica efeito de volume
aplicar_volume(&mut bloco, 0.75);
let rms = calcular_rms(&bloco);
blocos_processados += 1;
println!(
" Bloco {}: {} amostras | RMS: {:.4}",
blocos_processados,
bloco.len(),
rms
);
buffer.exibir_medidor();
}
println!("\nResumo:");
println!(" Blocos processados: {}", blocos_processados);
println!(" Amostras processadas: {}", buffer.total_processadas);
println!(" Amostras perdidas: {}", buffer.amostras_perdidas);
}
Exercícios
Exercício 1 — Ring Buffer Thread-Safe (SPSC)
Implemente um Ring Buffer Single Producer, Single Consumer (SPSC) thread-safe usando AtomicUsize para os ponteiros head e tail. Nesta configuração, um produtor e um consumidor podem operar simultaneamente sem locks, pois cada um modifica apenas seu próprio ponteiro.
Dica: Use std::sync::atomic::{AtomicUsize, Ordering}. O produtor faz store no tail com Ordering::Release e o consumidor faz load com Ordering::Acquire.
Exercício 2 — Ring Buffer com Blocos de Tamanho Variável
Modifique o Ring Buffer para suportar escritas e leituras em blocos contíguos. Implemente escrever_bloco(&mut self, dados: &[T]) -> usize que retorna quantos elementos foram efetivamente escritos, e ler_bloco(&mut self, destino: &mut [T]) -> usize. Considere o caso em que o bloco cruza o limite de wrap-around (precisa de duas cópias).
Dica: Use std::ptr::copy_nonoverlapping para cópias eficientes. Calcule a quantidade de espaço contíguo disponível antes do wrap-around.
Exercício 3 — Log Circular com Exportação
Crie um sistema de logging circular que armazene as últimas N mensagens de log. Cada mensagem tem nível (Debug, Info, Warn, Error), timestamp e texto. Implemente:
registrar(nivel, mensagem)para adicionar logsexportar_por_nivel(nivel)para filtrar e exportar logs de um nível específicoexportar_desde(timestamp)para exportar logs a partir de um momento
Quando o buffer estiver cheio, as mensagens mais antigas são sobrescritas automaticamente.
Conclusão
O Ring Buffer é uma estrutura deceptivamente simples que se revela extraordinariamente poderosa em cenários do mundo real. Os pontos fundamentais são:
- O(1) para todas as operações: Leitura, escrita e verificação de estado, tudo em tempo constante.
- Zero alocação dinâmica: Após a criação, não há alocação de memória, tornando-o ideal para sistemas de tempo real e embarcados.
- Cache-friendly: Dados em memória contígua maximizam o uso de cache L1/L2.
- Padrão produtor-consumidor: Naturalmente se encaixa em cenários onde um produtor gera dados e um consumidor os processa.
- Base do VecDeque: O
VecDeque<T>da biblioteca padrão do Rust é essencialmente um ring buffer com crescimento dinâmico.
O principal trade-off do ring buffer e sua capacidade fixa. Se o tamanho necessário for imprevisível, considere usar VecDeque que cresce automaticamente. Para cenários com requisitos rígidos de memória e latência (áudio, redes, sistemas embarcados), o ring buffer de tamanho fixo e a escolha ideal.
Na prática, para projetos Rust em produção, considere a crate ringbuf que oferece implementações SPSC lock-free e otimizadas para performance. Para aprendizado, a implementação manual como fizemos aqui e essencial para entender como buffers circulares funcionam nas entranhas dos sistemas operacionais.