Composant tableau dynamique

Introduction

Un problème tant classique que recurrent se pose très souvent. C'est le problème de la gestion de la mémoire. En temps normal, pour de petites quantités de mémoire ponctuellement nécessaires, les points d'entrée malloc() et free() remplissent très bien leur fonction. Cependant, lorsqu'il est nécessaire d'allouer de grandes quantités de mémoire dont tous les atomes sont équivalent en taille, ces fonctions standards laissent à désirer, en particulier du fait de leur faibles performances et du nombre d'appels importants à ces routines.
Une autre fonction standard est calloc(), peut nous aider lorsque l'on gère des tableaux. Malgré tout, cette fonction ne permet pas de modifier la taille des tableaux alloués. Il est alors nécessaire de passer par realloc() qui ne garantie pas que les données existantes ne seront pas déplacées.
Le composant « dyna », qui est une réécriture du composant storage nous permet de simplifer la gestion de la mémoire pour des tableaux de grandes tailles, dont tous les composants sont équivalents.
Il nous permet d'ajouter autant d'éléments que l'on veut, s'occupe de réallouer si besoin, garantit que les données ne seront pas déplacées lors des acroissements de taille.
Contrairement au composant storage, il permet aussi de déallouer des éléments de manière atomique.
En revanche, sous sa forme actuelle, l'opération de libération complète de la mémoire est un tout petit peu plus longue et est fonction du nombre de pages et du nombre de cases libres.

Ce composant sera particulièrement utile lors de la mise en cache de données en mémoire.

Il sera aussi particulièrement efficace en tant qu'allocateur spécifique générique. Par exemple, si un module quelconque doit créer de nombreuses structures, l'utilisation de malloc/free sera très lente. L'utilisation de dyna pour préallouer ces éléments permettra de gagner beaucoup de temps. De même, la désallocation deviendra beaucoup plus rapide que si elle devait se faire élément par élément.

Principe

Le principe du composant dyna repose sur celui des tableaux dynamiques. Connaissant la taille d'un élément, le composant pré-alloue une certaine quantité d'éléments.
Lorsqu'un nouvel espace est demandé, le pointeur sur les données locales est passé à la fonction. La fonction prend le premier espace libre du tableau et recopie les données du pointeur sur la variable locale de la fonction appelante, puis le « nouveau » pointeur est retourné.
S'il n'y a plus d'espace disponible, le composant réalloue la même quantité qu'il avait préallouée au départ. Cette quantité représente la « granularité » de l'allocation. Elle est passée en paramètre avec la taille d'un élément lors de la construction du composant.
La réallocation ne peut pas s'effectuer de manière directe par un simple realloc(). En effet, la fonction de réllocation de la bibliothèque standard ne garantie pas la pérénité de la position dans la mémoire. Au contraire, realloc() se charge même de déplacer les données (de les recopier) dans la nouvelle zone mémoire si la précédente ne permettait pas le redimentionnement.
Cette pratique est la plupart du temps tout à fait raisonnable. Mais dans de nombreux cas de figure, les données stockée par notre composant dyna peuvent être indexées par différents autres composants, comme les des btree qui permettent d'ordonner les données, des listes chaînées, ou encore des tables de hashage qui constituent des un système d'indexation.
Si les données référencées en terme de pointeurs par d'autres composants, il est dangereux de déplacer les données. Les pointeurs stockés dans les autres composants pointerait alors dans des zones non réservées pouvant contenir n'importe quoi et rendrait les autres composants caducs, voire dangereux.
Au lieu de réallouer par realloc, on utilisera plutôt un système paginé dont chaque page aura pour taille le produit de la taille d'un élément du stockage par le facteur de granularité défini plus haut.

Lorsque tous les éléments d'une page sont utilisés, on alloue une nouvelle page de grain * size.

Afin de permettre d'éliminer un ou des éléments stockés dans dyna, il va nous falloir ajouter 2 mécanismes supplémentaires.
Il n'est pas nécessaire de « libérer » réellement la mémoire lié à un élement. Au contraire, l'objectif du composant est d'effectuer des préallocations pour accélérer les temps d'allocation et de désallocation mémoire.
Par contre, il va falloir faire en sorte de pouvoir réutiliser, à moindre frais, notre élément fraichement vidé. Pour ce faire, nous ajoutons une liste chainée dans cases libérées. Quand on voudra allouer de la mémoire pour un élément, dyna va tout d'abord regarder dans la liste chaînée si un élément est présent. Si c'est le cas, cet élément (le premier de la liste chaînée), sera éliminé de la liste et immédiatement utilisé pour stocker un nouvel élément.

