Problème : Un système de gestion de fichiers avec réorganisation différée

Pour réaliser des opérations sur un fichier o� chaque article est composé de deux champs:

- la clé ( 5 caractères numériques )

- une chaîne de caractères de longueur variable.

on décide de structurer le fichier comme un ensemble de M blocs contigus sur le disque (de 0 à M-1). Chaque bloc est un tableau de B caractères (de 0 à B-1). En plus, pour pouvoir accéder directement à tout article, on maintient une table Tchaîne en mémoire centrale de Max éléments, triée selon la clé, o� chaque entrée est le quadruplé (Cle, Adresse, Déplacement, Longueur) avec :

- Clé : clé de l'article.

- Adresse : adresse du bloc o� se trouve l'article.

- Déplacement : indice dans le bloc ou commence l'article.

- Longueur de l'article.

On décide aussi de réserver les N premiers blocs pour y mettre les caractéristiques et l'index(table Tchaîne).

- le bloc 0 contient les caractéristiques du fichier.

- les (N-1) prochains blocs contiennent la table d'index.

- les blocs suivants contiennent les articles proprement dits.

NB.

* Une chaîne de caractères est assimilée à un tableau de caractères.

* La fonction Long(Y) donne la longueur de la chaîne contenue dans le tableau Y.

* La fonction Chaîne(Nombre) donne la chaîne de caractères associée au nombre Nombre.

* La fonction Nombre(Chaîne) donne le nombre (entier ou réel) associé à la chaîne de caractères.

* Un article peut commencer dans un bloc et finir dans un autre qui lui soit contigu. On dit qu'il est "à cheval" sur 2 blocs.

* Un bloc d'index contient un nombre entier d'entrées de la table d'index.

* La longueur maximale d'un article est la taille du bloc.

Dans l'exemple suivant, on obtient la configuration suivante après l'insertion des articles suivants, faites dans cet ordre ( B = 50 ):

Article = 34537aaaaaaaaaaaaaaa

Article = 12345bbbbbbbbbbbb

Article = 53721ccccc

Article = 33333xxxxxxxxxxxxxxxxxxxxxxxxx

Article = 00000yyyyyyyyyyyyyyyxxxxxxxxxxxxxxxxxxxxxxxxy

Le fichier

Bloc 10 :

51 52 53 51 55 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 49 50 51 52 53 98 98 98 98 98 98 98 98 98 98 98 98 53 51 55 50 49 99 99 99 99 99 51 51 51

Bloc 11 :

51 51 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 48 48 48 48 48 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 120 120 120

Bloc 12 :

120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 121 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32

NB : quelques codes ASCII

'x' = 120; 'y' = 121; 'a' = 97; 'b' = 98 ; 'c' = 99;

'0' = 48 ; '1' = 49 ; '2' = 50 ; etc.

Questions :

*Initialisation : Définir tous les paramètres nécessaires à l'exploitation (caractéristiques) du fichier et dire comment les initialiser.

*Ouverture : Donner une organisation possible du bloc 0 contenant les caractéristiques du fichier et une organisation possible des blocs contenant la table d'index (fournir des schémas respectifs). Ecrire le module qui récupère les caractéristiques du fichier (se trouvant dans le bloc 0), et qui charge en mémoire la table d'index(se trouvant dans les blocs 1,2.. N-1). Donner également une description de la table d'index.

*Consultation : Ecrire le module qui récupère l'article de clé X donnée.

*Insertion : Ecrire le module qui insère un article de clé K donnée et de chaîne Y donnée. Les ajouts d'articles se font en fin de fichier.

*Réorganisation :On suppose que les suppressions sont physiques au niveau de Tchaîne et engendrent donc des "trous" dans le fichier. On décide alors de faire une réorganisation chaque fois que le pourcentage de l'espace inoccupé devient supérieur à un seuil donné.

- Que faut-il rajouter dans les autres modules ?

- Ecrire l'algorithme correspondant.