Discussion :

[Lavock]

Non ><... Tu y arrive comment à la ligne que tu veux ? Ben pendant ce traitement, tu retiens les lignes.

[elishac]

J'y arrive avec fseek .

[Lavock]

Hum, attent, je veux bien mais >< Tu l'ouvre en binaire du coup ?

Enfin, si tu connais l'offset de ta donnée à testé, comment peux-tu ne pas connaître celui de la ligne précédente ?

[Melem]

@elishac : Ton entêtement nous fait tourner en rond.

- Soit tu décides d'écrire un programme compatible avec une poignée de formats de fichiers texte uniquement. Dans ce cas tu détectes le format de fichier comme tu sembles vraiment avoir envie de faire et t'es libre d'utiliser fseek. Mais avec solution, tu dis au revoir à la portabilité. Sous Mac OS par exemple, la marque de fin de ligne (CRLF sous DOS/Windows et LF sous UNIX) est CR simplement, et je ne parle même pas encore du code de LF qui est 10 (0x0A) en ASCII et 37 (0x25) en EBCDIC ...

- Soit tu décides d'écrire un programme 100% portable et tu n'utilise fseek qu'avec 0 ou des valeurs renvoyées par ftell. Cela requiert bien évidemment que tu aies déjà parcouru le fichier de la position 0 à la plus grande position que tu as déjà obtenue (ou que tu AIES PU obtenir) avec ftell, ce que tu veux éviter.

S'il y a un truc que t'as toujours pas bien saisi ou qui t'as peu convaincu, n'hésite jamais ...

[elishac]

Bon, je vois que vous ne voyez pas du tout où je veux en venir. Je vais donc tout écrire.
C'est par conséquent un peu long, désolé.
Mon but est le suivant : à partir d'un log de longue taille, je veux pouvoir accéder à la ligne d'une date précise de ce log (les dates sont en début de ligne et au format "Jan 11 00:00:00"), sans avoir à lire tout le log pour y parvenir. Si la date cherchée n'y est pas, on renvoie la date présente immédiatement plus récente. Si elle est en doublon, on renvoie la plus ancienne. On cherche les dates par dichotomie (pondérée).
Voici mon code tel qu'il est à présent (qui ne marche pas :-( )

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <stdio.h>
#include <string.h>
#include <time.h>
 
time_t string_to_time_t(char *s)
{
        time_t rawtime;
        struct tm * timeinfo;
        char month_s[4] ;
        int month,day,hour,minute,second;
        sscanf(s, "%3s %d %d:%d:%d", month_s, &day, &hour, &minute, &second);
 
        char * month_names[12]={"Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"};
        int i=0;
        while( strcmp(month_s,month_names[i]) != 0  )
                i++;
        month=i;
 
        time (&rawtime);
        timeinfo=localtime(&rawtime);
        timeinfo->tm_mon=month;
        timeinfo->tm_mday=day;
        timeinfo->tm_hour=hour;
        timeinfo->tm_min=minute;
        timeinfo->tm_sec=second;
        return mktime(timeinfo);
}
 
time_t get_date(FILE *fp)
{
        char s[16];
        return string_to_time_t(fgets(s,16,fp));
}
 
int goto_nextline(FILE *fp)
{
        int c; //EOF is a int
        do c=fgetc(fp) ;
        while ((c != '\n') &&  (c !=EOF));
        if (c=='\n')
                return 0;
        else
                return 1;
}
 
 
void goto_beginning_of_line(FILE *fp)
{
        int c;
        if (ftell(fp) !=0)
        {
                fseek(fp,1,SEEK_CUR);
                do
                {
                        fseek(fp,-2,SEEK_CUR);
                        c=fgetc(fp);
                }
                while ( ftell(fp)-2>=0 && c != '\n' );
                if( ftell(fp)==1 )
                        fseek(fp,-1,SEEK_CUR);
        }
}
 
int search_date(FILE *fp, time_t time)
{
        FILE *fpmin, *fpmax, *fptmp;
        time_t timemin, timemax;
        fpos_t pos;
        fpmin=fpmax=fptmp=fp;
        fseek(fpmin,0,SEEK_SET);
        fseek(fpmax,0,SEEK_END);
        fseek(fptmp,0,SEEK_SET);
        timemin=get_date(fpmin);
        goto_beginning_of_line(fpmax);
        timemax=get_date(fpmax);
        fgetpos(fpmin,&pos);
        while(goto_nextline(fpmin)==0 && get_date(fpmin)<time)
        {
                fsetpos(fpmin,&pos);
                fsetpos(fptmp,&pos);
                float weight=(float)(time-timemin)/(float)(timemax-timemin);
                long difference=ftell(fpmax)-ftell(fpmin);
                fseek(fptmp,(long) weight * difference,SEEK_CUR);
                goto_beginning_of_line(fptmp);
                if (time < get_date(fptmp))
                {
                        fpmax=fptmp;
                        timemax=get_date(fpmax);
                }
                else
                {
                        fpmin=fptmp;
                        timemin=get_date(fpmin);
                        fgetpos(fpmin,&pos);
                }
        }
        fp=fpmin;
        return 0;
}
 
