Notre allocateur précédent doit parcourir successivement l’ensemble des éléments d’un tableau de grande taille pour trouver un bloc libre. Ce temps de parcours peut être pénalisant.
Nous allons proposer une implémentation plus rapide de notre allocateur mémoire qui permettra de trouver un bloc libre en un temps constant.
Notre allocateur va identifier des séries de blocs libres contigus. L’ensemble des séries de blocs libres contigus seront chainées entre-elles.
Nous allons utiliser le premier bloc de chaque série de blocs libres contigus pour mémoriser
L’allocateur mémorisera le numéro du premier bloc de la première série de blocs libres contigus (-1 si il n’y a plus de blocs libres) :
#define BLOC_END -1 static int first_free_blocs;
La recherche d’un bloc libre est donc immédiate à partir de ce numéro first_free_blocs.
On remarque aussi que le coût mémoire de nouvel allocateur est réduit.
L’allocateur cbl fournit l’interface suivante :
#define CBL_BLOCSIZE ... void * cbl_newbloc(); int cbl_freebloc(void *bloc); int cbl_init();
L’allocateur définit un type union pour mémoriser dans un bloc
On conserve un tableau membloc alloué statiquement pour y garder les blocs.
Initialement, l’ensemble des blocs du tableau sont libres, formant une unique série de blocs libres contigus. La variable first_free_blocs sera donc initialisée à 0. Le bloc 0 sera initialisée avec une structure (NBLOCS, CBL_END).
Lors de la désallocation d’un bloc, on ne cherchera pas à le rattacher à une série de blocs libres contigus qui le précèderait ou le suivrait. On créera une nouvelle série de blocs libres contigus constituée d’un unique bloc.