Probleme – Les $k$ dernières lignes d'un flux qu'on ne peut lire qu'une fois

1. Pourquoi le problème est un vrai problème. Un fichier ordinaire a une taille et un accès direct : on peut s'y déplacer. Un flux n'a ni l'une ni l'autre. Quand l'entrée vient d'un tube — ./generer | ./fin — il n'y a pas de fin connue d'avance, pas de position où revenir, et les octets déjà lus sont perdus. Toute solution doit donc décider quoi retenir avant de savoir où le flux s'arrête.

Deux fausses solutions à écarter d'abord. Tout stocker dans un tableau : c'est $\Theta (m)$ en mémoire pour un flux de $m$ lignes, donc impossible sur un flux infini, et gaspilleur sur un gros fichier. Lire deux fois : c'est impossible sur un tube, et deux fois plus lent sur un fichier.

2. Le tampon circulaire. On retient les $k$ dernières lignes lues, dans un tableau de $k$ cases où la ligne numéro $j$ occupe la case $j\mathrm{mod}k$. Chaque nouvelle ligne écrase la plus ancienne — exactement celle dont on n'a plus besoin.

/* Affiche sur stdout les k dernieres lignes du flux f.
   Preconditions : f ouvert en lecture, k >= 1, tampon a k lignes de LIGNE_MAX.
   Un seul passage ; memoire Theta(k), INDEPENDANTE de la taille du flux. */
void fin(FILE* f, int k, char tampon[][LIGNE_MAX]) {
    assert(f != NULL && k >= 1);
    int lues = 0;
    /* INVARIANT : tampon[j % k] contient la ligne j du flux, pour tout j
       verifiant max(0, lues - k) <= j < lues. */
    while (fgets(tampon[lues % k], LIGNE_MAX, f) != NULL) {
        lues = lues + 1;
    }
    int debut = lues > k ? lues - k : 0;
    for (int j = debut; j < lues; j = j + 1) {
        printf("%s", tampon[j % k]);
    }
}

3. Preuve.

Terminaison. Variant : le nombre de lignes restant dans le flux. Chaque tour en consomme une ; fgets rend NULL en fin de flux.

Conservation de l'invariant. Avant le tour numéro lues, l'invariant dit que les cases contiennent les lignes de $\max (0,\text{lues}-k)$ à $\text{lues}-1$. On écrit la ligne lues en case lues % k. Cette case contenait la ligne $\text{lues}-k$ si elle existait : c'est la plus ancienne de l'intervalle, et elle en sort précisément à ce tour. L'invariant est donc rétabli pour $\text{lues}+1$. L'écrasement est correct parce que l'indice modulo $k$ ne peut associer deux lignes de l'intervalle à la même case : deux entiers de $[\text{lues}-k,\text{lues}-1]$ congrus modulo $k$ sont égaux, l'intervalle étant de longueur $k$.

À la sortie, lues est le nombre total de lignes. Les cases contiennent les lignes $\max (0,\text{lues}-k)$ à $\text{lues}-1$, c'est-à-dire les $\min (k,\text{lues})$ dernières, et la boucle d'affichage les parcourt dans l'ordre croissant de $j$ — donc dans l'ordre du fichier. Parcourir les cases de $0$ à $k-1$ les donnerait dans le désordre : c'est la faute que l'indexation par $j$ évite.

Complexité. $\Theta (m)$ en temps pour $m$ lignes, $\Theta (k)$ en mémoire.

Les cas limites, tous vérifiés par la même écriture.

• Flux plus court que $k$. Mesure : sur l'entrée a, b avec $k=3$, la sortie est a, b. Le max de la borne debut traite ce cas sans branche particulière.
• Flux vide. lues vaut $0$, debut vaut $0$, la boucle d'affichage ne tourne pas.
• Gros flux. Mesure sur un fichier de $200000$ lignes et $2488895$ octets, avec $k=3$ : la sortie est ligne 199998, ligne 199999, ligne 200000, identique à celle de tail -3. La mémoire employée est de $3\times 256=768$ octets — soit $0,03\%$ du fichier.

La limite honnête de cette version. fgets tronque toute ligne de plus de LIGNE_MAX - 1 caractères, et le reste est compté comme une ligne de plus. C'est une décision, et elle doit figurer dans la spécification : la fonction traite « les $k$ dernières lignes d'au plus $255$ caractères ». La lever demanderait des lignes de taille dynamique, donc $k$ blocs du tas et autant de free — et la spécification devrait alors dire qui libère.