int main(int argc, char **argv)
{
        FILE *fp=fopen("log.txt","r");
        if (fp==NULL)
                fprintf(stderr,"File can't be opened\n");
        else
        {
                time_t time=string_to_time_t("Dec 11 12:00:00");
                search_date(fp,time);
                //faire des choses ici
        }
        fclose(fp);
        return 0;
}

Au moins comme ça vous voyez où j'ai besoin d'aller au début d'une ligne.
J'ai besoin de votre aide pour faire marcher ce programme (j'ai un segmentation fault pour l'instant).
Voilà, merci d'avance.

[Lavock]

Ton offset est donc calculable. Pourquoi donc tu ne le calculerais pas pour aller au début de la ligne précédente ?

[elishac]

Je ne vois pas comment je pourrais le calculer...

[Lavock]

Ton nombre de ligne actuelle (offset actuelle/taille d'une ligne) - 1 ?
Au passage, il te faudra savoir la taille d'une ligne. Ce qui ne pose pas de problème en pré-traitement à l'aide d'un getline.

[elishac]

La taille d'une ligne n'est malheureusement pas fixe. La seule chose que l'on sache, c'est que toute ligne commence par une date, au format spécifié précédemment.

[Lavock]

Donc comment procède tu au seek lors de ta recherche dicotomique ?

[elishac]

Etant donné deux bornes (inf et sup, appelées fpmin et fpmax dans mon programme), je prends le milieu des deux, puis je vais au début de la ligne du caractère où je me suis rendu.
(en fait, plutôt que de prendre simplement le milieu des deux, je prends le barycentre de ces deux points avec un poids correspondant à la distance entre la date cherchée et les extrémités ; j'ai fait cela car souvent je vais chercher une date récente dans un log très long, mais ce n'est qu'un détail et ça ne rajoute que deux lignes de code).

[Lavock]

Oui, mais comme les lignes ne sont pas de longueur fixe, tu ne sais pas ou tu es vraiment non ? Tu pourrais très bien être à la deuxième ligne sur dix, parce que la première est est dix fois plus grande...

[elishac]

Certes, mais je ne vois pas en quoi ça dérange.
L'important c'est juste qu'on a une borne supérieure, une borne inférieure, et on sait que notre test (fptmp) est entre les deux. A force de diminuer la borne sup (ou inf), on finira par trouver notre objet cherché. Peu importe si on n'etait pas exactement au milieu, l'important c'est d'etre entre les deux (d'ailleurs, je l'ai dit, je ne fais pas le milieu des deux mais un calcul un peu évolué car je connais la date que je cherche).

[Melem]

Beaucoup d'erreurs dans le code, que ce soit au niveau algorithmique qu'au niveau du code C en soit, presque toutes concentrées dans search_date (que j'ai du complètement refaire au lieu de modifier une partie bien précise ). Elles sont trop nombreuses pour être énumérées ici mais la plus horrible était de voir des affectations telles que FILE * fp2 = fp1; Ca ne sauvegarde pas l'état du fichier pointé par fp1 dans un nouveau fichier (fp2). Ca copie juste l'adresse contenue dans le pointeur fp1 vers le pointeur fp2. Voici une version qui marche mais qu'on peut toujours améliorer (améliorer la robustesse, remplacer les appel à exit par du code plus "doux", (exit est d'ailleurs une fonction dont il ne faut jamais abuser ...), choisir un même style pour les valeurs de retour des fonctions (soit toutes "error level" soit toutes "bool"), améliorer la présentation du code, etc.). Je n'ai pas le temps de faire ces modifs. Bon codage.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
 
#define _ENDOFLN '\n' /* Le dernier caractere de la marque de fin de ligne. */
 
time_t string_to_time_t(const char *s)
{
    time_t rawtime;
    struct tm * timeinfo;
    char month_s[4];
    int month,day,hour,minute,second;
    char * month_names[12]={"Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"};
    int i = 0;
 
    if (sscanf(s, "%3s %d %d:%d:%d", month_s, &day, &hour, &minute, &second) != 5)
    {
        printf("Le format du fichier n'est pas reconnu.\n");
        exit(0);
    }
 
    while(strcmp(month_s,month_names[i]) != 0 && i < 12)
        i++;
 
    if (i > 12)
    {
        printf("Le format du fichier n'est pas reconnu.\n");
        exit(0);
    }
 
    month=i;
 
    time(&rawtime);
    timeinfo=localtime(&rawtime);
    timeinfo->tm_mon=month;
    timeinfo->tm_mday=day;
    timeinfo->tm_hour=hour;
    timeinfo->tm_min=minute;
    timeinfo->tm_sec=second;
    return mktime(timeinfo);
}
 
time_t get_date(FILE *fp)
{
    static char s[16];
    return string_to_time_t(fgets(s,16,fp));
}
 
int goto_beginning_of_nextline(FILE *fp)
{
    int c;
    do c=fgetc(fp) ;
    while ((c != _ENDOFLN) && (c !=EOF));
    if (c==_ENDOFLN)
        return 0;
    else
        return 1;
}
 
void goto_beginning_of_line(FILE *fp)
{
    int c, done;
 
    c = '\0';
    done = (ftell(fp) == 0);
    while ((!done) && (c != EOF))
    {
        fseek(fp,-1,SEEK_CUR);
        done = (ftell(fp) == 0);
 
        if (!done)
        {
            c=fgetc(fp);
            done = (c == _ENDOFLN);
 
            if (!done)
                fseek(fp,-1,SEEK_CUR);
        }
    }
}
 
long filesize(FILE * f)
{
    long pos, size;
 
    pos = ftell(f);
    fseek(f, 0, SEEK_END);
    size = ftell(f);
    fseek(f, pos, SEEK_SET);
 
    return size;
}
 
int search_date(FILE *fp, const char * date)
{
    long i = 0, j = filesize(fp), k = j / 2;
    int done = 0, trouve = 0;
    time_t t_cible = string_to_time_t(date);
 
    while (!done)
    {
        time_t t;
 
        fseek(fp, k, SEEK_SET);
        goto_beginning_of_line(fp);
        t = get_date(fp);
 
        if (t_cible == t)
        {
            int c;
            trouve = 1;
            done = 1; /* On arrete puisqu'on a trouve */
            printf("Trouve : ");
            goto_beginning_of_line(fp);
            do
                putchar(c = getc(fp));
            while (c != _ENDOFLN && c != EOF);
        }
        else
        {
            if (t_cible < t)
                j = k;
            else
                i = k;
 
            k = (i + j) / 2;
        }
 
        if (!trouve)
            done = (abs(i - j) <= 1); /* On arrete lorsqu'on n'a plus rien entre i et j */
    }
 
    if (!trouve)
        printf("Pas trouve !");
 
    return trouve;
}
 
int main(int argc, char **argv)
{
    FILE *fp=fopen("log.txt","rb");
    if (fp==NULL)
        fprintf(stderr,"File can't be opened\n");
    else
    {
        search_date(fp,"Dec 11 12:00:00");
        fclose(fp);
    }
    return 0;
}

[elishac]

Merci beaucoup. Effectivement il est probablement plus simple d'utiliser des entiers qui comptent le nombre d'octets que de s'embrouiller avec les fichiers comme je l'ai fait.
J'ai deux petites questions : quelle est l'importante de rajouter static et const par rapport à ma solution ?

Sinon, mon problème majeur est que la fonction search_date que vous proposez ne fait pas exactement ce que je veux (car je me suis mal exprimé et car son nom n'est pas parlant).
Je voudrais certes qu'elle positionne le pointeur sur la date à chercher si elle existe dans le fichier. Mais si elle n'existe pas, je veux qu'elle pointe sur la date qui existe immédiatement après (par exemple, on cherche 42.7 dans les entiers, je veux pointer sur 43). Et si, en revanche, elle existe en doublons, je veux que fp pointe sur le premier (en partant du début du fichier) de ces doublons.
Comment pourrais-je modifier le code pour incorporer ces contraintes?

[Melem]

J'ai deux petites questions : quelle est l'importante de rajouter static et const par rapport à ma solution ?

- Une variable déclarée static dans une fonction est une variable globale qui n'est visible que dans la fonction (plus d'explications). Sans static, la variable est créée et détruite chaque fois qu'on entre puis quitte la fonction. Ca fait perdre du temps précieux non ?

- La présence de const indique au compilateur que les données pointées par le pointeur ne peuvent être que lues, c'est-à-dire qu'on ne peut pas les modifier. Cela permet d'éliminer certaines "tentations" par la suite (plus d'explications).

Sinon, mon problème majeur est que la fonction search_date que vous proposez ne fait pas exactement ce que je veux (car je me suis mal exprimé et car son nom n'est pas parlant).
Je voudrais certes qu'elle positionne le pointeur sur la date à chercher si elle existe dans le fichier. Mais si elle n'existe pas, je veux qu'elle pointe sur la date qui existe immédiatement après (par exemple, on cherche 42.7 dans les entiers, je veux pointer sur 43). Et si, en revanche, elle existe en doublons, je veux que fp pointe sur le premier (en partant du début du fichier) de ces doublons.
Comment pourrais-je modifier le code pour incorporer ces contraintes?

Non tu ne t'es pas mal exprimé. J'ai bien compris ce que tu voulais faire. Dans mon code, je me suis contenté d'afficher "Pas trouvee" si la date n'a pas été trouvée. Dans TON code, TU remplaces ce printf par ce que tu veux - afficher la date la plus proche par excès par exemple. Il faudra donc déjà que tu crées autant de variables que nécessaires pour stocker à tout moment les deux dernières dates encadrant la date à rechercher, ça te simplifiera la tâche. Tu devrais donc peut-être modifier le prototype de getdate en time_t get_date(FILE * fp, char date[16]), également pour te faciliter la tâche. Adapte donc la fonction à tes besoins et poste nous ton code quand tu auras fini, j'aurai encore deux ou trois mots à dire .

[souviron34]

j'ajouterais que, ayant déjà fait ce genre de recherche sur des fichiers de 600Mo ou plus, une recherche dichotomique correcte te trouve la bonne ligne dans un temps plus que raisonnable (de l'ordre d'un centième de seconde sur un Pentium 2 !!)

[elishac]

bonjour,

avant toute chose bonne année a tous.
me voici de nouveau pour essayer de terminer cette fonction.
j'ai essayé de faire ce qui manquait.
je me suis naturellement inspiré des conseils precedents et je remercie tout particulierement Melem pour son dernier message qui m'a ete fort utile.
je n'ai neanmoins pas fait du recopiage car cela ne m'aiderait pas. aussi, excusez moi si le resultat est moins bon que le message precedent, c'est simplement que je n'en ai pas compris toutes les subtilites.

Afin que vous n'ayez pas besoin de relire tous les messages précédents, je répète mon but : créer une fonction search_date qui cherche une date de la forme "Dec 18 00:00:20" dans un log où chaque ligne commence par une date de ce format. Voici les différents résultats que je souhaite obtenir :
* Si la date existe dans le log en un seul exemplaire, pointer sur le début de la ligne en question.
* Si elle existe en plusieurs exemplaires, pointer sur le début de ligne du premier de ces exemplaires.
* Si elle n'existe pas dans le log mais que des dates qui la précèdent et la succèdent existent dans le log, pointer sur la date existante directement après la date cherchée.
* Si elle est avant la première date du log, pointer sur le début du fichier.
* Si le fichier est vide, renvoyer un code d'erreur (1, par exemple, par opposition à 0 pour tous les cas précédents) et par homogénéité remettre par exemple le pointeur au début du fichier.
* Si elle est après la dernière date du log, renvoyer un code d' erreur (2, par exemple) et par homogénéité remettre par exemple le pointeur au début du fichier.

Voilà, je crois que j'ai tout dit. Voici ce que j'ai fait (ça plante pour l'instant).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
#include <stdio.h>
#include <string.h>
#include <time.h>
 
#define _ENDOFLINE '\n' /*Marque de fin de ligne*/
 
 
 
 
 
time_t string_to_time_t(const char *s)
{
        time_t rawtime;
        struct tm *timeinfo;
        char month_s[4] ;
        int month,day,hour,minute,second;
 
        if (sscanf(s, "%3s %d %d:%d:%d", month_s, &day, &hour, &minute, &second) != 5)
		fprintf(stderr,"Error 001: unknown date format\n");
	else
	{    
	        char *month_names[12] = {"Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"};
	        int i = 0;
	        while ( i < 12 &&  strcmp(month_s,month_names[i]) != 0 )
	                i++;
		if (i >= 12)
			 fprintf(stderr,"Error 002: unknown date format\n");
		else
		{			
	        month=i;
 
	        time (&rawtime);
	       	timeinfo=localtime(&rawtime);
	        timeinfo->tm_mon=month;
	        timeinfo->tm_mday=day;
	        timeinfo->tm_hour=hour;
	        timeinfo->tm_min=minute;
	        timeinfo->tm_sec=second;
	        return mktime(timeinfo);
		}
	}
}
 
 
 
 
 
time_t get_date(FILE *fp)
{
	static char s[16];
	return string_to_time_t(fgets(s,16,fp));
}
 
 
 
 
 
int goto_beginning_of_next_line(FILE *fp)
{
	int c;
	do
		c=fgetc(fp) ;
	while ((c != _ENDOFLINE) &&  (c != EOF));
	if (c == _ENDOFLINE)
		return 0;
	else
		return 1;
}
 
 
 
 
void goto_beginning_of_current_line(FILE *fp)
{
    int c = '\0' ;
 
    while (ftell(fp) != 0 && c != _ENDOFLINE)
    {
        fseek(fp,-1,SEEK_CUR);
	c=fgetc(fp); // c ne peut jamais être EOF ici, si ?
	if (c != _ENDOFLINE)
        	fseek(fp,-1,SEEK_CUR);
    }
}
 
 
 
long filesize(FILE * f)
{
    long pos, size;
 
    pos = ftell(f);
    fseek(f, 0, SEEK_END);
    size = ftell(f);
    fseek(f, pos, SEEK_SET);
 
    return size;
}
 
void goto_first_occurrence(FILE *fp, time_t t)
{
	time_t test = t;
	goto_beginning_of_current_line(fp);
	while (ftell(fp) != 0 && test == t)
	{
        	fseek(fp,-1,SEEK_CUR);
		goto_beginning_of_current_line(fp);
        	test=get_date(fp);
        	goto_beginning_of_current_line(fp);
	}
	if (test != t)
		goto_beginning_of_next_line;
}
 
int search_date(FILE *fp, time_t t_target)
{
	long min=0, max=filesize(fp), k= max/2;
	time_t t_min, t_max, t_test;
 
	if (max == 0)
	{
		fseek(fp,0,SEEK_SET);
		return 1;
	}
 
	fseek(fp,min,SEEK_SET);
	t_min=get_date(fp);
	fseek(fp,max,SEEK_SET);
	goto_beginning_of_current_line(fp);
	t_max=get_date(fp);
 
	if(t_target<t_min)
	{
		fseek(fp,0,SEEK_SET);
		return 0;
	}
	if(t_target>t_max)
	{
		fseek(fp,0,SEEK_SET);
		return 2;
	}	
 
	while (abs(max-min) > 1)
	{
		fseek(fp, k, SEEK_SET);
		goto_beginning_of_current_line(fp);
		t_test = get_date(fp);
		if(t_target == t_test)
		{
			goto_first_occurrence(fp,t_test);
			return 0;
		}
		else
		{
			if(t_target < t_test)
				max=k;
			else
				min=k;
			k = (min + max) / 2;
		}	
	}
	fseek(fp,max,SEEK_SET);
	return 0;
}	
 
 
int main(int argc, char **argv)
{
	FILE *fp = fopen("log","r");
	if (fp == NULL)
		fprintf(stderr,"File can't be opened\n");
	else
	{	
                time_t time=string_to_time_t("Jan 12 10:30:06");
	        search_date(fp,time);  // BUG
	        // affichage de la ligne obtenue :
	        int c; 
                do
        	        putchar(c = getc(fp));
                while (c != _ENDOFLINE && c != EOF);
	        fclose(fp);
	        return 0;
       }
}

[Melem]

FILE *fp = fopen("log","r");

Aucune chance de marcher. C'est "rb" et non "r". Déjà expliqué maintes fois.

Ensuite, tu as de nombreuses fonctions. As-tu déjà procédé à des tests unitaires ? Si tu ne les as pas encore fait, fais-les, identifie les fonctions qui ne font pas ce que tu souhaites, essaie de résoudre toi-même le problème si tu peux et si tu n'y arrives pas, reviens ici pour avoi de l'aide.

[elishac]

Bonjour,
Ah oui pardon, il s'agit d'un mauvais copier coller d'une vieille version car dans mon dernier fichier c'est bien rb. Ce n'est pas avec "r" que je l'ai testé, mais avec rb, et donc ça ne marche toujours pas.
Sinon, pour ce qui est de la recherche du problème, j'ai pris plusieurs semaines pour prendre mon temps d'écrire le code et de chercher les éventuelles erreurs. Je n'ai pas trouvé ce qui ne marchait pas.

Encore merci pour l'intérêt que vous apportez à mon problème, c'est grandement apprécié.