Listas libres y reutilización
Registre y recicle bloques
Listas libres y reutilización es una lección gratuita de C Academy en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de C Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de C Academy incluye 4 lecciones en total.
Más allá del asignador bump
Para liberar bloques individuales y reutilizarlos, necesitamos llevar un registro. Una lista libre es una lista enlazada de bloques disponibles que el asignador busca antes de tomar memoria nueva.
Cada bloque contiene una cabecera para que el asignador pueda encontrar su tamaño y el enlace al siguiente bloque de la cadena.
Cabecera de bloque con un enlace
Ampliamos la cabecera con un puntero next y una marca free. Juntos convierten nuestro conjunto en una lista de bloques que se puede recorrer.
La carga útil se encuentra inmediatamente después de la cabecera en la memoria.
typedef struct block {
size_t size; /* payload bytes */
int free; /* 1 if reusable */
struct block *next; /* next block in pool */
} block_t;Inicialización de un único bloque libre grande
Al iniciarse, todo el conjunto es un único bloque libre enorme. A medida que se realizan asignaciones, lo dividimos; cuando se liberan bloques, los marcamos como reutilizables.
La cabeza de la lista es este bloque inicial, que cubre toda el área de memoria.
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;
}Búsqueda del primer bloque adecuado
La estrategia de reutilización más sencilla es elegir el primer bloque adecuado: recorrer la lista y devolver el primer bloque libre que tenga el tamaño suficiente. Es rápida y tiende a mantener los bloques pequeños cerca del principio.
Las alternativas son elegir el bloque más adecuado (el bloque suficiente más pequeño) y elegir el peor bloque, intercambiando velocidad por un comportamiento distinto frente a la fragmentación.
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;
}Asignación desde un bloque libre
Cuando encontramos un bloque adecuado, lo marcamos como usado y devolvemos el puntero que está justo después de su cabecera. Por ahora entregamos el bloque completo; la división se verá en la siguiente lección.
El puntero devuelto es block + 1, de modo que la cabecera queda oculta para el llamador.
void *my_alloc(size_t size) {
block_t *b = first_fit(size);
if (!b) return NULL;
b->free = 0;
return (void *)(b + 1);
}Liberación de un bloque
Para liberar un bloque, retroceda desde el puntero del usuario hasta su cabecera y cambie la marca de libre. El bloque podrá reutilizarse en la siguiente búsqueda.
Recuperar la cabecera desde la carga útil utiliza el mismo truco de punteros de un paso que vimos anteriormente.
void my_free(void *p) {
if (!p) return;
block_t *b = (block_t *)p - 1;
b->free = 1;
}Fusión de bloques libres adyacentes
Liberar bloques sin más deja el conjunto lleno de pequeños bloques libres. La fusión combina un bloque liberado con el siguiente si este también está libre, reconstruyendo regiones contiguas más grandes.
Esto combate la fragmentación externa para que las solicitudes grandes futuras se puedan satisfacer.
void coalesce(block_t *b) {
if (b->next && b->next->free) {
b->size += sizeof(block_t) + b->next->size;
b->next = b->next->next;
}
}Una demostración ejecutable de una lista libre
Este programa completo inicializa un conjunto, asigna dos bloques, libera el primero y después lo reutiliza para una solicitud más pequeña, demostrando que la lista libre 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;
}El coste de buscar
Una lista libre simplemente enlazada hace que la asignación sea O(n) respecto al número de bloques. Con muchas asignaciones, esto se vuelve lento.
Los asignadores reales utilizan listas libres segregadas (contenedores por tamaño) o árboles para que la búsqueda se acerque a O(1). El principio de reutilización sigue siendo el mismo.
/* Segregated lists: one bucket per size class */
static block_t *bins[NUM_SIZE_CLASSES];
/* lookup goes straight to the right bucket */Doble liberación y corrupción
Marcar un bloque como libre dos veces o escribir más allá de su tamaño corrompe las cabeceras vecinas. La siguiente búsqueda sigue entonces un puntero next basura y se bloquea.
Por eso los errores de memoria en C son tan peligrosos: los metadatos del propio asignador se encuentran justo al lado de sus datos.
Integración de la reutilización
Un asignador de lista libre funcional necesita inicialización, una estrategia para encontrar bloques adecuados, asignación, liberación y fusión. Con estos elementos, la memoria circula por el conjunto en lugar de crecer indefinidamente.
El refinamiento restante consiste en dividir los bloques sobredimensionados y respetar la alineación, que es el tema de la lección final.
Comprobación rápida
Piense en qué evita que una lista libre se fragmente gravemente.
Resumen
Una lista libre enlaza bloques mediante cabeceras para que las asignaciones individuales se puedan liberar y reutilizar. La búsqueda del primer bloque adecuado encuentra un bloque, la liberación cambia una marca y la fusión combina los bloques vecinos para combatir la fragmentación.
La búsqueda lineal es O(n); los asignadores de producción agrupan por tamaño para ganar velocidad. A continuación añadiremos la división y la alineación.
Aprende C con un tutor de IA — gratis
Escribe y ejecuta código real en tu navegador, obtén ayuda instantánea de un tutor de IA disponible 24/7 y continúa donde lo dejaste en la web o en la aplicación.
- Cursos
- 39
- Lecciones
- 144
Preguntas frecuentes
¿La lección «Listas libres y reutilización» es gratis?
Sí — el texto completo de «Listas libres y reutilización» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de C Academy, actualiza a CoddyKit PRO. El curso de C Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Listas libres y reutilización»?
Registre y recicle bloques Practicas C Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar C Academy?
No se requiere experiencia previa. C Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «Listas libres y reutilización»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de C Academy?
Sí. Cada lección de C Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Cómo funciona malloc
- Un asignador bump sencillo
- Listas libres y reutilización
- Alineación y división