Se pose alors un nouveau problème : si l'on vient juste d'éffacer l'élément n°i d'un tableau en contenant n, le premier élément entré reprendra la place n°i, ce qui peut être gênant lors d'un accès séquentiel aux éléments du tableau.
Pour y remédier, nous introduisons une deuxième structure : la gestion d'un index.
Notre index sera un tableau de pointeurs pointant directement vers les éléments du tableau. Ainsi, peu importe le nombre et l'ordre des éléments en mémoire, l'index se débrouillera pour pointer correctement vers la bonne case mémoire.


Lorsque nous éliminerons un élément n°i quelconque, la case libre sera ajoutée à la liste chainée. Ensuite, nous déplacerons tous les éléments i+1 à n vers i à l'aide d'un memmove.

La gestion de l'index nous permet aussi bien d'inserrer un élément entre 2 cases quelconques. Il suffit d'agrandir le tableau index (s'il n'y a plus de place dedans), et de déplacer tous les éléments de i à n vers i+1 à n+1, puis d'affecter à la case i l'adresse de la mémoire affecté au nouvel élément.

En résumé, on tend à diminuer le nombre de malloc en allouant à chaque fois un certain nombre (grain) d'éléments à chaque fois. Plus le grain est grand, et moins on sera suceptible d'utiliser la fonction malloc(). A contrario, plus la granularité est grande, et plus on risque d'avoir de l'espace alloué mais non utilisé.
Ce composant permet de gérer des entités composées de nombreux éléments de taille identique, comme les tables d'une base de données. On ne pourra éliminer ou inserrer un élément de la table de manière atomique.

Architecture du composant dyna

Notes préliminaires

Notre composant a pour but de stocker des entités composées d'éléments identiques de façon rapide et efficace. Il doit décharger son utilisateur de la notion de gestion de la mémoire. Il doit assurer la pérénité de la localisation des données en mémoire afin de pouvoir indexer ou manipuler ces données dans d'autre composants.

Contraintes primaires

Pas d'a priori sur le contenu

La notion de généricité nécessitent impérativement de ne pas avoir d'a priori sur le type des données à stocker. Ce point peut être géré en C++ par l'utilisation de types paramétres ou « templates ». En C, il suffira d'utiliser la notion de type générique représentée par void * et de savoir ce que l'on en fait.

Garantie de l'immobilité des données

Il est impératif de garantir l'abscence de déplacement des données stockées. En effet, comme nous l'avons vu plus haut, les données peuvent être utilisées à plusieurs endroits indépendants et référencées par différents composant. Tout déplacement au cours de l'exécution du programme entraînerait la perte des informations réféncées.

Facilité d'utilisation

Ce composant doit apporter une réelle valeur ajoutée en simplifiant de maniète importante la gestion de la mémoire. L'interface doit donc être la plus simple et la plus dépouillée possible.

Contrainte secondaire structurante

Enfin, il est nécessaire de prendre en compte la possibilité de multithreading. Cette contrainte n'est pas une contrainte primaire, mais elle ajoute des restriction structurantes au programme.
Nous devons en effet tenir compte des verrous mutuellements exclusifs (mutex locks), et nous devons nous arranger pour empêcher toute opération directe sur la structure de données. Il est donc nécessaire de cacher la structure aux programmes utilisateurs et de définir toutes les méthodes modifiant ou lisant les paramètres « visibles » du composant.

Structuration des données

Notre structure de base doit contenir des éléments invariant pendant toutes la durée de vie du composant. Ces données invariantes sont : la taille d'un élément et la granularité.
La structure doit aussi contenir des éléments variables. Ceux-ci sont : le nombre d'éléments alloués, la nombre d'éléments utilisés, le nombre de pages, et le tableau de pages. Enfin, pour la partie

L'interface

« Constructeur » et « destructeur »

/* Constructor: */
pdyna_t dyna_new(size_t unit, size_t grain);

/* Destructor :*/
pdyna_t dyna_destroy(pdyna_t ps);

Ajout d'éléments

char * dyna_add(pdyna_t ps, char *pdata);

Récupération d'un élément du « tableau »

char * dyna_get(pdyna_t ps, int i);

Information et supervision

int dyna_used(pdyna_t ps);

int dyna_allocated(pdyna_t ps);

int dyna_available(pdyna_t ps);

int dyna_grain(pdyna_t ps);

int dyna_unit(pdyna_t ps);

Limitations

Conclusion