Corrigé 40  Enoncé

Une structure simple de fichiers avec récupération dynamique des fragments.

Soient F un Fichier de vecteur ( 1024 ) de caractères avec un entête à trois champs ( Entier , Entier , Entier ) qui désigne respectivement le dernier bloc, le nombre de trous et le nombre d'articles et qui représentent donc les caractéristiques du fichier. Buf1 désigne le buffer associé à F

Soit Table_trous un vecteur ( 100 ) de ( Entier , Entier , Entier ) désignant respectivement le numéro du bloc, le déplacement et la longueur.

Création

    Ouvrir ( F , 'f.pas' , 'N' )
    Aff_entete ( F , 1 , 0 )
    Aff_entete ( F , 2 , 0 )
    Aff_entete ( F , 3 , 0 )
    Fermer ( F )

Insertion

    Cle := Caract ( Art , 1 ) + Caract ( Art , 2 ) +
    Caract ( Art , 3 ) + Caract ( Art , 4 )
    Long := Longchaine ( Art )
    SI ( Entete ( F , 3 ) = 0 )
        { première insertion }
        Copier ( C ( Long ) + Art , Long + 3 , 1 )
        Aff_entete ( F , 3 , Entete ( F , 3 ) + 1 )
        Rajouter ( F , Buf1 )

        SI Taille - ( Long + 3 ) > 0
            Inserer_trou ( 1 , Long + 3 + 1 , Taille - ( Long + 3 ) )
            Aff_entete ( F , 2 , Entete ( F , 2 ) + 1 )
        FSI
        Aff_entete ( F , 1 , Entete ( F , 1 ) + 1 )

    SINON
        Rechercher ( Cle , Trouv , Adr , Depl , L )
        SI NON Trouv
            Rechercher_trou ( Long + 3 , Trouv , A , B , L )
            SI Trouv
                Liredir ( F , Buf1 , A )
                Copier ( C ( Long ) + Art , Long + 3 , B )
                Aff_entete ( F , 3 , Entete ( F , 3 ) + 1 )
                Ecriredir ( F , Buf1 , A )
                Supprimer_trou ( A , B )
                Aff_entete ( F , 2 , Entete ( F , 2 ) - 1 )
                SI L - ( Long + 3 ) > 0
                    Inserer_trou ( A , B + Long + 3 , L - ( Long + 3 ) )
                    Aff_entete ( F , 2 , Entete ( F , 2 ) + 1 )
                FSI
            SINON
                Copier ( C ( Long ) + Art , Long + 3 , 1 )
                Aff_entete ( F , 3 , Entete ( F , 3 ) + 1 )
                Rajouter ( F , Buf1 )
                SI Taille - ( Long + 3 ) > 0
                    Inserer_trou ( Entete ( F , 1 ) + 1 , Long + 3 + 1 ,
                    Taille - ( Long + 3 ) )
                    Aff_entete ( F , 2 , Entete ( F , 2 ) + 1 )
                FSI
                Aff_entete ( F , 1 , Entete ( F , 1 ) + 1 )
            FSI
        SINON
            Ecrire ( 'cle existe ' )
        FSI
    FSI


Recherche

Rechercher ( Cledonnee , Trouv1 , Adr , Depl , Lg )

    Ouvrir ( F , 'f.pas' , 'A' )
    Deb := 1
    Adr := 1
    Trouv1 := FAUX
    TANTQUE NON FINfich ( F ) Et ( NON Trouv1 )
        Liredir ( F , Buf1 , Adr )
        TANTQUE ( Deb <= Taille ) Et NON Trouv1
            Est_ce_un_trou ( Adr , Deb , Trouv2 , L )
            SI Trouv2
                Deb := Deb + L
            SINON
                Extraire ( Deb , 3 , Chainelg )
                Lg := E ( Chainelg )
                Extraire ( Deb + 3 , 4 , Cle )
                SI Cle = Cledonnee
                    Trouv1 := VRAI
                SINON
                    Deb := Deb + Lg + 3
                FSI
            FSI
        FTANTQUE
        SI NON Trouv1
            Adr := Adr + 1
            Deb := 1
        FSI
    FTANTQUE


Réorganisation

    POUR I := 1 , ENTETE ( F , 1 )
        LIREDIR ( F , Buf1 , I )
        Pos := 1
        Continue := VRAI
        TANTQUE Continue
            Deb := 1
            TANTQUE Deb < Taille
                Est_ce_un_trou ( I , Deb , Trouv , Long )
                SI Trouv
                    Deb := Deb + Long
                    Supprimer_trou ( I , Deb )
                    AFF_ENTETE ( F , 2 , ENTETE ( F , 2 ) - 1 )
                SINON
                    Extraire ( Deb , 3 , Ch )
                    Lg := E ( Ch )
                    SI Pos # 1 :
                        Extraire ( Deb , Lg + 3 , Ch )
                        Copier ( Ch , Lg + 3 , Pos )
                    FSI
                    Deb := Deb + Lg + 3
                    Pos := Pos + Lg + 3
                FSI
            FTQ
            SI Pos > 1
                ECRIREDIR ( F , Buf1 , Adr )
                Inserer_trou ( Adr , Pos , Taille - Pos + 1 )
                AFF_ENTETE ( F , 2 , ENTETE ( F , 2 ) + 1 )
                Continue := FAUX
            SINON
                LIREDIR ( F , Buf1 , ENTETE ( F , 1 ) )
                AFF_ENTETE ( F , 1 , ENTETE ( F , 1 ) - 1 )
            FSI
        FTQ
    FPOUR

Mesures

Nombre moyen d'accès pour les opérations considérées :
Recherche : N/2
Insertion : N/2 ( Recherche) + 2 ( Lecture + écriture)
Suppression : N/2 ( Recherche)

Le but de la réorganisation est double : récupérer l'espace disque et accélérer les opérations sur fichiers.