Listes libres et réutilisation
Suivez et recyclez les blocs.
Listes libres et réutilisation est une leçon C Academy gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage C Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours C Academy comprend 4 leçons au total.
Au-delà de l’allocateur par incrément
Pour libérer des blocs individuels et les réutiliser, nous avons besoin d’un suivi administratif. Une liste de blocs libres est une liste chaînée de blocs disponibles que l’allocateur parcourt avant de réserver de la mémoire neuve.
Chaque block contient un en-tête afin que l’allocateur puisse retrouver sa taille et le relier au block suivant de la chaîne.
En-tête de block avec un lien
Nous complétons l’en-tête avec un pointeur next et un indicateur free. Ensemble, ils transforment notre zone mémoire en une liste de blocs que l’on peut parcourir.
La charge utile se trouve immédiatement après l’en-tête en mémoire.
typedef struct block {
size_t size; /* payload bytes */
int free; /* 1 if reusable */
struct block *next; /* next block in pool */
} block_t;Initialisation d’un grand block libre
Au démarrage, toute la zone mémoire constitue un unique grand block libre. Au fil des allocations, nous le découpons ; lors des libérations, nous marquons les blocs comme réutilisables.
La tête de la liste est ce block initial qui couvre toute l’arène.
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;
}Recherche first_fit
La stratégie de réutilisation la plus simple est first_fit : parcourez la liste et renvoyez le premier block libre suffisamment grand. Elle est rapide et tend à conserver les petits blocs près du début.
Les solutions de rechange sont la meilleure adéquation (le plus petit block suffisant) et la pire adéquation, au prix de compromis entre rapidité et comportement face à la fragmentation.
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;
}Allocation à partir d’un block libre
Une fois une adéquation trouvée, nous le marquons comme utilisé et renvoyons le pointeur situé juste après son en-tête. Pour l’instant, nous remettons tout le block ; le découpage sera abordé dans la leçon suivante.
Le pointeur renvoyé est block + 1, ce qui masque l’en-tête à l’appelant.
void *my_alloc(size_t size) {
block_t *b = first_fit(size);
if (!b) return NULL;
b->free = 0;
return (void *)(b + 1);
}Libération d’un block
Pour libérer un block, reculez depuis le pointeur utilisateur jusqu’à son en-tête et inversez l’indicateur de disponibilité. Le block peut alors être réutilisé lors de la prochaine recherche.
Récupérer l’en-tête à partir de la charge utile repose sur la même astuce de pointeur d’un pas que celle vue précédemment.
void my_free(void *p) {
if (!p) return;
block_t *b = (block_t *)p - 1;
b->free = 1;
}Fusion de blocs libres adjacents
La libération seule laisse la zone mémoire remplie de petits blocs libres. La fusion réunit un block libéré avec le block suivant si celui-ci est également libre, afin de recréer de grandes régions contiguës.
Elle lutte contre la fragmentation externe pour que les futures demandes importantes puissent encore être satisfaites.
void coalesce(block_t *b) {
if (b->next && b->next->free) {
b->size += sizeof(block_t) + b->next->size;
b->next = b->next->next;
}
}Une démonstration exécutable de la liste de blocs libres
Ce programme complet initialise une zone mémoire, alloue deux blocs, libère le premier, puis le réutilise pour une demande plus petite, ce qui prouve que la liste de blocs libres fonctionne.
#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;
}Le coût de la recherche
Une liste chaînée simple de blocs libres signifie que l’allocation est en O(n) par rapport au nombre de blocs. Avec de nombreuses allocations, cela devient lent.
Les allocateurs réels utilisent des listes de blocs libres séparées (des compartiments par taille) ou des arbres afin de rendre la recherche proche de O(1). Le principe de réutilisation reste le même.
/* Segregated lists: one bucket per size class */
static block_t *bins[NUM_SIZE_CLASSES];
/* lookup goes straight to the right bucket */Double libération et corruption
Marquer deux fois un block comme libre, ou écrire au-delà de la taille d’un block, corrompt les en-têtes voisins. La recherche suivante suit alors un pointeur next incohérent et provoque un plantage.
C’est pourquoi les bogues de mémoire en C sont si dangereux : les métadonnées de l’allocateur se trouvent juste à côté de vos données.
Assembler la réutilisation
Un allocateur fonctionnel avec liste de blocs libres a besoin d’une initialisation, d’une stratégie d’adéquation, de l’allocation, de la libération et de la fusion. Grâce à ces éléments, la mémoire circule dans la zone mémoire au lieu de croître indéfiniment.
Le dernier raffinement consiste à découper les blocs surdimensionnés et à respecter l’alignement ; c’est le sujet de la dernière leçon.
Vérification rapide
Réfléchissez à ce qui empêche une liste de blocs libres de se fragmenter excessivement.
Récapitulatif
Une liste de blocs libres relie les blocs par leurs en-têtes afin que les allocations individuelles puissent être libérées et réutilisées. La recherche first_fit trouve un block, la libération inverse un indicateur et la fusion réunit les voisins pour lutter contre la fragmentation.
La recherche linéaire est en O(n) ; les allocateurs de production regroupent les blocs par taille pour gagner en rapidité. Nous allons maintenant ajouter le découpage et l’alignement.
Questions Fréquemment Posées
La leçon « Listes libres et réutilisation » est-elle gratuite ?
Oui — le texte complet de « Listes libres et réutilisation » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours C Academy, passe à CoddyKit PRO. Le cours C Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Listes libres et réutilisation » ?
Suivez et recyclez les blocs. Tu pratiques C Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer C Academy ?
Aucune expérience préalable n'est requise. C Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Listes libres et réutilisation » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon C Academy ?
Oui. Chaque leçon C Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Comment fonctionne malloc
- Un allocateur linéaire simple
- Listes libres et réutilisation
- Alignement et découpage