Listas livres e reutilização
Acompanhe e recicle blocos.
Listas livres e reutilização é uma aula grátis de C Academy no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de C Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de C Academy inclui 4 aulas no total.
Além do Alocador bump
Para liberar blocos individuais e reutilizá-los, precisamos manter informações de controle. Uma lista livre é uma lista encadeada de blocos disponíveis que o alocador pesquisa antes de obter memória nova.
Cada bloco contém um cabeçalho para que o alocador possa encontrar seu tamanho e vinculá-lo ao próximo bloco da cadeia.
Cabeçalho de Bloco com um Vínculo
Ampliamos o cabeçalho com um ponteiro next e uma sinalização free. Juntos, eles transformam nosso pool em uma lista navegável de blocos.
O conteúdo vem imediatamente depois do cabeçalho na memória.
typedef struct block {
size_t size; /* payload bytes */
int free; /* 1 if reusable */
struct block *next; /* next block in pool */
} block_t;Inicializando um Grande Bloco Livre
Na inicialização, todo o pool é um único bloco livre enorme. Conforme as alocações ocorrem, nós o dividimos; conforme as liberações ocorrem, marcamos os blocos como reutilizáveis.
O início da lista é este bloco inicial, que cobre toda a arena.
static unsigned char pool[4096];
static block_t *head;
void heap_init(void) {
head = (block_t *)pool;
head->size = sizeof(pool) - sizeof(block_t);
head->free = 1;
head->next = NULL;
}Busca pelo Primeiro Encaixe
A estratégia de reutilização mais simples é o primeiro encaixe: percorra a lista e retorne o primeiro bloco livre que seja grande o suficiente. Ela é rápida e tende a manter os blocos pequenos próximos do início.
As alternativas são o melhor encaixe (o menor bloco suficiente) e o pior encaixe, trocando velocidade pelo comportamento da fragmentação.
block_t *first_fit(size_t size) {
for (block_t *b = head; b; b = b->next)
if (b->free && b->size >= size)
return b;
return NULL;
}Alocando a partir de um Bloco Livre
Assim que encontramos um encaixe, marcamos o bloco como usado e retornamos o ponteiro logo depois do cabeçalho. Por enquanto, entregamos o bloco inteiro; a divisão será abordada na próxima lição.
O ponteiro retornado é block + 1, ocultando o cabeçalho do chamador.
void *my_alloc(size_t size) {
block_t *b = first_fit(size);
if (!b) return NULL;
b->free = 0;
return (void *)(b + 1);
}Liberando um Bloco
Para liberar, recue do ponteiro do usuário até o cabeçalho e altere a sinalização de livre. O bloco agora está qualificado para reutilização na próxima busca.
Recuperar o cabeçalho a partir do conteúdo usa o mesmo truque de ponteiro de um passo que vimos anteriormente.
void my_free(void *p) {
if (!p) return;
block_t *b = (block_t *)p - 1;
b->free = 1;
}Coalescência de Blocos Livres Adjacentes
Liberar blocos isoladamente deixa o pool cheio de pequenos blocos livres. A coalescência combina um bloco liberado com o bloco seguinte se ele também estiver livre, reconstruindo regiões contíguas maiores.
Isso combate a fragmentação externa para que solicitações grandes futuras ainda possam ser atendidas.
void coalesce(block_t *b) {
if (b->next && b->next->free) {
b->size += sizeof(block_t) + b->next->size;
b->next = b->next->next;
}
}Uma Demonstração Executável de Lista Livre
Este programa completo inicializa um pool, aloca dois blocos, libera o primeiro e então o reutiliza para uma solicitação menor, comprovando que a lista livre funciona.
#include <stdio.h>
#include <stddef.h>
typedef struct block { size_t size; int free; struct block *next; } block_t;
static unsigned char pool[1024];
static block_t *head;
void heap_init(void){ head=(block_t*)pool; head->size=sizeof(pool)-sizeof(block_t); head->free=1; head->next=NULL; }
block_t *first_fit(size_t s){ for(block_t *b=head;b;b=b->next) if(b->free&&b->size>=s) return b; return NULL; }
void *my_alloc(size_t s){ block_t *b=first_fit(s); if(!b) return NULL; b->free=0; return (void*)(b+1); }
void my_free(void *p){ if(!p) return; ((block_t*)p-1)->free=1; }
int main(void){
heap_init();
int *a = my_alloc(sizeof(int));
*a = 7;
printf("a=%d free=%d\n", *a, head->free);
my_free(a);
printf("after free: free=%d\n", head->free);
return 0;
}O Custo da Busca
Uma única lista livre encadeada faz com que a alocação seja O(n) em relação ao número de blocos. Com muitas alocações, isso se torna lento.
Os alocadores reais usam listas livres segregadas (compartimentos por tamanho) ou árvores para tornar a busca próxima de O(1). O princípio da reutilização permanece o mesmo.
/* Segregated lists: one bucket per size class */
static block_t *bins[NUM_SIZE_CLASSES];
/* lookup goes straight to the right bucket */Liberação Dupla e Corrupção
Marcar um bloco como livre duas vezes ou escrever além do tamanho de um bloco corrompe os cabeçalhos vizinhos. A próxima busca então segue um ponteiro next inválido e falha.
É por isso que os erros de memória em C são tão perigosos: os próprios metadados do alocador ficam ao lado dos seus dados.
Reunindo a Reutilização
Um alocador de lista livre funcional precisa de inicialização, uma estratégia de encaixe, alocação, liberação e coalescência. Com esses elementos, a memória circula pelo pool em vez de crescer indefinidamente.
O refinamento restante é dividir blocos grandes demais e respeitar o alinhamento, assunto da lição final.
Verificação Rápida
Pense no que impede uma lista livre de se fragmentar excessivamente.
Recapitulação
Uma lista livre vincula blocos por meio de cabeçalhos, permitindo que alocações individuais sejam liberadas e reutilizadas. A busca pelo primeiro encaixe encontra um bloco, a liberação altera uma sinalização e a coalescência combina os vizinhos para combater a fragmentação.
A busca linear é O(n); os alocadores de produção agrupam os blocos por tamanho para obter velocidade. Em seguida, adicionaremos divisão e alinhamento.
Aprenda C com um tutor de IA — grátis
Escreva e execute código real no seu navegador, obtenha ajuda instantânea de um tutor de IA 24/7 e continue de onde parou na web ou no app.
- Cursos
- 39
- Aulas
- 144
Perguntas Frequentes
A aula “Listas livres e reutilização” é grátis?
Sim — o texto completo de “Listas livres e reutilização” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de C Academy, atualize para CoddyKit PRO. O curso de C Academy inclui 4 aulas no total.
O que vou aprender em “Listas livres e reutilização”?
Acompanhe e recicle blocos. Você pratica C Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar C Academy?
Nenhuma experiência prévia é necessária. C Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “Listas livres e reutilização”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de C Academy?
Sim. Cada aula de C Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Como funciona malloc
- Um alocador bump simples
- Listas livres e reutilização
- Alinhamento e divisão